数据结构第03章

1、数据结构数据结构使用使用C语言语言(第第4版版)1 1第第3 3章章 堆栈和队列堆栈和队列主要知识点主要知识点堆栈堆栈堆栈应用堆栈应用队列队列优先级队列优先级队列数据结构数据结构使用使用C语言语言(第第4版版)2 21.1. 定义定义是一种特殊的线性表，限定只能在表的是一种特殊的线性表，限定只能在表的进行插入和删除操作的线性表。进行插入和删除操作的线性表。特点特点：后进先出后进先出。堆栈中允许进行插入和删除操作的一堆栈中允许进行插入和删除操作的一端称为端称为栈顶栈顶，另一端称为另一端称为栈底栈底。3.1 3.1 堆堆 栈栈数据结构数据结构使用使用C语言语言(第第4版版)3 3图图3-1 3-1

2、 火车调度模型火车调度模型（a a）车轨设置）车轨设置 （b b）驶入）驶入 （c c）驶出）驶出 堆栈的功能和火车调度装置的功能类同，如图堆栈的功能和火车调度装置的功能类同，如图3-13-1所示：所示：数据结构数据结构使用使用C语言语言(第第4版版)4 4与线性表相同，仍为一对一与线性表相同，仍为一对一( 1:1)关系关系。用用或或存储均可，但以顺序栈更常见存储均可，但以顺序栈更常见只能在只能在运算，且访问结点时依照运算，且访问结点时依照（LIFOLIFO）或）或（FILOFILO）的原则。）的原则。关键是编写关键是编写和和函数，具体实现依顺函数，具体实现依顺序栈或链栈的存储结构有别而不同。

3、序栈或链栈的存储结构有别而不同。3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式 2. 逻辑结构逻辑结构基本操作有基本操作有：建栈、判断栈满或栈空、入栈、出栈、建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值等等。读栈顶元素值等等。数据结构数据结构使用使用C语言语言(第第4版版)5 5 是仅在是仅在表尾表尾进行插入、删除操作的线性表。进行插入、删除操作的线性表。表尾表尾(即即 an 端端)称为称为栈顶栈顶 /top ; 表头表头(即即 a1 端端)称为称为栈底栈底/base例如：例如： 栈栈 = (a , a2 , a3 , .,an-1 , an )插入元素到栈顶的插入元素到

4、栈顶的操作，称为操作，称为入栈入栈。从栈顶删除最后一从栈顶删除最后一个元素的操作，称个元素的操作，称为为出栈出栈。a an n称为栈顶元素称为栈顶元素a a0 0称为栈底元素称为栈底元素插入和删除都只能在表插入和删除都只能在表的一端（栈顶）进行！的一端（栈顶）进行！注：注：堆栈可以完成比较复杂的数据元素特定序列的转换堆栈可以完成比较复杂的数据元素特定序列的转换任务，但它不能完成任何输入输出序列的转换任务。任务，但它不能完成任何输入输出序列的转换任务。数据结构数据结构使用使用C语言语言(第第4版版)6 6例例1 1：堆栈是什么？它与一般线性表有什么不同？：堆栈是什么？它与一般线性表有什么不同？

5、堆栈是一种特殊的线性表，它只能在表的堆栈是一种特殊的线性表，它只能在表的一端（即一端（即栈顶）栈顶）进行插入和删除运算。进行插入和删除运算。 与一般线性表的区别：仅在于与一般线性表的区别：仅在于不同。不同。逻辑结构：逻辑结构：1:1 逻辑结构：逻辑结构： 1:1 存储结构：顺序存储结构：顺序表表、链、链表表 存储结构：顺序存储结构：顺序栈栈、链、链栈栈运算规则：运算规则： 运算规则：运算规则：(LIFO)“进进”插入插入= =压入压入“出出”删除删除= =弹弹出出数据结构数据结构使用使用C语言语言(第第4版版)7 7例例2 2 一个栈的输入序列为一个栈的输入序列为1,2,31,2,3，若在，若

6、在入栈的过程中允入栈的过程中允许出栈，许出栈，则可能得到的出栈序列是什么？则可能得到的出栈序列是什么？解：可以通过穷举所有可能性来求解：可以通过穷举所有可能性来求解： 1 1入入1 1出，出， 2 2入入2 2出，出，3 3入入3 3出，出， 即即123123； 1 1入入1 1出，出， 2 2、3 3入，入，3 3、2 2出，出， 即即132132； 1 1、2 2入，入，2 2出，出， 3 3入入3 3出，出， 即即231231； 1 1、2 2入，入，2 2、1 1出，出，3 3入入3 3出，出， 即即213213； 1 1、2 2、3 3入，入，3 3、2 2、1 1出，出， 即即32

