数据结构实验二线性表 [复制链接]

一、实验目的

掌握线性表的逻辑结构；顺序表和链表的基本操作的实现；掌握利用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;}

五、实验心得体会

学习到有关链表的知识，体会到链表在增加和删除的方便性。

了解科技资讯，更可获得实用技巧。