《数据结构课程设计长整数运算》由会员分享,可在线阅读,更多相关《数据结构课程设计长整数运算(13页珍藏版)》请在金锄头文库上搜索。
1、. 一、需求分析【问题描述】设计一个程序实现两个任意长的整数求和运算。【基本要求】利用双向循环链表实现长整数的存储,每个结点含一个整型变量。任何整型变量的范围是:-(215-1)(215-1)。输入和输出形式: 按中国对于长整数的表示习惯,每四位一组,组间用逗号隔开。【测试数据】 (1)0;0;应输出“0”。 (2)2345,6789;-7654,3211;应输出“-1,0000,0000”。 (3)9999,9999;1,0000,0000,0000;应输出“9999,0000,0001”。 (4)1,0001,0001;-1,0001,0001;应输出“0”。 (5)1,0001,0001
2、;-1,0001,0000;应输出“1”。二、设计1. 设计思想(1)存储结构:循环双向链表(2)主要算法基本思想:1、每个结点中可以存放的最大整数为215-1=32767,才能保证两数相加不会溢出。但若这样存,即相当于按32768进制数存,在十进制数与32768进制数之间的转换十分不方便。故可以在每个结点中仅存十进 制数4位,即不超过9999的非负整数,整个链表视为万进制数。 2、可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。2. 设计表示 (1)函数
3、调用关系图:(2)函数接口规格说明:结构体:struct dl_nodeint 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. 详细设计(1)输入两个数,用链表来存储。链表的头结点的数据的值为1时,表示的是输入的数非负
4、;为-1时表示输入的数是负数。(2)在创建链表时,让高位在链表的尾部,低位在链表的头部。(3)在做加法时,先判断两个数的符号是否相同,如果相同,在根据加数的符号,决定和数的符号,取两个数的绝对值做加法,但是的处理进位。(4)如果异号,用一函数来判断和的符号,判断异号的两个数相加和的符号,当两个数的长度不相等时,取较长数的符号作为和的符号,否则比两个数的大小,再决定和的符号。(5)异号的两个数想加时,先去两个数的绝对值,用较大的数减去较小的数,差作为和的绝对值。如果相应的位够减时,直接做减法,否则借位,但是要注意被借位的值是否为零,如果为零,则继续借位。(6)输出最终结果,输出数时,要去掉大数最
5、前面的零,直到数的首位不是零时为止。在输出地位的数时,有可能某些单元的数低于四位,必须要在四位数的高位补零,即四位一个单元输出。空缺处用零补齐。三、调试分析(1)经过不断的的DEBUG,不断的输出看结果调试,最终成功(2)经验和体会:通过这次学习,让我认识到自己在学习上的诸多不足。从刚拿到题目到完成整个编程,从理论到实践,虽然学到很多的的东西,但是也因为自己知识的不足,不能考虑周全,完全成功的完成此次课程设计。在认识自己的不足后,我便开始认真复习书本知识,同时与动手能力强的同学互相交流,让自己学到了很多平时上课过程中学不到的东西。通过这次课程设计,我深刻的认识到,理论知识需要与实践结合,才能真
6、正领悟所学知识。同时我发现,我现在的动手能力不强,所以还要继续努力。同时还要学会独立思考,才能真正的编出属于我自己的程序。通过这次实习,敦促我将过去学习过的知识进行了温习,知识只有多巩固,才能真正的理解与领悟。不论这次课程设计是否完全成功,我相信它对我的影响还是很大的。这会敦促我在下次课程设计中,能更好地完成设计任务。为自己加油!四、用户手册输入两整数,从低位起,每四位用逗号隔开,按从高到低位依次输入,以分号结束此书的输入;五、运行结果 运行环境:code:blocks六、源代码#include#include#include#include#include#include#includeus
7、ing namespace std;/ 定义一个结构体struct dl_nodeint x;dl_node *pre;dl_node *next;/结点的初始化void list_init(dl_node * 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-p
8、re-next=s;s-next=h;h-pre=s;/打印输出void prin(dl_node *h)/coutxnext;if(p=h) /如果头结点为空,则直接输出0puts(0);return;coutx;p=p-next;while(p!=h) /循环双向链表一直往右找,直到找到头结点为止printf(,%04d,p-x); /%04d为对齐方式,当一个结点值不足4位则补齐p=p-next;/coutx;puts();/元素值相加,已处理好h1比h2的长度大于等于h1的长度/最后结果保存在h1(即长串中)void list_add(dl_node *h1,dl_node *h2)d
9、l_node *p=h1-pre,*q=h2-pre;int e=0;while(q!=h2)/每次相加,如果有进位则保存到e变量中int tmp=p-x+q-x+e;if(tmp9999)p-x=tmp%10000;e=tmp/10000;elsep-x=tmp;p=p-pre;q=q-pre;/p=p-pre;/当h1长度大于h2的时候,还要对未相加的部分进行操作while(p!=h1)int tmp=p-x+e;if(tmp9999)p-x=tmp%10000;e=tmp/10000;else p-x=tmp;p=p-pre;p=h1-next;/如果最高位得到的结果还有进位,那么就要再
10、创建一个结点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;/元素值相减 方法同相加类似/最后结果保存在h1(即长串中)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;
11、elsep-x=p-x+10000-q-x-flag;/p-pre-x-;flag=1;p=p-pre;q=q-pre;/p=p-pre;/coutxx-flagx=p-x+10000-flag;flag=1;elsep-x=p-x-flag;flag=0;p=p-pre;/coutxnext;while(p-x=0)p-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) /coutasdfa;scanf(%d%c,&a,&c);/coutcnext-xx=-h1-x;h1-next-x=-h1-next-x;/prin(h1);list_init(&h2);int r=0;/相同方法输入第二个链表,碰到 ; 则停止,并且读到文件结束while(1)if(scanf(%d%c,&a,&c)=EOF) r=1;break;list_insert(h2,a);if(c=;)break;/coutrne