数据结构课程设计长整数四则运算(共6页)

1、精选优质文档-倾情为你奉上数据结构课程设计题目：长整数四则运算班级学号学生姓名提交日期成 绩 计算机与通信工程学院长整数四则运算 一 需求分析： 问题描述：设计一个实现任意长的整数进行加法运算的演示程序。基本要求：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是 -(215 - 1) (215 - 1)。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。在现实生活中有很多地方，例如航空航海、生物医疗等等方面，都需要很大的数来表示，这些用int甚至长整型long long都是远不够的，所以需要有一种算法来解决这种大数的表示和运算。该问题只要求了

2、大数的相加运算。二 详细设计：大致思路：【存储】用两个链表，每个节点保存一位数，在链表头保存数的正负，正数保存1，负数保存-1，如果是正数，后面每一位都储存正数，负数每一位都储存负数，数字按照链表头到链表尾从高位到低位的顺序；【相加】从两个链表的尾部开始同步向前相加，加完存到第一个链表，第二个加完的结点销毁，会存在两个链表不一样长的情况，没加的直接连到链表的前面，最高位的符号存到链表的头；【调整】根据表头的符号，调整后面的数字的值，中间会产生进位或者退位的问题，各个节点的符号不一定相同，但对于正负数都可以建立同样的调整模式，将正负到tmp中（1或-1）加或者减(tmp*10)，然后对前一位加或

3、者减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)/将各个位的正负、大小、进

4、位进行调整源程序：#include<iostream>#include<stdio.h>#include<cstring>using 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; cin>>str; if(str0='-') p->data=-1; tmp=-1; else p->data=1; cur =

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

6、 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) cout<<p->data; p=p->next; l-; if(l%4=0&&l!=0) cout<<',' if(l=0) cout<<endl; void add(Node *h1,Node *t1,Node *h2,Node *t2) Node *

7、p1=t1->pre,*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=

8、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*tmp>0) if(p->data>9|p->data<-9) p->data-=(tmp*10); p->pre->data+=tmp; if(p->data*tmp<0) if(p->data<10|p->data>-10) p->data+=(t

9、mp*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->nex

10、t=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); 三 调试分析将两个链表对应位相加，再进行调整，算法的设计上还是不错的，但是遍历的次数太多对效率有所影响，这一点应该再修改修改以提高效率。两个链表在相加的时候把结果保存到第一个链表中，同时销毁第