題目長整數(shù)乘法

1、 題目: 長整數(shù)乘法班級:姓名:學(xué)號:完成日期:1：需求分析(1) 輸入的形式和輸入值的范圍:用戶從鍵盤輸入2個任意長度的長整數(shù)，輸入的時候是按4個為一段輸入的,即一段一段輸入的,求它們的乘積的大小，并將結(jié)果在屏幕上顯示;2個長整數(shù)的輸入沒有大小的限制,要輸入多大的數(shù)據(jù),就可以輸入多大的數(shù)據(jù).(2) 輸出的形式: 輸出直接在屏幕上顯示2個任意長度的長整數(shù)的乘積大小(3) 程序所能達到的功能: 對于用戶輸入的任意長度的2個的長整數(shù),能夠正確沒有錯誤的顯示結(jié)果,和電腦附件中的計算器的計算值要一致;能夠準(zhǔn)確無誤地顯示結(jié)果(4) 測試數(shù)據(jù) 如輸入1000 1000 和1111 2個長整數(shù)后,顯示011

2、1 1111 1111 1000的話,就是正確的結(jié)果形式; 如輸入1111 1111 1111和1111 2個長整數(shù)后,結(jié)果顯示0123 4444 4444 4322就不是正確結(jié)果,因為這2個長整數(shù)的積為0123 4444 4444 43212:概要設(shè)計 a：抽象數(shù)據(jù)類型的定義為了實現(xiàn)任意長整數(shù)的乘法，因為這種運算存在進位和位移等操作，因此選擇雙鏈表的結(jié)構(gòu)體，它有一個data，left，right；考慮到data表示的數(shù)據(jù)的范圍，使它只接受4個數(shù)字的整數(shù)，這樣一個長整數(shù)就分為若干段，每一段為4個數(shù)字，便于進位和借位以及位移的操作,用戶在輸入時就是每次輸入4個數(shù)字.b:主程序的流程 主程序是首先

3、調(diào)用初始化2個長整數(shù)的函數(shù),用戶4個數(shù)字一段一段地輸入2個長整數(shù),用雙鏈表的形式和頭插法的形式建立,返回2個長整數(shù)的頭節(jié)點;建立完2個長整數(shù)后,就開始進行2個長整數(shù)的乘積的運算了;首先將第一個長整數(shù)的全部去乘第2個長整數(shù)的最后一段,這樣得到一個長整數(shù);接著將第一個長整數(shù)的全部去乘第2個長整數(shù)的倒數(shù)第2段,這樣得到一個長整數(shù),但是要向左位移4位; 這次得到的長整數(shù)要和上一次相加,得到一個新的長整數(shù);接著接著將第一個長整數(shù)的全部去乘第2個長整數(shù)的倒數(shù)第3段,得到一個長整數(shù),再和前面相加;依次進行,一直到已經(jīng)到第一個長整數(shù)的全部乘于了第2個長整數(shù)的最高1段,那么乘法就結(jié)束了;這時將得到的長整數(shù)從高位

4、到低位一段一段,4個4個數(shù)字顯示在屏幕上,程序就運行結(jié)束了.c:模塊之間的層次(調(diào)用)關(guān)系 程序的調(diào)用關(guān)系如下:主函數(shù)調(diào)用了初始化2個長整數(shù)的函數(shù),然后再調(diào)用了2個2個長整數(shù)的乘積的函數(shù);2個長整數(shù)的乘積的函數(shù)調(diào)用了部分求和的函數(shù)和從表頭得到表尾的函數(shù),以及將一個長整數(shù)前后數(shù)值交換的函數(shù)以及顯示一個長整數(shù)的函數(shù).3詳細設(shè)計 a：2個長整數(shù)的輸入 接著采用頭插法的方式，當(dāng)輸入一個 4個數(shù)字的整數(shù)時，就產(chǎn)生一個新的節(jié)點，它的值為輸入的整數(shù)值，建立起它的左右指針，并用頭節(jié)點指向它；為了判斷一個長整數(shù)是否輸入結(jié)束，定義一個結(jié)束標(biāo)志，當(dāng)輸入正數(shù)時就繼續(xù)，當(dāng)輸入負數(shù)時，就結(jié)束一個長整數(shù)的輸入；同時用一個函

