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 .首先書上給的鏈表輸入是倒序的，寫的時候想都沒想就抄上去了，結果運行時發現問題，可是上網百度依然沒有把問題解決，導致最后輸出鏈表倒