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

*******************实践教学*******************兰州理工大学软件学院2013年春季学期算法与数据结构课程设计题目：长整数的运算专业班级：软件二班姓名：齐祥荣学号：12700244指导教师：王连相成绩：目录摘要.........................................................................................1前言.........................................................................................2正文.........................................................................................31.采用类C语言定义相关的数据类型.............................................32.各模块的伪码算法...................................................................33.函数的调用关系图...................................................................74.调试分析...............................................................................85.测试结果...............................................................................86.源程序（带注释）...................................................................9总结.................................................................................19参考文献....................................................................................20致谢.......................................................................................21附件Ⅰ部分源程序代码................................................................22摘要数据结构该设计要求学生设计程序，实现两个任意长的整数求和及差的运算问题。通过该题目的设计过程，可以加深理解线性表的逻辑结构、存储结构，掌握线性表上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力关键词：双循环链表；插入；删除；长整数加减前言利用双向循环链表来实现对长整数的存储。每个节点只存储四位十进制数字，即不超过9999的非负整数。双向链表有头指针，它的data值存储长整数的符号，1为正，-1为负，0代表长整数为0；它的over值存储除头节点外节点的个数。其他节点的data值存储四位整数，over存储该四位整数溢出0~~9999范围的情况，一般over0表示四位数超出9999，over0表示四位数小于0。选择该数据结构来完成长整数的加减运算是因为要对长整数进行运算，需要对长整数进行存储，所以选择用链表对长整数存储，又由于存储的顺序是从左到右，而运算的顺序则是从右到左，这样位了操作方便选择循环链表，在运算过程中有进位和借位的操作，所以最终选择双向循环链表的数据结构。正文1.采用类c语言定义相关的数据类型typedefstructDoubleNode//定义链表元素voidInitNode(DLNode**head)//初始化链表intInsertNode(DLNode*head,intn,DataTypex)//向链表第N个位置插入元素Xintdigit(intn)//判断整数N有几位voidPrintNode(DLNode*head)//打印链表voidDestroyNode(DLNode**head)//销毁链表voidadd(DLNode*h1,DLNode*h2)//两数相加voidjian(DLNode*h1,DLNode*h2)//两数相减intmain()//入口函数2.各模块的伪码算法1.宏定义及链表定义：#defineN100typedefintDataType;typedefstructDoubleNode//定义链表元素{DataTypedata;structDoubleNode*prior;structDoubleNode*next;}DLNode;voidInitNode(DLNode**head)//初始化链表{每个节点只存储四位十进制数字，即不超过9999的非负整数。双向链表有头指针，它的data值存储长整数的符号，1为正，-1为负，0代表长整数为0；2.插入函数设计思路：intInsertNode(DLNode*head,intn,DataTypex)//向链表第N个位置插入元素X{DLNode*p,*nt;inti=0;p=head-next;while(p!=head&&in){p=p-next;i++;}if(i!=n){printf(插入位置错误\n);return0;}3.加法函数设计思路：先将各位做加减，然后根据所得长整数正负和各结点data值进位或退位计算所得长整数的值并输出。voidadd(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-data0)//处理负数{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.减法函数设计思路：voidjian(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-data0)//处理负数{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.函数的调用关系图开始主函数调运voidadd(DLNode*h1,DLNode*h2)建立链表主函数结束束])调运voidInitNode(DLNode*h1)建立运算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.源程序（带注释）#includestdio.h#includestring.h#includestdlib.h#includemath.h#defineN100typedefintDataType;typedefstructDoubleNode//定义链表元素{DataTypedata;structDoubleNode*prior;structDoubleNode*next;}DLNode;voidInitNode(DLNode**head)//初始化链表{if((*head=(DLNode*)malloc(sizeof(DLNode)))==NULL)exit(1);(*head)-prior=*head;(*head)-next=*head;}intInsertNode(DLNode*head,intn,DataTypex)//向链表第N个位置插入元素X{DLNode*p,*nt;inti=0;p=head-next;while(p!=head&&in){p=p-next;i++;}if(i!=n){printf(插入位置错误\n);return0;}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;return1;}intdigit(intn)//判断整数N有几位{inti;for(i=1;;n/=10,i++){if(n/10==0)returni;}}voidPrintNode(DLNode*head)//打印链表{DLNode*p=head-next;inti;while(p-data==0)//去掉前面的一串0{p=p-next;if(p==head){printf(0\n);return;}}printf(%d,p-data);//最前面的一个数进行特殊处理,不用补零p=p-n