7、1321；合计有合计有5 5种可能性。种可能性。数据结构数据结构使用使用C语言语言(第第4版版)8 8例例3 3 一个栈的输入序列是一个栈的输入序列是1234512345，若在，若在入栈的过入栈的过程中允许出栈程中允许出栈，则栈的输出序列则栈的输出序列4351243512可能实现吗？可能实现吗？1234512345的输出呢？的输出呢？解：解： 4351243512不可能实现，主要是其中的不可能实现，主要是其中的1212顺序不能顺序不能实现；实现； 1234512345的输出可以实现，每压入一数便立即弹的输出可以实现，每压入一数便立即弹出即可。出即可。 数据结构数据结构使用使用C语言语言(第第4

8、版版)9 9数据集合：数据集合：aa0 0, a, a1 1, , , a , an-1n-1 a ai i的的数据类型数据类型为为DataTypeDataType操作集合操作集合：(1)StackInitiate(S) (1)StackInitiate(S) 初始化堆栈初始化堆栈S S (2)StackNotEmpty(S) (2)StackNotEmpty(S) 堆栈堆栈S S非空否非空否 (3)StackPush(S,x) (3)StackPush(S,x) 入栈入栈 (4)StackPop(S,d) (4)StackPop(S,d) 出栈出栈 (5)StackTop(S,d) (5)S

9、tackTop(S,d) 取栈顶数据元素取栈顶数据元素 数据结构数据结构使用使用C语言语言(第第4版版)10101、顺序（堆）栈顺序（堆）栈 顺序存储结构的堆栈。顺序存储结构的堆栈。2 2、顺序栈的存储结构、顺序栈的存储结构 它是利用一组地址连续的存储单元它是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，依次存放自栈底到栈顶的数据元素，同时设指针同时设指针toptop指示当前栈顶位置。指示当前栈顶位置。 a0 a1 an-1顺序栈顺序栈S ai栈底栈底栈顶栈顶数据结构数据结构使用使用C语言语言(第第4版版)1111 其中：其中： stackstack：为：为顺序堆栈存放数据元素的数

10、组；顺序堆栈存放数据元素的数组； MaxStackSizeMaxStackSize：为为stackstack的最大存储单元个数；的最大存储单元个数； toptop：为：为堆栈的当前栈顶位置。堆栈的当前栈顶位置。用用C C语言定义为：语言定义为：typedef structtypedef struct DataType stackMaxStackSize DataType stackMaxStackSize; int int top; top;SeqStackSeqStack; ;a4a3a2a1a001234Top=5栈顶栈顶栈底栈底Stack MaxStackSize-1数据结构数据结构使用

