第三章_栈与队列.ppt

第三章 栈和队列 3.1 栈 3.1.1 抽象数据类型栈的定义 3.1.2 栈的表示和实现 3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.4 行编辑程序 3.2.5 迷宫求解 3.2.5 表达式求值 第三章 栈和队列 3.3 栈与递归的实现 略 3.4 队列 3.4.1 抽象数据类型队列的定义 3.4.2 链队列-队列的链式表示与实现 3.4.4 循环队列-队列的顺序表示与实现 3.4 离散事件模拟 略 第三章 栈和队列 3.1 栈 3.1.1 抽象数据类型栈的定义 3.1.2 栈的表示和实现 顺序栈、链栈 第三章 栈和队列 3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.4 行编辑程序 3.2.5 迷宫求解 3.2.5 表达式求值 第三章 栈和队列 3.4 队列 3.4.1 抽象数据类型队列的定义 3.4.2 链队列-队列的链式表示与实现 3.4.4 循环队列-队列的顺序表示与实现 入口 出口 3.2.4 迷宫求解 入口 出口 3.2.4 迷宫求解 如果是你，你如何走迷宫？ 入口 出口 3.2.4 迷宫求解 如果是你，你如何走迷宫？ 如果给你一个粉笔呢？ 队列(Queue)是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。　　 例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。 　 当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an ，也就是说队列的修改是依先进先出的原则进行的。 3.4.1 队列的定义 1、队头 允许删除的一端称为队头(front) 2、队尾 允许插入的一端称为队尾(rear)。 　 3.4.1 队列的定义-基本名词 下图是队列的示意图： 　　　　　 　　　　　　 a1　a2　…　an 　　 　　　　　 出队 入队 队头 队尾 队列的抽象数据定义见书Ｐ59 3.4.1 队列的定义 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由一个头指针唯一确定。 和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型LinkQueue定义为一个结构类型如下： 3.4.2 链队列—队列的链式表示与实现 typedef struct queuenode{ datatype data; struct queuenode *next; }queuenode; typedef struct{ queuenode *front; queuenode *rear; }linkqueue; 3.4.2 链队列-定义 1、初始化 void initqueue(linkqueue *q) { q–front=q–rear=null; } 2、空队列判断 int queueempty(linkqueue *q) { return q–front==null q–rear==null; } 3.4.2 链队列-基本运算 3、入队操作 void enqueue(linkqueue *q,datatype x) { queuenode *p p=(queuenode * )malloc(sizeof(queuenode)); p–data=x; p–next=null; if(queueempty(q)) q–front=q–rear=p; else{ q–rear–next=p; q–rear=p; } } 3.4.2 链队列-基本运算 4、出队操作 Datatype dequeue(linkqueue *q) { datatype x; queueno