长整数运算课设设计说明书.doc

*******************
实践教学
*******************

兰州理工大学

计算机与通信学院

2011年春季学期

算法与数据结构 课程设计

题 目： 长整数的运算
专业班级：09级计算机科学与技术3班
姓 名： 车 吉 良
学 号： 09240323
指导教师： 张 永
成 绩：

目 录
摘 要 1
前 言 2
正 文 3
1. 采用类c语言定义相关的数据类型 3
2. 各模块的伪码算法 3
3. 函数的调用关系图 6
4. 调试分析 7
5. 测试结果 7
6. 源程序（带注释） 8
总 结 15
参考文献 16
致 谢 17
附件Ⅰ 部分源程序代码 18

摘 要
数据结构
该设计要求学生设计程序，实现两个任意长的整数求和及差的运算问题。通过该题目的设计过程，可以加深理解线性表的逻辑结构、存储结构，掌握线性表上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力

关键词：双循环链表；插入；删除；长整数加减

18

前 言
利用双向循环链表来实现对长整数的存储。每个节点只存储四位十进制数字，即不超过9999的非负整数。双向链表有头指针，它的data值存储长整数的符号，1为正，-1为负，0代表长整数为0；它的over值存储除头节点外节点的个数。其他节点的data值存储四位整数，over存储该四位整数溢出0~~9999范围的情况，一般over>0表示四位数超出9999，over<0表示四位数小于0。
选择该数据结构来完成长整数的加减运算是因为要对长整数进行运算，需要对长整数进行存储，所以选择用链表对长整数存储，又由于存储的顺序是从左到右，而运算的顺序则是从右到左，这样位了操作方便选择循环链表，在运算过程中有进位和借位的操作，所以最终选择双向循环链表的数据结构。

