栈和队列的应用的实验报告

栈和队列的应用的实验报告一、实验目的掌握队列和栈的顺序存储结构和链式存储结构，并初步学会在实际背景下灵活运用；掌握栈和队列的基本运算在两种存储结构上的实现方法；掌握栈和队列的特点，即FILO及FIFO的原则。二、实验内容停车场管理的模拟；迷宫问题的模拟。三、实验要求1.“停车场管理的模拟”部分［问题说明］设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已放满n辆车，则后到达的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如果有某辆车要开走，在它之后进入停车场的车辆都必须先退出停车场（进入规避所）为它让道，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交纳停车费。如果停留在便道上的车辆没有进入停车场就要离去，则允许其离去，不收停车费，并且仍然保持在便道上等待车辆的次序。编制一程序模拟停车场的管理。［基本要求］程序能输出每辆车到达后的停车位置（停车场/便道），每辆车离开停车场时应交纳的费用。1.编译并运行：输入数据：’A'/'D',车牌号，到达时间/离开时间E---退出。输入数据：’A'/'D',车牌号，到达时间/离开时间E---退出。A,2120,6 ＜回车＞第2120号车停在停车场的第1号车位上Pressanykeytocontinue...＜回车＞输入数据：’A'/'D',车牌号，到达时间/离开时间E---退出。A,8761,ll＜回车〉StackOverflow!第8761号车停在便道的第1号车位上Pressanykeytocontinue...

输入数据：’A'/'D',车牌号，到达时间/离开时间E---退出。A,2110,7<回车〉第2110号车停在停车场的第2号车位上Pressanykeytocontinue...回车>输入数据：’A'/'D',车牌号，到达时间/离开时间E---退出。A,4153,8<回车〉第4153号车停在停车场的第3号车位上Pressanykeytocontinue...回车>输入数据：’A'/'D',车牌号，到达时间/离开时间E---退出。A,5154<回车〉第5354号车停在停车场的第4号车位上Pressanykeytocontinue...<回车>2.分析程序（注：该程序的Delive函数有错误，已将更改后的程序覆盖到原程序上）#defineN4#defineN4#defineM5#defineTrue1#defineFalse0#defineNull0#include<stdio.h>#include<stdlib.h>#include<conio.h>/*声明停车场n为4*//*收费单价*/typedefstructelement{intnum;/*定义到达时间*//*/*定义到达时间*//*ElemType代表一个新类型名,}ElemType;代表上面指定的一个结构体类型。这是就可以用ElemType定义变量*/typedefstructstacktag{ElemTypestack[N];inttop;}STACK;/*STACK代表一个新类型名，代表上面指定的一个结构体类型。这是就可以用STACK定义变量*/typedefstructnodetag{intnum;structnodetag*next;}QUEUE;/*QUEUE代表一个新类型名，代表上面指定的一个结构体类型。这是就可以用QUEUE定义变量*/typedefstructqueuetag{QUEUE*front,*rear; /“定义队头指针*front,队尾指针*rear”/}LinkedQueTp; /*LinkedQueTp代表一个新类型名，代表上面指定的一个结构体类型。这是就可以用LinkedQueTp定义变量*/voidIniStack(STACK*s); /*定义STACK*s表示s为指向STACK结构体类型数据的指针，初始化栈*/intPush(STACK*s,ElemTypex);ElemTypePop(STACK*s);voidIniLinkedQue(LinkedQueTp*s); /*初始化队列*/voidEnLinkedQue(LinkedQueTp*s,intnum1);intDeLinkedQue(LinkedQueTp*s); /*删除队列*/voidArrive(STACK*s1,LinkedQueTp*p,ElemTypex);/*到达*/voidDelive(STACK*s1,STACK*s2,LinkedQueTp*p,ElemTypex);/*离开*//*初始化栈*//*定义为空栈*//*初始化栈*//*定义为空栈*/{s->top=-1;return;}intPush(STACK*s,ElemTypex)操作？？)*/intPush(STACK*s,ElemTypex)操作？？)*/{if(s->top==N-1){问：/*压栈函数（完成进栈/*判断队是否为满*/printf("\nStackOverflow!\n");return(False); }值*/else{printf("\nStackOverflow!\n");return(False); }值*/else{s->top++;s->stack[s->top]=x;/*返回“错误”，即返回“0”/*指针s后移*//*把s->top中的值赋给stack[],并把数据域的值定为x*/return(True); }}/*InitializeStack*/{ElemTypex;inti;{ElemTypex;inti;if(s->top<0){x.num=Null;x.arrtime=Null;return(x);}else{s->top--;i=s->top+1;x=s->stack[i];栈，即所谓的删除车辆工作)*/returnx;}}/*Pop*/问题：/*判断栈是否为空？*//*不计入车辆入栈时间*//*指针从栈顶下移(后进先出)*//*用i记录移动前指针s的位置*//*将该位置的数据给x(完成出voidIniLinkedQue(LinkedQueTp*s){QUEUE*p1;s->front=(QUEUE*)malloc(sizeof(QUEUE));/*为s指针开辟一个新结点*/s->rear=s->front;p1=s->front; /*pl指向栈顶*/p1->next=Null; /*头结点指针域初始化(定义为空栈)*/pl->num=0; /*头结点数据域初始化*/}/*IniLinkedQue*/voidEnLinkedQue(LinkedQueTp*s,intnum1)/*数据入队列(链接式循环队列)*/{QUEUE*p,*pl;p=(QUEUE*)malloc(sizeof(QUEUE)); /*产生一个新节点*/p->num=numl; /*加入数据*/p->next=Null; /*下一个为零*/p1=s->rear; /*加入队尾*/(在这里我觉得pl可以删除。等同于s->rear->next二p,即结构体指针s中rear成员的指针域等于P,为尾插法，)pl->next=p; /*加入*/s->rear=p; /将p指针移动到s->rear,完成尾插/pl=s->front;pl->num++; /*修改保存在头结点数据域中的车辆数*/}/*EnLinkedQue*/intDeLinkedQue(LinkedQueTp*s){/*数据节点出队列*/

