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

重庆大学本科学生课程设计任务书 课程设计题目 长整数运算 学院 软件学院 专业 软件工程 年级 16级 已知参数和设计要求： [问题描述] 设计一个程序实现两个任意长的整数求和运算。 学生应完成的工作： [基本要求] 利用双项循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是-（215-1）~（215-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. 课程设计的工作计划： 第1~4天 完成方案设计与程序框图 第4~10天 编写程序代码 第10~15天 程序调试分析和结果 第15~20天 课程设计报告和总结 任务下达日期 2017 年 12 月 15 日 完成日期 2018年 1 月 12 日 指导教师 文俊浩 （签名） 学 生 陈勇 （签名） 说明：1、学院、专业、年级均填全称，如：光电工程学院、测控技术、2003。 2、本表除签名外均可采用计算机打印。本表不够，可另附页，但应在页脚添加页码。 1.方案设计 1.1问题描述 利用双项循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是-（215-1）~（215-1）。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。 1.2需求分析 核心问题：长整形数的进行拆分再加减 数据模型（逻辑结构）：类似汇编的带进位加法和带进位减法 存储结构：循环链表，字符数组 核心算法：字符数组提取数字，链表的加减 输入数据：两个长整形数字 输出数据：加减结果 通过以上分析，该程序具有可行性。 1.3运行环境 硬件开发环境：PC机 软件开发环境：VS2015 操作系统环境Window 1.4概要设计 整个设计的流程图 图1.1  2.算法设计 2.1算法设计思想 用两个字符数组储存输入的字符串，再将字符串中的每个4位整数转入成链表的关键节点分别储存到两个链表中，这样就让长整数分割开来，使得储存成为现实，然后再分别把两个链表的节点相加储存到另一个链表中，用flag来判断有无进位与借位，有进位flag置为1，无进位flag置为-1，最后将结果链表按照要求的格式输出即可1111,4444,5555,3334,0000,0001与1,0000,2321,9000,5555,0000相加相加3.详细设计 3.1设计思想 用字符数组来存储输入的数，用循环链表的储存整数的节点，以及计算的结果。用链表的好处可以节约空间，它可以随着数据的长短来调整大小，同时，双向循环链表也方便了查找和删除。 3.2设计关键算法 节点类： public: E element; // Value for this node Link* next; // Point to next node in list Link*prev; //Pointer to previous node // Constructors Link(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 typename E class DoubleLList { private: LinkE* head;