重庆大学本科学生课程设计任务书——长整数运算

数据结构课程设计 方案设计重庆大学本科学生课程设计任务书课程设计题目 长整数运算学院 软件学院 专业 软件工程 年级 16 级已知参数和设计要求：问题描述设计一个程序实现两个任意长的整数求和运算。学生应完成的工作：基本要求利用双项循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是- （2 15-1）（2 15-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,000；-1,0001,0001 ；应输出“0” 。（5） 1,0001,0001；-1,0001,0000 ；应输出“1” 。目前资料收集情况（含指定参考资料）：1. Robert L. Kruse 编. Data Structures and Program Design in C+. 高等教育出版社，2001.2. 严蔚敏编. 数据结构. 清华大学出版社，2000.3. 李春葆编. 数据结构教程. 清华大学出版社，2002.4. Clifford A.Shaffer 著. 张铭，刘晓丹等译. 数据结构与算法分析(第三版).电子工业出版社，2013.10.课程设计的工作计划：第 14 天 完成方案设计与程序框图 第 410 天 编写程序代码第 1015 天 程序调试分析和结果第 1520 天 课程设计报告和总结任务下达日期 2017 年 12 月 15 日完成日期 2018 年 1 月 12 日指导教师 文俊浩 （签名） 学 生 陈勇 （签名）说明：1、学院、专业、年级均填全称，如：光电工程学院、测控技术、2003。2、本表除签名外均可采用计算机打印。本表不够，可另附页，但应在页脚添加页码。数据结构课程设计 方案设计1.方案设计1.1 问题描述利用双项循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是- （ 215-1） （2 15-1） 。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。1.2 需求分析核心问题：长整形数的进行拆分再加减数据模型（逻辑结构）：类似汇编的带进位加法和带进位减法存储结构：循环链表，字符数组核心算法：字符数组提取数字，链表的加减输入数据：两个长整形数字输出数据：加减结果通过以上分析，该程序具有可行性。1.3 运行环境硬件开发环境：PC 机软件开发环境：VS2015操作系统环境 Window 1.4 概要设计整个设计的流程图数据结构课程设计 方案设计主函数输入数据 存入链表 判断运算输出运算图 1.1数据结构课程设计 算法设计2.算法设计2.1 算法设计思想用两个字符数组储存输入的字符串，再将字符串中的每个 4 位整数转入成链表的关键节点分别储存到两个链表中，这样就让长整数分割开来，使得储存成为现实，然后再分别把两个链表的节点相加储存到另一个链表中，用 flag 来判断有无进位与借位，有进位flag 置为 1，无进位 flag 置为-1，最后将结果链表按照要求的格式输出即可2.2 算法设计的对应方式如 1,1111,4444,5555,3334,0000,0001 与 1,0000,2321,9000,5555,0000 相加图 2长整数 1 1111 4444 5555 3334 0000 0001长整数 1 0000 2321 9000 5555 0000flag 0 0 0 1(有进位)0 0 0相加1 1112 4444 7877 2334 5555 0001数据结构课程设计 详细设计3.详细设计3.1 设计思想用字符数组来存储输入的数，用循环链表的储存整数的节点，以及计算的结果。用链表的好处可以节约空间，它可以随着数据的长短来调整大小，同时，双向循环链表也方便了查找和删除。3.2 设计关键算法节点类：public:E element; / Value for this nodeLink* next; / Point to next node in listLink*prev; /Pointer to previous node/ ConstructorsLink(const E& it, Link* prevp,Link*nextval)element = it; next = nextval;prev = prevp;Link(Link*prevp = NULL,Link* nextval = NULL) next = nextval; prev = prevp; 双向循环链表类：template class DoubleLList private:Link* head; / Pointer to list headerLink* tail; / Pointer to last elementLink* curr; / Access to current elementint cnt; / Size of listpublic:void init() / Intialization helper methodcurr = tail = head = new Link(0,NULL,NULL);tail-next = head;head-prev = tail;数据结构课程设计 详细设计cnt = 1;void removeall() / Return link nodes to free storewhile (head != tail) curr = head;head = head-next;delete curr;delete head;/DoubleLList() init(); / ConstructorDoubleLList(const E&it) /constructorcurr = tail = head = new Link(it, NULL, NULL);tail-next = head;head-prev = tail;cnt = 0;DoubleLList() /Constructor,make the head element with 0curr = tail = head = new Link(0, NULL, NULL);head-next = head-prev = head;cnt = 1;/ DestructorDoubleLList() removeall(); void clear() removeall(); init(); / Clear list/ Insert it at current positionvoid insert(const E&it) curr-next = curr-next-prev = new Link(it, curr, curr-next);if (tail = head)tail = curr-next;cnt+;数据结构课程设计 详细设计void append(const E& it) / Append it to listif (cnt = 1) /当节点为1的时候head-next=head-prev=tail = new Link(it, head, head);elsetail=head-prev = tail-next = new Link(it, tail, head);cnt+;输入：void input(char *a, char *b) /输入字符串cout a;cout b;转化：（将输入的输入转化到链表中）/将储存在字符串数组中的整数转化到链表中void charTransformList(DoubleLList &L1, char a)int temp=0, r,count,flag=0 ; /temp用于存储中间每个4位整数，r用于表示在4位整数的哪个位上,count用于表示a的字符串长度,flag=0表示整数，1表示负数count = strlen(a);if (a0 = -)flag = 1;for (int i = count - 1, j = 0; i = 0+flag; i-, j+)int m = j / 5; /m用于记录第几个数r = j % 5;if (r = 4)continue;else if (r!=4&(ai 9) /当输入格式错误的时候，退出cout strlen(b)&a0 = -&b0 != -)return -1;else if(a0=-&b0!=-&strlen(a)-1=strlen(b) /当两整数长度相同，符号相反时for (int i = 0; i bi) return -1;break;if (ai+1 bi + 1) return 1;break;if (ai strlen(b) | a0 != -&strlen(a) strlen(b) - 1) /当第一个整数绝对值长度大于第二个整数绝对值长度，返回truereturn 1;else if (a0 = -&strlen(a) - 1 bi) return 1;break;if (ai + 1 bi + 1) return 1;break;if (ai &L1, DoubleLList&L2, DoubleLList&L3, char charArray1100, char charArray2100)int flag = 0, temp; /保存是否有进位或则是借位，进位为1，未进位为0，借位为-1;temp用为暂时存储链表相加的结果cout = 10000) /处理进位flag = 1;temp = temp - 10000;L3.append(temp);if (i = (L1.length() - 2) & flag = 1) /当最后有进位的时候L3.append(1);else if (L1.length() L2.length() /当L1的长度大于L2的长度L1.moveToStart();L2.moveToStart();for (int i = 0; i = 10000)flag = 1;temp -= 10000;L3.append(temp);if (i = L1.length() - 2) & flag = 1) /当最后有进位的时候L3.append(1);else /当L2的长度大于L1的长度L1.moveToStart();L2.moveToStart();for (int i = 0; i = 10000)flag = 1;temp -= 10000;L3.append(temp);if (i = L2.length() - 2) & flag = 1) /当最后有进位的时候L3.append(1);else /当符号不相同时if (aboluteValue(charArray1, charArray2) = 0) /如果两个整数绝对值大小相等，结果为0L3.append(0);else if (aboluteValue(charArray1, charArray2) 0) /如果第一个整数绝对值大于数据结构课程设计 详细设计第二个整数的绝对值L1.moveToStart();L2.moveToStart();for (int i = 0; i = L2.getValue()temp = L1.getValue() - L2.getValue() + flag;flag = 0; /没有借位elsetemp = L1.getValue() + 10000 - L2.getValue();flag = -1; /有借位elseif (L1.getValue() + flag = 0)temp = L1.getValue() + flag;flag = 0; /没有借位elsetemp = L1.getValue() + flag + 10000;flag = -1; /有借位L3.append(temp);/第二个整数大于第一个整数绝对值的时候elseL1.moveToStart();L2.moveToStart();for (int i = 0; i = L1.getValue()temp = L2.getValue() - L1.getValue() + flag;flag = 0; /没有借位elsetemp = L2.getValue()+flag + 10000 - L1.getValue();flag = -1; /有借位else /L1中整数遍历完后，只剩下L2的整数if (L2.getValue() + flag = 0)temp = L2.getValue() + flag;flag = 0; /没有借位elsetemp = L2.getValue() + flag + 10000;flag = -1; /有借位L3.append(temp);输出：void resultPrint(DoubleLListL3,int flag) /L3存储了相加的结果，flag储存了结果的正负,结果显示到屏幕上if(flag=1000)cout = 100)cout = 10)cout 00 L3.getValue();elsecout 000 L3.getValue();cout endl;数据结构课程设计 调试分析4.调试分析_ 图 6数据结构课程设计 参考文献5.总结通过半个多月的学习和实践，解决实际问题，让我对链表有了更深的了解，对数据结构产生了浓厚的兴趣，同时也让我提高了解决实际问题的能力。我们要不断的通过上机来提高自己的学习水平，在上机的同时改正了自己对某些算法的错误使用，使自己在通过程序解决问题时抓住关键算法，有了算法设计思想和流程图，并用 C+语言描绘出关键算法。以前我对数据结构（C+语言描述）的一些标准库函数不太了解，还有对函数调用的正确使用不够熟悉，还有对 C 语言中经常出现的错误也不了解，通过实践，使我在这几个方面的认识有所提高。让自己有一定的能力去改正一些常见的错误语法，很高兴这半个多月的学习让我对数据结构（C+语言描述）有了新的认识，所以后在学习过程中，我会更加注视实践操作，使自己便好地学好计算机。在这次课程设计的实验中，我收获了许多知识，通过查找大量资料，请教老师，以及不懈的努力，也培养了独立思考、动手操作的能力。我也学会了许多学习和解决实际问题的方法，让我受益匪浅。时间的紧缺成为一个很大的问题。也希望老师可以为我们知道一下以后的发展方向。如果可以让每个人都有动手焊接以及参与其他的各个流程，有专门的知道就更好了。课程设计对我来说，趣味性强，不仅锻炼能力，而且可以学到很多东西，在与老师和同学的交流过程中，互动学习，将知识融会贯通，也增强了我和同学之间的团队合作的能力。让我们知道只要努力，集中精力解决问题，一定会有收获的，过程也是很重要的。在这次课程设计中我们要学会利用时间，在规定的时间内完成我们的任务，要逐渐养成用 C+语言编写程序的良好习惯。这些对我来说都是一种锻炼，一个知识积累的过程，一种能力的提高。要打好基础，才能用更好的办法，更简洁明了的程序解决实际问题，只有这样才能进一步的取得更好的成绩。我们会更加努力，努力的去弥补自己的缺点，发展自己的优点，去充实自己，只有在了解了自己的长短之后，我们会更加珍惜拥有的，更加努力的去完善它，增进它。参考文献数据结构与算法分析第三版 （C+）数据结构课程设计 参考文献17