2022年任意长整数加法运算-课程设计报告.docx

《2022年任意长整数加法运算-课程设计报告.docx》由会员分享，可在线阅读，更多相关《2022年任意长整数加法运算-课程设计报告.docx（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品_精品资料_一、【试验内容】【问题描述】设计一个实现任意长的整数进行加法运算的演示程序【基本要求】：利用双向循环链表实现长整数的储备,每个结点含一个整形变量.任何整形变量的范畴是-215 - 1215 - 1.输入和输出形式：按中国对于长整数的表示习惯,每四位一组,组间用逗号隔开.【测试数据】：（ 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

2、,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 ”.二、试验目的 、熟识把握双向循环链表的基本操作.、熟识任意长字符串的输入,并实现把字符串转化为整数.、熟识任意长整数的加法运算.、更进一步把握有关类的操作三、试验文档：任意长整数加法运算一、需求分析1、本程序实现运算任意长的整数的加法运算 . 以用户和运算机对话的

3、方式,即在运算机终端上显示“提示信息”之后, 由用户在键盘上输入演示程序中规定的运算命令,然后程序就运算并显示出这两个数的运算.2、本演示程序中,集合的元素限定为数字字符 09 和字符,与 .,输入字符可以任意长,输入形式以“回车符”为终止标志,串中字符次序不限,且答应显现重复字符.3、利用双向循环链表现实长整数的储备,每个结点含一个整形变量.输入的形式以回车终止, 可以直接输入正数或负数. 按中国对于长整数的表示习惯, 每四位一组, 除数字和位于首位置的负号外, 其它一切字符都将作为分隔符, 连续多个分隔符当一个处理.但不使用分隔符也不影响结果.4、测试数据10; 0;输出“ 0”;2-23

4、45,6789; -7654,3211;输出 “ - 1,000,000 ”;3-9999,9999; 1,0000,0000,0000;输出 “9999,0000,0001 ”;41,0001,0001; -1,0001,0001;输 出 “0”;51,0001,0001; -1,0001,0000;输 出 ”1”;6-9999,9999,9999; -9999,9999,9999;输出“ - 1,9999,9999,9998 ”;71,0000,9999,9999; 1;输出 1,0001,0000,0000.可编辑资料 - - - 欢迎下载精品_精品资料_二、概要设计为实现上述程序功能,

5、应以双向循环链表表示长整数.为此,需要定义一个抽象数据类型.1. 抽象数据类型定义为：ADT OrderedList数据对象： D=ai|aiint,i=1,2,.n, n0 数据关系： R1=|ai-1,ai D|=2,n 基本操作：Creatstring a操作结果：通过字符串a 构造两个位数不限的长整数.addtwohead0,head1 ,result初始条件： head0,head1 都已存在 , 且 head0 的肯定值比 head1 大操作结果： result等于 head0 和 head1 的和. Addhead0,head1初始条件： head0,head1 都已存在.操作结

6、果：判定head0 与 head1 肯定值的大小,并 使 head0 的 绝 对 值 比 head1 大 Displayresult初始条件： result已存在.操作结果：按四位一组,分隔符为,的格式,在屏幕上输出result.ADT OrderedList2. 本程序包含三个模块：1) 主程序模块： void main可编辑资料 - - - 欢迎下载精品_精品资料_do初始化.接受命令.处理命令.可编辑资料 - - - 欢迎下载精品_精品资料_while“命令” =”退出”2) 、集合单元模块实现集合的抽象数据类型3) 、结点结构单元模块定义集合的结点结构各模块之间的调用关系如下：块主程序

7、模块集合单元模可编辑资料 - - - 欢迎下载精品_精品资料_结点模块二、具体设计可编辑资料 - - - 欢迎下载精品_精品资料_资料word 精心总结归纳 - - - - - - - - - - - -1、ZhengshuAdd.h 文件,链表的定义部分#include#include#include using namespace std; struct LinkNodeintdata;/记录每个节点的整数 （小于10000）LinkNode *next;/记录下一个节点的的址LinkNode *pre;/记录前一个节点的的址;class LinkListprivate:LinkNode

