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

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

2、能够：输入并建立多项式；输出多项式；执行两个多项式相加；执行两个多项式相减；(选做)执行两个多项式相乘。三、数据结构设计1.按所用指针的类型、个数、方法等的不同，又可分为：线性链表(单链表)静态链表循环链表双向链表双向循环链表2.用一组任意的存储单元存储线性表中数据元素，用指针来表示数据元素间的逻辑关系。四、算法设计1 .定义一个链表voidcreatlist(Linklist&L,intn)inti;Linklistp,s;L=(Linklist)malloc(sizeof(Lnode);P=L;L->next=NULL;for(i=0;i<n;i+)s=(Linklis

3、t)malloc(sizeof(Lnode);scanf("%d",&s->data);s->next=NULL;p->next=s;p=s;2. (1)两个链表的合并voidMergelist(Linklist&La,Linklist&Lb,Linklist&Lc)Linklistpa,pb,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb)if(pa->data<=pb->data)pc->next=pa;pc=pa;pa

4、=pa->next;elsepc->next=pb;pc=pb;pb=pb->next;pc->next=pa?pa:pb;free(Lb);(2)两个链表的并集Linklistunionlist(Linklist&La,Linklist&Lb)Linklistp1,p2,head,q,s;intflag;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

5、;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;returnhead;3. (1)一元多项式的加法Listaddpoly(Listpa,Listpb)/一元多项式的加法intn;Listpc,s,p;pa=pa->next;pb=pb->next;pc=(List)malloc(sizeof(structLinklist);pc->next=

6、NULL;p=pc;while(pa!=NULL&&pb!=NULL)if(pa->expn>pb->expn)s=(List)malloc(sizeof(structLinklist);s->expn=pa->expn;s->coef=pa->coef;s->next=NULL;p->next=s;p=s;pa=pa->next;elseif(pa->expn<pb->expn)s=(List)malloc(sizeof(structLinklist);s->expn=pb->expn;

7、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(structLinklist);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(structLinklist);s

8、->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(structLinklist);s->expn=pb->expn;s->coef=pb->coef;s->next=NULL;p->next=s;p=s;pb=pb->next;returnpc;(2)一元多项式的减法Listsubpoly(Listpa,Listpb)/一元多项式的减法intn;

9、Listpc,s,p;pa=pa->next;pb=pb->next;pc=(List)malloc(sizeof(structLinklist);pc->next=NULL;p=pc;while(pa!=NULL&&pb!=NULL)if(pa->expn>pb->expn)s=(List)malloc(sizeof(structLinklist);s->expn=pa->expn;s->coef=pa->coef;s->next=NULL;p->next=s;p=s;pa=pa->next;)el

10、seif(pa->expn<pb->expn)(s=(List)malloc(sizeof(structLinklist);s->expn=pb->expn;s->coef=-pb->coef;s->next=NULL;p->next=s;p=s;pb=pb->next;)else(n=pa->coef-pb->coef;if(n!=0)(s=(List)malloc(sizeof(structLinklist);s->expn=pa->expn;s->coef=n;s->next=NULL;p-&

11、gt;next=s;p=s;)pb=pb->next;pa=pa->next;)while(pa!=NULL)(s=(List)malloc(sizeof(structLinklist);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(structLinklist);s->expn=pb->expn;s->coef=-pb->coef;s-&g

12、t;next=NULL;p->next=s;p=s;pb=pb->next;returnpc;(3)一元多项式的乘法voidmulpolyn(polynomailpa,polynomailpb,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;五、测试结果7表表链链y锥槌ssanLaLb售.出出集并eS91'押开合喋2.3.六、心得体会（包括对于本次实验的小结，实验过程中碰到的问题等）1 .首先书上给的链表输入是倒序的，写的时候想都没想就抄上去了，结果运行时发现问题，可是上网百度依然没有把问题解决，导致最后输出链表倒