5、數(shù)得到長整數(shù)的尾節(jié)點和段數(shù)，段數(shù)在比較2個數(shù)的大小有用。 b：2個長整數(shù)的乘法先定義一個部分加法的函數(shù)，就是2個正的長整數(shù)的加法的運算；它從2個長整數(shù)的尾部開始，同時相加，接著再向左移一段，又同時相加；當(dāng)2個數(shù)據(jù)的某一段同時存在時，就相加；當(dāng)一個數(shù)據(jù)已經(jīng)全部被相加后，另外一個數(shù)據(jù)的剩下的段就要全部復(fù)制到和中；在實行加法的時候，設(shè)置一個進位標(biāo)志位，目的是為了使結(jié)果正確；當(dāng)一 段的數(shù)據(jù)相加產(chǎn)生進位時，那么進位標(biāo)志位為1；下一次一 段的數(shù)據(jù)相加就要加上這個進位標(biāo)志位；而且如果2個長整數(shù)的所有的段的數(shù)據(jù)都相加完了，還要判斷是否產(chǎn)生了進位標(biāo)志位，如果有的話，就要新建一個節(jié)點，它的值就是1；2個正的長整數(shù)

6、的求和就完成了。再定義一個部分乘法的函數(shù)，就是1個正的長整數(shù)乘于一個4位整數(shù)，并向左位移特定的段數(shù)的運算；其實開始實現(xiàn)向左位移的運算，只需要建立新的節(jié)點，節(jié)點的數(shù)目為需要左移段數(shù)，并將這些節(jié)點的值設(shè)置為0；接著實現(xiàn)一個長整數(shù)乘于一個4位整數(shù)的運算，采用每一段都和這個4位整數(shù)的相乘的方法，當(dāng)積超過10000時，那么多于高4位全為進位，參與下一次相乘時要加上它；低4位就是要新建的節(jié)點的值；和加法一樣，當(dāng)這個正的長整數(shù)的每一段都和這個4位整數(shù)相乘后，但還存在進位時，就要新建一個節(jié)點，它的值就是進位值；現(xiàn)在1個正的長整數(shù)乘于一個4位整數(shù)，并向左位移特定的段數(shù)的運算就完成了；再實現(xiàn)2個正的長整數(shù)的乘法的

7、運算，采用第一個長整數(shù)作為一個整體乘于第二個長整數(shù)的每一段，并向左位移的方法；例如當(dāng)采用第一個長整數(shù)作為一個整體乘于第二個長整數(shù)的最后一段，就不用向左位移；但是第一個長整數(shù)作為一個整體乘于第二個長整數(shù)的倒數(shù)第二段，就用向左位移一段，就是最后一段為0，依次類推；此過程是調(diào)用部分乘法的函數(shù)實現(xiàn)的；我們只需要定義2個長整數(shù)的臨時變量，1個是本次新產(chǎn)生的部分乘法的結(jié)果，1個是上次的總和；那么總和加上本次新產(chǎn)生的部分乘法的結(jié)果重新給總和，此操作是調(diào)用2個長整數(shù)的加法實現(xiàn)的；第2個數(shù)的段一直向左位移，總和也就不斷擴大，當(dāng)?shù)?個數(shù)的段達到最高一段時，就完成了2個正的長整數(shù)的乘法的運算。f：補充說明 在程序中

8、，因為我們需要得到一個長整數(shù)的頭部和尾部，因此定義了2個函數(shù)，一個是已知一個一長整數(shù)的頭部，得到它的尾部；一個是已知一個一長整數(shù)的尾部，得到它的頭部；具體實現(xiàn)都是利用指針的左移和右移，為空時就得到頭部或尾部；在程序中，我們輸入是從高位到低位輸入的，而相加后的順序就相反了，因此我們需要定義一個將一個長整數(shù)的數(shù)據(jù)前后交換的函數(shù)，新建一個一個長整數(shù)，使用頭插法，將從原來一個長整數(shù)的尾部開始，向左移，一個一個給新建的長整數(shù)。4調(diào)試分析a調(diào)試過程中遇到的問題是如何解決 問題1:調(diào)試過程中發(fā)生內(nèi)存錯誤的提示? 內(nèi)存錯誤有非常大的原因是指針的濫用和它的空間的使用不規(guī)范情況,但最可能是指針還沒有開辟空間,就已

