第03章 栈和队列(严蔚敏数据结构C语言版第二版).ppt

* 北京林业大学信息学院 需要解决的问题： 1、表示迷宫的数据结构 2、试探方向 3、栈的设计 4、防止重复到达某点，避免发生死循环 迷宫求解 * 北京林业大学信息学院 1、表示迷宫的数据结构 表示一个m行n列迷宫： 用maze[m][n]表示，0≤im,0≤jn maze[i][j] = 0 通路 maze[i][j] = 1 不通 改进： 用maze[m+2][n+2]表示 且maze[i][j]=1，i=0或m＋1, j=0或n＋1 入口坐标为（1，1），出口坐标为（m，n） 迷宫求解 * 北京林业大学信息学院 0 1 2 3 4 5 6 7 8 9 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0 1 0 1 2 1 0 0 1 0 0 0 1 0 1 3 1 0 0 0 0 1 1 0 0 1 4 1 0 1 1 1 0 0 0 0 1 5 1 0 0 0 1 0 0 0 0 1 6 1 0 1 0 0 0 1 0 0 1 7 1 0 1 1 1 0 1 1 0 1 8 1 1 0 0 0 1 0 0 0 1 9 1 1 1 1 1 1 1 1 1 1 * 北京林业大学信息学院 迷宫的定义： #define m 8 /*迷宫的实际行*/ #define n 8 /*迷宫的实际列*/ int maze [m+2][n+2] ; 2、试探方向 表示位置的类型PosType定义如下： typedef struct { int x，y; } PosType ; 迷宫求解 * 北京林业大学信息学院 试探顺序规定为：从正东沿顺时针方向 与点(x，y)相邻的4个点及坐标 (x,y) (x,y+1) (x,y-1) (x+1,y) (x-1,y) 迷宫求解 * 北京林业大学信息学院 3、栈的设计 栈中每个元素的组成： 通道块在路径上的序号 坐标位置 前进方向（东为1，南为2，西为3，北为4） 栈元素的类型定义： typedef struct { int ord; PosType seat; int di; }SElemType; 迷宫求解 * 北京林业大学信息学院 4、防止重复到达某点 走过不通之处要加以标记（MarkPrint操作） 迷宫求解 * 北京林业大学信息学院 【案例分析】 设置两个队列分别存放男士和女士入队者 假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。 当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。 此时，若某队仍有等待配对者，则输出此队列中排在队头的等待者的姓名，此人将是下一轮舞曲开始时第一个可获得舞伴的人。 案例3.4 ：舞伴问题 * 北京林业大学信息学院 【数据结构】 //- - - - - 跳舞者个人信息- - - - - typedef struct { char name[20]; //姓名 char sex; //性别，F表示女性，M表示男性 }Person; //- - - - - 队列的顺序存储结构- - - - - #define MAXQSIZE 100 //队列可能达到的最大长度 typedef struct { Person *base; //队列中数据元素类型为Person int front; //头指针 int rear; //尾指针 }SqQueue; SqQueue Mdancers,Fdancers; //分别存放男士和女士入队者队列 * 北京林业大学信息学院 【算法步骤】 ① 初始化Mdancers队列和Fdancers队列。 ② 反复循环，依次将跳舞者根据其性别插入Mdancers队列或Fdancers队列。 ③ 当Mdancers队列和Fdancers队列均为非空时，反复循环，依次输出男女舞伴的姓名。 ④ 如果M