数据结构：长整数的加减法(任意长度的加减法).doc

第 PAGE 1页 姓名 学号 姓名 学号 班级 计算机1703 年级 大二 指导教师 《数据结构》 课程设计报告 课程设计报告名称 长整数的加法运算 实验室 实验楼502 完成日期 2018年11月30日 长整数的加法运算 目的与要求 1. 掌握线性结构的逻辑特点及存储实现； 2. 根据选题，按规范化流程完成课程设计报告： ⑴．提供需求分析。（15分） ⑵．列出概要设计。（包括：抽象数据类型的描述；程序结构图或功能模块图）（20分） ⑶．给出详细设计。（包括：①存储结构的描述；②算法的详细设计，对复杂算法，最好画出其N-S流程图；③函数的调用关系图）（30分） ⑷．进行调试分析（注：调试时遇到的问题及解决方法，程序的输出结果及对结果的分析）。（15分） ⑸. 整理设计总结。（设计心得体会，以及其他总结信息等）（10分） ⑹．附有程序清单（注：代码可具有适当注释，用来说明程序的功能、结构）。（10分） 设计步骤 需求分析：实现任意长的整数进行加法、减法运算：⑴利用链表实现长整数的存储，每个结点含一个整型变量。提醒：任何整型变量int的范围是-(2^15-1)~(2^15-1)。? ⑵输入和输出形式按照中国对于长整数的表示习惯，每四位一组,组间用逗号隔开。?如：-2345，6789，3211； 概要设计： (1)为了满足任意长的两个整数的存储和对两个整数运算的进位与借位问题，现在采用双向链表这种数据结构，其抽象类型的数据类型如下： ADT DualNode { 数据对象：D = { ai | ai∈ElemSet, i = 1, 2, …, n, n ≥ 0 } 数据关系：R = { <ai-1, ai> | ai-1, ai ∈D, i = 1, 2, …, n } 基本操作： DualList InitList(int sign); 初始条件：获取一个数字表示符号； 操作结果：构造一个空的双向链表； void DelNode(DualList L, DualNode *p) 初始条件：改节点不为； 操作结果：删除节点； void InsertNodeAtTail(DualList L, int data) 初始条件：链表L已经存在； 操作结果：向后插入一个数据 void InsertNodeAtHead(DualList L, int data) 初始条件：链表L已经存在； 操作结果：向前插入一个数据； void PrintList(DualList L) 初始条件：链表L已经存在； 操作结果：向后遍历打印节点的信息； } 程序结构图 输入两个长整数 输入两个长整数 选择计算方式 选择计算方式 减法模块加法模块 减法模块 加法模块 功能模块 长整数的运算计算方式加法减法结果输入符号位数字部分 SHAPE 长整数的运算 计算方式 加法 减法 结果 输入 符号位 数字部分 详细设计： 存储结构采用双向链表，使用头结点存放符号，后继节点存放其数字部分 3.算法描述 针对同号加法void Sub(DualList a, DualList b, DualList c) 对两个链表的节点进行的最低位进行加法，默认都需要进位，超过10000的情况，会给在操作下一位的时候在加上进位数字1，如果没有发生进位那就加上进位数0 void Add(DualList a, DualList b, DualList c) { DualList pa, pb; int carry = 0, tmp; pa = a->prior; pb = b->prior; while((pa != a) && (pb != b)) { tmp = pa->data + pb->data + carry; if (tmp >= 10000) { carry = 1; tmp -= 10000; }else carry = 0; InsertNodeAtHead(c, tmp); pa = pa->prior; pb = pb->prior; } while(pa != a) { // pb = b