数学与软件科学学院实验报告一、实验目的及要求(1)熟练掌握线性表ADT和相关算法描述、基本程序实现结构；(2)以线性表的基本操作为基础实现相应的程序；(3)掌握线性表的顺序存储结构和动态存储结构之区分。二、实验内容(1)一元多项式运算的C语言程序实现(加法必做，其它选做)；(2)有序表的合并；(3)集合的并、交、补运算；(4)约瑟夫问题的求解。三、实验准备：1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。四、实验步骤(该部分不够填写.请填写附页)1.录入程序代码并进行调试和算法分析；2.编写实验报告。<一>对实验问题的描述：利用线性表的动态分配顺序存储结构实现有序表的合并，线性表的长度可变，且所需的最大存储空间随问题的改变而变，在C语言中可用动态分配的一维数组表示。根据一元多项式相加的规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成和多项式中的一项；对于两个和多项式中指数不相同的项，则分别复抄到和多项式中去。<二>算法的数据结构有序表的合并数据结构定义如下：#defineLIST_INIT_SIZE100/*线性表存储空间的初始分配量*/#defineLISTINCREMENT10/*线性表存储空间的分配增量*/typedefstruct{ElemType*elem;/*存储空间基址*/intlength;/*当前长度*/intlistsize;/*当前分配的存储容量（以sizeof(ElemType)为单位）*/}SqList;一元多项式的加法实现：数据结构定义如下：typedefstructpolynode/*用单链表存储多项式的结点结构*/{intcoef;/*多项式的系数*/intexp;/*多项式的指数*/structpolynode*next;}node;<三>算法基本操作的说明及分析有序表的合并<1>，构造一个空线性表的算法实现：StatusInitList_sq(SqList*A){A->elem=(ElemType\*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!A->elem)returnERROR;/*存储分配失败*/A->length=0;/*空表长度为0*/A->listsize=LIST_INIT_SIZE;/*初始存储容量*/returnOK;}//InitList_sq<2>,输入顺序表的值，并输出，算法实现如下：intInput_Sq(SqList*L){inti;if(L->length==0)printf("TheListisempty!");else{for(i=0;i<L->length;i++)printf("%d",L->elem[i]);}printf("\n");returnOK;}<3>，顺序表的合并，算法实现如下：SqListMergeList_Sq(SqListA,SqListB,SqListC)/*A,B,C的值均按照非递减的顺序排列*/{ElemType*pa,*pb,*pc,*pa_last,*pb_last;pa=A.elem;pb=B.elem;C.listsize=C.length=A.length+B.length;pc=C.elem=(ElemType*)malloc(C.listsize*sizeof(ElemType));if(!C.elem)exit(ERROR);/*存储分配失败*/pa_last=A.elem+A.length-1;pb_last=B.elem+B.length-1;while((pa<pa_last)&&(pb<pb_last)){if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;}while(pa<=pa_last)*pc++=*pa++;while(pb<=pb_last)*pc++=*pb++;returnC;}一元多项式的加法相关操作的算法实现：<1>，多项式的建立，算法实现如下：create(void){node*h,*r,*s;intc,e;h=(node*)malloc(sizeof(node));/*建立多项式的头结点，为头结点分配存储空间*/r=h;/*r指针动态指向链表的当前表尾，其初值指向头结点*/printf("coef:");scanf("%d",&c);/*输入系数*/printf("exp:");scanf("%d",&e);/*输