长整数的四则运算

1、课程名称 :数据结构课程设计课程设计题目 :长整数的四则运算姓 名:院系 :计算机学院专 业: 计算机科学与技术年 级:学 号 :指导教师 :2014 年月日-。目 录1课程设计的目的32需求分析33课程设计报告内容33.1概要设计33.2详细设计33.3调试分析33.4用户手册43.5测试结果43.6程序清单54小结 x5参考文献 8-可编辑修改 -。1. 课程设计的目的(1) 熟练使用 C 语言编写程序，解决实际问题 ;(2) 了解并掌握数据结构与算法的设计方法， 具备初步的独立分析和设计能力 ;(3) 初步掌握软件开发过程的问题分析、 系统设计、 程序编码、测试等基本方法和技能 ;(4)

2、 提高综合运用所学的理论知识和方法独立分析和解决问题的能力;2. 需求分析问题描述 : 设计一个实现任意长的整数进行加法运算的演示程序。 基本要求 : 利用双向循环链表实现长整数的存储， 每个结点含一个整形变量。 任何整形变量的范围是 -215 - 1 215 - 1 。输入和输出形式 : 按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。测试数据:(1)0;0; 应输出“0” 。(2)-23456789;-76543211; 应输出“-100000000” 。应输出“999(4)100010001;-100010001; 应输出“ 0”。(5)100010001;-100010000;

3、应输出“1” 。(6)-999999999999;-999999999999; 应输出“” 。应输出“”。实现提示 :(1) 每个结点中可以存放的最大整数为 32767 ，才能保证两数相加不会溢出，但若这样存放， 即相当于按 32768 进制存放，在十进制与 32768 进制数之间的转换十分不方便，故可以在每个结点中仅存十进制的4位，即不超过 9999 的非负整数，整个链表表示为万进制。 (2) 可以利用头结点数据域的符号代表长整数的符号。 用其绝对值表示元素结点数目。 相加过程中不要破坏两个操作数链表。不能给长整数位数规定上限。3.1 概要设计利用双向循环链表现实长整数的存储， 每个结点含一

4、个整形变量。 输入的形式以回车结束， 可以直接输入正数或负数。 按中国对于长整数的表示习惯， 每四位一组，除数字和位于首位置的负号外， 其它一切字符都将作为分隔符， 连续多个分隔符当一个处理 , 但不使用分隔符也不影响结果。3.3 调试分析测试数据，测试输出的结果， 时间复杂度分析， 和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？） ，算法的改进设想。-可编辑修改 -。3.4 用户手册 ( 略)3.5 测试结果 ( 略)4 总结长整数用双向循环队列的数据结构，用的比较少，查阅不少资料5、程序清单 :( 见附录 )#include<iostream>#include

5、<string.h>#include<stdlib.h>#include<math.h> using namespace std; struct LinkNodeint data;/记录每个节点的整数（小于10000）LinkNode *next;/记录下一个节点的地址LinkNode *pre;/记录前一个节点的地址;class LinkListprivate:LinkNode *head0,*head1;/head0， head1 分别记录两个整数链表的-可编辑修改 -。头指针LinkNode *currptr;LinkNode *result;/res

6、ult记录结果链表的头指针public:LinkList();/构造函数，初始化链表LinkList();/析构函数，释放空间void Creat(string a);/引入字符串，创立两个链表，分别表示两个整数void Add();/实现两个整数相加void Display();/显示结果void addtwo();/ 节点多的作为被加数，少的作为加数，实现整数绝对值大的加小的;int sum(int n);LinkList:LinkList()/构造函数，初始化链表head0=new LinkNode;/ 申请一个空间记录整数的符号和节点数head1=new LinkNode;head0-

7、>next=head0;head0->pre=head0;/初始化链表，建立双向循环链表head1->next=head1;head1->pre=head1;result=new LinkNode;result->next=result;result->pre=result;currptr=NULL;LinkList:LinkList()/析构函数，释放空间LinkNode *p1=head0,*p2=head1,*p3=result;/ 三个指针分别指向三条链表的头指针 while(p1!=p1->pre)p1->pre->next=p1

8、->next;p1->next->pre=p1->pre; currptr=p1; p1=p1->next;delete currptr;while(p2!=p2->pre)/逐个删除节点，释放空间p2->pre->next=p2->next;-可编辑修改 -。p2->next->pre=p2->pre;currptr=p2;p2=p2->next;delete currptr;while(p3!=p3->pre)p3->pre->next=p3->next;p3->next->p

9、re=p3->pre;currptr=p3;p3=p3->next;delete currptr;void LinkList:Creat(string a)/引入字符串，创立两个链表，分别表示两个整数int i=0,j=0,m=0,n=0,k=0,l=0,s=0,w=0;/i记录字符串， j 记录加数节点数； s 记录被加数节点数/w标记字符串中的 - 号/k记录字符串中的字符转化为整数的值，l 使每个节点记录4 位while(am!='') m+;/m记录字符串中被加数的字符数n=m;while(an!='0') n+;/n记录字符串的总字符数if

10、(a0='-')head0->data=(-1);/记录整数符号w=1;else head0->data=1;for(i=m-1;i>=w;i-)if(ai!=',')/把字符转化为整数k+=(ai-'0')*sum(l);l+;if(ai=','|i=w)currptr=new LinkNode;/把整数存到双向循环链表中currptr->data=k;currptr->next=head0;-可编辑修改 -。currptr->pre=head0->pre;head0->pre-&

