数据结构程序设计任意长的整数进行加法.doc

完整word版)数据结构程序设计任意长的整数进行加法
任意长的整数进行加法课程设计报告

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，9998”。
(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，做
{ //为标示位
number[k]=888;
break;
}
}
return number;
}
输出格式转换函数
char *test_takeprint(Linklist *list,int j) {
int length,i,remainder,shang,position=0,positionnum=0,k;
char *chfinal;
int num[100];
Lnode *now;
now=list->head->next;
chfinal=(char*)malloc(sizeof(char)*100); //为将要输出的字符穿申请内存空间
length=list->length;
shang=length/4; //求链表长度对4 的商
remainder=length%4; //求链表长度除于4的余数
if(shang==0)
remainder=0; //如果商等于0时，将余数设为0
for(i=length-1;i>=0;i--) //将保存在链表中的数值反向复制到数组中
{
num[i]=now->data;
now=now->next;
}
if(j==888) // j为结果符号标识变量，j=888时结果为负数
{
chfinal[position]=45; //在字符串第一位加上‘-’号
position++;
}
if(length<=4) //结果少与4位时不需要，添加‘，’号 直接添加到字符串中
{
for(i=0;ii
chfinal[position]=44;
position++;
}
for(i=0;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->datadata; //节点数据位赋值为要插入的值
n->next=l->head->next; //修改节点和头结点的指针
l->head->next=n;
l->length++; //链表长度加一
return l;
}
Linklist *Inlistfail(Linklist *list,int data) //结果进位时链表插入函数
{
Lnode *failn;
int i;
fail=list->head;
for(i=0;ilength;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;ilength;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;ilength - two->length;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;ilength;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=Judgment(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;
default : printf("error");
}
p=Judgementprint(listone,listtwo,j); //判断结果是否为负
iii=test_takeprint(final,p); //将储存结果的链表变成标准字符串

return iii; //返回字符串
}
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(hwnd,1001,numberone,sizeof(numberone)/sizeof(char));
char numbertwo[100];
GetDlgItemText(hwnd,1002,numbertwo,sizeof(numbertwo)/sizeof(char));
finalch=mainlist(numberone,numbertwo);
SetDlgItemText(hwnd,1004,finalch);
break;
default:break;
}
}

5 调试分析
1：进行加