数据结构综合实验实验指导书.doc

《数据结构综合实验实验指导书.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、温州大学瓯江学院WENZHOUUNIVERSITYOUJIANGCOLLEGE综合实验指导书专业计算机科学与技术课程数据结构综合实验数据结构综合实验实验指导书瓯江学院理工分院谢胜利编实验一线性表的应用实验一（1）长整数运算[问题描述]　　设计一个程序实现两个任意长的正整数求和运算。[基本要求]　　利用单链表实现长整数的存储，每个结点存储四位数。任何整型变量的范围不超过255位。输入形式为不超过255位数字组成的字符串，输出形式为每四位一组，组间用逗号隔开。[测试数据]　　（1）0；0；应输出“0”。

2、　　（2）；1；应输出“1,0000,0000”。[实现提示]　　（1）可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表现为万进制数，且低四位在最前，逆序排列。　　（2）相加过程中不要破坏两个操作数链表。建立一个新的链表来存放两数的和。[算法思想]：（1）数据描述：可采用一个带有头结点的循环链表来表示一个非负的超大整数。从低位开始每四位组成的数字，依次放在链表的第一个、第二个、……结点中，不足四位的最高位存放在链表的最后一个结点中。例如：大整数“4321”可用如下的头结点的链

3、表表示：4321876589090567head图1.1按照此数据结构，可以从两个表头结点开始，顺序依次对应相加，求出所需要的进位后，将其带入下一个结点进行运算。typedefintElemType;typedefstructLnode{ElemTypedata;structLnode*next;}LNode,*LinkList,*BigInteger;（2）模块划分：主要包括三个模块，分别为创建大整数，输出大整数，两个大整数的加法。1.大整数的创建：BigIntegerCreateBigInteg

4、er(char*str){/*函数功能：把由数字组成的字符串str转化为图1.1所示的单链表，从字符串右边开始每4位，创建一个结点，直到字符串的最左边。*/BigIntegerL,p;intn,i,x;初始化单链表：创建一个只含头结点的单链表L;统计字符串str的长度n;i=n-1;/*从字符串的右边开始处理*/while(i>=0){/*如果还没到字符串str的最左边，循环继续*/依次从右边取4位数字字符，转化为十进制的4位数，放在变量x中，每取一个字符，i的值减1；创建一个新的结点p,p的数据域

5、为x，将p追加到单链表L的尾部；}returnL;}BigIntegerL,p;intn,i,x,a,b;n=strlen(str);L->next=NULL;L->data=0;i=n-1;L->next=q;这句话放在循环外面while(i>=0){for(x=0,a=4,b=1;a&&(i>=0);i--,a--,b*=10)x=b*(str[i]-'0')+x;p=(LNode*)malloc(sizeof(Lnode));p->data=x;q->data=x;q->next=p;q=p;

6、q->next=NULL;}returnL;}main(){char*str="";BigIntegerL=CreateBigInteger(str);printf("%d",L->data);}p->next=L->next;L->next=p;这句话有问题，链表不成立，需要重新添加一个结构体qL->next=q;这句话放在循环外面q->data=x;q->next=p;q=p;q->next=NULL;2.大整数的输出：输出形式为每四位一组，组间用逗号隔开。由于在单链表中，大整数是最低的4位在前

7、，最高的4位在后，为逆序排列，而打印必须是从高位到低位，所以输出过程可借助栈来实现。voidPrintBigInteger(BigIntegerL){初始化栈；从左到右依次将单链表中结点的数据入栈；将栈里的数据（4位数）依次出栈并打印，不足4位的用0补足，并在中间加逗号；}3.两个大整数的加法：算法的结构类似于常用的两个单链表的合并算法，只是两个结点合并产生新结点的方式不同，一般情况下新结点的数据域为两个结点的数据域的和，由于每个结点只能存放4位数，当和超过4位时，会产生进位，所以算法中必须处理进

8、位问题。BigIntegerAddBigIntege(BigIntegerL1,BigIntegerL2){/*创建一个单链表用于存放L1+L2，并将该单链表作为函数值返回*/LNode*L,*p,*q1,*q2;intx,carry;/*carry为进位*/初始化单链表：创建一个只含头结点的单链表L;q1=L1->next;q2=L2->next;carry=0;while(q1&&q2){/*两者均未到尾部*/将结点q1和结点q2的数据域与进位三者相加求和；将和的