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