數(shù)據(jù)結構課程設計大數(shù)相乘與多項式相乘

1、目錄1、 問題描述2、 設計思路3、 數(shù)據(jù)結構設計4、 功能函數(shù)設計5、 程序代碼6、 運行與測試7、 設計心得一、大數(shù)相乘1、問題描述：輸入兩個相對較大的正整數(shù)，能夠通過程序計算出其結果2、設計思路：首先考慮設計將兩個大數(shù)按照輸入順序存入分別存入數(shù)a ,b 中.把這個數(shù)組中的每一位數(shù)字單獨來進行乘法運算，比如我們可以用一個數(shù)字和另外一個數(shù)組中的每一位去相乘，從而得到乘法運算中一行的數(shù)字，再將每一行數(shù)字錯位相加。這就是乘法運算的過從低位往高位依次計算，同時確定每一列的項數(shù)，確定每一位上的結果存入數(shù)組c 中.找到最高位在數(shù)組中的項ci,然后依次輸出各位上的數(shù)值通過主函數(shù)來調用其它各個函數(shù)。3、數(shù)

2、據(jù)結構設計：輸入階段采用一維數(shù)組a ,b 在輸入階段當大數(shù)輸入時，大數(shù)a,b從高位到低位分別依次存入數(shù)組a ,b 。調用函數(shù)計算階段采用一維數(shù)組c 在調用sum(a,b,m,n)函數(shù)中，在計算過程中，由個位到高位依次計算各位的結果，并依次存入數(shù)組c 中。4、功能函數(shù)設計：找出每一列的所有項首先找規(guī)律，如下所示 進行乘法:a0 a1 a2b0 b1 b2b2a0 b2a1 b2a2b1a0b1a1 b1a2b0a0b0a1b0a2下標之和01 2 3 4 i=4 i=3 i=2 i=1 i =0(循環(huán)時的i的數(shù)值)即有 下標之和=m+n-2-i,由此限定條件可設計循環(huán)得出每一列的所有項。故首先解

3、決了找出每一列所有項的問題。計算從低位到高位每一位的值。顯然考慮到進位的問題，故必須從低位到高位依次計算，對于每一列 ，第一項可以除十取余數(shù)，保留在原位，存入c ，所得商進位存入mm。然后對于第二列，第一項加進位mm，然后取余數(shù)存入su,再加第二項，取余數(shù)存入c ,求商存入進位mm，直到該列所有項參與運算到該列結束時，求的最終的c ,和mm. 依次進行后面的運算。找出反向存入結果c 中的首項.因為最高位一定不為零，故可以設計程序從c399開始判斷，當ci不等于零時，即為最高項。設計主函數(shù)，依次調用如上函數(shù)。然后通過for循環(huán)5、程序代碼：#include #include void sum(i

