C語言單鏈表實(shí)現(xiàn)大數(shù)加法和乘法

1、軟件技術(shù)基礎(chǔ)一.項(xiàng)目題目當(dāng)正整數(shù)的位數(shù)較多時，采用int或者long變量儲存時會發(fā)生溢出?？梢圆捎靡粋€單鏈表儲存，每一位作為一個節(jié)點(diǎn)。設(shè)計完成如下功能的算法并用給定數(shù)據(jù)進(jìn)行測試。(1)由一數(shù)字字符串創(chuàng)建對應(yīng)的整數(shù)單鏈表；(2)輸出一個由證書單鏈表表示的正整數(shù)；(3)實(shí)現(xiàn)兩個多位正整數(shù)的加法運(yùn)算；(4)實(shí)現(xiàn)兩個多位正整數(shù)的乘法運(yùn)算。二算法設(shè)計(1)輸入要進(jìn)行處理的數(shù)據(jù)(2)輸出要測試的數(shù)據(jù)(3)分別調(diào)用已定義的“求和”、“求積”函數(shù)對數(shù)據(jù)進(jìn)行操作(4)打印得到的結(jié)果(5)銷毀所有鏈表三.函數(shù)設(shè)計(1)求字符數(shù)組長度函數(shù)：傳入一個字符數(shù)組的指針，用一個指針p和一個計數(shù)變量遍歷整個字符數(shù)組，返回計數(shù)

2、變量，即為數(shù)組長度。(2)字符串轉(zhuǎn)鏈表函數(shù)： 遍歷字符串， 使用尾插法將數(shù)據(jù)存入單鏈表中，并將字符型數(shù)據(jù)轉(zhuǎn)換成整形數(shù)據(jù)，每一個節(jié)點(diǎn)儲存一個數(shù)字。(3)求鏈表長度函數(shù)：傳入一個鏈表的頭結(jié)點(diǎn)，用一個指針p和一個計數(shù)變量遍歷整個鏈表，返回計數(shù)變量，即為鏈表長度。(4)讀取鏈表指定位數(shù)字函數(shù)：傳入一個鏈表的頭結(jié)點(diǎn)、指定第n個節(jié)點(diǎn)和讀取元素的地址，返回鏈表中第n個元素的值，賦給讀取變量。(5)將指定數(shù)字寫入鏈表指定位函數(shù)：傳入一個鏈表的斗節(jié)點(diǎn)、指定第n個元素和待寫入的值，將該值賦給鏈表中第n個節(jié)點(diǎn)的數(shù)據(jù)域。(6)逆置函數(shù)： 利用一個指針p,使整個鏈表尾插改頭插， 具體過程為令p為L指向的下一結(jié)點(diǎn)，斷開L

3、結(jié)點(diǎn)使之指向NULL,再將P插到L結(jié)點(diǎn)后面，且P結(jié)點(diǎn)后移一位，再插到L結(jié)點(diǎn)后面，一直重復(fù)操作直到P結(jié)點(diǎn)指向NULL,停止操作，則逆置完成，實(shí)現(xiàn)鏈表的原地逆置。(7)創(chuàng)建全零鏈表函數(shù)：根據(jù)指定鏈表長度n,創(chuàng)建一個全零的鏈表，用于后續(xù)的累加操作(8)進(jìn)位化簡函數(shù)：將鏈表中每一個節(jié)點(diǎn)的數(shù)對10取整，進(jìn)位給下一個節(jié)點(diǎn)，本節(jié)點(diǎn)的數(shù)變?yōu)閷ψ陨砣∮?，直至整個鏈表每一個節(jié)點(diǎn)的數(shù)都在0-9之間，如果節(jié)點(diǎn)數(shù)不夠進(jìn)位，則先開辟一個節(jié)點(diǎn)，連到鏈表尾部，再進(jìn)行上述進(jìn)位過程。(9)加法函數(shù)：用鏈表儲存兩個大數(shù)的數(shù)據(jù)p,q,pp,pq分別為指向的下一結(jié)點(diǎn)，利用逆置函數(shù)分別逆置數(shù)據(jù)，當(dāng)pp和pq指向均不為NULL時， 兩數(shù)相

