1數(shù)據(jù)結(jié)構(gòu)-實(shí)驗(yàn)報(bào)告一(線性表的基本操作)

PAGEPAGE7數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)一線性表的基本操作及其應(yīng)用專業(yè)信息與計(jì)算科學(xué)班級(jí)1301學(xué)號(hào)33姓名蔣豐沛指導(dǎo)教師劉長(zhǎng)松2015年4月22日實(shí)驗(yàn)基本格式一、實(shí)驗(yàn)?zāi)康亩?shí)驗(yàn)內(nèi)容和要求三、源代碼四、測(cè)試結(jié)果五、心得體會(huì)實(shí)驗(yàn)一線性表的基本操作及其應(yīng)用一、實(shí)驗(yàn)?zāi)康?、幫助讀者復(fù)習(xí)C++語(yǔ)言程序設(shè)計(jì)中的知識(shí)。2、熟悉線性表的邏輯結(jié)構(gòu)。3、熟悉線性表的基本運(yùn)算在兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。4、掌握順序表的存儲(chǔ)結(jié)構(gòu)形式及其描述和基本運(yùn)算的實(shí)現(xiàn)。5、熟練掌握動(dòng)態(tài)鏈表結(jié)構(gòu)及有關(guān)算法的設(shè)計(jì)二、實(shí)驗(yàn)內(nèi)容求兩個(gè)多項(xiàng)式的相加運(yùn)算[問(wèn)題描述]用單鏈表存儲(chǔ)一元多項(xiàng)式，并實(shí)現(xiàn)兩個(gè)多項(xiàng)式的相加運(yùn)算。[基本要求]（1）本程序需要基于線性表的基本操作來(lái)實(shí)現(xiàn)一元多項(xiàng)式的加法，也可以用數(shù)組實(shí)現(xiàn)。；（2）兩個(gè)多項(xiàng)式都有鍵盤輸入相應(yīng)的系數(shù)和指數(shù)[測(cè)試數(shù)據(jù)]由學(xué)生任意指定。三、源代碼//文件名:exp2-7.cpp#include<stdio.h>#include<malloc.h>#defineMAX20 //多項(xiàng)式最多項(xiàng)數(shù)typedefstruct //定義存放多項(xiàng)式的數(shù)組類型{ doublecoef; //系數(shù) intexp; //指數(shù)}PolyArray[MAX];typedefstructpnode //定義單鏈表結(jié)點(diǎn)類型{ doublecoef; //系數(shù) intexp; //指數(shù) structpnode*next;}PolyNode;voidDispPoly(PolyNode*L) //輸出多項(xiàng)式{ boolfirst=true; //first為true表示是第一項(xiàng) PolyNode*p=L->next; while(p!=NULL) { if(first) first=false; elseif(p->coef>0) printf("+"); if(p->exp==0) printf("%g",p->coef); elseif(p->exp==1) printf("%gx",p->coef); else printf("%gx^%d",p->coef,p->exp); p=p->next; } printf("\n");}voidDestroyList(PolyNode*&L) //銷毀單鏈表{ PolyNode*p=L,*q=p->next; while(q!=NULL) { free(p); p=q; q=p->next; } free(p);}voidCreateListR(PolyNode*&L,PolyArraya,intn)//尾插法建表{ PolyNode*s,*r;inti; L=(PolyNode*)malloc(sizeof(PolyNode)); //創(chuàng)建頭結(jié)點(diǎn) L->next=NULL; r=L; //r始終指向終端結(jié)點(diǎn),開(kāi)始時(shí)指向頭結(jié)點(diǎn) for(i=0;i<n;i++) { s=(PolyNode*)malloc(sizeof(PolyNode));//創(chuàng)建新結(jié)點(diǎn) s->coef=a[i].coef; s->exp=a[i].exp; r->next=s; //將*s插入*r之后 r=s; } r->next=NULL; //終端結(jié)點(diǎn)next域置為NULL}voidSort(PolyNode*&head) //按exp域遞減排序{ PolyNode*p=head->next,*q,*r; if(p!=NULL) //若原單鏈表中有一個(gè)或以上的數(shù)據(jù)結(jié)點(diǎn) { r=p->next; //r保存*p結(jié)點(diǎn)后繼結(jié)點(diǎn)的指針 p->next=NULL; //構(gòu)造只含一個(gè)數(shù)據(jù)結(jié)點(diǎn)的有序表 p=r; while(p!=NULL) { r=p->next; //r保存*p結(jié)點(diǎn)后繼結(jié)點(diǎn)的指針 q=head; while(q->next!=NULL&&q->next->exp>p->exp) q=q->next; //在有序表中找插入*p的前驅(qū)結(jié)點(diǎn)*q p->next=q->next; //將*p插入到*q之后 q->next=p; p=r; } }}voidAdd(PolyNode*ha,PolyNode*hb,PolyNode*&hc)//求兩有序集合的并{ PolyNode*pa=ha->next,*pb=hb->next,*s,*tc; doublec; hc=(PolyNode*)malloc(sizeof(PolyNode)); //創(chuàng)建頭結(jié)點(diǎn) tc=hc; while(pa!=NULL&&pb!=NULL) { if(pa->exp>pb->exp) { s=(PolyNode*)malloc(sizeof(PolyNode)); //復(fù)制結(jié)點(diǎn) s->exp=pa->exp;s->coef=pa->coef; tc->next=s;tc=s; pa=pa->next; } elseif(pa->exp<pb->exp) { s=(PolyNode*)malloc(sizeof(PolyNode)); //復(fù)制結(jié)點(diǎn) s->exp=pb->exp;s->coef=pb->coef; tc->next=s;tc=s; pb=pb->next; } else //pa->exp=pb->exp { c=pa->coef+pb->coef; if(c!=0) //系數(shù)之和不為0時(shí)創(chuàng)建新結(jié)點(diǎn) { s=(PolyNode*)malloc(sizeof(PolyNode)); //復(fù)制結(jié)點(diǎn) s->exp=pa->exp;s->coef=c; tc->next=s;tc=s; } pa=pa->next; pb=pb->next; } } if(pb!=NULL)pa=pb; //復(fù)制余下的結(jié)點(diǎn) while(pa!=NULL) { s=(PolyNode*)malloc(sizeof(PolyNode)); //復(fù)制結(jié)點(diǎn) s->exp=pa->exp;s->coef=pa->coef; tc->next=s;tc=s; pa=pa->next; } tc->next=NULL;}voidmain(){ PolyNode*ha,*hb,*hc; PolyArraya={{1.2,0},{2.5,1},{3.2,3},{-2.5,5}}; PolyArrayb={{-1.2,0},{2.5,1},{3.2,3},{2.5,5},{5.4,10}}; CreateListR(ha,a,4); CreateListR(hb,b,5); printf("原多項(xiàng)式A:");DispPoly(ha); printf("原多項(xiàng)式B:");DispPoly(hb); Sort(ha); Sort(hb); printf("有序多項(xiàng)式A:");DispPoly(ha); printf("有序多項(xiàng)式B:");DispPoly(hb); Add