3.2栈的应用举例 例1:括号匹配的检验 假设一个算法表达式中包含圆括号、方括号和花括 号三种类型的括号,编写一个判别表达式中括号是 否正确配对的函数 设计思路:用栈暂存左括号
1 3.2 栈的应用举例 例1：括号匹配的检验 假设一个算法表达式中包含圆括号、方括号和花括 号三种类型的括号，编写一个判别表达式中括号是 否正确配对的函数。 设计思路：用栈暂存左括号
void ExpIsCorrect(char exp[l, int n) //判断有n个字符的字符串exp左右括号是否配对正确 I SeqStack my Stack; int i, char c StackInitiate(&my Stack) for(i=0; i<n; i++) Hif((exp[i]=='(')I(exp[i]=='[')(exp[i] t')) StackPush(&myStack, exp[]) else if(expli]==')'&& StackNotEmpty(my Stack & StackTop(myStack, &c)&&c () StackPop(&my Stack, &c)
2 void ExpIsCorrect(char exp[], int n) //判断有n个字符的字符串exp左右括号是否配对正确 { 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(expli]==')'&& StackNotEmpty(my Stack) && Stack Top( my Stack,&c)&匙c!=’() printf("左右括号配对次序不正确!\n") return; else if(expli]== ']'&& StackNotEmpty(myStack && StackTop( my Stack,&c)&匙c=’[) StackPop(&myStack, &c) else if(exp[i]==']'&& Stack NotEmpty(my Stack & StackTop(my Stack &c)&&c! =[) printf("左右括号配对次序不正确!\n"); return;}
3 else if(exp[i] == ')' && StackNotEmpty(myStack) && StackTop(myStack, &c) && c != '(') { printf("左右括号配对次序不正确！\n"); return;} 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;｝
else if(expli]=='&& StackNotEmpty(my Stack) && StackTop( myStack,&c)&匙c三=’{) StackPop ( &my Stack, &c) else if(exp[i]==''&& StackNotEmpty(myStack) & StackTop(my Stack, &c)&&c!='t) printf("左右括号配对次序不正确!\n"); return;} else if((exp[i]=’)’)‖|(exp[i]==’])|1 (expli]=='))&&! Stack NotEmpty(myStack)) printf("右括号多于左括号!n"); return;}
4 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;} else if(((exp[i] == ')') || (exp[i] == ']') || (exp[i] == '}')) && !StackNotEmpty(myStack)) { printf("右括号多于左括号！\n"); return;} }
if( Stack NotEmpty(myStack)) printf("左括号多于右括号!n") else printf("左右括号匹配正确!Ⅶn")
5 if(StackNotEmpty(myStack)) printf("左括号多于右括号！\n"); else printf("左右括号匹配正确！\n"); }
3.3队列 队列的基本概念 队尾插 1、队列定义只能在表的一端进行插入操作,在表的另一端 进行删除操作的线性表。 2、逻辑结构与线性表相同,仍为_对一关系。<队头删 3、存储结构顺序队列或链队列,以循环顺序队列更常见 4、运算规则只能在队首和队尾运算,且访问结点时依照 先进先出(FIFo)的原则 5、实现方式关键是掌握入队和出队操作,具体实现依顺 序队或链队的不同而不同。 基本操作:入队或出队,建空队列,判队空或队满等操作
6 3.3 队列 一、队列的基本概念 １、队列定义 ３、存储结构 ４、运算规则 ５、实现方式 ２、逻辑结构 只能在表的一端进行插入操作，在表的另一端 进行删除操作的线性表。 队尾插 入 队头删 除 与线性表相同，仍为一对一关系。 顺序队列或链队列，以循环顺序队列更常见。 只能在队首和队尾运算，且访问结点时依照 先进先出（FIFO）的原则。 关键是掌握入队和出队操作，具体实现依顺 序队或链队的不同而不同。 基本操作：入队或出队，建空队列，判队空或队满等操作
队列( Queue)是仅在表尾进行插入操作,在表头进 行删除操作的线性表。它是一种先进先出(FIF0) 的线性表。 例如:队列Q=(a1,a2,a3, 队首 队尾 在队尾插入元素称为入队;在队首删除元素称为 出队。 当队列中没有数据元素时称为空队列
7 队列 （Queue）是仅在表尾进行插入操作，在表头进 行删除操作的线性表。它是一种先进先出（ＦＩＦＯ） 的线性表。 例如：队列 Q= (a1 , a2 , a3 , ……….,an-1 , an ) 在队尾插入元素称为入队；在队首删除元素称为 出队。 当队列中没有数据元素时称为空队列。 队首 队尾
问:为什么要设计队列?它有什么独特用途? 答:1.离散事件的模拟(模拟事件发生的先后顺序, 例如CPU芯片中的指令译码队列); 2.操作系统中的作业调度(一个CPU执行多个 作业); 3.简化程序设计。 注:队列的实现方式是本节重点,关键是掌握入队和出队操作。 具体实现依存储结构(链队列或顺序队列)的不同而不同
8 注：队列的实现方式是本节重点，关键是掌握入队和出队操作。 具体实现依存储结构（链队列或顺序队列）的不同而不同。 1. 离散事件的模拟（模拟事件发生的先后顺序, 例如 CPU芯片中的指令译码队列）； 2. 操作系统中的作业调度（一个CPU执行多个 作业）； 3. 简化程序设计。 答： 问：为什么要设计队列？它有什么独特用途？
队列抽象数据类型 数据集合:{aa1,…,a1,…,an-1}a1的数据类型为 DataType 操作集合:(1) Queueinitiate(Q)初始化队列Q (2) QueueNotEmpty(Q)队列Q非空否 (3) QueueAppend(Q,x)入队列 (4) QueueDelete(Q,d)出队列 (5 QueueGet(Q, d) 取队头数据元素 等
9 二、队列抽象数据类型 数据集合：{a0 ,a1 ,…,ai ,…,an-1｝ ai的数据类型为 DataType 操作集合：(1)QueueInitiate(Q) 初始化队列Q (2)QueueNotEmpty(Q) 队列Q非空否 (3)QueueAppend(Q,x) 入队列 (4)QueueDelete(Q,d) 出队列 (5)QueueGet(Q,d) 取队头数据元素 等
顺序队列 1、顺序队列用顺序存储结构的队列。 、顺序队列的存储结构 它利用一个一维数组来 存储数据元素,另再设立 data 个队头指示器和一个队尾指 rear 示器分别指向当前队头元素 和当前队尾元素。用C语言 定义为 87654321 a(队尾) typedef struct 巴 a3 DataType queue MaxQueueSize a4(队头 int rear int front: 0 Seq qUeue;
10 三、顺序队列 1、顺序队列 采用顺序存储结构的队列。 2、顺序队列的存储结构 它利用一个一维数组来 存储数据元素，另再设立一 个队头指示器和一个队尾指 示器分别指向当前队头元素 和当前队尾元素。用C语言 定义为： typedef struct { DataType queue[MaxQueueSize]; int rear; int front; }SeqCQueue; a1 a2 a3 data a4 ８ ７ ６ ５ ４ ３ ２ １ ０ front rear (队尾) (队头)