任意长的整数加法

《结数据构》课程设计报告任意长的整数加法姓名：专业：班级：学号：指导老师:设计时间：2010年5月7日

摘要1、 本程序实现计算任意长的整数的加法运算.以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就计算并显示出这两个数的运算。2、 本演示程序中，集合的元素限定为数字字符和字符'，与L，，输入字符可■以任意长，输入形式以“回车符”为结束标志，串中字符顺序不限，且允许出现重复字符。3、 利用双向循环链表现实长整数的存储，每个结点含一个整形变量。输入的形式以回车结束，可以直接输入正数或负数。按中国对于长整数的表示习惯，每四位一组，除数字和位于首位置的负号外，其它一切字符都将作为分隔符，连续多个分隔符当一个处理。但不使用分隔符也不影响结果。任意长的整数相加关键字任意长的整数相加关键字双向循环链表目录TOC\o"1-5"\h\z\o"CurrentDocument"1.设计思想 4\o"CurrentDocument"1.1设计内容 4\o"CurrentDocument"1.2向循环链表作存储结构 4\o"CurrentDocument"概要设计（程序模块分析） 5\o"CurrentDocument"21为链表指针申请空间模块 5\o"CurrentDocument"2.2数求和模块 5\o"CurrentDocument"2.3创建链表模块 7\o"CurrentDocument"2.4获取整数模块 7\o"CurrentDocument"2.5输入任意长整数的模块 8\o"CurrentDocument"2.6释放空间模块 9\o"CurrentDocument"2.7主函数（main）设计模块 9\o"CurrentDocument"算法描述（流程图及源代码） 113.1双向循环链表结构程序流程图 113.2代码 12\o"CurrentDocument"4.运行程序及结果 16\o"CurrentDocument"5.心得体会 18绪论数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力，培养科学的软件工作方法。学生通过数据结构课程设计在下述各方面得到锻炼：能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并旦修改。培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平设计思想1.1设计内容【问题描述】设计一个实现任意长的整数进行加法运算的演示程序【基本要求】：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是-(215-1)~(215-l)o输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。【测试数据】0；0；应输出“0”。-2345,6789：-7654,3211；应输出“-1,0000,0000气.9999,9999；1.0000,0000,0000：应输出“9999,0000,0001气1,0001,0001；-1,0001,0001；应输出“。气1,0001,0001；-1,0001,0000；应输出勺气・9999,9999,9999；-9999.9999,9999；应输出“1,9999,9999,9998气1,0000,9999,9999；1；应输出“1,0001,0000,0000”。1-2向循环链表作存储结构为实现上述程序功能，应以双向循环链表表示长整数。为此，需要定义一个抽象数据类型。利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范闱是＜215-1)~(215-1)。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。建立双向循环链表方式。查找函数采用链表的方式进行算法。有创建链表(ImtNode),释放空间(FreeNode),求和(Func_Add),获取数字(Func_GetNum)和输入(printf)等函数组合而成的源程序对求任意长的整数加法进行双向循环链表方式。在进位的问题上，若要进位的话，就从右往左依次进行进位；若不要进行进位的话，就直接相加概要设计（程序模块分析）2.1为链表指针申请空间模块链表申请空间存储实现长整数，并且及时清空，释放占空间的整数，避免浪费存储空间#include"stdio.hH#iiicludeHstring.hHtypedefstmctNode{stiuctNode*pre;charNumbei[5];/Z用来存放4个字符末尾加个0stiuctNode*next;}Node_t;/*为链表指针申请空间*/voidInitNode(Node_t**node){*node=(Node_t*)malloc(sizeof(Node_t));meniset((*node)->Number.OxOO,sizeof((*node)->Number));(*node)->pre=NULL;(*node)->next=NULL;}2.2数求和模块加法函数：先找到链表尾部进行进位加法，把同长度部分搞定然后再长的那条表操作Node_t*Func_Add(Node_t*operatel,Node_t*operate2){Node_t*nodel=operate1;Node_t*node2=operate?;Node_t^Result=NULL.*RetuniNode=NULL.*NewNode;charTempStr[6];hitAdda=0,Addb=O.IiidexA=0,IndexB=0;hitCarry=0;wliile(nodel->next?=NULL)nodel=nodel->next;IndexA++；}wliile(node2->next?=NULL){node2=node2->next;IiidexB++;}if(IiidexA>IndexB)〃得到长的那条链表做为存结果{Result=nodel;}else{Result=node2;}while((uodel!=NULL)&&(node2!=NULL))Adda=atoi(node1->Number);〃字符转整形Addb=atoi(node2->Number);〃字符转整形meniset(TempSti\0x00.6);itoa(Adda+Addb+Carry,TempStr,10);H结果转字符结果可能是进位+4个需要数据或只有4个需要数据if(Adda+Addb+Carry>=l0000){Carry=1;J z}else{Carry=0;}//pimtf(nResult=%s,Cany=%d\nH,TempStf,CaiTy);〃打印信息有帮助memcpy(Result->Numbei;TempStr+Cairy,4)；〃拷值时有进位第一个不拷，没进位就全拷进位己经记住给下一次加RetuniNode=Result;〃备分返回使用Result=Result->pre;nodel=nodel->pre;node2=node2->pre;}wlule(Result)〃如果俩链表不等长Adda=atoi(Result->Number);itoa(Adda+CanyTenipSti;10);if(Adda+Caiiy>=10000)Carry=1;}else{Carry=0;}//pimtf(nResult=%s,Caiiy=%d\n,\TempSti;CaiTy);〃打印信息有帮助memcpy(Result->Numbei;TempStr+Cairy.4)；〃拷值时有进位第一个不拷，相反就全拷RetuniNode=Result;〃备分返回使用if((Result->pre=NULL)&&Cany)2.3创建链表模块创建一个双向循环链表，输入新的数，结果会是这个新的数，按照这样依次下去IiutNode(&NewNode);Result->pre=NewNode;NewNode->next=Result;}Result=Result->pie;}returnRetuniNode;2.4获取整数模块获取字符串，将输入的字符串分给链表单元，开头为最高位，10位数字则为2,4,4voidFunc_GetNum(Node_t*node,char*IiiputSti){Node_t*TempNode=node;Node_t*NewNode=NULL;char*TempStr=InputStr;hitIndex=0,Offset=0:hitStrLen=strlen(InputSti);if(?(StrLen%4)){Offset=4;}else{Offset=StiLen%4;//为最高位计算为数10%4=2}StrLen=StrLen-Offset;wliile(StrLen>0){IiutNode(&NewNode);TempNode->next=NewNode;NewNode->pie=TempNode;TempNode=TempNode->next;memcpy(TempNode->Numbei\TempStr+hidex+Offset,4)；〃4位4位拷的链表里StrLen-=4;Index+=4;}_memcpy(node->Numbei;TenipStr.Offset);〃最高位拷值}2.5输入任意长整数的模块输入任意长的两个整数相加voidPriiitfNode(Node_t*node){Node_t*TempNode=node;piintf(”％s",TempNode・>Number);TempNode=TempNode->next;wliile(TempNode!=NULL){％s”,TempNode->Number);TempNode=TempNode->next;}pmirffW);}2.6释放空间模块释放空间，避免字符串占空间，清楚多余的空间voidFreeNode(Node_t*node){Node_t*TempNode=node,*Temp;wlule(TempNode){Temp=TempNode->next;free(TempNode);TempNode=Temp;}}2.7主函数(main)设计模块该模块功能主要是给用户提供清晰的可操作界面，易于人机操作。并能很好的调用其他各模块，使程序更加优化，思路更加清晰，结构更加明了。提高了程序的实用性。voidmain(){mti=10;charstr[128];Node_t*node1,*node2,*Result;{IiutNode(&node1);IiutNode(&node2);meniset(sti;OxOO,sizeof(sti));gets(str);Func_GetNum(nodeLstr);meniset(sti;OxOO,sizeof(sti));gets(str);Func_GetNum(node2?str);printfCTuncStartW);PrintfNode(node1);prmtf(M+\nH)；PrintfNode(node2);Result=Fimc_Add(nodel,node2);PrintfNode(Result);/*释放由于我将结果保留在加数1或加数2中长的那条链表中如果有进位的话还多申请一个空间存放所以释放的时候就要判断到底是哪条链表*/if(Result=nodel|Result->next==nodel){FieeNode(Result);FieeNode(node2);}if(Result=node2|Result->next==node2){FieeNode(Result);FreeNode(nodel);}}}算法描述（流程图及源代码）3.1双向循环链表结构程序流程退出程序3.2源代码#include"stdio.h"#iiicludeHstring.hHtypedefstmctNode{metNode*pre;arNumber[5];structNode*next;}Node_t;voidInitNode(Node_t**node){ode=(Node_t*)malloc(sizeof(Node_t));inset((*node)->Numbei;OxOO,sizeof((*node)->Number));(*node)->pre=NULL;(*node)->next=NULL;}Node_t*Func_Add(Node_t*operatel,Node_t*operate2){Node_t*nodel=operate1;Node_t*node2=operate?;Node_t^Result=NULL.*RetuniNode=NULL.*NewNode;charTempStr[6];hitAdda=0,Addb=O.IiidexA=0,IndexB=0;hitCarry=0;wliile(nodel->next!=NULL){nodel=nodel->next;IndexA++；}wliile(node2->next?=NULL){node2=node2->next;IndexB++;}if(IiidexA>IndexB)/{Result=nodel;}elseResult=node2;}while((uodel!=NULL)&&(node2!=NULL)){Adda=atoi(node1->Numbei);Addb=atoi(node2->Number);meniset(TempSti\0x00.6);itoa(Adda+Addb+CanyTempSti;10);if(Adda+Addb+Carry>=l0000){Carry=1;J z}else{Carry=0;J z}memcpy(Result->Numbei;TempSti+Cany4)；RetuniNode=Result;Result=Result->pre;nodel=nodel->pre;node2=node2->pre;}while(Result){Adda=atoi(Result->Number);itoa(Adda+CanyTenipSti;10);if(Adda+Cairy>=10000){Carry=1;J z}else{Carry=0;J z}memcpy(Result->Numbei;TempSti+Cany4)；RetuniNode=Result;if((Result->pre=NULL)&&Cany){IiutNode(&NewNode);Result->pre=NewNode;NewNode->next=Result;}Result=Result->pre;}retuinRetuniNode;}voidFunc_GetNum(Node_t*node,char*IiiputSti){Node_t*TempNode=node;Node_t*NewNode=NULL;char*TempStr=InputStr;hitIndex=0,Offset=0:hitStrLen=strlen(IiiputSti);if(?(StrLen%4)){Offset=4;}else{Offset=StrLen%4;}StrLen=StrLen-Offset;while(StrLen>0){IiutNode(&NewNode);TempNode->next=NewNode;NewNode->pie=TempNode;TempNode=TempNode->next;memcpy(TempNode->Numbei;TempStr+Iiidex+Offset,4)；StrLen-=4;Index+=4;}memcpy(node->Numbei;TenipStr.Offset);}voidPriiitfNode(Node_t*node){Node_t*TempNode=node;piintf(”％s",TempNode・>Number);TempNode=TempNode->next;wliile(TempNode!=NULL){％s”,TempNode-^Number);TempNode=TempNode->next;}pnntf(侦')；}voidFreeNode(Node_t*node){Node_t*TempNode=node,*Temp;while(TempNode){Temp=TempNode->next;free(TempNode);TempNode=Temp:}}voidmain(){mti=10;charstr[128];Node_t*node1,*node2,*Result;{IiutNode(&node1);IiutNode(&node2);meniset(sti;OxOO.sizeof(sti));gets(str);Func_GetNum(nodeLstr);meniset(sti;OxOO.sizeof(sti));gets(str);Func_GetNum(node2,sti);pnntfCTuncStart's”)；PrintfNode(node1);pnntf(M+\nH)；PrintfNode(node2);Result=Func_Add(nodel,node2);PrintfNode(Result);if(Result=nodel|Result->next==nodel){FieeNode(Result);FieeNode(node2);}if(Result=node2|Result->next==node2)

FreeNode(Result);FreeNode(nodel);}4.运行程序及结果对程序进行调试，无误后运行该程序，输入两个任意长的整数相加求和,456579123456)23656789FiincStart12.345612345,67891.2358,02451236567899876543210FuncStart1,2345,6789-4-98,7656,321099,9999,99991234987605109864680FuncStart12,3498,76051/986,468013.4485.2285S3C:\Windews\system32\cmde:<e123456789。FuncStart12344-56,912412345678909876542321FuncStart12,3456,789098,7654,2321111,1111,0211123456789098765432112345698765432145678954FuncStart123,4567,8909,8765,4321云3,&569,8765,4321,4567.8954123,4693,3333,3231,3