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

数据结构课程设计题目：长整数四则运算班级学号学生姓名提交日期成绩计算机与通信工程学院长整数四则运算一需求分析：问题描述：设计一个实现任意长的整数进行加法运算的演示程序。

基本要求：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。

任何整形变量的范围是 -(2^15 - 1) (2^15 - 1)。

输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。

在现实生活中有很多地方，例如航空航海、生物医疗等等方面，都需要很大的数来表示，这些用int甚至长整型long long都是远不够的，所以需要有一种算法来解决这种大数的表示和运算。

该问题只要求了大数的相加运算。

二详细设计：大致思路：【存储】用两个链表，每个节点保存一位数，在链表头保存数的正负，正数保存1，负数保存-1，如果是正数，后面每一位都储存正数，负数每一位都储存负数，数字按照链表头到链表尾从高位到低位的顺序；【相加】从两个链表的尾部开始同步向前相加，加完存到第一个链表，第二个加完的结点销毁，会存在两个链表不一样长的情况，没加的直接连到链表的前面，最高位的符号存到链表的头；【调整】根据表头的符号，调整后面的数字的值，中间会产生进位或者退位的问题，各个节点的符号不一定相同，但对于正负数都可以建立同样的调整模式，将正负到tmp中（1或-1）加或者减(tmp*10)，然后对前一位加或者减tmp*1即可。

第一位保留符号不变，这样不用处理多余的进位，也就不用再产生新的节点，也不用保存符号。

【输出】从前到后遍历已经处理好的表，将每一位进行输出就可以了。

结构体定义struct Node{Node *pre;Node *next;int data;};功能函数void Input(Node *p,Node *t)//处理输入和保存void disply(Node *h,Node *t,int l)//输出void add(Node *h1,Node *t1,Node *h2,Node *t2)//每一位相加int adjust(Node *h,Node *t)//将各个位的正负、大小、进位进行调整源程序：。

沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：长整数的代数计算院（系）：计算机学院专业：计算机科学与技术班级：学号：姓名：指导教师：沈阳航空航天大学课程设计报告目录1 题目介绍和功能要求 (1)1.1题目介绍 (1)1.2功能要求 (1)1.3基本功能 (1)2 系统功能模块结构图 (2)2.1系统功能结构框图 (2)2.2系统主要模块的功能说明 (2)3 使用的数据结构的描述 (4)3.1数据结构设计 (4)3.2数据结构用法说明 (4)4 函数的描述 (5)4.1主要函数设计 (5)4.2主要函数流程图 (6)5程序测试和运行的结果 (11)5.1程序测试 (11)5.2运行结果 (12)6参考文献 (14)附录（关键部分程序清单） (15)沈阳航空航天大学课程设计报告1 题目介绍和功能要求1.1 题目介绍设计数据结构完成长整数的表示和存储，并编写算法来实现两个长整数的加、减、乘、除等基本代数运算。

1.2 功能要求1) 长整数长度在一百位以上。

2）实现两长整数在同余代数下的加、减、乘、除操作。

即实现算法来求解a+b mod n，a-b mod n，a*b mod n，a\b mod n。

3）输入输出均在文件中。

（选作）1.3 基本功能1.jiafa();将一百位以上的长整数进行加法运算，计算出和。

2.jianfa();将一百位以上的长整数进行减法运算，计算出差。

3.chenfa();将一百位以上的长整数进行乘法运算，计算出积。

4.chufa();将一百位以上的长整数进行除法运算，计算出商和余数。

2 系统功能模块结构图2.1 系统功能结构框图图2.1 系统功能结构框图2.2 系统主要模块的功能说明1.主模块kongzhi()；控制输入模块、加法模块、减法模块、乘法模块、除法模块、输出模块的循环使用。

2.输入模块shuru();将输入的两组长整数分别通过转换将其转换成所需要的形式存储到两个链表（opr1、opr2）中保存起来。

数据结构课程设计题目名称：长的整数加法计算机科学与技术学院一、需求分析1.问题描述：设计一个程序实现两个任意长的整数的求和运算。

2.基本要求：利用双向循环链表，设计一个实现任意长的整数进行加法运算的演示程序。

要求输入和输出每四位一组，组间用逗号隔开。

如：1，0000，0000，0000，0000。

3.任务陈述：(a)输入的形式和输入值的范围：本实验中演示中，长整数的每位上的数字必须为数字［0 ——9］之间，长整数的位数要求无限长。

测试的时候输入数据，当输入回车键的时候结束输入，如果输入的字符不符合题目要求，则程序能过滤这些不符合要求的字符。

(b)输出的形式: 整数的范围无限制，可为正数，可为负数。

按照中国对于长整数的表示习惯，每四位是一组，组间用逗号隔开。

(c)程序所能达到的功能: 演示程序以用户和计算机的对话方式执行，即在计算机显示“提示信息”后之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算结果显示在其后，并对错误。

(d)测试数据: ①—⑧为正确输入数据，⑨为错误输入数据( 超出 4 位) ，⑩为错误输入数据( 不足 4 位)。

