十进制大整数运算设计报告.docx
《十进制大整数运算设计报告.docx》由会员分享，可在线阅读，更多相关《十进制大整数运算设计报告.docx（22页珍藏版）》请在冰点文库上搜索。
十进制大整数运算设计报告
目录
1、问题描述--------------------------------------------------1
2、需求分析--------------------------------------------------1
3、数据结构设计--------------------------------------------1
4、算法设计
（1）、概要设计---------------------------------------------1
（2）、详细设计---------------------------------------------2
5、测试分析
（1）、实际测试数据---------------------------------------3
（2）、预期的结果------------------------------------------4
（3）、实际运行结果及分析-------------------------------4
（4）、算法的时空分析及改进思想----------------------6
6、总结-------------------------------------------------------------
7、参考文献-------------------------------------------------------
8、附录-------------------------------------------------------------
问题描述
在现实生活中整数之间的运算受整型长度范围的限制，所以无法进行大整数运算，故本次设计以解决十进制大整数运算为目的。
通过使用单链表实现大整数运算。
需求分析
本次设计只需实现加减功能，用单链表存放不限大小的整数，每个结点存储一位数字（即int型数据），整数和运算符通过键盘输入，在运算前，应先对输入整数的正负进行判断，然后进行正常的加减运算，得出的结果应不限大小并能体现其的正负性。
数据结构设计
根据设计要求，本次设计选择带头结点的存储值为int型的单链表，结构如下：
typedefstructLNode
{
intdata;
structLNode*next;
}LNode,*LinkList;
算法设计
（1）、概要设计
creat_L（）:
LinkList型函数，尾插法建立单链表，通过每次将新输入的数插到链表的尾部。
模拟正常的数字书写顺序。
init_L（）；LinkList型函数，初始化链表
empty_L（LinkLista）:
布尔型函数，判断链表是否为空。
若为空，返回true，否则，返回false。
delectzero_L（LinkLista）：
LinkList型函数，在链表第一节点的后继指针不为空的情况下，检测链表第一节点数据是否为0，若为0，则删除该节点，继续检测链表，直到链表第一节点数据不为0。
模拟正常整数运算时，0不做首位的情况。
本函数分别在建立单链表和输出最终单链表时调用。
length_L（LinkLista）：
int型函数，计算链表a的长度并返回其值。
last_L（LinkLista）:
int型函数,获取单链表a最后一位值，并返回其值。
同时删除并释放原尾节点所占空间，使链表表长减一。
insert_L（LinkLista,intshu）：
LinkList型函数，将shu按头插法方式插入到链表a中，模拟正常的获取整数相加或相减值的顺序。
add_L（LinkLista,LinkListb）：
LinkList型函数。
加法运算，模拟正常的整数相加过程，默认链表a的长度大于等于链表b的长度。
用while循环语句控制相加过程，对链表a、b调用empty_L（）判断，若a为空，循环结束，输出最终链表；否则，对链表a、b调用last_L（），分别获取链表a、b尾节点数值（若b为空，则默认取值0），相加后调用insert_L（）插入到最终链表中。
其中进位方法如下：
设定一bool型数值flag和一int型数值shu，shu用来暂存a、b链表尾节点数值相加结果，flag为true时，shu的初值为1，flag为false时，shu的初值为0。
若a、b链表尾节点数值相加结果与shu值之和大于9，flag为true，否则flag为false。
mul_L（LinkLista,LinkListb）：
LinkList型函数，减法运算，模拟正常的整数相减过程，默认链表a的长度大于等于链表b的长度。
用while循环语句控制相减过程，对链表a、b调用empty_L（）判断，若a为空，循环结束，输出最终链表；否则，对链表a、b调用last_L（），分别获取链表a、b尾节点数值（若b为空，则默认取值0），相加后调用insert_L（）插入到最终链表中。
其中借位方法如下：
设定一bool型数值flag和一int型数值shu，shu用来暂存a、b链表尾节点数值相加结果，flag为true时，shu的初值为1，flag为false时，shu的初值为0。
若a、b链表尾节点数值相加结果与shu值之和大于9，flag为true，否则flag为false。
printall_L（LinkLista）：
void型函数，输出链表中的数据。
main（）：
void型函数，通过控制界面，调用以上函数，实现整个设计应有的功能。
（2）、详细设计
测试分析
（1）、实际测试数据
本次实验的测试数据共有10组，取值分别对应于正数和正数之间，负数和负数之间，正数和负数之间的加减运算以及多零值的检测。
数据如下：
①负数减负数：
-9999999999--88888888888
②负数加负数：
-123451234512345+-123412341234512345
③正数减正数：
642759273987293852-3284729834937892389
④正数加正数：
12345678987654321+98765432123456789
⑤正数减负数：
12345123451234512345--111111*********11111
⑥正数加负数：
12345123451234512345+-111111*********11111
⑦去除零值：
0-111111*********
⑧去除零值：
0023520352035+-2352000000
⑨去除零值：
123451234512345-123450000000000
（2）、预期的结果
①输出结果为：
788888888889
②输出结果为：
-246902469024690
③输出结果为：
-264197056095059
④输出结果为：
111111111110
⑤输出结果为：
23456234562345623456
⑥输出结果为：
1234012340123401234
⑦输出结果为：
-111111*********
⑧输出结果为：
35035
⑨输出结果为：
1234512345
（3）、实际运行结果及分析
①
②
③
④
⑤
⑥
⑦
⑧
⑨
实际运行结果与预期结果一致，功能全部实现。
（4）、算法的时空分析及改进思想
在本设计中，add_L（）和mul_L（）的时间复杂度为T（n），时空复杂度为O（n）。
对于主函数main（），数字与正负号是按先后顺序获取并处理的，这无疑增加了整个程序的运行时间，在以后的设计中，应将正负号和整数一同存放于同一结构中，调用统一的方法进行加减运算。
减少处理次数。
总结
通过为期五天的课程设计，自己终于完成了这个任务，不仅长舒口气，对于链表的知识，本以忘得差不多了，通过本次设计，又重新捡回来了，但对于知识点的遗忘，还是让我吃尽了苦头，本次设计遇到的第一个问题是创建链表报错，自己在定义creat_L（）函数时，没有定义一个工作指针，致使每次创建的链表都只能显示部分数据。
错误所在最终是在老师的帮助下发现的。
第二个问题是在创建第二个链表时，没有将回车键去除，导致第二链表的第一节点存放的数据是-38，后来在调用creat_L（）之前用添加getchar（）去除了回车键即可。
在设计过程中，对于每一个新创建的函数，我们可以通过输出它的每一步步骤来检查功能运行是否正常。
这样便于发现整个程序出现错误的地方。
这是最方便的方法。
参考文献
《数据结构（C语言版）》严蔚敏吴伟民编著清华大学出版社
附录
#include"stdio.h"
#include"malloc.h"
#include"stdlib.h"
//定义节点,本次实验所使用的的单链表包含头结点。
typedefstructLNode
{
intdata;
structLNode*next;
}LNode,*LinkList;
boolflag=false;
//判断单链表是否为空
boolempty_L（LinkLista）
{
if（a->next）
returnfalse;
returntrue;
}
//初始化单链表
LinkListinit_L（）
{
LinkLista;
a=（LinkList）malloc（sizeof（LNode））;
if（a）
a->next=NULL;
returna;
}
//尾插法建表
LinkListcreat_L（）
{
charch;
intn;
LinkLista,s,p;
p=a=（LinkList）malloc（sizeof（LNode））;
while（（ch=getchar（））!
='#'）
{
n=ch-'0';
s=（LinkList）malloc（sizeof（LNode））;
s->data=n;
p->next=s;
p=s;
}
p->next=NULL;
returna;
}
//向单链表中插入值（头插法）
LinkListinsert_L（LinkLista,intn）
{
LinkLists,p;
p=a;
s=（LinkList）malloc（sizeof（LNode））;
s->data=n;
s->next=p->next;
p->next=s;
returna;
}
//输出单链表的值
voidprintall_L（LinkLista）
{
a=a->next;
while（a）
{
printf（"%d",a->data）;
a=a->next;
}
printf（"\n"）;
}
//对单链表的第一个数字为零这种情况的处理
LinkListdelectzero_L（LinkLista）
{
LinkLists,p;
p=a;
s=a->next;
if（s->data==0&&s->next）
{
p->next=p->next->next;
delectzero_L（a）;
}
returna;
}
//单链表的长度
intlength_L（LinkLista）
{
intcount=0;
while（a->next!
=NULL）
{
count++;
a=a->next;
}
returncount;
}
//取单链表最后值并使单链表表长缩短单位一个单位
intlast_L（LinkLista）
{
intn;
LinkLists,p;
s=a->next;
p=a;
while（s->next）
{
s=s->next;
p=p->next;
}
p->next=NULL;
n=s->data;
free（s）;
returnn;
}
//加法运算（默认a大于b）
LinkListadd_L（LinkLista,LinkListb）
{
LinkListc;
inta1,b1,shu;
c=init_L（）;
while（!
empty_L（a））
{
if（empty_L（b））
{
a1=last_L（a）;
b1=0;
}
else
{
a1=last_L（a）;
b1=last_L（b）;
}
if（flag）//进位方法
shu=1;
else
shu=0;
if（（shu+a1+b1）<10）
{
shu=shu+a1+b1;
c=insert_L（c,shu）;
flag=false;
}
else
{
shu=（shu+a1+b1）%10;
c=insert_L（c,shu）;
flag=true;
}
}
returnc;
}
//减法运算（默认a大于b）
LinkListmul_L（LinkLista,LinkListb）
{
LinkListc;
inta1,b1,shu;
c=init_L（）;
while（!
empty_L（a））
{
if（empty_L（b））
{
a1=last_L（a）;
b1=0;
}
else
{
a1=last_L（a）;
b1=last_L（b）;
}
if（flag）//借位方法
{
if（a1!
=0）
{
a1=a1-1;
flag=false;
}
else
{
a1=9;
flag=true;
}
}
if（a1-b1>=0）
{
shu=a1-b1;
c=insert_L（c,shu）;
flag=false;
}
else
{
shu=10+a1-b1;
c=insert_L（c,shu）;
flag=true;
}
}
returnc;
}
//主函数
voidmain（）
{
LinkListinteger1,integer2,integer3;
charch,ch1,ch2,fuhao;
intnumber1,number2;
boolflag1,flag2;
integer3=（LinkList）malloc（sizeof（LNode））;
printf（"**********大整数计算**********\n"）;
printf（"请输入第一个值：
"）;
integer1=creat_L（）;
integer1=delectzero_L（integer1）;
number1=length_L（integer1）;
printf（"\n"）;
//对输入的值的正负进行判断
printf（"请输入第一值的符号:
"）;
while（（ch1=getchar（））!
='#'）
{
if（ch1=='+'）
flag1=true;
if（ch1=='-'）
flag1=false;
}
printf（"\n"）;
printf（"请输入第二个值：
"）;
getchar（）;
integer2=creat_L（）;
integer2=delectzero_L（integer2）;
number2=length_L（integer2）;
printf（"\n"）;
//对输入的值的正负进行判断
printf（"请输入第二值的符号:
"）;
while（（ch2=getchar（））!
='#'）
{
if（ch2=='+'）
flag2=true;
if（ch2=='-'）
flag2=false;
}
printf（"\n"）;
printf（"请输入运算方式：
"）;
ch=getchar（）;
while（ch!
='#'）
{
if（ch=='+'）
{
if（number1>=number2）
{
if（flag1）
{
if（flag2）
{
fuhao='';
integer3=add_L（integer1,integer2）;
}
else
{
fuhao='';
integer3=mul_L（integer1,integer2）;
}
}
else
{
if（flag2）
{
fuhao='-';
integer3=mul_L（integer1,integer2）;
}
else
{
fuhao='-';
integer3=add_L（integer1,integer2）;
}
}
}
else
{
if（flag1）
{
if（flag2）
{
fuhao='';
integer3=add_L（integer2,integer1）;
}
else
{
fuhao='-';
integer3=mul_L（integer2,integer1）;
}
}
else
{
if（flag2）
{
fuhao='';
integer3=mul_L（integer2,integer1）;
}
else
{
fuhao='-';
integer3=add_L（integer2,integer1）;
}
}
}
}
if（ch=='-'）
{
if（number1>=number2）
{
if（flag1）
{
if（flag2）
{
fuhao='';
integer3=mul_L（integer1,integer2）;
}
else
{
fuhao='';
integer3=add_L（integer1,integer2）;
}
}
else
{
if（flag2）
{
fuhao='-';
integer3=add_L（integer1,integer2）;
}
else
{
fuhao='-';
integer3=mul_L（integer1,integer2）;
}
}
}
else
{
if（flag1）
{
if（flag2）
{
fuhao='-';
integer3=mul_L（integer2,integer1）;
}
else
{
fuhao='';
integer3=add_L（integer2,integer1）;
}
}
else
{
if（flag2）
{
fuhao='-';
integer3=add_L（integer2,integer1）;
}
else
{
fuhao='';
integer3=mul_L（integer2,integer1）;
}
}
}
}
ch=getchar（）;
}
printf（"\n"）;
printf（"最终值为:
"）;
printf（"%c",fuhao）;
integer3=delectzero_L（integer3）;
printall_L（integer3）;
}
升级会员 