数据结构课程设计长整数运算

.,.一、需求分析【问题描述】设计一个程序实现两个任意长的整数求和运算。【基本要求】利用双向循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是：-（215-1）~（215-1）。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。【测试数据】（1）0；0；应输出“0”。（2）–2345，6789；-7654，3211；应输出“-1，0000，0000”。（3）–9999，9999；1，0000，0000，0000；应输出“9999，0000，0001”。（4）1，0001，0001；-1，0001，0001；应输出“0”。（5）1，0001，0001；-1，0001，0000；应输出“1”。二、设计1.设计思想（1）存储结构：循环双向链表（2）主要算法基本思想：1、每个结点中可以存放的最大整数为215-1=32767，才能保证两数相加不会溢出。但若这样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。故可以在每个结点中仅存十进制数4位，即不超过9999的非负整数，整个链表视为万进制数。2、可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。2.设计表示（1）函数调用关系图：（2）函数接口规格说明：结构体：structdl_node{intx;dl_node*pre;dl_node*next;};.,.初始化：voidlist_init(dl_node**h)插入元素：voidlist_insert(dl_node*h,intx)输出链表：voidprin(dl_node*h)实现相加：voidlist_add(dl_node*h1,dl_node*h2)实现相减：voidlist_sub(dl_node*h1,dl_node*h2)3.详细设计（1）输入两个数，用链表来存储。链表的头结点的数据的值为1时，表示的是输入的数非负；为-1时表示输入的数是负数。（2）在创建链表时，让高位在链表的尾部，低位在链表的头部。（3）在做加法时，先判断两个数的符号是否相同，如果相同，在根据加数的符号，决定和数的符号，取两个数的绝对值做加法，但是的处理进位。（4）如果异号，用一函数来判断和的符号，判断异号的两个数相加和的符号，当两个数的长度不相等时，取较长数的符号作为和的符号，否则比两个数的大小，再决定和的符号。（5）异号的两个数想加时，先去两个数的绝对值，用较大的数减去较小的数，差作为和的绝对值。如果相应的位够减时，直接做减法，否则借位，但是要注意被借位的值是否为零，如果为零，则继续借位。（6）输出最终结果，输出数时，要去掉大数最前面的零，直到数的首位不是零时为止。在输出地位的数时，有可能某些单元的数低于四位，必须要在四位数的高位补零，即四位一个单元输出。空缺处用零补齐。三、调试分析（1）经过不断的的DEBUG，不断的输出看结果调试，最终成功（2）经验和体会：通过这次学习，让我认识到自己在学习上的诸多不足。从刚拿到题目到完成整个编程，从理论到实践，虽然学到很多的的东西，但是也因为自己知识的不足，不能考虑周全，完全成功的完成此次课程设计。在认识自己的不足后，我便开始认真复习书本知识，同时与动手能力强的同学互相交流，让自己学到了很多平时.,.上课过程中学不到的东西。通过这次课程设计，我深刻的认识到，理论知识需要与实践结合，才能真正领悟所学知识。同时我发现，我现在的动手能力不强，所以还要继续努力。同时还要学会独立思考，才能真正的编出属于我自己的程序。通过这次实习，敦促我将过去学习过的知识进行了温习，知识只有多巩固，才能真正的理解与领悟。不论这次课程设计是否完全成功，我相信它对我的影响还是很大的。这会敦促我在下次课程设计中，能更好地完成设计任务。为自己加油！四、用户手册输入两整数，从低位起，每四位用逗号隔开，按从高到低位依次输入，以分号结束此书的输入；五、运行结果运行环境：code::blocks.,..,..,.六、源代码#includecstdio#includecstring#includestring#includemalloc.h#includeiostream#includecstdlib#includecmathusingnamespacestd;//定义一个结构体structdl_node{intx;dl_node*pre;dl_node*next;};//结点的初始化voidlist_init(dl_node**h){*h=(dl_node*)malloc(sizeof(dl_node));(*h)-x=0;(*h)-pre=*h;(*h)-next=*h;}//插入一个元素，循环双向链表voidlist_insert(dl_node*h,intx){h-x++;dl_node*s;s=(dl_node*)malloc(sizeof(dl_node));s-x=x;s-pre=h-pre;h-pre-next=s;s-next=h;h-pre=s;}.,.//打印输出voidprin(dl_node*h){//couth-xendl;dl_node*p;p=h-next;if(p==h)//如果头结点为空，则直接输出0{puts(0);return;}coutp-x;p=p-next;while(p!=h)//循环双向链表一直往右找，直到找到头结点为止{printf(,%04d,p-x);//%04d为对齐方式，当一个结点值不足4位则补齐p=p-next;}//coutp-x;puts();}//元素值相加，已处理好h1比h2的长度大于等于h1的长度//最后结果保存在h1（即长串中）voidlist_add(dl_node*h1,dl_node*h2){dl_node*p=h1-pre,*q=h2-pre;inte=0;while(q!=h2)//每次相加，如果有进位则保存到e变量中{inttmp=p-x+q-x+e;if(tmp9999){p-x=tmp%10000;e=tmp/10000;}elsep-x=tmp;p=p-pre;q=q-pre;}//p=p-pre;.,.//当h1长度大于h2的时候，还要对未相加的部分进行操作while(p!=h1){inttmp=p-x+e;if(tmp9999){p-x=tmp%10000;e=tmp/10000;}elsep-x=tmp;p=p-pre;}p=h1-next;//如果最高位得到的结果还有进位，那么就要再创建一个结点if(e!=0){dl_node*s;s=(dl_node*)malloc(sizeof(dl_node));s-x=e;s-pre=p-pre;p-pre-next=s;s-next=p;p-pre=s;}}//元素值相减方法同相加类似//最后结果保存在h1（即长串中）voidlist_sub(dl_node*h1,dl_node*h2){dl_node*p=h1-pre,*q=h2-pre;//此处flag的值即位借位的值，借位的值为0或者为1，因为减0无关紧要intflag=0;while(q!=h2){if(p-x-flag=q-x){p-x-=q-x+flag;flag=0;}.,.else{p-x=p-x+10000-q-x-flag;//p-pre-x--;flag=1;}p=p-pre;q=q-pre;}//p=p-pre;//coutp-xendl;//同样的，如果h1的长度大于h2的长度，那么对剩下的操作while(p!=h1){if(p-x-flag0){p-x=p-x+10000-flag;flag=1;}else{p-x=p-x-flag;flag=0;}p=p-pre;}//coutp-xendl;//如果最高位为0的话，那么就要删除最高位的结点了p=h1-next;while(p-x==0){p-pre-next=p-next;p-next-pre=p-pre;p=h1-next;}}intmain(){//freopen(大数求和.txt,r,stdin);while(1){puts();charc;inta;.,.dl_node*h1,*h2;list_init(&h1);//输入元素，直到读入;则停止输入第一个链表值while(1){//coutasdfa;scanf(%d%c,&a,&c);//coutcendl;list_insert(h1,a);if(c==';')break;}//如果第一个元素小于0，则取正值，并在头结点当中保存信息if(h1-next-x0){h1-x=-h1-x;h1-next-x=-h1-next-x;}//prin(h1);list_init(&h2);intr=0;//相同方法输入第二个链表，碰到;则停止，并且读到文件结束while(1){if(scanf(%d%c,&a,&c)==EOF){r=1;break;}list_insert(h2,a);if(c==';')break;}//coutrendl;//如果第一个元素小于0，则取正值，并在头结点当中保存信息if(h2-next-x0){h2-x=-h2-x;h2-next-x=-h2-next-x;}//h1_num和h2_num分别表示长度inth1_num=h1-x,h2_num=h2-x;//把长的放到h1里面，是为了后面的加减操作更顺利if(abs(h1_num)abs(h2_num)){dl_node*tmp=h1;h1=h2;h2=tmp;.,.h1_num=h1-x,h2_num=h2-x;}//couth1_numh2_numendl;/*此处为重点部分，分为两个部分，如果h1大于h2四种情况如果h1等于h2也有四种情况*///其实在此处，可以缩减为6种情况，但为了方便，写了8种//如果他们的长度不相等，即h1大于h2了if(abs(h1_num)!=abs(h2_num)){//如果都为正数if(h1_num0&&h2_num0){//prin(h1);list_add(h1,h2);prin(h1);continue;}//如果都为负数elseif(h1_num0&&h2_num0){list_add(h1,h2);cout-;prin(h1);continue;}//如果h1为正而h2为负elseif(h1_num0&&h2_num0){list_sub(h1,h2);prin(h1);continue;}//如果h1为负而h2为正elseif(h1_num0&&h2_num0){.,.cout-;list_sub(h1,h2);prin(h1);}}//否则，如果他们长度都相等的话：else{//如果都为正数if(h1_num0&&h2_num0){list_add(h1,h2);prin(h1);continue;}//如果都为负数elseif(h1_num0&&h2_num0){list_add(h1,h2);cout-;prin(h1);continue;}//如果h1为正而h2为负elseif(h1_num0&&h2_num0){//这种情况，如果h1最高结点元素大于h2的最高元素，那么交换链表if(h1-next-xh2-next-x){dl_node*tmp=h1;h1=h2;h2=tmp;//h1_num=h1-x,h2_num=h2-x