数据结构课程设计长整数运算

1、、需求分析问题描述】设计一个程序实现两个任意长的整数求和运算【基本要求】 利用双向循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是： -(215-1)(215-1)。输入和输出形式： 按中国对于 长整数的表示习惯，每四位一组，组间用逗号隔开。测试数据】(1) 0；0；应输出“ 0”。(2) -345, 6789; -7654, 3211;应输出“ -1, 0000, 0000”。(3) £999, 9999; 1, 0000, 0000, 0000;应输出 “9999 0000, 0001”。(4) 1, 0001, 0001; -1, 0001, 0001;应

2、输出“ 0”。(5) 1, 0001, 0001; -1, 0001, 0000;应输出“ 1”。二、设计1. 设计思想( 1 )存储结构：循环双向链表( 2)主要算法基本思想：1 、每个结点中可以存放的最大整数为 215-1=32767,才能保证两数相加 不会溢出。但若这样存,即相当于按 32768进制数存,在十进制数与 32768 进制数之间的转换十分不方便。故可以在每个结点中仅存十进 制数 4 位, 即不超过 9999的非负整数,整个链表视为万进制数。2、可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示 元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存 于指针

3、数组中是简化程序结构的一种方法。不能给长整数位数规定上限。2. 设计表示( 1 )函数调用关系图：( 2)函数接口规格说明：结构体： struct dl_node int x; dl_node *pre;dl_node *next;初始化：void list_init(dl_node * h)插入元素：void list_insert(dl_node *h,int x)输出链表：void prin(dl_node *h)实现相加：void list_add(dl_node *h1,dl_node *h2)实现相减：void list_sub(dl_node *h1,dl_node *h2)3.

4、 详细设计（1）输入两个数，用链表来存储。链表的头结点的数据的值为1 时，表示的是输入的数非负；为 -1 时表示输入的数是负数。（ 2）在创建链表时，让高位在链表的尾部，低位在链表的头部。（3）在做加法时，先判断两个数的符号是否相同，如果相同，在根据加数的符 号，决定和数的符号，取两个数的绝对值做加法，但是的处理进位。（4）如果异号，用一函数来判断和的符号，判断异号的两个数相加和的符号， 当两个数的长度不相等时， 取较长数的符号作为和的符号， 否则比两个数的大小， 再决定和的符号。（5）异号的两个数想加时，先去两个数的绝对值，用较大的数减去较小的数， 差作为和的绝对值。如果相应的位够减时，直接

5、做减法，否则借位，但是要注意 被借位的值是否为零，如果为零，则继续借位。（6）输出最终结果，输出数时，要去掉大数最前面的零，直到数的首位不是零 时为止。 在输出地位的数时， 有可能某些单元的数低于四位， 必须要在四位数的 高位补零，即四位一个单元输出。空缺处用零补齐。三、调试分析（ 1）经过不断的的 DEBUG ，不断的输出看结果调试，最终成功（ 2）经验和体会：通过这次学习， 让我认识到自己在学习上的诸多不足。 从刚拿到题目到完成 整个编程，从理论到实践， 虽然学到很多的的东西， 但是也因为自己知识的不足， 不能考虑周全， 完全成功的完成此次课程设计。 在认识自己的不足后， 我便开始 认真复

6、习书本知识， 同时与动手能力强的同学互相交流， 让自己学到了很多平时 上课过程中学不到的东西。通过这次课程设计， 我深刻的认识到， 理论知识需要与实践结合， 才能真正 领悟所学知识。同时我发现，我现在的动手能力不强，所以还要继续努力。同时 还要学会独立思考，才能真正的编出属于我自己的程序。通过这次实习，敦促我将过去学习过的知识进行了温习，知识只有多巩固， 才能真正的理解与领悟。不论这次课程设计是否完全成功， 我相信它对我的影响还是很大的。 这会敦 促我在下次课程设计中，能更好地完成设计任务。为自己加油！四、用户手册 输入两整数，从低位起，每四位用逗号隔开，按从高到低位依次输入，以分 号结束此书

7、的输入；五、运行结果运行环境： code:blocks六、源代码#include<cstdio>#include<cstring>#include<string>#include<malloc.h> #include<iostream>#include<cstdlib> #include<cmath> using namespace std;/ 定义一个结构体 struct dl_node int x;dl_node *pre;dl_node *next;/结点的初始化 void list_init(dl_no

