大整数加减运算器

《大整数加减运算器》由会员分享，可在线阅读，更多相关《大整数加减运算器（22页珍藏版）》请在装配图网上搜索。

1、数据结构课程设计沈航北方科技学院课程设计说明书 课程名称 数据结构课程设计 教 学 部 工学一部 专 业 计算机科学与技术 班 级 学 号 学生姓名 指导教师 刘 峰 19大整数加减运算器目录摘 要11绪论12系统分析12.1 功能需求12.2数据需求12.3 性能需求23总体设计23.1系统设计方案23.2功能模块设计44详细设计44.1 数据结构定义44.2 生成链表函数模块54.3 输出函数模块54.4 转换函数模块64.5 加法函数模块74.6 减法函数模块75调试与测试75.1 调试75.2 测试76结论8结束语9参考文献10附录1用户手册11附录2源程序14摘 要随着科技的进步和人

2、类文明的发展，人们对数据的管理要求也越来越高，运算器的使用越来越普遍，人性化智能化程度逐步提高，不仅提高了工作效率，也节约了人力物力。 大整数加减法运算器运用C语言实现，运用了数据结构链表中的相关知识实现了大整数的加法功能，减法功能。本文从分析课题的题目背景、题目意义、题目要求等出发，分别从需求分析、总体设计、详细设计、测试等各个方面详细介绍了系统的设计与实现过程，最后对系统的完成情况进行了总结。关键词：大整数，双向循环链表，长整数1绪论本次课设的主要目的在于帮助读者熟悉抽象数据类型的表示和实现方法。抽象数据类型需要借助固有的数据类型来表示和实现，即运用高级程序设计语言中已经存在的数据类型来说

3、明新的结构，用已经实现的操作来组合新的操作，具体实现细节以来于所用语言的功能。通过本次实现可以帮助读者复习高级语言的使用方法。2系统分析 2.1 功能需求本程序中采用双向循环链表实现对长整数的存储与运算，每个节点含一个整型变量，每四位一组。程序由用户输入数据，选择加减运算，计算机计算出结果并反馈。程序由多个函数组成，函数见概要设计长整数位数为100，可根据需要扩充。2.2数据需求大整数加减法设计数据主要是通过界面的输入进行操作，具体需求如下：输入数据：任意长整数 输出数据：长整数进行加减法运算后的结果2.3 性能需求3总体设计3.1系统设计方案（1）菜单1.输入长整数a 2.输入长整数b3.a

4、+b4.a-b5.b-a（2）抽象数据类型定义：#define MAXQSIZE 100 /最大队列长度Typedef structQElemType *base;/初始化的动态分配存储空间int front; /头指针，若队列不为空，指向队列头元素int rear; /尾指针，若对列不空，指向队尾元素的下一个位置SqQueue;Status InitQueue(sqQueue &Q)/构造一个空队列QQ.base=(QElemType*)malloc(MAXSIZE *sizeof (QElemType);If (!Q.base) exit (OVERFLOW); /存储分配失败Q.fron

5、t=Q.rear=0;Return OK;int QueueLength(SqQueue)/返回Q的元素个数，即队列的长度Return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;Status EnQueue(SqQueue &Q,QElemType e)/插入元素e为Q的新的队尾元素If(Q.rear + 1)%MAXQSIZE = Q.front)return ERROR;/队列满Q.baseQ.rear = e;Q.rear = (Q.rear + 1) % MAXQSIZE;return OK;Status DeQueue (SqQueue & Q,QElem

6、Type &e)/若队列不为空，则删除Q的对头元素，用e返回其值，并返回OK；/否则返回ERROR；If (Q.front=Q.rear) return ERROR;E=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;（3）存储结构大整数加减法运算器是采用双循环链表存储数据信息，运用了链表方面的相关知识，进行进位退位，实现了大整数加减法的存储。（4）算法设计有while循环和ifelse判断，最后用if循环结束程序。每个节点只存储四位十进制数字，即不超过9999的非负整数。双向链表有头指针，它的data值存储长整数的符号，1为正，-1为

7、负，0代表长整数为0。它的over值存储除头节点节点的个数。其他节点的data值存储四位整数，over存储该四位整数溢出09999范围的情况，一般over0表示四位数超出9999，over0表示四位数超出9999，over0表示四位数小于0。4.2 生成链表函数模块建造一个空的只有头指针的双向循环链表，当头指针为空的时候则输出错误，无法进行运算，返回头指针。如图2所示。图2 生成链表函数流程图4.3 输出函数模块先判断长整数的正负，为负时先输出“”号，然后按节点顺序依次输出，返回到头节点为止，输出前要判断各个节点data值的位数来判断先输出几个0。如图3示。图3 输出函数流程图4.4 转换函数

