数据结构：长整数的加减法(任意长度的加减法)(共15页)

1、精选优质文档-倾情为你奉上姓名 学号 班级 计算机1703 年级 大二 指导教师 西安财经学院信息学院 数据结构 课程设计报告课程设计报告名称 长整数的加法运算 实验室 实验楼502 完成日期 2018年11月30日 长整数的加法运算一、 目的与要求1. 掌握线性结构的逻辑特点及存储实现；2. 根据选题，按规范化流程完成课程设计报告：提供需求分析。（15分）列出概要设计。（包括：抽象数据类型的描述；程序结构图或功能模块图）（20分）给出详细设计。（包括：存储结构的描述；算法的详细设计，对复杂算法，最好画出其N-S流程图；函数的调用关系图）（30分）进行调试分析（注：调试时遇到的问题及解决方法，

2、程序的输出结果及对结果的分析）。（15分）. 整理设计总结。（设计心得体会，以及其他总结信息等）（10分）附有程序清单（注：代码可具有适当注释，用来说明程序的功能、结构）。（10分）二、 设计步骤1. 需求分析：实现任意长的整数进行加法、减法运算：利用链表实现长整数的存储，每个结点含一个整型变量。提醒：任何整型变量int的范围是-(215-1)(215-1)。 输入和输出形式按照中国对于长整数的表示习惯，每四位一组,组间用逗号隔开。 如：-2345，6789，3211；2. 概要设计：(1)为了满足任意长的两个整数的存储和对两个整数运算的进位与借位问题，现在采用双向链表这种

3、数据结构，其抽象类型的数据类型如下：ADT DualNode 数据对象：D = ai | aiElemSet, i = 1, 2, , n, n 0 数据关系：R = <ai-1, ai> | ai-1, ai D, i = 1, 2, , n 基本操作： DualList InitList(int sign); 初始条件：获取一个数字表示符号； 操作结果：构造一个空的双向链表； void DelNode(DualList L, DualNode *p) 初始条件：改节点不为； 操作结果：删除节点； void InsertNodeAtTail(DualList L, int dat

4、a) 初始条件：链表L已经存在；操作结果：向后插入一个数据 void InsertNodeAtHead(DualList L, int data) 初始条件：链表L已经存在；操作结果：向前插入一个数据；void PrintList(DualList L)初始条件：链表L已经存在；操作结果：向后遍历打印节点的信息；(2) 程序结构图输入两个长整数选择计算方式减法模块加法模块(3) 功能模块长整数的运算计算方式加法减法结果输入符号位数字部分3. 详细设计：1. 存储结构采用双向链表，使用头结点存放符号，后继节点存放其数字部分3.算法描述1. 针对同号加法void Sub(DualList a, D

5、ualList 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 &

6、gt;= 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 >= 1000) carry = 1; tmp -= 10000; else carry = 0; InsertNodeAtHead(c, tmp); pa = pa->prior; while(pb != b) / pa = a tm

7、p = pb->data + carry; if (tmp >= 1000) carry = 1; tmp -= 10000; else carry = 0; InsertNodeAtHead(c, tmp); pb = pb->prior; if (carry != 0) InsertNodeAtHead(c, 1);2. 减法（异号加法）void Sub(DualList a, DualList b, DualList c)对待异号，从最低位开始相减判断是否需要借位，借位之后会对下一些节位运算的是减1void Sub(DualList a, DualList b, Dua

8、lList c) DualList pa, pb, pc; int borrow = 0,tmp; pa = a->prior; pb = b->prior; while(pa != a) && (pb != b) if (pa->data >= pb->data + borrow) tmp = pa->data - pb->data - borrow; borrow = 0; else tmp = 10000 + pa->data - pb->data - borrow; borrow = 1; InsertNodeAtH

