数据结构课程设计长的整数加法

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

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

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

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

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

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

7、四位进行运算）请按照如下形式输入第一个长整数，每四位一组: -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,

8、0011您的运算结果为:-11二、概要设计1.目标需求与设计思想通过尾插输入长整数，为实现顺序存入，并用头插存储的运算后的长整数，因为运算必定从后向前计算，同样为了实现顺序存入。因为任意的长整数可能为负数，则第一步需判断其符号。先判断长整数a，b的符号的异同，相同，则将a的符号存入新的双向链表c的符号位；相异，则将b的符号存入c，之后再处理。根据c的符号位，使用加法或减法的函数，需要考虑进位借位，从后开始进行运算。通过删除函数，删除因借位而出现的多余的0。最后打印运算后的c。2数据结构此实验采用的数据结构是双向循环链表。这样可以很容易的找到他的前驱以及它的后继，并使用它们存储。这是其结构体声明

9、：typedef struct DualNode int data; struct DualNode *prior, *next;DualNode, *DualList;2.程序构成1）DualList InputData() 操作结果：初始化一双向循环链表，完成输入操作，并将该链表返回。2）DualList AddList(DualList a, DualList b) 操作结果：判断其符号3）DualList InitList(int sign) 操作结果：初始化一双向循环链表，存储符号位，并将该链表返回。4）void InsertNodeAtTail(DualList L, int da

10、ta) 操作结果：尾插，用于存储数据的存入。5）void InsertNodeAtHead(DualList L, int data) 操作结果：插在头结点之后，用于计算结果的存储。6）void Add(DualList a, DualList b, DualList c)操作结果：加运算7）void Sub(DualList a, DualList b, DualList c)操作结果：减运算8）void DelNode(DualList L, DualNode *p)操作结果：删除因借位产生的多余的0。9）void PrintList(DualList L)操作结果：打印链表3.流程及调用

11、关系主程序模块 输入aPrintList()InputData()调用 输入bPrintList()InputData()调用InitList()AddList()调用Sub()InsertNodeAtHead()Add()调用调用 调用DelNode()PrintList()结束三、详细设计1.头文件定义#include <stdio.h>#include <stdlib.h>#include <ctype.h>2.数据结构详细设计typedef struct DualNode int data; struct DualNode *prior, *next