8、*head0,*head1;/head0, head1 分别记录两个整数链表的头指针LinkNode *currptr;LinkNode *result;/result记录结果链表的头指针public:LinkList;/构造函数,初始化链表LinkList;/析构函数,释放空间voidCreatstringa;/引入字符串,创立两个链表,分别表示两个整数void Add;/实现两个整数相加void Display;/显示结果void addtwo;/ 节点多的作为被加数,少的作为加数,实现整数肯定值大的加小的;2、ZhengshuAdd.cpp 文件,链表的实现部分#includeZheng

9、shuAdd.h int sumint n;LinkList:LinkList/构造函数,初始化链表head0=new LinkNode;/ 申请一个空间记录整数的符号和节点数head1=new LinkNode; head0-next=head0;head0-pre=head0;/初始化链表,建立双向循环链表head1-next=head1; head1-pre=head1;result=new LinkNode;可编辑资料 - - - 欢迎下载精品_精品资料_学习资料 名师精选 - - - - - - - - - -第 3 页,共 13 页 - - - - - - - - - -可编辑资料

10、 - - - 欢迎下载精品_精品资料_result-next=result; result-pre=result; currptr=NULL;LinkList:LinkList/ 析构函数,释放空间LinkNode *p1=head0,*p2=head1,*p3=result;/ 三个指针分别指向三条链表的头指针whilep1.=p1-prep1-pre-next=p1-next; p1-next-pre=p1-pre; currptr=p1;p1=p1-next; delete currptr;whilep2.=p2-pre/逐个删除节点,释放空间p2-pre-next=p2-next; p

11、2-next-pre=p2-pre; currptr=p2;p2=p2-next;delete currptr;whilep3.=p3-prep3-pre-next=p3-next; p3-next-pre=p3-pre; currptr=p3;p3=p3-next; delete currptr;/ delete p1;/ delete p2;/ delete p3;void LinkList:Creatstring a/引入字符串,创立两个链表,分别表示两个整数int i=0,j=0,m=0,n=0,k=0,l=0,s=0,w=0;可编辑资料 - - - 欢迎下载精品_精品资料_/i记录字

12、符串, j记录加数节点数. s 记录被加数节点数/w标记字符串中的 - 号/k记录字符串中的字符转化为整数的值,l使每个节点记录 4 位whileam.=;m+;/m记录字符串中被加数的字符数n=m;whilean.=0 n+;ifa0=-/n记录字符串的总字符数head0-data=-1;/记录整数符号w=1;else head0-data=1; fori=m-1;i=w;i-可编辑资料 - - - 欢迎下载精品_精品资料_为整数ifai.=,/把字符转化k+=ai-0*suml; l+;可编辑资料 - - - 欢迎下载精品_精品资料_ifai=,|i=wcurrptr=new LinkNo

13、de;/把整数存到双向循环链表中currptr-data=k; currptr-next=head0;currptr-pre=head0-pre; head0-pre-next=currptr; head0-pre=currptr; head0=currptr;s+;/节点数加 1 k=0;/重新初始化 k 和 ll=0;head0-pre-data*=s;/储备整数符号和节点数可编辑资料 - - - 欢迎下载精品_精品资料_/ 与建第一个整数链表一样,建立其次个整数链表head1 k=0;l=0;ifam+1=-可编辑资料 - - - 欢迎下载精品_精品资料_elsehead1-data=-

14、1; m+;head1-data=1;可编辑资料 - - - 欢迎下载精品_精品资料_fori=n-1;im;i-ifai.=,k+=ai-0*suml; l+;ifai=,|i=m+1currptr=new LinkNode; currptr-data=k; currptr-next=head1;currptr-pre=head1-pre; head1-pre-next=currptr; head1-pre=currptr; head1=currptr;j+; k=0; l=0;head1-pre-data*=j;void LinkList:Add/实现两个整数相加LinkNode *tem

15、p;ifabshead0-pre-dataabshead1-pre-data/两个整数中,肯定值大的为被加数addtwo;else ifabshead0-pre-datapre-data可编辑资料 - - - 欢迎下载精品_精品资料_temp=head0; head0=head1; head1=temp; addtwo;else ifabshead0-pre-data=abshead1-pre-dataint k1,k2;LinkNode *p=head0,*q=head1;/ 假如节点数相同,就判定节点中数值大小whilep-data=q-data&p.=head0-pre-pre&q.=h

