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

软件技术基础

一.项目题目

当正整数的位数较多时.，采用int或者10ng变量储存时会发生溢

出。可以采用一个单链表储存，每一位作为一个节点。设计完成如下

功能的算法并用给定数据进行测试。

（1）由一数字字符串创建对应的整数单链表；

（2）输出一个由证书单链表表示的正整数；

（3）实现两个多位正整数的加法运算；

（4）实现两个多位正整数的乘法运算。

二.算法设计

（1）输入要进行处理的数据

（2）输出要测试的数据

（3）分别调用已定义的“求和”、“求积”函数对数据进行操作

（4）打印得到的结果

（5）销毁所有链表

三.函数设计

（1）求字符数组长度函数：传入一个字符数组的指针，用一个

指针P和一个计数变量遍历整个字符数组，返回计数变量,

即为数组长度。

（2）字符串转链表函数：遍历字符串，使用尾插法将数据存入

单链表中，并将字符型数据转换成整形数据，每一个节点

储存一个数字。

（3）求链表长度函数：传入一个链表的头结点，用一个指针p

和一个计数变量遍历整个链表，返回计数变量，即为链表

长度。

（4）读取链表指定位数字函数：传入一个链表的头结点、指定

第n个节点和读取元素的地址，返回链表中第n个元素的

值，赋给读取变量。

（5）将指定数字写入链表指定位函数:传入一个链表的斗节点、

指定第n个元素和待写入的值，将该值赋给链表中第n个

节点的数据域。

（6）逆置函数：利用一个指针p,使整个链表尾插改头插，具体

过程为令p为L指向的卜一结点，断开L结点使之指向

NULL,再将P插到L结点后面，且P结点后移一位，再

插到L结点后面，一直重复操作直到P结点指向NULL,

停止操作，则逆置完成，实现链表的原地逆置。

（7）创建全零链表函数：根据指定链表长度n,创建一个全零

四.测试数据

(1)测试数据1

(2)Dl=l()()(X)9;D2=900001

(3)求D1+D2,D1*D2

(4)测试数据2

(5)D3=9999999999;D4=888888888

(6)求D3+D4,D3*D4

五.程序代码

#include<stdio.h>

#incIude<stdIib.h>

#include<math.h>

typedefintEIemType;

typedefstructnode

(ElemTypedata;〃数据域

structnode*next;//指针域

}SLinkNode;〃单链表结点类型

voidDestroyList(SLinkNode*L)〃销毁一个链表

{SLinkNode*pre=L,*p=pre->next;

whiIe(p!=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;

1

returni;

}

voidDispList(SLinkNode*L)〃输出一个链表

{SLinkNode*p=L->next;

while(p!二NULL)

{printf("%d",p->data);

p=p->next;

1

printf("\n");

)

intGetEIem(SLinkNode*L,inti,ElemType*e)〃查找链表的第i个元素

{intj=0;

SLinkNode*p=L;〃p指向头结点，计数器J置为0

if(i<=0)return0;〃参数i错误返回0

whiIe(p!=NULL&&j<i)

{j++；

p=p->next;

}

if(p==NULL)return0;〃未找到返回0

eIse

{*e=p->data;

return1;〃找到后返回1

)

)

intWriteEIem(SLinkNode*L,inti,EIemTypea)〃写入链表的第i个元素

{intj=0;

SLinkNode*p=L;〃p指向头结点，计数器j置为0

if(i<=0)return0;〃参数i错误返回0

whiIe(p!=NULL&&j<i)

{j++；

p=p->next;

1

if(p二二NULL)return0;〃未找到返回0

eIse

{p->data=a;〃写入指定数字a

return1;//找到后返回1

)

)

voidCreate(SLinkNode*L,intn)〃创建长度为n的全零链表

(

SLinkNode*s,*tc;inti;

tc=L;//tc始终指向尾结点,初始时指向头结点

for(i=0;i<n;i++)

{s=(SLinkNode*)maIIoc(sizeof(SLinkNode));

tc->next=s;

s->data=0;〃将s插入tc之后

tc二s;

)

tc->next=NULL;〃尾结点next域置为NULL

)

voidCreateListR(SLinkNode*L,chara口，intn)〃将给定字符数组转为链表

(

SLinkNode*s,*tc;inti;

tc=L;//tc始终指向尾结点,初始时指向头结点

for(i=0;i<n;i++)

{s=(SLinkNode*)maIIoc(sizeof(SLinkNode));

s->data=(int)(a[i]-'0')；〃创建存放a[i]元素的新结点s

tc->next=s;〃将s插入tc之后

tc=s;

)

tc->next=NULL;〃尾结点next域置为NULL

)

intLens(charc口)//获取指定字符数组的长度

(

inti=0;

char*p=c;

while(*p!='\0')

(

i++；

P++；

)

returni;

)

voidReverse(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;

PF；

}

1

intMax(inta,intb)//比较两数的大小，返回最大数

(

return(a>b?a:b):

)

voidSimpIify(SLinkNode*L)〃进位化简函数

(

SLinkNode*p,*q:

p=L->next;

q二P；

whiIe(p->next!=NULL||p->data>=10)

{

if(p->next==NULL)

q=(SLinkNode*)maIloc((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；

)

1

voidAdd(SLinkNodexp,SLinkNode*q,SLinkNode*sumhead)〃加法函数

(

intmm=Max(GetLength(p),GetLength(q));

Create(sumhead,mn);

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=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);

SimpIify(sumhead);

Reverse(sumhead);

DispList(sumhead);

printf("\n");

)

voidPIus(SLinkNode*p,SLinkNode*q,SLinkNode*pIushead)〃乘法函数

(

inti,j,k;

intai,bj,ck;

Reverse(p);

Reverse(q);

Create(pIushead,(GetLength(p)+GetLength(q)-1));

for(j=1;j<=GetLength(q);j++)

for(k=j,i=1;i<=GetLength(p);k++,i++)

I

GetElem(p,i,&ai);

GetElem(q,j,&bj);

GetElem(pIushead,k,&ck);

ck=ck+bj*ai;

WriteEIem(pIushead,k,ck);

)

SimpIify(pIushead);

Reverse(p);

Reverse(q);

Reverse(pIushead);

DispList(pIushead);

printf("\n"):

)

intmain()

SLinkNodesum,plus;

SLinkNodedhead,c2head,c3head,c4head;

charc1[]={-100009");

charc2[]={-900001"};

charc3[]=("9999999999");

charc4[]=("888888888");

CreateListR(&dhead,d,Lens(cD);

CreateListR(&c2head,c2,Lens(c2));

CreateListR(&c3head,c3,Lens(c3));

CreateListR(&c4head,c4,Lens(c4));

printf(”第一组测试数据为\rT);

DispList(&c1head);

DispList(&c2head);

printf("\n");

printf("两数之和为\n");

Add(&c1head,&c2head,&sum);

printf("两数之积为\n");

PIus(&c1