4、加儲存在新建的一個和鏈表中； 當(dāng)pp或pq一個指向?yàn)榭諘r，另一個不為空的鏈表數(shù)據(jù)直接存儲到新建的鏈表中去，此時存在進(jìn)位情況，利用simple函數(shù)實(shí)現(xiàn)進(jìn)位運(yùn)算，最后逆置和鏈表，輸出即為兩數(shù)之和。(10)乘法函數(shù)：用鏈表儲存兩個大數(shù)的數(shù)據(jù)a,b,利用逆置函數(shù)分別逆置數(shù)據(jù)，創(chuàng)建長度為a,b長度和減1的全0積鏈表，從b的第一位開始，將b的低位依次乘以a的各位，加到積鏈表中，b每移動以為，積鏈表開始累加的第一位也向右移動一位，即實(shí)現(xiàn)豎式乘法的移位相加，再利用simplify函數(shù)實(shí)現(xiàn)進(jìn)位運(yùn)算，最后逆置積鏈表，輸出即為兩數(shù)之積。(11)銷毀鏈表算法：從頭結(jié)點(diǎn)開始，利用一個遍歷指針，依次釋放所有節(jié)點(diǎn)，直至p指

5、向NULL。四.測試數(shù)據(jù)(1)測試數(shù)據(jù)1(2)D1=100009;D2=900001(3)求D1+D2,D1*D2(4)測試數(shù)據(jù)2(5)D3=9999999999;D4=888888888(6)求D3+D4,D3*D4五.程序代碼#include#include#includetypedefintElemType;typedefstructnodeElemTypedata;/數(shù)據(jù)域structnode*next;/指針域SLinkNode;/單鏈表結(jié)點(diǎn)類型voidDestroyList(SLinkNode*L)/銷毀一個鏈表SLinkNode*pre=L,*p=pre-next;while(p

6、!=NULL)free(pre);pre=p;p=p-next;/pre、p同步后移free(pre);intGetLength(SLinkNode*L)/獲取鏈表的長度inti=0;SLinkNode*p=L-next;while(p!=NULL)i+;p=p-next;returni;voidDispList(SLinkNode*L)/輸出一個鏈表SLinkNode*p=L-next;while(p!=NULL)printf(%d,p-data);p=p-next;printf(n);intGetElem(SLinkNode*L,inti,ElemType*e)/查找鏈表的第i個元素int

7、j=0;SLinkNode*p=L;/p指向頭結(jié)點(diǎn)，計數(shù)器j置為0if(i=0)return0;/參數(shù)i錯誤返回0while(p!=NULL&jnext;)if(p=NULL)return0;未找到返回0else*e=p-data;return1;/找到后返回1)intWriteElem(SLinkNode*L,inti,ElemTypea)/寫入鏈表的第i個元素intj=0;SLinkNode*p=L;/p指向頭結(jié)點(diǎn)，計數(shù)器j置為0if(i=0)return0;/參數(shù)i錯誤返回0while(p!=NULL&jnext;)if(p=NULL)return0;未找到返回0elsep-data=a