正 文
1. 采用类c语言定义相关的数据类型
typedef struct DoubleNode //定义链表元素
void InitNode(DLNode **head) //初始化链表
int InsertNode(DLNode *head,int n,DataType x) //向链表第N个位置插入元素X
int digit(int n) //判断整数N有几位
void PrintNode(DLNode *head) //打印链表
void DestroyNode(DLNode **head)//销毁链表
void add(DLNode *h1,DLNode *h2) //两数相加
void jian(DLNode *h1,DLNode *h2) //两数相减
int main() //入口函数
2. 各模块的伪码算法
1.宏定义及链表定义：
#define N 100
typedef int DataType;
typedef struct DoubleNode //定义链表元素
{ DataType data;
struct DoubleNode *prior;
struct DoubleNode *next; }DLNode;
void InitNode(DLNode **head) //初始化链表
{
每个节点只存储四位十进制数字，即不超过9999的非负整数。双向链表有头指针，它的data值存储长整数的符号，1为正，-1为负，0代表长整数为0；
2.插入函数设计思路：
int InsertNode(DLNode *head,int n,DataType x) //向链表第N个位置插入元素X
{ DLNode *p,*nt;
int i=0;
p=head->next;
while(p!=head&&i<n)
{
p=p->next; i++;
}
if(i!=n)
{
printf("插入位置错误\n");
return 0;
}

3.加法函数设计思路：
先将各位做加减，然后根据所得长整数正负和各结点data值进位或退位计算所得长整数的值并输出。
void add(DLNode *h1,DLNode *h2) //两数相加
{ DLNode *p1=h1->prior,*p2=h2->prior;
while(p1!=h1&&p2!=h2) //每个链表元素相加
{ p1->data+=p2->data ;
p1=p1->prior; p2=p2->prior; }
p1=h1->prior;
while(p1!=h1->next) //处理链表元素
{ if(p1->data>=10000)
{ p1->prior->data+=p1->data/10000;
p1->data%=10000; } if(p1->data<0) //处理负数
{ if(h1->next!=0)
{ p1->prior->data-=1;
p1->data+=10000; }
} p1=p1->prior; }
if(h1->next->data>=10000) //处理最前面的数
{ InsertNode(h1,0,h1->next->data/10000);
h1->next->next->data%=10000; }
if(h1->data<=-10000)
{ InsertNode(h1,0,h1->next->data/10000);
h1->next->next->data%=-10000; }
PrintNode(h1); }
4.减法函数设计思路：
void jian(DLNode *h1,DLNode *h2) //两数相减
{ DLNode *p1=h1->prior,*p2=h2->prior;
while(p1!=h1&&p2!=h2) //每个链表元素相减
{ p1->data-=p2->data ;
p1=p1->prior;
p2=p2->prior; }
p1=h1->prior;
while(p1!=h1->next) //处理链表元素
{ if(p1->data>=10000)
{ p1->prior->data+=p1->data/10000;
p1->data%=10000; }
if(p1->data<0) //处理负数
{ if(h1->next!=0)
{ p1->prior->data-=1;
p1->data+=10000; }
} p1=p1->prior; }
if(h1->next->data>=10000) //处理最前面的数
{ InsertNode(h1,0,h1->next->data/10000);
h1->next->next->data%=10000; }
if(h1->data<=-10000)
{ InsertNode(h1,0,h1->next->data/-10000);
h1->next->next->data%=-10000; }
PrintNode(h1); }
3. 函数的调用关系图

开始
主函数

调运void add(DLNode *h1,DLNode *h2)
建立链表

主函数
结束束])
调运void InitNode(DLNode
建立运算

4. 调试分析
a、 调试中遇到的问题及对问题的解决方法
调试过程中的困难：
在数据的运算中，应为是根据数的大小来选择运算的，所以过程相对比较繁琐。而且对于双向链表的两个指针的定位以及链表的插入和删除等操作花费的较多的时间。在这查阅参照了大量的网络资料。

b、算法的时间复杂度和空间复杂度
由于链表采用双向循环链表结构，可以从链表两头操作，各种操作的算法时间复杂度比较合理，各函数以及确定链表中的结点位置都是O（n）,n为链表长度。

5. 测试结果
a、 输入0和0做加法运算，输出“0”，结果如下图：

b、 输入2345，6789和-7654，3211做减法运算，输出“1，0000，0000”，结果如下图：

c、 输入1，0000，0000，0000和9999，9999做减法运算，输出“9999，0000，0001”，结果如下图：

d、 输入1，0001，0001和1，0001，0001做减法运算，输出“0”，结果如下图：

e、 输入1,2345,6789 和9,8765,4321做加法运算，结果如下图：

6. 源程序（带注释）
#include <stdafx.h>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define N 100
typedef int DataType;
typedef struct DoubleNode //定义链表元素
{ DataType data;
struct DoubleNode *prior;
struct DoubleNode *next; }DLNode;
void InitNode(DLNode **head) //初始化链表
{
if((*head=(DLNode*)malloc(sizeof(DLNode)))==NULL)
exit(1);
(*head)->prior=*head;
(*head)->next=*head;
}
int InsertNode(DLNode *head,int n,DataType x) //向链表第N个位置插入元素X
{ DLNode *p,*nt;
int i=0;
p=head->next;
while(p!=head&&i<n)
{
p=p->next; i++;
}
if(i!=n)
{
printf("插入位置错误\n");
return 0;
}
if((nt=(DLNode *)malloc(sizeof(DLNode)))==NULL)
exit(1);
nt->data=x;
nt->prior=p->prior;
nt->prior->next=nt;
nt->next=p;
p->prior=nt;
return 1;
}
int digit(int n) //判断整数N有几位
{
int i;
for(i=1;;n/=10,i++)
{
if(n/10==0)
return i;
}
}
void PrintNode(DLNode *head) //打印链表
{ DLNode *p=head->next;
int i;
while(p->data==0) //去掉前面的一串0
{ p=p->next;
if(p==head)
{ printf("0\n");
return;
}
}
printf("%d",p->data); //最前面的一个数进行特殊处理,不用补零
p=p->next;
while(p!=head) //打印后面的数字
{ printf(",");
if(p->data==0)
{
printf("0000");
p=p->next;
continue;
}
for(i=0;i<4-digit(p->data);i++) //补零
printf("0");
printf("%d",p->data);
p=p->next;
}
printf("\n");
}
void DestroyNode(DLNode **head)
{ DLNode *p,*p1;
p=(*head)->next;
while(p!=*head)
{ p1=p;
p=p->next;
free(p1);
}
free(p);
head=NULL;
}
void add(DLNode *h1,DLNode *h2) //两数相加
{ DLNode *p1=h1->prior,*p2=h2->prior;
while(p1!=h1&&p2!=h2) //每个链表元素相加
{ p1->data+=p2->data ;
p1=p1->prior; p2=p2->prior; }
p1=h1->prior;
while(p1!=h1->next) //处理链表元素
{ if(p1->data>=10000)
{ p1->prior->data+=p1->data/10000;
p1->data%=10000; } if(p1->data<0) //处理负数
{ if(h1->next!=0)
{ p1->prior->data-=1;
p1->data+=10000; }
} p1=p1->prior; }
if(h1->next->data>=10000) //处理最前面的数
{ InsertNode(h1,0,h1->next->data/10000);
h1->next->next->data%=10000; }
if(h1->data<=-10000)
{ InsertNode(h1,0,h1->next->data/10000);
h1->next->next->data%=-10000; }
PrintNode(h1); }
void jian(DLNode *h1,DLNode *h2) //两数相减
{ DLNode *p1=h1->prior,*p2=h2->prior;
while(p1!=h1&&p2!=h2) //每个链表元素相减
{ p1->data-=p2->data ;
p1=p1->prior;
p2=p2->prior; }
p1=h1->prior;
while(p1!=h1->next) //处理链表元素
{ if(p1->data>=10000)
{ p1->prior->data+=p1->data/10000;
p1->data%=10000; }
if(p1->data<0) //处理负数
{ if(h1->next!=0)
{ p1->prior->data-=1;
p1->data+=10000; }
} p1=p1->prior; }
if(h1->next->data>=10000) //处理最前面的数
{ InsertNode(h1,0,h1->next->data/10000);
h1->next->next->data%=10000; }
if(h1->data<=-10000)
{ InsertNode(h1,0,h1->next->data/-10000);
h1->next->next->data%=-10000; }
PrintNode(h1); }
int main() //入口函数
{
DLNode *head1,*head2;
InitNode(&head1);
InitNode(&head2);
char data1[N],data2[N];
char d1[10],d2[10];
int i,j,k;
int xun;
while(1)
{ printf("输入数据：\n");
scanf("%s %s",data1,data2);
InitNode(&head1);
InitNode(&head2);
i=0;k=0;
while(data1[i]!=';') //将数1用链表储存
{
for(j=0;j<10;j++)
d1[j]=0;
j=0;
while(data1[i]!=';'&&data1[i]!=',')
d1[j++]=data1[i++];
if(data1[i]==',')
i++;
if(data1[0]=='-') //处理正负数
j=-(int)fabs(atoi(d1));
else j=atoi(d1);
InsertNode(head1,k++,j);
}
i=0;
k=0;
while(data2[i]!=';') //将数2用链表储存
{
for(j=0;j<10;j++)
d2[j]=0; j=0;
while(data2[i]!=';'&&data2[i]!=',')
d2[j++]=data2[i++];
if(data2[i]==',') i++;
if(data2[0]=='-') //处理正负数
j=-(int)fabs(atoi(d2));
else j=atoi(d2);
InsertNode(head2,k++,j); }
printf("选择加减法：1—加法，2-减法\n");
scanf("%d",&xun);
switch(xun)
{
case 1:if(strlen(data1)>strlen(data2)) //较长的数作为被加数
add(head1,head2);
else add(head2,head1);
break;
case 2:if(strlen(data1)>strlen(data2)) //较长的数作为被减数
jian(head1,head2);
else jian(head2,head1);
break;
default:break;
}
DestroyNode(&head1);
DestroyNode(&head2); }
return 0;
}

总 结
关于实验本身的收获是掌握了双向链表，通过该题目的设计过程，可以加深理解线性表的逻辑结构、存储结构，掌握线性表上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。而实验外的就是更好的利用了网路资源，通过网络的搜索引擎等。加深了自己在这方面知识的补充。并且在于同学交流中分析了彼此算法的优劣程度。我觉得这是本次实验最大的收获。

参考文献
1 严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学出版社.
2 严蔚敏，吴伟民.《数据结构题集（C语言版）》.清华大学出版社.
3 《DATA STRUCTURE WITH C++》. William Ford,William Topp .清华大学出版社（影印版）.
4 谭浩强.《c语言程序设计》. 清华大学出版社.
5．数据结构与算法分析（Java版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 张铭,刘晓丹译 电子工业出版社 2001 年1月

致 谢
首先，我要感谢我的《算法与数据结构》及课程设计老师张永老师，谢谢张老师对我的谆谆教导，让我懂得了《算法与数据结构》的理论知识，为我做课程设计奠定了理论基础。另外，感谢张老师在我做课程设计的过程中给我提出的宝贵意见和建议，我根据张老师的建议对我的程序进行了改进，从而使程序更加完善。最后我还要感谢，在课设的这几周给我帮助的同学们，谢谢他们给我鼓励和支持。
附件Ⅰ 部分源程序代码
定义链表;
typedef int DataType;
typedef struct DoubleNode //定义链表元素
{ DataType data;
struct DoubleNode *prior;
struct DoubleNode *next; }DLNode;
void InitNode(DLNode **head) //初始化链表
{

循环结构：
while(p!=head&&i<n)
{
p=p->next; i++;
}
if(i!=n)
{
printf("插入位置错误\n");
return 0;
}