C语言单链表实现大数加法和乘法

1、软件技术基础一.项目题目当正整数的位数较多时，采用int或者long变量储存时会发生溢 出。可以采用一个单链表储存，每一位作为一个节点。设计完成如下 功能的算法并用给定数据进行测试。(1)由一数字字符串创建对应的整数单链表；(2)输出一个由证书单链表表示的正整数；(3)实现两个多位正整数的加法运算；(4)实现两个多位正整数的乘法运算。二算法设计(1)输入要进行处理的数据(2)输出要测试的数据(3)分别调用已定义的“求和”、“求积”函数对数据进行操作(4)打印得到的结果(5)销毁所有链表三.函数设计(1)求字符数组长度函数：传入一个字符数组的指针，用一个 指针p和一个计数变量遍历整个字符数组，返

2、回计数变量， 即为数组长度。(2)字符串转链表函数：遍历字符串，使用尾插法将数据存入 单链表中，并将字符型数据转换成整形数据，每一个节点 储存一个数字。(3)求链表长度函数：传入一个链表的头结点，用一个指针 p 和一个计数变量遍历整个链表，返回计数变量，即为链表 长度。(4)读取链表指定位数字函数：传入一个链表的头结点、指定 第n个节点和读取元素的地址，返回链表中第 n个元素的 值，赋给读取变量。(5)将指定数字写入链表指定位函数：传入一个链表的斗节点、 指定第n个元素和待写入的值，将该值赋给链表中第 n个 节点的数据域。(6)逆置函数：利用一个指针p,使整个链表尾插改头插，具体 过程为令p为

3、L指向的下一结点，断开 L结点使之指向 NULL ,再将P插到L结点后面，且P结点后移一位，再 插到L结点后面，一直重复操作直到 P结点指向NULL , 停止操作，则逆置完成，实现链表的原地逆置。(7)创建全零链表函数：根据指定链表长度 n,创建一个全零的链表，用于后续的累加操作(8)进位化简函数：将链表中每一个节点的数对10取整，进位 给下一个节点，本节点的数变为对自身取余，直至整个链 表每一个节点的数都在0-9之间，如果节点数不够进位， 则先开辟一个节点，连到链表尾部，再进行上述进位过程。(9)加法函数：用链表储存两个大数的数据 p,q, pp,pq分别为 指向的下一结点，利用逆置函数分别

4、逆置数据，当pp和pq 指向均不为NULL时，两数相加储存在新建的一个和链表 中；当pp或pq一个指向为空时，另一个不为空的链表数 据直接存储到新建的链表中去，此时存在进位情况，利用 simple函数实现进位运算，最后逆置和链表，输出即为两 数之和。(10) 乘法函数：用链表储存两个大数的数据 a, b,利用逆置 函数分别逆置数据，创建长度为a, b长度和减1的全0积 链表，从b的第一位开始，将b的低位依次乘以a的各位， 加到积链表中，b每移动以为，积链表开始累加的第一位 也向右移动一位，即实现竖式乘法的移位相加，再利用 simplify函数实现进位运算，最后逆置积链表，输出即为两 数之积。(

5、11) 销毁链表算法：从头结点开始，利用一个遍历指针，依 次释放所有节点，直至p指向NULL。四.测试数据(1)测试数据1(2) D1 = 100009;D2=900001(3)求 D1+D2,D1*D2(4)测试数据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; / 数据域struc

6、t node *next;/ 指针域 SLinkNode;/单链表结点类型void DestroyList(SLinkNode *L)/ 销毁一个链表 SLinkNode *pre=L,*p=pre->next;while (p!=NULL) free(pre);pre=p; p=p->next; /pre、p 同步后移free(pre);int GetLength(SLinkNode *L)/获取链表的长度 int i=0;SLinkNode *p=L->next;while (p!=NULL) i+;p=p->next;return i;void DispList(

7、SLinkNode *L)/输出一个链表 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 个元素 int j=0;SLinkNode *p=L;/p指向头结点，计数器j置为0if (i<=0) return 0;/ 参数 i 错误返回 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)/写入链表的第 i 个元素 int j=0;SLinkNode *p=L;/p指向头结点，计数器j置为0if (i<=0) return 0;/ 参数 i 错误返回 0while (p!=NULL && j<i) j+;p=p->next;)if (p=NULL) return 0;未找到返回 0else p->da

9、ta=a;/写入指定数字areturn 1;/找到后返回1)void Create(SLinkNode*L,int n)/创建长度为 n 的全零链表SLinkNode *s,*tc; int i;tc=L;/tc始终指向尾结点，初始时指向头结点for (i=0;i<n;i+) s=(SLinkNode *)malloc(sizeof(SLinkNode);tc->next=s;s->data=0; /将s插入tc之后 tc=s;)tc->next=NULL; / 尾结点 next 域置为 NULL )void CreateListR(SLinkNode *L,char

10、a口,int n)/将给定字符数组转为链表SLinkNode *s,*tc; int i;tc=L;/tc始终指向尾结点，初始时指向头结点for (i=0;i<n;i+) s=(SLinkNode *)malloc(sizeof(SLinkNode);s->data=(int)(ai-'0');/ 创建存放 ai元素的新结点 stc->next=s; / 将 s 插入 tc 之后 tc=s;)tc->next=NULL; / 尾结点 next 域置为 NULL )int Lens(char c)/获取指定字符数组的长度(int i=0;char *p=c

11、;while(*p!='0')(i+;p+;)return i;) void Reverse(SLinkNode *L) / 逆置函数，将指定链表原地逆置 SLinkNode *p=L->next,*q;L->next=NULL;while (p!=NULL)/遍历所有数据结点 q=p->next; /q临时保存p结点之后的结点 p->next=L->next; /将结点p插入到头结点之后 L->next=p; p=q;)比较两数的大小，返回最大数) int Max(int a,int b)/return(a>b?a:b);)void

12、Simplify(SLinkNode* L)/进位化简函数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;)加法函数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");乘法函数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("第一组测试数据为n");DispList(&c1head);DispList(&c2head);printf("n");printf("两数之和为n");Add(&c1head,&c2head,&sum);print

18、f("两数之积为n");Plus(&c1head,&c2head,&plus); printf("nn");printf("第二组测试数据为n");DispList(&c3head);DispList(&c4head);printf("n");printf("两数之和为n");Add(&c3head,&c4head,&sum); printf("两数之积为n");Plus(&c3head,&c4head,&plus);Destro