线性表的链式存储结构实验报告

1、.实验报告课程名称：数据结构与算法分析实验名称：链表的实现与应用实验日期：2015.01.30 班级： 数媒1401 姓名： 范业嘉 学号 1030514108 一、实验目的 掌握线性表的链式存储结构设计与基本操作的实现。二、实验内容与要求定义线性表的链式存储表示； 基于所设计的存储结构实现线性表的基本操作； 编写一个主程序对所实现的线性表进行测试；线性表的应用：设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用 线性表L3代表集合C；（选做）设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中

2、的数据元素也按值非递减有序排列。 设计一个一元多项式计算器，要求能够：输入并建立多项式；输出多项式；执行两个多项式相加；执行两个多项式相减；（选做）执行两个多项式相乘。三、数据结构设计 1.按所用指针的类型、个数、方法等的不同，又可分为： 线性链表（单链表） 静态链表 循环链表 双向链表 双向循环链表2.用一组任意的存储单元存储线性表中数据元素，用指针来表示数据元素间的逻辑关系。四、算法设计1.定义一个链表void creatlist(Linklist &L,int n)int i;Linklist p,s;L=(Linklist)malloc(sizeof(Lnode);p=L;L-next

3、=NULL;for(i=0;idata);s-next=NULL;p-next=s; p=s;2. （1）两个链表的合并void Mergelist(Linklist &La,Linklist &Lb,Linklist &Lc)Linklist pa,pb,pc;pa=La-next;pb=Lb-next;Lc=pc=La;while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;else pc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;free(Lb);（2） 两个链表的并集Linklist uni

4、onlist(Linklist &La,Linklist &Lb)Linklist p1,p2,head,q,s;int flag;head=q=(Linklist)malloc(sizeof(Lnode);p1=La-next;while(p1)flag=0;p2=Lb-next;while(p2)if(p1-data=p2-data)flag=1;break;p2=p2-next;if(flag=0)s=(Linklist)malloc(sizeof(Lnode);s-data=p1-data;q-next=s;q=s;p1=p1-next; q-next=Lb-next;return h

5、ead;3. （1）一元多项式的加法List addpoly(List pa,List pb) /一元多项式的加法int n;List pc,s,p;pa=pa-next;pb=pb-next;pc=(List)malloc(sizeof(struct Linklist);pc-next=NULL;p=pc;while(pa!=NULL&pb!=NULL)if(pa-expnpb-expn)s=(List)malloc(sizeof(struct Linklist);s-expn=pa-expn;s-coef=pa-coef;s-next=NULL;p-next=s;p=s;pa=pa-nex

6、t;else if(pa-expnexpn)s=(List)malloc(sizeof(struct Linklist);s-expn=pb-expn;s-coef=pb-coef;s-next=NULL;p-next=s;p=s;pb=pb-next;elsen=pa-coef+pb-coef;if(n!=0)s=(List)malloc(sizeof(struct Linklist);s-expn=pa-expn;s-coef=n;s-next=NULL;p-next=s;p=s;pb=pb-next;pa=pa-next;while(pa!=NULL)s=(List)malloc(siz

7、eof(struct Linklist);s-expn=pa-expn;s-coef=pa-coef;s-next=NULL;p-next=s;p=s;pa=pa-next;while(pb!=NULL)s=(List)malloc(sizeof(struct Linklist);s-expn=pb-expn;s-coef=pb-coef;s-next=NULL;p-next=s;p=s;pb=pb-next;return pc;（2） 一元多项式的减法List subpoly(List pa,List pb) /一元多项式的减法int n;List pc,s,p;pa=pa-next;pb=

8、pb-next;pc=(List)malloc(sizeof(struct Linklist);pc-next=NULL;p=pc;while(pa!=NULL&pb!=NULL)if(pa-expnpb-expn)s=(List)malloc(sizeof(struct Linklist);s-expn=pa-expn;s-coef=pa-coef;s-next=NULL;p-next=s;p=s;pa=pa-next;else if(pa-expnexpn)s=(List)malloc(sizeof(struct Linklist);s-expn=pb-expn;s-coef=-pb-co

9、ef;s-next=NULL;p-next=s;p=s;pb=pb-next;elsen=pa-coef-pb-coef;if(n!=0)s=(List)malloc(sizeof(struct Linklist);s-expn=pa-expn;s-coef=n;s-next=NULL;p-next=s;p=s;pb=pb-next;pa=pa-next;while(pa!=NULL)s=(List)malloc(sizeof(struct Linklist);s-expn=pa-expn;s-coef=pa-coef;s-next=NULL;p-next=s;p=s;pa=pa-next;w

10、hile(pb!=NULL)s=(List)malloc(sizeof(struct Linklist);s-expn=pb-expn;s-coef=-pb-coef;s-next=NULL;p-next=s;p=s;pb=pb-next;return pc;（3） 一元多项式的乘法void mulpolyn(polynomail pa,polynomail pb,polynomail &pc) LNode *p,*q,*s,*hc;p=pa-next;q=pb-next;hc=pc;while(p!=NULL) while(q!=NULL) s=(polynomail)malloc(sizeof(LNode);hc-next=s;hc=hc-next;hc-coef=q-coef*p-coef;hc-expn=q-expn+p-expn;q=q-next;p=p-next;q=pb-next;hc-next=NULL;5、 测试结果2.3.六、心得体会（包括对于本次实验的小结，实验过程中碰到的问题等） 1.首先书上给的链表输入是倒序的，写的时候想都没想就抄上去了，结果运行时发现问题，可是上网百度依然没有把问题解决，导致最后输出链表倒序的，并且链表的合并并集依旧是倒序的。 2.当写一元多项式的加减时，前提