11、gt;next=currptr;head0->pre=currptr;head0=currptr;s+;/节点数加 1k=0;/重新初始化 k 和 ll=0;head0->pre->data*=s;/存储整数符号和节点数/ 与建第一个整数链表一样，建立第二个整数链表 head1 k=0;l=0;if(am+1='-')head1->data=(-1);m+;elsehead1->data=1;for(i=n-1;i>m;i-)if(ai!=',')k+=(ai-'0')*sum(l);l+;if(ai='

12、;,'|i=m+1)currptr=new LinkNode;currptr->data=k;currptr->next=head1;currptr->pre=head1->pre;head1->pre->next=currptr;head1->pre=currptr;head1=currptr;j+;k=0;l=0;-可编辑修改 -。head1->pre->data*=j;void LinkList:Add()/实现两个整数相加LinkNode *temp;if(abs(head0->pre->data)>abs

13、(head1->pre->data)/ 两个整数中，绝对值大的为被加数 addtwo();else if(abs(head0->pre->data)<abs(head1->pre->data)temp=head0;head0=head1;head1=temp;addtwo();else if(abs(head0->pre->data)=abs(head1->pre->data)int k1,k2;LinkNode *p=head0,*q=head1;/ 如果节点数相同，则判断节点中数值大小while(p->data=q-&

14、gt;data&&p!=head0->pre->pre&&q!=head1->pre->pre)p=p->next;q=q->next;k1=p->data;k2=q->data;if(k1>k2)addtwo();elsetemp=head0;head0=head1;head1=temp;addtwo();void LinkList:addtwo()/ 节点多的作为被加数，少的作为加数，实现整数绝对值大的加小的/默认 head0 存的整数绝对值比 head1 大int s=0,m1=head0->da

15、ta,m2=head1->data;-可编辑修改 -。m1=(head0->pre->data/abs(head0->pre->data);/head0的符号m2=(head1->pre->data/abs(head1->pre->data);/head1的符号LinkNode *p=head0->pre->pre,*q=head1->pre->pre;result->data=head0->pre->data;/存结果的节点数和符号while(q!=head1->pre)/head0 存的整

16、数绝对值比head1 大，即 head0 的节点数大于或等于head1currptr=new LinkNode;currptr->data=(p->data)*m1+(q->data)*m2+s;/两整数相加if(m1*m2)>0)/如果符号相同if(abs(currptr->data)-10000>=0)/相加后超过10000，则进位s=currptr->data/10000;currptr->data=abs(currptr->data)%10000;else/abs(currptr->data)-10000<0，不进位s=

17、0;currptr->data=abs(currptr->data);else if(m1>0&&m2<0)/ 符号不同，在此相当于实现两个正整数相减s=0;if(currptr->data<0)/小于 0，向前一位借1currptr->data+=10000;s=-1;else if(m1<0&&m2>0)/ 符号不同，在此相当于实现负整数加上正整数s=0;if(currptr->data>0)/大于 0，currptr->data=10000-currptr->data;s=1;-

18、可编辑修改 -。else currptr->data=abs(currptr->data);currptr->next=result;/存入链表currptr->pre=result->pre;result->pre->next=currptr;result->pre=currptr;result=currptr;p=p->pre;q=q->pre;/ 当 head0 节点数比 head1 长时，继续建链 while(p!=head0->pre)currptr=new LinkNode; currptr->data=p-&

19、gt;data*m1+s; s=currptr->data/10000;if(m1*m2)>0)if(abs(currptr->data)-10000>=0)s=currptr->data/10000;currptr->data=abs(currptr->data)%10000;else s=0;currptr->data=abs(currptr->data);else if(m1>0&&m2<0)s=0;if(currptr->data<0)currptr->data+=10000;s=-1;

20、else if(m1<0&&m2>0)s=0;if(currptr->data>0)currptr->data=10000-currptr->data;s=1;else currptr->data=abs(currptr->data);-可编辑修改 -。currptr->data=abs(currptr->data)%10000;currptr->next=result;currptr->pre=result->pre;result->pre->next=currptr;result-&g

21、t;pre=currptr;result=currptr;p=p->pre;if(s!=0)/处理相加后，进位问题currptr=new LinkNode;currptr->data=abs(s);currptr->next=result;currptr->pre=result->pre;result->pre->next=currptr;result->pre=currptr;result=currptr;result->pre->data=m1*(abs(result->pre->data)+1);void LinkL

22、ist:Display()/显示结果LinkNode *p=result;int FuHao=result->pre->data/abs(result->pre->data);/结果的符号while(p->data=0&&p!=result->pre->pre)/ 当运算后前几个节点的数据为0 时，不输出p=p->next;result->pre->data=(abs(result->pre->data)-1)*FuHao;/ 结果记录非 0 节点数cout<<FuHao*p->data;

23、/首先显示符号和第一个节点中的数if(abs(result->pre->data)!=1) p=p->next; /判断非 0 节点数是否为 1while(p!=result->pre->pre)/继续输出cout<<","/每 4 位一组，并用，隔开cout.width(4);cout.fill('0');cout<<p->data;p=p->next;if(p=result->pre->pre&&abs(result->pre->data)!=1)/ 显示最后一个节点数据-可编辑修改 -。cout<<","cout.width(4)