第3章 堆栈和队列 堆栈 堆栈应用 队列 队列应用 优先级队列 主要知识点.

Presentation on theme: "第3章 堆栈和队列 堆栈 堆栈应用 队列 队列应用 优先级队列 主要知识点."— Presentation transcript:

1 第3章 堆栈和队列 堆栈 堆栈应用 队列 队列应用 优先级队列 主要知识点

2 3.1 堆 栈 1、堆栈的基本概念 (1)定义:限定只能在固定一端进行插入和删除操作的线性表。特点：后进先出。
3.1 堆 栈 1、堆栈的基本概念 (1)定义:限定只能在固定一端进行插入和删除操作的线性表。特点：后进先出。 (2)允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。 作用：可以完成从输入数据序列到某些输出数据序列的转换

3 2、堆栈抽象数据类型 数据集合: {a0,a1,…,an-1}ai的数据类型为DataType。 操作集合：
(1) StackInitiate(S) ：初始化堆栈S (2) StackNotEmpty(S)：堆栈S非空否 (3) StackPush(S, x) ：入栈 (4) StackPop(S, d)：出栈 (5) StackTop(S, d)：取栈顶数据元素

4 3、顺序堆栈 顺序堆栈：顺序存储结构的堆栈。 顺序栈的存储结构： 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素.

5 a0 a1 a2 a3 a4 stack = 栈底 栈顶 MaxStackSize-1 1 2 3 4 5 top
1 2 3 4 5 = top typedef struct { DataType stack[MaxStackSize]; int top; } SeqStack;

6 顺序堆栈的操作实现： （1）初始化StackInitiate(S)
void StackInitiate(SeqStack *S) { S->top = 0; } （2）非空否StackNotEmpty(S) int StackNotEmpty(SeqStack S) if(S.top <= 0)return 0; else return 1;

