长整数的四则运算.docx

《长整数的四则运算.docx》由会员分享，可在线阅读，更多相关《长整数的四则运算.docx（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上课程名称: 数据结构课程设计课程设计题目: 长整数的四则运算姓 名: 院系: 计算机学院专 业:计算机科学与技术 年 级: 学 号:指导教师: 2014 年月 日目 录 1 课程设计的目的32 需求分析3 3 课程设计报告内容3 3.1概要设计33.2详细设计3 3.3调试分析3 3.4用户手册4 3.5测试结果43.6程序清单5 4 小结 x 5 参考文献 81.课程设计的目的(1) 熟练使用 C 语言编写程序，解决实际问题;(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基

2、本方法和技能;(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力;2.需求分析问题描述:设计一个实现任意长的整数进行加法运算的演示程序。基本要求:利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是 -215 - 1 215 - 1。输入和输出形式:按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。测试数据:(1)0;0;应输出“0” 。(2)-;-;应输出“-” 。(3)-;00;应输出“999(4);-;应输出“0”。(5);-;应输出“1” 。(6)-9;-9;应输出“98” 。(7)99;1;应输出“00”。实现提示:(1)每个结点中可以存

3、放的最大整数为 32767，才能保证两数相加不会溢出，但若这样存放，即相当于按 32768 进制存放，在十进制与 32768 进制数之间的转换十分不方便，故可以在每个结点中仅存十进制的 4 位，即不超过 9999 的非负整数，整个链表表示为万进制。(2)可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。不能给长整数位数规定上限。3.1概要设计利用双向循环链表现实长整数的存储，每个结点含一个整形变量。输入的形式以回车结束，可以直接输入正数或负数。按中国对于长整数的表示习惯，每四位一组，除数字和位于首位置的负号外，其它一切字符都将作为分隔符，

4、连续多个分隔符当一个处理,但不使用分隔符也不影响结果。3.3调试分析测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。3.4用户手册(略)3.5测试结果(略)4总结长整数用双向循环队列的数据结构，用的比较少，查阅不少资料5、程序清单:(见附录)#include#include#include#includeusing namespace std;struct LinkNodeint data; /记录每个节点的整数（小于10000）LinkNode *next; /记录下一个节点的地址LinkNode *pre; /记

5、录前一个节点的地址;class LinkListprivate:LinkNode *head0,*head1; /head0，head1分别记录两个整数链表的头指针LinkNode *currptr;LinkNode *result; /result记录结果链表的头指针public:LinkList(); /构造函数，初始化链表LinkList(); /析构函数，释放空间void Creat(string a); /引入字符串，创立两个链表，分别表示两个整数void Add(); /实现两个整数相加void Display(); /显示结果void addtwo();/节点多的作为被加数，少的

6、作为加数，实现整数绝对值大的加小的;int sum(int n);LinkList:LinkList() /构造函数，初始化链表head0=new LinkNode;/申请一个空间记录整数的符号和节点数head1=new LinkNode;head0-next=head0;head0-pre=head0; /初始化链表，建立双向循环链表head1-next=head1;head1-pre=head1; result=new LinkNode;result-next=result;result-pre=result;currptr=NULL;LinkList:LinkList() /析构函数，释

7、放空间LinkNode *p1=head0,*p2=head1,*p3=result;/三个指针分别指向三条链表的头指针while(p1!=p1-pre) p1-pre-next=p1-next; p1-next-pre=p1-pre; currptr=p1; p1=p1-next; delete currptr;while(p2!=p2-pre) /逐个删除节点，释放空间 p2-pre-next=p2-next; p2-next-pre=p2-pre; currptr=p2; p2=p2-next; delete currptr;while(p3!=p3-pre) p3-pre-next=p

8、3-next; p3-next-pre=p3-pre; currptr=p3; p3=p3-next; delete currptr;void LinkList:Creat(string a) /引入字符串，创立两个链表，分别表示两个整数int i=0,j=0,m=0,n=0,k=0,l=0,s=0,w=0;/i记录字符串，j记录加数节点数；s记录被加数节点数 /w标记字符串中的-号 /k记录字符串中的字符转化为整数的值，l使每个节点记录4位while(am!=;) m+; /m记录字符串中被加数的字符数 n=m;while(an!=0) n+; /n记录字符串的总字符数if(a0=-) he

9、ad0-data=(-1); /记录整数符号 w=1;else head0-data=1;for(i=m-1;i=w;i-) if(ai!=,) /把字符转化为整数 k+=(ai-0)*sum(l); l+; if(ai=,|i=w) currptr=new LinkNode; /把整数存到双向循环链表中 currptr-data=k; currptr-next=head0; currptr-pre=head0-pre; head0-pre-next=currptr; head0-pre=currptr; head0=currptr; s+; /节点数加1 k=0; /重新初始化k和l l=0

10、; head0-pre-data*=s; /存储整数符号和节点数/与建第一个整数链表一样，建立第二个整数链表head1k=0;l=0;if(am+1=-) head1-data=(-1); m+;else head1-data=1;for(i=n-1;im;i-) if(ai!=,) k+=(ai-0)*sum(l); l+; if(ai=,|i=m+1) currptr=new LinkNode; currptr-data=k; currptr-next=head1; currptr-pre=head1-pre; head1-pre-next=currptr; head1-pre=currp

11、tr; head1=currptr; j+; k=0; l=0; head1-pre-data*=j;void LinkList:Add() /实现两个整数相加LinkNode *temp;if(abs(head0-pre-data)abs(head1-pre-data) /两个整数中，绝对值大的为被加数 addtwo();else if(abs(head0-pre-data)pre-data) temp=head0; head0=head1; head1=temp; addtwo();else if(abs(head0-pre-data)=abs(head1-pre-data) int k1

12、,k2; LinkNode *p=head0,*q=head1;/如果节点数相同，则判断节点中数值大小while(p-data=q-data&p!=head0-pre-pre&q!=head1-pre-pre) p=p-next; q=q-next; k1=p-data; k2=q-data; if(k1k2) addtwo(); else temp=head0; head0=head1; head1=temp; addtwo(); void LinkList:addtwo()/节点多的作为被加数，少的作为加数，实现整数绝对值大的加小的 /默认head0存的整数绝对值比head1大int s=

13、0,m1=head0-data,m2=head1-data;m1=(head0-pre-data/abs(head0-pre-data); /head0的符号m2=(head1-pre-data/abs(head1-pre-data); /head1的符号LinkNode *p=head0-pre-pre,*q=head1-pre-pre;result-data=head0-pre-data; /存结果的节点数和符号while(q!=head1-pre)/head0存的整数绝对值比head1大，即head0的节点数大于或等于head1 currptr=new LinkNode; currptr

14、-data=(p-data)*m1+(q-data)*m2+s; /两整数相加 if(m1*m2)0) /如果符号相同 if(abs(currptr-data)-10000=0) /相加后超过10000，则进位 s=currptr-data/10000; currptr-data=abs(currptr-data)%10000; else /abs(currptr-data)-10000data=abs(currptr-data); else if(m10&m2datadata+=10000; s=-1; else if(m10)/符号不同，在此相当于实现负整数加上正整数 s=0; if(cu

15、rrptr-data0) /大于0， currptr-data=10000-currptr-data; s=1; else currptr-data=abs(currptr-data); currptr-next=result; /存入链表 currptr-pre=result-pre; result-pre-next=currptr; result-pre=currptr; result=currptr; p=p-pre; q=q-pre; /当head0节点数比head1长时，继续建链while(p!=head0-pre) currptr=new LinkNode; currptr-dat

16、a=p-data*m1+s; s=currptr-data/10000; if(m1*m2)0) if(abs(currptr-data)-10000=0) s=currptr-data/10000; currptr-data=abs(currptr-data)%10000; else s=0;currptr-data=abs(currptr-data); else if(m10&m2datadata+=10000; s=-1; else if(m10) s=0; if(currptr-data0) currptr-data=10000-currptr-data; s=1; else curr

17、ptr-data=abs(currptr-data); currptr-data=abs(currptr-data)%10000; currptr-next=result; currptr-pre=result-pre; result-pre-next=currptr; result-pre=currptr; result=currptr; p=p-pre;if(s!=0) /处理相加后，进位问题 currptr=new LinkNode; currptr-data=abs(s); currptr-next=result; currptr-pre=result-pre; result-pre-

18、next=currptr; result-pre=currptr; result=currptr; result-pre-data=m1*(abs(result-pre-data)+1);void LinkList:Display() /显示结果LinkNode *p=result;int FuHao=result-pre-data/abs(result-pre-data);/结果的符号while(p-data=0&p!=result-pre-pre)/当运算后前几个节点的数据为0时，不输出 p=p-next; result-pre-data=(abs(result-pre-data)-1)*

19、FuHao;/结果记录非0节点数coutdata; /首先显示符号和第一个节点中的数if(abs(result-pre-data)!=1) p=p-next; /判断非0节点数是否为1while(p!=result-pre-pre) /继续输出 cout,; /每4位一组，并用，隔开 cout.width(4); cout.fill(0); coutdata; p=p-next;if(p=result-pre-pre&abs(result-pre-data)!=1)/显示最后一个节点数据 cout,; cout.width(4); cout.fill(0); coutdata;coutendl

20、;int sum(int n) /计算10的乘方int i,s=1;for(i=1;i=n;i+) s=s*10;return s;int main() /主函数cout-长整数的加法运算-endl;cout|输入形式为：(-)*,*,*;(-)*,*,*,*|n;string ch;char Yes_No;do coutch; /输入任意长字符串 LinkList List; /定义链表对象 List.Creat(ch); /把字符串转化为整数，并存到链表中 List.Add(); /实现两个整数相加 List.Display(); /输出结果 coutYes_No;while(Yes_No=y|Yes_No=Y); /Yes_No不等于Y或y时，程序退出6、参考文献1 严蔚敏，吴伟民 编著. 数据结构(C 语言版)-北京: 清华大学出版社，2007.2 严蔚敏，吴伟民 米 宁 编著. 数据结构题集(C 语言版)-北京: 清华大学出版社， 2007.3网上搜索相关程序作为参考专心-专注-专业