16、ead1-pre-prep=p-next; q=q-next;k1=p-data; k2=q-data; ifk1k2addtwo; elsetemp=head0; head0=head1; head1=temp; addtwo;void LinkList:addtwo/ 节点多的作为被加数,少的作为加数,实现整数肯定值大的加小的/默认 head0 存的整数肯定值比head1 大int s=0,m1=head0-data,m2=head1-data;m1=head0-pre-data/abshead0-pre-data;/head0的符号m2=head1-pre-data/abshead1-p

17、re-data;/head1的符号LinkNode *p=head0-pre-pre,*q=head1-pre-pre;result-data=head0-pre-data;/存结果的节点数和符号whileq.=head1-pre/head0存的整数肯定值比head1 大,即 head0 的节点数大于或等于head1可编辑资料 - - - 欢迎下载精品_精品资料_currptr=new LinkNode;currptr-data=p-data*m1+q-data*m2+s;/两整数相加ifm1*m20/假如符号相同ifabscurrptr-data-10000=0/相加后超过10000,就进位

18、s=currptr-data/10000;currptr-data=abscurrptr-data%10000;else/abscurrptr-data-10000data=abscurrptr-data;else ifm10&m2datadata+=10000; s=-1;else ifm10/ 符号不同,在此相当于实现负整数加上正整数s=0;ifcurrptr-data0/大于 0,currptr-data=10000-currptr-data; s=1;else currptr-data=abscurrptr-data;currptr-next=result;/存入链表currptr-p

19、re=result-pre;可编辑资料 - - - 欢迎下载精品_精品资料_result-pre-next=currptr; result-pre=currptr; result=currptr;p=p-pre; q=q-pre;/当 head0 节点数比 head1 长时,连续建链whilep.=head0-precurrptr=new LinkNode; currptr-data=p-data*m1+s; s=currptr-data/10000; ifm1*m20ifabscurrptr-data-10000=0s=currptr-data/10000;currptr-data=absc

20、urrptr-data%10000;else s=0;currptr-data=abscurrptr-data;else ifm10&m2datadata+=10000; s=-1;else ifm10s=0;ifcurrptr-data0currptr-data=10000-currptr-data; s=1;else currptr-data=abscurrptr-data;currptr-data=abscurrptr-data%10000; currptr-next=result;currptr-pre=result-pre; result-pre-next=currptr;可编辑资料

21、 - - - 欢迎下载精品_精品资料_result-pre=currptr; result=currptr;p=p-pre;ifs.=0/处理相加后,进位问题currptr=new LinkNode; currptr-data=abss; currptr-next=result; currptr-pre=result-pre; result-pre-next=currptr; result-pre=currptr; result=currptr;result-pre-data=m1*absresult-pre-data+1;void LinkList:Display/显示结果LinkNode

22、*p=result;int FuHao=result-pre-data/absresult-pre-data;/结果的符号whilep-data=0&p.=result-pre-pre/ 当运算后前几个节点的数据为0 时,不输出p=p-next;result-pre-data=absresult-pre-data-1*FuHao;/ 结果记录非 0 节点数coutdata;/第一显示符号和第一个节点中的数ifabsresult-pre-data.=1 p=p-next; /判定非 0 节点数是否为 1whilep.=result-pre-pre/连续输出cout,;/每 4 位一组,并用,隔开

23、cout.width4;cout.fill0;coutdata; p=p-next;ifp=result-pre-pre&absresult-pre-data.=1/ 显示最终一个节点数据可编辑资料 - - - 欢迎下载精品_精品资料_资料word 精心总结归纳 - - - - - - - - - - - -cout,; cout.width4;cout.fill0;coutdata;coutendl;int sumint n/运算 10 的乘方int i,s=1; fori=1;i=n;i+s=s*10;return s;3、main.cpp 文件,主函数和其他函数的实现#includeZh