7 （3）入栈StackPush(S, x) int StackPush(SeqStack *S, DataType x)
{ if(S->top >= MaxStackSize) { printf("堆栈已满无法插入! \n"); return 0; } else { S->stack[S->top] = x; S->top ++; return 1;

8 （4）出栈StackPop(S, d) int StackPop(SeqStack *S, DataType *d)
{ if(S->top <= 0) { printf("堆栈已空无数据元素出栈! \n"); return 0; } else { S->top --;*d = S->stack[S->top]; return 1;

9 （5）取栈顶数据元素StackTop(SeqStack S, DataType *d)
int StackTop(SeqStack S, DataType *d) { if(S.top <= 0) { printf("堆栈已空! \n"); return 0; } else { *d = S.stack[S.top - 1]; return 1;

10 任务：建立一个顺序堆栈，首先依次输入数据元素1, 2, 3,......,10，然后依次出栈堆栈中的数据元素并显示。
测试主程序： 任务：建立一个顺序堆栈，首先依次输入数据元素1, 2, 3,......,10，然后依次出栈堆栈中的数据元素并显示。 假设该顺序堆栈的数据元素个数在最坏情况下不会超过100个。 #include <stdio.h> #include <stdlib.h> #define MaxStackSize 100 typedef int DataType; #include "SeqStack.h"

11 void main(void) { SeqStack myStack; int i , x; StackInitiate(&myStack); for(i = 0; i < 10; i++) StackPush(&myStack, i+1) StackTop(myStack, &x) printf("当前栈顶数据元素为：%d\n", x); printf("依次出栈的数据元素序列如下：\n"); while(StackNotEmpty(myStack)) { StackPop(&myStack, &x); printf("%d ", x); }

12 程序运行输出结果如下： 当前栈顶数据元素为：10 依次出栈的数据元素序列如下：

13 4、链式堆栈 链式存储结构的堆栈。 1)链式堆栈 2)链式栈的存储结构 它是以头指针为栈顶，在头指针处插入或删除，带头结点的链式堆栈结构：
an-1 an-2 a0 ∧ … h 栈底 栈顶 链栈中每个结点由两个域构成：data域和next域

14 （1）初始化StackInitiate(head)
结点结构体定义如下： typedef struct snode { DataType data; struct snode *next; } LSNode; 3)链式堆栈的操作实现 （1）初始化StackInitiate(head) void StackInitiate(LSNode **head) { *head = (LSNode *)malloc(sizeof(LSNode)) ; (*head)->next = NULL; }

15 （2）非空否StackNotEmpty(head)
int StackNotEmpty(LSNode *head) { if(head->next == NULL) return 0; else return 1; }

16 （3）入栈StackPush(head, x)
int StackPush(LSNode *head, DataType x) { LSNode *p;   p = (LSNode *)malloc(sizeof(LSNode)) ;   p->data = x; p->next = head->next; head->next = p; return 1; }

17 （4）出栈StackPop(head, *d)
int StackPop(LSNode *head, DataType *d) { LSNode *p = head->next; if(p == NULL) { printf("堆栈已空出错！"); return 0; }   head->next = p->next; *d = p->data; free(p); return 1;

18 （5）取栈顶数据元素StackTop(head, d)
int StackTop(LSNode *head, DataType *d) { LSNode *p = head->next; if(p == NULL) printf("堆栈已空出错！"); return 0; } *d = p->data; return 1;

19 （6）撤消动态申请空间Destroy(*head)
void Destroy(LSNode *head) { LSNode *p, *p1;   p = head; while(p != NULL) p1 = p; p = p->next; free(p1); }

20 说明： 1) 链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可完成。 2)一般不会出现栈满情况；除非没有空间导致malloc分配失败。 3)采用链栈存储方式的优点是，当栈中元素个数变化较大，准确数字难以确定时，链栈较顺序堆栈方便。

21 3.2 堆栈应用 1、括号匹配问题 例：假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个判别表达式中括号是否正确配对的函数，并设计一个测试主函数。 解题：这是一个输入元素序列到特定输出元素序列转换问题。 算法思想： 算术表达式中右括号和左括号匹配的次序正好符合后到的括号要最先被匹配的“后进先出”堆栈操作特点，因此可以借助一个堆栈来进行判断。 括号匹配共有四种情况： （1）左右括号配对次序不正确；（2）右括号多于左括号； （3）左括号多于右括号； （4）左右括号匹配正确。

22 具体方法：顺序扫描算术表达式（表现为一个字符串），当遇到三种类型的左括号时让该括号进栈；当扫描到某一种类型的右括号时，比较当前栈顶括号是否与之匹配，若匹配则退栈继续进行判断；若当前栈顶括号与当前扫描的括号不相同，则左右括号配对次序不正确；若字符串当前为某种类型左括号而堆栈已空，则右括号多于左括号；字符串循环扫描结束时，若堆栈非空（即堆栈中尚有某种类型左括号），则说明左括号多于右括号；否则，左右括号匹配正确。 括号匹配共有四种情况： （1）左右括号配对次序不正确： "(())abc{[]()]" （2）右括号多于左括号： "(()))abc{[]}" （3）左括号多于右括号： "(()()abc{[]}" （4）左右括号匹配正确： "(())abc{[]}"

23 void ExpIsCorrect(char exp[], int n)
{ SeqStack myStack; int i; char c;   StackInitiate(&myStack); for(i = 0; i < n; i++) { if((exp[i] == '(') || (exp[i] == '[') || (exp[i] == '{')) StackPush(&myStack, exp[i]);  else if(exp[i] == ')' && StackNotEmpty(myStack) && StackTop(myStack, &c) && c == '(') StackPop(&myStack, &c); else if(exp[i] == ')' && StackNotEmpty(myStack) && StackTop(myStack, &c) && c != '(') { printf("左右括号配对次序不正确！\n"); return; }

24 else if(exp[i] == ']' && StackNotEmpty(myStack) && StackTop(myStack, &c) && c == '['] StackPop(&myStack, &c); && StackTop(myStack, &c) && c != '[') { printf("左右括号配对次序不正确！\n"); return; }  else if(exp[i] == '}' && StackNotEmpty(myStack) && StackTop(myStack, &c) && c == '{'} && StackTop(myStack, &c) && c != '{') }

25 else if(((exp[i] == ')') || (exp[i] == ']') || (exp[i] == '}'))
&& !StackNotEmpty(myStack)) { printf("右括号多于左括号！\n"); return; } if(StackNotEmpty(myStack)) printf("左括号多于右括号！\n"); else printf("左右括号匹配正确！\n");

26 2、表达式计算问题 表达式计算是编译系统中的基本问题，其实现方法是堆栈的一个典型应用。在编译系统中，要把便于人理解的表达式翻译成能正确求值的机器指令序列，通常需要先把表达式变换成机器便于理解的形式，这就要变换表达式的表示序列。 假设计算机高级语言中的一个算术表达式为 A+(B-C/D)*E

27 这种表达式称为中缀表达式，写成满足四则运算规则的相应
的后缀表达式即为 ABCD/-E*+ 优点：可以直接计算中缀表达式的值。 编译系统中表达式的计算分为两个步骤： （1）把中缀表达式变换成相应的后缀表达式； （2）根据后缀表达式计算表达式的值。 其中，步骤（1）这种数据序列的特定变换可以利用堆栈来实现； 步骤（2）的算法也可借助堆栈来实现。

28 中缀表达式变换为后缀表达式的算法步骤可以总结为：
( 1 ) 设置一个堆栈，初始时将栈顶元素置为“＃”。 ( 2 ) 顺序读入中缀表达式，当读到的单词为操作数时就将其输出，并接着读下一个单词。 ( 3 ) 令x1为当前栈顶运算符的变量，x2为当前扫描读到运算符的变量，当顺序从中缀表达式中读入的单词为运算符时就赋予x2，然后比较x1的优先级与x2的优先级，若x1的优先级高于x2的优先级，将x1退栈并作为后缀表达式的一个单词输出，然后接着比较新的栈顶运算符x1的优先级与x2的优先级。 如：中缀表达式A+(B-C/D)*E＃ 后缀表达式ABCD/-E*+

29 运算符优先级关系表

30 把中缀表达式A+(B-C/D)*E变换成后缀表达式的过程

31 计算后缀表达式的值的过程仍是一个堆栈应用问题
算法思想是：设置一个堆栈存放操作数，从左到右依次扫描后缀表达式，每读到一个操作数就将其进栈；每读到一个运算符就从栈顶取出两个操作数施以该运算符所代表的运算操作，并把该运算结果作为一个新的操作数入栈；此过程一直进行到后缀表达式读完，最后栈顶的操作数就是该后缀表达式的运算结果。 后缀表达式ABCD/-E*+求值过程:

32

33 3.3 队 列 1、队列的基本概念 (1)定义:只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表。一个队列的示意图如下： a0
3.3 队 列 队尾插入 1、队列的基本概念 (1)定义:只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表。一个队列的示意图如下： 队头删除 a0 a1 a2 … an-1 队头 队尾

34 2、队列抽象数据类型 3、顺序队列 数据集合:{a0,a1,…,an-1}，ai的数据类型为DataType。 操作集合：
（1）初始化QueueInitiate(Q) （2）非空否QueueNotEmpty(Q) （3）入队列QueueAppend(Q, x) （4）出队列QueueDelete(Q, d) （5）取队头数据元素QueueGet(Q, d) 3、顺序队列 (1)顺序队列： 顺序存储结构的队列。

35 (2)顺序队列的存储结构 有6个存储空间的顺序队列动态示意图 C B A (b)入队列A、 B、C后 front =0 1 2 3 4 5
front rear =0 1 2 3 4 5 C (c)出队列A、B后 front= 1 2 3 4 5 rear = E D C (d)入队列D、E后 front= 1 2 3 4 5 rear =

36 (3)顺序队列的“假溢出”问题 ①假溢出 　　顺序队列因多次入队列和出队列操作后出现的虽有存储空间但不能进行入队列操作的情况。

37 ②如何解决顺序队列的假溢出问题？ 可采取四种方法： 　1)采用顺序循环队列；（教材中的方法） 2)按最大可能的进队操作次数设置顺序队列的最大 元素个数；（最差的方法） 3)修改出队算法，使每次出队列后都把队列中剩余 数据元素向队头方向移动一个位置； 　４)修改入队算法，增加判断条件，当假溢出时，把队列中的数据元素向对头移动，然后方完成入队操作。