8、模块将长整数的字符形式转化成数字形式，存放到双向循环链表中，先判断长整数若为负，减去字符串的第一位，将数字部分存到双向循环链表中。如图4示。 图4 转换函数流程图4.5 加法函数模块先将各位做加减，然后根据所得长整数正负和各结点data值进位或退位计算所得长整数的值并输出。如图5示。 图5 加法函数流程图4.6 减法函数模块两个循环链表分别存有两个长整数。用第一个长整数减第二个长整数并输出结果将被减数的符号改变先将各位做减，然后根据所得长整数正负和各结点data值进位或退位计算所得长整数的值并输出。data值存储长整数的符号，1为正，-1为负，0代表长整数为0。它的over值存储除头节点节点的

9、个数。5调试与测试5.1 调试由于本程序输入时对长整数的格式不加限制，且退进位的语句已经写在加法函数里，所以加法函数过于复杂，但减法函数直接调用加法函数即可。整体设计思路明朗，使用者操作简便。调试过程中多次出现进退位的错误，可见条件的限制，语句间的逻辑关系都是本程序设计的关键。设节点数为n，那么加减法的复杂度为O(n)。5.2 测试由于本程序输入时对长整数的格式不加限制，且退进位的语句已经写在加法函数里，所以加法函数过于复杂，但减法函数直接调用加法函数即可。整体设计思路明朗，使用者操作简便。调试过程中多次出现进退位的错误，可见条件的限制，语句间的逻辑关系都是本程序设计的关键。设节点数为n，那么

10、加减法的复杂度为O(n)。算法多处地方可以合并优化，但要注意逻辑关系。本程序的设计强化了编程能力，加深了链表存储结构的理解。软件测试是软件生存期中的一个重要阶段，是软件质量保证的关键步骤从用户的角度来看，普遍希望通过软件测试暴露软件中隐藏的错误和缺陷，所以软件测试应该是“为了发现错误而执行程序的过程”。或者说，软件测试应该根据软件开发各阶段的规格说明和程序的内部结构而精心设计一批测试用例（即输入数据及其预期的输出结果），并利用这些测试用例去运行程序，以发现程序错误或缺陷。过度测试则会浪费许多宝贵的资源。到测试后期，即使找到了错误，然而付出了过高的代价。测试数据过程如下。(1) 输入功能测试输入

11、数据123456789123456789 12345678910111213预期结果135802468033568002运行结果135802468033568002输入数据123456789123456789 12345678910111213预期结果111111110213345576运行结果111111110213345576输入数据123456789123456789 12345678910111213预期结果 -1111111101213345576运行结果 -1111111101213345576 6结论该程序主要通过数据结构双循环链表的相关知识完成的，可以说为期两周的课设基本上完成

12、了任务书的要求。本程序实现了对大整数加减法的运算。这个程序比较简单，在实际生活中比较实用。但是算法多处地方可以合并优化，但要注意逻辑关系，希望在以后的学习中可以改进，本程序的设计强化了编程能力，加深了对链表存储结构的理解。结束语经过两周的课程设计，我体会颇多，感受也很深刻，首先，我在拿到任务书的时候不能够深刻正确理解其内容，导致了我编出的程序缺少一些功能。其次，在程序编出后，我对于程序的调试不是很擅长。当然，这次也有很多收获，关于数据结构双循环链表，各种函数都有更为深刻的理解。参考文献1 谭浩强.C语言程序设计(第三版).清华大学出版社，20072 姜灵芝，余健.C语言课程设计案例精编.清华大

13、学出版社，20083 严蔚敏.数据结构.清华大学出版社，20074 吴伟民，严蔚敏.数据结构. 清华大学出版社，20085 网上资料附录1用户手册点击运行，首先出现的是大整数加减法运算器的界面，在里面输入一个数即可。如图6所示。图6 大整数加减法运算界面输入a后，再继续输入b即可，如图7所示。图7 显示界面点击“回车”即可以进入到系统的总界面，如图8所示。图8 系统总界面在此界面可以进行两个大整数的加减法运算，输入1，即可以进入到加法运算的界面，如图9所示。图9 加法运算界面在此界面输入2时，可以进行a-b的减法运算，如图10所示。图10 减法运算界面在此界面输入3的时候即可进行b-a的运算，

14、如图11所示。图11 减法运算界面在键盘输入任意键，即可退出本系统。附录2源程序#include#include#include#define LEN sizeof(struct long_int)struct long_int/1.每个节点只存储四位十进制数字，即不超过9999的非负整数。/双向链表有头指针，它的data值存储长整数的符号，1为正，-1为负，0代表长整数为0；它的over值存储除头节点节点的个数。/9999范围的情况，一般over0表示四位数超出9999，overdata=0; head-over=0; head-pro=head; head-next=head; retur

