




已阅读5页,还剩6页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
。数据结构课程设计题目:长整数四则运算班级学号学生姓名提交日期成 绩 计算机与通信工程学院长整数四则运算 一 需求分析: 问题描述:设计一个实现任意长的整数进行加法运算的演示程序。基本要求:利用双向循环链表实现长整数的存储,每个结点含一个整形变量。任何整形变量的范围是 -(215 - 1) (215 - 1)。输入和输出形式:按中国对于长整数的表示习惯,每四位一组,组间用逗号隔开。在现实生活中有很多地方,例如航空航海、生物医疗等等方面,都需要很大的数来表示,这些用int甚至长整型long long都是远不够的,所以需要有一种算法来解决这种大数的表示和运算。该问题只要求了大数的相加运算。二 详细设计:大致思路:【存储】用两个链表,每个节点保存一位数,在链表头保存数的正负,正数保存1,负数保存-1,如果是正数,后面每一位都储存正数,负数每一位都储存负数,数字按照链表头到链表尾从高位到低位的顺序;【相加】从两个链表的尾部开始同步向前相加,加完存到第一个链表,第二个加完的结点销毁,会存在两个链表不一样长的情况,没加的直接连到链表的前面,最高位的符号存到链表的头;【调整】根据表头的符号,调整后面的数字的值,中间会产生进位或者退位的问题,各个节点的符号不一定相同,但对于正负数都可以建立同样的调整模式,将正负到tmp中(1或-1)加或者减(tmp*10),然后对前一位加或者减tmp*1即可。第一位保留符号不变,这样不用处理多余的进位,也就不用再产生新的节点,也不用保存符号。【输出】从前到后遍历已经处理好的表,将每一位进行输出就可以了。结构体定义struct Node Node *pre; Node *next; int data; 功能函数void Input(Node *p,Node *t)/处理输入和保存void disply(Node *h,Node *t,int l)/输出void add(Node *h1,Node *t1,Node *h2,Node *t2)/每一位相加int adjust(Node *h,Node *t)/将各个位的正负、大小、进位进行调整源程序:#include#include#includeusing namespace std;struct Node Node *pre; Node *next; int data;void Input(Node *p,Node *t) Node * cur; string str; int tmp=1; char num; cinstr; if(str0=-) p-data=-1; tmp=-1; else p-data=1; cur = new Node; cur-data=str0-0; cur-pre=p; cur-next=t; t-pre=cur; p-next=cur; p=cur; for(int i=1;stri!=0;i+) if(stri=,) continue; cur = new Node; cur-data=(stri-0)*tmp; cur-pre=p; cur-next=t; t-pre=cur; p-next=cur; p=cur; void disply(Node *h,Node *t,int l) Node *p; p=h; p=h-next; while(p-data=0&p-next!=t) p=p-next; l-; while(p!=t) coutdata; p=p-next; l-; if(l%4=0&l!=0) cout,; if(l=0) coutpre,*p2=t2-pre; while(p1!=h1&p2!=h2) p1-data=p1-data+p2-data; p1=p1-pre; p2=p2-pre; delete(p2-next); if(p2!=h2) p2-next=h1-next; h1-next-pre=p2; h1-next=h2-next; h2-next-pre=h1; if(h1-next-data=0) h1-data=1; else h1-data=-1;int adjust(Node *h,Node *t) int l=0,tmp=h-data; Node *p=t-pre; while(p!=h-next) if(p-data*tmp0) if(p-data9|p-datadata-=(tmp*10); p-pre-data+=tmp; if(p-data*tmpdatadata-10) p-data+=(tmp*10); p-pre-data-=tmp; p-data=tmp*(p-data); p=p-pre; l+; l+; return l;int main() while(1) char symbol,ch; Node *head1 = new Node; Node *head2 = new Node; Node *tail1 = new Node; Node *tail2 = new Node; head1-next=tail1; head1-pre=NULL; tail1-pre=head1; tail1-next=NULL; head2-next=tail2; head2-pre=NULL; tail2-pre=head2; tail2-next=NULL; Input(head1,tail1); Input(head2,tail2); add(head1,tail1,head2,tail2); int l=adjust(head1,tail1); disply(head1,tail1,l); 三 调试分析将两个链表对应位相加,再进行调整,算法的设计上还是不错的,但是遍历的次数太多对效率有所影响,这一点应该再修改修改以提高效率。两个链表在相加的时候把结果保存到第一个链表中,同时销毁第二个链表的相对结点,这样节省了空间。在调试过程中,使用的多数是指针,指针掌握的不熟练,以至于调试的时候出现很多问题,指针还是很方便的 ,以后要多加练习
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论