①两长整数a=b=0请按照如下形式输入第一个长整数，每四位一组: -1234,1234,1234---- 按该模式输入输入长整数 a您的输入结果为:0 ---------------------- 显示a（防止错误输入）请按照如下形式输入第一个长整数，每四位一组: -1234,1234,1234---- 输入长整数 b 您的输入结果为:您的运算结果为:输出②b>a>01,1111,1111,1111您的输入结果为:1,1111,1111,11119,9999,9999,9999您的输入结果为:9,9999,9999,9999您的运算结果为:11,1111,1111,1110③a>b>09999,9999,9999您的输入结果为:9999,9999,9999请按照如下形式输入第二个长整数，每四位一组: -1234,1234,1234请按照如下形式输入第一个长整数，每四位一组: -1234,1234,1234 请按照如下形式输入第二个长整数，每四位一组: -1234,1234,1234 请按照如下形式输入第一个长整数，每四位一组: -1234,1234,1234您的输入结果为:2您的运算结果为:1,0000,0000,0001 ④b<a<0请按照如下形式输入第一个长整数，每四位一组-2345,6789您的输入结果为:-2345,6789请按照如下形式输入第二个长整数，每四位一组-7654,3211您的输入结果为:-7654,3211您的运算结果为:－1,0000,0000⑤a<0,b>0,|a|>|b|请按照如下形式输入第一个长整数，每四位一组-1,0000,00001您的输入结果为:-1,0000,0001请按照如下形式输入第二个长整数，每四位一组2您的输入结果为:: -1234,1234,1234 : -1234,1234,1234 : -1234,1234,1234 : -1234,1234,12342您的运算结果为:-9999,9999⑥a<0,b>0,|a|<|b|请按照如下形式输入第一个长整数，每四位一组-9999您的输入结果为:-9999请按照如下形式输入第二个长整数，每四位一组1,0000您的输入结果为:1,0000您的运算结果为:1⑦a>0,b<0,|a|>|b|请按照如下形式输入第二个长整数，每四位一组1,0000,0000您的输入结果为:1,0000,0000请按照如下形式输入第二个长整数，每四位一组-9999您的输入结果为:-9999您的运算结果为:9999,0001⑧a>0,b<0,|a|<|b| : -1234,1234,1234: -1234,1234,1234: -1234,1234,1234: -1234,1234,1234请按照如下形式输入第一个长整数，每四位一组: -1234,1234,1234您的输入结果为: 1请按照如下形式输入第二个长整数，每四位一组: -1234,1234,1234-1,0000,0000您的输入结果为:-1,0000,0000您的运算结果为:-9999,9999⑨错误输入（例：输入超过四位，则自动取其前四位进行运算）请按照如下形式输入第一个长整数，每四位一组: -1234,1234,12341,00000您的输入结果为:1,0000请按照如下形式输入第二个长整数，每四位一组: -1234,1234,1234-99998,01234您的输入结果为:-9999,1234您的运算结果为:-9998,1234⑩错误输入（例：非第一次输入少于四位，则在输入前加0 补足四位进行运算）请按照如下形式输入第一个长整数，每四位一组: -1234,1234,1234 1,000您的输入结果为:1,0000请按照如下形式输入第二个长整数，每四位一组: -1234,1234,1234-1,11您的输入结果为:-1,0011您的运算结果为:-11二、概要设计1.目标需求与设计思想通过尾插输入长整数，为实现顺序存入，并用头插存储的运算后的长整数，因为运算必定从后向前计算，同样为了实现顺序存入。

课程名称数据结构课程设计题目长整数加减运算一、需求分析设计一个实现任意长的整数间进行四则运算的程序，要求完成长整数的加运算和减运算。

长整数的长度没有限制，可以是任意长。

正确处理好运算之后的进位和借位。

（1）输入：[-]**,****,****;[-]*,****,****,**** //[-]表示“-”可选（2）输出：**,****，****,****是否继续计算(Y/N):（3）功能：能正确进行相关数据的加减运算（4）测试数据：0；0；输出“0”2345,6789；7654,3211；输出“1,0000,0000”1,0000,0000,0000；-9999,9999；输出“9999,0000,0001”1,0001,00001；-1,0001,0000；输出“0”自选数据二、概要设计1、使用双向循环链表实现长整数的运算及存储，构造双向循环链表，创建双向循环链表表示两个整数2、设计两整数相加的函数Add()，addtwo()，其中Add()调用addtwo()函数，addtwo()具体实现两个整数的加减操作，进位及借位问题；设计显示函数Display()及主函数main()三、详细设计1、数据结构设计双向循环链表的构造t ypedef struct LinkNode{int data; //记录每个节点的整数（小于）LinkNode *next, *pre; //记录下一个节点的地址和前一个节点的地址}linklist;2、创建两个长整数的链表伪算法void Creat(char a[]) //引入字符串，创立两个链表，分别表示两个整数{int 记录字符串i；记录加数节点数j；记录被加数节点数s；标记字符串中的‘-’号记录字符串中的字符转化为整数的值k，使每个节点记录位l while(指针所指不是“；”)被加数字符数m自动加1 //m记录字符串中被加数的字符数n=m;while(执政没有指到结尾处) 总字符串n位数自动加1; //n记录字符串的总字符数if被加数不是负数{head0->data=(-1); //记录整数符号w=1;}else {head0->data=1;}for(i=m-1;i>=w;i--){If指针所指为数字，而不是“，” //把字符转化为整数{k+=(a[i]-'0')*sum(l); //sum()计算的乘方l++;}if(a[i]==','||i==w){把整数存到双向循环链表中s++; //节点数加k=0; //重新初始化k和ll=0;}}head0->pre->data*=s; //存储整数符号和节点数}四、调试分析a、调试过程中，连续输入数字运算，速度会明显变慢，发现在初始化链表及运算后没有释放链表，造成系统资源浪费，经改造后自爱后面添加了析构函数b、算法的时空分析创建整数链表有三个循环，次数都为n。

