实用数据结构基础 第3章 栈.

Presentation on theme: "实用数据结构基础 第3章 栈."— Presentation transcript:

1 实用数据结构基础 第3章 栈

2 第 3 章 栈 知 识 点 难 点 栈的定义和特点 栈的基本运算和算法 栈的典型应用 后缀表达式的算法 数制的换算
第 3 章 栈 知 识 点 栈的定义和特点 栈的基本运算和算法 栈的典型应用 难 点 后缀表达式的算法 数制的换算 利用本章的基本知识设计相关的应用问题

3 要 求 掌握栈的特点 掌握栈的基本运算 熟悉栈的各种实际应用 能设计栈的应用的典型算法 了解栈的运算时间复杂度分析

4 第3章 目录 3-1 栈的定义与运算 3-2 栈的存储和实现 3-3 栈的应用举例 小 结 实验3 栈子系统 习题3

5 3-1 栈的定义和运算 3-1-1 栈（Stack）的定义 1. 栈的定义 栈是限制在表尾进行插入和删除的线性表。 a3 a2 a1 进栈
3-1 栈的定义和运算 3-1-1 栈（Stack）的定义 1. 栈的定义     栈是限制在表尾进行插入和删除的线性表。 进栈 出栈 a1 a2 a3 图3-1栈的 示意图

6 2. 栈的特性 3. 应用实例 （1）栈的主要特点是“后进先出”
（2）允许插入、删除的这一端称为栈顶（Top），另一端称为栈底（Bottom）。 3. 应用实例 （1）分币筒； （2）铁路调度站。

7 3-1-2 栈的运算 1．进栈： Push（&s，x） 初始条件：栈s已存在且非满。 操作结果：在栈顶插入一个元素x，栈中多了一个元素。
2．出栈：Pop（&s） 初始条件：栈s存在且非空。 操作结果：删除栈顶元素，栈中少了一个元素。 3．读栈顶元素：ReadTop（s，&e） 初始条件：栈s已存在且非空。 操作结果：输出栈顶元素，但栈中元素不变。

8 4. 判栈空：SEmpty（s） 初始条件：栈s已存在。 操作结果：若栈空则返回为0，否则返回为1。 5. 判栈满：SFull（s） 操作结果：若栈满则返回为0，否则返回为1。 6. 显示栈元素：ShowStack (s) 初始条件：栈s已存在 ，且非空。 操作结果：显示栈中所有元素。

9 3-2 栈的存储和实现 3-2-1 顺序栈 1． 顺序栈的实现 （1） 用一维数组实现顺序栈
设栈中的数据元素的类型是字符型，用一个足够长度的一维数组s来存放元素，数组的最大容量为MAXLEN，栈顶指针为top，则顺序栈可以用C（或C++）语言描述如下： #define MAXLEN // 分配最大的栈空间 char s[MAXLEN]； // 数据类型为字符型 int top； // 定义栈顶指针

10 （2） 用结构体数组实现顺序栈 顺序栈的结构体描述： #define MAXLEN // 分配最大的栈空间 typedef struct // 定义结构体 { datatype data[MAXLEN]; // datatype可根据用需要定义类型 int top； // 定义栈顶指针 } SeqStack； 再定义一个指向顺序栈的指针： SeqStack *S； // 定义S为结构体类型的指针变量

11 F E D C B A F E D C B A J I H G F E D C B A A （3）栈操作的示意图如图3-3所示。
top=9 J I H G F E D C B A A top=5 top=3 top=0 top=-1 (a) (b) (c) (d) (e)

12 当top = -1时，表示栈空，如图3-3（a）；
当top=0时，表示栈中有一个元素，如图3-3（b）表示栈中已输入一个元素A； 入栈时，栈顶指针上移，指针top加1，如图3-3（c）是6个元素入栈后的状况； 出栈时，栈顶指针下移，指针top减1， 如图3-3（d）是在F、E相继出栈后的情况。此时栈中还有A、B、C、D 4个元素，top=3，指针已经指向了新的栈顶。但是出栈的元素F、E仍然在原先的存储单元，只是不在栈中了，因为栈是只能在栈顶进行操作的线性表。 当top=9时，即top=MAXLEN–1，表示栈满，如图3-3（e）。

