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

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