《大整数地运算大数据结构课程设计.doc》由会员分享，可在线阅读，更多相关《大整数地运算大数据结构课程设计.doc（21页珍藏版）》请在三一办公上搜索。
1、目 录 一、题目概述内容与要求3二、功能分析4三、设计5四、运行与测试6五、总结22六、参考文献23一、 题目概述内容与要求内容： 请设计一个有效的算法，可以进展两个n位大整数的四如此运算。长整数长度在二十位以上。实现两长整数的加、减、乘、除操作。要求： 1.设计数据结构，存储结构； 2.在c兼容环境完成上述题目的代码编写与调试； 3.程序运行界面交互性好； 4.软件运行，给出测试数据。二、功能分析1. 设计一个实现长整数进展四如此运算的程序，长整数长度在二十位以上，有正负数的区别。2. 输入每四位一组，组间用逗号隔开，长整数位数没有上限，以分号完毕长整型数据的输入。用lnode结点数据结构存
2、储数据。每一个数据有一个头结点，它的data域用来放数据的正负数。其余结点的数都为正整数。3. 程序包含数据的输入，判断，运算,输出和主函数。4. 具体程序执行的命令包括:a) 输入函数：inputa();inputb();/的输入并建立双向循环链表b) 判断函数：pare();/比拟数据的大小c) 运算函数：unsigndeadd();/无符号的加法a) unsigndesub();/无符号的减法b) add();sub();mul();div();/加减乘除四如此运算d) 输出函数：divput();/除法结果的输出函数a) putoutc();/其余结果的输出函数e) 主函数：main(
3、)；5. 系统功能结构框图系统功能结构框图三、设计首先要考虑的是如何表示长整型数。可以4位数形成1组，而一个长整型数可能会有很多组这种4位数，而每节之间是有先后顺序的，因此我们可以考虑用数组和链表来存储数据。(1)再考虑到每个长整型数的长度在输入之间是无法预知的，因此使用链表在存储空间的分配上更方便一些。(2)在输入数据时总是从高位到低位地存储，而计算时总是从低位向高位运算，因此采用双向链表更方便，而为了从头结点方便地转到尾结点可以采用循环链表。综上考虑，应以双向循环链表表示长整数，每个结点含一个整型变量，且仅绝对值不超过9999的整数，整个链表用十进制数表示。(3)对于每一个长整型数可以设置
4、一个头结点，其中的数据域用来表示该长整型数的正负号与组数，该值的符号如此表示该长整型数的符号，该数的绝对值表示该长整型数包含的4位数的组数。第一个存储4位数据组的结点称为首结点，而最后一个4位数据组结点称为尾结点。为此需要结构数据类型：双向循环链表：typedef struct lnode/结点结构体int data;struct lnode *next;struct lnode *prior;lnode,*lnodelist主要的模块可分为： 输入函数：inputa();inputb();/的输入并建立双向循环链表 判断函数：pare();/比拟两个数据的大小，进展相应的的计算。 运算函数：
5、add();sub();mul();div();/运算 输出函数：divput();putoutc();/除法的输出与其他运算的输出。 主函数：main()；四、运行与测试图长整数加法运行结果图实现以上加法操作的程序如下：int add(lnodelist &ahead,lnodelist &bhead)int e,acount=0,bcount=0,q;e=ahead-data*bhead-data;cout输出运算结果为:data=-1)coutdata=-1)coutdata=1)coutdata*bhead-data;cout输出运算结果为:data=-1)coutdata=-1)co
6、utdata=1)coutdata*bhead-data;cout输出运算结果为:endl;if(e=-1)coutnext;pb=bhead-next;p=chead=new lnode;/头结点p-data=0;p-next=p;p-prior=p;pc=ow=chead;while(pb!=bhead)carry=0;while(pa!=ahead)multi=pa-data*pb-data+carry;carry = multi/10000;if(pc-prior=chead)p=new lnode; p-data=multi%10000; p-next=chead-next; che
7、ad-next-prior=p; chead-next=p; p-prior=chead;elsemulti=pc-prior-data+multi%10000;pc-prior-data=multi%10000;carry=carry+multi/10000;pc=pc-prior; pa=pa-next;if(carry!=0)p=new lnode; p-data=carry; p-next=chead-next; chead-next-prior=p; chead-next=p; p-prior=chead;ow=ow-prior;pc=ow;pa=ahead-next;pb=pb-n
8、ext;putoutc(chead);return OK;图长整数除法运行结果图实现以上除法操作的程序如下：int divput(lnode *chead)lnode *s,*pr;pr=chead-prior; if(pr!=chead) coutdata;pr=pr-prior;while(pr!=chead)if(pr-data=0)coutdata0&pr-data10)coutdata=10&pr-data100)coutdata=100&pr-data1000)cout0;coutdata;s=pr;pr=pr-prior;delete s;coutendl;return 0;in
9、t div(lnodelist &ahead,lnodelist &bhead)cout输出运算结果为:data*bhead-data;cout输出运算结果为:endl; cout商为;if(e=-1)cout-;while(borrow=0)pare(ahead,bhead,q);if(q=0)borrow=1;cout+count，余数为0endl;else if(q=-1)borrow=1;coutcountnext;pb=bhead-next;while(pa!=ahead&pb!=bhead)diffe=pa-data-borrow-pb-data;if(diffedata=diff
10、e;pa = pa-next;pb = pb-next;if(pa!=ahead)while(pa!=ahead)diffe=pa-data-borrow;if (diffedata=diffe;pa=pa-next;p=pa-prior;while(p-data=0&p-prior!=ahead)s=p;p=p-prior;ahead-prior=p;p-next=ahead;delete s;return 0;附录其它代码实现：第一局部：#includeusing namespace std;#define OK 1;#define FALSE 0;typedef struct lnode
11、 /结点结构体int data;struct lnode *next;struct lnode *prior;lnode,*lnodelist;int pare(lnodelist &ahead,lnodelist &bhead,int &q)/比拟a和b的大小lnode *pa,*pb;int bcount=0,acount=0;pa=ahead-next;pb=bhead-next;while(pa!=ahead)acount+;pa=pa-next;while(pb!=bhead)bcount+;pb=pb-next;if(acountbcount)q=1;else if(acountp
12、rior;pb=bhead-prior;while(pa-data=pb-data)&(pa-prior!=ahead)pa=pa-prior; pb=pb-prior;if(pa-datapb-data)q=1;else if(pa-datadata)q=-1;else q=0;return 0;int inputa(lnodelist &ahead)/输入长整数alnode *p;char ch; int afirst;cout请输入第一个无符号长整型数，要求每四位用逗号隔开末尾为分号:data=0;p-next=p;p-prior=p;cinafirstch;/输入第一个结点数据if(a
13、firstdata=-1;afirst=-afirst;else ahead-data=1;p=new lnode;p-data=afirst;p-next=ahead;ahead-prior=p; ahead-next=p;p-prior=ahead; while(ch!=;)cinafirstch;p=new lnode; p-data=afirst; p-next=ahead-next;ahead-next-prior=p;ahead-next=p;p-prior=ahead;return OK;int inputb(lnodelist &bhead)/输入长整数blnode *p;ch
14、ar ch; int bfirst;cout请输入第二个无符号长整型数，要求每四位用逗号隔开末尾为分号:data=0;p-next=p;cinbfirstch;/输入第一个结点数据if(bfirstdata=-1; bfirst=-bfirst;else bhead-data=1;p=new lnode;p-data=bfirst;p-next=bhead; bhead-prior=p;bhead-next=p;p-prior=bhead;while(ch!=;)cinbfirstch;p=new lnode; p-data=bfirst; p-next=bhead-next;bhead-ne
15、xt-prior=p;bhead-next=p;p-prior=bhead;return OK;void putoutc(lnode *chead)/输出结果lnode *s,*pr;pr=chead-next;if(pr!=chead)coutdata; pr=pr-next;while(pr!=chead)if(pr-data=0)coutdata0&pr-data10)coutdata=10&pr-data100)coutdata=100&pr-data1000)cout0;coutdata;s=pr;pr=pr-next;delete s;coutnext;pb=bhead-next;
16、p=chead=new lnode;/头结点p-data=0;p-next=p;p-prior=p;while(pa!=ahead&pb!=bhead)sum=pa-data+pb-data+carry;p=new lnode;p-data=sum%10000;carry = sum/10000; p-next=chead-next;chead-next-prior=p;chead-next=p;p-prior=chead;pa=pa-next;pb=pb-next;if(pa!=ahead)/a还没有处理完，把a剩下的数字加到和上while(pa!=ahead)sum=pa-data+car
17、ry;p=new lnode;p-data=sum%10000; p-next=chead-next;chead-next-prior=p;chead-next=p;p-prior=chead;carry = sum/10000;pa=pa-next;if(pb!=bhead)/b还没有处理完，把b剩下的数字加到和上while(pb!=bhead)sum=pb-data+carry;p=new lnode;p-data=sum%10000; p-next=chead-next; chead-next-prior=p; chead-next=p; p-prior=chead; carry = s
18、um/10000; pb=pb-next;if(carry)/如果最后一位有进位，就申请一个结点存储p=new lnode;p-data=carry;p-next=chead-next;chead-next-prior=p;chead-next=p;p-prior=chead;putoutc(chead);return OK;int unsigndesub(lnodelist &ahead,lnodelist &bhead)/无符号长整数的减法a比b大。int diffe,borrow=0; /借位lnode *pa,*pb,*chead;lnode *p;pa=ahead-next;pb=b
19、head-next;p=chead=new lnode;/头结点p-data=0;p-next=p;p-prior=p;while(pa!=ahead&pb!=bhead)diffe=pa-data-borrow-pb-data;if (diffedata=diffe; p-next=chead-next;chead-next-prior=p;chead-next=p;p-prior=chead;pa = pa-next;pb = pb-next;if(pa!=ahead)while(pa!=ahead)diffe=pa-data-borrow; if (diffedata=diffe; p-
20、next=chead-next; chead-next-prior=p; chead-next=p; p-prior=chead; pa=pa-next;while (p-data=0&p-next!=chead)lnode *s;s=p;p=p-next;chead-next=p;p-prior=chead;delete s;putoutc(chead);return OK;第二局部：int xuan(int &c) cout 开始菜单 endl;cout*请选择要进展的操作:*endl;cout1.加法运算 2.减法运算 3.乘法运算 4.除法运算c;return 0;int main()
21、int c,h;char b;lnodelist ahead,bhead;inputa(ahead);inputb(bhead);do xuan(c);switch(c)case 1:add(ahead,bhead);break;case 2:sub(ahead,bhead);break;case 3:mul(ahead,bhead);break;case 4:div(ahead,bhead);break;cout*是否还要进展其他运算操作，是选择Y,否选N;*b;if(b=Y)h=1;else h=0;while(h);return 0;五、总结经过这几天的编程，我发现我有好多的不足，给了我好多的启发，我感觉能变出一道题目来，真的很开心。在平常的学习中，没有发现数据结构有什么用处，于是也不太在意，但编完程序后，我知道了，其实根底的东西才要掌握的更熟练。我也深深的感到，细节决定程序的好坏，一个程序，可能就一点小毛病但却能使整个程序不能运行，必须要一点一点的去查找，所以在以后的编程中，还要细心，不可以马马虎虎的，这样对以后的编程是一个大麻烦。在以后我要好好学习，努力专研这门专业。不断的扩大自己的知识和阅读量。六、参考文献1严蔚敏、吴伟某某编数据结构C语言版清华大学2 严蔚敏、吴伟民数据结构习题集C语言版清华大学3 谭浩强编著面向对象程序设计C+清华大学