课程设计实验报告：1.4长整数四则运算题目：长整数四则运算一、实验内容【问题描述】设计一个实现任意长的整数进行加法运算的演示程序【基本要求】利用双向循环链表实现长整数的存储，每个结点含一个整形变量。

任何整形变量的范围是-（2八15-1）〜（2八15-1）。

输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。

【实现基本功能】⑴是想长整数的四则运算；（ii）实现长整数的乘方和阶乘运算；（iii）整形量范围是-（2沏-1）~（2八n-1），其中n是由程序读入的参量。

输入数据的分组方法另行规定；【实现加强版本的功能】⑴四则运算在原来版本的基础上支持小数运算，除法还可以通过输入整数后加小数点与相应要求取的精确位数求出精确值，如：求取3666除以7的后三位精确值，可以在输入时将除数输入为3666.000或3666.0000，就能得出相应的精确位数，当然求取后，没有余数的输出；（ii）乘方的功能也进行了强化，支持小数操作；（iii）添加了多个出错处理（即输入重操作）对相应数据输入与输出进行提示；【加强版的实现原理】⑴加减法运算加强：在原来版本的基础上依照基本的加减法操作将数据用小数点进行分隔，记录下连个输入数的小数位长度，并将小数位较短的一个数据后补0直至小数位数相同，然后用函数处理输出的数据；（ii）乘除法、乘方：其处理方法较为简单，主要是记录数据中小数位数的长度，然后通过每种运算方式不同的运算原理截取小数位，再按照输出格式将数据处理进行输出；（iii）根据定义，阶乘保持不变；【特色分析】⑴加强版程序加上了简单的声音提示，无论是输入与输出均会有八个音符的其中之一对输入与输出与否进行提示，同时在输入输出数据出错时，还会用三个音符对重输入进行提示，增强了人性化操作；【测试数据】（1）0；0；应输出“0”。

（2）-2345,6789；-7654,3211；应输出“-1,0000,0000”。

（3）-9999,9999；1,0000,0000,0000；应输出“9999,0000,0001”。

数据结构课程设计报告长整数运算数据结构课程设计报告题目：长整数四则运算一、需求分析1.问题描述：由于工程上有时候需要对很大的数进行计算，可是计算机本身提供的数据类型无法保存几百位甚至几千位的数字，因此需要设计专门的算法对数据进行相应的计算。

此程序的设计任务是：设计一个程序能够实现长整数运算的程序，而且能够对一些错误异常进行辨别调整，计算出正确的结果。

程序输入格式是字符串，保存时需要用双向循环链表将字符串每四位保存在循环链表中的一个节点中，然后再计算后运行出结果。

2.基本功能功能一：建立双向循环链表,计算链表个数，对链表的数据进行修改，能在链表中插入结点。

功能二：将字符串转换成相应的数字存储在双向循环链表中功能三：对存入双向循环链表的长整数进行相加，相减，相除。

3.输入输出程序输入以字符串的形式输入，数据的类型是字符串，包含元素的范围是数字，逗号，负号。

输入时用字符串输入，输出时以一链表结点输出，而且每个结点表示四位。

二、概要设计1.设计思路：由于计算机无法完成位数很大的数字计算，设计思路就是将很长的数据进行分割，一部分一部分的用计算机固有数据类型进行计算。

将各部分的结果整合起来。

由于计算机固有的整数类型存数的对大整数是2＾15-1，因此为了方便，且符合中国人对长整数的表示习惯，建立一个双向循环链表，每个结点存储四位数字，以万为进制。

从最低位开始加法，超过一万向上进位，因此每次加法应该是对应两个结点和进位数相加，进位值初始为0；减法也是一个结点计算一次，每次计算应该是第一个链表对应的结点值减去第二个结点的值和借位值的和，借位值初始值为0；除法的计算能够借助减法，被减数被减数减一次则最终结果加一；直至被减数比减数小。

2.数据结构设计：因为计算的是一个连续的数字，需要桉顺序一次计算，因此采用的数据结构的逻辑结构是线性表。

因为要求每一个结点只存储四位数字，为了将数字连接起来，采用的数据结构的存储结构是链式。

数据结构课程设计－－－长整数运算没有测试，代码仅供参考！！！1：需求分析用户输入2个任意长整数，求它们的加法，减法和乘法，并将结果显示；2：设计思想a：数据结构的选用为了实现任意长整数的加法，减法和乘法，因为这几种运算都存在进位和借位以及位移等操作，因此选择双链表的结构体，它有一个data，left，right；考虑到data表示的数据的范围，使它只接受4个数字的整数，这样一个长整数就分为若干段，每一段为4个数字，便于进位和借位以及位移的操作；b：2个长整数的输入首先输入数的正负号，将它转化为相应的0和1；接着采用头插法的方式，当输入一个4个数字的整数时，就产生一个新的节点，它的值为输入的整数值，建立起它的左右指针，并用头节点指向它；为了判断一个长整数是否输入结束，定义一个结束标志，当输入正数时就继续，当输入负数时，就结束一个长整数的输入；同时用一个函数得到长整数的尾节点和段数，段数在比较2个数的大小有用。

c：2个长整数的加法先定义一个部分加法的函数，就是2个正的长整数的加法的运算；它从2个长整数的尾部开始，同时相加，接着再向左移一段，又同时相加；当2个数据的某一段同时存在时，就相加；当一个数据已经全部被相加后，另外一个数据的剩下的段就要全部复制到和中；在实行加法的时候，设置一个进位标志位，目的是为了使结果正确；当一段的数据相加产生进位时，那么进位标志位为1；下一次一段的数据相加就要加上这个进位标志位；而且如果2个长整数的所有的段的数据都相加完了，还要判断是否产生了进位标志位，如果有的话，就要新建一个节点，它的值就是1；2个正的长整数的求和就完成了。

