栈和队列的应用---车厢排序的设计与实现

浙江大学城市学院实验报告课程名称数据结构实验项目名称实验四栈和队列的应用---车厢排序的设计与实现实验成绩指导老师（签名）日期一.实验目的和要求1、掌握栈的后进先出原则以及栈的存储结构和基本操作。2、掌握队列的先进先出原则以及队列的存储结构及基本操作。3、通过具体的应用实例，掌握栈和队列在实际问题中的运用。4、加强综合程序的分析、设计能力。二.实验内容1.1、共享栈的设置，问题描述如下：在一维数组空间stack[MaxSize]中可以同时存放两个顺序栈，栈底分别处在数组的两端，当第1个栈的栈顶指针top1等于－1时则栈1为空，当第2个栈的栈顶指针top2等于MaxSize时则栈2为空。两个栈均向中间增长，当有元素向栈1进栈时，使top1增1得到新的栈顶位置，当有元素向栈2进栈时，使top2减1得到新的栈顶位置。当top1==top2-1或top1+1==top2时，存储空间用完，无法再向任一栈做进栈操作，此时可考虑给出错误信息并停止运行。要求：⑴给出共享栈的顺序存储类型定义。⑵给出共享栈的抽象数据类型定义。⑶建立头文件SeqStack.h，包含共享栈的基本操作实现函数；建立主程序文件test4_1.cpp，在主函数中对共享栈的各个操作进行测试。1.2、利用上述共享栈，实现火车车厢的调度模拟设火车车厢分为三类：硬座、硬卧、软卧，分别用A、B、C表示。下图描述车厢调度的示意图，图中右端为排列无序的车厢，左端为调度后的车厢排列，使得所有软卧车厢在最前面、所有硬卧车厢在中间、所有硬座车厢在最后。编程模拟上述车厢调度过程。提示：两个辅助铁轨相当于两个栈，右端车厢进入用相应字符串给出，如“BBACBCAABBCAA”，左端车厢的序列放在一个链式存储的队列中。在LinkQueue.h给出模拟函数，并在test4_2.cpp中进行调用测试。BBACBCAABBCAACCCBBBBBAAAAA铁轨辅助铁轨2、以小组为单位认真填写实验报告，实验报告必须包括各类数据类型的结构定义说明，各类数据的组织方式，系统的功能结构，各个操作的定义以及实现方法，运行结果与分析，难点如何解决，存在问题以及可改进之处等。同时，在实验报告中需写明小组每位同学的分工，得分（小组总分不超过12分）等。实验报告文件取名为report4.doc。每组还必须制作一个答辩PPT，该PPT的命名为PPT_车厢排序_(各小组成员名字).PPT。3、每位同学上传实验报告文件report4.doc、源程序文件test4_1.cpp、test4_2.cpp及SeqStack.h、LinkQueue.h，以及答辩PPT压缩打包后到BB平台上。共享栈结构体定义structStack{ElemType*stack;inttop1,top2;//表示栈顶元素的位置}S;共享栈抽象数据类型定义ADTSTACK{数据对象：D={ai|ai(∈D0,i=1,2,...,n,n=0}数据关系：R={ai-1,ai|ai-1,ai∈D0,i=2…n}约定其中a1端为栈顶，an端为栈底基本操作：StatusInitStack(Stack&S)//构造一个空栈StatusClearStack(Stack&S,intk)//清空栈。当k=1或2时对应栈1或栈2被清空，k=3时两个栈均被清空intStackEmpty(Stack&S,intk)//判断栈是否为空。当k=1或2时判断对应的栈1或栈是否为空；k=3时，判断两个栈是否同时为空。若判断结果为空则返回1，否则返回0StatusGetTop(Stack&S,intk,ElemType&e)//取栈顶元素。若栈不为空，根据k得值用e返回栈1或栈2的栈顶元素，并返回OK；否则返回ERRORStatusPush(Stack&S,intk,ElemTypee)//进栈。当k=1或2时对应向栈1或栈2的顶端插入元素e，并返回OK；否则返回ERRORStatusPop(Stack&S,intk,ElemType&e)//出栈。若栈不为空，根据k的值删除栈1或栈2的栈顶元素，用e返回其值，并返回OK；否则返回ERROR}ADTSTACK共享栈操作测试程序功能模块结构图共享栈操作测试程序函数调用结构图mainInitStackClearStackStackEmptyPopPushGetTopMenu主菜单构造一个空栈清空栈判断栈是否为空取栈顶元素栈1栈2栈1栈2栈1栈2出栈进栈全部全部栈1栈2栈1栈2共享栈操作测试程序运行结果与分析输入对应的数字，测试相应的功能队列结构体定义typedefstructqNode{chardata;structqNode*next;}QNode,*QueuePtr;typedefstruct{QNode*front;//队头指针QNode*rear;//队尾指针}LinkQueue;队列抽象数据类型定义ADTQUEUE{数据对象：D={ai|ai(∈D0,i=1,2,...,n,n=0}数据关系：R={ai-1,ai|ai-1,ai∈D0,i=2…n}约定其中a1端为队列头，an端为队列尾基本操作：StatusInitQueue(LinkQueue&q)//构造一个空队列StatusEnQueue(LinkQueue&q,ElemTypee)//插入元素e为q的新的队尾元素StatusDeQueue(LinkQueue&q,ElemType&e)//若队列不空，则删除q的队头元素，用e返回其值，并返回OK；否则返回ERRORStatusDestroyQueue(LinkQueue&q)//销毁队列q}ADTQUEUE火车调度函数调用结构图火车调度思路将字符串中的字符’B’进入栈1，字符’A’进入栈2，字符’C’进入队列，栈1的元素依次出栈进入队列，栈2的元素依次出栈进入队列，遍历队列并输出每个元素mainInitQueueInitStackPushEnQueuePop火车调度运行结果与分析难点现象：测试共享栈时未输入进栈的字符就直接执行了下一条语句原因：忽视了输入之后的回车也是个字符解决：在输入进栈的字符前，增加一句getchar（）存在的问题及可改进之处问题：输入非法字符无法使程序正常运行改进：可以增加对输入的非法字符的处理程序清单test4_1.cpp#includestdio.h#includestdlib.htypedefcharElemType;typedefintStatus;#defineOK1#defineERROR0#defineMaxSize20#defineOVERFLOW-2structStack{ElemType*stack;inttop1,top2;//表示栈顶元素的位置}S;#includeSeqStack.hvoidmenu(){printf(输入1，清空栈\n);printf(输入2，判断栈是否为空\n);printf(输入3，取栈顶元素\n);printf(输入4，进栈\n);printf(输入5，出栈\n);printf(输入0，退出\n);}intmain(){inti,k;chare;if(InitStack(S))printf(成功创建空栈\n);menu();while(scanf(%d,&i)){switch(i){case1:printf(输入1清空栈1，输入2清空栈2，输入3均清空\n);scanf(%d,&k);ClearStack(S,k);printf(输入6，返回;输入0，退出\n);break;case2:printf(输入1判断栈1，输入2判断栈2，输入3均判断\n);scanf(%d,&k);if(StackEmpty(S,k))printf(空栈\n);elseprintf(非空栈\n);printf(输入6，返回;输入0，退出);break;case3:printf(输入1取栈1，输入2取栈2\n);scanf(%d,&k);GetTop(S,k,e);printf(栈顶元素为%c\n,e);printf(输入6，返回;输入0，退出);break;case4:getchar();printf(输入进栈元素\n);e=getchar();printf(输入1操作栈1，输入2操作栈2\n);scanf(%d,&k);Push(S,k,e);printf(输入6，返回;输入0，退出);break;case5:printf(输入1操作栈1，输入2操作栈2\n);scanf(%d,&k);Pop(S,k,e);printf(%c\n,e);printf(输入6，返回;输入0，退出);break;case6:system(cls);menu();break;case0:exit(0);break;default:printf(请输入0-5!);}}}SeqStack.hStatusInitStack(Stack&S)//构造一个空栈{S.stack=(ElemType*)malloc(MaxSize*sizeof(ElemType));if(!S.stack)exit(OVERFLOW);//存储分配失败S.top1=-1;S.top2=MaxSize;returnOK;}StatusClearStack(Stack&S,intk)//清除空。当k=1或2时对应栈1或栈2被清空，k=3时两个栈均被清空{if(k==1)S.top1=-1;elseif(k==2)S.top2=MaxSize;elseif(k==3){S.top1=-1;S.top2=MaxSize;}returnOK;}intStackEmpty(Stack&S,intk)//判断栈是否为空。当k=1或2时判断对应的栈1或栈是否为空；k=3时，判断两个栈是否同时为空。若判断结果为空则返回1，否则返回0{if(k==1)returnS.top1==-1;elseif(k==2)returnS.top2==MaxSize;elseif(k==3)return(S.top1==-1)&&(S.top2==MaxSize);else{printf(k的值不正确!);returnERROR;}}StatusGetTop(Stack&S,intk,ElemType&e)//取栈顶元素。若栈不为空，根据k得值用e返回栈1或栈2的栈顶元素，并返回OK；否则返回ERROR{if(k==1){if(S.top1==-1){printf(栈1是空栈!\n);returnERROR;}e=S.stack[S.top1];}elseif(k==2){if(S.top2==MaxSize){printf(栈2是空栈!\n);returnERROR;}e=S.stack[S.top2];}else{printf(k的值不正确!);returnERROR;}returnOK;}StatusPush(Stack&S,intk,ElemTypee)//进栈。当k=1或2时对应向栈1或栈2的顶端插入元素e，并返回OK；否则返回ERROR{if(S.top1==S.top2-1){printf(存储空间已用完!\n);returnERROR;}if(k==1){S.top1++;S.stack[S.top1]=e;}elseif(k==2){S.top2--;S.stack[S.top2]=e;}returnOK;}StatusPop(Stack&S,intk,ElemType&e)//出栈。若栈不为空，根据k的值删除栈1或栈2的栈顶元素，用e返回其值，并返回OK；否则返回ERROR{if(k==1){if(S.top1==-1){printf(栈1是空栈!\n);returnERROR;}e=S.stack[S.top1];S.top1--;returnOK;}elseif(k==2){if(S.top2==MaxSize){printf(栈2是空栈!\n);returnERROR;}e=S.stack[S.top2];