长整数的运算-算法与数据结构课程设计

1、*实践教学* 兰州理工大学 软件学院2013年春季学期 算法与数据结构 课程设计题 目： 长整数的运算 专业班级： 软件二班 姓 名： 齐 祥 荣 学 号： 12700244 指导教师： 王 连 相 成 绩： 目 录 TOC o 1-3 h z HYPERLINK l _Toc297748685 摘 要 PAGEREF _Toc297748685 h 1 HYPERLINK l _Toc297748686 前 言 PAGEREF _Toc297748686 h 2 HYPERLINK l _Toc297748687 正 文 PAGEREF _Toc297748687 h 3 HYPERLINK

2、 l _Toc297748688 1.采用类c语言定义相关的数据类型 PAGEREF _Toc297748688 h 3 HYPERLINK l _Toc297748689 2.各模块的伪码算法 PAGEREF _Toc297748689 h 3 HYPERLINK l _Toc297748690 3.函数的调用关系图 PAGEREF _Toc297748690 h 6 HYPERLINK l _Toc297748691 4.调试分析 PAGEREF _Toc297748691 h 7 HYPERLINK l _Toc297748692 5.测试结果 PAGEREF _Toc297748692

3、 h 7 HYPERLINK l _Toc297748693 6.源程序（带注释） PAGEREF _Toc297748693 h 8 HYPERLINK l _Toc297748694 总 结 PAGEREF _Toc297748694 h 15 HYPERLINK l _Toc297748695 参考文献 PAGEREF _Toc297748695 h 16 HYPERLINK l _Toc297748696 致 谢 PAGEREF _Toc297748696 h 17 HYPERLINK l _Toc297748697 附件 部分源程序代码 PAGEREF _Toc297748697 h

4、 18摘 要数据结构该设计要求学生设计程序，实现两个任意长的整数求和及差的运算问题。通过该题目的设计过程，可以加深理解线性表的逻辑结构、存储结构，掌握线性表上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力关键词：双循环链表；插入；删除；长整数加减前 言利用双向循环链表来实现对长整数的存储。每个节点只存储四位十进制数字，即不超过9999的非负整数。双向链表有头指针，它的data值存储长整数的符号，1为正，-1为负，0代表长整数为0；它的over值存储除头节点外节点的个数。其他节点的data值存储四位整数，over存储该四位整

5、数溢出09999范围的情况，一般over0表示四位数超出9999，overnext; while(p!=head&inext; 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=p

6、2-prior; p1=h1-prior; while(p1!=h1-next) /处理链表元素 if(p1-data=10000) p1-prior-data+=p1-data/10000; p1-data%=10000; if(p1-datanext!=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-datanext-data/10000)

7、; 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%

8、=10000; if(p1-datanext!=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-datanext-data/-10000); h1-next-next-data%=-10000; PrintNode(h1); 函数的调用关系图开始主函数调运void add(DLNode *h1,DLNode *h2)建立链表主函数结束束)调运v

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

10、00”，结果如下图：输入1，0000，0000，0000和9999，9999做减法运算，输出“9999，0000，0001”，结果如下图：输入1，0001，0001和1，0001，0001做减法运算，输出“0”，结果如下图：输入1,2345,6789 和9,8765,4321做加法运算，结果如下图：源程序（带注释）#include #include #include#include #define N 100 typedef int DataType; typedef struct DoubleNode /定义链表元素 DataType data; struct DoubleNode *pri

11、or; 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&inext; i+; if(i!=n)

12、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; whil

13、e(p-data=0) /去掉前面的一串0 p=p-next; if(p=head) printf(0n); 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;idata);i+) /补零 printf(0); printf(%d,p-data); p=p-next; printf(n); void DestroyNode(DLNode *head) D

14、LNode *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

15、-prior-data+=p1-data/10000; p1-data%=10000; if(p1-datanext!=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-datanext-data/10000); h1-next-next-data%=-10000; PrintNode(h1); void jian(DLNode *h2,DLNo

16、de *h1) /两数相减 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-datanext!=0) p1-prior-data-=1; p1-data+=10000; p1=p1-prior; if(h1-

17、next-data=10000) /处理最前面的数 InsertNode(h1,0,h1-next-data/10000); h1-next-next-data%=10000; if(h1-datanext-data/-10000); h1-next-next-data%=-10000; PrintNode(h1); int main() /入口函数 DLNode *head1,*head2; char data1N,data2N; char d110,d210; int i,j,k; int xun; InitNode(&head1); InitNode(&head2); while(1)

18、printf(输入数据：n);scanf(%s %s,data1,data2); InitNode(&head1); InitNode(&head2); i=0;k=0; while(data1i!=;) /将数1用链表储存 for(j=0;j10;j+) d1j=0; j=0; while(data1i!=;&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(d

19、ata2i!=;) /将数2用链表储存 for(j=0;jstrlen(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语言版）.清华大学出版社