数据结构课程设计报告-长整数运算.doc

数据结构课程设计报告题目：长整数四则运算一、需求分析1.问题描述：由于工程上有时候需要对很大的数进行计算，但是计算机本身提供的数据类型无法保存几百位甚至几千位的数字，所以需要设计专门的算法对数据进行相应的计算。此程序的设计任务是：设计一个程序能够实现长整数运算的程序，而且能够对一些错误异常进行辨别调整，计算出正确的结果。程序输入格式是字符串，保存时需要用双向循环链表将字符串每四位保存在循环链表中的一个节点中，然后再计算后运行出结果。 2.基本功能 功能一：建立双向循环链表,计算链表个数，对链表的数据进行修改，能在链表中插入结点。功能二：将字符串转换成相应的数字存储在双向循环链表中功能三：对存入双向循环链表的长整数进行相加，相减，相除。 3.输入输出程序输入以字符串的形式输入，数据的类型是字符串，包含元素的范围是数字，逗号，负号。输入时用字符串输入，输出时以一链表结点输出，而且每个结点表示四位。二、概要设计1.设计思路：由于计算机无法完成位数很大的数字计算，设计思路就是将很长的数据进行分割，一部分一部分的用计算机固有数据类型进行计算。将各部分的结果整合起来。由于计算机固有的整数类型存数的对大整数是215-1，所以为了方便，且符合中国人对长整数的表示习惯，建立一个双向循环链表，每个结点存储四位数字，以万为进制。从最低位开始加法，超过一万向上进位，所以每次加法应该是对应两个结点和进位数相加，进位值初始为0；减法也是一个结点计算一次，每次计算应该是第一个链表对应的结点值减去第二个结点的值和借位值的和，借位值初始值为0；除法的计算可以借助减法，被减数被减数减一次则最终结果加一；直至被减数比减数小。 2.数据结构设计：因为计算的是一个连续的数字，需要桉顺序一次计算，所以采用的数据结构的逻辑结构是线性表。因为要求每一个结点只存储四位数字，为了将数字连接起来，采用的数据结构的存储结构是链式。1双向循环链表的抽象数据类型定义为：adt link数据对象：d=ai | aicharset，i=1，2，n，n0数据关系; r= | ai-1,aid,i=2，n基本操作：initlinklist(&l,a) 操作结果：构造一个双向循环链表l ，用a判断是正数还是负数 destroylist(&l) 初始条件：双向循环两已经存在操作结果：销毁有序表linsert(&l,a)初始条件：双向循环链表已经存在操作结果：在循环链表的末尾插入一个结点，且此结点的数据值为aheadinsert(&l,a)初始条件：双向循环链表已经存在操作结果：在循环链表的头结点后插入一个结点，且此结点的数据值为acountnode(&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为结果的标识符操作结果：两个链表相加，求出结果。sub(l1,l2, op) 初始条件：双向循环链表l1和l2存在操作结果：l1减去l2,求出结果 ，op为结果的标识符erasezero(link &l)初始条件：双向循环链表l存在操作结果：删去l链表头结点后，第一个数据不为零结点前的所有数据为零的结点。如果结点数据都为零，则保存一个结点。print(l)初始条件：双向循环链表l存在操作结果：从l头结点开始顺此打印每个结点中的数据3.软件结构设计：本程序包含四个模块：1.主程序模块int main()接受命令while(“命令”!=“退出”)输入字符串建立双向循环链表将字符串转换为要求的格式存入链表的每个结点对链表中数据进行即兴操作数理再次接受命令2.双向链表操作模块-实现结点的插入、删除、修改3.字符串转换存储模块-实现将字符串转换为数字按格式存储在链表中4.数据计算模块-对存储在链表中的数据进行计算，得到最终期望的结果各个模块调用的关系如下： 主程序模块数据运算模块双向链表操作模块字符串转换模块主程序模块中的函数原型：void interface()-操作界面函数status creatnum(link &l,char*s)-创建数字链表函数link compute(link &l1,link &l2,char ope)-数据计算函数数据运算模块：link add(link &l1,link &l2,char op) -加法计算link sub(link &l1,link &l2,char op) -减法运算双向链表操作模块void initlinklist(link &l,char a)status destroylist(link &l)status insert(link &l,elemtype a)int countnode(link l)bool compare(link &l1,link &l2)void erasezero(link &l)status headinsert(link &l,elemtype a) 字符串转换模块status creatnum(link &l,char*s)status tonum(char*s,int i,long &e)人机界面：三、 详细设计 1.根据分析和链表操作的特点，采用双向循环链表实现，这里头结点存储数字的符号。typedef long elemtype ;typedef int status;typedef int bool;typedef struct lnodeelemtype data;lnode *next;lnode *prior;node,*link;void initlinklist(link &l,char a)/对一个双向循环链表进行初始化，分配头结点l = (link)malloc(sizeof(node);/动态分配存储空间 if(!l) return false;if(a = -) l-data = -1;/l-data存放符号节点，如果是-则为，否则为0else l-data = 1;l-prior = l;l-next = l;status destroylist(link &l)/销毁链表lif(!l)return error;/链表不存在p = l-prior;/p指向链表头节点的前驱while(p!=l)/删除节点节点pq = p-prior;free(p);/释放节点p的空间p = q;free(l);/释放链表l的存储空间return ok;status insert(link &l,elemtype a)/分配一个结点，并将其数据值存为a,插入到链表的末尾p=(link)malloc(sizeof(lnode);if(!p)exit(overflow);p-next=p-prior=null;p-data=a;link q=l-prior;q-next=p;p-prior=q;p-next=l;l-prior=p;return ok;status headinsert(link &l,elemtype a) /分配一个结点，并将其数据值存为a，按头插入法插入p=(link)malloc(sizeof(lnode);if(!p)exit(overflow);p-data=a; link q=l-next;q-prior=p;p-next=q;l-next=p;p-prior=l;return ok;status tonum(char*s,int i,long &e)/将字符串s的前i位转换为正数，并由e保存sum=0;for(m=1,n=1;mnext;while(p!=l)i+;p=p-next;return i;bool compare(link &l1,link &l2)/比较链表l1和l2的大小，如果l1大于l2,返回1,如果l2大于l1,返回-1,如果相等，返回0if(countnode(l1)countnode(l2) / l1大于l2else if(countnode(l1)next,p2=l2-next;while(p1!=l1&p2!=l2)if(p1-datap2-data) / l1大于l2if(p1-datadata)return -1;p1=p1-next;p2=p2-next;l1和l2相等link add(link &l1,link &l2,char op) 主要函数/将字符串l1和l2的数据相加，得到的结果链表头结点指针返回int c=0,templink p1,p2,p3p1=p1-prior,p2=p2-priorinitlinklist(l3)p1!=l1&p2!=l2temp=p1-data+p2-data+c是否temp=10000是否temp=temp-10000headinsert(l3,temp)c=0headinsert(l3,temp) c=1p1=p1-prior p2=p2-priorp1!=l1temp=p1-data+c c=temp/10000是否temp=10000是否temp=temp-10000headinsert(l3,temp)headinsert(l3,temp)p1=p1-priorp2!=l2temp=p2-data+c c=temp/10000是否temp=10000是否temp=temp-10000headinsert(l3,temp)headinsert(l3,temp)p2=p2-prior是否c=1是否headinsert(l3,c)link sub(link l1,link l2,char op) 主要函数/将字符串l1和l2的数据相减，得到的结果链表的头结点指针返回int c=0,templink p1,p2,p3p1=p1-prior,p2=p2-priorinitlinklist(l3)p1!=l1&p2!=l2temp=p1-data-p2-data-c是否tempprior p2=p2-priorp1!=l1temp=p1-data-c 是否temppriorp2!=l2temp=p2-data-c是否temp=10000是否temp=temp+10000 c=1headinsert(l3,temp)c=0headinsert(l3,temp) p2=p2-prior是 否 c=1是否headinsert(l3,c)void erasezero(link &l)/删除链表l的无效零元素结点 p=l-next,q;while(p-data=0&p-next!=l)q=p;p=p-next;p-prior=q-prior;free(q);l-next=p;link compute(link &l1,link &l2,char ope) /主要函数/对链表l1和链表l2进行计算，即相加，相减等等erasezero(l1) erasezero(l2) p1=l1-prior p2=l2-prior;op=+l1-data=1&l2-data=1 l3=add(l1,l2,+) l1-data=-1&l2-data=1 是否l1和l2相等是 否l3=sub(l1,l2,+)是否l1大于l2是否l3=sub（l1,l2，-）l3=sub(l2,l1,-)l1-data=1&l2-data=-1是否l1和l2相等是否l3=sub(l1,l2,+)是否l1大于l2是否l3=sub(l1,l2,+)l3=sub(l2,l1,-)l1-data=-11&l2-data=-1l3=add(l1，l2,-)op=-l1-data=1&l2-data=1是否l1大于l2是否l3=sub(l1,l2,+)l3=sub(l2,l1,-)l1-data=1&l2-data=-1l3=add(l1,l2,+);l1-data=-1&l2-data=1l3=add(l1,l2,-);l1-data=-1&l2-data=-1是否l1大于l2是否l3=sub(l1,l2,-)l3=sub(l2,l1,+)void interface() /界面函数,显示操作的主界面status print(link l)/顺次打印链表l中的数据erasezero(l);if(*s57) /第一个不是数字也不是-，则出错return error;if(*s=-) k=0;else k=1;i=1;while(*(s+i)!=0)if(*(s+i)!=,&(*(s+i)57|*(s+i)5)return error;if(*(s+i)=0)return ok;k=4;while(*(s+i)!=0)if(*(s+i)=,)if(k!=4)return error;k=-1; /此时逗号字符不能在四个数字的计算之中k+;i+;if(k!=4) /最后一个逗号后必须有四个数return error;return ok;函数调用关系图： maininterfaceinputjudegcreatnumcomputeprintdestroylistinserttonumerasezeroaddcomparesubcountnodeheadinsert四、 调试分析 1.实际完成的功能有：长整数的加法和减法，支持的数据类型是整形，能够对异常输入进行判断，打印和计算的时候能够消除可能出现的前置零。2.程序的主要函数compute时间复杂度为o(n)，其实n为计算的两个链表的结点个数的较大值。物理存储使用的是双向链表，有两个指针域，空间消耗在合理范围之内3.调试中由于是双向链表，在插入时应该注意将prior域进行考虑，刚开始写程序时忘记，导致输出结果错误。清楚前置零的时候开始没有考虑输入数据全是零的时候，结果将全部的数据结点都给删除，最后没有结果输出，调试中发现这个问题，应该将每个链表至少保存一个数据结点。4.由于时间仓促，而且长整数四则运算的乘法一直没有想到好的办法，如果再有几天时间，乘法这个功能完全可以加上。随之就可以完成乘方的计算5.本程序还有很大的扩充地方，应该可以将程序由正数扩充为浮点数，能够运行更复杂的数据，如求阶乘，开方等功能。如果实现了，则这个计算器的功能方面就可以和windows系统自带的计算器媲美了。五、测试结果列出你的测试结果，包括输入和输出。注意测试数据应该完整和严格，至少给出2组测试结果（含合法数据与非法数据）。输入0;0，输出0输入1,0001,0001;-1,0001,0001；输出0输入1,0001,0001；-1,0001,0000；输出1输入-9999,9999；-9999；9999；输出-1,9999,9998非法数据1,000；000,1；输出“输入错误”六、用户手册说明如何使用你编写的程序，详细列出每一步的具体操作步骤。这里可以有适当的运行结果抓图。用户手册与开发过程无关，只与使用有关，必须是step by step的。 所有运行结果截图均要求有实际数据的内容，截图尺寸要求按页宽排版两张大小，且要求有每张图下面有规范的标题说明如何使用你编写的程序，详细列出每一步的操作步骤。1.进入操作主界面2按照命令提示操作选1，进入加法运算输入第一个操作数：并且按照提示格式输入如果输入错误，比如1,000，则程序会提示错误，重新输入如果输入正确，比如输入1,0000，输入下一个数输入正确，如输入9999,9999 则计算出结果输出每个链表中的结点值，便于观察比较输出结果1,0000,9999选2，进入减法运算输入第一个操作数，并按照提示的格式输入如果输入错误，比如，10,000，程序会提示输入错误，重新输入如果输入正确，比如9999,9999，输入下一个数。第二个数也输入正确，比如输入10,0000，输出结果提示是否继续