长整数的运算算法与数据结构课程设计报告书

1、*实践教学*兰州理工大学软件学院2013年春季学期算法与数据结构课程设计题目：长整数的运算专业班级：软件二班姓名：齐祥荣学号：12700244指导教师：王 连 相成绩：目录摘要1前言2正文31.采用类 C 语言定义相关的数据类型32.各模块的伪码算法33.函数的调用关系图74.调试分析85.测试结果86.源程序（带注释） . 9总结 . 19参考文献20致谢21附件部分源程序代码22摘要数据结构该设计要求学生设计程序，实现两个任意长的整数求和及差的运算问题。通过该题目的设计过程，可以加深理解线性表的逻辑结构、存储结构，掌握线性表上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学

2、会如何把学到的知识用于解决实际问题，培养学生的动手能力关键词：双循环链表；插入；删除；长整数加减前言利用双向循环链表来实现对长整数的存储。每个节点只存储四位十进制数字，即不超过 9999 的非负整数。双向链表有头指针， 它的 data 值存储长整数的符号，1 为正， -1 为负， 0 代表长整数为 0 ；它的 over 值存储除头节点外节点的个数。其他节点的 data 值存储四位整数， over 存储该四位整数溢出09999范围的情况，一般 over>0 表示四位数超出 9999 ，over<0 表示四位数小于0 。选择该数据结构来完成长整数的加减运算是因为要对长整数进行运算，需要

3、对长整数进行存储，所以选择用链表对长整数存储，又由于存储的顺序是从左到右，而运算的顺序则是从右到左，这样位了操作方便选择循环链表，在运算过程中有进位和借位的操作，所以最终选择双向循环链表的数据结构。正文1. 采用类 c 语言定义相关的数据类型typedef struct DoubleNode /定义链表元素void InitNode(DLNode *head) /初始化链表int InsertNode(DLNode *head,int n,DataType x) /向链表第N 个位置插入元素Xint digit(int n) /判断整数N 有几位void PrintNode(DLNode *h

4、ead) /打印链表void DestroyNode(DLNode *head)/销毁链表void add(DLNode *h1,DLNode *h2) /两数相加void jian(DLNode *h1,DLNode *h2) /两数相减int main() /入口函数2. 各模块的伪码算法1. 宏定义及链表定义 ：#define N 100typedef int DataType;typedef struct DoubleNode /定义链表元素 DataType data;struct DoubleNode *prior;struct DoubleNode *next; DLNode;v

5、oid 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(" 插

6、入位置错误 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->ne

7、xt) /处理链表元素 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-&

8、gt;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->d

9、ata-=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(

10、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. 函数的调用关系图开始主函数建立运算建立链表调 运voidadd(DLNode调运void*h

11、1,DLNode *h2)InitNode(DLNode *h1)主函数结 束4. 调试分析a、调试中遇到的问题及对问题的解决方法调试过程中的困难：在数据的运算中，应为是根据数的大小来选择运算的，所以过程相对比较繁琐。而且对于双向链表的两个指针的定位以及链表的插入和删除等操作花费的较多的时间。在这查阅参照了大量的网络资料。b 、算法的时间复杂度和空间复杂度由于链表采用双向循环链表结构，可以从链表两头操作，各种操作的算法时间复杂度比较合理，各函数以及确定链表中的结点位置都是O （n ）,n 为链表长度。5. 测试结果a、输入 0 和 0 做加法运算，输出“ 0 ”，结果如下图：b 、输入 234

12、5 ，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<stdio.h>#include<string.h>#include<stdl

13、ib.h>#include<math.h>#define N 100typedef 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=*h

14、ead;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->

15、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("0n"); return;printf("%d",

16、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(

17、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-&g

18、t;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->

19、;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 *h2,DLNode *h1) /两数相减 DLNode *p1=h1->prior,*p2=h2->prior;while(p1!=h1&&p2!=h2) /每个链

20、表元素相减 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-

21、>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,*head

22、2;char data1N,data2N;char d110,d210;int i,j,k;int xun;InitNode(&head1);InitNode(&head2);while(1) printf("输入数据： n");scanf("%s %s",data1,data2);InitNode(&head1);InitNode(&head2);i=0;k=0;while(data1i!='') /将数 1 用链表储存for(j=0;j<10;j+)d1j=0;j=0;while(data1i!=

23、''&&data1i!=',')d1j+=data1i+;if(data1i=',')i+;if(data10='-') /处理正负数j=-(int)fabs(atoi(d1);else j=atoi(d1);InsertNode(head1,k+,j);i=0;k=0;while(data2i!='') /将数 2 用链表储存for(j=0;j<10;j+)d2j=0; j=0;while(data2i!=''&&data2i!=',')d2j

24、+=data2i+;if(data2i=',') i+;if(data20='-') /处理正负数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

25、);break;case 2:if(strlen(data1)>strlen(data2) /较长的数作为被减数jian(head1,head2);else jian(head2,head1);break;default:break;DestroyNode(&head1);DestroyNode(&head2); return 0;总结关于实验本身的收获是掌握了双向链表，通过该题目的设计过程，可以加深理解线性表的逻辑结构、存储结构，掌握线性表上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。而实验外的就是更好的利