数据结构课程设计长整数四则运算.docx

数据结构课程设计题目：长整数四则运算班级学号学生姓名提交日期成 绩 计算机与通信工程学院长整数四则运算 一 需求分析： 问题描述：设计一个实现任意长的整数进行加法运算的演示程序。基本要求：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是 -(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); 三 调试分析将两个链表对应位相加，再进行调整，算法的设计上还是不错的，但是遍历的次数太多对效率有所影响，这一点应该再修改修改以提高效率。两个链表在相加的时候把结果保存到第一个链表中，同时销毁第二个链表的相对结点，这样节省了空间。在调