再定义一个部分减法的函数，就是2个正的长整数的减法的运算；第一个长整数的大小一定大于第二个长整数的大小；它从2个长整数的尾部开始，同时相减，接着再向左移一段，又同时相减；当2个数据的某一段同时存在时，就相加；当第二个长整数已经全部被相减后，第一个数据的剩下的段就要全部复制到结果中；在实行减法的时候，设置一个借位标志位，目的是为了使结果正确；当一段的数据相减产生借位时，那么借位标志位为1；下一次一段的数据相减就要借去这个进位标志位；2个正的长整数的减法就完成了。

数据结构课程设计报告题目：长整数四则运算一、需求分析1. 问题描述：由于工程上有时候需要对很大的数进行计算，但是计算机本身提供的数据类型无法保存几百位甚至几千位的数字，所以需要设计专门的算法对数据进行相应的计算。

此程序的设计任务是：设计一个程序能够实现长整数运算的程序，而且能够对一些错误异常进行辨别调整，计算出正确的结果。

程序输入格式是字符串，保存时需要用双向循环链表将字符串每四位保存在循环链表中的一个节点中，然后再计算后运行出结果。

2. 基本功能功能一：建立双向循环链表，计算链表个数，对链表的数据进行修改，能在链表中插入结点。

功能二：将字符串转换成相应的数字存储在双向循环链表中功能三：对存入双向循环链表的长整数进行相加，相减，相除。

3. 输入输出程序输入以字符串的形式输入，数据的类型是字符串，包含元素的范围是数字，逗号，负号。

输入时用字符串输入，输出时以一链表结点输出，而且每个结点表示四位。

二、概要设计1. 设计思路：由于计算机无法完成位数很大的数字计算，设计思路就是将很长的数据进行分割，一部分一部分的用计算机固有数据类型进行计算。

将各部分的结果整合起来。

由于计算机固有的整数类型存数的对大整数是2人15-1 ,所以为了方便，且符合中国人对长整数的表示习惯，建立一个双向循环链表，每个结点存储四位数字，以万为进制。

从最低位开始加法，超过一万向上进位，所以每次加法应该是对应两个结点和进位数相加，进位值初始为0 ;减法也是一个结点计算一次，每次计算应该是第一个链表对应的结点值减去第二个结点的值和借位值的和，借位值初始值为0 ;除法的计算可以借助减法，被减数被减数减一次则最终结果加一；直至被减数比减数小。

2. 数据结构设计：因为计算的是一个连续的数字，需要桉顺序一次计算，所以采用的数据结构的逻辑结构是线性表。

因为要求每一个结点只存储四位数字，为了将数字连接起来，采用的数据结构的存储结构是链式。

1．双向循环链表的抽象数据类型定义为：ADT Link{数据对象：D={ai | ai € CharSet , i=1 , 2 , .......... , n, n > 0}数据关系；R={<ai-1,ai> | ai-1,ai € D,i=2 , ............ , n}}基本操作：InitLinkList(&L,a) 操作结果：构造一个双向循环链表L ，用a 判断是正数还是负数DestroyList(&L)初始条件：双向循环两已经存在操作结果：销毁有序表LInsert(&L,a) 初始条件：双向循环链表已经存在操作结果：在循环链表的末尾插入一个结点，且此结点的数据值为 a HeadInsert(&L,a)初始条件：双向循环链表已经存在操作结果：在循环链表的头结点后插入一个结点，且此结点的数据值为 a CountNode(&L)初始条件：双向循环链表存在操作结果：计算出链表中结点的个数，并返回个数Compare(&L1, &L2) 初始条件：L1 和L2 存在操作结果：比较两个双向循环链表的大小，用返回值 1 表示L1 大于L2, 返回值-1 标志L1 小于L2, 返回值0 标志L1 和L2 相等ToNum(*s,i,&e)初始条件：s 为字符串中指向某个字符的指针操作结果：将s 的前i 个字符转换为数字，存入 e 中CreatNum(&L,&s)初始条件：s 为某个字符串，双向循环链表L 存在操作结果：将字符串s 转换成数字存入到循环链表L 中Add(L1 ，L2, op)初始条件：双向循环链表L1 和L2 存在，op 为结果的标识符操作结果：两个链表相加，求出结果。

中国石油大学（北京）远程教育学院《数据结构》课程设计报告2019 ～2019 学年第 1 学期课程设计题目第一题任意长的整数加减法运算2019 年8 月任意长的整数加减法运算1需求分析设计算法，实现一个任意长的整数进行加法、减法运算的演示程序。

例如：1234，5123，4512，3451，2345与-1111，1111，1111，1111，1111的加法结果为：0123，4012，3401，2340，1234。

基本要求如下：（1）利用链表实现长整数的存储，每个节点含一个整型变量；（2）整型变量的范围：-（2^15 -1）~（2^15 -1）；（3）输入与输出形式每四位一组，组间用逗号分隔开。

如：1986,8213,1935,2736,3299；（4）界面友好，每步给出适当的操作提示，并且系统具有一定的容错能力。