9、經(jīng)指向了一個實際存在的數(shù);查找代碼,果然發(fā)現(xiàn),head在使用中沒有開辟空間,.但后面語句有給它賦值的情況,因此添加代碼head=(dnode*)malloc(sizeof(dnode);再次調(diào)試時沒有發(fā)生一樣的錯誤;問題2:結(jié)果顯示的時候本應(yīng)該按從高位到低位輸出,結(jié)果從從低位到高位輸出? 我們定義的部分和的加法是從長整數(shù)的尾部開始的，即先從小的開始加起,再加大的;但是我們還是采用的是頭插法的方法,因此頭節(jié)點其實是和的最小值,依次類推,那么當(dāng)我們按從頭到尾節(jié)點輸出時,就是從低到高輸出了;因此我們輸出的時候可以先從頭節(jié)點寫一個函數(shù)得到尾節(jié)點,再從尾節(jié)點,從右到左的形式輸出結(jié)果,即從尾到頭的形式輸出

10、結(jié)果;因此我定義了一個從頭節(jié)點得到尾節(jié)點的函數(shù),再從尾到頭的形式輸出結(jié)果,這次輸出結(jié)果沒有錯誤;問題3:結(jié)果顯示的時候本總出現(xiàn)一個為-858993460的節(jié)點? 有可能是定義了一個節(jié)點, 沒有被賦值,因此產(chǎn)生的情況; 查找代碼,果然發(fā)現(xiàn)s=(dnode*)malloc(sizeof(dnode);p->right=s;s->left=p;缺少了s的賦值的代碼,添加 s->data=inc后,運行沒有錯誤b算法的時空分析 時間復(fù)雜度:由于2個長整數(shù)的乘法是用第一個長整數(shù)的全部乘于了第2個長整數(shù)的每一段然后想加得到的,因此它實際上就是2重循環(huán)的作用,假設(shè)2個數(shù)的段數(shù)分別為n1和n

11、2,那么算法的時間復(fù)雜度為n1和n2的乘積;空間復(fù)雜度: 空間復(fù)雜度是和2個長整數(shù)的段數(shù)成正比, 2個長整數(shù)的段數(shù)越多,那么需要開辟的空間越多,求和需要的長整數(shù)的開辟的空間也越多c經(jīng)驗和體會在寫程序中要規(guī)范書寫，這樣便于檢查錯誤的出現(xiàn)所在的地方；寫代碼要前后照應(yīng)，前面的變量和函數(shù)在后面使用時可能要對應(yīng)，如果不注意，可能發(fā)生錯誤；當(dāng)出現(xiàn)錯誤時，要大膽猜測各種出錯的可能的原因，一種一種排除，一種一種嘗試，問題可能解決。定義了指針就需要開辟空間,否則會出錯;同時指針開辟的空間單元要初始一定的值, 否則會出現(xiàn)不需要的數(shù)據(jù);5用戶使用說明 本程序使用簡單,運行程序后出現(xiàn)了input the first

12、data,input negative data exit的提示,告訴用戶輸入第一個長整數(shù),4個數(shù)字一段輸入,要想結(jié)束輸入直接輸入一個負數(shù)就可以結(jié)束了;如需要輸入1011 1011時;input the first data,input negative data exit10111011-1接著出現(xiàn)input the second data,input negative data exit的提示,告訴用戶輸入第2個長整數(shù),4個數(shù)字一段輸入,要想結(jié)束輸入直接輸入一個負數(shù)就可以結(jié)束了;如需要輸入1011 1011時;input the second data,input negative dat

13、a exit10111011-10102 2325 4344 2121輸入完以后,程序直接顯示運行結(jié)果,按回車就退出程序.6測試結(jié)果7附錄#include<stdio.h>#include<malloc.h>typedef struct linknodeint data;/*節(jié)點的值*/struct linknode *left,*right;/*左指針和右指針*/dnode;dnode *r1,*r2,*r3,*head1,*head2,*head3;dnode *head_temp,*rear_temp;/*head1為第1個數(shù)的頭指針，r1為 為第1個的尾指針*/

14、*head2為第2個數(shù)的頭指針，r2為 為第2個的尾指針*/*head3為結(jié)果的頭指針，r3為結(jié)果的尾指針*/*head_temp為臨時數(shù)的頭指針，rear_temp為臨時數(shù)的尾指針*/*產(chǎn)生一個長整數(shù)*/dnode* creat()dnode *head,*p,*s;/*head為頭指針，p和s為臨時指針*/int x,cycle=1;/*x為輸入的數(shù)據(jù)，cycle為是否繼續(xù)輸入的標(biāo)志*/head=(dnode*)malloc(sizeof(dnode);p=head;/*指向頭*/while(cycle)scanf("%d",&x);/*輸入數(shù)據(jù)*/if(x&g

15、t;=0)/*輸入正數(shù)才有效*/s=(dnode*)malloc(sizeof(dnode);s->data=x;p->right=s;s->left=p;p=s;/*采用的是頭插法*/else cycle=0;/*輸入負數(shù)就退出*/head=head->right;/*第一個頭沒有用到*/head->left=NULL;p->right=NULL;return head;dnode *rear(dnode *head)/*根據(jù)一個數(shù)的頭節(jié)點，得到尾節(jié)點，并得到這個數(shù)的段數(shù)*/dnode *p;p=head;while(p->right)/*向右移*/

16、 p=p->right;return p;void input_and_init()/*初始化2個數(shù)據(jù)的大小*/*符號變?yōu)閷?yīng)的0或1*/printf("input the first data,input negative data exitn"); head1=creat(); /*產(chǎn)生第一個數(shù)，得到它的頭指針*/ r1=rear(head1); /*得到第一個數(shù)的尾指針和*/*符號變?yōu)閷?yīng)的0或1*/ printf("input the second data,input negative data exitn"); head2=creat(

17、); /*產(chǎn)生第2個數(shù)，得到它的頭指針*/ r2=rear(head2); /*得到第一個數(shù)的尾指針和段數(shù)*/*打印一個數(shù)*/void print(int data)if(data>=1000)/*含有4個數(shù)字*/ printf("%d",data);else if(data>=100)/*含有3個數(shù)字，補1個零*/ printf("0%d",data);else if(data>=10)/*含有2個數(shù)字，補2個零*/ printf("00%d",data);else/*含有1個數(shù)字，補3個零*/ printf(&q

18、uot;000%d",data);/*顯示一個結(jié)果的長整數(shù)，從后向前移*/void display(dnode *rear)dnode *p; p=rear;while(p)print(p->data); printf(" "); p=p->left; /*向左移*/printf("n");dnode *find_sum2(dnode *r1,dnode *r2)/*得到2個正數(shù)的和*/dnode *head,*p,*s,*p1,*p2;/*head為頭指針，p,s為臨時指針，p1指向第1個數(shù)并向左移動，p2指向第2個數(shù)并并向左移動

19、*/ int inc=0,sum=0,f1=0,f2=0;/*inc為進位，sum為和，f1為第一個數(shù)是否結(jié)束，f2為第一個數(shù)是否結(jié)束*/head=(dnode*)malloc(sizeof(dnode);p=head;/*開辟空間*/p1=r1;/*指向第一個數(shù)的尾*/p2=r2;/*指向第二個數(shù)的尾*/while(p1!=NULL&&p2!=NULL)/*2個數(shù)的某一段都不為空時 */sum=p1->data+p2->data+inc;/*和為2個數(shù)之和加進位*/inc=0;/* 進位回0*/if(sum>=10000)/*當(dāng)超過2位數(shù)的大小時，和減去10

20、000，并進位*/sum=sum-10000;inc=1;/*用頭插法建立一個新的節(jié)點*/s=(dnode*)malloc(sizeof(dnode);s->data=sum;p->right=s;s->left=p;p=s;/*2個數(shù)都向左移*/p1=p1->left;p2=p2->left;if(p1=NULL&&p2=NULL)if(inc=1)/*當(dāng)2個數(shù)據(jù)都完了，但是存在進位時，新建一個節(jié)點，值就是進位*/s=(dnode*)malloc(sizeof(dnode); s->data=1;p->right=s;s->le

21、ft=p;p=s;while(p1!=NULL)/*當(dāng)?shù)?個數(shù)空，第1個數(shù)不為空時，將第一個數(shù)剩下的全用新節(jié)點產(chǎn)生*/f1=1;s=(dnode*)malloc(sizeof(dnode);sum=p1->data+inc;inc=0;if(sum>=10000)sum=sum-10000;inc=1;s->data=sum;p->right=s;s->left=p;p=s;/*第1個數(shù)都向左移*/p1=p1->left;/*當(dāng)?shù)?個數(shù)據(jù)完了，但是存在進位時，新建一個節(jié)點，值就是進位*/if(f1=1&&inc=1&&!p1)

22、s=(dnode*)malloc(sizeof(dnode);s->data=1;p->right=s;s->left=p;p=s;/*當(dāng)?shù)?個數(shù)空，第2個數(shù)不為空時，將第一個數(shù)剩下的全用新節(jié)點產(chǎn)生*/while(p2!=NULL)f2=1;s=(dnode*)malloc(sizeof(dnode);sum=p2->data+inc;inc=0;if(sum>=10000)sum=sum-10000;inc=1;s->data=sum;p->right=s;s->left=p;p=s;p2=p2->left;/*第2個數(shù)都向左移*/*當(dāng)?shù)?/p>

23、2個數(shù)據(jù)完了，但是存在進位時，新建一個節(jié)點，值就是進位*/if(f2=1&&inc=1)s=(dnode*)malloc(sizeof(dnode);s->data=1;p->right=s;s->left=p;p=s;head=head->right;head->left=NULL;p->right=NULL;return head;/*返回頭節(jié)點*/dnode * find_sub_mult(dnode * r1,int data ,int i)/*將r1指向的數(shù)全乘于data，并向左位移i段*/dnode *head,*p,*s,*rr

24、;/*head為頭指針，p,s為臨時指針，rr為尾指針*/int k,inc=0;/*k為循環(huán)用的，inc為進位*/long sum=0; /*求和*/rr=r1;head=(dnode*)malloc(sizeof(dnode);p=head;/*開辟空間*/*先將需要位移的段數(shù)全用0補齊*/if(i!=0)for(k=1;k<=i;k+)s=(dnode*)malloc(sizeof(dnode);s->data=0;p->right=s;s->left=p;p=s;while(rr!=NULL)/* 當(dāng)rr沒有到頭時*/s=(dnode*)malloc(sizeo

25、f(dnode);sum=rr->data*data+inc;if(sum>10000)inc=sum/10000;/*得到和的高4位*/s->data=sum-inc*10000;/*值為低4位的值*/ elses->data=sum;/*直接給值*/inc=0;p->right=s;s->left=p;p=s;/*左移*/rr=rr->left;if(inc!=0)/*如果還有進位，就需要新建一個節(jié)點*/s=(dnode*)malloc(sizeof(dnode);s->data=inc;p->right=s;s->left=p;

26、p=s;head=head->right;head->left=NULL;p->right=NULL;/*返回頭指針*/return head;/*由一個數(shù)的尾指針得到頭指針*/dnode * return_head(dnode *rear)dnode *p;p=rear;while(p->left)p=p->left;return p;/*由一個數(shù)的頭指針得到尾指針*/dnode * return_rear(dnode *head)dnode *p;p=head;while(p->right)p=p->right;return p;/*將一個數(shù)的數(shù)據(jù)前后交換*/dnode * tansfer_rear2(dnode *rear_temp)dnode *h