栈的操作(实验报告)(3)

do

{ printf("\n 链队列的基本操作\n ");

printf("=========================================\n");

printf(" 主菜单 \n");

printf("=========================================\n");

printf(" 1 初始化并建立链队列 \n");

printf(" 2 入链队列 \n");

printf(" 3 出链队列 \n");

printf(" 4 遍历链队列 \n");

printf(" 5 结束程序运行 \n");

printf("==========================================\n");

scanf("%d",&cord);

switch(cord)

{ case 1:

{ p=(Lqueue *)malloc(sizeof(Lqueue));

creat(p);

display(p);

}break;

case 2:

{ printf("请输入队列元素的值：x=");

scanf("%d",&x);

Lappend(p,x);

display(p);

}break;

case 3:

{ printf("出链队列元素：x=%d\n",Ldelete(p));

栈的基本操作,附带源程序

}

display(p); }break; case 4: {display(p);}break; case 5: {exit (0);} } }while (cord<=5);

3.4 提高实验

[实验1] 迷宫的求解

实验内容与要求:

迷宫只有两个门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到出口的路径。

分析:

迷宫问题是栈应用的一个典型例子。求解过程可采用回溯法。回溯法是一种不断试探且及时纠正错误的搜索方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向 ; 若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。

在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的下标及从该点前进的方向，栈中保存的就是一条迷宫的通路。

为了确保程序能够终止，调整时，必须保证曾被放弃过的填数序列不被再次试验，即要求按某种有序模型生成填数序列。给解的候选者设定一个被检验的顺序，按这个顺序逐一生成候选者并检验。

参考程序::

#include<stdio.h>

#include<stdlib.h>

#define n1 10

#define n2 10

typedef struct node

{

int x; //存x坐标

int y; //存Y坐标

int c; //存该点可能的下点所在的方向,1表示向右,2向上,3向左,4向右

栈的基本操作,附带源程序

}linkstack;

linkstack top[100];

//迷宫矩阵

int maze[n1][n2]={1,1,1,1,1,1,1,1,1,1,

0,0,0,1,0,0,0,1,0,1,

1,1,0,1,0,0,0,1,0,1,

1,0,0,0,0,1,1,0,0,1,

1,0,1,1,1,0,0,0,0,1,

1,0,0,0,1,0,0,0,0,0,

1,0,1,0,0,0,1,0,0,1,

1,0,1,1,1,0,1,1,0,1,

1,1,0,0,0,0,0,0,0,1,

1,1,1,1,1,1,1,1,1,1,};

int i,j,k,m=0;

main()

{//初始化top[],置所有方向数为左

for(i=0;i<n1*n2;i++)

{top[i].c=1;}

printf("the maze is:\n");

//打印原始迷宫矩阵

for(i=0;i<n1;i++)

{for(j=0;j<n2;j++)

printf(maze[i][j]?"* ":" ");

printf("\n"); }

i=0;top[i].x=1;top[i].y=0;

maze[1][0]=2;

/*回溯算法*/

do{

if(top[i].c<5) //还可以向前试探

{if(top[i].x==5 && top[i].y==9) //已找到一个组合

{ //打印路径

printf("The way %d is:\n",m++);

for(j=0;j<=i;j++)

{printf("(%d,%d)-->",top[j].x,top[j].y);}

printf("\n");

//打印选出路径的迷宫

for(j=0;j<n1;j++)

{for(k=0;k<n2;k++)

{if(maze[j][k]==0) printf(" ");

else if(maze[j][k]==2) printf("O ");

else printf("* ");}

printf("\n"); }

maze[top[i].x][top[i].y]=0;

top[i].c = 1;

栈的基本操作,附带源程序

i--;

top[i].c += 1;

continue;}

switch (top[i].c) //向前试探

{

case 1:

{ if(maze[top[i].x][top[i].y+1]==0)

{i++;

top[i].x=top[i-1].x;

top[i].y=top[i-1].y+1;

maze[top[i].x][top[i].y]=2;}

else

{top[i].c += 1;}

break;}

case 2:

{if(maze[top[i].x-1][top[i].y]==0)

{i++;

top[i].x=top[i-1].x-1;

top[i].y=top[i-1].y;

maze[top[i].x][top[i].y]=2;}

else

{top[i].c += 1;}

break;}

case 3:

{if(maze[top[i].x][top[i].y-1]==0)

{i++;

top[i].x=top[i-1].x;

top[i].y=top[i-1].y-1;

maze[top[i].x][top[i].y]=2;}

else

{top[i].c += 1;}

break;}

case 4:

{if(maze[top[i].x+1][top[i].y]==0)

{i++;

top[i].x=top[i-1].x+1;

top[i].y=top[i-1].y;

maze[top[i].x][top[i].y]=2;}

else

{ top[i].c += 1;}

break;}

}

}

else //回溯

栈的基本操作,附带源程序

{if(i==0) return; //已找完所有解

maze[top[i].x][top[i].y]=0;

top[i].c = 1;

i--;

top[i].c += 1;}

}while(1);

}

[实验2] 停车场管理

实验内容与要求:

设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。 试为停车场编制按上述要求进行管理的模拟程序。

分析:

综合利用栈和队列模拟停车场管理，学习利用栈和队列解决实际问题。

以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离 …… 此处隐藏：2969字，全部文档内容请下载后查看。喜欢就下载吧 ……