9、ead(c, tmp); pa = pa->prior; pb = pb->prior; if (pa != a | (pa = a && pb = b && borrow = 0) / a >= b c->data = a->data; if (c->data != a->data) / a < b pc = c->prior; while(pc != c) / 结果转换 if (pc = c->prior) pc->data = 10000 - pc->data; else pc->

10、;data = 9999 - pc->data; pc = pc->prior; / 因为符号判断错误，所以borrow要取反 borrow = borrow?0:1; while(pb != 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; else / a>b whi

11、le(pa != 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; pc = c->next; while(pc->next !=c && pc->data = 0) pc = pc->next; DelNode(c, pc->prior); 函数调用Add1.

12、第一数字输入InputData()2.第2数字输入InputData()输入符号InitList()加入数字InsertNodeAtHead( L,data)加法DualList AddList( a, b)加减法选择同号Add()同号Sub()减法DualList SubList( a, b)结果PrintList(DualList L)4. 调试分析：错误分析：.经常出现忘记符号终止符号，或大小写的小问题导致编译无法通过不安全的设计导致计算机崩溃(无图)最后结果显示错误正确测试结果：三、 设计总结通这次实验让我充分认识到了自己所掌握程序设计知识的贫瘠，在长整的数字的运算之中，在一些数字的长

13、度人可以接受的范围内我们通过用笔列算式、大脑的思考对两个较长的整数进行运算如果计算能力可以的话很快就能得出结果，整个运算的过程简单。在计算机实现的过程之中要任意长一个数字存储，就不能采用循序表（例如字符串），因为这样的长度依然是有限制的。采用双向链表的可以解决以上的难题，可以用头节点来保存一个数字的符号，向后插入来保存其它低位，这样限制最终的数字的长度就有计算机硬件水平来决定，几乎实现了任意长度，通过向前遍历可以实现加减法之中的进位和借位问题，让计算更加灵活。在设计一个程序的过程之中安全问题不可以在被忽视，比如我在调试分析之中提到的，因为给链表的想后插入问题没有设置终止条件，导致计算机卡死，电

14、脑只能强制关机。四、代码清单#include "stdio.h"#include "stdlib.h"#include "conio.h"#include "ctype.h"/双向链表的节点 typedef struct DualNode int data; struct DualNode *prior, *next;DualNode, *DualList;DualList InitList(int sign);/创建头结点保存符号位 void InsertNodeAtTail(DualList L, int da

15、ta);/尾插法，方便数据从 void InsertNodeAtHead(DualList L, int data);/头插法，用于存放结果 void PrintList(DualList L);/打印结果DualList InputData();/读入数据 void DelNode(DualList L, DualNode *p);/删除节点 void Add(DualList a, DualList b, DualList c);/计算加法void Sub(DualList a, DualList b, DualList c);/异号DualList SubList(DualList a,

16、 DualList b);DualList AddList(DualList a, DualList b); 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) /尾插，用于存储数据的输入 DualNode *s; s = (DualList)mall

17、oc(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 =

18、L; L->next->prior = s; L->next = s;void PrintList(DualList L) /打印结果 int FirstTime = 1; DualNode *p = L; if (p->data = -1) printf("-"); p = p->next; printf("%d",p->data); p=p->next; while(p != L) if(p->data<10) printf(",000"); else if(p->dat

19、a<100) printf(",00"); else if(p->data<1000) printf(",0"); else printf(","); printf("%d",p->data); p = p->next; printf("n");DualList InputData() int FirstNum = 1, data; char c; DualList L; L = (DualList)malloc(sizeof(DualNode); L->ne

20、xt = L->prior = L; printf("输入数据如: -1234,1234,1234n"); if (c = getchar() = '-') L = InitList(-1); else L = InitList(1); if (isdigit(c) / 退格处理 ungetc(c, stdin); do scanf("%d", &data); InsertNodeAtTail(L, data); while(c = getchar() != 'n'); printf("你输入的数为

21、: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 !

22、= 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 >= 1000) carry = 1; tmp -= 10000; else carry = 0; InsertNodeAtHead

23、(c, tmp); pa = pa->prior; while(pb != b) / pa = a tmp = pb->data + carry; if (tmp >= 1000) carry = 1; tmp -= 10000; else carry = 0; InsertNodeAtHead(c, tmp); pb = pb->prior; if (carry != 0) InsertNodeAtHead(c, 1);void Sub(DualList a, DualList b, DualList c) DualList pa, pb, pc; int borro

24、w = 0,tmp; pa = a->prior; pb = b->prior; while(pa != a) && (pb != b) 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 = pb

25、->prior; if (pa != a | (pa = a && pb = b && borrow = 0) / a >= b c->data = a->data; if (c->data != a->data) / a < b pc = c->prior; while(pc != c) / 结果转换 if (pc = c->prior) pc->data = 10000 - pc->data; else pc->data = 9999 - pc->data; pc = pc->

26、;prior; / 因为符号判断错误，所以borrow要取反 borrow = borrow?0:1; while(pb != 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; else / a>b while(pa != 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; pc = c->next; while(pc->n