4、nt a200,int b200,int m,int n)/結果在數(shù)組里順序是反著的 int mm=0;/保存進位int c400=0;/保存結果int i,j,su,tt;for(i=0;im+n;i+) su=0;for(j=0;j=n|(tt=(m-1+n-1-i-j)=0;i-)/找首位 if(ci!=0)tt=i;break; else continue; for(i=tt;i=0;i-)/輸出printf(%d,ci); printf(n);void main()int i,m,n,c;int a200=0,b200=0;printf(*n);printf(請輸入第一個數(shù)字：n);

5、for(i=0;(c=getchar()!=n;i+)ai=c-48;m=i;printf(n*n);printf(請輸入第二個數(shù)字：n);for(i=0;(c=getchar()!=n;i+)bi=c-48;n=i;/m,n為數(shù)字長度sum(a,b,m,n);6運行與測試：7、設計心得：根據(jù)數(shù)字相乘原理，編程實現(xiàn)了大數(shù)相乘，雖然過程中出現(xiàn)了許多問題但經(jīng)過與同學討論后都順利解決。二、多項式相乘1、問題描述：能夠按照指數(shù)降序排列建立多項式，能夠完成兩個多項式的相乘，并將結果輸出。2、設計思路：這個程序的關鍵是多項式的創(chuàng)建和排列，以及相乘時相同指數(shù)的系數(shù)相加。由于多項式擁有指數(shù)和系數(shù)（假設基數(shù)已定

6、），所以可以定義一個包含指數(shù)系數(shù)的結構體，用單鏈表存儲多項式的數(shù)據(jù)，所以結構體包含next指針。數(shù)據(jù)插入時比較兩數(shù)的指數(shù)，按照降序排序，從表頭的next開始，直至找到合適的位置，然后開始鏈表中數(shù)值的插入，如果相等則直接將指數(shù)相加，如果大于就將新數(shù)據(jù)插入到當前指向的前面，否則將新數(shù)據(jù)插入到最后。輸入完數(shù)據(jù)后相乘，多項式運算時要循環(huán)遍歷整個多項式，多項式的每一組數(shù)據(jù)都要和另一個多項式整組數(shù)據(jù)相乘，直到兩個多項式都遍歷完結束。3、數(shù)據(jù)結構設計：對已排序且合并了同指數(shù)項的兩個多項式實現(xiàn)乘法操作，并輸出結果；結果多項式要求以動態(tài)鏈表為存儲結構，復用原多項式的結點空間；輸出結果多項式要求按指數(shù)升序排列，同

7、指數(shù)的多項要合并，項數(shù)的正負號要求顯示合理。4、 功能函數(shù)設計（見源代碼）5、 程序代碼：#include #include #define TRUE 1#define FALSE 0#define N sizeof(struct quantic)/跳轉頁面void welcome()printf(n*n);/創(chuàng)建多項式結構體struct quanticint xishu;int mi;struct quantic *next;/得到一元變量char getx(void)char x;printf(n請輸入一元變量：);scanf(%c, &x);return x;/創(chuàng)建多項式鏈表struct

8、 quantic *input(void)struct quantic *p1, *p2, *head;head = p2 = (struct quantic *)malloc(N);printf(n請輸入：系數(shù) 冪值(系數(shù)輸入0結束)。n);p1 = (struct quantic *)malloc(N);scanf(%d %d, &p1 - xishu, &p1 - mi);while(p1 - xishu != 0)p2 - next = p1;p2 = p1;p1 = (struct quantic *)malloc(N);scanf(%d %d, &p1 - xishu, &p1 -

9、 mi);p2 - next = NULL;free(p1);return head;/查找void find(char x, struct quantic *p)struct quantic *p1;int m, n, i = 0;p1 = p;printf(1.按系數(shù)查找。n);printf(2.按指數(shù)查找。n);printf(0.退出查找。n);scanf(%d, &m);switch(m)case 1:printf(請輸入索引關鍵字:);scanf(%d, &n);p1 = p1 - next;while(p1 != NULL)if(p1 - xishu = n)printf(%d%c

10、(%d), p1 - xishu, x, p1 - mi);i +;p1 = p1 -next;if(i = 0)printf(查無此數(shù)據(jù)。n);printf(n);find(x, p);break;case 2:printf(請輸入索引關鍵字:);scanf(%d, &n);p1 = p1 - next;while(p1 != NULL)if(p1 - mi = n)printf(%d%c(%d), p1 - xishu, x, p1 - mi);i +;p1 = p1 -next;if(i = 0)printf(查無此數(shù)據(jù)。n);printf(n);find(x, p);break;cas

11、e 0:welcome();/多項式相乘struct quantic *MulExp(struct quantic *exp1,struct quantic *exp2)struct quantic *head,*p1,*q,*p2,*last,pre,*p;int flag=TRUE;head=p1=*exp1;/p1=p1-next;for(;p1-next != NULL;p1=p1-next);p=last=p1;p1=(*exp1)-next;while(p1 != p-next)pre = *p1;flag=TRUE;p2=(*exp2)-next;while(p2)if(flag

12、=TRUE)p1-xishu=p1-xishu*p2-xishu;p1-mi=p1-mi+p2-mi;p2=p2-next;flag=FALSE;elseq=(struct quantic *)malloc(N);q-xishu=pre.xishu*p2-xishu;q-mi=pre.mi+p2-mi;last-next=q;last=q;p2=p2-next;p1=p1-next;last-next=NULL;return head;/排序多項式struct quantic *sort(struct quantic *pol)struct quantic *head = pol;struct

13、 quantic *p,*q;struct quantic *r,*t;if(head-next = NULL)printf(請輸入有效信息。n);elsep = head-next;q = p-next;p-next = NULL;p = q;while(p!=NULL)r = head;q = r-next;while(q != NULL& q-mi mi)r = q;q = q-next; t=p-next; p-next=r-next; r-next=p; p=t;return(head);/合并多項式struct quantic *combine(struct quantic *he

14、ad)struct quantic *p1,*p2;p1 = head -next;while(p1 - next != NULL )if(p1 - next - mi = p1 - mi)p2 = p1 -next;p1 - xishu = p1 - xishu + p2 - xishu;p1 - next = p1 - next -next;free(p2);elsep1 = p1 - next;return(head);/輸出多項式void output(char x, struct quantic *p)p = p - next;while(p != NULL)if(p - xishu

15、 xishu, x, p - mi);p = p -next;printf(b );printf(n);main()char x;struct quantic *p, *q, *l, *s, *k, *a, *b, *c, *d;/歡迎界面開始welcome();/輸入一元未知量x = getx();/輸入兩個多項式并輸出printf(n請輸入第一個多項式:n);p = input();output(x, p);printf(n請輸入第二個多項式:n);l = input();output(x, l);/查找相應節(jié)點find(x, p);find(x, l);/對隊列進行排序、合并，然后輸出q = s