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

温州大学瓯江学院WENZHOUUNIVERSITYOUJIANGCOLLEGE综合实验指导书专业计算机科学与技术课程数据结构综合实验数据结构综合实验实验指导书瓯江学院理工分院谢胜利编实验一线性表的应用实验一（1）长整数运算[问题描述]设计一个程序实现两个任意长的正整数求和运算。[基本要求]利用单链表实现长整数的存储，每个结点存储四位数。任何整型变量的范围不超过255位。输入形式为不超过255位数字组成的字符串，输出形式为每四位一组，组间用逗号隔开。[测试数据]（1）0；0；应输出“0”。（2）99999999；1；应输出“1,0000,0000”。[实现提示]（1）可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表现为万进制数，且低四位在最前，逆序排列。（2）相加过程中不要破坏两个操作数链表。建立一个新的链表来存放两数的和。[算法思想]：（1）数据描述：可采用一个带有头结点的循环链表来表示一个非负的超大整数。从低位开始每四位组成的数字，依次放在链表的第一个、第二个、……结点中，不足四位的最高位存放在链表的最后一个结点中。例如：大整数“567890987654321”可用如下的头结点的链表表示：图1.14321876589090567head按照此数据结构，可以从两个表头结点开始，顺序依次对应相加，求出所需要的进位后，将其带入下一个结点进行运算。typedefintElemType;typedefstructLnode{ElemTypedata;structLnode*next;}LNode,*LinkList,*BigInteger;（2）模块划分：主要包括三个模块，分别为创建大整数，输出大整数，两个大整数的加法。1.大整数的创建：BigIntegerCreateBigInteger(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的数据域为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;q-next=NULL;}returnL;}main(){char*str=542139109;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位在前，最高的4位在后，为逆序排列，而打印必须是从高位到低位，所以输出过程可借助栈来实现。voidPrintBigInteger(BigIntegerL){初始化栈；从左到右依次将单链表中结点的数据入栈；将栈里的数据（4位数）依次出栈并打印，不足4位的用0补足，并在中间加逗号；}\3.两个大整数的加法：算法的结构类似于常用的两个单链表的合并算法，只是两个结点合并产生新结点的方式不同，一般情况下新结点的数据域为两个结点的数据域的和，由于每个结点只能存放4位数，当和超过4位时，会产生进位，所以算法中必须处理进位问题。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的数据域与进位三者相加求和；将和的低4位放入变量x中；若和大于等于10000则进位为1否则为0；创建一个新的结点p,p的数据域为x，将p追加到单链表L的尾部；q1=q1-next;q2=q2-next;}while(q1){/*q1未到尾部*/将结点q1的数据域与进位两者相加求和；将和的低4位放入变量x中；若和大于等于10000则进位为1否则为0；创建一个新的结点p,p的数据域为x，将p追加到单链表L的尾部；q1=q1-next;}while(q2){/*q1未到尾部*/将结点q2的数据域与进位两者相加求和；将和的低4位放入变量x中；若和大于等于10000则进位为1否则为0；创建一个新的结点p,p的数据域为x，将p追加到单链表L的尾部；q2=q2-next;}if(carry){创建一个新的结点p,p的数据域为carry，将p追加到单链表L的尾部；}returnL;}另外，程序中使用了栈，必须添加有关栈的基本操作模块。实验一（2）停车场管理[问题描述]设停车场内只有一个的停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。[基本要求]以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。[测试数据]设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。[实现提示]需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含三个数据项：汽车的牌照号码、到达时间和进入停车场的时间。[选作内容]（1）两个栈共享空间，思考应开辟数组的空间是多少？（2）汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。（3）汽车可以直接从便道上开走，此时派在它前面的汽车要先开走让路，然后再依次排到队尾。（4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。[算法思想]：（1）数据描述：1、定义一个结构体表示车，其中包括三项数据：车牌号、车到达时间、车入库时间；typedefstructCar{intCarNum;//车牌号intArriveTime;//到达时间intEnterTime;//入库时间}Car;2、定义一个顺序栈来表示停车场；typedefCarSElemType;/*栈的数据元素为车*/typedefstruct{SElemTypedata[MaxSize];inttop;/*栈顶元素的下标，栈空时为-1*/}SqStack;3、链式队列表示便道；typedefCarQElemType;/*队列的数据元素为车*/typedefstructQNode{/*结点类型*/QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{/*链队列类型*/QueuePtrfront;/*队头指针*/QueuePtrrear;/*队尾指针*/}LinkQueue;（2）模块划分：本程序包括三个主要模块和有关栈与队列的基本操作模块：1）停车场管理模块intPark(void){/*模块功能：不断地输入命令，若为车辆到达则调用车辆到达模块，若为车辆离开则调用车辆离开模块，若为无效命令则不处理继续输入命令，直到接受到结束命令*/intend;初始化停车场（栈）和便道（队列）；end=0;while(!end){输入命令字，车辆牌号，时间;switch(命令字){case'a':case'A':车辆到达模块;break;/*调用车辆到达模块*/case'd':case'D':车辆离开模块;break;/*调用车辆离开模块*/case'e':case'E':printf(end\n);end=1;break;/*算法结束*/default:printf(无效命令，继续输入！\n);/*无效命令则不处理继续输入命令*/}}return1;}2)车辆到达模块voidArrival(intcarnumber,inttime,SqStack*Parking,LinkQueue*Aisle)/*车辆到达*/{/*参数说明：carnumber:车辆牌号，time:到达时间，Parking:停车场（栈），Aisle:便道（队列）。模块功能：若停车场未满，车辆进停车场，入库时间即为到达时间，打印相应信息；否则车辆暂时存放在便道，打印相应信息。*/if(!IsFull(*Parking)){/*停车场未满，车进停车场*/设置该车辆相应信息，进停车场；printf(车牌为%d的车辆进停车场\n,carnumber);}else{/*车场已满，车进便道*/设置该车辆相应信息，进便道；printf(车牌为%d的车辆须在便道等待!\n,carnumber);}}3）车离去模块voidLeave(intcarnumber,inttime,SqStack*Parking,LinkQueue*Aisle){/*车辆离开模块*/Carcar1;intsumtime;SqStacktemp;//临时停放栈，用于车辆离开时，存放在它后面的让路的车InitStack(&temp);while(!IsEmpty(*Parking)&&GetTop(*Parking).CarNum!=carnumber){//后面的车辆让路从停车场Parking中出栈入临时停放栈temp；}if(IsEmpty(*Parking)){//该车辆不在停车场内printf(停车场中没有牌号为%d的车辆\n,carnumber);临时停放栈temp中让路的所有车辆重新入库}else{//车辆离开Pop(Parking,&car1);//出栈，离开停车场sumtime=time-car1.EnterTime;//计算车辆存放时间printf(牌号为%d的车辆离开，总存放时间为%d。\n,car1.CarNum,sumtime);