至少给出下面的测试数据：（1）0；0（2）-2345,6789；-7654,3211（3）-9999,9999；1,0000,0000,0000（4）1,0001,0001；-1,0001,0001（5）1,0001,0001；-1,0001,0000（6）-9999,9999,9999；-9999,9999,9999（7）1,0000,9999,9999； 12概要设计注意这里是整数，浮点数需要额外的操作，实现大整数的加减，三个栈就OK了，两个运算整数栈，一个结果栈，基本的逻辑的就是利用栈的先入后出的特点将高位push到栈底，低位push到栈顶，之后两个栈pop出来之后push到结果栈，结果栈pop出来就是我们想要的结果。

typedef char ElemType;typedef struct{ElemType *base;ElemType *top;int stacksize;}sqStack;void initStack(sqStack *s)void Push(sqStack *s, ElemType e)void Pop(sqStack *s , ElemType *e)int StackLen(sqStack s)void ADD(sqStack *s1,sqStack *s2,sqStack *s3)3详细设计1. 主函数设计int main(){char e;sqStack s1,s2,s3;initStack(&s1); /*初始化堆栈s1，存放加数*/initStack(&s2); /*初始化堆栈s2，存放加数*/initStack(&s3); /*初始化堆栈s3，存放结果*/printf("江紫花090451\n"); /*输入第一个任意长整数，按”#”结尾*/printf("Please input the first integer\n"); /*输入第一个任意长整数，按”#”结尾*/scanf("%c",&e);while(e!='#'){Push(&s1,e); /*将加数（字符串）入栈s1*/scanf("%c",&e);}getchar(); /*接收回车符*/printf("Please input the second integer\n"); /*输入第二个任意长整数，按”#”结尾*/scanf("%c",&e);while(e!='#'){Push(&s2,e); /*将加数（字符串）入栈s2*/scanf("%c",&e);}ADD(&s1,&s2,&s3); /*加法运算，将结果存放在s3中*/printf("The result is\n");while(StackLen(s3)!=0) /*输出结果，打印在屏幕上*/{Pop(&s3,&e);printf("%c",e);}void initStack(sqStack *s){/*内存中开辟一段连续空间作为栈空间，首地址赋值给s->base*/s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));if(!s->base) exit(0); /*分配空间失败*/s->top = s->base; /*最开始，栈顶就是栈底*/s->stacksize = STACK_INIT_SIZE; /*最大容量为STACK_INIT_SIZE */ }/*入栈操作，将e压入栈中*/void Push(sqStack *s, ElemType e){if(s->top - s->base >= s->stacksize){/*栈满，追加空间*/s->base = (ElemType *)realloc(s->base, (s->stacksize +STACKINCREMENT)*sizeof(ElemType));if(!s->base) exit(0); /*存储分配失败*/s->top = s->base + s->stacksize;s->stacksize = s->stacksize + STACKINCREMENT; /*设置栈的最大容量*/}*(s->top) = e; /*放入数据*/s->top++;}/*出栈操作，用e将栈顶元素返回*/void Pop(sqStack *s , ElemType *e){if(s->top == s->base) return;*e = *--(s->top);}/*计算堆栈s当前的长度*/int StackLen(sqStack s){return (s.top - s.base) ;}void ADD(sqStack *s1,sqStack *s2,sqStack *s3){char a1,a2,a3,c=0; /*a1,a2分别存放从堆栈s1,s2中取出的（数据）元素，a3=a1+a2,c中存放进位*/while(StackLen(*s1)!=0 && StackLen(*s2)!=0){Pop(s1,&a1); /*取出s1栈的栈顶元素给a1*/Pop(s2,&a2); /*取出s2栈的栈顶元素给a2*/a3 = (a1-48) + (a2-48) + c + 48; /*相加*/if(a3>'9'){a3 = a3 - '9' + 47; /*产生进位的情况*/c = 1;}elsec = 0; /*不产生进位*/Push(s3,a3); /*将结果入栈s3*/}if(StackLen(*s1)!=0) /*栈s1不为空的情况*/{while(StackLen(*s1)!=0){Pop(s1,&a1); /*取出s1栈的栈顶元素给a1*/a3 = a1 + c ; /*与进位标志c相加*/if(a3>'9'){a3 = a3 - '9' + 47; /*产生进位的情况*/c = 1;}elsec = 0; /*不产生进位*/Push(s3,a3); /*将结果入栈s3*/}}else if(StackLen(*s2)!=0) /*栈s1不为空的情况*/{while(StackLen(*s2)!=0){Pop(s2,&a2); /*取出s1栈的栈顶元素给a1*/a3 = a2 + c; /*与进位标志c相加*/if(a3>'9'){a3 = a3 - '9' + 47; /*产生进位的情况*/c = 1;}elsec = 0; /*不产生进位*/Push(s3,a3); /*栈s1不为空的情况*/}}if(c==1)Push(s3,'1'); /*如果最后有进位，将字符’1’入栈s3*/ }4程序测试（1）0；0（2）-2345,6789；-7654,3211（3）-9999,9999；1,0000,0000,0000（4）1,0001,0001；-1,0001,0001（5）1,0001,0001；-1,0001,0000（6）-9999,9999,9999；-9999,9999,9999（7）1,0000,9999,9999； 15感想与体会这是一门纯属于设计的科目，它需用把理论变为上机调试。

