数据结构课程设计报告(大整数的运算)

1、精选优质文档-倾情为你奉上山东理工大学计算机学院课 程 设 计（数据结构）班 级姓 名 学 号 指导教师二一二年一月十日课程设计任务书及成绩评定课题名称长整数的代数计算、题目的目的和要求：(1) 课程设计目的 巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。通过本课程的学习，能熟练掌握几种基本数据结构的基本操作，能够应用线性数据结构解决实际问题。（2）基本要求 ： 设计数据结构完成长整数的表示和存储，并编写算法来实现两长整数的加、减、 乘除等基本代数运算。 长整数长度在二十位以上。 实现两长整数的加、减、乘、除操作。 选作：

2、 输入输出均在文件中。 分析算法的时空复杂性。 、设计进度及完成情况日 期内 容1.2-1.3选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。1.41.5创建相关数据结构,录入源程序。1.61.7调试程序并记录调试中的问题，初步完成课程设计报告。1.9上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。1.9考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。、主要参考文献及资料1 严蔚敏 数据结构（C语言版）清华大学出版社 19992 严蔚敏 数据结构题集（C语言版）清华大学出版社 19993 谭浩强 C语言程序设计 清华大学出版

3、社4 与所用编程环境相配套的C语言或C+相关的资料、成绩评定：设计成绩： （教师填写）指导老师： （签字）二一二年 一 月 十 日专心-专注-专业目 录第一章 概述1第二章 系统分析2第三章 概要设计3第四章 详细设计4第五章 运行与测试14第六章 总结与心得16参考文献 15第一章 概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和

4、物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。在这次程序设计中我选择了长整数的代数计算这个题目，在一般的程序运算中，长整数是无法计算的，因为计算机一次能够运算的位数是有限，一旦整数很长，就需要一个程序来进行多次计算，通过这个程序，可一把一个长整数分成多个普通整数来进行计算，使得长整数也可以进行运算。我编写的这个程序就可以进行加减乘除的运算，各个数据也可以是负数。第二章 系统分析1、 设计一个实现长整数进行四则运算的程序，长整数长度在二十位以上，有正负数的区别。2、 输入每四位

5、一组，组间用逗号隔开，长整数位数没有上限，以分号结束长整型数据的输入。用lnode结点数据结构存储数据。每一个数据有一个头结点，它的data域用来放数据的正负数。其余结点的数都为正整数。3、 程序包含数据的输入，判断，运算,输出和主函数。4、 具体程序执行的命令包括: 输入函数：inputa();inputb();/的输入并建立双向循环链表 判断函数：compare();/比较数据的大小 运算函数：unsigndeadd();/无符号的加法unsigndesub();/无符号的减法add();sub();mul();div();/加减乘除四则运算 输出函数：divput();/除法结果的输出函

6、数putoutc();/其余结果的输出函数 主函数：main()；第三章 概要设计首先要考虑的是如何表示长整型数。可以4位数形成1组，而一个长整型数可能会有很多组这种4位数，而每节之间是有先后顺序的，因此我们可以考虑用数组和链表来存储数据。(1)再考虑到每个长整型数的长度在输入之间是无法预知的，因此使用链表在存储空间的分配上更方便一些。(2)在输入数据时总是从高位到低位地存储，而计算时总是从低位向高位运算，因此采用双向链表更方便，而为了从头结点方便地转到尾结点可以采用循环链表。综上考虑，应以双向循环链表表示长整数，每个结点含一个整型变量，且仅绝对值不超过9999的整数，整个链表用十进制数表示。

7、(3)对于每一个长整型数可以设置一个头结点，其中的数据域用来表示该长整型数的正负号及组数，该值的符号则表示该长整型数的符号，该数的绝对值表示该长整型数包含的4位数的组数。第一个存储4位数据组的结点称为首结点，而最后一个4位数据组结点称为尾结点。为此需要结构数据类型：双向循环链表：typedef struct lnode/结点结构体int data;struct lnode *next;struct lnode *prior;lnode,*lnodelist主要的模块可分为 输入函数：inputa();inputb();/的输入并建立双向循环链表 判断函数：compare();/比较两个数据的大

8、小，进行相应的的计算。 运算函数：add();sub();mul();div();/运算 输出函数：divput();putoutc();/除法的输出及其他运算的输出。 主函数：main()；第四章 详细设计#include<iostream>using namespace std;#include<stdio.h>#define OK 1;#define FALSE 0;typedef struct lnode/结点结构体int data;struct lnode *next;struct lnode *prior;lnode,*lnodelist;int compa

9、re(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(acount>bcount)q=1;else if(acount<bcount)q=-1;elsepa=ahead->prior;pb=bhead

10、->prior;while(pa->data=pb->data)&&(pa->prior!=ahead)pa=pa->prior;pb=pb->prior;if(pa->data>pb->data)q=1;else if(pa->data<pb->data)q=-1;else q=0;return 0;int inputa(lnodelist &ahead)/输入长整数alnode *p;char ch; int afirst;cout<<"请输入第一个无符号长整型数，要求每四

11、位用逗号隔开末尾为分号:"<<endl;p=ahead=new lnode;/头结点p->data=0;p->next=p;p->prior=p;cin>>afirst>>ch;/输入第一个结点数据if(afirst<0)ahead->data=-1;afirst=-afirst;else ahead->data=1;p=new lnode;p->data=afirst;p->next=ahead;ahead->prior=p; ahead->next=p;p->prior=ahea

12、d; while(ch!='')cin>>afirst>>ch;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;char ch; int bfirst;cout<<"请输入第二个无符号长整型数，要求每四位用逗号隔开末尾为分号:&q

13、uot;<<endl;p=bhead=new lnode;/头结点p->data=0;p->next=p;cin>>bfirst>>ch;/输入第一个结点数据if(bfirst<0)bhead->data=-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!='')cin&g

