目录

3.2栈和队列案例引入

一.进制转换

1.把十进制数159转换为八进制数

二.括号匹配的检验

三.表达式求值

1.算符优先算法

 四.舞伴问题

3.3栈的表示和操作的实现

一.栈的抽象数据类型的类型定义

 二.栈的相关操作

 1.LnitStack（&S）初始化操作

2.DestroyStack(&S)销毁栈操作

3.StackLength(S)求栈的长度

4.GetTop（S，&e）取栈顶元素

5.ClearStack（&S）栈置空操作

6.Push（&S，e）入栈操作

7.Pop（&S,&e）出栈操作

三.栈的表示和实现

1.栈的两种实现方式

2.存储方式

3.使用数组作为顺序栈存储方式的特点：

3.3.2顺序栈的表示和实现

一.数据类型定义

1.顺序栈的表示

 2.顺序栈的实现

 3.3.3链栈的表示和实现

一.链栈的表示

1.链栈的实现

 3.4栈与递归

一.递归的定义

1.递归定义

2.三种情况常常用到递归方法

3.递归问题——用分治法求解

 二.函数的调用

1.函数调用的过程

2.嵌套调用

 三.递归函数调用的实现

1.递归的优缺点

2.递归转化非递归

3.5队列的表示和操作实现

一.队列相关概念

1.相关术语

2.队列的抽象数据类型定义

 二.队列的顺序表示和实现

1.队列的顺序表示和实现

 2.出队，入队相关问题

 3.循环队列

 三.循环队列的类型定义

1.初始化

2.求队列的长度

3.入队

4. 出队

5.取队头元素

 3.5.3队列的链式表示和实现

一.链队列的表示

 1.链队列的类型定义

 2.链队列运算指针变化状况

二.链队列的操作

1.初始化

 2.销毁

3. 将元素e入队

 4.出队

5.求链队列的队头元素

---

3.2栈和队列案例引入

一.进制转换

1.把十进制数159转换为八进制数

二.括号匹配的检验

（1）假设表达式中允许包含两种括号：圆括号和方括号

（2）其嵌套的顺序随意，即：

三.表达式求值

1.算符优先算法

 四.舞伴问题

3.3栈的表示和操作的实现

一.栈的抽象数据类型的类型定义

 二.栈的相关操作

 1.LnitStack（&S）初始化操作

操作结果：构造一个空栈S

2.DestroyStack(&S)销毁栈操作

初始条件：栈S已存在

操作结果：若栈S为空栈，则返回TEUE,否则FALSE

3.StackLength(S)求栈的长度

初始条件：栈S已存在

操作结果：返回S的元素个数，即栈的长度

4.GetTop（S，&e）取栈顶元素

初始条件：栈S已存在且非空

操作结果：用e返回S的栈顶元素

5.ClearStack（&S）栈置空操作

初始条件：栈S已存在

操作结果：将S清为空栈

6.Push（&S，e）入栈操作

初始条件：栈S已存在

操作结果：插入元素e为新的栈顶元素

7.Pop（&S,&e）出栈操作

初始条件：栈S已存在且非空

操作结果：删除S的栈顶元素an，并用e返回其值

三.栈的表示和实现

1.栈的两种实现方式

由于栈本身就是线性表，于是栈也有顺序存储和链式存储两种实现那方式

• 栈的顺序存储——顺序栈
• 栈的链式存储——链栈

2.存储方式

（1）存储方式：同一般线性表的顺序存储结构完全相同

（2）利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端。

• 附设top指针，指示栈顶元素在顺序栈中的位置
• 另设base指针，指示栈底元素在顺序栈中的位置

但是，为了方便操作，通常top指示真正的栈顶元素之上的下标地址

• 用stacksize表示栈可使用的最大容量

3.使用数组作为顺序栈存储方式的特点：

简单，方便，但容易溢出

• 上溢：栈已经满了，但又要压入元素
• 下溢：栈已经空了，还要弹出元素

3.3.2顺序栈的表示和实现

一.数据类型定义

1.顺序栈的表示

 

 2.顺序栈的实现

（1）初始化