38 (4)顺序循环队列的基本原理 把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当rear和front达到MaxQueueSize-1后，再前进一个位置就自动到０。 a3 a2 a1 1 2 3 N-1 rear front 循环队列 顺序队列 a3 a2 a1 front rear 1 2 3 . N-1

39 (5)顺序循环队列的队空和队满判断问题 新问题：在顺序循环队列中，队空特征是front=rear；队满时也会是 front=rear；判决条件将出现二义性！解决方案有三： ①使用一个计数器记录队列中元素个数（即队列长度）； （教材中的方法） 　　判队满：count>0 && rear==front 判队空：count==0 ②设标志位，出队时置０,入队时置１,则可识别当前front=rear 属于何种情况 　　判队满：tag==1 && rear==front 判队空：tag==0 && rear==front ③ 少用一个存储单元 　　判队满： front=＝(rear+1)%MaxQueueSize 判队空： rear==front

40 4、顺序循环队列 顺序循环队列的结构体定义如下： typedef struct {
DataType queue[MaxQueueSize]; int rear; int front; int count; } SeqCQueue;

41 （1）初始化QueueInitiate(Q)
void QueueInitiate(SeqCQueue *Q) { Q->rear = 0; Q->front = 0; Q->count = 0; } （2）非空否QueueNotEmpty(Q) int QueueNotEmpty(SeqCQueue Q) if(Q.count != 0) return 1; else return 0;

