毕设论文 整长数的运算 算法与数据结构课程设计.docx
《毕设论文 整长数的运算 算法与数据结构课程设计.docx》由会员分享，可在线阅读，更多相关《毕设论文 整长数的运算 算法与数据结构课程设计.docx（18页珍藏版）》请在冰点文库上搜索。
毕设论文整长数的运算算法与数据结构课程设计
*******************
实践教学
*******************
兰州理工大学
软件学院
2013年春季学期
算法与数据结构课程设计
题目：
长整数的运算
专业班级：
软件二班
姓名：
齐祥荣
学号：
12700244
指导教师：
王连相
成绩：
目录
摘要1
前言2
正文3
1.采用类c语言定义相关的数据类型3
2.各模块的伪码算法3
3.函数的调用关系图6
4.调试分析7
5.测试结果7
6.源程序（带注释）8
总结15
参考文献16
致谢17
附件Ⅰ部分源程序代码18
摘要
数据结构
该设计要求学生设计程序，实现两个任意长的整数求和及差的运算问题。
通过该题目的设计过程，可以加深理解线性表的逻辑结构、存储结构，掌握线性表上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力
关键词：
双循环链表；插入；删除；长整数加减
前言
利用双向循环链表来实现对长整数的存储。
每个节点只存储四位十进制数字，即不超过9999的非负整数。
双向链表有头指针，它的data值存储长整数的符号，1为正，-1为负，0代表长整数为0；它的over值存储除头节点外节点的个数。
其他节点的data值存储四位整数，over存储该四位整数溢出0~~9999范围的情况，一般over>0表示四位数超出9999，over<0表示四位数小于0。
选择该数据结构来完成长整数的加减运算是因为要对长整数进行运算，需要对长整数进行存储，所以选择用链表对长整数存储，又由于存储的顺序是从左到右，而运算的顺序则是从右到左，这样位了操作方便选择循环链表，在运算过程中有进位和借位的操作，所以最终选择双向循环链表的数据结构。
正文
1.采用类c语言定义相关的数据类型
typedefstructDoubleNode//定义链表元素
voidInitNode（DLNode**head）//初始化链表
intInsertNode（DLNode*head,intn,DataTypex）//向链表第N个位置插入元素X
intdigit（intn）//判断整数N有几位
voidPrintNode（DLNode*head）//打印链表
voidDestroyNode（DLNode**head）//销毁链表
voidadd（DLNode*h1,DLNode*h2）//两数相加
voidjian（DLNode*h1,DLNode*h2）//两数相减
intmain（）//入口函数
2.各模块的伪码算法
1.宏定义及链表定义：
#defineN100
typedefintDataType;
typedefstructDoubleNode//定义链表元素
{DataTypedata;
structDoubleNode*prior;
structDoubleNode*next;}DLNode;
voidInitNode（DLNode**head）//初始化链表
{
每个节点只存储四位十进制数字，即不超过9999的非负整数。
双向链表有头指针，它的data值存储长整数的符号，1为正，-1为负，0代表长整数为0；
2.插入函数设计思路：
intInsertNode（DLNode*head,intn,DataTypex）//向链表第N个位置插入元素X
{DLNode*p,*nt;
inti=0;
p=head->next;
while（p!
=head&&i{
p=p->next;i++;
}
if（i!
=n）
{
printf（"插入位置错误\n"）;
return0;
}
3.加法函数设计思路：
先将各位做加减，然后根据所得长整数正负和各结点data值进位或退位计算所得长整数的值并输出。
voidadd（DLNode*h1,DLNode*h2）//两数相加
{DLNode*p1=h1->prior,*p2=h2->prior;
while（p1!
=h1&&p2!
=h2）//每个链表元素相加
{p1->data+=p2->data;
p1=p1->prior;p2=p2->prior;}
p1=h1->prior;
while（p1!
=h1->next）//处理链表元素
{if（p1->data>=10000）
{p1->prior->data+=p1->data/10000;
p1->data%=10000;}if（p1->data<0）//处理负数
{if（h1->next!
=0）
{p1->prior->data-=1;
p1->data+=10000;}
}p1=p1->prior;}
if（h1->next->data>=10000）//处理最前面的数
{InsertNode（h1,0,h1->next->data/10000）;
h1->next->next->data%=10000;}
if（h1->data<=-10000）
{InsertNode（h1,0,h1->next->data/10000）;
h1->next->next->data%=-10000;}
PrintNode（h1）;}
4.减法函数设计思路：
voidjian（DLNode*h1,DLNode*h2）//两数相减
{DLNode*p1=h1->prior,*p2=h2->prior;
while（p1!
=h1&&p2!
=h2）//每个链表元素相减
{p1->data-=p2->data;
p1=p1->prior;
p2=p2->prior;}
p1=h1->prior;
while（p1!
=h1->next）//处理链表元素
{if（p1->data>=10000）
{p1->prior->data+=p1->data/10000;
p1->data%=10000;}
if（p1->data<0）//处理负数
{if（h1->next!
=0）
{p1->prior->data-=1;
p1->data+=10000;}
}p1=p1->prior;}
if（h1->next->data>=10000）//处理最前面的数
{InsertNode（h1,0,h1->next->data/10000）;
h1->next->next->data%=10000;}
if（h1->data<=-10000）
{InsertNode（h1,0,h1->next->data/-10000）;
h1->next->next->data%=-10000;}
PrintNode（h1）;}
3.函数的调用关系图
4.调试分析
a、调试中遇到的问题及对问题的解决方法
调试过程中的困难：
在数据的运算中，应为是根据数的大小来选择运算的，所以过程相对比较繁琐。
而且对于双向链表的两个指针的定位以及链表的插入和删除等操作花费的较多的时间。
在这查阅参照了大量的网络资料。
b、算法的时间复杂度和空间复杂度
由于链表采用双向循环链表结构，可以从链表两头操作，各种操作的算法时间复杂度比较合理，各函数以及确定链表中的结点位置都是O（n）,n为链表长度。
5.测试结果
a、输入0和0做加法运算，输出“0”，结果如下图：
b、输入2345，6789和-7654，3211做减法运算，输出“1，0000，0000”，结果如下图：
c、输入1，0000，0000，0000和9999，9999做减法运算，输出“9999，0000，0001”，结果如下图：
d、输入1，0001，0001和1，0001，0001做减法运算，输出“0”，结果如下图：
e、输入1,2345,6789和9,8765,4321做加法运算，结果如下图：
6.源程序（带注释）
#include
#include
#include
#include
#defineN100
typedefintDataType;
typedefstructDoubleNode//定义链表元素
{DataTypedata;
structDoubleNode*prior;
structDoubleNode*next;}DLNode;
voidInitNode（DLNode**head）//初始化链表
{
if（（*head=（DLNode*）malloc（sizeof（DLNode）））==NULL）
exit
（1）;
（*head）->prior=*head;
（*head）->next=*head;
}
intInsertNode（DLNode*head,intn,DataTypex）//向链表第N个位置插入元素X
{DLNode*p,*nt;
inti=0;
p=head->next;
while（p!
=head&&i{
p=p->next;i++;
}
if（i!
=n）
{
printf（"插入位置错误\n"）;
return0;
}
if（（nt=（DLNode*）malloc（sizeof（DLNode）））==NULL）
exit
（1）;
nt->data=x;
nt->prior=p->prior;
nt->prior->next=nt;
nt->next=p;
p->prior=nt;
return1;
}
intdigit（intn）//判断整数N有几位
{
inti;
for（i=1;;n/=10,i++）
{
if（n/10==0）
returni;
}
}
voidPrintNode（DLNode*head）//打印链表
{DLNode*p=head->next;
inti;
while（p->data==0）//去掉前面的一串0
{p=p->next;
if（p==head）
{printf（"0\n"）;
return;
}
}
printf（"%d",p->data）;//最前面的一个数进行特殊处理,不用补零
p=p->next;
while（p!
=head）//打印后面的数字
{printf（","）;
if（p->data==0）
{
printf（"0000"）;
p=p->next;
continue;
}
for（i=0;i<4-digit（p->data）;i++）//补零
printf（"0"）;
printf（"%d",p->data）;
p=p->next;
}
printf（"\n"）;
}
voidDestroyNode（DLNode**head）
{DLNode*p,*p1;
p=（*head）->next;
while（p!
=*head）
{p1=p;
p=p->next;
free（p1）;
}
free（p）;
head=NULL;
}
voidadd（DLNode*h1,DLNode*h2）//两数相加
{DLNode*p1=h1->prior,*p2=h2->prior;
while（p1!
=h1&&p2!
=h2）//每个链表元素相加
{p1->data+=p2->data;
p1=p1->prior;p2=p2->prior;}
p1=h1->prior;
while（p1!
=h1->next）//处理链表元素
{if（p1->data>=10000）
{p1->prior->data+=p1->data/10000;
p1->data%=10000;}if（p1->data<0）//处理负数
{if（h1->next!
=0）
{p1->prior->data-=1;
p1->data+=10000;}
}p1=p1->prior;}
if（h1->next->data>=10000）//处理最前面的数
{InsertNode（h1,0,h1->next->data/10000）;
h1->next->next->data%=10000;}
if（h1->data<=-10000）
{InsertNode（h1,0,h1->next->data/10000）;
h1->next->next->data%=-10000;}
PrintNode（h1）;}
voidjian（DLNode*h2,DLNode*h1）//两数相减
{DLNode*p1=h1->prior,*p2=h2->prior;
while（p1!
=h1&&p2!
=h2）//每个链表元素相减
{p1->data-=p2->data;
p1=p1->prior;
p2=p2->prior;}
p1=h1->prior;
while（p1!
=h1->next）//处理链表元素
{if（p1->data>=10000）
{p1->prior->data+=p1->data/10000;
p1->data%=10000;}
if（p1->data<0）//处理负数
{if（h1->next!
=0）
{p1->prior->data-=1;
p1->data+=10000;}
}p1=p1->prior;}
if（h1->next->data>=10000）//处理最前面的数
{InsertNode（h1,0,h1->next->data/10000）;
h1->next->next->data%=10000;}
if（h1->data<=-10000）
{InsertNode（h1,0,h1->next->data/-10000）;
h1->next->next->data%=-10000;}
PrintNode（h1）;}
intmain（）//入口函数
{
DLNode*head1,*head2;
chardata1[N],data2[N];
chard1[10],d2[10];
inti,j,k;
intxun;
InitNode（&head1）;
InitNode（&head2）;
while
（1）
{printf（"输入数据：
\n"）;
scanf（"%s%s",data1,data2）;
InitNode（&head1）;
InitNode（&head2）;
i=0;k=0;
while（data1[i]!
=';'）//将数1用链表储存
{
for（j=0;j<10;j++）
d1[j]=0;
j=0;
while（data1[i]!
=';'&&data1[i]!
=','）
d1[j++]=data1[i++];
if（data1[i]==','）
i++;
if（data1[0]=='-'）//处理正负数
j=-（int）fabs（atoi（d1））;
elsej=atoi（d1）;
InsertNode（head1,k++,j）;
}
i=0;
k=0;
while（data2[i]!
=';'）//将数2用链表储存
{
for（j=0;j<10;j++）
d2[j]=0;j=0;
while（data2[i]!
=';'&&data2[i]!
=','）
d2[j++]=data2[i++];
if（data2[i]==','）i++;
if（data2[0]=='-'）//处理正负数
j=-（int）fabs（atoi（d2））;
elsej=atoi（d2）;
InsertNode（head2,k++,j）;}
printf（"选择加减法：
1-加法，2-减法\n"）;
scanf（"%d",&xun）;
switch（xun）
{
case1:
if（strlen（data1）>strlen（data2））//较长的数作为被加数
add（head1,head2）;
elseadd（head2,head1）;
break;
case2:
if（strlen（data1）>strlen（data2））//较长的数作为被减数
jian（head1,head2）;
elsejian（head2,head1）;
break;
default:
break;
}
DestroyNode（&head1）;
DestroyNode（&head2）;}
return0;
}
总结
关于实验本身的收获是掌握了双向链表，通过该题目的设计过程，可以加深理解线性表的逻辑结构、存储结构，掌握线性表上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。
而实验外的就是更好的利用了网路资源，通过网络的搜索引擎等。
加深了自己在这方面知识的补充。
并且在于同学交流中分析了彼此算法的优劣程度。
我觉得这是本次实验最大的收获。
参考文献
1严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学出版社.
2严蔚敏，吴伟民.《数据结构题集（C语言版）》.清华大学出版社.
3《DATASTRUCTUREWITHC++》.WilliamFord,WilliamTopp.清华大学出版社（影印版）.
4谭浩强.《c语言程序设计》.清华大学出版社.
5．数据结构与算法分析（Java版）,APracticalIntroductiontoDataStructuresandAlgorithmAnalysisJavaEditionCliffordA.Shaffer,张铭,刘晓丹译 电子工业出版社2001年1月
致谢
首先，我要感谢我的《算法与数据结构》及课程设计老师王连相老师，谢谢王老师对我的谆谆教导，让我懂得了《算法与数据结构》的理论知识，为我做课程设计奠定了理论基础。
另外，感谢王老师在我做课程设计的过程中给我提出的宝贵意见和建议，我根据王老师的建议对我的程序进行了改进，从而使程序更加完善。
最后我还要感谢，在课设的这两周给我帮助的同学们，谢谢他们给我鼓励和支持。
附件Ⅰ部分源程序代码
定义链表;
typedefintDataType;
typedefstructDoubleNode//定义链表元素
{DataTypedata;
structDoubleNode*prior;
structDoubleNode*next;}DLNode;
voidInitNode（DLNode**head）//初始化链表
{
循环结构：
while（p!
=head&&i{
p=p->next;i++;
}
if（i!
=n）
{
printf（"插入位置错误\n"）;
return0;
}
升级会员 