8、;/寫入指定數(shù)字areturn1;/找到后返回1)voidCreate(SLinkNode*L,intn)/創(chuàng)建長度為n的全零鏈表SLinkNode*s,*tc;inti;tc=L;/tc始終指向尾結(jié)點(diǎn)，初始時指向頭結(jié)點(diǎn)for(i=0;inext=s;s-data=0;/將s插入tc之后tc=s;)tc-next=NULL;/尾結(jié)點(diǎn)next域置為NULL)voidCreateListR(SLinkNode*L,chara口,intn)/將給定字符數(shù)組轉(zhuǎn)為鏈表SLinkNode*s,*tc;inti;tc=L;/tc始終指向尾結(jié)點(diǎn)，初始時指向頭結(jié)點(diǎn)for(i=0;idata=(int)(ai-0

9、);/創(chuàng)建存放ai元素的新結(jié)點(diǎn)stc-next=s;/將s插入tc之后tc=s;)tc-next=NULL;/尾結(jié)點(diǎn)next域置為NULL)intLens(charc)/獲取指定字符數(shù)組的長度(inti=0;char*p=c;while(*p!=0)(i+;p+;)returni;)voidReverse(SLinkNode*L)/逆置函數(shù)，將指定鏈表原地逆置SLinkNode*p=L-next,*q;L-next=NULL;while(p!=NULL)/遍歷所有數(shù)據(jù)結(jié)點(diǎn)q=p-next;/q臨時保存p結(jié)點(diǎn)之后的結(jié)點(diǎn)p-next=L-next;/將結(jié)點(diǎn)p插入到頭結(jié)點(diǎn)之后L-next=p;p=q

10、;)intMax(inta,intb)/return(ab?a:b);)voidSimplify(SLinkNode*L)/進(jìn)位化簡函數(shù)SLinkNode*p,*q;p=L-next;q=p;while(p-next!=NULL|p-data=10)if(p-next=NULL)q=(SLinkNode*)malloc(sizeof(SLinkNode);q-data=0;p-next=q;q-next=NULL;)q=p-next;q-data=q-data+(int)(p-data/10);p-data=p-data%10;p=q;)voidAdd(SLinkNode*p,SLinkNod

11、e*q,SLinkNode*sumhead)/intmm=Max(GetLength(p),GetLength(q);比較兩數(shù)的大小，返回最大數(shù)加法函數(shù)Create(sumhead,mm);Reverse(p);Reverse(q);SLinkNode*pp=p-next,*pq=q-next,*psum=sumhead-next;while(pp!=NULL&pq!=NULL)psum-data=pp-data+pq-data;pp=pp-next;pq=pq-next;psum=psum-next;)if(pp=NULL)while(pq!=0)psum-data=pq-data;pq=p

12、q-next;psum=psum-next;)if(pq=NULL)while(pp!=0)(psum-data=pp-data;pp=pp-next;psum=psum-next;Reverse(p);Reverse(q);Simplify(sumhead);Reverse(sumhead);DispList(sumhead);printf(n);voidPlus(SLinkNode*p,SLinkNode*q,SLinkNode*plushead)/(乘法函數(shù)inti,j,k;intai,bj,ck;Reverse(p);Reverse(q);Create(plushead,(GetLen

13、gth(p)+GetLength(q)-1);for(j=1;j=GetLength(q);j+)for(k=j,i=1;i=GetLength(p);k+,i+)(GetElem(p,i,&ai);GetElem(q,j,&bj);GetElem(plushead,k,&ck);ck=ck+bj*ai;WriteElem(plushead,k,ck);Simplify(plushead);Reverse(p);Reverse(q);Reverse(plushead);DispList(plushead);printf(n);)intmain()(SLinkNodesum,plus;SLink

14、Nodec1head,c2head,c3head,c4head;charc1=100009;charc2=900001;charc3=9999999999;charc4=888888888;CreateListR(&c1head,c1,Lens(c1);CreateListR(&c2head,c2,Lens(c2);CreateListR(&c3head,c3,Lens(c3);CreateListR(&c4head,c4,Lens(c4);printf(第一組測試數(shù)據(jù)為n);DispList(&c1head);DispList(&c2head);printf(n);printf(兩數(shù)之和為n);Add(&c1head,&c2head,&sum);printf(兩數(shù)之積為n);Plus(&c1head,&c2head,&plus);printf(nn);printf(第二組測試數(shù)據(jù)為n);DispList(&c3head);DispList(&c4head);printf(n);printf(兩數(shù)之和為n);Add(&c3head,&c4head,&sum);printf(兩數(shù)之積為n);Plus(&c3head,&c4head,&plus);DestroyList(&c1head