中南大学数据结构实验报告

中南大学数据结构试验报告题目实验二学生姓名王云鹏学号8213180228指导老师郑瑾学院计算机学院专业班级物联网1802完成时间2020.6指导老师评定签名实验二1.需求分析1．栈和队列操作的实现（验证性实验）问题描述(1)建立一个顺序栈。(2)建立一个循环顺序队列。(3)分别实现栈和队列的基本操作。2．数制转换问题（设计性实验）问题描述十进制数n和其他d进制数的转换是计算机实现计算的基本问题，其解决方案很多，其中最简单的方法基于下列原理，即除d取余法。例如，(1348)10＝(2504)8。Nndiv8nmod8134816841682102125202从中可以看出，最先产生的余数4是转换结果的最低位，这正好符合栈先进后出的特性，所以可以用顺序栈来模拟这个过程。基本要求从键盘输入任意一个非负的十进制整数，打印输出与其等值的八进制数。由于上述的计算过程是从低位到高位顺序产生的八进制数的各个数位，而打印输出一般来说应从高位到低位进行，恰好与计算过程相反。因此，可以先将计算过程中得到的八进制数的各位进栈，待相对应的八进制数的各位均产生以后，再使其按顺序出栈，并打印输出。这样就得到了与输入的十进制数相对应的八进制数。测试数据由读者依据软件工程的测试技术自己确定。注意测试边界数据5.停车场管理（综合性实验）问题描述设停车场内是一个可停放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)。每一组输入数据包括3个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，“A”表示到达，“D”表示离去，“E”表示输入结束。基本要求以顺序栈模拟停车场，以链队列模拟便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括3项：是“到达”还是“离去”、汽车牌照号码及“到达”或“离去”的时刻。对每一组输入数据进行操作后的输出数据为：如果是到达的车辆，则输出其在停车场内或便道上的停车位置；如果是离去的车辆，则输出其在停车场内的停留时间和应交的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。实现提示需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。选作内容(1)两个栈共享空间，思考应开辟数组的空间是多少？(2)汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。(3)汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。(4)停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。2.概要设计验证性实验函数：设计性实验函数：综合性实验函数：3.详细设计验证性实验#includestdio.h#includestdlib.h#definemaxsize10typedefintElemType;typedefstruct{ElemType*base;ElemTypetop;//下标}stack;stack*Init(){//初始化函数stack*s;s-base=(ElemType*)malloc(maxsize*sizeof(ElemType));//申请空间if(s==NULL){printf(mallocfailinInit);returnNULL;}s-top=0;returns;}voidpush(stack*s,ElemTypee){//压栈if(s-top==maxsize){//溢出printf(stackisoverflow);return;}*(s-base+s-top)=e;//压入s-top++;//栈顶上移}intpop(stack*s){//出栈if(s-top==0){//空栈printf(stackisunderflow);return0;}s-top--;//栈顶下移return*(s-base+s-top);//返回移出的值}intgetTop(stack*s){//取栈顶，而不动栈顶指针if(s-top==0){//空栈printf(stackisunderflow);return0;}return*(s-base+s-top-1);}voidprint(stack*s){//从栈顶到栈底打印栈printf(stack:\n);for(inti=s-top-1;i=0;i--){printf(%d\n,*(s-base+i));}}intmain(){stack*s=(stack*)malloc(sizeof(stack));//产生一个栈s-base=(ElemType*)malloc(maxsize*sizeof(ElemType));if(s==NULL){printf(mallocfailinmain);return0;}s-top=0;//栈顶指针初始为0，该指针仅代表数组的下标push(s,1);push(s,2);push(s,3);print(s);printf(pop:%d\n,pop(s));print(s);printf(getTop:%d\n,getTop(s));return0;}#includestdio.h#includestdlib.h#definequeuesize100#defineoverflow1#defineunderflow-1#defineok0typedefintElemType;typedefstructsqueue{ElemTypesq[queuesize];ElemTypefront;ElemTyperear;}queue;inten_cycque(queue*q,ElemTypex){//入队inti=(q-rear+1)%queuesize;//循环队列if((i==q-front)){//空出一个不用printf(overflow\n);//溢出returnoverflow;}q-sq[q-rear]=x;//写入,rear指向队列最后一个元素后面的位置q-rear=i;//尾指针移动returnok;}intdl_cycque(queue*q,ElemType*x){//出队if(q-front==q-rear){//空队printf(underflow\n);returnunderflow;}*x=q-sq[q-front];//用x带出q-front=(q-front+1)%queuesize;//头指针后移，从队头删除returnok;}intprint(queue*q)//打印队列{if(q-front==q-rear)//溢出{printf(underflow\n);returnunderflow;}elseif((q-rear+1)%queuesize==q-front)//空队{printf(overflow);returnoverflow;}elseif(q-rearq-front)//若队尾指针在队头指针后面{for(inti=q-front;iq-rear;i++)//遍历打印{printf(%d\n,q-sq[i]);}}elseif(q-rearq-front)//若队尾指针在队头指针前面{for(inti=q-front;i=queuesize;i++){printf(%d\n,q-sq[i]);}for(inti=0;iq-rear;i++){printf(%d\n,q-sq[i]);}}}intmain(){queueq;//生成循环队列q.front=0;//使队头队尾皆为0q.rear=0;en_cycque(&q,1);en_cycque(&q,2);en_cycque(&q,3);print(&q);inte;//带出删掉的元素dl_cycque(&q,&e);//printf(%d\n,e);//查看删掉的元素print(&q);return0;}设计性实验#includestdio.h#includestdlib.h#definemaxsize10typedefintElemType;typedefstruct{ElemType*base;ElemTypetop;//下标}stack;voidpush(stack*s,ElemTypee){//压栈if(s-top==maxsize){//溢出printf(stackisoverflow);return;}*(s-base+s-top)=e;//压入s-top++;//栈顶上移}voidprint(stack*s){//从栈顶到栈底打印栈for(inti=s-top-1;i=0;i--){printf(%d,*(s-base+i));}}intmain(){//产生一个栈stack*s=(stack*)malloc(sizeof(stack));//产生一个栈s-base=(ElemType*)malloc(maxsize*sizeof(ElemType));if(s==NULL){printf(mallocfailinmain);return0;}s-top=0;//栈顶指针初始为0，该指针仅代表数组的下标//转换数制intd=8;//要转化为的数制intdest=1348;//目标数intcout=dest;//记录，用于输出intremainder=0;//余数while(1){remainder=dest%d;//取余，压到栈中push(s,remainder);dest=dest/d;if(dest==0){综合性实验break;}}printf(十进制数%d转化为八进制数后为：,cout);print(s);}#includestdio.h#includestdlib.h//栈#definemaxsize2//栈的空间#definefull1#definenotfull-1#defineempty0#definenotempty1#defineok0#definefail1#defineunderflow-1typedefintElemType;typedefstruct//栈{ElemType*base;//基指针ElemTypetop;//下标}stack;voidInit(stack*s){//初始化函数s-base=(ElemType*)malloc(maxsize*sizeof(ElemType));//申请空间if(s==NULL){printf(mallocfailinInit);return;}s-top=0;//初始化时下标为0}voidpush(stack*s,ElemTypee){//压栈if(s-top==maxsize){//溢出printf(stackisoverflow);return;}*(s-base+s-top)=e;//压入s-top++;//栈顶上移}intpop(stack*s){/