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

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

《数据结构课程设计长整数运算.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计长整数运算.docx（18页珍藏版）》请在冰点文库上搜索。

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

一、需求分析

【问题描述】

设计一个程序实现两个任意长的整数求和运算。

【基本要求】

利用双向循环链表实现长整数的存储，每个结点含一个整型变量。

任何整型变量的范围是：

-（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；-1，0001，0000；应输出“1”。

二、设计

1.设计思想

（1）存储结构：

循环双向链表

（2）主要算法基本思想：

1、每个结点中可以存放的最大整数为215-1=32767，才能保证两数相加不会溢出。

但若这样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。

故可以在每个结点中仅存十进制数4位，即不超过9999的非负整数，整个链表视为万进制数。

2、可以利用头结点数据域的符号代表长整数的符号。

用其绝对值表示元素结点数目。

相加过程中不要破坏两个操作数链表。

两操作数的头指针存于指针数组中是简化程序结构的一种方法。

不能给长整数位数规定上限。

2.设计表示

（1）函数调用关系图：

（2）函数接口规格说明：

结构体：

structdl_node

{

intx;

dl_node*pre;

dl_node*next;

};

初始化：

voidlist_init（dl_node**h）

插入元素：

voidlist_insert（dl_node*h,intx）

输出链表：

voidprin（dl_node*h）

实现相加：

voidlist_add（dl_node*h1,dl_node*h2）

实现相减：

voidlist_sub（dl_node*h1,dl_node*h2）

3.详细设计

（1）输入两个数，用链表来存储。

链表的头结点的数据的值为1时，表示的是输入的数非负；为-1时表示输入的数是负数。

（2）在创建链表时，让高位在链表的尾部，低位在链表的头部。

（3）在做加法时，先判断两个数的符号是否相同，如果相同，在根据加数的符号，决定和数的符号，取两个数的绝对值做加法，但是的处理进位。

（4）如果异号，用一函数来判断和的符号，判断异号的两个数相加和的符号，当两个数的长度不相等时，取较长数的符号作为和的符号，否则比两个数的大小，再决定和的符号。

（5）异号的两个数想加时，先去两个数的绝对值，用较大的数减去较小的数，差作为和的绝对值。

如果相应的位够减时，直接做减法，否则借位，但是要注意被借位的值是否为零，如果为零，则继续借位。

（6）输出最终结果，输出数时，要去掉大数最前面的零，直到数的首位不是零时为止。

在输出地位的数时，有可能某些单元的数低于四位，必须要在四位数的高位补零，即四位一个单元输出。

空缺处用零补齐。

三、调试分析

（1）经过不断的的DEBUG，不断的输出看结果调试，最终成功

（2）经验和体会：

通过这次学习，让我认识到自己在学习上的诸多不足。

从刚拿到题目到完成整个编程，从理论到实践，虽然学到很多的的东西，但是也因为自己知识的不足，不能考虑周全，完全成功的完成此次课程设计。

在认识自己的不足后，我便开始认真复习书本知识，同时与动手能力强的同学互相交流，让自己学到了很多平时上课过程中学不到的东西。

通过这次课程设计，我深刻的认识到，理论知识需要与实践结合，才能真正领悟所学知识。

同时我发现，我现在的动手能力不强，所以还要继续努力。

同时还要学会独立思考，才能真正的编出属于我自己的程序。

通过这次实习，敦促我将过去学习过的知识进行了温习，知识只有多巩固，才能真正的理解与领悟。

不论这次课程设计是否完全成功，我相信它对我的影响还是很大的。

这会敦促我在下次课程设计中，能更好地完成设计任务。

为自己加油！

四、用户手册

输入两整数，从低位起，每四位用逗号隔开，按从高到低位依次输入，以分号结束此书的输入；

五、运行结果

运行环境：

code:

:

blocks

六、源代码

#include

#include

#include

#include

#include

#include

#include

usingnamespacestd;

//定义一个结构体

structdl_node

{

intx;

dl_node*pre;

dl_node*next;

};

//结点的初始化

voidlist_init（dl_node**h）

{

*h=（dl_node*）malloc（sizeof（dl_node））;

（*h）->x=0;

（*h）->pre=*h;

（*h）->next=*h;

}

//插入一个元素，循环双向链表

voidlist_insert（dl_node*h,intx）

{

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;

}

//打印输出

voidprin（dl_node*h）

{

//cout<x<

dl_node*p;

p=h->next;

if（p==h）//如果头结点为空，则直接输出0

{

puts（"0"）;return;

}

cout<x;

p=p->next;

while（p!

=h）//循环双向链表一直往右找，直到找到头结点为止

{

printf（",%04d",p->x）;//%04d为对齐方式，当一个结点值不足4位则补齐

p=p->next;

}

//cout<x;

puts（""）;

}

