实验三 队列及其应用
一、 实验教学目的
(1) 掌握队列的特点及其描述方法。 (2) 用链式结构实现一个队列。 (3) 掌握队列的各种基本操作。 (4) 掌握队列的简单应用程序。
二、 实验教学内容 1、 实验题目
（1）链队子系统的设计与实现 ①设计一个字符型的链队列；
②编写队列的进队、出队、读队头元素、显示队列中全部元素程序；
③设计一个选择式菜单，以菜单方式选择队列的各种基本操作。菜单形式如下：
队 列 子 系 统
************************************************* * 1----------进 队 * * 2----------出 队 * * 3----------读 队 头 元 素 * * 4----------显 示 * * 0----------退 出 * ************************************************* 请选择菜单号：
（2）利用队列的性质与基本运算编程解决迷宫问题 2、实验要求：
(1)选择合适的存储结构（循环队列）表示队列，解决队空、队满判断条件相同的矛盾。
(2)实现基于循环队列的存储结构的基本操作，初始化、队空/满判断，入队、出队、取队头元素，求队列长度等。
(3)对所写出的算法进行时间复杂度分析。
3、实验预备知识
（1）队列的定义及队列的“先进先出”的特点。
（2）队列的顺序与链式存储结构及队列的初始化、入队、出队、取队头元素等基本操作。
4、实验环境
（1）一台运行 Windows 2000/XP 操作系统的计算机 （2）选用 turbo c或visual c++
5、实验说明
（1）类型定义 ①顺序队列
#define MAXSIZE 100 /*队列的最大长度*/ typedef struct
{ElemType elem[MAXSIZE]；
int front，rear； int len;
}SqQueue； /*顺序队列的类型定义*/ ②链队列
typedef struct node{
ElemType data; struct node *next;
}QNode; /*链队结点类型的定义*/ typedef struct
{QNode *front, *rear;
}LinkQueue; /*链队类型的定义*/ （2）注意问题
①重点理解队列的算法思想，能够根据实际情况选择合适的存储结构
②队列的算法是后续实验的基础（广义表、树、图、查找、排序等）
三、实验内容和实验步骤：（由学生填写）
四、实验用测试数据和相关结果分析：（由学生填写） 五、实验总结：（由学生填写） 六、参考程序模板
第1题：链队子系统的设计与实现 #include
/*初始化并建立链队列*/ void Creat(LinkQueue *q) {
//请自行完成 }
main()
{ LinkQueue *p;
p=(LinkQueue *)malloc(sizeof(LinkQueue)); int x,cord;
printf(\第一次操作请选择初始化并建立链队列！*****\\n \ do
{ printf(\ 链队列的基本操作\\n \
printf(\ printf(\ 主菜单 \\n\
printf(\ printf(\ 1 初始化并建立链队列 \\n\ printf(\ 2 入链队列 \\n\ printf(\ 3 出链队列 \\n\ printf(\ 4 遍历链队列 \\n\ printf(\ 5 结束程序运行 \\n\
printf(\ scanf(\ switch(cord) { case 1:
{
Creat(p); Display(p);
}break; case 2:
{ printf(\请输入队列元素的值：x=\ scanf(\ EnQueue(p,x); Display(p); }break; case 3:
{ DeQueue(p, &x); printf(\出链队列元素：x=%d\\n\ Display(p); }break; case 4:
{Display(p);}break;
case 5:
{exit (0);} }
}while (cord<=5); }
/*迷宫求解（用两种方法实现：一种用栈实现，另一种用队列实现）。该算法用队列实现。*/ #include \#include \
#define M 6 #define N 8
#define MAXSIZE M*N
typedef struct{ int x,y; int pre;
}ElemType; /*队列中元素类型定义*/
typedef struct{ int x,y; }item;
#include \顺序队列.h\
void printpath(SqQueue q) /*输出迷宫路径*/ {int i;
i=q.rear-1; do{
printf(\ i=(q.elem[i]).pre; /*回溯*/ }while(i!=-1); printf(\}
int mazepath(int maze[M+2][N+2],item move[8])
/*采用队列的迷宫算法。Maze[M+2][N+2]表示迷宫数组，move[8]表示坐标增量数组*/ {
//请自行完成 }
void main() {int
maze[M+2][N+2]={{1,1,1,1,1,1,1,1,1,1},{1,0,1,1,1,0,1,1,1,1},{1,1,0,1,0,1,1,1,1,1}, {1,0,1,0,0,0,0,0,1,1},{1,0,1,1,1,0,1,1,1,1},{1,1,0,0,1,1,0,0,0,1},{1,0,1,1,0,0,1,1,0,1}, {1,1,1,1,1,1,1,1,1,1}};
item move[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}}; printf(\ system(\}