数据结构课程设计长的

1、 数据结构课程设计长的整数加 法 数据结构课程设计 题目名称：长的整数加法 计算机科学与技术学院 一、 需求分析 1.问题描述： 设计一个程序实现两个任意长的整数的求和运算。 2.基本要求： 利用双向循环链表，设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000。 3.任务陈述： 输入的形式和输入值的范围：本实验中演示中，长整数的每位上的数(a)之间，长整数的位数要求无限长。测试的时候输入数据，90字必须为数字当输入回车键的时候结束输入，如果输入的字符不符合题目要求，则程序能过 滤这些不符合要求的字符。 整数的

2、范围无限制，可为正数，可为负数。按照中国对:输出的形式(b) 于长整数的表示习惯，每四位是一组，组间用逗号隔开。 演示程序以用户和计算机的对话方式执行，即(c) 程序所能达到的功能:在计算机显示“提示信息”后之后，由用户在键盘上输入演示程序中规定的运 算命令；相应的输入数据和运算结果显示在其后，并对错误。，4位)为正确输入数据，为错误输入数据（d）测试数据:(超出 位)。为错误输入数据(不足4a=b=0 两长整数: -1234,1234,1234 请按照如下形式输入第一个长整数，每四位一组 -按该模式输入a -输入长整数 0 : 您的输入结果为 ) 防止错误输入a(显示- 0 请按照如下形式输

3、入第一个长整数，每四位一组: -1234,1234,1234 -输入长整数b 您的输入结果为: 0 您的运算结果为: 0 -输出 ba0 请按照如下形式输入第一个长整数，每四位一组: -1234,1234,1234 1,1111,1111,1111 您的输入结果为: 1,1111,1111,1111 请按照如下形式输入第二个长整数，每四位一组: -1234,1234,1234 9,9999,9999,9999 您的输入结果为: 9,9999,9999,9999 :您的运算结果为11,1111,1111,1110 ab0 请按照如下形式输入第一个长整数，每四位一组: -1234,1234,123

4、4 9999,9999,9999 您的输入结果为: 9999,9999,9999 请按照如下形式输入第二个长整数，每四位一组: -1234,1234,1234 2 : 您的输入结果为 2 您的运算结果为: 1,0000,0000,0001 ba0 请按照如下形式输入第一个长整数，每四位一组: -1234,1234,1234 -2345,6789 您的输入结果为: -2345,6789 请按照如下形式输入第二个长整数，每四位一组: -1234,1234,1234 -7654,3211 您的输入结果为: -7654,3211 您的运算结果为: 1,0000,0000 a0,|a|b| 请按照如下形

5、式输入第一个长整数，每四位一组: -1234,1234,1234 -1,0000,00001 您的输入结果为: -1,0000,0001 请按照如下形式输入第二个长整数，每四位一组: -1234,1234,1234 2 您的输入结果为: 2 您的运算结果为: -9999,9999 a0,|a|0,b|b| 请按照如下形式输入第二个长整数，每四位一组: -1234,1234,1234 1,0000,0000 您的输入结果为: 1,0000,0000 请按照如下形式输入第二个长整数，每四位一组: -1234,1234,1234 -9999 您的输入结果为: -9999 您的运算结果为: 9999,

6、0001 a0,b0,|a|b| 请按照如下形式输入第一个长整数，每四位一组: -1234,1234,1234 1 您的输入结果为: 1 请按照如下形式输入第二个长整数，每四位一组: -1234,1234,1234 -1,0000,0000 您的输入结果为: -1,0000,0000 您的运算结果为: -9999,9999 错误输入（例：输入超过四位，则自动取其前四位进行运算） 请按照如下形式输入第一个长整数，每四位一组: -1234,1234,1234 1,00000 您的输入结果为: 1,0000 请按照如下形式输入第二个长整数，每四位一组: -1234,1234,1234 -99998,

7、01234 您的输入结果为: -9999,1234 您的运算结果为: -9998,1234 错误输入（例：非第一次输入少于四位，则在输入前加0补足四位进行运算） 请按照如下形式输入第一个长整数，每四位一组: -1234,1234,1234 1,000 您的输入结果为: 1,0000 请按照如下形式输入第二个长整数，每四位一组: -1234,1234,1234 -1,11 您的输入结果为: -1,0011 您的运算结果为: -11 二、概要设计 1.目标需求与设计思想 通过尾插输入长整数，为实现顺序存入，并用头插存储的运算后的长整数，因为运算必定从后向前计算，同样为了实现顺序存入。 因为任意的长

8、整数可能为负数，则第一步需判断其符号。先判断长整数a，b的符号的异同，相同，则将a的符号存入新的双向链表c的符号位；相异， 则将b的符号存入c，之后再处理。 根据c的符号位，使用加法或减法的函数，需要考虑进位借位，从后开始进行运算。通过删除函数，删除因借位而出现的多余的0。 最后打印运算后的c。 2数据结构 此实验采用的数据结构是双向循环链表。这样可以很容易的找到他的前驱以及它的后继，并使用它们存储。这是其结构体声明： typedef struct DualNode int data; struct DualNode *prior, *next; DualNode, *DualList; 2.

9、程序构成 DualList InputData() ）1 操作结果：初始化一双向循环链表，完成输入操作，并将该链表返回。 2）DualList AddList(DualList a, DualList b) 操作结果：判断其符号 DualList InitList(int sign) 3） 操作结果：初始化一双向循环链表，存储符号位，并将该链表返回。 void InsertNodeAtTail(DualList L, int data) 4） 操作结果：尾插，用于存储数据的存入。 ）void InsertNodeAtHead(DualList L, int data) 5 操作结果：插在头结点

10、之后，用于计算结果的存储。void Add(DualList a, DualList b, DualList c) ）6 操作结果：加运算void Sub(DualList a, DualList b, DualList c) ）7 操作结果：减运算void DelNode(DualList L, DualNode *p) 8） 操作结果：删除因借位产生的多余的。0void PrintList(DualList L) ）9 操作结果：打印链表 流程及调用关系3. 主程序 a 输入 调用InputDaPrintLi 输入b 调用PrintLiInputDa 调InitList(AddList()

11、 调调Sub(Add(InsertNodeAtHead 调 用 DelNode() PrintList() 结束 三、详细设计 头文件定义1.#include #include #include 2.数据结构详细设计typedef struct DualNode int data; struct DualNode *prior, *next; DualNode, *DualList; 双向循环链表的节点由三个部分组成，第一是数据部分data存储此节点的数据，第二是此节点的前驱指针部分*prior指向此节点的前驱，第三是此节点的后继指针部分*next指向此节点的后继。数据部分我们约定它为整形变量

12、，前驱后继指针均为结构体DualNode类型。 3.输入函数与初始化函数设计 DualList InputData() int FirstNum = 1, data; char c; DualList L; L = (DualList)malloc(sizeof(DualNode); L-next = L-prior = L; printf(Please Input as Format: -1234,1234,1234n); if (c = getchar() = -) L = InitList(-1); else L = InitList(1); if (isdigit(c) /判断是否为1

13、0进制数 / 退格处理 ungetc(c, stdin); do scanf(%d, &data); while(data9999) data=data/10; InsertNodeAtTail(L, data); while(c = getchar() != n); printf(Your Input is:n); PrintList(L); return L; 该函数在其内创建了一个双向函数链表，通过返回该链表完成初始化，减少函数个数，降低复杂度。L = (DualList)malloc(sizeof(DualNode)为开辟存储空间，L-next = L-prior = L将其前驱、后继

14、都指向L,构成循环。调用的函数InitList()是为了在头结点存放符号。 ungetc()的使用，是因为将本该输入却被取出的数返回到输入流中去，以便正常输入。do-while语句是为了当输入回车时，能够停止。 while(data9999) data=data/10 该句是为了当输入错误，超过4位时，取前四位当做正常输入存储。PrintList(L)打印存储的链表，以便观察输入的长整数是否符合预期，并在该函数中，解决当输入小于4位的错误的情况，在前补0存储。 4.符号位的存放 DualList InitList(int sign) /头结点存放符号位，1为正，-1为负 DualList L;

15、 L = (DualList)malloc(sizeof(DualNode); L-next = L-prior = L; L-data = sign; return L; 建立一个双向循环链表，并将其返回。在头结点存储其符号位，1为正，-1为 负。 5.符号位的初步判断 DualList AddList(DualList a, DualList b) /判断符号 DualList c; if (a-data * b-data 0) c = InitList(a-data); Add(a, b, c); else c=InitList(b-data); Sub(a, b, c); return

16、 c; 当a，b符号相乘大于0时，即相同时，运算后c的符号一定等于a的符号，执行Add()函数。 当a，b符号相乘小于0时，即相异时，运算后c的符号不一定等于b的符号。 因为|a|可能大于|b|，则需在Sub()函数，进一步进行判断。 6.尾插用于输入数据的存储 void InsertNodeAtTail(DualList L, int data) /在链表最后插入 /尾插，用于存储数据的输入 DualNode *s; s = (DualList)malloc(sizeof(DualNode); s-data = data; s-next = L; s-prior = L-prior; L-p

17、rior-next = s; L-prior = s; 例如：输入1,2345 先是1被存入一个新的结点，在插入L的末尾，之后2345再存入结点，插入末尾，如此一来，方便数据的调用。 7.头插用于运算后数据的存储 void InsertNodeAtHead(DualList L, int data) / 即插在头结点之后，用于计算结果的存储 DualNode *s; s = (DualList)malloc(sizeof(DualNode); s-data = data; s-next = L-next; s-prior = L; L-next-prior = s; L-next = s; 例

18、如：a=1234,5678 b=1,0001。 在本程序中，无论加减运算都从最后四位向前运算，则在头结点后存储，即为顺序存储，符合人的思维逻辑。即先在头结点存入5679，再在头结点后存入 ，1235 这样存储着为：1235,5679。 8.打印 void PrintList(DualList L) /打印 int FirstTime = 1; DualNode *p = L; if (p-data = -1&p-next-data!=0) printf(-); p = p-next; while(p != L) if (FirstTime) FirstTime = 0; printf(%d,

19、p-data); else printf(,d, p-data); p = p-next; printf(); if (p-data = -1&p-next-data!=0) printf(-) 首先判断头结点的符号并将其输出。FirstTime的作用是判断是否为前四位，printf(,d, p-data)在本函数中，则需要在前输出逗号。时，FirstTime=0当 解决了当输入小于4位时的输入错误，通过在前补0的方法。 9.加预算 void Add(DualList a, DualList b, DualList c) DualList pa, pb; int carry = 0, tmp;

20、 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 tmp = pa-data + carry; if (tmp = 10000) carry = 1; tmp -= 10000; else car

21、ry = 0; InsertNodeAtHead(c, tmp); pa = pa-prior; while(pb != b) / pa = a tmp = pb-data + carry; if (tmp = 10000) carry = 1; tmp -= 10000; else carry = 0; InsertNodeAtHead(c, tmp); pb = pb-prior; if (carry != 0) InsertNodeAtHead(c, 1); 本函数主要由3个while语句和一个if语句构成。 首先int carry = 0, tmp; carry代表着进位，开始为0。t

22、mp为存储运行中的结果。 pa = a-prior; pb = b-prior; 因为a，b为双向循环链表，pa，pb指向其前驱，则为a，b的末尾。 例如：a=1,1111 b=2,2222 此时pa-data=1111,pb-data=2222,符合运算顺序。 第一个while语句： while(pa != a) & (pb != b) 这是用来将a，b从后开始相同长度的结点数据进行运算。 tmp = pa-data + pb-data + carry; 考虑进位的正常加法 if (tmp = 10000) carry = 1; tmp -= 10000; else carry = 0; 当

23、运算结果大于等于10000时，进位carry=1，因为进位，运算结果减-10000。 否则进位为0。 InsertNodeAtHead(c, tmp); 将运算结果插入到c的头结点后。 pa = pa-prior; pb = pb-prior; 前移 语句：while第二个 while(pa != a) 则说明a的长度大于等于b，这是需将a剩余的结点导入c中，需要考虑进位。 第三个while语句： while(pa != a) 则说明b的长度大于a，这是需将b剩余的结点导入c中，需要考虑进位。 If语句 当a,b中的数据结点都运算后，还存在进位，则需要在c的头结点插入1。 10.减运算 voi

24、d Sub(DualList a, DualList b, DualList c) DualList pa, pb, pc; int borrow = 0,tmp; pa = a-prior; pb = b-prior; while(pa != a) & (pb != b) /判断ab还是adata = pb-data + borrow) borrow = 0; else borrow = 1; pa = pa-prior; pb = pb-prior; if (pa != a | (pa = a & pb = b & borrow = 0) /判断ab还是a= b c-data = a-da

25、ta; pa = a-prior; pb = b-prior; if(c-data!=b-data) /ab情况 borrow=0; while(pa != a) & (pb != b) /将b中与a等大的相减导入c if (pa-data = pb-data + borrow) /不存在借位 tmp = pa-data - pb-data - borrow; borrow = 0; else tmp = 10000 + pa-data - pb-data - borrow; borrow = 1; InsertNodeAtHead(c, tmp); pa = pa-prior; pb = p

26、b-prior; while(pa != a) /把a中剩余导入c if (pa-data = borrow) tmp = pa-data - borrow; borrow = 0; else tmp = 10000 - pa-data - borrow; borrow = 1; InsertNodeAtHead(c, tmp); pa = pa-prior; else /cdata=b-data; borrow=0; while(pa != a) & (pb != b) /将a中与b等大导入c if (pb-data = pa-data + borrow) tmp = pb-data - p

27、a-data - borrow; borrow = 0; else tmp = 10000 + pb-data - pa-data - borrow; borrow = 1; InsertNodeAtHead(c, tmp); pa = pa-prior; pb = pb-prior; while(pb != b) /导入b中剩余 if (pb-data = borrow) tmp = pb-data - borrow; borrow = 0; else tmp = 10000 - pb-data - borrow; borrow = 1; InsertNodeAtHead(c, tmp);

28、pb = pb-prior; pc = c-next; while(pc-next !=c & pc-data = 0) /为了防止头因借位变为0的情况 pc = pc-next; DelNode(c, pc-prior); 本函数主要由1个while与2个if语句构成。 int borrow = 0,tmp; borrow表示借位，tmp同加函数。 第一个while语句： while(pa != a) & (pb != b) /判断ab还是adata = pb-data + borrow) borrow = 0; else borrow = 1; pa = pa-prior; pb = pb

29、-prior; 通过不断地指向前驱，以判断a和b谁先到达头结点，以判断a和b的绝对值谁大，从而判断符号是否正确。 第一个if语句： if (pa != a | (pa = a & pb = b & borrow = 0) / a = b c-data = a-data; 判断ab还是adata!=b-data) /|a|b|情况 borrow=0; /重新置借位为0 while(pa != a) & (pb != b) /不为符号位时进行 if (pa-data = pb-data + borrow) /因为|a|b|,应该用大数减小数 tmp = pa-data - pb-data - bo

30、rrow; /考虑借位的减法 borrow = 0; /借位置0 else tmp = 10000 + pa-data - pb-data - borrow; /需向前一位借1 borrow = 1; InsertNodeAtHead(c, tmp); /在c的头结点后插入 pa = pa-prior; pb = pb-prior; while(pa != a) /把a中剩余导入c，因为|a|b，则只可能a有剩余 if (pa-data = borrow) tmp = pa-data - borrow; borrow = 0; else tmp = 10000 - pa-data - borr

31、ow; borrow = 1; InsertNodeAtHead(c, tmp); pa = pa-prior; Else 语句: 的区别。|a|next; while(pc-next !=c & pc-data = 0) pc = pc-next; DelNode(c, pc-prior); 这是为了防止开头因借位变为0的情况。 例如：a=1,0000 b=-1 运算后为0,9999 ，这时0时多余的，需要删除。 0：11删除多余void DelNode(DualList L, DualNode *p) p-prior-next = p-next; p-next-prior = p-prio

32、r; free(p); 删除结点 12主函数：int main() while(1) 多组输入/ DualList a, b, c; a = InputData(); b = InputData(); c = AddList(a, b); printf(The result is:); PrintList(c); printf(*n); return 0; 为了满足实验要求，采用while(1)实现多组输入。 四、调试分析 1.遇到的问题 在实验中，主要是在减函数中遇到的问题。首先我并没有对a和b的长度进行比较，而是直接开始对其相同长度的部分进行减法运算，对其借位进行的是borrow = bo

33、rrow?0:1;的操作，但在实现的过程中遇到了问题，借位总是会发生错误，导致结果出错。在最后通过先判断其大小，再进行减法这一符合正常算法的方式，解决了这个问题。 在调试时，并没有考虑多组输入问题，一个一个输入输入十分麻烦，采用while(1)的方法。 在输入的时候，经常会多按或稍按几个数，导致其调试十分麻烦，则在程序 中添加算法解决这个麻烦。 2.算法的时空分析 在本次实验，主要是考虑长整数的加减法问题，并没有太大的时间复杂度。 其主要来源于输入，输入的输出，加减法运算，和输出。 由于这并不是一个很大的时间复杂度，改进的方式只能从链表的存储下手，减 少存入和调出的次数已减少时间复杂度。 3.

34、经验体会 本次实验是求两个无限长整数加减运算。由于没有限制长度和必须使用链表来表示两个长整数，这样来求它们的加减运算。在开始的时候，不知道怎么去做。最后，明白应该用模块化，将程序分成一个个小部分，在将他们串联起来，才能完成。虽然中间遇到了许多困难，但同样复习了数据结构的知识和复习链表。 五、用户使用说明 用户在使用该程序时，只需按照程序提示进行即可实现长整数的加减运算，具体使用步骤如下： 1） 按照输入格式输入 此时会输出你刚才的数值） 2按照输入格式输入第二个长整数 3） 此时会输出你刚才的数值 4） 此时会输出运算结果 5） 可重复上述操作，多次输入 6）六、测试结果与情况 两长整数a=b

35、=0 ba0 a=1,1111,1111,1111 b=9,9999,9999,9999 ab0 a=9999,9999,9999 b=2 ba0 a=-2345,6789 b=-7654,3211 a0,|a|b| a=-1,0000,00001 b=2 a0,|a|0,b|b| a=1 b=-1,0000,0000 a0,b0,|a|b| 错误输入（例：输入超过四位，则自动取其前四位进行运算）a=1,00000 b=-99998,01234 补足四位进0错误输入（例：非第一次输入少于四位，则在输入前加 行运算）b=-1,11 a=1,000 ): 附录(源代码#include #inclu

36、de #include typedef struct DualNode int data; struct DualNode *prior, *next; DualNode, *DualList; DualList InitList(int sign) /头结点存放符号位，1为正，-1为负 DualList L; L = (DualList)malloc(sizeof(DualNode); L-next = L-prior = L; L-data = sign; return L; void InsertNodeAtTail(DualList L, int data) / 在链表最后插入 尾插，

37、用于存储数据的输入 / DualNode *s; s = (DualList)malloc(sizeof(DualNode); s-data = data; s-next = L; s-prior = L-prior; L-prior-next = s; L-prior = s; void InsertNodeAtHead(DualList L, int data) / 即插在头结点之后，用于计算结果的存储 DualNode *s; s = (DualList)malloc(sizeof(DualNode); s-data = data; s-next = L-next; s-prior =

38、L; L-next-prior = s; L-next = s; void PrintList(DualList L) /打印结果 int FirstTime = 1; DualNode *p = L; if (p-data = -1&p-next-data!=0) printf(-); p = p-next; while(p != L) if (FirstTime) FirstTime = 0; printf(%d, p-data); else printf(,d, p-data); p = p-next; printf(); DualList InputData() int count=0; int FirstNum = 1, data; char c; DualList L; L = (DualList)malloc(sizeof(DualNode); L-next = L-prior = L; if (c = getchar() = -) L = InitList(-1); else L = InitList(1); if (isdigit(c) /判