数据结构第五讲

1、数据结构数据结构第五讲第五讲数据结构 第三章第三章栈和队列栈和队列第3章 栈 和 队 列 内容提要： 1 1，本章主要介绍了栈与队列两种数据结构，本章主要介绍了栈与队列两种数据结构以及他们的顺序存储与链式存储方式，并在此以及他们的顺序存储与链式存储方式，并在此基础上介绍了一些基于栈与队列的应用。基础上介绍了一些基于栈与队列的应用。 2 2，关于递归程序的设计。，关于递归程序的设计。本章要点3.1 栈栈3.1.1 栈的定义及运算栈的定义及运算3.1.2 栈的顺序存储结构及基本运算的实现栈的顺序存储结构及基本运算的实现3.1.3 栈的链式存储结构及基本运算的实现栈的链式存储结构及基本运算的实现3.

2、2 栈的应用栈的应用 3.2.1 中缀表达式中缀表达式 3.2.2 中缀表达式转换为等价的后缀表达式中缀表达式转换为等价的后缀表达式 3.2.3 后缀表达式及求值后缀表达式及求值3.3 栈与递归栈与递归 3.3.1 递归与递归程序的设计递归与递归程序的设计 3.3.2 递归程序的执行过程递归程序的执行过程 3.3.3 递归的应用举例递归的应用举例3.4 队队 列列3.4.1 队列的定义和运算队列的定义和运算3.4.2 队列的顺序存储结构及基本运算的实现队列的顺序存储结构及基本运算的实现3.4.3 队列的链式存储结构及基本运算的实现队列的链式存储结构及基本运算的实现3.4.4 队列的应用举例队列

3、的应用举例本章小结本章小结3.1.1 栈的定义栈的定义栈是限制在表的一端进行插入和删除的线性表。栈是限制在表的一端进行插入和删除的线性表。栈的相关术语：栈顶、栈底、空栈、进栈（压栈）、出栈等。栈的相关术语：栈顶、栈底、空栈、进栈（压栈）、出栈等。 栈顶（栈顶（top）：允许插入和删除的一端）：允许插入和删除的一端 栈底（栈底（bottom）：不允许插入和删除的一端）：不允许插入和删除的一端进栈的顺序是进栈的顺序是e1、e2。出栈的顺序为出栈的顺序为e2、e1。所以栈又称为后进先出线性表所以栈又称为后进先出线性表(Last In First Out)，简称，简称 LIFO表表或称先进后出线性表。

4、或称先进后出线性表。Top1Top0Top1Top0Top1课堂练习若进栈序列为若进栈序列为3，5，7，9，进栈过程中可以出栈，进栈过程中可以出栈，则不可能的一个出栈次序是（则不可能的一个出栈次序是（ ）。）。 (a) 7,5,3,9 (b) 9,7,5,3 (c) 7,5,9,3 (d) 9,5,7,33.1.1 栈的运算栈的运算（1）初始化栈）初始化栈 InitStack(S) 初始条件：初始条件：栈栈S不存在。不存在。 操作结果：操作结果：构造一个空栈构造一个空栈S。（2）压栈（入栈）压栈（入栈） Push(S, e) 初始条件初始条件：栈：栈S已存在。已存在。 操作结果：操作结果：插入

5、元素插入元素e为新的栈顶元素。为新的栈顶元素。（3）出栈）出栈Pop(S, e) 初始条件：初始条件：栈栈S已存在且非空。已存在且非空。 操作结果：操作结果：删除删除S的栈顶元素，并用的栈顶元素，并用e返回其值。返回其值。（4） GetTop(S, &e) 初始条件：初始条件：栈栈S已存在且非空。已存在且非空。 操作结果：操作结果：用用e返回返回S的栈顶元素。的栈顶元素。 （5）StackEmpty(S) 初始条件：初始条件：栈栈S已存在。已存在。 操作结果：操作结果：若栈若栈S为空栈，则返回为空栈，则返回TRUE(1)，否则，否则FALSE(0)。课堂练习 用一维数组设计栈，初态是用

