《长整数的加法运算-数据结构与算法课程设计》由会员分享，可在线阅读，更多相关《长整数的加法运算-数据结构与算法课程设计（11页珍藏版）》请在金锄头文库上搜索。
1、课程设计（论文）说明书题目：长整数的加法运算学 院：计算机科学与工程学院专业：信息安全学号:指导教师：2014年10月18日目录引言 41、系统概述42、系统分析52.1需求分析 52.2系统功能 52.3开发环境 53、详细设计53.1功能结构框图 63.2 软件设计 63.2.1 定义链表与接收数据输入 63.2.2长整数的加法运算 83.2.3显示长整数相加结果 104、所遇到的问题和分析解决105、系统特色及关键技术116、结论 11参考文献 12引言随着计算机技术的发展，人们利用计算机开发了许许多多方便的，实用的应 用软件，在信息化的现代社会里，人们依赖着很多的应用软件，这些软件在推
2、进 社会发展的同时，也丰富了人们的生活，然而，在开发过程中，由于计算机系统 的局限性，在需要某些功能时，总会遇到困难。例如在开发某些工程项目时，有 时需要对很大的数进行计算。但是计算机本身无法计算某些较大的数，所以我们 有必要设计专门的算法对一些较大的数进行相应的计算，通过简化运算之后，对 其他程序功能的编写能起到良好的促进作用，大大的减轻了程序员的负担。此次 设计的程序将用于长整数的加法运算，程序运行时，将提示用户输入两个长整数， 然后将两个长整数相加的结果输出。1、系统概述在该长整数加法运算系统中，我将定义双向循环链表来表示长整数，按照中 国对长整数的表示方法，如 199999999 表示
3、为 1,9999,9999。双向循环链表数据 域存储的是长整数的每 4 位。双向链表也叫双链表，是链表的一种，它的每个数 据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的 任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。通过造双向 循环链表，可以对长整数进行方便的存储，在对长整数进行数学运算时，也能通 过方便的操作链表，从而对长整数进行需要的计算。在实现该长整数加法运算的系统中，我将会编程实现以下功能。定义一个函 数，用于接收长整数的输入，同时将长整数存储到双向循环链表当中，为了检验 是否按预期要求进行存储，我还会编写一个函数，将双向循环链表中数据域的值 打印
4、出来。定义一个长整数相加的函数，实现两个长整数加法运算的功能，实际 上是对双向循环链表进行操作，这里包括结点空间的申请，插入结点，修改指针 所保存的值。当两个长整数完成加法运算后，我会定义一个显示结果的函数，将它们相加 的结果打印出来。一些较大的整数，在单纯的用计算机进行相加运算的时候可能 会产生溢出现象，但该系统每次只对 4 位整数进行运算，避免了数据过大在计算 时产生的溢出问题。2、系统分析2.1 需求分析设计一个计算两个长整数加法的程序，要求长整数的位数不能规定上限。根 据中国对于长整数的表示习惯，长整数每 4 位用逗号隔开。故可以利用双向循环 链表对长整数进行存储，每个结点可以存储长整
5、数的 4 位，即每个结点的数据域 最大值为 9999，头结点的数据域的值的正负号可以表示长整数的正负，其绝对 值可以表示结点数目。为了运算与编程的方便，在相加过程中不要破坏两个操作 数链表。2.2 系统功能（1）建立双向循环链表，用于保存长整数及长整数的运算。（2）接收长整数的输入，长整数的每 4位都保存到链表的结点中。（3）对存入双向链表的长整数进行加法运算，在进行运算时，能很好的处理进 位，借位问题以及对长整数的正负能做出判断，然后进行相应的运算处理，保证 运算结果能与预期结果一致。（4）正确的输出运算后的结果，这里的运算结果也是长整数，故对数的存储也 是采用双向循环链表，输出结果即是按长
6、整数的显示方式打印出双向循环链表数 据域的值。2.3 开发环境所用开发环境为微软公司开发的 VC+6.0 软件，该软件可将“高级语言”翻 译为“机器语言”，该程序开发语言为C语言。3、详细设计3.1功能结构框图图3-1系统功能结构框图这是长整数相加运算的一个设计思路。在该系统中，我会设置几个函数，分别 实现不同的功能，如接收数据输入的函数，将两个长整数进行相加的函数，显示 出长整数相加结果的函数。重点是在加法运算的函数里，在功能结构框图中只是 大致的介绍出设计思路，分3种情况考虑，具体在每种情况里，也分许多细小的 情况进行处理。该系统重要的部分是对双向循环链表进行操作。3.2软件设计3.2.1
7、定义链表与接收数据输入因为该系统的功能是对长整数进行运算，所以对长整数是用双向循环链表进 行存储，链表每个结点均存储绝对值不超过9999的整数，在进行运算时，依次 对每个结点进行运算，再判断是否需要进位和借位。该系统主要使用的数据结构 是双向循环链表，无任何特殊的算法，只有对双向循环链表的一些简单操作，如 插入操作，注意前驱指针和后继指针发生变化时的修改即可。（1）定义双向循环链表的抽象数据类型打定义结点的数据域和指针域，用结构休进行封装typedef struct Nodeint data;/结点数据域作为指向结点的指针struct Node *pre;/指向町区结点 struct Node
8、 *next;/指向后继结点 JNODE；typedeF struct Node *PN0DE ;/gjPN0DE,图3-2双向循环链表的结点定义此双向循环链表中，定义了一个头结点来保存长整数的信息，即头结点的 正负表示该长整数的正负，头结点数据域的绝对值表示双向循环链表除头结点外 的结点个数。为了后面的编程方便，将结点类型重命名为PN0DE。头结点数据域 的信息对于加法运算起到一定的作用。用双向循环链表来保存长整数，避免了长 整数位数达到上限的问题，间接的解决了计算机无法计算某些较大整数的问题。 同时，定义了一个双链表类型的结构体，对双向循环链表的头指针和尾指针进行 封装，双链表类型的结构体
9、可以准确的表示长整数。同样为了后续的编程方便， 将双向循环链表类型的结构体重命名为List。数据类型如下图所示，定义双错表类型struct DoubleListnext-data的正负以及统计出除头结点外的其 他结点个数，然后将结果保存到头结点的数据域中，用于表示长整数的正负及长 整数的位数长度。为了确定长整数已经按预期的形式保存到双向循环链表当中， 我设置了一个打印链表的函数，从头结点的后继结点开始对链表进行访问，直到 访问到链表最后一个结点为止，将链表中的每个结点数据域打印出来，观察其结 果。如果某个结点的数据域的值为 0000，打印链表时显示出来的结果是 0，这对 后面的计算没有影响，类
10、似于这样的问题在计算完长整数后，显示结果时会进行 处理，此时仅是确认链表中数据域的信息。长整数接收输入完毕后，已经保存到一个带有头结点的链表当中了，为了后 续的计算方便，需要对该双向循环链表设置一个尾指针。定义一个函数，用于设 置双向循环链表的尾指针，在该函数中定义一个 PNODE 类型的变量 p，p 从链 表的头结点的后继结点开始进行访问，当 p 访问到链表的最后一个结点时，结束 循环，将p作为函数的返回值返回，此时p表示的便是该双向循环链表的尾指针。 因为在加法的操作中，都是先对双向循环链表的最后一个结点进行操作，所以设 置尾指针是很方便的，很有必要的。3.2.2 长整数的加法运算长整数是
11、用双向循环链表进行存储的，对长整数进行加法运算，相当于对双 向循环链表操作。在此程序当中，进行加法运算时，可分为3 种不同的情况，即 两正数相加，两负数相加，两符号互异的数进行相加，符号互异的两数在进行运 算时，可视为做减法运算。下面进行详细的介绍。链表相加操作时，采用的思路 是将长度较短的链表加到长度较长的链表中，所以在相加之前，先计算出两个链 表的长度，用长度较长的链表先保存计算结果，最后将结果赋给“结果”链表。 为了说明及编程方便，用p指向长链表的尾结点，用q指向短链表的尾结点，此 次设计的思想是长链表的值加上短链表的值，最后保存长链表。（1）两正数相加如果两个都是绝对值不超过9999的
12、整数，则将两个数进行相加，即将p的 数据域的值加上q的数据域的值，然后判断相加结果即p结点的数据域的值是否 超过 9999，如果超过 9999，则需要进行进位处理，即申请一个 PNODE 型结点 空间，其数据域用于保存进位值，进位值为1，将该结点插入头结点的后面，头 结点的后继指针保存该结点的地址，该结点的前驱指针保存头结点的地址，后继 指针保存原头结点后继结点的地址。若不产生进位，则用 result_list 保存所得到 的结果链表，result_list为List类型的变量，即它表示双向循环链表。如果两个长整数当中，有超过 9999 的数，即该链表中存在多个结点，则对 其从最后一个结点进行
13、操作，即p结点数据域的值加上q结点数据域的值,p q指 针依次往前访问链表，重复如上的相加操作，直到p或q访问到头结点为止，出 现需要进位的情况时，前驱结点数据域进行加一操作，该结点数据域进行减 10000的操作，若在最高4位结点产生进位，则申请一个PNODE型的结点空间， 其数据域保存进位值，将该结点插入头结点的后继结点，注意保持链表最后一个 结点的后继指针一直保存头结点后继指针的地址，保证该链表一直是双向循环 的，否则在打印链表时会出现指针异常的情况。最后用result_list保存所得到的 结果链表。（2）两负数相加 当两个长整数均为负数时，进行以下操作。如果两数当中存在一个数，其绝 对值小于9999 时，分为两种情况，一种是两个数的绝对值都小于9999，另一种 则是只有一个数的绝对值小于 9999。当两个数的绝对值都小于 9999 时，将两个双向循环链表的尾结点数据域进行 相加，即p结点数据域的值加上q结点数据域的值，若相加结果data进行取反操作，再将其与p-data进行相加，同时从p指向的结点开始进