42 （3）入队列QueueAppend(Q, x)
int QueueAppend(SeqCQueue *Q, DataType x) { if(Q->count > 0 && Q->rear == Q->front) { printf("队列已满无法插入! \n"); return 0; } else { Q->queue[Q->rear] = x; Q->rear = (Q->rear + 1) % MaxQueueSize; Q->count++; return 1;

43 （4）出队列QueueDelete(Q, d)
int QueueDelete(SeqCQueue *Q, DataType *d) { if(Q->count == 0) { printf("队列已空无数据元素出队列! \n"); return 0; } else { *d = Q->queue[Q->front]; Q->front = (Q->front + 1) % MaxQueueSize; Q->count--; return 1;

44 （5）取队头数据元素QueueGet(Q, d)
int QueueGet(SeqCQueue Q, DataType *d) { if(Q.count == 0) { printf("队列已空无数据元素可取! \n"); return 0; } else { *d = Q.queue[Q.front]; return 1;

45 5、链式队列 1)链式队列 链式存储结构的队列。 2)链式队列的存储结构
链式队列的队头指针指向队列的当前队头结点;队尾指针指在队列的当前队尾结点. 一个不带头结点的链式队列的结构： a0 a1 an-1 ∧ … front rear

46 队头指针front和队尾指针rear的结构体类型：
结点的结构体可定义如下： typedef struct qnode { DataType data; struct qnode *next; } LQNode; 队头指针front和队尾指针rear的结构体类型： typedef struct LQNode *front; LQNode *rear; } LQueue;

47 3) 链式队列操作的实现 （1）初始化QueueInitiate(Q) void QueueInitiate(LQueue *Q)
{ Q->rear = NULL; Q->front = NULL; } （2）非空否QueueNotEmpty(Q) int QueueNotEmpty(LQueue Q) { if(Q.front == NULL) return 0; else return 1;

48 （3）入队列QueueAppend(Q, x)
int QueueAppend(LQueue *Q, DataType x) { LSNode *p;   p = (LQNode *)malloc(sizeof(LQNode)) ; p->data = x; p->next = NULL; if(Q->rear != NULL) Q->rear->next = p; Q->rear = p; if(Q->front == NULL) Q->front = p; return 1; }

49 （4）出队列QueueDelete(Q, d)
int QueueDelete(LQueue *Q, DataType *d) { LQNode *p; if(Q->front == NULL) { printf("队列已空无数据元素出队列! \n"); return 0; } else { *d = Q->front->data; p = Q->front; Q->front = Q->front->next; if(Q->front == NULL) Q->rear = NULL; free(p); return 1;

50 （5）取队头数据元素QueueGet(Q, d)
int QueueGet(LQueue Q, DataType *d) { if(Q.front == NULL) { printf("队列已空无数据元素出队列! \n"); return 0; } else { *d = Q.front->data; return 1;

51 6、队列的应用 任务描述：一个计算机局域网系统中有若干台计算机，为了节约资源，只安装了一台打印机，要求设计一个对打印机的打印任务进行管理的打印任务管理器，打印机的打印任务按照先来先打印的方式进行管理。 任务分析：打印任务管理器可设计成一个链式队列。打印任务管理器应包含的操作有： （1）初始化。 （2）入队列。把新的打印任务加入到队尾。 （3）出队列。 （4）输出。 （5）清空。 任务说明：每一个打印任务应包含打印任务标识号和要打印的内容。

52 数据结构设计：链式队列的结点结构体定义如下：
typedef struct node { int id; //打印任务标识号 char *text; //要打印的内容 struct node *next; //指向下一个结点的指针 }Task; //结点结构体Task 链式队列的头指针、尾指针结构体定义如下： typedef struct Task *front; //头指针 Task *rear; //尾指针 }Queue; //链式队列结构体}Queue

53 （2）入队列。把新的打印任务加入到队尾。 void AppendPrintTask(Queue *taskmanager, int tid, char *text) //打印任务包括打印任务标识号tid和要打印的内容text { Task *p; p = (Task *) malloc(sizeof(Task)); p->text = (char *) malloc(strlen(text) * sizeof(Task) +1); strcpy(p->text, text); p->id = tid; p->next = NULL; if(taskmanager->rear != NULL) taskmanager->rear->next = p; taskmanager->rear = p; if(taskmanager->front == NULL) taskmanager->front = p; }

54 （3）出队列。 int PrintFirstTask(Queue *taskmanager)
{ Task *p = taskmanager->front; if(p == NULL) return 0; else printf("Task id: %d\n", p->id); printf("Task context: %s\n", p->text); } taskmanager->front = taskmanager->front->next; if(taskmanager->front == NULL) taskmanager->rear = NULL; free(p->text); free(p); return 1;

55 3.4 优先级队列 １、优先级队列 带有优先级的队列。 ２、顺序优先级队列 用顺序存储结构存储的优先级队列。
１、优先级队列　　带有优先级的队列。 ２、顺序优先级队列　用顺序存储结构存储的优先级队列。 ３、优先级队列和一般队列的主要区别 　　优先级队列的出队列操作不是把队头元素出队列，而是把队列中优先级最高的元素出队列。

56 注：顺序优先级队列除出队列操作外的其他操作的实现方法与前边讨论的顺序队列操作的实现方法相同。
它的数据元素定义为如下结构体： struct DataType { ElemType elem; //数据元素 int priority; //优先级 }; 注：顺序优先级队列除出队列操作外的其他操作的实现方法与前边讨论的顺序队列操作的实现方法相同。

57 出队列操作(把优先级最高的元素出队列并由函数返回,优先级相同时按先进先出的原则出队列。取顺序优先队列中优先级最高的元素算法类同)
出队列算法如下： int QueueDelete(SeqPQueue *Q, DataType *d) { DataType min; int minIndex, i;   if(Q->size <= 0) { printf("队列已空无数据元素出队列! \n"); return 0; }

58 else { min = Q->queue[0]; minIndex = 0; for(i = 1; i < Q->size; i++) //找到最高 if(Q->queue[i].priority < min.priority) { min = Q->queue[i]; minIndex = i; }   *d = Q->queue[minIndex]; //取出 for(i = minIndex+1; i < Q->size; i++) //前移 Q->queue[i-1] = Q->queue[i]; Q->size--; //减1 return 1;

59 例:设计一个程序模仿操作系统的进程管理进程。进程服务按优先级高的先服务、
优先级相同的先到先服务的原则管理。 模仿数据包括两部分:进程编号和优先级。一个模仿数据集合如下，其中第一列表示进程编号，第二列表示进程优先级: 1 30 2 20 3 40 4 20 5 0

60 #include <stdio.h>
#include <stdlib.h> #define MaxQueueSize 100 typedef int ElemType; #include "SeqPQueue.h" void main(void) { SeqPQueue myPQueue; FILE *fp; DataType task; int i;   if((fp = fopen("task.dat", "r")) == NULL) { printf("不能打开文件task.dat!"); exit(0); } 

61 QueueInitiate(&myPQueue);
while(!feof(fp)) { fscanf(fp, "%d %d", &task.elem, &task.priority); QueueAppend(&myPQueue, task); } i = 1; printf("序号 任务号 优先级\n"); while(QueueNotEmpty(myPQueue)) QueueDelete(&myPQueue, &task); printf("%d ", i); printf("%d ", task.elem); printf("%d \n", task.priority); i++; }

62 程序运行的输出结果为： 序号 任务号 优先级 从程序的运行结果可以看出，进程管理的服务遵从了优先级高的进程先服务、优先级相同的进程先到先服务的管理原则。

63 作业 1)习题3-1，3-2中的堆栈部分 2)习题3-10，3-4，3-14 3)习题3-1，3-2中的队列部分 习题3-10，3-4，3-14 4)习题3-6，3-11