QUEUE*p;intn;if(s->front==s->rear)return(Null);/*若队列为空，则返回空*/else{p=s->front->next;s->front->next=p->next;if(p->next==Null)/*p是第1个节点*//*将P指针指向的节点中的数据取出*//*若仅有一个节点，则直接删除*/s->rear=s->front;n=p->num;针和尾指针画在一个节点里，free(p);s->front->num--;return(n);}}/*DeLinkedQue*//*存储取出的数据，即头指表示此时链队列为空*//*释放单元*//*队列个数减一*//*返回取出的数据，即车牌号*/voidArrive(STACK*s1,LinkedQueTp*p,ElemTypex)/*车辆到达处理*/{intf；f=Push(s1,x);if(f==False)/*新到车辆进入停车场栈。在栈si的栈顶插入数据元素x*//*如停车场满,就进入便道队列等待*/{EnLinkedQue(p,x.num);printf(“第％小号车停在便道的第％d号车位上\n",x.num,p->front->num);}else{/*新到车辆进入停车场*/printf(“第％小号车停在停车场的第％d号车位上\n",x.num,sl->top+1);}} /*Arrive*/voidDelive(STACK*s1,STACK*s2,LinkedQueTp*p,ElemTypex){intn,f=False;ElemTypey,z; /*增加z*/QUEUE*q;while((s1->top>-l)&&(f!二True))/*循环条件：栈中有数据并且没找到那辆要出来的车*/{/*在停车场中寻找要离开的车辆*/y=Pop(s1);/*弹出数据*/if(y.num!=x.num)/*如果栈顶元素不是要离开的车辆,就将其放如车辆规闭所*/n二Push(s2,y)/*压不离开的车辆入规避所*/elsef=True/*找到要离开的车辆，此时y.num二二x.num*/}/******//*规避所的车辆回原位*/while(s2->top>-1){ /*将y改为z，不能改变Y因为里面存着要离开的车辆*/Z二Pop(s2);/*规避所的车辆出栈*/f二Push(sl,z);/*再次进入停车场*/}if(y.num==x.num)/*在停车场中找到要离开的车辆*/{printf("第%d号车应收费％d元",y.num,(x.arrtime-y.arrtime)*M);/*规避所的车辆回原位*/while(s2->top>-1){ /*将y改为z，不能改变Y因为里面存着要离开的车辆*/z=Pop(s2);/*规避所的车辆出栈*/f=Push(s1,z);/*再次进入停车场*/}/*规避所的车辆全部回原位后*/n二DeLinkedQue(p);/*车出便道队列*/if(n!=Null){ /*有车在便道队列中等待*/y.num=n;/*存入车牌号*/y.arrtime=x.arrtime;/*存入到达时间*/f=Push(s1,y);/*进入停车场*/printf("第%d号车停在停车场第％d号车位上\n",y.num,sl->top+1);/*打印一下有车进入*/}}else{/*在停车场中没有找到要离开的车辆，说明在便道*/q=p->front;/*指向队头*/f二False/*没在停车场*/while(f==False&&q->next!=Null/*在便道上寻找要离开的车辆*/{if(q->next->num!二x.num)q=q->next/*不是该车后以继续寻找*/else/*在便道上找到该车辆*/{q->next二q->next->next;/*将该车删除*/p->front->num--;if(q->next二二Null) p->rear=q; /*二p->front是错误的*/printf("第%小号车离开便道\n",x.num);/*该车离开便道，但不收费*/f=True;}

if（f二二False）printf（"输入数据错误，停车场和便道上均无第％d号车\n",x.num）;}voidmain（）{ /*停车场模拟管理程序*/charch1，ch2S;TACK*s1，*s2;/*定义两个栈，一个停车场，一个规避所*/LinkedQueTp*p; /*定义一个便道队列*/ElemTypex;/*新建停车场*//*新建规避所*//*新建停车场*//*新建规避所*//*新建便道队列*//*初始化停车场栈*//*初始化车辆规避所栈*//*初始化便道队列*//*初始化退出旗帜*/s1=(STACK*)malloc(sizeof(STACK));s2=(STACK*)malloc(sizeof(STACK));p=(LinkedQueTp*)malloc(sizeof(LinkedQueTp));IniStack(s1);IniStack(s2);IniLinkedQue(p);flag=True;for(;;){clrscr();printf("\n输入数据：’A'/'D',车牌号，到达时间/离开时间\n");printf("E退出。\n");scanf("%c,%d,%d",&ch1,&t1,&t2);x.num=t1;x.arrtime=t2; /*只记录小时值，没有考虑分钟*/ch2=getchar();/*清空输入缓冲区*/switch(ch1){case'a': /*加入车辆*/case'A':Arrive(s1,p,x); /*调用加入函数*/printf("\nPressanykeytocontinue...\n");getch();break;case'd': /*删除车辆*/case'D':Delive(s1,s2,p,x); /*调用删除车辆函数*/printf("\nPressanykeytocontinue...\n");getch();break;case'e': /*退出程序*/case'E':flag=False;printf("\n程序正常结束\n");break;default:printf("\n输入数据错误，重新输入\n");printf("\nPressanykeytocontinue...\n");getch();break;}if(flag==False)break; /*退出循环*/}return;}思考：该停车场管理系统程序与现实生活中的停车场有一些区别。其使用价值有些令人质疑。比如对时间的计算(如果单纯的计入小时数，如果一辆车9：00pm.进的而第二天&00am•出的停车场，其缴纳的费用就会有错误。)思考题如何改进“停车场管理模拟程序”的设计，使每辆车到达及离开的时间可以人们习惯的方式输入？如果用数据库系统来做这一模拟工作，如何设计？先自定义一个函数，读入到达离开的小时、分钟。分钟换算成小时的小数，小时、分钟相加，用单价*分钟=费用。2.“迷宫问题的模拟”部分［问题说明］模拟心理学实验中老鼠对仅有一入口和一个出口的迷宫找出路的过程。［基本要求］设计一程序对任意设定的迷宫，求出一条从入口到出口的路线，或得出没有可行通路的结论。#defineM212/*以下均为声明*/#defineN211#defineMAXLENM2#defineTrue1#defineFalse0#defineNull0#include<stdio.h>#include<stdlib.h>#include<string.h>#include<conio.h>intM=M2-2,N=N2-2;typedefstructelem{

intx,y,dir;/*定义一个结构体类型*/}ElemType;/*定义一个结构体类型*/typedefstructstktag{ElemTypestack[MAXLEN];inttop;}STACK;typedefstructmoved{intdx,dy;}MOVE;voidIniMaze(intmaze[][N2]);/*初始化迷宫*/voidIniMove(MOVEmove[]);voidIniStack(STACK*s);intPush(STACK*s,ElemTypex);ElemTypePop(STACK*s);voidpath(intmaze[][N2],MOVEmove[],STACK*s);voiddraw(intmaze[][N2],STACK*s);voidmain(){/*主函数*//*寻找迷宫通路程序*/STACK*s;intmaze[M2][N2];MOVEmove[8];IniMaze(maze);/*初始化迷宫数组*/getch();s=(STACK*)malloc(sizeof(STACK));/*创建一个栈，开辟新结点*/IniStack(s);/*初始化栈*/IniMove(move);/*初始化移动函数*/path(maze,move,s); /*调用路径函数，寻找路径，并存储在栈s里*/draw(maze,s); /*用“*”显示迷宫通路*/getch();} 为原样本程序的一个错误。由于没有该句，导致运行时屏幕显示的不全。voidIniMaze(intmaze[][N2]){voidIniMaze(intmaze[][N2]){inti,j,num;for(i=0,j=0;i<=M+1;i++)字1代表墙壁*/for(i=0,j=N+1;i<=M+1;i++)字1代表墙壁*//*初始化迷宫*/maze[i][j]=1;/*构建迷宫第一列，用数maze[i][j]=1/*构建迷宫第11列，用数for(i=0,j=0;j<=N+1;j++)数字1for(i=0,j=0;j<=N+1;j++)数字1代表墙壁*/maze[i][j]=1;/*构建迷宫第1行，用maze[i][j]=1;/*构建迷宫第12maze[i][j]=1;/*构建迷宫第12行，用maze[i][j]=1;maze[i][j]=0;/*在迷宫内部填满“0”数字1代表墙壁*/for(i=1;i<=M;i++){for(j=1;j<=N;j++){num=(800*(i+j)+1500)%327;if((num<150)&&(i!=M||j!=N))else或“1”来将迷宫构建完善*/}}printf("\n");for(i=0;i<=M+1;i++){printf("\n");for(j=0;j<=N+1;j++){if((i==O)&&(j==O)||(i二二M+1)&&(j二二N+l))printf("%3d",0);/*显示迷宫的出口和入口*/elseprintf("%3d",maze[i][j]);*将迷宫的图示整个完整的输出*/}}/*IniMaze*/voidIniMove(MOVEmove[]/*设置移动函数表示8个方向*/{TOC\o"1-5"\h\zmove[0].dx=0; move[0].dy=l; /*北*/move[l].dx=l;move[l].dy=l; /*东北*/move[2].dx=l; move[2].dy=0; /*东*/move[3].dx=l; move[3].dy=-l; /*东南*/move[4].dx=0;move[4].dy=-l; /*南*/move[5].dx=-l;move[5].dy=-l; /*西南*/move[6].dx=-l;move[6].dy=0; /*西*/move[7].dx=-l;move[7].dy=l; /*西北*/}/*IniMove*/voidIniStack(STACK*s) /*初始化栈*/{s->top=-l;}/*IniStack*/intPush(STACK*s,ElemTypex)/*压栈函数*/{if(s->top==MAXLEN-l)return(False);else{s->stack[++s->top]=x;}/*Push*/ElemTypePop(STACK*s)/*弹栈*/{ElemTypeelem;if(s->top<0){elem.x二Null; /*栈空时，返回NULL，栈非空，返回一个值*/elem.y=Null;elem.dir=Null;return(elem);}else{s->top—; /*STACK形指针s指向该结构体内成员top,再移动s*/return(s->stack[s->top+1]); }/*将s指向的成员中的值*/}/*pop*/voidpath(intmaze[][N2],M0VEmove[],STACK*s)/*定义路径函数*/{inti,j,dir,x,y,f;ElemTypeelem;i=1; j=1;dir=0;maze[1][1]=-1; /*设[1][1]为入口处*/do{x=i+move[dir].dx;/*求下一步可行的到达点的坐标*/y=j+move[dir].dy;if(maze[x][y]==0){elem.x=i;elem.y=j;elem.dir=dir;f=Push(s,elem);if(f二二False)printf("栈长度太短\n");i=x; j=y;dir=0;maze[x][y]=-1; }elseif(dir<7)dir++;else{ /*8个方向都不可行,就退回一步*/elem=Pop(s);if(elem.x!=Null){i=elem.x; j=elem.y; /*把刚才经过的路径记录在坐标里*/dir=elem.dir+1; }}while(!((s->top==-1)&&(dir>=7)||(x==M)&&(y==N)&&(maze[x][y]==-1)));if(s->top==-l) printf(“此迷宫无路\n");else{elem.x=x;elem.y=y;elem.dir=dir;f=Push(s,elem);printf("\n迷宫的通路是：\n");i=0;while(i<=s->top){printf("(%d,%d)",s->stack[i].x,s->stack[i].y);/*显示迷宫通路*/if(i!=s->top) printf("-->");if((i+1)%4==0) printf("\n");i++; }printf("\n");}}/*path*/voiddraw(intmaze[][N2],STACK*s)/*调用通路函数*/{inti,j;ElemTypeelem;for(i=1;i<=M;i++) /*将迷宫中全部的-1值恢复为0值*/for(j=1;j<=N;j++)if(maze[i][j]==-1) maze[i][j]=0;while(s->top>-1){elem=Pop(s);i=elem.x; j=elem.y;maze[i][j]=8;/*将通路用8表示*/ }for(i=0;i<=M+1;i++){for(j=0;j<=N+1;j++){if((i==0)&&(j==0)||(i==M+1)&&(j==N+1))printf("%3d",0);elseif(maze[i][j]==8)printf("%c",'*');/*用“*"代替8,来表示迷宫通路*/elseprintf("%3d",maze[i][j]);/*显示已标记通路的迷宫*/}printf("\n");}printf("\n");}/*draw*/思考题“迷宫模拟”中程序是如何记住可行线路的？用栈记住，栈有先进后出的性质，利用这个特点记住线路。思考：以上为迷宫程序，使用了栈思想，而下面的程序用了“队列”的思想，运用了“先进先出”的思想。可以表达同样的效果。由于两程序有许多相似之处，所以注释处有省略。“迷宫问题的最短线路”部分1)编译并运行样本程序；显示屏上出现：TOC\o"1-5"\h\z0 1 1 1 1 1 1 1 1 1 11 0 0 1 0 1 0 1 0 1 11 0 1 0 1 0 1 0 1 0 11 1 0 1 0 1 0 1 0 0 11 0 1 0 1 0 1 0 0 1 11 1 0 1 0 1 0 0 1 0 11 0 1 0 1 0 0 1 0 1 11 1 0 1 0 0 1 0 1 0 11 0 1 0 0 1 0 1 0 1 11 1 0 0 1 0 1 0 1 0 11 0 0 1 0 1 0 1 0 0 11 1 1 1 1 1 1 1 1 1 0迷宫中的最短通路是：(1,1)-->(1,2)-->(2,3)-->(3,4)-->4,5)-->(5,6)-->(6,6)-->(7,7)-->(8,8)-->(9,9)-->(10,9)* 1 1 1 1 1 1 1 1 1 11 * * 1 0 1 0 1 0 1 11 0 1 * 1 0 1 0 1 0 11 1 0 1 * 1 0 1 0 0 11 0 1 0 1 * 1 0 0 1 11 1 0 1 0 1 * 0 1 0 11 0 1 0 1 0 * 1 0 1 11 1 0 1 0 0 1 * 1 0 11 0 1 0 0 1 0 1 * 1 11 1 0 0 1 0 1 0 1 * 11 0 0 1 0 1 0 1 0 * 11 1 1 1 1 1 1 1 1 1 *

2.分析程序#defineM212#defineN211#defineMAXLENM2*N2#defineTrue1#defineFalse0#defineNull0#include<stdio.h>#include<stdlib.h>#include<string.h>#include<conio.h>intM=M2-2,N=N2-2;typedefstructelem{intx,y;intdir;}typedefstructelem{intx,y;intdir;}ElemType;typedefstructstktag{ElemTypestack[MAXLEN];inttop;}STACK;typedefstructQueEle{intx,y;intpre;}QueElem;typedefstructQueTag{QueElemqueue[MAXLEN];intfront,rear;}QUEUE;typedefstructmoved{intdx,dy;}MOVE;/*定义栈元素的数据类型*//*定义顺序栈结构*//*定义队列元素的数据类型*//*定义方向位移数组元素的类型*/voidIniMaze(intmaze[][N2]);/*初始化迷宫*/voidIniMove(MOVEmove[]);voidIniStack(STACK*s);intPush(STACK*s,ElemTypex);ElemTypePop(STACK*s);intshortpath(intmaze[][N2],MOVEmove[],QUEUE*p);voiddraw(intmaze[][N2],STACK*s);voidIniQueue(QUEUE*s);/*初始化队列*/voidprintpath(QUEUE*p,STACK*s);/*显示迷宫通路*/voidmain(){/*寻找迷宫通路程序*/STACK*s;QUEUE*p;intmaze[M2][N2],f;MOVEmove[8];IniMaze(maze);/*初始化迷宫数组*/getch();s=(STACK*)malloc(sizeof(STACK));IniStack(s);p=(QUEUE*)malloc(sizeof(QUEUE));IniQueue(p);/*初始化队列*/IniMove(move);/*初始化位移方向数组*/f=shortpath(maze,move,p);/*寻找迷宫中的一条最短路径*/if(f==True){printpath(p,s);/**/draw(maze,s);}elseprintf("\n此迷宫无通路\n");/*如果没找到，显示"无通路"*/getch();}/*main*//*初始化迷宫*/maze[i][j]=1;voidIniMaze(intmaze[][N2]){/*初始化迷宫*/maze[i][j]=1;inti,j,num;printf("\n");maze[i][j]=1;maze[i][j]=1;maze[i][j]=1;maze[i][j]=1;maze[i][j]=1;maze[i][j]=1;for(i=0,j=N+1;i<=M+1;i++)for(i=0,j=0;j<=N+1;j++)for(i=M+1,j=0;j<=N+1;j++)for(i=1;i<=M;i++){for(j=1;j<=N;j++){num=(800*(i+j)+1500)%327;if((num<150)&&(i!=M||j!=N))else maze[i][j]=0; }}for(i=0;i<=M+1;i++){printf("\n");for(j=0;j<=N+1;j++){if((i==0)&&(j==0)||(i==M+1)&&(j==N+1))printf("%3d",0);elseprintf("%3d",maze[i][j]);}}printf("\n");}/*IniMaze*/voidIniMove(MOVEmove[]){move[0].dx=0;move[0].dy=1;move[1].dx=1;move[1].dy=1;move[2].dx=1;move[2].dy=0;move[3].dx=1;move[3].dy=-1;move[4].dx=0;move[4].dy=-1;move[5].dx=-1;move[5].dy=-1;move[6].dx=-1;move[6].dy=0;move[7].dx=-1;move[7].dy=1;}voidIniStack(STACK*s){s->top=-1;}/*IniStack*/intPush(STACK*s,ElemTypex){/*数据元素x进入s指针所指的栈*/if(s->top==MAXLEN-1)/*栈满处理*/return(False);else{ /*进栈*/s->stack[++s->top]=x;return(True);}}/*EndofPush*/ElemTypePop(STACK*s){ElemTypeelem;if(s->top<0){ /*栈空处理*/elem.x=Null;elem.y=Null;elem.dir=Null;return(elem);}else{s->top--;return(s->stack[s->top+1]);}}/*Pop*/voidIniQueue(QUEUE*s){ /*初始化队列*/s->front=1;/*设置队头在数组下标为1处*/s->rear=1;return;}intshortpath(intmaze[][N2],MOVEmove[],QUEUE*p