8、de * h)*h=(dl_node *)malloc(sizeof(dl_node); (*h)->x=0;(*h)->pre=*h; (*h)->next=*h;/插入一个元素，循环双向链表 void list_insert(dl_node *h,int x) h->x+;dl_node *s;s=(dl_node *)malloc(sizeof(dl_node); s->x=x;s->pre=h->pre; h->pre->next=s;s->next=h; h->pre=s;/打印输出void prin(dl_node

9、*h)/cout<<h->x<<endl;dl_node *p;p=h->next;if(p=h) /如果头结点为空，则直接输出 0puts("0");return;cout<<p->x;p=p->next;while(p!=h) /循环双向链表一直往右找，直到找到头结点为止 printf(",%04d",p->x); /%04d 为对齐方式，当一个结点值不足 4位则补齐 p=p->next;/cout<<p->x;puts("");/元素值相加

10、，已处理好hl比h2的长度大于等于hl的长度/最后结果保存在hl (即长串中)void list_add(dl_node *h1,dl_node *h2)dl_node *p=h1->pre,*q=h2->pre;int e=0;while(q!=h2)/每次相加，如果有进位则保存到 e 变量中int tmp=p->x+q->x+e; if(tmp>9999) p->x=tmp%10000; e=tmp/10000;elsep->x=tmp;p=p->pre;q=q->pre;/p=p->pre;/当hl长度大于h2的时候，还要对未相

11、加的部分进行操作 while(p!=h1)int tmp=p->x+e; if(tmp>9999) p->x=tmp%10000; e=tmp/10000;else p->x=tmp; p=p->pre; p=h1->next;/如果最高位得到的结果还有进位，那么就要再创建一个结点 if(e!=0)dl_node *s;s=(dl_node *)malloc(sizeof(dl_node); s->x=e;s->pre=p->pre; p->pre->next=s; s->next=p; p->pre=s;/元素值相

12、减 方法同相加类似/最后结果保存在hl (即长串中)void list_sub(dl_node *h1,dl_node *h2) dl_node *p=h1->pre,*q=h2->pre;此处flag的值即位借位的值，借位的值为 0或者为1,因为减0无关紧要 int flag=0;while(q!=h2)if(p->x-flag>=q->x)p->x-=q->x+flag;flag=0;else p->x=p->x+10000-q->x-flag; /p->pre->x-; flag=1; p=p->pre; q=

13、q->pre; /p=p->pre; /cout<<p->x<<endl;/同样的，如果 h1 的长度大于 h2 的长度，那么对剩下的操作 while(p!=h1)if(p->x-flag<0) p->x=p->x+10000-flag; flag=1;else p->x=p->x-flag; flag=0; p=p->pre;/cout<<p->x<<endl;/如果最高位为 0 的话，那么就要删除最高位的结点了 p=h1->next;while(p->x=0) p-

14、>pre->next=p->next; p->next->pre=p->pre; p=h1->next;int main()/ freopen("大数求和.txt","r",stdin);while(1)puts("");char c;int a;dl_node *h1,*h2;list_init(&h1); /输入元素，直到读入" ; " 则停止输入第一个链表值while(1)/cout<<"asdfa" scanf("%

15、d%c",&a,&c); /cout<<c<<endl;list_insert(h1,a); if(c='') break; /如果第一个元素小于 0，则取正值，并在头结点当中保存信息 if(h1->next->x<0) h1->x=-h1->x; h1->next->x=-h1->next->x;/prin(h1); list_init(&h2);int r=0;/相同方法输入第二个链表，碰到" ; "则停止，并且读到文件结束while(1) i

16、f(scanf("%d%c",&a,&c)=EOF) r=1;break; list_insert(h2,a);if(c='')break;/cout<<r<<endl;/如果第一个元素小于 0，则取正值，并在头结点当中保存信息 if(h2->next->x<0) h2->x=-h2->x; h2->next->x=-h2->next->x;/ h1_num 和 h2_num 分别表示长度int h1_num=h1->x,h2_num=h2->x;/把长

17、的放到 h1 里面，是为了后面的加减操作更顺利 if(abs(h1_num)<abs(h2_num)dl_node *tmp=h1; h1=h2;h2=tmp;h1_num=h1->x,h2_num=h2->x; /cout<<h1_num<<" "<<h2_num<<endl;/*此处为重点部分，分为两个部分，如果 h1 大于 h2 四种情况 如果hl等于h2也有四种情况*/其实在此处，可以缩减为 6 种情况，但为了方便，写了 8种如果他们的长度不相等，即hl大于h2 了 if(abs(h1_num)!=a

18、bs(h2_num) /如果都为正数if(h1_num>0&&h2_num>0)/prin(h1);list_add(h1,h2);prin(h1); continue;/如果都为负数else if(h1_num<0&&h2_num<0) list_add(h1,h2);cout<<"-"prin(h1); continue;/如果 h1 为正而 h2 为负else if(h1_num>0&&h2_num<0)list_sub(h1,h2);prin(h1); continue;/如果 h1 为负而 h2 为正else if(h1_num<0&&h2_num>0)cout<<"-" list_sub(h1,h2); prin(h1);/否则，如果他们长度都相等的话：else/如果都为正数if(h1_num>0&&h2_num>0) list_add(h1,h2); prin(h1); continue;/如果都为负数else if(h1_num<0&&h2_num<0) list_add(h1,h2); cout<