6、一维数组设计栈，初态是栈空，栈空，top=-1。现有输入序列是现有输入序列是 a、b、c、d，经过，经过 push、push、pop、push、pop、push操作后操作后。输出序列是（输出序列是（ ）栈顶指针是（栈顶指针是（ ）b，c1本章要点3.1 栈栈3.1.1 栈的定义及运算栈的定义及运算3.1.2 栈的顺序存储结构及基本运算的实现栈的顺序存储结构及基本运算的实现3.1.3 栈的链式存储结构及基本运算的实现栈的链式存储结构及基本运算的实现3.2 栈的应用栈的应用 3.2.1 中缀表达式中缀表达式 3.2.2 中缀表达式转换为等价的后缀表达式中缀表达式转换为等价的后缀表达式 3.2.3

7、后缀表达式及求值后缀表达式及求值3.3 栈与递归栈与递归 3.3.1 递归与递归程序的设计递归与递归程序的设计 3.3.2 递归程序的执行过程递归程序的执行过程 3.3.3 递归的应用举例递归的应用举例3.4 队队 列列3.4.1 队列的定义和运算队列的定义和运算3.4.2 队列的顺序存储结构及基本运算的实现队列的顺序存储结构及基本运算的实现3.4.3 队列的链式存储结构及基本运算的实现队列的链式存储结构及基本运算的实现3.4.4 队列的应用举例队列的应用举例本章小结本章小结3.1.2 顺序栈的结构及运算顺序栈的结构及运算(1)栈的顺序存储简称顺序栈。 通常由一个一维数组dataMAXSIZE

8、和一个记录栈顶元素位置的变量(top)组成 说明：说明：toptop指向栈顶元素当前位置。指向栈顶元素当前位置。012MAXSIZE-1012MAXSIZE-1本章要点4.1 栈4.1.1 栈的抽象数据类型4.1.2 顺序栈顺序栈4.1.3 链栈4.1.4 栈的应用4.2 队队 列列4.2.1 队列的抽象数据类型4.2.2 顺序队列4.2.3 链队列4.2.4 队列的应用4.3 递递 归归4.3.1 递归算法书写要点及方法4.3.2 递归过程的调用和返回4.3.3 递归的应用 4.3.4 递归函数的非递归化本章小结本章小结栈的顺序存储示意图：说明：也可以将说明：也可以将basebase指向下标

9、为指向下标为-1-1的位置，的位置，toptop指向栈顶元素当前位置。指向栈顶元素当前位置。4.1.2 顺序栈顺序栈(1)012MAXSIZE-1#define MAXSIZE 100typedef struct ElemType dataMAXSIZE; int top;Stack;顺序栈的描述顺序栈的描述1) 栈的初始化InitStack(Stack *S) void InitStack(Stack *S) s-top=-1; 顺序栈的运算顺序栈的运算(1)012MAXSIZE-1Top12) 压栈(入栈)操作int PushStack(Stack *S,ElemType e) /进栈操作

10、 if(S-top=MAXSIZE-1) prinft(“n Stack is full”); return 0; s-top+; s-datas-top=e; return 1;顺序栈的运算顺序栈的运算(2)x2X1012MAXSIZE-1Top1eTop23) 判断栈是否为空判断栈是否为空 int EmptyStack() /判断栈是否为空判断栈是否为空 if (S-top=-1) return 1; else return 0; 顺序栈的运算顺序栈的运算(3)012MAXSIZE-1Top12)出栈操作int PopStack(Stack *S,ElemType *e) / if(Emp

11、ty(S) prinft(“n Stack is empty”); return 0; *e=S-datas-top; s-top-; return 1;顺序栈的运算顺序栈的运算(4)x2X1012MAXSIZE-1Top15) 取栈顶元素操作int GetTop (Stack *S,ElemType *x)/取栈顶元素操作 if(Empty(S) printf(“Stack is Empty”); return 0; else *x=S-dataS-top; return 1; 顺序栈的运算顺序栈的运算(5)x2X1012MAXSIZE-1Top1栈的应用举例栈的应用举例 例一、例一、 数制转换数制转换:编写程序实现对于一个任意的十编写程序实现对于一个任意的十进制数打印输出与之等值的八进制数。进制数打印输出与之等值的八进制数。 十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于“除d求余”原理。 例如：例如：（1348)10 = ( ？ )8 N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 22504void co