一眼看穿---栈和队列剖析.ppt

* 用计算机实现上述求解的搜索过程可以采用两种不同的策略： 一种是广度优先(breadth_first)搜索， 另一种是深度优先(depth_first)。 －－实现这两种策略所依赖的数据结构正好是前面介绍的队列和栈。 本节讨论队列的应用，所以下面重点介绍广度优先的策略。 3.6 队列的应用—农夫过河问题* 模拟农夫过河问题： 用四位二进制数分别顺序表示农夫、狼、白菜和羊的位置。 0表示在南岸，1表示在北岸 Path：15，6，14，2，11，1，9，0 从初始状态0到最终状态15的动作序列为： * 线 性 表 存储结构 运 算 队列 链 表 顺序表 栈 顺序栈 链 栈 顺序队列 链队列 线性表小结 * 顺序表 typedef int datatype ; #define MAXNUM 1024 typedef struct { datatype data[MAXNUM] ; int last ; } sequenlist; * 链 表 typedef int datatype; typedef struct node { datatype data; struct node *next; } linklist; linklist *head, *p; * 顺序栈 typedef int datatype; #define MAXNUM 64 typedef struct { datatype data[MAXNUM]; int top; } PSeqStack; PSeqStack *s; * 链 栈 typedef int datatype; typedef struct node { datatype data; struct node *next; } linkstack; linkstack *top; * 顺序队列 typedef struct { datatype data[MAXNUM]; int f,r; } sequeue; sequeue *sq; * 链队列 typedef struct { linklist *f , *r; } linkqueue; linkqueue *q; * 队列 只允许在表的一端进行插入，而在另一端 进行删除。 队头 允许删除的一端 队尾 允许插入的一端 队列的概念 出队 入队 队头 队尾 a1 a2 an ... 队列是先进先出表 * 队列的基本运算： 创建一个空队列 Queue createEmptyQueue ( void ) 判队列是否为空队列 int isEmptyQueue ( Queue qu ) 往队列中插入一个元素 void enQueue ( Queue qu, DataType x ) 从队列中删除一个元素 void deQueue ( Queue qu ) 求队列头部元素的值 DataType frontQueue ( Queue qu ) 队列的运算 * 3.5 队列的实现 3.5.1. 顺序队列 3.5.2. 链队列 * 3.5.1 顺序队列 队列的顺序存储结构简称为顺序队列。顺序队 列实际上是运算受限的顺序表。 由于队列的队头和队尾的位置均是变化的，因 而要设置两个指针，分别指示当前队头元素和队尾 元素在向量空间中的位置。 * #define MAXNUM 100 struct SeqQueue { datatype q[MAXNUM]; int f,r; }; typedef struct SeqQueue *PSeqQueue; PSeqQueue sq; 顺序队列的定义 3.5.1 顺序队列 f r 7 6 5 4 3 2 1 0 k1 k2 k3 f r r f k8 k7 ①队列空 ④队列数组越界 顺序队列 ②约定 ③队列满 k1 k2 k3 f k8 r k4 k5 k6 k7 * 开始： sq-f=0; sq-r=0; 入队： sq-data[sq-r]=x; sq-r++; 出队： sq-f++; 顺序队列的入队和出队 3.5.1 顺序队列 * 元素个数（队列长度）:（sq-r) - (sq-f) 若（sq-r) - (sq-f)=0 ，则队列长度 为0，即空队