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

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

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

3、L指向的下一結(jié)點(diǎn)，斷開(kāi) L結(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ù)指定鏈表長(zhǎng)度 n,創(chuàng)建一個(gè)全零的鏈表，用于后續(xù)的累加操作(8)進(jìn)位化簡(jiǎn)函數(shù)：將鏈表中每一個(gè)節(jié)點(diǎn)的數(shù)對(duì)10取整，進(jìn)位 給下一個(gè)節(jié)點(diǎn)，本節(jié)點(diǎn)的數(shù)變?yōu)閷?duì)自身取余，直至整個(gè)鏈 表每一個(gè)節(jié)點(diǎn)的數(shù)都在0-9之間，如果節(jié)點(diǎn)數(shù)不夠進(jìn)位， 則先開(kāi)辟一個(gè)節(jié)點(diǎn)，連到鏈表尾部，再進(jìn)行上述進(jìn)位過(guò)程。(9)加法函數(shù)：用鏈表儲(chǔ)存兩個(gè)大數(shù)的數(shù)據(jù) p,q, pp,pq分別為 指向的下一結(jié)點(diǎn)，利用逆置函數(shù)分別

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

5、11) 銷(xiāo)毀鏈表算法：從頭結(jié)點(diǎn)開(kāi)始，利用一個(gè)遍歷指針，依 次釋放所有節(jié)點(diǎn)，直至p指向NULL。四.測(cè)試數(shù)據(jù)(1)測(cè)試數(shù)據(jù)1(2) D1 = 100009;D2=900001(3)求 D1+D2,D1*D2(4)測(cè)試數(shù)據(jù)2(5) D3=9999999999;D4=888888888(6)求 D3+D4,D3*D4五.程序代碼#include <stdio.h>#include <stdlib.h>#include <math.h>typedef int ElemType;typedef struct node ElemType data; / 數(shù)據(jù)域struc

6、t node *next;/ 指針域 SLinkNode;/單鏈表結(jié)點(diǎn)類(lèi)型void DestroyList(SLinkNode *L)/ 銷(xiāo)毀一個(gè)鏈表 SLinkNode *pre=L,*p=pre->next;while (p!=NULL) free(pre);pre=p; p=p->next; /pre、p 同步后移free(pre);int GetLength(SLinkNode *L)/獲取鏈表的長(zhǎng)度 int i=0;SLinkNode *p=L->next;while (p!=NULL) i+;p=p->next;return i;void DispList(

7、SLinkNode *L)/輸出一個(gè)鏈表 SLinkNode *p=L->next;while (p!=NULL) printf("%d ",p->data);p=p->next;printf("n");int GetElem(SLinkNode *L,int i,ElemType *e)/查找鏈表的第 i 個(gè)元素 int j=0;SLinkNode *p=L;/p指向頭結(jié)點(diǎn)，計(jì)數(shù)器j置為0if (i<=0) return 0;/ 參數(shù) i 錯(cuò)誤返回 0while (p!=NULL && j<i) j+； p

8、=p->next;)if (p=NULL) return 0;未找到返回 0else *e=p->data;return 1;/找到后返回1)int WriteElem(SLinkNode *L,int i,ElemType a)/寫(xiě)入鏈表的第 i 個(gè)元素 int j=0;SLinkNode *p=L;/p指向頭結(jié)點(diǎn)，計(jì)數(shù)器j置為0if (i<=0) return 0;/ 參數(shù) i 錯(cuò)誤返回 0while (p!=NULL && j<i) j+;p=p->next;)if (p=NULL) return 0;未找到返回 0else p->da

9、ta=a;/寫(xiě)入指定數(shù)字areturn 1;/找到后返回1)void Create(SLinkNode*L,int n)/創(chuàng)建長(zhǎng)度為 n 的全零鏈表SLinkNode *s,*tc; int i;tc=L;/tc始終指向尾結(jié)點(diǎn)，初始時(shí)指向頭結(jié)點(diǎn)for (i=0;i<n;i+) s=(SLinkNode *)malloc(sizeof(SLinkNode);tc->next=s;s->data=0; /將s插入tc之后 tc=s;)tc->next=NULL; / 尾結(jié)點(diǎn) next 域置為 NULL )void CreateListR(SLinkNode *L,char

10、a口,int n)/將給定字符數(shù)組轉(zhuǎn)為鏈表SLinkNode *s,*tc; int i;tc=L;/tc始終指向尾結(jié)點(diǎn)，初始時(shí)指向頭結(jié)點(diǎn)for (i=0;i<n;i+) s=(SLinkNode *)malloc(sizeof(SLinkNode);s->data=(int)(ai-'0');/ 創(chuàng)建存放 ai元素的新結(jié)點(diǎn) stc->next=s; / 將 s 插入 tc 之后 tc=s;)tc->next=NULL; / 尾結(jié)點(diǎn) next 域置為 NULL )int Lens(char c)/獲取指定字符數(shù)組的長(zhǎng)度(int i=0;char *p=c

11、;while(*p!='0')(i+;p+;)return i;) void Reverse(SLinkNode *L) / 逆置函數(shù)，將指定鏈表原地逆置 SLinkNode *p=L->next,*q;L->next=NULL;while (p!=NULL)/遍歷所有數(shù)據(jù)結(jié)點(diǎn) q=p->next; /q臨時(shí)保存p結(jié)點(diǎn)之后的結(jié)點(diǎn) p->next=L->next; /將結(jié)點(diǎn)p插入到頭結(jié)點(diǎn)之后 L->next=p; p=q;)比較兩數(shù)的大小，返回最大數(shù)) int Max(int a,int b)/return(a>b?a:b);)void

12、Simplify(SLinkNode* L)/進(jìn)位化簡(jiǎ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;)加法函數(shù)void

13、Add(SLinkNode *p,SLinkNode *q,SLinkNode *sumhead)/ int mm=Max(GetLength(p),GetLength(q);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=ps

14、um->next;)if(pp=NULL)while(pq!=0)psum->data=pq->data;pq=pq->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");乘法函數(shù)void Plus(SLinkN

15、ode *p,SLinkNode *q,SLinkNode *plushead)/ (int i,j,k;int ai,bj,ck;Reverse(p);Reverse(q);Create(plushead,(GetLength(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(plushe

16、ad,k,ck);Simplify(plushead);Reverse(p);Reverse(q);Reverse(plushead);DispList(plushead);printf("n");)int main()(SLinkNode sum,plus;SLinkNode c1head,c2head,c3head,c4head;char c1="100009"char c2="900001"char c3="9999999999"char c4="888888888"CreateListR

17、(&c1head,c1,Lens(c1);CreateListR(&c2head,c2,Lens(c2);CreateListR(&c3head,c3,Lens(c3);CreateListR(&c4head,c4,Lens(c4); printf("第一組測(cè)試數(shù)據(jù)為n");DispList(&c1head);DispList(&c2head);printf("n");printf("兩數(shù)之和為n");Add(&c1head,&c2head,&sum);print

18、f("兩數(shù)之積為n");Plus(&c1head,&c2head,&plus); printf("nn");printf("第二組測(cè)試數(shù)據(jù)為n");DispList(&c3head);DispList(&c4head);printf("n");printf("兩數(shù)之和為n");Add(&c3head,&c4head,&sum); printf("兩數(shù)之積為n");Plus(&c3head,&c4head,&plus);Destro