长整数的加法运算-数据结构与算法课程设计.doc

题 目：长整数的加法运算 学 院：计算机科学与工程学院 专 业：信息安全 姓 名：农锦文 学 号：1200360220 指导教师：张瑞霞 2014年10月18日13目 录引言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引言 随着计算机技术的发展，人们利用计算机开发了许许多多方便的，实用的应用软件，在信息化的现代社会里，人们依赖着很多的应用软件，这些软件在推进社会发展的同时，也丰富了人们的生活，然而，在开发过程中，由于计算机系统的局限性，在需要某些功能时，总会遇到困难。例如在开发某些工程项目时，有时需要对很大的数进行计算。但是计算机本身无法计算某些较大的数，所以我们有必要设计专门的算法对一些较大的数进行相应的计算，通过简化运算之后，对其他程序功能的编写能起到良好的促进作用，大大的减轻了程序员的负担。此次设计的程序将用于长整数的加法运算，程序运行时，将提示用户输入两个长整数，然后将两个长整数相加的结果输出。1、 系统概述 在该长整数加法运算系统中，我将定义双向循环链表来表示长整数，按照中国对长整数的表示方法，如199999999表示为1,9999,9999。双向循环链表数据域存储的是长整数的每4位。双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。通过造双向循环链表，可以对长整数进行方便的存储，在对长整数进行数学运算时，也能通过方便的操作链表，从而对长整数进行需要的计算。 在实现该长整数加法运算的系统中，我将会编程实现以下功能。定义一个函数，用于接收长整数的输入，同时将长整数存储到双向循环链表当中，为了检验是否按预期要求进行存储，我还会编写一个函数，将双向循环链表中数据域的值打印出来。定义一个长整数相加的函数，实现两个长整数加法运算的功能，实际上是对双向循环链表进行操作，这里包括结点空间的申请，插入结点，修改指针所保存的值。 当两个长整数完成加法运算后，我会定义一个显示结果的函数，将它们相加的结果打印出来。一些较大的整数，在单纯的用计算机进行相加运算的时候可能会产生溢出现象，但该系统每次只对4位整数进行运算，避免了数据过大在计算时产生的溢出问题。2、 系统分析2.1需求分析 设计一个计算两个长整数加法的程序，要求长整数的位数不能规定上限。根据中国对于长整数的表示习惯，长整数每4位用逗号隔开。故可以利用双向循环链表对长整数进行存储，每个结点可以存储长整数的4位，即每个结点的数据域最大值为9999，头结点的数据域的值的正负号可以表示长整数的正负，其绝对值可以表示结点数目。为了运算与编程的方便，在相加过程中不要破坏两个操作数链表。2.2系统功能 （1）建立双向循环链表，用于保存长整数及长整数的运算。（2）接收长整数的输入，长整数的每4位都保存到链表的结点中。（3) 对存入双向链表的长整数进行加法运算，在进行运算时，能很好的处理进位，借位问题以及对长整数的正负能做出判断，然后进行相应的运算处理，保证运算结果能与预期结果一致。（4）正确的输出运算后的结果，这里的运算结果也是长整数，故对数的存储也是采用双向循环链表，输出结果即是按长整数的显示方式打印出双向循环链表数据域的值。2.3开发环境 所用开发环境为微软公司开发的VC+6.0软件，该软件可将“高级语言”翻译为“机器语言”，该程序开发语言为C语言。3、 详细设计3.1功能结构框图 图3-1系统功能结构框图 这是长整数相加运算的一个设计思路。在该系统中，我会设置几个函数，分别实现不同的功能，如接收数据输入的函数，将两个长整数进行相加的函数，显示出长整数相加结果的函数。重点是在加法运算的函数里，在功能结构框图中只是大致的介绍出设计思路，分3种情况考虑，具体在每种情况里，也分许多细小的情况进行处理。该系统重要的部分是对双向循环链表进行操作。3.2 软件设计 3.2.1 定义链表与接收数据输入 因为该系统的功能是对长整数进行运算，所以对长整数是用双向循环链表进行存储，链表每个结点均存储绝对值不超过9999的整数，在进行运算时，依次对每个结点进行运算，再判断是否需要进位和借位。该系统主要使用的数据结构是双向循环链表，无任何特殊的算法，只有对双向循环链表的一些简单操作，如插入操作，注意前驱指针和后继指针发生变化时的修改即可。（1） 定义双向循环链表的抽象数据类型 图3-2双向循环链表的结点定义 此双向循环链表中，定义了一个头结点来保存长整数的信息，即头结点的正负表示该长整数的正负，头结点数据域的绝对值表示双向循环链表除头结点外的结点个数。为了后面的编程方便，将结点类型重命名为PNODE。头结点数据域的信息对于加法运算起到一定的作用。用双向循环链表来保存长整数，避免了长整数位数达到上限的问题，间接的解决了计算机无法计算某些较大整数的问题。同时，定义了一个双链表类型的结构体，对双向循环链表的头指针和尾指针进行封装，双链表类型的结构体可以准确的表示长整数。同样为了后续的编程方便，将双向循环链表类型的结构体重命名为List。数据类型如下图所示， 图3-2定义List指针表示双向循环链表（2） 接收长整数的输入 定义一个函数，用于接收长整数的输入，将长整数保存到双向循环链表中，长整数的每4位分别保存到链表的结点数据域中。在接收数据输入时，提示用户按XXXX,XXXX,XXXX;的格式输入，该程序定义了一个char ch用于保存“,”和“;”，当用户输入分号时表示结束输入，逗号用于间隔开每个结点。在接收用户的输入时，采用的方法是先让用户输入整型变量，然后再输入字符型变量，即提示用户每输入一个4位整数，就输入逗号或分号，若用户输入分号，则表示用户输入数据完毕，每输入一个4位整数，申请一个PNODE型的结点空间（申请结点空间的时候要注意判断结点空间是否申请成功，若申请结点空间失败，则打印提示信息，然后退出函数的操作），然后将该结点空间插入表示长整数的双向循环链表中，新申请结点的前驱指针保存原链表最后一个结点的地址，后继指针保存最高位结点的地址，这里是通过while循环的方式把双向循环链表建立起来，直到输入ch的值为分号时，结束链表的建立。这时4位整数已经存储到链表的结点数据域中，长整数已经用双向循环链表表示。输入完成后，判断出head-next-data的正负以及统计出除头结点外的其他结点个数，然后将结果保存到头结点的数据域中，用于表示长整数的正负及长整数的位数长度。为了确定长整数已经按预期的形式保存到双向循环链表当中，我设置了一个打印链表的函数，从头结点的后继结点开始对链表进行访问，直到访问到链表最后一个结点为止，将链表中的每个结点数据域打印出来，观察其结果。如果某个结点的数据域的值为0000，打印链表时显示出来的结果是0，这对后面的计算没有影响，类似于这样的问题在计算完长整数后，显示结果时会进行处理，此时仅是确认链表中数据域的信息。长整数接收输入完毕后，已经保存到一个带有头结点的链表当中了，为了后续的计算方便，需要对该双向循环链表设置一个尾指针。定义一个函数，用于设置双向循环链表的尾指针，在该函数中定义一个PNODE类型的变量p，p从链表的头结点的后继结点开始进行访问，当p访问到链表的最后一个结点时，结束循环，将p作为函数的返回值返回，此时p表示的便是该双向循环链表的尾指针。因为在加法的操作中，都是先对双向循环链表的最后一个结点进行操作，所以设置尾指针是很方便的，很有必要的。3.2.2长整数的加法运算长整数是用双向循环链表进行存储的，对长整数进行加法运算，相当于对双向循环链表操作。在此程序当中，进行加法运算时，可分为3种不同的情况，即两正数相加，两负数相加，两符号互异的数进行相加，符号互异的两数在进行运算时，可视为做减法运算。下面进行详细的介绍。链表相加操作时，采用的思路是将长度较短的链表加到长度较长的链表中，所以在相加之前，先计算出两个链表的长度，用长度较长的链表先保存计算结果，最后将结果赋给“结果”链表。为了说明及编程方便，用p指向长链表的尾结点，用q指向短链表的尾结点，此次设计的思想是长链表的值加上短链表的值，最后保存长链表。（1）两正数相加如果两个都是绝对值不超过9999的整数，则将两个数进行相加，即将p的数据域的值加上q的数据域的值，然后判断相加结果即p结点的数据域的值是否超过9999，如果超过9999，则需要进行进位处理，即申请一个PNODE型结点空间，其数据域用于保存进位值，进位值为1，将该结点插入头结点的后面，头结点的后继指针保存该结点的地址，该结点的前驱指针保存头结点的地址，后继指针保存原头结点后继结点的地址。若不产生进位，则用result_list保存所得到的结果链表，result_list为List类型的变量，即它表示双向循环链表。如果两个长整数当中，有超过9999的数，即该链表中存在多个结点，则对其从最后一个结点进行操作，即p结点数据域的值加上q结点数据域的值,p q指针依次往前访问链表，重复如上的相加操作，直到p或q访问到头结点为止，出现需要进位的情况时，前驱结点数据域进行加一操作，该结点数据域进行减10000的操作，若在最高4位结点产生进位，则申请一个PNODE型的结点空间，其数据域保存进位值，将该结点插入头结点的后继结点，注意保持链表最后一个结点的后继指针一直保存头结点后继指针的地址，保证该链表一直是双向循环的，否则在打印链表时会出现指针异常的情况。最后用result_list保存所得到的结果链表。（2）两负数相加 当两个长整数均为负数时，进行以下操作。如果两数当中存在一个数，其绝对值小于9999时，分为两种情况，一种是两个数的绝对值都小于9999，另一种则是只有一个数的绝对值小于9999。 当两个数的绝对值都小于9999时，将两个双向循环链表的尾结点数据域进行相加，即p结点数据域的值加上q结点数据域的值，若相加结果data进行取反操作，再将其与p-data进行相加，同时从p指向的结点开始进行进位判断，直到判断到最高位结点为止，此处的进位处理情况与（1）中的进位处理相同，但在处理最高位时，要注意符号的正负性。若在最高位产生进位，则申请新的PNODE型结点空间，命名为high，high-data的值为-1，此时p指向的是最高位结点，则p的数据域的值先加上10000，然后进行取反操作，这是为了将第2个4位整数的负号去除。 除上述两种情况，其他情况下可对表示长整数的链表，从其尾结点处开始，将q-data加到p-data中，在进行相加的过程中判断是否需要进位，若相加结果绝对值超过9999，则需要进行进位处理（最高位进位做特殊处理），即前驱结点进行+1操作，该结点数据域进行-10000的操作。若操作到最高位的数据域，则申请新的PNODE型结点空间，命名为high，high-data的值为-1，此时p指向的是最高位结点，则p的数据域的值先加上10000，然后进行取反操作，这是为了将负号去除。最后所得的结果用result_list链表进行存储，将该变量作为相加函数的返回值。若两个链表长短不同，q已经访问到最高位结点而p还未访问到最高位结点，则先将q的数据域的值进行取反操作，然后与p数据域的值进行相加，这里判断进位，处理进位的方法与上述情况相同。（3） 两符号互异的长整数相加，做相减运算 当且仅当两个长整数绝对值均不大于9999时，直接将两个链表的尾结点数据域进行相加，即p结点数据域的值加上q结点数据域的值，将所得结果的链表用result_list进行存储。两个绝对值不超过9999的数，且两数的符号互异（即两数为一正一负），它们在做加法运算时，所得的结果长整数的绝对值不会超过9999，故这里不用考虑进位的问题，两数直接相加即可。 两个长整数当中存在一个长整数的绝对值不超过9999时，若q-data为负数，判断p-data与q-data的绝对值大小，若p-data的绝对值小于q-data，则需要进行借位操作，即p的前驱结点数据域进行-1操作，p结点数据域进行+10000操作，如果不需要借位，则p的数据域和q的数据域直接进行相加。最后结果用result_list存储，将result_list返回。如果q-data为正数，判断p结点数据域与q结点数据域的大小，若p-datadata，则需要进行借位操作，然后p结点的数据域减掉q结点数据域的值。若不需要借位操作，则p的数据域直接减去q的数据域的值。 两个长整数的绝对值均大于9999,时，均从链表的尾结点开始进行相减操作，在需要借位时，前驱结点的数据域-1，自身结点的数据域+10000，若q已到达最高位，p还未到达最高位时，判断p的数据域与q的数据域的值，看是否需要进行借位操作，然后p的数据域的值直接加上q的数据域的值。若p和q同时指向最高位的结点，则它们的数据域的值可以直接进行相加操作。最后所得到的的结果链表用result_list进行存储，将result_list返回。3.2.3显示长整数相加结果 由程序可知，两个长整数相加的结果是用List类型的双向循环链表进行存储，可以通过定义一个简单的打印链表数据域的值的函数，将长整数相加的结果打印出来。在打印链表的过程中，可做一些处理，使得显示结果不影响长整数的数值大小。在打印每个结点数据域之前对数据域的值进行判断，若结点数据域的值小于1000，可在显示数据前面“补0”，使得每个结点显示出来的都是“4位整数”。在打印链表时，定义一个PNODE类型的p，用p从最高位结点开始，依次访问链表中的每个结点，直到尾结点，然后将结点的数据域的值“按要求”显示在屏幕上，即打印出来的结点数据域的值用逗号隔开，这就是中国对于长整数的传统表示方法。程序运行结果如下图所示：图3-3程序运行结果4、 所遇到的问题和分析解决 4.1 对双向循环链表进行操作时，总是出现指针异常的情况，如在做插入操作时，需要修改指针的值，无意间使某些指针成为“野指针”。通过分析每个指针变量所存储的信息，便可找出异常指针，然后将其赋为NULL指针或者修改其信息，使该指针成为正确的指针，同时，在定义指针的时候要将指针的值初始化为NULL，这样可以避免指针成为“野指针”。 4.2 在进行相加（相减）操作时，所得到的相加（相减）结果不是预期结果。解决该问题，要通过分析测试数据的性质，观察两个测试长整数满足了什么条件，执行了程序当中的哪条语句，是哪条语句或语句块没有考虑到功能的完善性，再进一步的从数学角度分析数的性质，最后通过修改部分语句，完善其功能。 4.3 在输出长整数相加结果的函数当中，输出的长整数产生“错误”，如1,0001的数输出为1,1。要解决该问题，先分析长整数的性质，通过分析，发现除最高位结点外，其他结点的数据域的值，小于1000的数要在前面补上“0”，使他们以4位整数的形式输出，这样才不会影响整个长整数的大小及表示方法。5、 系统特色及关键技术 该系统的特色在于能计算较大的，位数较长的长整数。无论多长的整数，运用该系统进行计算时，都可以将该整数按每4位的“分割”方法，将4位整数保存到双向循环链表的结点数据域中，然后再进行计算（即对链表进行操作，如修改指针，数据域的值），相当于每次只进行4位数的计算。解决了计算机无法计算一些较大数据的问题。关键技术在于双向循环链表的操作以及在做长整数相加操作时的进位，借位操作。做相加操作之前，先计算出两个链表的长度，将较短的链表“加进”较长的链表中，最后直接用较长的链表表示相加结果，这样就不需要额外建立一个链表来保存两个长整数相加的结果，减少了结点空间的申请。6、 结论在本次的数据结构与算法课程设计中，该系统提供了长整数加法运算的功能，根据课程设计指导书的测试数据进行测试，该系统也成功实现了这些数据的加法运算。与加法算法类似，该系统中也可以增加长整数减法功能，还可以通过查阅更多的相关资料，文献，增加乘法