數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告完成多項(xiàng)式的運(yùn)算.docx

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