14、t;>bfirst>>ch;p=new lnode; p->data=bfirst; p->next=bhead->next;bhead->next->prior=p;bhead->next=p;p->prior=bhead;return OK;void putoutc(lnode *chead)/输出结果lnode *s,*pr;pr=chead->next;if(pr!=chead)cout<<pr->data;pr=pr->next;while(pr!=chead)if(pr->data=0)

15、cout<<"0000"else if(pr->data>0&&pr->data<10)cout<<"000"else if(pr->data>=10&&pr->data<100)cout<<"00"else if(pr->data>=100&&pr->data<1000)cout<<"0"cout<<pr->data;s=pr;p

16、r=pr->next;delete s;cout<<endl;int unsigndeadd(lnodelist &ahead,lnodelist &bhead)/无符号长整数的加法int sum,carry=0; /进位lnode *pa,*pb;lnode *p,*chead;pa=ahead->next;pb=bhead->next;p=chead=new lnode;/头结点p->data=0;p->next=p;p->prior=p;while(pa!=ahead&&pb!=bhead)sum=pa-&g

17、t;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+carry;p=new lnode;p->data=sum%10000;

18、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

19、->prior=chead; carry = sum/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

20、diffe,borrow=0; /借位lnode *pa,*pb,*chead;lnode *p;pa=ahead->next;pb=bhead->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 (diffe<0)borrow=1;diffe+=10000;else borrow=0; p=new lnode;/存储差p->data=di

21、ffe; 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 (diffe<0)borrow=1;diffe+=10000;else borrow=0; p=new lnode;/存储差 p->data=diffe; p->next=chead->next; chea

22、d->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 add(lnodelist &ahead,lnodelist &bhead)int e,acount=0,bcount=0,q;e=ahea

23、d->data*bhead->data;cout<<"输出运算结果为:"<<endl;if(e=1)if(ahead->data=-1)cout<<"-"unsigndeadd(ahead,bhead);else unsigndeadd(ahead,bhead);elsecompare(ahead,bhead,q);if(q=1)if(ahead->data=-1)cout<<"-"unsigndesub(ahead,bhead);else unsigndesub

24、(ahead,bhead);elseif(ahead->data=1)cout<<"-"unsigndesub(bhead,ahead);else unsigndesub(bhead,ahead);return 0;int sub(lnodelist &ahead,lnodelist &bhead)int e,q;e=ahead->data*bhead->data;cout<<"输出运算结果为:"<<endl;if(e=-1)if(ahead->data=-1)cout<&

25、lt;"-"unsigndeadd(ahead,bhead);elseunsigndeadd(ahead,bhead);elsecompare(ahead,bhead,q);if(q=1)if(ahead->data=-1)cout<<"-"unsigndesub(ahead,bhead);else unsigndesub(ahead,bhead);elseif(ahead->data=1)cout<<"-"unsigndesub(bhead,ahead);else unsigndesub(bhea

26、d,ahead);return 0;int mul(lnodelist &ahead,lnodelist &bhead)long multi,carry; /进位int e;lnode *pa,*pb,*pc,*cnow;lnode *p,*chead;e=ahead->data*bhead->data;cout<<"输出运算结果为:"<<endl;if(e=-1)cout<<"-"pa=ahead->next;pb=bhead->next;p=chead=new lnode;/

27、头结点p->data=0;p->next=p;p->prior=p;pc=cnow=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; chead->next->prior=p; chead->next=p; p->prior=che

28、ad;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;cnow=cnow->prior;pc=cnow;p

29、a=ahead->next;pb=pb->next;putoutc(chead);return OK;int divput(lnode *chead)lnode *s,*pr;pr=chead->prior; if(pr!=chead) cout<<pr->data;pr=pr->prior;while(pr!=chead)if(pr->data=0)cout<<"0000"else if(pr->data>0&&pr->data<10)cout<<"0

30、00"else if(pr->data>=10&&pr->data<100)cout<<"00"else if(pr->data>=100&&pr->data<1000)cout<<"0"cout<<pr->data;s=pr;pr=pr->prior;delete s;cout<<endl;return 0;int div(lnodelist &ahead,lnodelist &bhead

31、)cout<<"输出运算结果为:"<<endl;lnode *pa,*pb,*s,*p;int borrow=0,diffe,count=0,q,acount=0,bcount=0,e; /借位e=ahead->data*bhead->data;cout<<"输出运算结果为:"<<endl; cout<<"商为"if(e=-1)cout<<"-"while(borrow=0)compare(ahead,bhead,q);if(q=0

32、)borrow=1;cout<<+count<<"，余数为0"<<endl;else if(q=-1)borrow=1;cout<<count<<"，余数为"divput(ahead);else count=count+1;pa=ahead->next;pb=bhead->next;while(pa!=ahead&&pb!=bhead)diffe=pa->data-borrow-pb->data;if(diffe<0)borrow=1;diffe=diffe+10000;else borrow=0;pa->data=diffe;pa = pa->next;pb = pb->next;if(pa!=ahead)while(pa!=ahead)diffe=pa->data-borrow;if (diffe<0)borrow=1;diffe+=10000;else borrow=0;pa->data=diffe;pa=pa->next;p=pa->prior;while(p->data=0&&p->prior!=ahead)s=