數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告一元多項式加減乘計算

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

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

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

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

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

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

7、t; /*定義結(jié)構(gòu)體*/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) /*插入函數(shù)*/Dnodelist p;Dnodelist q;Dnodelist r;p=D;while(p->next) r=p;p=p->next;if(zs=p->zs) /*指數(shù)相等，系數(shù)直接相加，結(jié)束*/p->xs=p->x

8、s+xs;return 1;else if(zs>p->zs) /*指數(shù)大于當(dāng)前數(shù)據(jù)的，將數(shù)據(jù)插入當(dāng)前數(shù)據(jù)之前，結(jié)束*/q=Creat_node();q->xs=xs;q->zs=zs;r->next=q;q->next=p;return 1;/*while(p->next)*/q=Creat_node(); /*要插入的數(shù)據(jù)指數(shù)最小，直接插入至鏈表最后*/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+) /*以三組數(shù)據(jù)為例*/scanf("%d,%d",&m,&n);Insert_node(D,m,n); /*調(diào)用插入函數(shù)，將輸入的系數(shù)指數(shù)插入鏈表*/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; /*系數(shù)相乘，指數(shù)相加*/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; /*直接插入數(shù)據(jù)，利用插入函數(shù)可完成該功能*/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) /*指數(shù)?。?的數(shù)據(jù)在2中不存在），直接插入*/x=-(q->xs); /*由于是式1減式2，所以系數(shù)置負(fù)*/z=q->zs;Insert_node(D,x,z);q=q->next;else if(p->zs)>(q->zs) /*指數(shù)大（2的數(shù)據(jù)在1中不存在），直接插入*/ x=p->xs;z=p->zs;Insert_node(D,x,z);p=p->next;else /*指數(shù)相同的先將系數(shù)相減，再插入*/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; /*將未遍歷完的數(shù)據(jù)直接插入*/return D;Dnodelist select(Dnodelist D1,Dnodelist D2) /*選擇函數(shù)*/Dnodelist D;int s

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

15、");break;default:printf("無此選項n");break;return D;void Show(Dnodelist D) /*顯示（輸出）函數(shù)*/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的組數(shù)：n”);scanf(“%d”,&length);printf("輸入多項式1系數(shù),指數(shù)：(%d組)n",length);D1=Creat_Dmeth(length); /*創(chuàng)建多項式1*/printf("輸入多項式2的組數(shù)：n”);scanf(“%d”,&length);printf("輸入多項式2系數(shù),指數(shù)：(%d組)n",length);D2=Creat_Dmeth(length); /*創(chuàng)建多項式2*/ D=select(D1,D2); /*選擇運(yùn)算方式*/Show(D); /*輸出顯示*/getch();6、 運(yùn)行與測試程序運(yùn)行時，先提示第一個多項式的組數(shù)，確定組數(shù)后才可輸入相應(yīng)的數(shù)據(jù)，之后是多項式2；輸入完數(shù)據(jù)后，程序提示選擇運(yùn)算方式。選擇錯誤則提示“無此選項”，運(yùn)行結(jié)束