//元素值相加，已处理好h1比h2的长度大于等于h1的长度

//最后结果保存在h1（即长串中）

voidlist_add（dl_node*h1,dl_node*h2）

{

dl_node*p=h1->pre,*q=h2->pre;

inte=0;

while（q!

=h2）//每次相加，如果有进位则保存到e变量中

{

inttmp=p->x+q->x+e;

if（tmp>9999）

{

p->x=tmp%10000;

e=tmp/10000;

}

else

p->x=tmp;

p=p->pre;

q=q->pre;

}

//p=p->pre;

//当h1长度大于h2的时候，还要对未相加的部分进行操作

while（p!

=h1）

{

inttmp=p->x+e;

if（tmp>9999）

{

p->x=tmp%10000;

e=tmp/10000;

}

elsep->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;

}

}

//元素值相减方法同相加类似

//最后结果保存在h1（即长串中）

voidlist_sub（dl_node*h1,dl_node*h2）

{

dl_node*p=h1->pre,*q=h2->pre;

//此处flag的值即位借位的值，借位的值为0或者为1，因为减0无关紧要

intflag=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=q->pre;

}

//p=p->pre;

//cout<x<

//同样的，如果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<x<

//如果最高位为0的话，那么就要删除最高位的结点了

p=h1->next;

while（p->x==0）

{

p->pre->next=p->next;

p->next->pre=p->pre;

p=h1->next;

}

}

intmain（）

{

//freopen（"大数求和.txt","r",stdin）;

while

（1）

{

puts（""）;

charc;

inta;

dl_node*h1,*h2;

list_init（&h1）;

//输入元素，直到读入";"则停止输入第一个链表值

while

（1）

{

//cout<<"asdfa";

scanf（"%d%c",&a,&c）;

//cout<

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）;

intr=0;

//相同方法输入第二个链表，碰到";"则停止，并且读到文件结束

while

（1）

{

if（scanf（"%d%c",&a,&c）==EOF）{r=1;break;}

list_insert（h2,a）;

if（c==';'）break;

}

//cout<

//如果第一个元素小于0，则取正值，并在头结点当中保存信息

if（h2->next->x<0）

{

h2->x=-h2->x;

h2->next->x=-h2->next->x;

}

//h1_num和h2_num分别表示长度

inth1_num=h1->x,h2_num=h2->x;

//把长的放到h1里面，是为了后面的加减操作更顺利

if（abs（h1_num）

{

dl_node*tmp=h1;

h1=h2;

h2=tmp;

h1_num=h1->x,h2_num=h2->x;

}

//cout<

/*

此处为重点部分，分为两个部分，如果h1大于h2四种情况

如果h1等于h2也有四种情况

*/

//其实在此处，可以缩减为6种情况，但为了方便，写了8种

//如果他们的长度不相等，即h1大于h2了

if（abs（h1_num）!

=abs（h2_num））

{

//如果都为正数

if（h1_num>0&&h2_num>0）

{

//prin（h1）;

list_add（h1,h2）;

prin（h1）;

continue;

}

//如果都为负数

elseif（h1_num<0&&h2_num<0）

{

list_add（h1,h2）;

cout<<"-";

prin（h1）;

continue;

}

//如果h1为正而h2为负

elseif（h1_num>0&&h2_num<0）

{

list_sub（h1,h2）;

prin（h1）;

continue;

}

//如果h1为负而h2为正

elseif（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;

}

//如果都为负数

elseif（h1_num<0&&h2_num<0）

{

list_add（h1,h2）;

cout<<"-";

prin（h1）;

continue;

}

//如果h1为正而h2为负

elseif（h1_num>0&&h2_num<0）

{

//这种情况，如果h1最高结点元素大于h2的最高元素，那么交换链表

if（h1->next->xnext->x）

{

dl_node*tmp=h1;

h1=h2;

h2=tmp;

//h1_num=h1->x,h2_num=h2->x;

//prin（h1）;

//prin（h2）;

//这种情况得先输出一个负号

cout<<"-";

}

//交换之后加法还是一样

list_sub（h1,h2）;

prin（h1）;

continue;

}

//如果h1为负而h2为正

elseif（h1_num<0&&h2_num>0）

{

if（h1->next->xnext->x）

{

dl_node*tmp=h1;

h1=h2;

h2=tmp;

//cout<<"-";

}

//否则为负值，要输出负号

elsecout<<"-";

list_sub（h1,h2）;

prin（h1）;

}

}

//puts（""）;

//r的值为1，说明读到了文件结束，整个循环结束

if（r==1）break;

}

return0;

}