數據結構課程設計報告一元多項式加減乘計算

1、數據結構課程設計多項式計算 班級： 學號： 姓名： 指導老師： 多項式計算1、 問題描述能夠按照指數降序排列建立多項式；能夠完成兩個多項式的相加、相減和相乘，并將結果輸出。2、 設計思路這個程序的關鍵是多項式的創(chuàng)建和排列，以及相乘時系數相乘和指數相加、相加時相同指數的系數相加、相減時相同指數的系數相減。由于多項式擁有指數和系數（假設基數已定），所以可以定義一個包含指數系數的結構體，用單鏈表存儲多項式的數據，所以結構體包含next指針。數據插入時比較兩數的指數，按照降序排序，從表頭的next開始，直至找到合適的位置，然后開始鏈表中數值的插入，如果相等則直接將指數相加，如果大于就將新數據插入到當前

2、指向的前面，否則將新數據插入到最后。輸入完數據后選擇計算方式（相乘、相加、相減），多項式運算時要循環(huán)遍歷整個多項式，多項式的每一組數據都要和另一個多項式整組數據相運算（每一個運算值都存儲到新建的“多項式”鏈表中），直到兩個多項式都遍歷完結束。3、 數據結構設計在模擬多項式對象時，為了簡化處理，只取最核心的兩個數據：多項式的系數和指數。前面提到，要用單鏈表操作，所以要加上個next指針，再由該結構體定義一個結點類型和指針類型。具體數據結構定義如下：typedef struct nodeint xs; /*系數*/int zs;/*指數*/struct node * next; /*next指針*

3、/Dnode,* Dnodelist;4、 功能函數設計（1）鏈表初始化函數Creat_node()帶有頭結點的頭指針指向空（NULL）。（2）多項式數據的創(chuàng)建函數Creat_Dmeth()當鏈表初始化成功后，開始創(chuàng)建多項式。分別循環(huán)輸入兩個多項式的系數和指數，其中要用到插入函數。（3）數據的插入函數Insert_node()當創(chuàng)建多項式時，要用到此函數，即利用插入的方式將多項式的數據連接起來。再輸入一組數據后，程序自動調用此函數，插入時也進行著排序，從表頭的next開始，一一比較指數大小，直到大于或等于當前指向的數據或遍歷完所有數據時停止，然后開始鏈表中數值的插入，如果相等則直接將指數相加，

4、如果大于就將新數據插入到當前指向的前面，否則將新數據插入到最后。（4）多項式的顯示函數Show()從多項式表頭的next開始，直到指向空（NULL），將系數與指數一一顯示。（5）選擇運算方式的函數select()三種選擇：1為相乘，2為相加，3為相減；每一種選擇調用相應的運算函數。（6）多項式的運算函數：新建鏈表存儲計算后的多項式1、多項式相乘Mulresult()創(chuàng)建兩個指針分別指向兩個多項式表頭的next，使用兩個while函數嵌套循環(huán)，遍歷每一組數據，每遍歷一次都將兩組數據的系數相乘，指數相加，再利用插入函數將系數與指數存儲到新建多項式的鏈表中。2、多項式相加Addresult()創(chuàng)建兩

5、個指針分別指向兩個多項式表頭的next，分別使用兩個while函數獨自循環(huán)，遍歷各自的每一組數據，每遍歷一次都將系數與指數存儲到新建多項式的鏈表中。因為存儲時利用到插入函數，而插入函數中有相同指數的系數相加功能，所以直接將兩個多項式的數據依次插入到新的多項式中即可完成多項式相加。3、多項式相減Subresult()創(chuàng)建兩個指針分別指向兩個多項式表頭的next，以兩個指針同時不為空為條件循環(huán)遍歷，如果當前多項式1的指數小于多項式2，則將當前多項式2的系數置負，指數不變，存入新建多項式中，指向多項式2的指針指向下一個；如果如果當前多項式1的指數大于多項式2，則將當前多項式1的系數指數不變，存入新建

6、多項式中，指向多項式1的指針指向下一個；否則將多項式1的系數減去2的系數后存入新建多項式中，指數不變存入，再將兩個指針同時指向下一個。結束循環(huán)后判斷是哪一個多項式遍歷完了，將未遍歷完的多項式剩下的數據全部插入到新建多項式中。（7）主函數main()創(chuàng)建兩個多項式的鏈表并且初始化，分別調用相應的多項式創(chuàng)建函數，創(chuàng)建成功后選擇運算方式，再將運算結果輸出顯示。5、 程序代碼#include<stdio.h>#include<stdlib.h>typedef struct nodeint xs;int zs;struct node * next;Dnode,* Dnodelis

7、t; /*定義結構體*/Dnodelist Creat_node(void) /*鏈表初始化*/Dnodelist D;D=(Dnodelist)malloc(sizeof(Dnode);if(D)D->next=NULL;return D;int Insert_node(Dnodelist D,int xs,int zs) /*插入函數*/Dnodelist p;Dnodelist q;Dnodelist r;p=D;while(p->next) r=p;p=p->next;if(zs=p->zs) /*指數相等，系數直接相加，結束*/p->xs=p->x

8、s+xs;return 1;else if(zs>p->zs) /*指數大于當前數據的，將數據插入當前數據之前，結束*/q=Creat_node();q->xs=xs;q->zs=zs;r->next=q;q->next=p;return 1;/*while(p->next)*/q=Creat_node(); /*要插入的數據指數最小，直接插入至鏈表最后*/q->xs=xs;q->zs=zs;q->next=p->next;p->next=q;return 1;free(p);free(q);free(r);Dnodeli

9、st Creat_Dmeth(int length) /*創(chuàng)建多項式*/int i,m,n;Dnodelist D;D=Creat_node();for(i=0;i<length;i+) /*以三組數據為例*/scanf("%d,%d",&m,&n);Insert_node(D,m,n); /*調用插入函數，將輸入的系數指數插入鏈表*/return D;Dnodelist Mulresult(Dnodelist D1,Dnodelist D2) /*多項式相乘*/Dnodelist D;Dnodelist p,q;int x,z;D=Creat_nod

10、e();p=D1->next;q=D2->next;while(q)while(p)x=p->xs*q->xs; /*系數相乘，指數相加*/z=p->zs+q->zs;Insert_node(D,x,z);p=p->next;p=D1->next;q=q->next;return D;Dnodelist Addresult(Dnodelist D1,Dnodelist D2) /*多項式相加*/Dnodelist D;Dnodelist p,q;int x,z;D=Creat_node();p=D1->next;q=D2->ne

11、xt;while(q)x=q->xs;z=q->zs;Insert_node(D,x,z);q=q->next;while(p)x=p->xs;z=p->zs;Insert_node(D,x,z);p=p->next; /*直接插入數據，利用插入函數可完成該功能*/return D;Dnodelist Subresult(Dnodelist D1,Dnodelist D2) /*多項式相減*/Dnodelist D;Dnodelist p,q;int x,z;D=Creat_node();p=D1->next;q=D2->next;while(p

12、&&q)if(p->zs)<(q->zs) /*指數?。?的數據在2中不存在），直接插入*/x=-(q->xs); /*由于是式1減式2，所以系數置負*/z=q->zs;Insert_node(D,x,z);q=q->next;else if(p->zs)>(q->zs) /*指數大（2的數據在1中不存在），直接插入*/ x=p->xs;z=p->zs;Insert_node(D,x,z);p=p->next;else /*指數相同的先將系數相減，再插入*/z=q->zs;x=(p->xs)-(

13、q->xs);Insert_node(D,x,z);p=p->next;q=q->next;/*while(p&&q)*/while(p)x=p->xs;z=p->zs;Insert_node(D,x,z);p=p->next;while(q)x=-(q->zs);z=q->zs;Insert_node(D,x,z);q=q->next; /*將未遍歷完的數據直接插入*/return D;Dnodelist select(Dnodelist D1,Dnodelist D2) /*選擇函數*/Dnodelist D;int s

14、;printf("請選擇:n1:相乘n2:相加n3:相減n");scanf("%d",&s);switch(s)case 1: D=Mulresult(D1,D2); /*調用相乘函數*/printf("相乘結果(系數,指數):n");break;case 2: D=Addresult(D1,D2); /*調用相加函數*/printf("相加結果(系數,指數):n");break;case 3: D=Subresult(D1,D2); /*調用相減函數*/printf("相減結果(系數,指數):n

15、");break;default:printf("無此選項n");break;return D;void Show(Dnodelist D) /*顯示（輸出）函數*/Dnodelist r;r=D->next;while(r)printf("(%d,%d)+",r->xs,r->zs);r=r->next;printf("n");void main()Dnodelist D1,D2,D;int length;D1=Creat_node();D2=Creat_node(); /*D1為多項式1，D2為多

16、項式2，初始化*/printf("輸入多項式1的組數：n”);scanf(“%d”,&length);printf("輸入多項式1系數,指數：(%d組)n",length);D1=Creat_Dmeth(length); /*創(chuàng)建多項式1*/printf("輸入多項式2的組數：n”);scanf(“%d”,&length);printf("輸入多項式2系數,指數：(%d組)n",length);D2=Creat_Dmeth(length); /*創(chuàng)建多項式2*/ D=select(D1,D2); /*選擇運算方式*/Show(D); /*輸出顯示*/getch();6、 運行與測試程序運行時，先提示第一個多項式的組數，確定組數后才可輸入相應的數據，之后是多項式2；輸入完數據后，程序提示選擇運算方式。選擇錯誤則提示“無此選項”，運行結束