中国科学技术大学：《数据结构及算法》课程教学资源（PPT课件讲稿）第3章 栈和队列

S > 链栈 栈顶 typedef LinkList LinkStack; InitStack L(LinkStack &S) Push L(LinkStack &S ,SelemType e) 栈底 Pop_L(LinkStackS ,SelemType &e) Bool GetTop L(Linkstack S,SElemType &e){ if(!S)return FALSE: e=S->data; return TRUE; ypb@ustc.edu.cn 6 中国科学技术大学

ypb@ustc.edu.cn 6 中国科学技术大学 ➢ 链栈 typedef LinkList LinkStack; InitStack_L(LinkStack &S) Push_L(LinkStack &S ,SelemType e) Pop_L(LinkStack S ,SelemType &e) Bool GetTop_L(Linkstack S,SElemType &e){ if(!S) return FALSE; e=S->data; return TRUE; } S ... 栈顶 栈底

3.3栈的应用 >例3.1数制转换 -算法3.11 void conversion0 N=a'dn+ad1+...+ard+ao >例3.2括号匹配检验 -算法3.12 bool match(0 a >例3.3背包问题求解 -算法3.13 void knapsack() -若可以w[n-l]>T,则应在pop前加入if(!StackEmpty(S) -外循环结束条件是：I(StackEmpty(S)&&k=n) >例3.4后缀表达式求值 -算法3.l4 void calculate(0 ypb@ustc.edu.cn 量树片做中国科学技术大学

ypb@ustc.edu.cn 7 中国科学技术大学 3.3栈的应用 ➢ 例3.1数制转换 – 算法3.11 void conversion() N=an d n+an-1 d n-1+…+a1 d+a0 ➢ 例3.2括号匹配检验 – 算法3.12 bool match() ➢ 例3.3 背包问题求解 – 算法3.13 void knapsack() – 若可以w[n-1]>T，则应在pop前加入 if(!StackEmpty (S)) – 外循环结束条件是：!(StackEmpty(S)&&k==n) ➢ 例3.4 后缀表达式求值 – 算法3.14 void calculate()

原表达式转化为后缀表达式 3.15 void transform(char suffix[],char exp[]) wrPt幻灯片放 规则 1)设立运算符栈，预设栈底为“#”，表达式的结束符为 "# 2)若当前字符是操作数，直接发送后缀表达式 3)若当前运算符是“(”，直接进栈，若当前运算符是“)” 从栈顶起依次退出栈顶运算符发送给后缀表达式，直至 栈顶相应运算符为"(”，“（不发送 4)若当前字符是运算符，且优先级大于栈顶运算符，则入 栈，否则退出栈顶运算符发送给后缀表达式，重复此过 程直至当前运算符优先级大于栈顶元素可以入栈，#不 入栈。 算法3.16：结合了算法3.14和3.15，直接运算中缀表达式> ypb@ustc.edu.cn 8 中国科学技术大学

ypb@ustc.edu.cn 8 中国科学技术大学 算法3.15 void transform(char suffix[],char exp[]) 规则 1)设立运算符栈，预设栈底为“#” ,表达式的结束符为“#” 2)若当前字符是操作数，直接发送后缀表达式 3)若当前运算符是“(” ，直接进栈，若当前运算符是“)” ， 从栈顶起依次退出栈顶运算符发送给后缀表达式，直至 栈顶相应运算符为“(” ， “(”不发送 4)若当前字符是运算符，且优先级大于栈顶运算符，则入 栈，否则退出栈顶运算符发送给后缀表达式，重复此过 程直至当前运算符优先级大于栈顶元素可以入栈，#不 入栈。 算法3.16：结合了算法3.14和3.15，直接运算中缀表达式。 原表达式转化为后缀表达式

3.4队列的基本概念 定义：队列(Queue)是限定只能在表得一端进 行插入在表的另一端进行删除操作的线性表 >队列的结构特点和操作 队列头(font)、队列尾(rear),先入先出(FIFO) >队列的ADT描述 ADT Queue D=aja;EElemSet,i=1,2,...n,n>0) QueueEmpty(Q) R={<a1,ala1,a∈D,i=2,3..n} QueueLength(Q) 基本操作： GetHead(Q,&e) InitQueue(&Q) EnQueue(&Q,e) DestroyQueue (&Q) Dequeue(&Q,&e) ClearQueue(&Q) QueueTraverse(Q) End ADT Queue ypb@ustc.edu.cn 9 中国科学技术大学

ypb@ustc.edu.cn 9 中国科学技术大学 3.4队列的基本概念 ➢ 定义：队列（Queue）是限定只能在表得一端进 行插入在表的另一端进行删除操作的线性表 ➢ 队列的结构特点和操作 队列头(front)、队列尾(rear)，先入先出(FIFO) ➢ 队列的ADT描述 ADT Queue｛ D={ai |aiElemSet,i=1,2,…n,n0} R={<ai-1 ,ai>|ai-1 ,aiD,i=2,3…n} 基本操作： InitQueue(&Q) DestroyQueue (&Q) ClearQueue(&Q) QueueEmpty(Q) QueueLength(Q) GetHead(Q,&e) EnQueue(&Q,e) Dequeue(&Q,&e) QueueTraverse(Q) }End ADT Queue

3.5队列的表示和实现 >顺序（循环）队列：队列首尾相接 表示结构 Q.rear M-1 typedefstruct{ Qelemtype *elem; int front; int rear, int queuesize; int incrementsize; Q.front }SqQueue; 空队列判断 不可用用首尾指针相等来判断队列的空 解决办法：1：增加标志位2：少用一个元素 ypb@ustc.edu.cn 10 中国科学技术大学

ypb@ustc.edu.cn 10 中国科学技术大学 ➢ 顺序(循环)队列：队列首尾相接 –表示结构 typedefstruct { Qelemtype *elem; int front; int rear; int queuesize; int incrementsize; }SqQueue; –空队列判断 不可用用首尾指针相等来判断队列的空 解决办法：1：增加标志位 2：少用一个元素 0 M-1 1 Q.front Q.rear …... 3.5队列的表示和实现