11、使用C语言语言(第第4版版)1212 a0 a1 an-1顺序栈顺序栈S S a ai i问：顺序表和顺序栈的操作有何区别？问：顺序表和顺序栈的操作有何区别？表头表头表尾表尾低地址低地址高地址高地址写入：写入：Si= Si= a ai i读出：读出： e= Sie= Si压入压入( (SStop+top+=a=an n弹出弹出( ( e=Se=S-top-top 低地址低地址高地址高地址SiSi a0 a1 a ai i an-1 顺序表顺序表S S a an n以线性表以线性表S S= (a= (a0 0 , a , a1 , 1 , . , . , a an-2 , n-2 , a an-

12、1n-1) )为例为例栈底栈底栈顶栈顶前提：一定要前提：一定要栈顶指针栈顶指针栈顶栈顶数据结构数据结构使用使用C语言语言(第第4版版)1313栈为空栈为空 的条件的条件 ： top=0;栈满的条件栈满的条件 ： top=MaxStackSize; a0 a1 an-1顺序栈顺序栈S ai低地址低地址高地址高地址 an栈底栈底栈顶栈顶入栈入栈口诀：堆栈指针口诀：堆栈指针top “先先压后加压后加” : SStop+top+=a=an n出栈出栈口诀：堆栈指针口诀：堆栈指针top “先先减后弹减后弹” : e=Se=S-top-top 数据结构数据结构使用使用C语言语言(第第4版版)1414问：为

13、什么要设计堆栈？它有什么独特用途？问：为什么要设计堆栈？它有什么独特用途？1.调用函数或子程序非它莫属；调用函数或子程序非它莫属；2.递归递归运算的有力工具；运算的有力工具；3.用于保护现场和恢复现场；用于保护现场和恢复现场；4.简化了程序设计的问题简化了程序设计的问题。下面用例子来帮助理解堆栈：下面用例子来帮助理解堆栈：数据结构数据结构使用使用C语言语言(第第4版版)1515void test(int *sum) int x;scanf(“%d”,&x);if(x=0)sum=0;else;sum+=x;printf(sum);断点地址断点地址入栈入栈例例1 1 阅读下列递归过程，说

14、明其功能。阅读下列递归过程，说明其功能。输入输入x10输入输入x50输入输入x2输入输入x3输入输入x4输出输出sum0输出输出sum0+x4输出输出sumx4+x3输出输出sum x4+x3 +x2输出输出sum x4+x3 +x2+x1注意：最先注意：最先输入的数据输入的数据 x x1 1 最后才被最后才被累加累加程序功能：对键盘输入数程序功能：对键盘输入数据求和，直到输入据求和，直到输入0 0结束结束数据结构数据结构使用使用C语言语言(第第4版版)16163 3、顺序栈的操作实现、顺序栈的操作实现(1) (1) 初始化栈初始化栈void StackInitiate(SeqStackvoi

15、d StackInitiate(SeqStack * *S)S)/ /* *初始化顺序堆栈初始化顺序堆栈S S* */ / S-top = 0; S-top = 0; / /* *定义初始栈顶下标值定义初始栈顶下标值* */ / 数据结构数据结构使用使用C语言语言(第第4版版)1717(2)(2)判栈非空否判栈非空否 int StackNotEmpty(SeqStack int StackNotEmpty(SeqStack S) S)/ /* *判顺序堆栈判顺序堆栈S S非空否，非空则返回非空否，非空则返回1 1，否则返回，否则返回0 0* */ / if(S.top = 0) if(S.to

16、p top = MaxStackSizeif(S-top = MaxStackSize) ) printf printf(堆栈已满无法插入堆栈已满无法插入! n);! n); return 0;return 0; else else S-stack S-stackS-topS-top = x; = x; S- S-top +;top +; return 1; return 1; 数据结构数据结构使用使用C语言语言(第第4版版)1919(4)(4)出栈出栈int StackPop(SeqStack int StackPop(SeqStack * *S, DataTypeS, DataType *

17、 *d)d)/ /* *弹出顺序堆栈弹出顺序堆栈S S的栈顶数据元素值到参数的栈顶数据元素值到参数d d ，出栈成功则返回，出栈成功则返回1 1，否则返回，否则返回0 0* */ / if(S-top top S-top -top -; ; * *d = S-stackd = S-stackS-topS-top; return 1; return 1; 数据结构数据结构使用使用C语言语言(第第4版版)2020(5)(5)取栈顶数据元素取栈顶数据元素int StackTop(SeqStack S, DataTypeint StackTop(SeqStack S, DataType * *d)d)

18、/ /* *取顺序堆栈取顺序堆栈S S的当前栈顶数据元素值到参数的当前栈顶数据元素值到参数d d ，成功则返回，成功则返回1 1，否则返回否则返回0 0* */ / if(S.top = 0) if(S.top stackS-top = x;S-stackS-top = x; S-top +;S-top +;toptoptoptoptoptoptoptop低地址低地址L L高地址高地址M MB BC CD D数据结构数据结构使用使用C语言语言(第第4版版)2222例：从栈中取出例：从栈中取出 DCBAtoptopDCABDCBAtopDCBAtop低地址低地址L高地址高地址MD顺序栈出栈函数的

19、核心语句：顺序栈出栈函数的核心语句：S-top -;*d = S-stackS-top;注注：DataType *d； SeqStack *S；数据结构数据结构使用使用C语言语言(第第4版版)2323测试主程序：测试主程序：任务：任务：建立一个建立一个顺序堆栈顺序堆栈，首先依次输入数据元素，首先依次输入数据元素1, 2, 3,.,10，然后，然后依次依次出栈堆栈中的数据元素并出栈堆栈中的数据元素并显示。显示。 假设该假设该顺序堆栈顺序堆栈的数据元素个数在最坏情况下不会超过的数据元素个数在最坏情况下不会超过100个。个。 #include stdio#include .h#define MaxS

20、tackSize #define MaxStackSize 100100typedef int DataTypetypedef int DataType; ;#include #include SeqStackSeqStack.h.h void main(void)void main(void) SeqStack myStackSeqStack myStack; ;intint i , x; i , x;数据结构数据结构使用使用C语言语言(第第4版版)2424StackInitiate(&myStackStackInitiate(&myStack););for(i = 0; i

21、 10; i+)for(i = 0; i next = NULL;head)-next = NULL; （2 2）非空否）非空否StackNotEmptyStackNotEmpty(head)(head)int StackNotEmpty(LSNodeint StackNotEmpty(LSNode * *head)head) if(if(head-nexthead-next = NULL) return 0; = NULL) return 0;else return 1;else return 1; 数据结构数据结构使用使用C语言语言(第第4版版)2727(3) (3) 入栈入栈void S

22、tackPush(LSNode void StackPush(LSNode * *head, DataTypehead, DataType x) x) LSNode LSNode * *p;p;p = (LSNode p = (LSNode * *)malloc(sizeof(LSNode)malloc(sizeof(LSNode) ) p-data = x; p-data = x;p-next = head-nextp-next = head-next; ; / /* *新结点链入栈顶新结点链入栈顶* */ /head-next = p;head-next = p; / /* *新结点成为新

23、的栈顶新结点成为新的栈顶* */ / 数据结构数据结构使用使用C语言语言(第第4版版)2828(4) (4) 出栈出栈int StackPop(LSNode int StackPop(LSNode * *head, DataTypehead, DataType * *d)d) LSNodeLSNode * *p = head-next;p = head-next;if(p = NULL) if(p = NULL) printfprintf(堆栈已空出错！堆栈已空出错！););return 0;return 0; head-next = p-next;head-next = p-next;/ /

24、* *删除原栈顶结点删除原栈顶结点* */ /* *d = p-data; d = p-data; / /* *原栈顶结点元素赋予原栈顶结点元素赋予d d* */ /free(p); free(p); / /* *释放原栈顶结点内存空间释放原栈顶结点内存空间* */ /return 1;return 1; 数据结构数据结构使用使用C语言语言(第第4版版)2929（5 5）取栈顶数据元素）取栈顶数据元素StackTopStackTop(head, d)(head, d)int StackTop(LSNode int StackTop(LSNode * *head, DataTypehead, D

25、ataType * *d)d) LSNodeLSNode * *p = head-next;p = head-next;if(p = NULL) if(p = NULL) printfprintf(堆栈已空出错！堆栈已空出错！););return 0;return 0; * *d = p-data;d = p-data;return 1;return 1; 数据结构数据结构使用使用C语言语言(第第4版版)3030（6 6）撤消动态申请空间）撤消动态申请空间Destroy(Destroy(* *head)head)void Destroy(LSNodevoid Destroy(LSNode *

26、*head)head) LSNodeLSNode * *p, p, * *p1;p1;p = head;p = head;while(p != NULL)while(p != NULL) p1 = p;p1 = p;p = p-next;p = p-next;free(p1);free(p1); 数据结构数据结构使用使用C语言语言(第第4版版)31311)1) 在链栈中的头结点对操作的实现影响不大，栈顶（表在链栈中的头结点对操作的实现影响不大，栈顶（表头）操作频繁，头）操作频繁，可不设头结点可不设头结点链栈。链栈。2)2) 一般一般不会出现栈满不会出现栈满情况；除非没有空间导致情况；除非没有空

