实验4 队列及其应用

《实验4 队列及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验四队列及其应用一、实验教学目的(1)  掌握队列的特点及其描述方法。(2) 用链式结构实现一个队列。(3)掌握队列的各种基本操作。(4)掌握队列的简单应用程序。二、实验教学内容1、实验题目利用队列的性质与基本运算编程解决迷宫问题2、实验要求：(1)选择合适的存储结构（循环队列）表示队列，解决队空、队满判断条件相同的矛盾。(2)实现基于循环队列的存储结构的基本操作，初始化、队空/满判断，入队、出队、取队头元素，求队列长度等。(3)对所写出的算法进行时间复杂度分析。3、实验预备知识（1）队列的定义及队列的“先进先出”的特点。（2）队列的顺序与链式存储结构及队列的初始

2、化、入队、出队、取队头元素等基本操作。4、实验环境（1）一台运行Windows2000/XP操作系统的计算机（2）选用turboc或visualc++5、实验说明（1）类型定义#defineMAXSIZE100/*队列的最大长度*/typedefstruct{ElemTypeelem[MAXSIZE]；intfront，rear；intlen;}SqQueue；/*顺序队列的类型定义*/（2）注意问题①重点理解队列的算法思想，能够根据实际情况选择合适的存储结构②队列的算法是后续实验的基础（广义表、树、图、查找、排序等）三、实验内容和实验步骤：（由学生填写）四、实验用

3、测试数据和相关结果分析：（由学生填写）五、实验总结：（由学生填写）六、参考程序模板/*迷宫求解（用两种方法实现：一种用栈实现，另一种用队列实现）。该算法用队列实现。*/#include"stdio.h"#include"stdlib.h"#defineM6#defineN8#defineMAXSIZEM*Ntypedefstruct{intx,y;intpre;}ElemType;/*队列中元素类型定义*/typedefstruct{ElemTypeelem[MAXSIZE];intfront,rear,len;}SqQueue;/*顺序队列类型定义*/typede

4、fstruct{intx,y;}item;voidInitQueue(SqQueue*q)/*队列的初始化*/{q->front=q->rear=0;q->len=0;}intQueueEmpty(SqQueueq)/*判队空*/{if(q.len==0)return1;elsereturn0;}voidEnQueue(SqQueue*q,ElemTypee)/*入队*/{if(q->len==MAXSIZE)printf("队列满！");else{q->elem[q->rear]=e;q->rear=(q->rear+1);q->len++;}}voidDeQ

5、ueue(SqQueue*q,ElemType*e)/*出队*/{if(q->len==0)printf("该队列为空队列！");else{*e=q->elem[q->front];q->front=(q->front+1);q->len--;}}voidGetHead(SqQueueq,ElemType*e)/*取队头元素*/{if(q.len==0)printf("该队列为空队列！");else*e=q.elem[q.front];}voidprintpath(SqQueueq)/*输出迷宫路径*/{inti;i=q.rear-1;do{printf("

6、(%d,%d)<--",(q.elem[i]).x,(q.elem[i]).y);i=(q.elem[i]).pre;/*回溯*/}while(i!=-1);printf("");}intmazepath(intmaze[M+2][N+2],itemmove[8])/*采用队列的迷宫算法。Maze[M+2][N+2]表示迷宫数组，move[8]表示坐标增量数组*/{//请自行完成}voidmain(){intmaze[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

7、,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}};itemmove[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};printf("%d",mazepath(maze,move));system("pause");}