长整数的加减运算.docx
《长整数的加减运算.docx》由会员分享，可在线阅读，更多相关《长整数的加减运算.docx（37页珍藏版）》请在冰点文库上搜索。
长整数的加减运算
*******************
实践教学
*******************
兰州理工大学
技术工程学院
2013年春季学期
数据结构课程设计
题目：
长整数的加减运算
专业班级：
计算机科学与技术一班
**************************
学号：
********
***********************
成绩：
计算机科学与技术专业
数据结构课程设计任务书
（11级）
题目：
长整数的加减运算
学生姓名：
郭利强学号：
********
班级：
11级计算机科学与技术一班
题目类型：
软件工程（R）指导教师：
王连相
一．题目简介
该设计要求学生设计程序，实现两个任意长的整数求和及差的运算问题。
通过该题目的设计过程，可以加深理解线性表的逻辑结构、存储结构，掌握线性表上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。
二．主要任务
第一部分：
基本算法实现
1、线性结构基本算法实现（指导老师根据题目指定）；
2、树型结构基本算法实现（指导老师根据题目指定）；
3、图型结构基本算法实现（指导老师根据题目指定）；
4、查找基本算法实现（指导老师根据题目指定）；
5、排序基本算法实现（指导老师根据题目指定）；
第二部分：
指定题目的设计与实现
1、查阅文献资料，一般在3篇以上；
2、建立数据的逻辑结构和物理结构；
3、完成相应算法的设计；
4、完成测试工作；
5、撰写设计说明书；
6、做好答辩工作。
三．主要内容、功能及技术指标
（1）使用双向循环链表存储长整数，每个结点含一个整型变量，主要功能有：
长整数输入（建立双向循环链表）、长整数的加法、长整数的减法及结果的显示输出等；
（2）至少要用10组测试数据，算法对于这些合法的输入数据都能产生满足规格说明要求的结果；
（3）算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；对算法实现过程中的异常情况能给出有效信息；
（4）任何整型变量的范围是-（215-1）~（215-1）。
输入和输出形式：
按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开，例1，0000，0000，0000；而输入为1，0001，0001和-1，0001，0000实现加法时，应输出"1"；
（5）较高要求：
使程序在整型量范围是-（2n-1）~（2n-1）的计算机上都能有效地运行。
其中，n是由程序读入的参量。
四．提交的成果
1.设计说明书一份，内容包括：
1）中文摘要100字；关键词3-5个；
2）序言；
3）采用类c语言定义相关的数据类型
4）各模块的伪码算法
5）函数的调用关系图
6）调试分析
a、调试中遇到的问题及对问题的解决方法；
b、算法的时间复杂度和空间复杂度。
7）测试结果
8）源程序（带注释）
9）设计总结、参考文献、致谢等。
2.刻制光盘一张。
五．主要参考文献
1．严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学出版社.
2．严蔚敏，吴伟民.《数据结构题集（C语言版）》.清华大学出版社.
3．《DATASTRUCTUREWITHC++》.WilliamFord,WilliamTopp.清华大学出版社（影印版）.
4．谭浩强.《c语言程序设计》.清华大学出版社.
5．数据结构与算法分析（Java版）,APracticalIntroductiontoDataStructuresandAlgorithmAnalysisJavaEditionCliffordA.Shaffer,张铭,刘晓丹译 电子工业出版社2001年1月
六、各阶段时间安排（共2周）
周次
日期
内容
地点
第1周
星期一
教师讲解设计要求，准备参考资料
教室
星期二~三
分析设计要求，进行数据结构及算法设计
教室、实验室
星期四~五
算法设计，编程实现
实验室
第2周
星期一~三
编程上机实现、测试程序
实验室
星期四~五
检查程序，答辩
实验室
2013年6月28日
摘要
数据结构解决实际应用中的问题，将学习的理论知识应用于实践，增强学生解决实际问题的能力。
采用的基本数据结构为线性表。
计算机存储的数据是有范围限制的，对于超出存储限制的数据无法直接在计算机中计算，为此需要设计相应的程序来完成这种超出范围限制的长整数间的加减运算。
实现任意长的整形数进行加减运算的程序，要求完成长整数的加、减运算。
在这里长整数没有范围限制，可任意长。
运算后的进位、借位等都要进行正确处理，可实现动态的输入，实时的输出。
关键字：
任意长整数，加、减运算
序言
课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。
课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。
《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。
数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。
同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
在这次程序设计中我选择了长整数的代数计算这个题目，在一般的程序运算中，长整数是无法计算的，因为计算机一次能够运算的位数是有限，一旦整数很长，就需要一个程序来进行多次计算，通过这个程序，可一把一个长整数分成多个普通整数来进行计算，使得长整数也可以进行运算。
我编写的这个程序就可以进行加减乘除的运算，各个数据也可以是负数。
一、概要设计……………………………………………………………
1.1数据结构…………………………………………………………
1.2使用函数…………………………………………………………
二、流程图………………………………………………………………
三、详细设计……………………………………………………………
3.1数据结构详细设计………………………………………………
3.2链表初始化函数：
………………………………………………
3.3计算已知的链表长度：
…………………………………………
3.4插入函数：
………………………………………………………
3.5绝对值函数：
……………………………………………………
3.6读入数据并插入对应的链表函数：
……………………………
3.7输出函数…………………………………………………………
3.8加法函数（正数加上正数）……………………………………
3.9判断俩正数大小函数：
…………………………………………
3.10减法函数：
………………………………………………………
3.11整合八种情况函数：
……………………………………………
3.12主函数：
…………………………………………………………
四、调试分析………………………………………………………………
4.1调试过程中遇到的问题…………………………………………
五、使用说明和测试结果…………………………………………………
5.1使用说明…………………………………………………………
5.2测试结果…………………………………………………………
附录…………………………………………………………………………
设计总结……………………………………………………………………
参考文献……………………………………………………………………
致谢…………………………………………………………………………
一、概要设计
1.1数据结构
此实验采用的数据结构是双向循环链表。
这样可以很容易的找到他的前驱以及它的后继。
节点采用结构体类型，代码如下：
typedefstructNode//双向链表的结构体定义
{
intdata;
structNode*prior;
structNode*next;
}DLNode;
1.2使用函数
1）voidListInitiate（DLNode**head）
操作结果：
初始化一个头结点为head的双向循环链表；
2）intListLength（DLNode*head）
操作结果：
计算以head为头结点的链表的长度
3）intListInsert（DLNode*head,inti,intx）
操作结果：
将节点数据为x的节点插到第i个位置上去。
4）intabs（intx）
操作结果：
绝对值函数，返回x的绝对值。
5）intInputNumber（DLNode*head）
操作结果：
将从键盘中接收数据并把得到的数据存入以head为头结点的链表中。
四位一存，中间以逗号区分，结束符为分号。
6）voidOutputNumber（DLNode*head,intsign）
操作结果：
将以head为头结点的链表中的所有数据输出到显示屏上，
7）voidadd（DLNode*head1,DLNode*head2,DLNode*head3）
操作结果：
实现正数加正数的加法操作。
8）intchange（DLNode*head1,DLNode*head2）
操作结果：
判断存在俩个链表中的数的大小，如何head1中的数大于head2中的数那么返回值为0，反之返回值为1，相等时返回值为2；
9）voidminus（DLNode*head1,DLNode*head2,DLNode*head3）
操作结果：
计算正数减正数的减法运算。
10）voidyunsuan（DLNode*head1,DLNode*head2,DLNode*head3,charch）
操作结果：
正数，负数，加法，减法。
计算式共分为八种运算，在这之前我已经实现了二种运算，那么这个函数就是把这八种运算按照一定的规则转化成已经实现的二种运算来实现完整的加减法运算。
11）voidmain（）
操作结果：
主函数。
调用以上的各个函数来引导用户进行长整数的加法运算，加法运算.
二、函数流程图
三、详细设计
3.1数据结构详细设计
typedefstructNode//双向链表的结构体定义
{
intdata;
structNode*prior;
structNode*next;
}DLNode;
双向循环链表的节点由三个部分组成，第一是数据部分data存储此节点的数据，第二是此节点的前驱指针部分*prior指向此节点的前驱，第三是此节点的后继指针部分*next指向此节点的后继。
数据部分我们约定它为整形变量，前驱后继指针均为结构体Node类型。
3.2链表初始化函数：
voidListInitiate（DLNode**head）//双向链表的初始化
{
if（（*head=（DLNode*）malloc（sizeof（DLNode）））==NULL）exit（0）;
（*head）->prior=*head;
（*head）->next=*head;
}
初始化之前需要定义一个类型为Node型的头结点变量，经过函数后完成链表的初始化即：
头节点的前驱指针指向自己，同时他的后继指针也指向自己。
3.3计算已知的链表长度：
intListLength（DLNode*head）//双向链表的表长
{
DLNode*p=head;
intsize=0;
while（p->next!
=head）
{
p=p->next;
size++;
}
returnsize;
}
此函数计算的是已知链表的长度。
主要思想：
从头结点开始寻找下一个节点，找到计数器加一。
直到再次寻找到头结点时停止，计算完毕。
3.4插入函数：
intListInsert（DLNode*head,inti,intx）//双向链表的数据插入,i表示是插入的第几个元素
{
DLNode*p,*s;
intj;
p=head->next;
j=0;
while（p!
=head&&j{
p=p->next;
j++;
}
if（j!
=i）
{
printf（"\n插入位置不合法！
"）;
return0;
}
if（（s=（DLNode*）malloc（sizeof（DLNode）））==NULL）exit（0）;
s->data=x;
s->prior=p->prior;//插入
p->prior->next=s;
s->next=p;
p->prior=s;
return1;
}
此函数是已知一双向链表实现在第i个位置插入data为x的节点。
函数需要注意的是在什么位置插入才是合法的，在就是在该节点指针时的顺序不要搞错。
3.5绝对值函数：
intabs（intx）
{
if（x<0）return-x;
elsereturnx;
}
此函数是实现求一个整数的绝对值。
设计这么一个函数主要是考虑到在存储负数的时候头结点应该变为正整数，然后通过其他手段变相实现那种运算。
3.6读入数据并插入对应的链表函数：
intInputNumber（DLNode*head）//读入输入的数据
{
intinput,i=0;//第i个节点
charc;
scanf（"%d%c",&input,&c）;
while
（1）
{
if（input<0&&i==0）//输入数为负且是第一个节点
{
head->data=0;//将长整数的符号保存在头结点中
//input=abs（input）;//取输入数字的绝对值
ListInsert（head,i,input）;//插入数据
}
elseif（input>=0&&i==0）//输入数为正且是第一个节点
{
head->data=1;//将长整数的符号保存在头结点中
ListInsert（head,i,input）;//插入数据
}
else
{
if（head->next->data>=0）
ListInsert（head,i,input）;//非第一个节点
else
{
//input=-1*input;
ListInsert（head,i,input）;
}
}
i++;
if（c==';'）break;//遇到数据输入完成标志，跳出循环
scanf（"%d%c",&input,&c）;
}
return1;
}
此函数实现的是从键盘上得到数据根据三种情况进行不同的处理，判断是否是头结点，判断是否是整数，判断输入的字符是否是“；”分号。
并且如果是正整数它的头结点data等于1否则为0。
3.7输出函数
voidOutputNumber（DLNode*head,intsign）//从表尾输出数据元素
{
DLNode*r=head->next;
while（r->data==0&&r!
=head->prior）
{
r=r->next;
}
if（sign==1）
{
printf（"结果是:
"）;
}
else
{
printf（"结果是:
-"）;
}
printf（"%d",r->data）;
r=r->next;
while（r!
=head）
{
if（r->data<10）
{
printf（",000"）;
printf（"%d",r->data）;
}
elseif（r->data<100）
{
printf（",00"）;
printf（"%d",r->data）;
}
elseif（r->data<1000）
{
printf（",0"）;
printf（"%d",r->data）;
}
else
{
printf（",%d",r->data）;
}
r=r->next;
}
printf（"\n"）;
}
此函数实现的是将最后的结果输出到显示屏上，经过判断数据的正负和数据的范围来进行不同的处理，以保证在显示屏上显示的是正确的格式。
3.8加法函数（正数加上正数）
voidadd（DLNode*head1,DLNode*head2,DLNode*head3）{
intz=0;
inte;
DLNode*p1,*p2;
p1=head1->prior;
p2=head2->prior;
while（p1!
=head1&&p2!
=head2）
{
e=p1->data+p2->data+z;
if（e>=10000）
{
z=1;
e=e%10000;
}
elsez=0;
ListInsert（head3,0,e）;
p1=p1->prior;p2=p2->prior;
}
if（p1==head1&&p2!
=head2）
{
while（p2!
=head2）
{
e=p2->data+z;
if（e>=10000）
{
z=1;
e=e%10000;
}
elsez=0;
ListInsert（head3,0,e）;
p2=p2->prior;
}
if（z==1）ListInsert（head3,0,z）;
}
elseif（p1!
=head1&&p2==head2）{
while（p1!
=head1）
{
e=p1->data+z;
if（e>=10000）
{
z=1;
e=e%10000;
}
elsez=0;
ListInsert（head3,0,e）;
p1=p1->prior;
}
if（z==1）ListInsert（head3,0,z）;
}
else{
if（z==1）ListInsert（head3,0,z）;
}
}
此函数实现的是两个正数之间的相加运算，主要的算法和我们手算加法是一样的，首先设置一个进位计数的变量，根据存储的特点从低位开始相加带上进位即可得出相应的位和，最后更新进位变量。
处理边界状况：
如果两个链表一样长同时他们最高位在计算完成时仍然会有进位，那么应该考虑到在数据的更高位插入一个1表示最后的计算结果，这样才可以保证数据的完整性。
3.9判断俩正数大小函数：
intchange（DLNode*head1,DLNode*head2）
{
intlength1,length2,r=2;
length1=ListLength（head1）;
length2=ListLength（head2）;
DLNode*p1,*p2;
p1=head1->next;
p2=head2->next;
if（length1>length2）
{
r=0;
returnr;
}
elseif（length1{
r=1;
returnr;
}
else
{
inti=0;
for（i=0;i{
if（p1->data>p2->data）
{
r=0;
returnr;
break;
}
elseif（p2->data>p1->data）
{
r=1;
returnr;
break;
}
else
{
p1=p1->next;
p2=p2->next;
r=2;
}
}
}
returnr;
}
此函数实现的是判断俩个正数的大小。
考虑俩正数的在链表中所占存储单元的多少，多的一定大，当他们一样长时，一位一位的比较直到找到一个节点中的data比另一个链表的对应节点的data大为止。
如果最后仍是一样大那么这两个数就是一样大的。
返回值为自己约定的参数r等于2表示俩数一样大，等于1表示第二个数大，等于0表示第一个数大。
3.10减法函数：
voidminus（DLNode*head1,DLNode*head2,DLNode*head3）
{
intz=0,x=-1;
inte;
DLNode*p1,*p2;
p1=head1->prior;
p2=head2->prior;
x=change（head1,head2）;
if（x==0）
{
while（p1!
=head1&&p2!
=head2）
{
p1->data=p1->data+z;
if（p1->data>=p2->data）
{
e=p1->data-p2->data;
ListInsert（head3,0,e）;
p1=p1->prior;p2=p2->prior;
z=0;
}
else
{
e=10000+p1->data-p2->data;
ListInsert（head3,0,e）;
p1=p1->prior;p2=p2->prior;
z=-1;
}
}
p1->data=p1->data+z;
while（p1!
=head1）
{
e=p1->data;
ListInsert（head3,0,e）;
p1=p1->prior;
}
}
elseif（x==1）
{
p2=head1->prior;
p1=head2->prior;
while（p1!
=head2&&p2!
=head1）
{
p1->data=p1->data+z;
if（p1->data>=p2->data）
{
e=p1->data-p2->data;
ListInsert（head3,0,e）;
p1=p1->prior;p2=p2->prior;
z=0;
}
else
{
e=10000+p1->data-p2->data;
ListInsert（head3,0,e）;
p1=p1->prior;p2=p2->prior;
z=-1;
}
}
p1
升级会员 