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

山东理工大学计算机学院课程设计（数据结构）班级姓名学号指导教师二○一二年一月十日课程设计任务书及成绩评定课题名称长整数的代数计算Ⅰ、题目的目的和要求：(1)课程设计目的巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。通过本课程的学习，能熟练掌握几种基本数据结构的基本操作，能够应用线性数据结构解决实际问题。（2）基本要求：设计数据结构完成长整数的表示和存储，并编写算法来实现两长整数的加、减、乘除等基本代数运算。①长整数长度在二十位以上。②实现两长整数的加、减、乘、除操作。选作：③输入输出均在文件中。④分析算法的时空复杂性。Ⅱ、设计进度及完成情况日期内容1.2-1.3选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。1.4~1.5创建相关数据结构,录入源程序。1.6~1.7调试程序并记录调试中的问题，初步完成课程设计报告。1.9上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。1.9考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。Ⅲ、主要参考文献及资料[1]严蔚敏数据结构（C语言版）清华大学出版社1999[2]严蔚敏数据结构题集（C语言版）清华大学出版社1999[3]谭浩强C语言程序设计清华大学出版社[4]与所用编程环境相配套的C语言或C++相关的资料Ⅳ、成绩评定：设计成绩：（教师填写）指导老师：（签字）二○一二年一月十日目录第一章概述……………………………………………………………1第二章系统分析………………………………………………………2第三章概要设计………………………………………………………3第四章详细设计………………………………………………………4第五章运行与测试……………………………………………………14第六章总结与心得……………………………………………………16参考文献………………………………………………………………151第一章概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。在这次程序设计中我选择了长整数的代数计算这个题目，在一般的程序运算中，长整数是无法计算的，因为计算机一次能够运算的位数是有限，一旦整数很长，就需要一个程序来进行多次计算，通过这个程序，可一把一个长整数分成多个普通整数来进行计算，使得长整数也可以进行运算。我编写的这个程序就可以进行加减乘除的运算，各个数据也可以是负数。2第二章系统分析1、设计一个实现长整数进行四则运算的程序，长整数长度在二十位以上，有正负数的区别。2、输入每四位一组，组间用逗号隔开，长整数位数没有上限，以分号结束长整型数据的输入。用lnode结点数据结构存储数据。每一个数据有一个头结点，它的data域用来放数据的正负数。其余结点的数都为正整数。3、程序包含数据的输入，判断，运算,输出和主函数。4、具体程序执行的命令包括:输入函数：inputa();inputb();//的输入并建立双向循环链表判断函数：compare();//比较数据的大小运算函数：unsigndeadd();//无符号的加法unsigndesub();//无符号的减法add();sub();mul();div();//加减乘除四则运算输出函数：divput();//除法结果的输出函数putoutc();//其余结果的输出函数主函数：main()；3第三章概要设计首先要考虑的是如何表示长整型数。可以4位数形成1组，而一个长整型数可能会有很多组这种4位数，而每节之间是有先后顺序的，因此我们可以考虑用数组和链表来存储数据。(1)再考虑到每个长整型数的长度在输入之间是无法预知的，因此使用链表在存储空间的分配上更方便一些。(2)在输入数据时总是从高位到低位地存储，而计算时总是从低位向高位运算，因此采用双向链表更方便，而为了从头结点方便地转到尾结点可以采用循环链表。综上考虑，应以双向循环链表表示长整数，每个结点含一个整型变量，且仅绝对值不超过9999的整数，整个链表用十进制数表示。(3)对于每一个长整型数可以设置一个头结点，其中的数据域用来表示该长整型数的正负号及组数，该值的符号则表示该长整型数的符号，该数的绝对值表示该长整型数包含的4位数的组数。第一个存储4位数据组的结点称为首结点，而最后一个4位数据组结点称为尾结点。为此需要结构数据类型：双向循环链表：typedefstructlnode{//结点结构体intdata;structlnode*next;structlnode*prior;}lnode,*lnodelist主要的模块可分为输入函数：inputa();inputb();//的输入并建立双向循环链表判断函数：compare();//比较两个数据的大小，进行相应的的计算。运算函数：add();sub();mul();div();//运算输出函数：divput();putoutc();//除法的输出及其他运算的输出。主函数：main()；4第四章详细设计#includeiostreamusingnamespacestd;#includestdio.h#defineOK1;#defineFALSE0;typedefstructlnode{//结点结构体intdata;structlnode*next;structlnode*prior;}lnode,*lnodelist;intcompare(lnodelist&ahead,lnodelist&bhead,int&q)//比较a和b的大小{lnode*pa,*pb;intbcount=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;elseif(acountbcount)q=-1;else{pa=ahead-prior;pb=bhead-prior;while((pa-data==pb-data)&&(pa-prior!=ahead)){pa=pa-prior;pb=pb-prior;}if(pa-datapb-data)q=1;elseif(pa-datapb-data)q=-1;elseq=0;}return0;}intinputa(lnodelist&ahead)//输入长整数a{lnode*p;charch;intafirst;cout请输入第一个无符号长整型数，要求每四位用逗号隔开末尾为分号:endl;p=ahead=newlnode;//头结点p-data=0;p-next=p;p-prior=p;cinafirstch;//输入第一个结点数据if(afirst0)5{ahead-data=-1;afirst=-afirst;}elseahead-data=1;p=newlnode;p-data=afirst;p-next=ahead;ahead-prior=p;ahead-next=p;p-prior=ahead;while(ch!=';'){cinafirstch;p=newlnode;p-data=afirst;p-next=ahead-next;ahead-next-prior=p;ahead-next=p;p-prior=ahead;}returnOK;}intinputb(lnodelist&bhead)//输入长整数b{lnode*p;charch;intbfirst;cout请输入第二个无符号长整型数，要求每四位用逗号隔开末尾为分号:endl;p=bhead=newlnode;//头结点p-data=0;p-next=p;cinbfirstch;//输入第一个结点数据if(bfirst0){bhead-data=-1;bfirst=-bfirst;}elsebhead-data=1;p=newlnode;p-data=bfirst;p-next=bhead;bhead-prior=p;bhead-next=p;p-prior=bhead;while(ch!=';'){cinbfirstch;p=newlnode;p-data=bfirst;p-next=bhead-next;bhead-next-prior=p;6bhead-next=p;p-prior=bhead;}returnOK;}voidputoutc(lnode*chead)//输出结果{lnode*s,*pr;pr=chead-next;if(pr!=chead){coutpr-data;pr=pr-next;}while(pr!=chead){if(pr-data==0)cout0000;elseif(pr-data0&&pr-data10)cout000;elseif(pr-data=10&&pr-data100)cout00;elseif(pr-data=100&&pr-data1000)cout0;coutpr-data;s=pr;pr=pr-next;deletes;}coutendl;}intunsigndeadd(lnodelist&ahead,lnodelist&bhead)//无符号长整数的加法{intsum,carry=0;//进位lnode*pa,*pb;lnode*p,*chead;pa=ahead-next;pb=bhead-next;p=chead=newlnode;//头结点p-data=0;p-next=p;p-prior=p;while(pa!=ahead&&pb!=bhead){sum=pa-data+pb-data+carry;p=newlnode;p-data=sum%10000;carry=sum/10000;p-next=chead-next;chead-next-prior=p;chead-next=p;7p-prior=chead;pa=pa-next;pb=pb-next;}if(pa!=ahead)//a还没有处理完，把a剩下的数字加到和上{while(pa!=ahead){sum=pa-data+carry;p=newlnode;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=newlnode;p-data=sum%10000;p-next=chead-next;chead-next-prior=p;chead-next=p;p-prior=chead;carry=sum/10000;pb=pb-next;}}if(carry)//如果最后一位有进位，就申请一个结点存储{p=newlnode;p-data=carry;p-nex