線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

1、實(shí)驗(yàn)報(bào)告課程名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)與算法分析實(shí)驗(yàn)名稱(chēng)：鏈表的實(shí)現(xiàn)與應(yīng)用實(shí)驗(yàn)日期：班級(jí)：數(shù)媒1401姓名:范業(yè)嘉學(xué)號(hào)一、實(shí)驗(yàn)?zāi)康恼莆站€(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)設(shè)計(jì)與基本操作的實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容與要求定義線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)表示；基于所設(shè)計(jì)的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線(xiàn)性表的基本操作；編寫(xiě)一個(gè)主程序?qū)λ鶎?shí)現(xiàn)的線(xiàn)性表進(jìn)行測(cè)試；線(xiàn)性表的應(yīng)用：設(shè)線(xiàn)性表L1和L2分別代表集合A和B,試設(shè)計(jì)算法求A和B的并集C,并用線(xiàn)性表L3代表集合C;(選做)設(shè)線(xiàn)性表L1和L2中的數(shù)據(jù)元素為整數(shù)，且均已按值非遞減有序排列，試設(shè)方t算法對(duì)L1和L2進(jìn)行合并，用線(xiàn)性表L3保存合并結(jié)果，要求L3中的數(shù)據(jù)元素也按值非遞減有序排列。設(shè)計(jì)一個(gè)一元多項(xiàng)式計(jì)算器，要求

2、能夠：輸入并建立多項(xiàng)式；輸出多項(xiàng)式；執(zhí)行兩個(gè)多項(xiàng)式相加；執(zhí)行兩個(gè)多項(xiàng)式相減；(選做)執(zhí)行兩個(gè)多項(xiàng)式相乘。三、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)1.按所用指針的類(lèi)型、個(gè)數(shù)、方法等的不同，又可分為：線(xiàn)性鏈表(單鏈表)靜態(tài)鏈表循環(huán)鏈表雙向鏈表雙向循環(huán)鏈表2.用一組任意的存儲(chǔ)單元存儲(chǔ)線(xiàn)性表中數(shù)據(jù)元素，用指針來(lái)表示數(shù)據(jù)元素間的邏輯關(guān)系。四、算法設(shè)計(jì)1 .定義一個(gè)鏈表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)兩個(gè)鏈表的合并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)兩個(gè)鏈表的并集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)一元多項(xiàng)式的加法Listaddpoly(Listpa,Listpb)/一元多項(xiàng)式的加法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)一元多項(xiàng)式的減法Listsubpoly(Listpa,Listpb)/一元多項(xiàng)式的減法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)一元多項(xiàng)式的乘法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;五、測(cè)試結(jié)果7表表鏈鏈y(cè)錐槌ssanLaLb售.出出集并eS91'押開(kāi)合喋2.3.六、心得體會(huì)（包括對(duì)于本次實(shí)驗(yàn)的小結(jié)，實(shí)驗(yàn)過(guò)程中碰到的問(wèn)題等）1 .首先書(shū)上給的鏈表輸入是倒序的，寫(xiě)的時(shí)候想都沒(méi)想就抄上去了，結(jié)果運(yùn)行時(shí)發(fā)現(xiàn)問(wèn)題，可是上網(wǎng)百度依然沒(méi)有把問(wèn)題解決，導(dǎo)致最后輸出鏈表倒