一、实验目的
掌握线性表的逻辑结构；顺序表和链表的基本操作的实现；掌握利用C/C++编程语言实现数据结构的编程方法；通过上机时间加强利用数据结构解决实际应用问题的能力；二、实验相关知识
线性表的顺序存储结构的实现；线性表的链式存储结构的实现；线性表的应用——一元多项式的表示及相加。三、实验内容与要求
1.利用顺序表或链表表示两个一元多项式，并完成两多项式的乘法运算。按指数的升序输入两个一元多项式polya与polyb各项的指数和系数，且以输入00结束。输出两一元多项式乘积的一元多项式polyc，并进行算法时间复杂度的分析
例1：(2+3x-3x4)*(4x2+6x6)=(8x2+12x3+18x7-18x10)
输入-32-输出--12在给出的代码素材polymul.cpp文件中补充完整以下函数，实现多项式相乘的计算。
voidpolyadd(Polylistpoly,intcoef,intexp)
voidpolymul(Polylistpolya,Polylistpolyb,Polylistpolyc)
2.利用循环单链表求解约瑟夫环问题（即n个人围成一个圆圈，然后从第一个人开始，按：1,2,3,…,m报数，数到m的人出圈，并有出圈者的下一个人重新开始报数，数到m又要出圈，如此类推，直到所有人都出圈，打印出圈的次序，其中n和m为输入数据）
输入输出3,6,9,4,8,5,2,7,在给出的代码素材josephus.cppp文件中补充完整以下函数，求解约瑟夫环中出列的人的编号。
linkcreatlink(intn)//创建值为1~n的n个结点的不带头结点的循环单链表
voidjosephus(linkjoselink,intn,intm)//用循环链表求解约瑟夫环
Node*move(Node*p,inti)//p指针向前走i步
四、程序代码及运行结果
1、
voidpolyadd(Polylistpoly,intcoef,intexp){ Polylists; s=(Polynode*)malloc(sizeof(Polynode)); s-coef=coef; s-exp=exp; Polynode*p; p=poly-next; boolflag=false; while(p!=NULL) { if(p-exp==exp) { p-coef+=coef; flag=true; break; } p=p-next; } if(flag==false) { s-next=poly-next; poly-next=s; }}voidpolymul(Polylistpolya,Polylistpolyb,Polylistpolyc){ Polynode*p=polya-next; while(p!=NULL) { polyadd(polyc,p-coef,p-exp); p=p-next; } p=polyb-next; while(p!=NULL) { polyadd(polyc,p-coef,p-exp); p=p-next; }}
T=O(n3)
2、
linkcreatlink(intn){ linkjoselink,current,s; joselink=(Node*)malloc(sizeof(Node)); current=(Node*)malloc(sizeof(Node)); current=joselink; joselink-next=NULL; joselink-data=1; while(current-datan) { s=(Node*)malloc(sizeof(Node)); s-data=current-data+1; current-next=s; current=current-next; } current-next=joselink; returnjoselink;}voidjosephus(linkjoselink,intn,intm){ linkp; p=(Node*)malloc(sizeof(Node)); p-next=joselink; inti=0; for(;p-next!=NULL;p=p-next) { i++; if(i%m==0) { i=1; printf(%d,p-next-data); p-next=p-next-next; } if(p-next==p) { printf(%d,p-data); return; } }}Node*move(Node*p,inti){ linkstart=p; while(i--) { p=p-next; } returnp;}
五、实验心得体会
学习到有关链表的知识，体会到链表在增加和删除的方便性。
了解科技资讯，更可获得实用技巧。