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

.

一、需求分析
【问题描述】
设计一个程序实现两个任意长的整数求和运算。

【基本要求】
利用双向循环链表实现长整数的存储，每个结点含一个整型变量。
任何整型变量的范围是：-（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）函数接口规格说明：

结构体：
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. 详细设计
（1）输入两个数，用链表来存储。链表的头结点的数据的值为1时，表示的是输入的数非负；为-1时表示输入的数是负数。
（2）在创建链表时，让高位在链表的尾部，低位在链表的头部。
（3）在做加法时，先判断两个数的符号是否相同，如果相同，在根据加数的符号，决定和数的符号，取两个数的绝对值做加法，但是的处理进位。
（4）如果异号，用一函数来判断和的符号，判断异号的两个数相加和的符号，当两个数的长度不相等时，取较长数的符号作为和的符号，否则比两个数的大小，再决定和的符号。
（5）异号的两个数想加时，先去两个数的绝对值，用较大的数减去较小的数，差作为和的绝对值。如果相应的位够减时，直接做减法，否则借位，但是要注意被借位的值是否为零，如果为零，则继续借位。
（6）输出最终结果，输出数时，要去掉大数最前面的零，直到数的首位不是零时为止。在输出地位的数时，有可能某些单元的数低于四位，必须要在四位数的高位补零，即四位一个单元输出。空缺处用零补齐。

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

（2）经验和体会：
通过这次学习，让我认识到自己在学习上的诸多不足。从刚拿到题目到完成整个编程，从理论到实践，虽然学到很多的的东西，但是也因为自己知识的不足，不能考虑周全，完全成功的完成此次课程设计。在认识自己的不足后，我便开始认真复习书本知识，同时与动手能力强的同学互相交流，让自己学到了很多平时上课过程中学不到的东西。
通过这次课程设计，我深刻的认识到，理论知识需要与实践结合，才能真正领悟所学知识。同时我发现，我现在的动手能力不强，所以还要继续努力。同时还要学会独立思考，才能真正的编出属于我自己的程序。
通过这次实习，敦促我将过去学习过的知识进行了温习，知识只有多巩固，才能真正的理解与领悟。
不论这次课程设计是否完全成功，我相信它对我的影响还是很大的。这会敦促我在下次课程设计中，能更好地完成设计任务。为自己加油！

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

五、运行结果

运行环境：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_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->pre->next=s;
s->next=h;
h->pre=s;
}

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

//元素值相加，已处理好h1比h2的长度大于等于h1的长度
//最后结果保存在h1（即长串中）
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;
}
else
p->x=tmp;
p=p->pre;
q=q->pre;
}
//p=p->pre;

//当h1长度大于h2的时候，还要对未相加的部分进行操作
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;
}
}

//元素值相减 方法同相加类似
//最后结果保存在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;
}
else
{
p->x=p->x+10000-q->x-flag;
//p->pre->x--;
flag=1;
}
p=p->pre;
q=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->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("%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)
{
if(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;

//把长的放到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四种情况
如果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;
}
//如果都为负数
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<<"-";
prin(h1);
continue;
}
//如果h1为正而h2为负
else if(h1_num>0&&h2_num<0)
{
//这种情况，如果h1最高结点元素大于h2的最高元素，那么交换链表
if(h1->next->x<h2->next->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为正
else if(h1_num<0&&h2_num>0)
{
if(h1->next->x<h2->next->x)
{
dl_node *tmp=h1;
h1=h2;
h2=tmp;
//cout<<"-";
}
//否则为负值，要输出负号
else cout<<"-";
list_sub(h1,h2);
prin(h1);
}
}
//puts("");
//r的值 为1，说明读到了文件结束，整个循环结束
if(r==1) break;
}
return 0;
}

精选范本