数据结构程序设计 任意长的整数进行加法
个性网络游戏名字-学员代表发言
任意长的整数进行加法课程设计报告
1目的：
通过课程设计，加深对《数据结构》课程所学知识的理解，熟练掌握和巩
固数据
结构的基本知识和语法规范。通过课程设计，巩固和加深对线性表、栈、队列、字符串、
树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包
括问题描述、系统
分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决
综合性实际问题的基本能力。包括
：数据类型（整形、实型、字符型、指针、数组、结
构等）；运算类型（算术运算、逻辑运算、自增自减
运算、赋值运算等）；程序结构（顺
序结构、判断选择结构、循环结构）；库函数应用等；
2
需求分析
在加法运算中，C语言所能定义的整形变量是有一定长度限制的。例如
int型变量
所能储存值的值域为-32768~32767，最长的整型long int 值域为-
2147483648~2157483646.
当在需要位数更长的整数加法时计算器设计运用简单的
加法运算符难以达到要求，或是在两
个较大整数相加的值超过了整型变量所能储存的数值是程序会发生溢
出。需要一种新的加法
模式来解决上述问题，来实现任意长的整数进行加法，得到想要的结果。
本程序完成对任意长的整数进行加法运算：
1：输入和输出形式：按中国对于长
整数的表示习惯，每四位一组，组间用逗号隔开。如：1，
0000，0000，0000，0000。
2：输入值范围为任意长的整数，输入时需输入数字和被允许的字符（‘，’，‘-’）。
3：基本功能包括大整数输入、加法运算、大整数输出。
4：测试数据为：
(1)
0；0；应输入“0”。
(2)
-2345，6789；-7654，3211；应输出“-1，0000，0000”。
(3)
-9999，9999；1，0000，0000，0000；应输出“9999，0000，0001”。
**
(4) 1，0001，0001；-1，0001，0001；应输出“0”。
(5) 1，0001，0001；-1，0001，0000；应输出“1”。
(6) -
9999，9999，9999；-9999，9999，9999；应输出“-1，9999，9999，99
98”。
(7)
1，0000，9999，9999；1；应输出“1，0001，0000，0000”。
3
概要设计
本程序使用C语言编写，编辑器为C-FREE 4.1
编译器为MinGW3.4.5 ，输入输出界
面为windows对话框。
本程序所用到的数据类型有自定义 Lnode 型
为节点类型，Lnode型变量包涵两个变
量，一个为整型的 int
data变量，另一个为Lnode 型的指针。自定义Linklist 型
变量包涵
两个变量，一个为Lnode型 的指针 head，一个是整型变量int length。
Linklist型变量为链
表类型，head为链表的头指针，整型length为链表的长度（链表
长度不包括头节点）。
本程序组成：
函数 int *Iput（char *ch）
功能：将输入的标准字符串，转换为所需要的数字储存
在int 型 数组中并返回数组指针。
函数 Linklist *CreateList(Linklist *l) 功能：
创建一个空的单链表，并返回该链表的
指针。
函数Linklist
*InList(Linklist *l,int data) 功能：在链表的头结点后插入一个节点，所需
参
数为所要插入的链表的指针，所插入节点的数据值。返回值为插入完成后的链表指针。
函数Linklist *Inlistfail(Linklist *list,int
data) 功能：当结果需要进位时，对结果进行进
位，参数为储存结果的链表，所插入节点的数据
值。返回值为插入完成后结果链表的指针。
函数Linklist
*OutList(Linklist *list) 功能：对输入的负数进行处理，使其变成标准加数或被加数。参数为储存输入数的链表指针。返回值为处理完成后的链表的指针。
函数Linklist *AddList(Linklist *one,Linklist
*two) 功能：两个标准加数和被加数，进行
加数。参数为储存加数和被加数的链表指针。返回值
为储存结果的链表。
函数Linklist *SubList(Linklist
*listone,Linklist *listtwo) 功能：两个标准减数和被减数
进行相减
。参数为储存标准减数和被减数链表指针。返回值为存储结果的链表。
函数Linklist *Linklistpush(int
*number,Linklist *list) 功能：将输入的存储在数组中的数
值依次插入到
创建好的链表中，每个链表节点储存一位输入的数值。参数为储存数值的数组
指针和创建好的链表的指针
。返回值为存储输入数值的链表的指针。
函数char
*test_takeprint(Linklist *list,int j) 功能：将储存结果的链表
里的值变为字符串
形式便于对话框输出。参数为存储结果的链表的指针，和整型输出控制变量。
函数int Judgmentsize(int *numone,int *numtwo,int
numberone,int numbertwo,int v) 功能：
对两个位数相同但符号不
同的两个数进行大小比较。参数为两个储存值的数值的指针，和两
连表的长度，和控制变量。返回值为判
断后得出的标识值。
函数int Judgment(int *numone,int
*numtwo,int numberone,int numbertwo) 功能：对输入
的两个
数值进行判断，是进行加法或是进行减法。参数为储存两个数的数组指针和两个数的
位数。返回值为判断
后的标志整型值。
函数int Judgementprint(Linklist
*listone,Linklist *listtwo,int i) 功能：对输出的值的正负
进
行判断。参数为储存两个值的链表的指针，和标识整型数。返回值为标识整型数。
函数Linklist *Caseone(Linklist *listone,Linklist
*listtwo) 功能：判断后的第一种情况对两
数的处理。参数为储存两数的链表打的指针。返回
值为处理后的储存结果的链表的指针。
函数Linklist *Casetwo(Linklist
*listone,Linklist *listtwo) 功能：判断后的第二种情况对
两数的处
理。参数为储存两数的链表打的指针。返回值为处理后的储存结果的链表的指针。
函数Linklist *Casethree(Linklist
*listone,Linklist *listtwo,int i) 功能：判断后的第三种情
况
的对两数的处理。参数为储存两数的链表的指针，和整型标识位。返回值为处理后的储存
结果的链表的指
针。
函数char *mainlist(char *numberone,char
*numbertwo) 功能：整个程序的流程。
参数为输入得到的两字符串的指针。返回值为最终要求输出的字符串的指针。
模块BOOL WINAPI Main_Proc(HWND hWnd, UINT uMsg,
WPARAM wParam, LPARAM
lParam) 对话框的定义。
模块BOOL Main_OnInitDialog(HWND hwnd, HWND
hwndFocus, LPARAM lParam)
对话框的定义。
函数 void Main_OnCommand(HWND hwnd, int id, HWND
hwndCtl, UINT codeNotify)
功能：当消息响应时操作系统所调用的函数。
主程序流程图：
同负两书相加
输出转换
输出结果
第一个数减
第二个
第二个数减
第一个
同正两数相加
输入两数
开始
数值转化链表
情况判断
相异判断
函数之间的调用关系为：
char *mainlist(char *numberone,char
*numbertwo)
调用Linklist *CreateList(Linklist
*l)
int *Input(char *ch)
Linklist
*Linklistpush(int *number,Linklist *list)
int Judgment(int *numone,int *numtwo,int
numberone,int numbertwo)
int
Judgementprint(Linklist *listone,Linklist
*listtwo,int i)
char
*test_takeprint(Linklist *list,int j)
Linklist *Caseone(Linklist *listone,Linklist
*listtwo)
Linklist *Casetwo(Linklist
*listone,Linklist *listtwo)
Linklist
*Casethree(Linklist *listone,Linklist *listtwo,int
i)
以上为平行关系
Linklist *AddList(Linklist
*one,Linklist *two)
函数调用Linklist
*Inlistfail(Linklist *list,int data)函数
int
Judgment(int *numone,int *numtwo,int numberone,int
numbertwo)
调用int Judgmentsize(int *numone,int
*numtwo,int numberone,int numbertwo,int v)函数
Linklist *Caseone(Linklist *listone,Linklist
*listtwo)
调用Linklist *AddList(Linklist
*one,Linklist *two)函数
Linklist
*Casetwo(Linklist *listone,Linklist *listtwo)
调用Linklist *OutList(Linklist *list)和Linklist
*AddList(Linklist *one,Linklist *two)函数
Linklist *Casethree(Linklist *listone,Linklist
*listtwo,int i)调用
Linklist *SubList(Linklist
*listone,Linklist *listtwo)函数
4详细设计
1:数据类型设计
typedef struct Lnode
节点类型
{
int data;
struct Lnode
*next;
}Lnode;
typedef struct Linklist
{
Lnode *head;
int length;
}Linklist;
2：输入输出函数设计
字符串转换函数
int *Input(char *ch)
{
int *number;
int i=2,j=0,k=0;
number=(int*)malloc(sizeof(int)*100);
while(i!=0)
{
链表类型
为数组分配空间
循环到字符串结束
if(ch[j]==44)
如果取到的字符为‘，’，跳过该字符继
{
转换
k--;
}
else
{
number[k]=ch[j]-48;
根据ASCL码数值等于该字符的值减去48
}
j++;
k++;
if(ch[j]==0)
转换结束，数组的最后一位赋值为888，做
{
为标示位
}
return number;
}
输出格式转换函数
char
*test_takeprint(Linklist *list,int j)
{
int length,i,remainder,shang,position=0,po
sitionnum=0,k;
char *chfinal;
number[k]=888;
break;
}
int num[100];
Lnode *now;
now=list->head->next;
chfinal=(char*)malloc(sizeof(char)*100);
为将要输出的字符穿申请内存空间
length=list->length;
shang=length4;
remainder=length%4;
if(shang==0)
remainder=0;
for(i=length-1;i>=0;i--)
{
num[i]=now->data;
now=now->next;
}
if(j==888)
{
chfinal[position]=45;
position++;
}
if(length<=4)
{
for(i=0;i
求链表长度除于4的余数
如果商等于0时，将余数设为0
将保存在链表中的数值反向复制到数组中
j为结果符号标识变量，j=888时结果为负数
在字符串第一位加上‘-’号
结果少与4位时不需要，添加‘，’号 直接添加到字符串中
{
chfinal[position]=num[i]+48;
ASC码字符与数值相差48
position++;
}
}
Else
结果大于4位是的情况
{
for(i=0;i
chfinal[position]=num[positionnum]+48;
position++;
positionnum++;
此变量为整型变量数组的取值位
}
字符串数组与整型数组的同一个数不在同
if(remainder!=0)
一位置，故要用不同的取值位
{
chfinal[position]=44;
position++;
}
for(i=0;i
for(k=0;k<4;k++)
每4位添加一个
{
}
chfinal[position]=num[positionnum]+48;
position++;
positionnum++;
}
if(i
chfinal[position]=44;
逗号的ASCII码值为44
position++;
}
}
chfinal[position]=0;
为字符串添加结束标识
return chfinal;
返回字符串
}
3：链表操作函数
链表创建函数
Linklist
*CreateList(Linklist *l)
{
l->head=(Lnode*)malloc(sizeof(Lnode));
头结点分配空间
l->head->next=NULL;
l->length=0; 链表长度为零
return l;
}
Linklist
*InList(Linklist *l,int data) 链表插入函数
{
Lnode *n;
n=(Lnode*)malloc(sizeof(Lnode));
为插入的节点分配空间
n->data=data;
n->next=l->head->next;
l->head->next=n;
l->length++;
return l;
}
Linklist
*Inlistfail(Linklist *list,int data)
{
Lnode *fail,*n;
int i;
fail=list->head;
for(i=0;i
{
fail=fail->next;
}
n=(Lnode*)malloc(sizeof(Lnode));
n->next=fail->next;
节点数据位赋值为要插入的值
修改节点和头结点的指针
链表长度加一
结果进位时链表插入函数
寻找到链表的最尾部的节点
分配一个新的节点的空间
将该节点插入到链表的最尾端
fail->next=n;
n->data=data;
list->length++;
链表长度加一
return list;
}
Linklist
*OutList(Linklist *list)
{
Lnode *temporary,*temporary2;
int i=0;
temporary=list->head;
for(i=0;i<(list->length-1);i++)
{
temporary=temporary->next;
}
temporary2=temporary->next;
temporary->next=NULL;
free(temporary2);
list->length--;
return list;
}
4：主要加减函数
Linklist *AddList(Linklist
*one,Linklist *two)
链表去负号函数
寻找到链表中保存负号的节点
修改该节点附近指针使其在链表
中删除
释放该节点内存空间
链表数值相加函数
{
int
i=0,j=3,p=0;
Lnode *nowone,*nowtwo;
nowone=one->head->next;
节点指针分别指向链表的头结点
nowtwo=two->head->next;
if(one->length==two->length)
判断两链表的长度，以便过后判断是否末位进位
p=1;
for(i=0;i
{
if(j==1)
j=1时表示该位有来至低位的进位
{
nowone->data=nowone->data+nowtwo->data+1;
该位有进位时的结果
j=0;
}
else
{
nowone->data=nowone->data+nowtwo->data;
该位没有进位的结果
}
if(nowone->data >= 10)
判断该位是否需要向高位进位
{
nowone->data=nowone->data-10;
进位后该位的值
j=1;
}
}
nowone=nowone->next;
nowtwo=nowtwo->next;
if(j==1&&p!=1)
两数位数不同，但最高位需进位时的情况
{
for(i=0;i
{
nowone->data++;
最高位向上进位一
if(nowone->data>=10)
如果该位加上来自低位的进位大于10时继
{
续向高位进位直至无需在进
nowone->data=nowone->data-10;
j=1;
nowone=nowone->next;
}
else
{
j=0;
break;
}
}
if(j==1)
如果结果的最高位也有进位
}
one=Inlistfail(one,1);
为储存结果的链表添加一个节点来保存进位
if(j==1&&p==1)
{
one=Inlistfail(one,1);
}
return one;
}
Linklist
*SubList(Linklist *listone,Linklist *listtwo)
减法函数
{
Lnode *nowone,*nowtwo;
int i=0,j=0;
nowone=listone->head->next;
定位到最低位的数值
nowtwo=listtwo->head->next;
for(i=0;i
{
if(j==1)
如果该位需向高位借位j=1
{
nowone->data=nowone->data - 1 - nowtwo->data;
该位借位后进行减法的结果
j==0;
}
else
nowone->data=nowone->data -
nowtwo->data; 无需借位情况
if(nowone->data<0)
若该位被低位借位至小
{
于零继续向高位借位
nowone->data=nowone->data+10;
借位后结果的值
j=1;
}
nowone=nowone->next;
nowtwo=nowtwo->next;
}
if(j==1)
{
while(j==1)
{
if(nowone->data==0)
{
nowone->data=9;
j=1;
nowone=nowone->next;
}
else
{
j=0;
若减数的最高位 ，仍需向高位借位，执行
向被减数的高位循环借位，直到无需在借位
}
nowone->data--;
}
}
return listone;
返回减法的到的结果
}
5:不同情况操作函数
Linklist
*Caseone(Linklist *listone,Linklist *listtwo)
{
判断后第一种情况
Linklist *final;
if(listone->length>=listtwo->length)
判断两数的位长，位数长的做为加数
final=AddList(listone,listtwo);
两数加法
else
final=AddList(listtwo,listone);
两数加法
return final;
}
Linklist
*Casetwo(Linklist *listone,Linklist *listtwo)
{
第二种情况
Linklist *final;
listone=OutList(listone);
两数值去负号，进行标准加法
listtwo=OutList(listtwo);
if(listone->length>=listtwo->length)
final=AddList(listone,listtwo);
加数与被加数相加
else
final=AddList(listtwo,listone);
return
final;
}
Linklist *Casethree(Linklist
*listone,Linklist *listtwo,int i)
{
第三种需要进行减法的情况
Linklist *final;
if(i<10)
listone=OutList(listone);
去负号操作
else
listtwo=OutList(listtwo);
if(i==7||i==16)
final=SubList(listtwo,listone);
else
{
if(listone->length>=listtwo->length)
{
final=SubList(listone,listtwo);
}
else
final=SubList(listtwo,listone);
}
return final;
}
6：主函数设计
char *mainlist(char *numberone,char
*numbertwo) 主程序函数
{
Linklist *listone,listone1;
Linklist *listtwo,listtwo1;
Linklist
*final,final1;
int i=0,j,p,experiment;
int
*num1,*num2;
char *iii;
listone=&listone1;
listtwo=&listtwo1;
final=&final1;
listone=CreateList(listone);
创建两个链表
listtwo=CreateList(listtwo);
num1=Input(numberone);
将输入的字符串复制到数组中
num2=Input(numbertwo);
listone=Linklistpush(num1,listone);
将数组中的数复制到链表
listtwo=Linklistpush(num2,listtwo);
j=Judg
ment(num1,num2,listone->length,listtwo->length);
对两数值进行判断
switch(j)
分情况进行不同操作
{
case 1 :
final=Caseone(listone,listtwo); b
case 2
: final=Casetwo(listone,listtwo); break；
case 3 :
final=Casethree(listone,listtwo,j); break;
case 4 : final=Casethree(listtwo,listone,j);
break;
case 6 :
final=Casethree(listone,listtwo,j); break;
case 7 : final=Casethree(listone,listtwo,j);
break;
case 15 :
final=Casethree(listone,listtwo,j); break;
case 16 : final=Casethree(listone,listtwo,j);
break;
return
iii; 返回字符串
}
default : printf(
}
p=Judgementprint(listone,listtwo,j);
判断结果是否为负
iii=test_takeprint(final,p);
将储存结果的链表变成标准字符串
7:对话框操作设计
void
Main_OnCommand(HWND hwnd, int id, HWND hwndCtl,
UINT codeNotify)
{
对话框主函数
char fuck[10];
fuck[0]=45;
fuck[1]=0;
char *finalch=(char*)malloc(sizeof(char)*100);
switch(id)
{
case
IDC_OK: 按钮被点击时，响应以下函数
char numberone[100];
GetDlgItemText(h
wnd,1001,numberone,sizeof(numberone)sizeof(char));
char numbertwo[100];
Ge
tDlgItemText(hwnd,1002,numbertwo,sizeof(numbertwo)
sizeof(char));
finalch=mainlist(numberone,numbertwo);
SetDlgItemText(hwnd,1004,finalch);
break;
default:break;
}
}
5
调试分析
1：进行加法时，当加数与被加数进行完加法，后当最高位有进位时，没有进
位。通过
测试数据9999+1，时 发现了这个bug。后在第一轮加法循环时，判断最高位是否要进
位，
若需要进位时，循环向高位进位直到无需在进位。
2：当结果最高位仍需要进位时
，储存结果的链表的位数不足无法在进行进位操作。解决
办法为在结果链表的最后在插入一个新的节点，
用来储存来自最高位的进位。
3：进行减法时，开始时是用位数长的数减去位数短的数值，当数
值的位数相同是，扔按
照先后顺序进行减法，照成运算bug。后新增加函数来判断位数相同时两数的大
小，判断后
做减法，保证结果正确。
4：开始时程序进行完一次运算后，程序关闭。对
用户不方便，后将控制台模式改为win32
的对话框模式，利用windows编程中操作系统反复调
用程序的模式，来达到，一次运算后
程序不关闭，重复进行计算。
5：在做对话框设计
时，结果字符串始终不输出负号，开始以为是windows的字符串与C
语言的字符串存在不一标准。
后经过仔细检查程序后，发现是标识输出符号的标识位没有被
传入输出转化函数。
6
测试结果
测试数据为
0；0；应输入“0”。
-2345，6789；-7654，3211；应输出“-1，0000，0000”。
-
9999，9999；1，0000，0000，0000；应输出“9999，0000，0001”。 **
1，0001，0001；-1，0001，0001；应输出“0”。
1，0001，0001；-1，0001，0000；应输出“1”。
-9999，999
9，9999；-9999，9999，9999；应输出“-1，9999，9999，9998”。
1，0000，9999，9999；1；应输出“1，0001，0000，0000”。
部分测试结果截图为：
7 用户使用说明
1：本程序试用操作系统为windows xp。
2：第一个输入框为输入被加数，第二个输入框为输入加数。
3：单击等号，第三个输出框，显示结果。
4：单击关闭按钮，程序结束。
8
课程设计总结
1：通过这次课程设计我对链表有了更深的的理解，更是从实际编程方面，对链表的基<
br>本，创建，插入，删除等操作有了更深的实际编程经验。
2：对自己的编程能力有了很大的进步
，对课题的理解，综合设计能力得到了一次综合
性的训练。
3：对windows编程有了初步了解。
4：同过这次课程设计也发现了自己在程序设计中
的不少缺点，例如考虑不全面等等，
同时也认识到了，好的编程风格的重要性。
5：这次课程设计做为程序设计学习中的里程碑，必将对将来的学习，工作起着巨大的
影响。
6：感谢对课程设计进行检查，批改的老师。感谢在课程设计的编写中给予过我帮助的
老师和同
学。