27、间导致mallocmalloc分分配失败。配失败。3)3) 链栈的入栈、出栈操作就是栈顶的插入与删除操作，链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可完成。修改指针即可完成。几点说明几点说明:数据结构数据结构使用使用C语言语言(第第4版版)32321. 1. 括号匹配问题（书括号匹配问题（书P55P55） 假设一个算法表达式中包含圆括号、方括号和花括号假设一个算法表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个判别表达式中括号是否正确配三种类型的括号，编写一个判别表达式中括号是否正确配对的函数，并设计一个测试主函数。对的函数，并设计一个测试主函数。 设计思路：用栈暂存左

28、括号设计思路：用栈暂存左括号 括号匹配有括号匹配有四种情况四种情况：（1 1）左右括号配对次序不正确；）左右括号配对次序不正确；（2 2）右括号多于左括号；）右括号多于左括号；（3 3）左括号多于右括号；）左括号多于右括号；（4 4）左右括号匹配正确。）左右括号匹配正确。3.2 堆栈应用堆栈应用数据结构数据结构使用使用C语言语言(第第4版版)3333void ExpIsCorrect(char exp, intvoid ExpIsCorrect(char exp, int n) n)/判断有判断有n n个字符的字符串个字符的字符串expexp左右括号是否配对正确左右括号是否配对正确 SeqStack myStack SeqStack myStack; ; int int i; i;char c;char c; StackInitiate(&myStack Stack