课程名称: 《数据结构》课程设计课程设计题目: 任意长整数加法运算姓名: XXX专业: 计算机科技2班年级: 13级学号: E11314XXX指导老师：XXX2015年9月17目录1.课程设计的目的 (1)2.需求分析 (1)3任意长整数加法的设计 (2)3.1概要设计 (2)3.2详细设计 (3)3.3调试分析 (9)3.4用户手册 (10)3.5测试结果 (10)4总结 (11)5、程序清单:(见附录) (11)7、程序运行结果 (11)附录1 (13)1.课程设计的目的(1) 熟练使用 C 语言编写程序，解决实际问题;(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力;2.需求分析(1)设计一个实现任意长的整数加法运算演示程序。

(2)利用双向链表实现长整数的存储，每个结点含一个整型变量。

(3)输入输出形式按中国对长整数的表示习惯，每四位一组，用逗号隔开。

3任意长整数加法的设计3.1概要设计(1)主界面设计图 1图2主界面，如图1所示，包含四个菜单项，输入数字选择对应菜单，进入子项。

其中选项2包含子菜单，如图2所示。

(2)存储结构本系统用结构体linlist存储数据，该结构体由数据data、下一节点指针next、上一节点指针prior组成。

data是short型变量，存放每个结点的数据。

本系统中data 一般不超过10000。

用结构体linlist构建链表，头结点的data域符号代表长整数的符号，绝对值表示链表结点数目。

(3)系统功能设计本系统主菜单包含四个选项，功能描述如下：菜单1：输入两个任意长的整数。

可按照标准四位一组中间用逗号隔开输入，也可直接输入，输入的数字保存在文件中，结束后自动返回主菜单。

菜单2：实现两个任意长整数的加法。

任意长的整数进行加法课程设计报告1目的：通过课程设计，加深对《数据结构》课程所学知识的理解，熟练掌握和巩固数据结构的基本知识和语法规范。

通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。

包括：数据类型（整形、实型、字符型、指针、数组、结构等）；运算类型（算术运算、逻辑运算、自增自减运算、赋值运算等）；程序结构（顺序结构、判断选择结构、循环结构）；库函数应用等；2 需求分析在加法运算中，C语言所能定义的整形变量是有一定长度限制的。

例如int型变量所能储存值的值域为-32768~32767，最长的整型long int 值域为-2147483648~2157483646.当在需要位数更长的整数加法时计算器设计运用简单的加法运算符难以达到要求，或是在两个较大整数相加的值超过了整型变量所能储存的数值是程序会发生溢出。

需要一种新的加法模式来解决上述问题，来实现任意长的整数进行加法，得到想要的结果。

本程序完成对任意长的整数进行加法运算：1：输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。

如：1，0000，0000，0000，0000。

2：输入值范围为任意长的整数，输入时需输入数字和被允许的字符（‘，’，‘-’）。

3：基本功能包括大整数输入、加法运算、大整数输出。

4：测试数据为：(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，0001；-1，0001，0001；应输出“0”。

(5)1，0001，0001；-1，0001，0000；应输出“1”。

《数据结构》课程设计报告课程设计报告名称长整数的加法运算实验室实验楼502 完成日期 2018年11月30日}(2) 程序结构图(3) 功能模块3. 详细设计：1. 存储结构采用双向链表，使用头结点存放符号，后继节点存放其数字部分长整数的运算计算方式加法减法结果输入符号位数字部分输入两个长整数选择计算方式 加法模块 减法模块3.算法描述1.针对同号加法void Sub(DualList a, DualList b, DualList c)对两个链表的节点进行的最低位进行加法，默认都需要进位，超过10000的情况，会给在操作下一位的时候在加上进位数字1，如果没有发生进位那就加上进位数0void 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;}elsecarry = 0;InsertNodeAtHead(c, tmp);pa = pa->prior;pb = pb->prior;}while(pa != a){// pb = btmp = pa->data + carry;if (tmp >= 1000){carry = 1;tmp -= 10000;}elsecarry = 0;InsertNodeAtHead(c, tmp);pa = pa->prior;}while(pb != b){// pa = atmp = pb->data + carry;if (tmp >= 1000)4. 调试分析：错误分析：.经常出现忘记符号终止符号，或大小写的小问题导致编译无法通过不安全的设计导致计算机崩溃(无图) 最后结果显示错误1.第一数字输入InputData()2.第2数字输入InputData()输入符号InitList()加入数字InsertNodeAtHead( L,data)加法DualList AddList( a, b)加减法选择同号Add()同号Sub()减法DualList SubList( a, b)结果PrintList(DualList L)正确测试结果：三、设计总结通这次实验让我充分认识到了自己所掌握程序设计知识的贫瘠，在长整的数字的运算之中，在一些数字的长度人可以接受的范围内我们通过用笔列算式、大脑的思考对两个较长的整数进行运算如果计算能力可以的话很快就能得出结果，整个运算的过程简单。

一、【实验内容】【问题描述】设计一个实现任意长的整数进行加法运算的演示程序【基本要求】：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。

任何整形变量的范围是 -(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,0001；-1,0001,0001；应输出“0”。

（5）1,0001,0001；-1,0001,0000；应输出“1”。

（6）-9999,9999,9999；-9999,9999,9999；应输出“1,9999,9999,9998”。

（7）1,0000,9999,9999；1；应输出“1,0001,0000,0000”。

二、实验目的１、熟悉掌握双向循环链表的基本操作；２、熟悉任意长字符串的输入，并实现把字符串转化为整数；３、熟悉任意长整数的加法运算；４、更进一步掌握有关类的操作三、实验文档：任意长整数加法运算一、需求分析1、本程序实现计算任意长的整数的加法运算. 以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就计算并显示出这两个数的运算。

2、本演示程序中，集合的元素限定为数字字符[‘0’~’9’]和字符‘，’与‘；’，输入字符可以任意长，输入形式以“回车符”为结束标志，串中字符顺序不限，且允许出现重复字符。

3、利用双向循环链表现实长整数的存储，每个结点含一个整形变量。

输入的形式以回车结束，可以直接输入正数或负数。

按中国对于长整数的表示习惯，每四位一组，除数字和位于首位置的负号外，其它一切字符都将作为分隔符，连续多个分隔符当一个处理。

桂林电子科技大学综合设计说明书用纸《数据结构与算法》课程设计说明书题目：长整数的加减运算学院：计算机科学与工程学院专业：信息安全姓名：xxxxxxxx学号：11003601xx指导教师：张瑞霞老师2013年9 月13 日成绩评定标准及成绩1、能按照格式进行写作，无抄袭现象（10分）2、报告内容行文通畅，有条理性，无错别字，结构严谨。

（10分）3、能够按照数据结构课设的格式要求、排版要求和字数要求等，有需求分析，系统分析，详细设计，关键技术的介绍和参考文献。

（10分）4、在验收过程中，能合理的回答问题（20分）5、软件能正常运行，实现所提出的功能（40分）6、软件代码规范性较好（5分）7、具有自己的创新或特色（5分）总成绩：目录1、前言 (3)2、需求分析 (4)2.1.问题描述： (4)2.2.基本要求： (4)2.3.更高要求： (4)2.4.测试数据： (4)2.5.开发环境 Visual C++6.0(完整绿色版） (5)3、系统概述 (5)3.1.关键技术。

(5)3.2.相关的函数接口 (6)3.3.功能设计 (7)4、系统分析 (7)5、系统的调试与结果 (17)5.1.调试过程出现的问题以及解决方法 (17)5.2.成功的测试数据截图 (17)6、课设小结 (20)7、参考文献： (21)1、前言本系统主要内容是为数据结构长整数加法的实现，所以整个程序是为了实现长整数的加减法运算。

设计一个实现任意长的整数间进行四则运算的程序，要求完成长整数的加运算和减运算。

长整数的长度没有限制，可以是任意长，正确处理好运算之后的进位和借位。

每个结点中可以存放的最大整数为215-1=32767，才能保证两数相加不会溢出。

但若这样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。

故可以在每个结点中仅存十进制数4位，即不超过9999的非负整数，整个链表视为万进制数。

可以利用头结点数据域的符号代表长整数的符号。

*******************实践教学*******************兰州理工大学软件学院2013年春季学期算法与数据结构课程设计题目：长整数的运算专业班级：软件二班姓名：齐祥荣学号：12700244指导教师：王连相成绩：目录摘要 (1)前言 (2)正文 (3)1.采用类C语言定义相关的数据类型 (3)2.各模块的伪码算法 (3)3.函数的调用关系图 (7)4.调试分析 (8)5.测试结果 (8)6.源程序（带注释） (9)总结 (19)参考文献 (20)致谢 (21)附件Ⅰ部分源程序代码 (22)摘要数据结构该设计要求学生设计程序，实现两个任意长的整数求和及差的运算问题。

通过该题目的设计过程，可以加深理解线性表的逻辑结构、存储结构，掌握线性表上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力关键词：双循环链表；插入；删除；长整数加减前言利用双向循环链表来实现对长整数的存储。

每个节点只存储四位十进制数字，即不超过9999的非负整数。

双向链表有头指针，它的data值存储长整数的符号，1为正，-1为负，0代表长整数为0；它的over值存储除头节点外节点的个数。

其他节点的data值存储四位整数，over存储该四位整数溢出0~~9999范围的情况，一般over>0表示四位数超出9999，over<0表示四位数小于0。

选择该数据结构来完成长整数的加减运算是因为要对长整数进行运算，需要对长整数进行存储，所以选择用链表对长整数存储，又由于存储的顺序是从左到右，而运算的顺序则是从右到左，这样位了操作方便选择循环链表，在运算过程中有进位和借位的操作，所以最终选择双向循环链表的数据结构。

正文1.采用类c语言定义相关的数据类型typedef struct DoubleNode //定义链表元素void InitNode(DLNode **head) //初始化链表int InsertNode(DLNode *head,int n,DataType x) //向链表第N个位置插入元素Xint digit(int n) //判断整数N有几位void PrintNode(DLNode *head) //打印链表void DestroyNode(DLNode **head)//销毁链表void add(DLNode *h1,DLNode *h2) //两数相加void jian(DLNode *h1,DLNode *h2) //两数相减int main() //入口函数2.各模块的伪码算法1.宏定义及链表定义：#define N 100typedef int DataType;typedef struct DoubleNode //定义链表元素{ DataType data;struct DoubleNode *prior;struct DoubleNode *next; }DLNode;void InitNode(DLNode **head) //初始化链表{每个节点只存储四位十进制数字，即不超过9999的非负整数。

目录1 绪论 (2)2 需求分析 (3)3 数据结构及详细设计 (4)3.1线性表的数据结构 (4)3.2详细设计 (5)4 程序的调试与结果 (10)5课设小结 (15)6参考文献 (16)1 绪论此次的课程设计内容为数据结构长整数加法的实现，整个程序是为了实现长整数的加法，有5个函数，其中主函数，输入、输出函数已经占了3个，只有执行加法的add函数，和测试用的text函数的算法比较复杂容易出错。

利用本程序可以实现长整数加法的计算。

2 需求分析1.因为要实现任意长的整数进行加法运算，本程序使用C语言的整型变量int存放数据，一个int型的变量值的范围为-32768~32767，显然远远不能满足。

因此利用双向循环链表实现长整数的存储，每个结点存放一个整型变量，且只存10进制数的4位，即不超过9999的非负整数，整个链表表示为万进制数。

表头数据域的符号代替长整数的符号。

相加过程不破坏两个操作数链表。

长整数位数没有上限。

2.演示程序以用户和计算机的对话方式执行，在计算机终端上显示提示信息之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在后。

3.程序执行的命令包括：1）构造链表1存放第一个输入数据2）构造链表2存放第二个输入数据3）求两数之和4）结束4.测试数据⑴0；0；应输出0⑵-2345，6789；-7654，3211；应输出-1，0000，0000⑶-9999，9999；1，0000，0000，0000；应输出9999，0000，0001⑷1，0001，0001；-1，0001，0001；应输出0⑸1，0001，0001；-1，0001，0000；应输出1⑹-9999，9999，9999；-9999，9999，9999；应输出-1，9999，9999，9998⑺1，0000，9999，9999；1；应输出1，0001，0000，00003 数据结构及详细设计3.1 线性表的数据结构ADT Lixt{数据对象：D={ai ∣ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R1={<ai-1,ai>∣ai-1,ai∈D,i=2,…，n}基本操作：InitList(&L)操作结果：构造一个空的线性表DestroyList(&)初始条件：线性表L已存在操作结果：销毁线性表LClearList(L)初始条件：线性表L已存在操作结果：将L重置为空表ListEmpty(L)初始条件：线性表L已存在操作结果：若L为空表，则返回TRUE,否则返回FALSE ListLength(L)初始条件：线性表L已存在操作结果：返回L中数据元素个数GetElem(L,i.&e)初始条件：线性表L已存在，1≤i≤ListLength(L)操作结果：用e返回L中第i个数据元素的值ListInsert(&L,I,e)初始条件：线性表L已存在，1≤i≤ListLength(L)+1操作结果：在L中第i个位置插入新的数据元素e，L的长度加1 ListDelete(&L,I,&e)初始条件：线性表L已存在，且非空，1≤i≤ListLength(L)操作结果：删除L的第i个元素，并且用e返回其值，L的长度减1}ADT List3.2 详细设计1.节点的定义：typedef struct node{int data;struct node *pre;struct node *next;}DataNode;2.对于程序中数据的输入以及对输入数据检测，主要利用for和while循环语句对输入的数据进行检测和判断：DataNode* Input(){char ch[50];DataNode *temp,*node;int count=0,count1=0,i,j,n,sum=0;scanf("%s",ch);while(ch[count++]!='\0');count--;node=(DataNode*)malloc(sizeof(DataNode));temp=node;count1++;if(ch[0]=='-'||ch[0]=='+'){if((count-1)%2)count1+=(count-1)/2+1;elsecount1+=(count-1)/2;}else{if(count%2)count1+=count/2+1;elsecount1+=count/2;}count--;for(i=1;i<count1;i++){temp->pre=(DataNode*)malloc(sizeof(DataNode)); temp->pre->next=temp;temp=temp->pre;temp->data=0;for(j=0;j<2&&ch[count]!='-'&&ch[count]!='+';j++) {if(count<0)break;sum=ch[count--]-'0';for(n=0;n<j;n++)sum*=10;temp->data+=sum;}}temp->pre=node;node->next=temp;if(ch[0]=='-')count1=0-count1;node->data=count1;return node;}3.对于数据的输出同样利用for和while循环，通过对条件的判定进行数据的输出。

实践教学*******************兰州理工大学2013年春季学期数据结构课稈设计目: 长整数的加减运算专业班级：计算机科学与技术一班名: 郭利强学号: 11730108指导教师: 王连相成绩:计算机科学与技术专业数据结构课程设计任务书（11 级）题目：长整数的加减运算 学生姓名：郭利强 班级：11级计算机科学与技术一班题目简介该设计要求学生设计程序，实现两个任意长的整数求和及差的运算问题。

通过该题 目的设计过程，可以加深理解线性表的逻辑结构、存储结构，掌握线性表上基本运算的 实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于 解决实际问题，培养学生的动手能力。

主要任务第一部分：基本算法实现4、 查找基本算法实现（指导老师根据题目指定）5、 排序基本算法实现（指导老师根据题目指定） 第二部分：指定题目的设计与实现1查阅文献资料，一般在3篇以上;2、建立数据的逻辑结构和物理结构；3、完成相应算法的设计;题目类型：软件工程（R ）指导教师： 王连相 学号：117301081线性结构基本算法实现2、 树型结构基本算法实现3、 图型结构基本算法实现（指导老师根据题目指定） （指导老师根据题目指定） （指导老师根据题目指定）4、完成测试工作;5、撰写设计说明书;6、做好答辩工作。

主要内容、功能及技术指标(1) 使用双向循环链表存储长整数，每个结点含一个整型变量，主要功能有：长整数输入(建立双向循环链表)、长整数的加法、长整数的减法及结果的显示输出等;(2) 至少要用10组测试数据，算法对于这些合法的输入数据都能产生满足规格说明要求的结果;(3) 算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；对算法实现过程中的异常情况能给出有效信息;(4)任何整型变量的范围是-(215-1)~ (215-1 )。

输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开，例1，0000, 0000, 0000;而输入为 1，0001, 0001 和-1，0001, 0000 实现加法时，应输出"1";(5)较高要求：使程序在整型量范围是-(2 n-1)~(2 n-1)的计算机上都能有效地运行。