24、engshuAdd.h/访问文件 ZhengshuAdd.hvoid main/主函数cout|=|n;cout|*|n;cout|*欢迎使用任意长整数加法系统*|n; cout|*刘伟高 *|n; cout|*|n;cout|在此系统中,可以输入任意长的整数 .|n;string ch; char Yes_No; docout|输入形式为： -*,*,*;-*,*,*,*|n;cout|即符号 +数,每 4 位加一个 ,两个数之间用 ;隔开 |n; coutch;/输入任意长字符串LinkListList;/定义链表对象List.Creatch;/把字符串转化为整数,并存到链表中List.A

25、dd;可编辑资料 - - - 欢迎下载精品_精品资料_学习资料 名师精选 - - - - - - - - - -第 11 页,共 13 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品_精品资料_资料word 精心总结归纳 - - - - - - - - - - - -/实现两个整数相加List.Display;/输出结果coutYes_No;whileYes_No=y|Yes_No=Y;/Yes_No不等于 Y或y时,程序退出cout|=|n;cout|*|n; cout|*感谢使用本系统 .*|n; cout|*|n;4、函数的调用关系图反映了演示程序的层次结

26、构：MainList.CreatchList.AddList.Display四、调试分析1、由于对任意长整数运算的算法推敲不足,是程序调试时费时不少2、本程序有些代码重复显现,从而削减了空间的利用率和增加了程序代码的杂乱 性 3、本程序模块划分比较合理,且把指针全部封装在链表模块中,操作便利.4、算法的时空分析由于链表采纳双向循环链表结构,可以从链表两头操作, 各种操作的算法时间复杂度比较合理,各函数以及确定链表中的结点位置都是O（n）,n 为链表长度.5、本试验采纳数据抽象的程序设计方法,将程序分为3 个模块,使得设计时思路清楚, 实现时调试顺当, 各模块具有较好的可重用性,的确得到了一次良

27、好的程序设计训练.五、用户手册1、本程序的运行环境为DOS操作系统2、进入演示程序后即显示文本方式的用户界面可编辑资料 - - - 欢迎下载精品_精品资料_学习资料 名师精选 - - - - - - - - - -第 12 页,共 13 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品_精品资料_资料word 精心总结归纳 - - - - - - - - - - - -3、进入界面后,就会提示输入字符串的输入形式,终止符为“回车符”.4、接受其他命令后继执行相应运算和现实相应结果六、测试结果键入 0.0 输出 0键入 y-2345 .6789.-7654 , 32

28、11 输出-1 ,0000,0000键入 y-9999 ,9999.1,0000,0000,0000 输 出 9999,0000,0001键入 y1 ,0001,0001.-1 ,0001,0000 输出 1键入 y-9999 ,9999,9999.-9999 , 9999,9999 输出-1 ,9999,9999, 9998键入 y1 ,0000,9999,9999.1 输出 1, 0001,0000,0000键入 n 退出七、附录源程序文件名清单：ZhengshuAdd.h/元素结点定义单元ZhengshuAdd.cpp/链表实现单元Main.cpp序/主程四、试验总结（心得体会） 、进一

29、步熟识把握了双向循环链表的基本操作.、熟识任意长字符串的输入,并实现把字符串转化为整数.、熟识任意长整数的加法运算.、更加熟识了函数的调用过程和调用方式5、娴熟把握了指针的定义和使用.6、通过这近一个星期的数据结构课程设计,不仅使我更加娴熟的把握了有关数 据结构的学问, 明白了程序中各个部分共同合作的过程,同时也熟识到了编写一个程序光有学问是不行的, 更要有把握全盘的才能, 从整体上把握程序的运行过程的才能.另外,在这项作业中仍更需要坚持的士气和信心.我信任,经过了这 一次的课程设计,在以后的这样的工作中我会更加娴熟的把握它们.五、参考文献：1、数据结构与算法黄定黄煜廉刘贤兴编著广东科技出版社2022 年 1 月第 1 版2、数据结构与算法学习与试验指导黄煜廉编著2022. 8可编辑资料 - - - 欢迎下载精品_精品资料_学习资料 名师精选 - - - - - - - - - -第 13 页,共 13 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载