12、;DualNode, *DualList;双向循环链表的节点由三个部分组成，第一是数据部分data存储此节点的数据，第二是此节点的前驱指针部分*prior指向此节点的前驱，第三是此节点的后继指针部分*next指向此节点的后继。数据部分我们约定它为整形变量，前驱后继指针均为结构体DualNode类型。3.输入函数与初始化函数设计DualList InputData() int FirstNum = 1, data; char c; DualList L; L = (DualList)malloc(sizeof(DualNode); L->next = L->prior = L; pr

13、intf("Please Input as Format: -1234,1234,1234n"); if (c = getchar() = '-') L = InitList(-1); else L = InitList(1); if (isdigit(c) /判断是否为10进制数 / 退格处理 ungetc(c, stdin); do scanf("%d", &data); while(data>9999) data=data/10; InsertNodeAtTail(L, data); while(c = getchar

14、() != 'n'); printf("Your Input is:n"); PrintList(L); return L; 该函数在其内创建了一个双向函数链表，通过返回该链表完成初始化，减少函数个数，降低复杂度。L = (DualList)malloc(sizeof(DualNode)为开辟存储空间，L->next = L->prior = L将其前驱、后继都指向L,构成循环。调用的函数InitList()是为了在头结点存放符号。ungetc()的使用，是因为将本该输入却被取出的数返回到输入流中去，以便正常输入。do-while语句是为了当输入

15、回车时，能够停止。while(data>9999) data=data/10该句是为了当输入错误，超过4位时，取前四位当做正常输入存储。PrintList(L)打印存储的链表，以便观察输入的长整数是否符合预期，并在该函数中，解决当输入小于4位的错误的情况，在前补0存储。4.符号位的存放DualList InitList(int sign) /头结点存放符号位，1为正，-1为负 DualList L; L = (DualList)malloc(sizeof(DualNode); L->next = L->prior = L; L->data = sign; return

16、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 c;当a，b符号相乘大于0时，即相同时，运算后c的符号一定等于a的符号，执行Add()函数。当a，b符号相乘小于0时，即相异时，运

17、算后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->prior->next = s; L->prior = s;例如：输入1,2345先是1被存

18、入一个新的结点，在插入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;例如：a=1234,5678 b=1,00

19、01。在本程序中，无论加减运算都从最后四位向前运算，则在头结点后存储，即为顺序存储，符合人的思维逻辑。即先在头结点存入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;

20、 printf("%d", p->data); else printf(",%04d", p->data); p = p->next; printf("n");if (p->data = -1&&p->next->data!=0) printf("-")首先判断头结点的符号并将其输出。FirstTime的作用是判断是否为前四位，当FirstTime=0时，则需要在前输出逗号。在本函数中，printf(",%04d", p->data)解决

21、了当输入小于4位时的输入错误，通过在前补0的方法。9.加预算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; InsertNodeAtH

22、ead(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 carry = 0; InsertNodeAtHead(c, tmp); pa = pa->prior; while(pb != b) / pa = a tmp = pb->data + carry; if (tmp >= 10000) carry = 1; tmp -= 1

23、0000; else carry = 0; InsertNodeAtHead(c, tmp); pb = pb->prior; if (carry != 0) InsertNodeAtHead(c, 1);本函数主要由3个while语句和一个if语句构成。首先int carry = 0, tmp; carry代表着进位，开始为0。tmp为存储运行中的结果。pa = a->prior; pb = b->prior; 因为a，b为双向循环链表，pa，pb指向其前驱，则为a，b的末尾。例如：a=1,1111 b=2,2222 此时pa->data=1111,pb->da

24、ta=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;当运算结果大于等于10000时，进位carry=1，因为进位，运算结果减-10000。否则进位为0。InsertNodeAtHead(c, tmp); 将运算结果插入到c的头结点后。pa = pa->

25、;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.减运算void Sub(DualList a, DualList b, DualList c) DualList pa, pb, pc; int borrow = 0,tmp; pa = a->prior; pb

26、= b->prior; while(pa != a) && (pb != b) /判断a>b还是a<b if (pa->data >= pb->data + borrow) borrow = 0; else borrow = 1; pa = pa->prior; pb = pb->prior; if (pa != a | (pa = a && pb = b && borrow = 0) /判断a>b还是a<b / a >= b c->data = a->data; pa

27、 = a->prior; pb = b->prior; if(c->data!=b->data) /a>b情况 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 =

28、 1; InsertNodeAtHead(c, tmp); pa = pa->prior; pb = pb->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 /c<b c->data=b->data; bor

29、row=0; while(pa != a) && (pb != b) /将a中与b等大导入c if (pb->data >= pa->data + borrow) tmp = pb->data - pa->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) /

30、导入b中剩余 if (pb->data >= borrow) tmp = pb->data - borrow; borrow = 0; else tmp = 10000 - pb->data - borrow; borrow = 1; InsertNodeAtHead(c, tmp); pb = pb->prior; pc = c->next; while(pc->next !=c && pc->data = 0) /为了防止头因借位变为0的情况 pc = pc->next; DelNode(c, pc->prior)

31、; 本函数主要由1个while与2个if语句构成。int borrow = 0,tmp; borrow表示借位，tmp同加函数。第一个while语句：while(pa != a) && (pb != b) /判断a>b还是a<b if (pa->data >= pb->data + borrow) borrow = 0; else borrow = 1; pa = pa->prior; pb = pb->prior; 通过不断地指向前驱，以判断a和b谁先到达头结点，以判断a和b的绝对值谁大，从而判断符号是否正确。第一个if语句：if (

32、pa != a | (pa = a && pb = b && borrow = 0) / a >= b c->data = a->data; 判断a>b还是a<b，因为在AddList函数中，将b的符号赋予给c，但如果a的绝对值大于b的绝对值，则将a的符号赋予给c，已完成符号位的正确判断。第二个if语句：if(c->data!=b->data) /|a|>|b|情况 borrow=0; /重新置借位为0 while(pa != a) && (pb != b) /不为符号位时进行 if (pa->

33、;data >= pb->data + borrow) /因为|a|>|b|,应该用大数减小数 tmp = pa->data - pb->data - borrow; /考虑借位的减法 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中剩余导入

34、c，因为|a|>|b，则只可能a有剩余 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 语句:大体内容同上，只是|a|<|b|的区别。DelNode()函数的调用： pc = c->next; while(pc->next !=c && pc->data

35、= 0) pc = pc->next; DelNode(c, pc->prior); 这是为了防止开头因借位变为0的情况。例如：a=1,0000 b=-1 运算后为0,9999 ，这时0时多余的，需要删除。11删除多余0：void DelNode(DualList L, DualNode *p) p->prior->next = p->next; p->next->prior = p->prior; free(p);删除结点12主函数：int main() while(1) /多组输入 DualList a, b, c; a = InputDat

36、a(); b = InputData(); c = AddList(a, b); printf("The result is:"); PrintList(c); printf("*n"); return 0;为了满足实验要求，采用while(1)实现多组输入。四、调试分析1.遇到的问题 在实验中，主要是在减函数中遇到的问题。首先我并没有对a和b的长度进行比较，而是直接开始对其相同长度的部分进行减法运算，对其借位进行的是borrow = borrow?0:1;的操作，但在实现的过程中遇到了问题，借位总是会发生错误，导致结果出错。在最后通过先判断其大小，再进

37、行减法这一符合正常算法的方式，解决了这个问题。 在调试时，并没有考虑多组输入问题，一个一个输入输入十分麻烦，采用while(1)的方法。 在输入的时候，经常会多按或稍按几个数，导致其调试十分麻烦，则在程序中添加算法解决这个麻烦。2.算法的时空分析在本次实验，主要是考虑长整数的加减法问题，并没有太大的时间复杂度。其主要来源于输入，输入的输出，加减法运算，和输出。由于这并不是一个很大的时间复杂度，改进的方式只能从链表的存储下手，减少存入和调出的次数已减少时间复杂度。3.经验体会本次实验是求两个无限长整数加减运算。由于没有限制长度和必须使用链表来表示两个长整数，这样来求它们的加减运算。在开始的时候，

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

39、9,9999 b=2 b<a<0 a=-2345,6789 b=-7654,3211a<0,b>0,|a|>|b| a=-1,0000,00001 b=2a<0,b>0,|a|<|b| a=-9999 b=1,0000a>0,b<0,|a|>|b| a=1,0000,0000 b=-9999 a>0,b<0,|a|<|b| a=1 b=-1,0000,0000错误输入（例：输入超过四位，则自动取其前四位进行运算） a=1,00000 b=-99998,01234 错误输入（例：非第一次输入少于四位，则在输入前加

40、0补足四位进行运算）a=1,000 b=-1,11附录(源代码):#include <stdio.h>#include <stdlib.h>#include <ctype.h>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 =

41、 L->prior = L; L->data = sign; return L;void InsertNodeAtTail(DualList L, int data) /在链表最后插入 /尾插，用于存储数据的输入 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

42、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;void PrintList(DualList L) /打印结果 int FirstTime = 1; DualNode *p = L; if (p->data = -1&&p->next->

43、;data!=0) printf("-"); p = p->next; while(p != L) if (FirstTime) FirstTime = 0; printf("%d", p->data); else printf(",%04d", p->data); p = p->next; printf("n");DualList InputData() int count=0; int FirstNum = 1, data; char c; DualList L; L = (DualLi

44、st)malloc(sizeof(DualNode); L->next = L->prior = L; if (c = getchar() = '-') L = InitList(-1); else L = InitList(1); if (isdigit(c) /判断是否为10进制数 / 退格处理 ungetc(c, stdin); do scanf("%d", &data); while(data>9999) data=data/10; InsertNodeAtTail(L, data); while(c = getchar()

45、 != 'n'); printf("您的输入结果为:n"); PrintList(L); return L;void DelNode(DualList L, DualNode *p) p->prior->next = p->next; p->next->prior = p->prior; free(p);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-&g