13 2．顺序栈运算的基本算法 （1）置空栈 首先建立栈空间，然后初始化栈顶指针。 SeqStack *Snull（） { SeqStack *s； s=new (SeqStack)； // 在C语言中用s=malloc（sizeof（SeqStack））； s->top= –1； // 置栈空 return s； }

14 int Push (SeqStack *s， datatype x)
（2） 进栈 进栈运算是在栈顶位置插入一个新元素x，其算法步骤为： (a)    判栈是否为满，若栈满，作溢出处理，并返回0； (b)    若栈未满，栈顶指针top加1； (c)    将新元素x送入栈顶，并返回1。 int Push (SeqStack *s， datatype x) { if （s->top= =MAXLEN–1） return 0； // 栈满不能入栈，且返回 0 else { s->top++； s->data[s->top]=x； // 栈不满，则压入元素x return 1；} // 进栈成功，返回1 }

15 （3）出栈 出栈运算是指取出栈顶元素，赋给某一个指定变量x，其算法步骤为： (a) 判栈是否为空，若栈空，作下溢处理，并返回0；
(b) 若栈非空，将栈顶元素赋给变量x； (c)  指针top减1，并返回1。 int Pop（SeqStack *s， datatype *x） { if (SEmpty ( s ) ) return 0； // 若栈空不能出栈 ，且返回0 else { *x=s->data[s->top]； // 栈不空则栈顶元素存入*x s->top - -； return 1； } // 出栈成功，返回1 }

16 （4）读栈顶元素 （5）判栈空 datatype ReadTop（SeqStack *s）
{ if (SEmpty ( s ) ) return 0； // 若栈空，则返回0 else return (s->data[s->top] )； // 否则，读栈顶元素，但指针未移动 } （5）判栈空 int SEmpty（SeqStack *s） { if （s->top= = –1） return 1； // 若栈空，则返回1 else return 0； // 否则返回0

17 3-2-2 链栈 （6）判栈满 1．链栈的实现 int SFull（SeqStack *s）
{ if （s->top= =MAXLEN–1） return 1；// 若栈满，则返回1 else return 0； // 否则返回0 } 3-2-2 链栈 1．链栈的实现 用链式存储结构实现的栈称为链栈。因为链栈的结点结构与单链表的结构相同，通常就用单链表来实现，在此用LinkStack表示，即有： typedef struct stacknode // 栈的存储结构 { datatype data; // 定义数据类型 struct stacknode *next; // 定义一个结构体的链指针 } stacknode;，* Linkstack； Linkstack top； // top为栈顶指针

18 由于栈中的操作只能在栈顶进行的，所以用链表的头部做栈顶是最合适的。链栈结构如图3-4所示。
top 4 3 2 ^ 图3-4 链栈示意图

19 2．链栈基本操作： （1）入栈 { stacknode *p=new stacknode; // 申请一个新结点
void Push(linkstack *s,int x) { stacknode *p=new stacknode; // 申请一个新结点 p->data=x; // 数据入栈 p->next=s->top; // 修改栈顶指针 s->top=p; }

20 （2） 出栈 int Pop(linkstack *s) { int x; // 定义一个变量x，用以存放出栈的元素
stacknode *p=s->top; // 栈顶指针指向p x=p->data; // 栈顶元素送x s->top=p->next; // 修改栈顶指针 delete p; // 回收结点p return x; // 返回栈顶元素 }

21 （3） 显示 void ShowStack (linkstack *s) { stacknode *p=s->top;
if (p= =NULL) // 若栈空，作“栈空”显示 printf ("栈为空"); else { printf ("栈元素为："); while (p!=NULL) //栈非空，则显示栈中所有元素 { printf ("%6d",p->data); // 输出一个元素 p=p->next; } // 修改栈顶指针 printf ("\n"); }

22 3-3. 栈的应用举例 3-3-1 数制转换 数值进位制的换算是计算机实现计算和处理的基本问题。比如将十进制数N转换为j进制的数，其解决的方法很多，其中一个常用的算法是除j取余法。将十进制数每次除以j，所得的余数依次入栈，然后按“后进先出”的次序出栈便得到转换的结果。 其算法原理是： N =（N / j）* j + N % j 其中： / 为整除，%为求余

23 【例3-1】将十进制数138转换为二进制数 N N / 2 （整除） N % 2（求余） 进 出 栈 栈 次 次 序 序 ∴ （138）10 =（ ）2

24 1．算法思想如下： （1） 若 N<>0，则将N % j 取得的余数压入栈s中 ，执行（2）；
若N=0，将栈s的内容依次出栈，算法结束。 （2）  用N / j 代替 N （3） 当N>0，则重复步骤（1）、（2）。

25 void Conversion(int n) // 将十进制数n转换为二进制数 int x; s.top=NULL; do
2. 算法的实现： void Conversion(int n) // 将十进制数n转换为二进制数 { linkstack s; int x; s.top=NULL; do { x=n%2; // 除2取余 n=n/2; stacknode *p=new stacknode; // 申请一个新结点 p->next=s.top; // 修改栈顶指针 s.top=p; s.top->data=x; } // 入栈

26 while(n); printf("转换后的二进制数值为："); while(s.top) // 余数出栈处理 { printf("%d",s.top->data); // 输出栈顶的余数 stacknode* p=s.top; // 修改栈顶指针 s.top=s.top->next; delete p; // 回收一个结点，C语言中用free p }

27 3-3-2 表达式求值 表达式是由运算对象、运算符、括号等组成的有意义的式子。 1．中缀表达式（Infix Notation）
一般我们所用表达式是将运算符号放在两运算对象的中间，比如：a+b，c/d等等，我们把这样的式子称为中缀表达式。 2．后缀表达式（Postfix Notation） 后缀表达式规定把运算符放在两个运算对象（操作数）的后面。在后缀表达式中，不存在运算符的优先级问题，也不存在任何括号，计算的顺序完全按照运算符出现的先后次次序进行。 3．中缀表达式转换为后缀表达式 其转换方法采用运算符优先算法。转换过程需要两个栈：一个运算符号栈和一个后缀表达式输出符号栈。

28 （1）读入操作数，直接送输出符号栈。 （2）读入运算符，压入运算符号栈。 (a) 若后进的运算符优先级高于先进的，则继续进栈； (b) 若后进的运算符优先级不高于先进的，则将运算符号栈内高于或等于后进运算符级别的运算符依次弹出后，自己进栈。 （3）括号处理： (a) 遇到开括号“（”，进运算符号栈； (b)遇到闭括号“）”，则把最靠近的开括号“（”，以及其后进栈的运算符依次弹出到输出符号栈（括号均不压入输出符号栈）。 （4）遇到结束符“#”，则把运算符号栈内的所有运算符号依次弹出，并压入输出符号栈。 （5）若输入为+、–单目运算符，改为0与运算对象在前，运算符在后。 例如：–A，转换为：0A–。

29 【例3-2】A / B ^ C + D * E–A*C A / B ^ /, ^ C + D * +,* E - -,* # 输入符号
运算符栈 输出结果 操作说明 A 输出A / / 进栈 B A,B 输出B ^ /, ^ ^优先级高于/，继续进栈 C A,B,C 输出C + A,B,C, ^,/ ^，/依次弹出 D A,B,C, ^,/,D 输出D * +,* *优先级高于+，继续进栈 E A,B,C, ^,/,D,E 输出E - A,B,C, ^,/,D,E,*,+ *，+ 依次弹出，- 进栈 A,B,C, ^,/,D,E,*,+,A -,* *优先级高于 -，继续进栈 A,B,C, ^,/,D,E,*,+,A,C # A,B,C, ^,/,D,E,*,+,A,C,*, - 遇到结束符#，依次弹出*，-

30 【例3-3】3 + 4 /（25–（6 + 15））* 8 输出结果 操作说明 3 输出3 + +进栈 4 3,4 输出4 / +,/
输入符号 运算符栈 输出结果 操作说明 3 输出3 + +进栈 4 3,4 输出4 / +,/ / 继续进栈 ( +,/,( （进栈 25 3,4,25 输出25 - +,/,(,- - 进栈 +,/,(,-,( （再进栈 6 3,4,25,6 输出6 +,/,(,-,(,+ 15 3,4,25,6,15 输出15 ) 3,4,25,6,15,+ 遇），依次弹出第2个（后的符号 3,4,25,6,15,+,- 遇），依次弹出第1个（后的符号 * +,* 3,4,25,6,15,+,-,/ 弹出/，但*高于+，继续进栈 8 +.* 3,4,25,6,15,+,-,/,8 输出8 # 3,4,25,6,15,+,-,/,8,*,+ 遇到结束符#，依次弹出*，+

31 4．后缀表达式求值 得到后缀表达式为：3 4 25 6 15 + – / 8 * +
得到后缀表达式为： – / 8 * + 4．后缀表达式求值 后缀表达式求值的运算要用到一个数栈stack和一个存放后缀表达式的字符型数组exp。其实现过程就是从头至尾扫描数组中的后缀表达式： （1）当遇到运算对象时，就把它插入到数栈stack中； （2）当遇到运算符时，就执行两次出栈的操作，对出栈的数进行该运算符指定的运算，并把计算的结果压入到数栈stack。把它插入到数栈stack中； （3）重复（1）、（2），直至扫描到表达式的终止符“#”，在数栈的栈顶得到表达式的值。

32 3 4 25 6 15 + - / 8 * + 第1次计算结果为：21 以例【例3-3】的结果看后缀表达式的计算过程： 第2次计算结果为：4
/ 8 * + 第1次计算结果为：21 第2次计算结果为：4 第3次计算结果为：1 第4次计算结果为：8 第5次计算结果为：11

33 3-3-3 子程序调用（Subroutine Call）
在计算机程序设计中，子程序的调用及返回地址就是利用堆栈来完成的。 在C(或C++)语言的主函数对无参子函数的嵌套调用过程中，在调用子程序前，先将返回地址保存到堆栈中，然后才转去执行子程序。当子函数执行到return语句（或函数结束）时，便从栈中弹出返回地址，从该地址处继续执行程序。 例如：主函数调用子函数a()时，则在调用之前先将a函数返回地址压入栈中；在子函数a()中调用子函数b()时，又将b函数返回地址压人栈中；同样，在子函数b()中调用子函数c()时，又将c函数返回地址压人栈中。其调用返回地址进栈示意图如图3-5所示。

34 c函数返回地址 b函数返回地址 a函数返回地址 返回地址栈： 图3-5 无参函数嵌套调用返回地址进栈示意图 当执行完子函数c()以后，就从栈顶弹出c()函数返回地址，回到子函数b()；子函数b()执行完毕返回时，又从栈顶弹出b函数返回地址，回到子函数a()；子函数a()返回时，再在栈顶弹出a函数返回地址，回到主函数，继续执行主函数程序。无参函数嵌调用返回示意图如图3-6所示。

35 图3-6 无参函数嵌套调用返回示意图

36 3-3-4 递归调用 1．递归 一个直接调用自己，或者通过一系列调用语句间接地调用自己的函数称为递归函数。在程序设计中，有许多实际问题是递归定义的，使用递归的方法编写程序将使许多复杂的问题大大简化。所以，递归是程序设计中的一个强有力的工具。 2．典型例子 （1）2阶斐波那契（Fibonacci）数列 0        n=0 1        n=1 Fib( n–1 )+Fib( n–2 ) 其它情况 Fib(n)=

37 （2）阶乘函数 n!的定义为： int fac ( int n ) { if (n= =0) return 1 ；
Fac(n)==== n*Fac (n-1) n> // 递归步骤 根据定义不难写出相应的递归函数： int fac ( int n ) { if (n= =0) return 1 ； else return (n* fac (n–1) )； }

38 在C++语言中，系统调用是通过中断来进行，中断调用示意图如图3-8所示。
3-3-5 中断处理和现场保护 1.中断处理（Interrupt Processing） 在C++语言中，系统调用是通过中断来进行，中断调用示意图如图3-8所示。 图3-8 中断调用示意图如 如果把中断处理想象成函数调用，则中断处理程序可以看成被调用的函数。

39 2. 现场保护和恢复 执行中断时，微处理机有时必须对状态寄存器，累加器，以及相关的寄存器对进行现场保护（压栈）；中断处理完毕，则必须按后进先出的原则恢复现场（出栈）。下面，我们以汇编语言来说明现场保护和恢复的原理： … ；接受中断处理 PUSH AX ；保护现场 PUSH BX PUSH CX PUSH BP PUSHF ；F状态寄存器进栈 … ；中断处理 POPF ；恢复现场，后进栈的先出栈 POP BP POP CX POP BX POP AX

40 小 结 （1）栈是一种运算受限制的线性表，它只允许在栈顶进行插入和删除等操作。
小 结 （1）栈是一种运算受限制的线性表，它只允许在栈顶进行插入和删除等操作。 （2）栈的逻辑结构和线性表相同，数据元素之间存在一对一的关系，其主要特点是“后进先出”。 （3）栈的存储结构有顺序栈和链栈之分，要求掌握栈的C语言描述方法。 （4）重点掌握在顺序栈和链栈上实现：进栈、出栈、读栈顶元素、判栈空和判栈满等基本操作。 （5） 熟悉栈在计算机的软件设计中的各种应用，能灵活应用栈的基本原理解决一些综合性的应用问题。

41 实验3 栈子系统 1．实验目的 2. 实验内容 （1） 掌握栈的特点及其描述方法。 （2） 用链式存储结构实现一个栈。
（1）  掌握栈的特点及其描述方法。 （2） 用链式存储结构实现一个栈。 （3） 掌握建栈的各种等基本操作。 （4）掌握栈的几个典型应用的算法。 2. 实验内容 （1）设计一个字符型的链栈； （2）编写进栈、出栈、显示栈中全部元素的程序； （3）编写一个把十进制整数转换成二进制数的应用程序； （4）编写一个把中缀表达式转换成后缀表达式（逆波兰式）的应用程序； （5）设计一个选择式菜单，以菜单方式选择上述操作。

42 *教材p64第3行void Stack() ，在作为子系统上机时上机时改为：void main()
栈 子 系 统 ******************************************** * 进 栈 * * 出 栈 * * 显 示 * * 数制转换 * * 逆波兰式 * * 返 回 * 请选择菜单号： *教材p64第3行void Stack() ，在作为子系统上机时上机时改为：void main()

43 习题3 参考习题解答 返回