1. SqStack：类型-->#define MAXSIZE 100

                                  typedef struct{

                                             SElemType*base;

                                             SElemType*top;

                                             int stacksize;

                                 }SqStack;

2.new后面 接数据类型+【大小】（数组）

（2）判断顺序栈是否为空

 （3）清空顺序栈

 （4）销毁顺序栈

 （5）顺序栈的入栈

 （6）顺序栈的出栈

 3.3.3链栈的表示和实现

一.链栈的表示

• 链栈是运算受限的单链表，只能在链表头部进行操作

1.链栈的实现

（1）链栈的初始化

 （2）判断链栈是否为空

（3）链栈的入栈

 （4）链栈的出栈

 （5）取栈顶元素

 3.4栈与递归

一.递归的定义

1.递归定义

• 若一个对象部分地包括它自己，或用它自己给自己定义，则称这个对象是递归；
• 若一个过程直接地或间接地调用自己，则称这个过程是递归的过程
• 例如：递归求n的阶乘

2.三种情况常常用到递归方法

• 递归定义的数学函数
• 具有递归特性的数据结构
• 可递归求解的问题

（1）递归定义的数学函数

 （2）具有递归特性的数据结构

（3）可递归求解的问题

3.递归问题——用分治法求解

（1）分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解。

（2）必备的三个条件

• 能将一个问题转变成一个新问题，而新问题与原问题的解法相同或者同类，不同的仅是处理的对象，且这些处理对象是变化有规律的
• 可以通过上述转化而使问题简化
• 必须有一个明确的递归出口，或称为递归的边界

（3）分治法求解递归问题算法的一般形式

 二.函数的调用

1.函数调用的过程

（1）调用前，调用后

• 将实参，返回地址等传递给被调用函数
• 为被调用函数的局部变量分配储存区
• 将控制转移到被调用函数的入口

（2）调用后，系统完成

• 保存被调用函数的计算结果
• 释放被调用函数的数据区
• 依照被调用函数保存的返回地址将控制转移到调用函数

2.嵌套调用

（1）当多个函数构成嵌套调用

 （2）求解阶乘n！的过程

 三.递归函数调用的实现

1.递归的优缺点

（1）优点：结构清晰，程序易读

（2）缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大。

2.递归转化非递归

（1)尾递归、单向递归->循环结构

• 尾递归

•  单向递归

 

 （2）自用栈模拟系统的运行时栈

3.5队列的表示和操作实现

一.队列相关概念

1.相关术语

• 队列是仅在表尾进行插入操作，在表头进行删除操作的线性表
• 表尾即an端，称为队尾；表头即a1端，称为队头
• 它是一种先进先出的线性表

•  插入元素称为入队；删除元素称为出队
• 队列的存储结构为链队或者顺序队（常用循环顺序队）

2.队列的抽象数据类型定义

 二.队列的顺序表示和实现

1.队列的顺序表示和实现

• 队列的物理存储可以用顺序存储结构，也可以用链式存储结构。相应的，队列的存储方式也分为两种，即顺序队列和链式队列
• 队列的顺序表示：用一维数组base【MAXQSIZE】

 2.出队，入队相关问题

（1）出队入队

 （2）解决假上溢的方法

• 将队中元素依次向队头方向移动
• 缺点：浪费时间每移动一次，队中元素都要移动
• 将队空间设想成一个循环的表，即分配给队列的m个存储单元可以循环使用，当rear为maxqsize时，若向量的开始端空着，又可以从头使用空着的空间。当front为maxqsize时，也是一样。

 3.循环队列

（1）循环队列的表示

（2） 队空队满的判断方法——少用一个元素空间

 三.循环队列的类型定义

1.初始化

2.求队列的长度

3.入队

4. 出队

5.取队头元素

 3.5.3队列的链式表示和实现

一.链队列的表示

 1.链队列的类型定义

 2.链队列运算指针变化状况

（1）空队列

（2） 元素x入队列

（3）y入队列

 （4）x出队列

二.链队列的操作

1.初始化

 2.销毁

3. 将元素e入队

 4.出队

5.求链队列的队头元素