簡單介紹：本次作業(yè)力在學(xué)會鏈表表示線性表的插入、刪除、查找等基本操作設(shè)計與實現(xiàn)，學(xué)習(xí)利用鏈表提供的接口去求解實際問題，同時熟悉鏈表的的存儲方法。再基于線性鏈表的基礎(chǔ)設(shè)計完成多項式的相加運算程序。一、 實驗?zāi)康暮鸵笸瓿啥囗検降南嗉印⑾喑诉\算。（1）掌握線性表的插入、刪除、查找等基本操作設(shè)計與實現(xiàn)（2）學(xué)習(xí)利用線性表提供的接口去求解實際問題（3）熟悉線性表的的存儲方法二、 實驗內(nèi)容和原理1.實驗內(nèi)容設(shè)計一個一元多項式的簡單計算程序，其基本功能有：（1）輸入并建立多項式；（2）輸出多項式；（3）多項式的相加運算。利用單鏈表實現(xiàn)。2.實驗原理使用單鏈表實現(xiàn)一元多項式的存儲，并實現(xiàn)兩個一元多項式的加法運算。三、 實驗環(huán)境硬件：（1）學(xué)生用微機(jī)（2）多媒體教室或遠(yuǎn)程教學(xué)（3）局域網(wǎng)環(huán)境軟件：（1）Windows XP中文操作系統(tǒng) （2）VC6.0四、 算法描述及實驗步驟1、 描述：加法：輸入建立一元多項式,進(jìn)行簡單加法運算,輸出結(jié)果；通過建立單鏈表A和B分別存放多項式的a和b的各項系數(shù)及指數(shù)；并且利用A使得不產(chǎn)生新的節(jié)點而在A中存放數(shù)據(jù)運算結(jié)果；該過程通過定義指針變量p和q使它們分別指向兩個多項式的第一個節(jié)點，之后依次比較它們所指向的項的指數(shù)，即一種情況指數(shù)相等時系數(shù)相加且和不為零，修改當(dāng)前p所指項的系數(shù)（和），同時刪除q所指項，若和為零則同時刪除p和q各自所指；情況二，p當(dāng)前項指數(shù)大于q當(dāng)前項，將q所指插入p所指之前作為結(jié)果項之一；情況三，p當(dāng)前項指數(shù)小于q當(dāng)前項，p所指作為多項式和的一項，移動p指向下一項，進(jìn)行比較，在移動p，q至其中以個鏈空，把另一個鏈余下節(jié)點插在p所指之后；乘法：定義指針p,q指向所操作節(jié)點，通過A鏈表的每一項與B鏈表各項相乘，指數(shù)相加，系數(shù)相乘，將值賦給新節(jié)點各自域，構(gòu)成一新的鏈表，最后返回頭結(jié)點。可這樣有一個問題，即新生成的鏈表，即最終結(jié)果混亂，沒有對數(shù)據(jù)進(jìn)行過濾，相同指數(shù)項應(yīng)在執(zhí)行加法運算，所以可以這樣實現(xiàn)，通過A鏈表的每一項與B鏈表各項相乘的新生成節(jié)點單獨構(gòu)成一鏈表，并將第一個鏈表加入另一新鏈表，循環(huán)此操作將后生成的鏈表加之先前的鏈表，即可實現(xiàn)排序問題。1）加法算法如下：polynomial * polyadd(polynomial *A,polynomial *B)polynomial *p,*q,*s,*r;float x;p=A-next;q=B-next;s=p;while(p!=NULL)&(q!=NULL)if(p-exp)(q-exp)r=q-next;q-next=p;s-next=q; s=q;q=r;else if(p-exp)exp)s=p;p=p-next;elsex=(p-coef)+(q-coef);/*if(x!=0)p-coef=x;s=p;elses-next=p-next;free(p);*/p=s-next;r=q;q=q-next;free(r); if(q!=NULL)s-next=q;free(B); return A;2） 乘法算法polynomial * polyand(polynomial *A,polynomial *B) /*核心算法實現(xiàn)兩鏈表的乘法運算*/polynomial * p,* q,* n,* head,* r,* temp,* m; /定義當(dāng)前指針p，q風(fēng)別指向兩鏈表和頭指針，尾指針，及新生成節(jié)點n int exp; /定義整型指數(shù)float coef; /定義浮點型系數(shù)head=(polynomial *)malloc(sizeof(polynomial); /創(chuàng)頭節(jié)點為新生鏈表準(zhǔn)備head-next=NULL; /置空鏈表 r=head; /臨時變量，為后移指針做準(zhǔn)備p=A-next; /當(dāng)前指針跳過A鏈表頭指向?qū)嶋H運算數(shù)while(p!=NULL) /控制操作，循環(huán)A鏈表與內(nèi)部while所控制B鏈表進(jìn)行項之間的運算 temp=(polynomial *)malloc(sizeof(polynomial); /在內(nèi)部創(chuàng)頭節(jié)點為新生鏈表準(zhǔn)備 即A中每一項與B中各項相乘構(gòu)成一新鏈表 temp-next=NULL; /置空鏈表 m=temp; /臨時變量，為后移指針做準(zhǔn)備q=B-next; /當(dāng)前指針跳過B鏈表頭指向?qū)嶋H運算數(shù)while(q!=NULL) n=(polynomial *)malloc(sizeof(polynomial); /建立新節(jié)點exp=p-exp+q-exp; /進(jìn)行系數(shù)相加操作 coef=p-coef*q-coef; / /進(jìn)行指數(shù)相乘操作n-coef=coef; /賦值新節(jié)點的系數(shù)域n-exp=exp; /賦值新節(jié)點的指數(shù)域 m-next=n; /鏈接節(jié)點至頭結(jié)點，構(gòu)成鏈表m=m-next; /后移指針，為下一節(jié)點做準(zhǔn)備q=q-next; /控制B鏈表下一項/printf(%f %d ,coef,exp); /調(diào)試用p=p-next; /控制A鏈表下一項m-next=NULL; /鏈表尾置空/head=head-next;polyadd(head,temp); /return head; 2、1）加法算法流程圖polynomial *p,*q,*s,*r; float x;p=A-next;q=B-next;s=p;Y (p-exp)(q-exp) Nr=q-next;s-next=q;free(B);return A;p=s-next;r=q;q=q-next;free(r);x=(p-coef)+(q-coef);q-next=p;s-next=q;Y x！=0 Ns=q; (p-exp)exp)N Y(p!=NULL)&(q!=NULL)q=r;p-coef=x;s=p;s-next=p-next;free(p);s=p;p=p-next; q!=NULLY 2）乘法算法流程圖polynomial * p,* q,* n,* head,* r,* temp,* m;int exp；float coef；head=(polynomial *)malloc(sizeof(polynomial); head-next=NULL;p=A-next;temp=(polynomial *)malloc(sizeof(polynomial);temp-next=NULL; m=temp;q=B-next;n=(polynomial *)malloc(sizeof(polynomial);exp=p-exp+q-exp; coef=p-coef*q-coef; n-coef=coef; n-exp=exp; m-next=n; m=m-next; q=q-next;p!=NULL;q!=NULL;p=p-next; m-next=NULL; polyadd(head,temp);return head;3、 代碼(注釋)#include stdio.h#include malloc.htypedef struct linknode /*定義節(jié)點*/float coef;int exp;struct linknode * next;polynomial;polynomial * creatlist() /*創(chuàng)建單鏈表*/float x; /*節(jié)點中存放項系數(shù)和指數(shù)*/int z;polynomial *head,*r,*n; /*下指針,分別是頭指針、尾指針和新建立節(jié)點的指針*/head=(polynomial *)malloc(sizeof(polynomial); /*malloc分配內(nèi)存單元給頭指針申請空間*/head-next=NULL; /*頭指針next指向空位空鏈表狀態(tài)*/r=head; printf(建立一元多項式:(以系數(shù)0結(jié)束)n);/*打印文字提醒用戶輸入*/while(x!=0) /*建立單鏈表*/n=(polynomial *)malloc(sizeof(polynomial); /*建立新節(jié)點,將用戶輸入的數(shù)據(jù)分別作為項(各節(jié)點)的系數(shù)和指數(shù)*/n-coef=x;n-exp=z;r-next=n; /*為指針指向下一新建節(jié)點*/r=r-next; /*后移尾指針*/r=n;printf(請按升冪輸入系數(shù)和指數(shù):); scanf(%f%d,&x,&z);r-next=NULL;head=head-next; /*鏈接節(jié)點使之勾成鏈表*/return (head); /*還回head指針(鏈表頭標(biāo)志或是說地址)給函數(shù)調(diào)用者*/void print(polynomial * head) /*打印輸出函數(shù)*/polynomial *p; /*為傳入的鏈表設(shè)立當(dāng)前指針*/p=head-next; /*將指針后移指向包含實際數(shù)據(jù)的節(jié)點*/while(p!=NULL) /*判斷需要打印的鏈表是否為空*/printf(%.2fX(%d) ,p-coef,p-exp);/*打印當(dāng)前指針?biāo)疙椀臄?shù)據(jù)*/p=p-next; /*后移指針指向下一節(jié)點*/printf(n); polynomial * polyadd(polynomial *A,polynomial *B) /*核心算法實現(xiàn)兩鏈表的加法運算并將結(jié)果保存在A中*/polynomial *p,*q,*s,*r; /*為鏈表設(shè)立指針分別指向鏈表A和鏈表B(多項式A和B)，s為臨時存放為后續(xù)移動指針做地址保留*/float x;p=A-next;q=B-next;s=A;/*/ /*s作為p的前驅(qū)*/while(p!=NULL)&(q!=NULL) /*判斷所比較鏈表是否為空不同時為空時反復(fù)執(zhí)行下列函數(shù)*/if(p-exp)(q-exp) /*將q插入p之前*/ r=q-next; /*保存當(dāng)前q的下一結(jié)點地址為r后移作準(zhǔn)備*/q-next=p; /*將p接到到q之后*/s-next=q; /*將q徹底的插入到A鏈表中p之前作為結(jié)果項之一*/ s=q; /*修改當(dāng)前指針為下一節(jié)點作比較準(zhǔn)備*/q=r;else if(p-exp)exp) /*將p作為結(jié)果項之一，后移p進(jìn)行下一結(jié)點比較*/s=p; /*后移s*/p=p-next; /*后移當(dāng)前指針p指向下一節(jié)點*/else /*當(dāng)前鏈表中節(jié)點的指數(shù)相等進(jìn)行系數(shù)加法運算*/x=(p-coef)+(q-coef); /*實現(xiàn)系數(shù)相加賦給x，節(jié)點中的系數(shù)單元*/ if(x!=0) /*判斷系數(shù)和是否為零,不為零執(zhí)行系數(shù)替換原有數(shù)據(jù)*/p-coef=x;s=p; /*p的前驅(qū)指針后移*/else /*系數(shù)和為零*/s-next=p-next; /*為釋放p準(zhǔn)備*/free(p);p=s-next; /*p指針指向下一節(jié)點*/ r=q; /*為釋放q作準(zhǔn)備*/q=q-next; /*q 指向下一節(jié)點*/free(r); if(q!=NULL) /*循環(huán)結(jié)束將q中剩余節(jié)點直接插入p的為節(jié)點之后作為結(jié)果項*/ s-next=q;free(B); /*運算結(jié)束釋放B鏈鎖占空間*/ return A; /*還回A鏈給函數(shù)調(diào)用者*/ polynomial * polyand(polynomial *A,polynomial *B) /*核心算法實現(xiàn)兩鏈表的乘法運算*/polynomial * p,* q,* n,* head,* r,* temp,* m; /定義當(dāng)前指針p，q風(fēng)別指向兩鏈表和頭指針，尾指針，及新生成節(jié)點n int exp; /定義整型指數(shù)float coef; /定義浮點型系數(shù)head=(polynomial *)malloc(sizeof(polynomial); /創(chuàng)頭節(jié)點為新生鏈表準(zhǔn)備head-next=NULL; /置空鏈表 r=head; /臨時變量，為后移指針做準(zhǔn)備p=A-next; /當(dāng)前指針跳過A鏈表頭指向?qū)嶋H運算數(shù)while(p!=NULL) /控制操作，循環(huán)A鏈表與內(nèi)部while所控制B鏈表進(jìn)行項之間的運算 temp=(polynomial *)malloc(sizeof(polynomial); /在內(nèi)部創(chuàng)頭節(jié)點為新生鏈表準(zhǔn)備 即A中每一項與B中各項相乘構(gòu)成一新鏈表 temp-next=NULL; /置空鏈表 m=temp; /臨時變量，為后移指針做準(zhǔn)備q=B-next; /當(dāng)前指針跳過B鏈表頭指向?qū)嶋H運算數(shù)while(q!=NULL) n=(polynomial *)malloc(sizeof(polynomial); /建立新節(jié)點exp=p-exp+q-exp; /進(jìn)行系數(shù)相加操作 coef=p-coef*q-coef; / /進(jìn)行指數(shù)相乘操作n-coef=coef; /賦值新節(jié)點的系數(shù)域n-exp=exp; /賦值新節(jié)點的指數(shù)域 m-next=n; /鏈接節(jié)點至頭結(jié)點，構(gòu)成鏈表m=m-next; /后移指針，為下一節(jié)點做準(zhǔn)備q=q-next; /控制B鏈表下一項/printf(%f %d ,coef,exp); /調(diào)試用p=p-next; /控制A鏈表下一項m-next=NULL; /鏈表尾置空/head=head-next;polyadd(head,temp); /return head; void selet(polynomial * A,polynomial * B)int p;polynomial * C;printf(1、實現(xiàn)相加運算n2、實現(xiàn)相乘運算n);printf(請選擇運算:);scanf(%d,&p);while(p!=1&p!=2)printf(輸入錯誤,請重新選擇:n);scanf(%d,&p);if(p=1) C=polyadd(A,B);else if(p=2)C=polyand(A,B);printf(The result is:n); print(C); /*調(diào)用輸出打印函數(shù)，打印運算結(jié)果*/ int main() /*主函數(shù)*/polynomial * A,* B; /*設(shè)立指針分別指向多項式鏈表A和鏈表B以及C作為結(jié)果*/A=creatlist(); /*建立打印多項式A*/print(A);B=creatlist(); /*建立打印多項式B*/ print(B); selet(A,B);return 0; /*還回系統(tǒng)調(diào)用0，結(jié)束整個程序*/4、 調(diào)試過程1打印輸出調(diào)試：輸入（3, 4） （-2 ,5） （2.6 ,7） 即3x4-2x5+2.6x6輸出3.00x(4) -2.00x(5) 2.60x(6) 如圖：輸出正常；2加法運算調(diào)試輸入數(shù)據(jù)：（2,3）（3,4）（4,5）和（1,2）（3,4）（-5,5）即2x3+3x4+4x5和x2+3x4-5x5 并沒有項預(yù)期的一樣實現(xiàn)加法運算，而是在打印出各項數(shù)據(jù)后程序終止。如圖：輸入數(shù)據(jù)：（2,3）（3,4）（4,5）和（1,3）（3,4）（-5,5）即2x3+3x4+4x5和x3+3x4-5x5 結(jié)果和項預(yù)期的一樣實現(xiàn)了加法運算，如圖：對比得知數(shù)據(jù)和唯一不同的是的第一項的的指數(shù)大于的第一項指數(shù)因此應(yīng)該想到程序在執(zhí)行比較第一項之后并不能進(jìn)行該有的操作即而之后的第二項第三項卻可以執(zhí)行有暗示著實現(xiàn)(p-exp)(q-exp)并沒內(nèi)部錯誤：因此矛頭指向了polynomial *p,*q,*s,*r; float x;p=A-next;q=B-next;s=p;/*出錯原因*/ 而其中正是出錯所在了，是作為的前驅(qū)而不是p -next的前驅(qū)，故而該是s=A；修改后正常的實現(xiàn)了改算法；但由于程序以實現(xiàn)該算法的核心思想為主因此并沒有過多注意的在用戶界面上實現(xiàn)和排序問題和出錯等處理。因此對用戶輸入的要求嚴(yán)格。3乘法運算調(diào)試通過以上改正后進(jìn)行測試測試數(shù)據(jù)（3,4）（4,5）（5,6）和（2，4）（3，6）（6,7） 未能得到預(yù)期結(jié)果；分析：可知第一項6.00x(8)并沒能出現(xiàn)可能有兩個原因，一是執(zhí)行運算時跳過了B鏈表第一項；二是運算了單沒能打印出；有后面的數(shù)據(jù)8.00x(9)可知,是第二種可能；因此在執(zhí)行運算后用printf(%f %d ,coef,exp);得結(jié)果如圖：可以確定錯誤出處了，經(jīng)檢查知運算后多了head=head-next;將其刪除即可。六、實驗結(jié)果測試數(shù)據(jù)（1）：2,3 3,4 5,6 和1,2 2,3 3,4 5,7即2x3+3x4+5x6 和1x22x3+3x4+5x7實驗結(jié)果（1）：加法1.00x(2) 4.00x(3) 6.00x(4) 5.00x(5) 5.00x(7)即1.00x2+4.00x3+ 6.00x4+ 5.00x5+ 5.00x7乘法9.00x(8) 12.00x(9) 15.00x(10) 38x(11) 30x(13)即9x2+12x3+15 x4+38x5+30x(13)實驗截圖（1）：加法乘