15、n(head);void print(struct long_int *head)/输出以head为头结点的长整数/先判断长整数的正负，为负时先输出-号，然后按节点顺序依次输出/返回到头节点为止，输出前要判断各个节点data值的位数来判断先输出几个0 struct long_int *p; p=head; if(head-next=head) printf(longint error!n); else if(head-data=-1) printf(-); /判断长整数是否为正 p=head-next; printf(%d,p-data); p=p-next; while(p!=head)/判

16、断各个节点data值的位数来判断先输出几个0 if(p-data=0&p-datadata); if(p-data=10&p-datadata); if(p-data=100&p-datadata); if(p-data=1000) printf(%d,p-data); p=p-next; printf(n); void insert(struct long_int *head,struct long_int *p)/head存在且p指向一个long_int型节点。/将节点p插到头节点后并返回头指针 p-next=head-next; head-next-pro=p; head-next=p;

17、 p-pro=head; head-over=head-over+1;/head存在且p指向的节点在头节点后/将头节点后的那个节点从链表里删除、释放p的空间并返回头指针void del(struct long_int *head,struct long_int *p) head-next=p-next; p-next-pro=head; free(p); head-over=head-over-1;struct long_int *get(char s)/字符串存有字符格式的长整数。/将以字符串形式存储的长整数转化到双向循环链表中存储并返回头指针。/将长整数的字符形式转化成数字形式，存放到双向

18、循环链表中，先判断长整数若为负，减去/字符串的第一位，将数字部分存到双向循环链表中 struct long_int *head,*q;/将长整数存到双向循环链表 int i,j,l=0; head=creat();/判断长整数的符号，并将信息存到头节点中 if(s00) head-data=1; if(s0=0) head-data=0; if(s0=-) l=1; head-data=-1; j=strlen(s)-1; for(i=l;i=3) q=(struct long_int *)malloc (LEN); q-data=sj+sj-1*10+sj-2*100+sj-3*1000;

19、insert(head,q); j=j-4; if(j=l)/当最后几位数的位数不足四位时 q=(struct long_int *)malloc(LEN); q-data=0; while(ldata=q-data*10+sl; l+; insert(head,q); return(head);void plus(struct long_int *a,struct long_int *b)/两个循环链表分别存有两个长整数/将两个长整数做和并输出结果/先将各位做加减，然后根据所得长整数正负和各结点data值进位或退位计算所得长整数的值并输出。 struct long_int *m,*n,*p,

20、*chead,*q; if(a-over=0|b-over=0) printf(long int error!n); else m=a-pro; n=b-pro; chead=creat(); while(m!=a&n!=b) p=(struct long_int *)malloc(LEN); p-data=a-data*m-data+b-data*n-data; insert(chead,p); m=m-pro; n=n-pro; while(m!=a|n!=b) if(m=a) p=(struct long_int *)malloc(LEN); p-data=b-data*n-data;

21、n=n-pro; insert(chead,p); else if(n=b) p=(struct long_int *)malloc(LEN); p-data=a-data*m-data; m=m-pro; insert(chead,p); p=chead-next; chead-data=0; while(p!=chead) if(p-data0) chead-data=1; break; if(p-datadata=-1; break; p=p-next; p=chead-pro; while(p!=chead) if(p-next!=chead) p-data=p-data*chead-

22、data+p-next-over; if(p-next=chead) p-data=p-data*chead-data; p-over=0; if(p-data=10000) p-over=1; if(p-dataover=-1; p-data=p-data-p-over*10000; p=p-pro; p=chead-next; while(p-data=0&p-over=0&p-next!=chead) q=p; p=p-next; del(chead,q); if(p-over0) q=(struct long_int*)malloc(LEN); q-data=p-over; inser

23、t(chead,q); if(chead-next-data=0) chead-data=0; print(chead);void minus(struct long_int *a,struct long_int *b)/两个循环链表分别存有两个长整数。/用第一个长整数减第二个长整数并输出结果 b-data=(-1)*b-data;/将被减数的符号改变 plus(a,b);void main() struct long_int *a,*b; char s1100,s2100; int n; printf(*n LONG INT CACILATION!n*n); printf(nplease input long int a:n); gets(s1); printf(nplease input long int b:n); gets(s2); a=get(s1); b=get(s2); printf(calulate:n 1.a+bn 2.a-bn 3.b-an); scanf(%d,&n); print(a); print(b); if(n=1) plus(a,b); if(n=2) minus(a,b); if(n=3) minus(b,a);完成日期：