《chap3栈和队列2》由会员分享，可在线阅读，更多相关《chap3栈和队列2（74页珍藏版）》请在金锄头文库上搜索。
1、1通常称，栈和队列是限定插入和删除通常称，栈和队列是限定插入和删除只能在表的只能在表的“端点端点”进行的线性表。进行的线性表。 线性表线性表 栈栈 队列队列Insert(L, i,x) Insert(S, n+1,x) Insert(Q,n+1,x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in栈和队列是两种常用的数据类型栈和队列是两种常用的数据类型23.1 栈的类型定义栈的类型定义3.2 栈的应用举例栈的应用举例3.3 栈类型的实现栈类型的实现3.4 队列的类型定义队列的类型定义3.5 队列类型的实现队列类型的实现33.1 栈的类型定义栈的
2、类型定义 ADT Stack 数据对象数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系数据关系： R1 | ai-1, aiD, i=2,.,n 约定约定an 端为栈顶，端为栈顶，a1 端为栈底。端为栈底。 基本操作基本操作： ADT Stack4InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit()5 InitStack(&S) 操作结果：构造一个空栈 S
3、。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。6 StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈， 则返回 TRUE，否则 FALE。7 StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回 S 的元素个数， 即栈的长度。8 GetTop(S, &e) 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回 S 的栈顶 元素。a1a2an 9 ClearStack(&S) 初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。10 Push(&S, e) 初始条件：栈 S 已存在。 操作结
4、果：插入元素 e 为新的 栈顶元素。a1a2ane 11 Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素， 并用 e 返回其值。a1a2anan-1 123.2 栈的应用举例栈的应用举例例例1 数制转换数制转换例例2 括号匹配的检验括号匹配的检验例例3 行编辑程序问题行编辑程序问题例例4 迷宫求解迷宫求解例例5 表达式求值表达式求值例例6 实现递归实现递归13 例1 数制转换数制转换 算法基于原理：算法基于原理： N = (N / d)d + N % d 14例如：（例如：（1348)10 = (2504)8 ，其运算过程如下：其运算过程如下： N N
5、 / 8 N % 81348 168 4 168 21 0 21 2 5 2 0 2计计算算顺顺序序输输出出顺顺序序15void conversion () InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N /= 8; while (!StackEmpty(S) Pop(S, e); printf ( %d, e ); / conversion16假设在表达式中假设在表达式中 （）或（）或（ ）等为正确的格式，等为正确的格式， （ ）或（）或（ ）或）或 ( )均为不正确的格式。均为不正确的格式。则则 检验括号是否匹配检验括号是否匹
6、配的方法可用的方法可用“期待的急迫程度期待的急迫程度”这个概念来描述。这个概念来描述。例2 括号匹配的检验括号匹配的检验17分析可能出现的分析可能出现的不匹配不匹配的情况的情况:到来的右括弧到来的右括弧非是所非是所“期待期待”的的;例如：考虑下列括号序列：例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8到来的是到来的是“不速之客不速之客”;直到结束，也没有到来直到结束，也没有到来所所“期待期待”的括弧的括弧;18算法的设计思想：算法的设计思想：1）凡出现）凡出现左括弧左括弧，则进栈；，则进栈；2）凡出现）凡出现右括弧右括弧，首先检查栈是否空，首先检查栈是否空 若栈空，则表明该若
7、栈空，则表明该“右括弧右括弧”多余多余 否则和栈顶元素比较，否则和栈顶元素比较， 若相匹配，则若相匹配，则“左括弧左括弧出栈出栈” 否则表明不匹配否则表明不匹配3）表达式检验结束时，）表达式检验结束时， 若栈空，则表明表达式中匹配正确若栈空，则表明表达式中匹配正确 否则表明否则表明“左括弧左括弧”有余有余19Status matching(string& exp) int state=1, i=0; while (expi & state) switch (expi) case (: Push(S,expi); i+; break; case ): if (!StackEmpty(S)&Get
8、Top(S)=( Pop(S,e); i+; else state = 0; break; if (StackEmpty(S) & state) return OK; return ERROR;20例3 行编辑程序问题行编辑程序问题如何实现？如何实现？“每接受一个字符即存入存储器每接受一个字符即存入存储器” ? 并不恰当！并不恰当！21 设立一个输入缓冲区，用以接受设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存用户输入的一行字符，然后逐行存入用户数据区入用户数据区; 并假设并假设“#”为退格为退格符，符，“”为退行符。为退行符。 在在用用户户输输入入一一行行的的过过程程中中，允允许
9、许 用用户户输输入入出出差差错错，并并在在发发现现有有误误时时 可以及时更正。可以及时更正。合理的做法是：合理的做法是：22假设从终端接受了这样两行字符：假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);则实际有效的是下列两行：则实际有效的是下列两行： while (*s) putchar(*s+);23 while (ch != EOF & ch != n) switch (ch) case # : Pop(S, c); break; case : ClearStack(S); break;/ 重置重置S为空栈为空栈 default
10、: Push(S, ch); break; ch = getchar(); / 从终端接收下一个字符从终端接收下一个字符 ClearStack(S); / 重置重置S为空栈为空栈if (ch != EOF) ch = getchar();while (ch != EOF) /EOF为全文结束符为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区将从栈底到栈顶的字符传送至调用过程的数据区;24常用常用“穷举求解穷举求解”的方法的方法例4 迷宫求解迷宫求解25求迷宫路径算法的基本思想是：求迷宫路径算法的基本思想是：若当前位置若当前位置“可通可通”，则纳入路，则纳入路径，继续前进径，继续前进;若当
11、前位置若当前位置“不可通不可通”，则后退，则后退，换方向继续探索换方向继续探索;若四周若四周“均无通路均无通路”，则将当前，则将当前位置从路径中删除出去。位置从路径中删除出去。26设定当前位置的初值为入口位置；设定当前位置的初值为入口位置； do 若当前位置可通，若当前位置可通， 则将当前位置插入栈顶；则将当前位置插入栈顶； 若该位置是出口位置，则算法结束；若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为否则切换当前位置的东邻方块为 新的当前位置；新的当前位置； 否则否则 while (栈不空）；栈不空）；求迷宫中一条从入口到出口的路径的算法：求迷宫中一条从入口到出口的路径的算法
12、：27若若栈不空且栈顶位置尚有其他方向未被探索栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为则设定新的当前位置为: 沿顺时针方向旋转沿顺时针方向旋转 找到的栈顶位置的下一相邻块；找到的栈顶位置的下一相邻块；若若栈不空但栈顶位置的四周均不可通栈不空但栈顶位置的四周均不可通，则删去栈顶位置；则删去栈顶位置；/ 从路径中删去该通道块从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置，若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空；直至找到一个可通的相邻块或出栈至栈空；若若栈空栈空，则表明迷宫没有通路。，则表明迷宫没有通路。28 限于二元运算符的表达式定义限于
13、二元运算符的表达式定义: 表达式表达式 := (操作数操作数) + (运算符运算符) + (操作数操作数) 操作数操作数 := 简单变量简单变量 | 表达式表达式 简单变量简单变量 : = 标识符标识符 | 无符号整数无符号整数例5 表达式求值表达式求值29设设 Exp = S1 + OP + S2则称则称 OP + S1 + S2 为为前缀表示法前缀表示法 S1 + OP + S2 为为中缀表示法中缀表示法 S1 + S2 + OP 为为后缀表示法后缀表示法 表达式的三种表示方法：表达式的三种表示方法：30例如例如: Exp = a b + (c d / e) f前缀式前缀式: + a b
14、c / d e f中缀式中缀式: a b + c d / e f后缀式后缀式: a b c d e / f + 结论结论:1）操作数之间的相对次序不变）操作数之间的相对次序不变;2）运算符的相对次序不同）运算符的相对次序不同;3）中缀式丢失了括弧信息，中缀式丢失了括弧信息， 致使运算的次序不确定致使运算的次序不确定;4)前缀式的运算规则为前缀式的运算规则为:连续出现的两个操作数和在它们连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一之前且紧靠它们的运算符构成一个最小表达式个最小表达式; 5)后缀式的运算规则为后缀式的运算规则为: 运算符在式中出现的顺序恰为运算符在式中出现的顺序恰为 表
15、达式的运算顺序表达式的运算顺序; 每个运算符和在它之前出现每个运算符和在它之前出现 且且 紧靠它的两个操作数构成一个最小紧靠它的两个操作数构成一个最小 表达式表达式;31如何从后缀式求值？如何从后缀式求值？先找运算符，先找运算符， 再找操作数再找操作数例如：例如： a b c d e / f +a bd/ec-d/e(c-d/e) f32l如何从原表达式求得后缀式？如何从原表达式求得后缀式？ 每个运算符的运算次序要由它之后的每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中一个运算符来定，在后缀式中,优先数高优先数高的运算符领先于优先数低的运算符。的运算符领先于优先数低的运算符。分析分
16、析 “原表达式原表达式” 和和 “后缀式后缀式”的运算符的运算符:原表达式原表达式: a + b c d / e f 后缀式后缀式: a b c + d e / f 33从原表达式求得后缀式的规律为：从原表达式求得后缀式的规律为：1) 设立设立运算符运算符栈栈;2) 设表达式的结束符为设表达式的结束符为“#”, 预设预设运算符栈的运算符栈的栈底为栈底为“#”3) 若若当前字符是当前字符是操作数操作数， 则则直接发送给后缀式直接发送给后缀式;344) 若若当前当前运算符的运算符的优先数高优先数高于栈顶于栈顶 运算符，则运算符，则进栈进栈;5) 否则，退出栈顶运算符发送给后否则，退出栈顶运算符发送
17、给后 缀式缀式; 6) “(” 对它之前后的运算符对它之前后的运算符起隔起隔离离 作用作用，“)”可视为自相应左括弧可视为自相应左括弧开开 始的表达式的结束符。始的表达式的结束符。从原表达式求得后缀式的规律为：从原表达式求得后缀式的规律为：35void transform(char suffix , char exp ) InitStack(S); Push(S, # ); p = exp; ch = *p; while (!StackEmpty(S) if (!IN(ch, OP) Pass( suffix, ch); else if ( ch!= # ) p+; ch = *p; else
18、 Pop(S, ch); Pass(suffix, ch); / while36switch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) Pass( Suffix, c); Pop(S, c); break; defult : while(GetTop(S, c) & precede(c,ch) Pass( Suffix, c); Pop(S, c); if ( ch!= # ) Push( S, ch); break; / switch37将所有的实在参数、返回地址等将所有的实在参数、返回地址等信息
19、信息传递给被调用函数传递给被调用函数保存保存;为被调用函数的局部变量为被调用函数的局部变量分配存储区分配存储区;将将控制转移控制转移到被调用函数的入口。到被调用函数的入口。 当在一个函数的运行期间当在一个函数的运行期间调用另一个调用另一个函数函数时，在时，在运行该被调用函数之前运行该被调用函数之前，需先完成三项任务：需先完成三项任务：例6 实现递归实现递归38保存保存被调函数的被调函数的计算结果计算结果;释放释放被调函数的被调函数的数据区数据区;依照被调函数保存的返回地依照被调函数保存的返回地址将址将控制转移控制转移到调用函数。到调用函数。从被调用函数从被调用函数返回返回调用函数调用函数之前之
20、前，应该完成下列三项任务：应该完成下列三项任务：39多个函数嵌套调用的规则是多个函数嵌套调用的规则是:此时的内存管理实行此时的内存管理实行“栈式管理栈式管理”后调用先返回后调用先返回 ！例如：例如：void main( ) void a( ) void b( ) a( ); b( ); /main / a / bMain的数据区的数据区函数函数a的数据区的数据区函数函数b的数据区的数据区 40递归工作栈：递归工作栈：递归过程执行过程中占用的递归过程执行过程中占用的 数据区。数据区。递归工作记录：递归工作记录：每一层的递归参数合成每一层的递归参数合成 一个记录。一个记录。当前活动记录：当前活动记
21、录：栈顶记录指示当前层的栈顶记录指示当前层的 执行情况。执行情况。当前环境指针：当前环境指针：递归工作栈的递归工作栈的栈顶指针。栈顶指针。递归函数执行的过程可视为同一函数递归函数执行的过程可视为同一函数进行嵌套调用，例如：进行嵌套调用，例如：41void hanoi (int n, char x, char y, char z) / 将塔座将塔座x上按直径由小到大且至上而下编号为上按直径由小到大且至上而下编号为1至至n/ 的的n个圆盘按规则搬到塔座个圆盘按规则搬到塔座z上，上，y可用作辅助塔座。可用作辅助塔座。1 if (n=1)2 move(x, 1, z); / 将编号为的圆盘从将编号为的
22、圆盘从x移到移到z3 else 4 hanoi(n-1, x, z, y); / 将将x上编号为至上编号为至n-1的的 / 圆盘移到圆盘移到y, z作辅助塔作辅助塔5 move(x, n, z); / 将编号为将编号为n的圆盘从的圆盘从x移到移到z6 hanoi(n-1, y, x, z); / 将将y上编号为至上编号为至n-1的的 / 圆盘移到圆盘移到z, x作辅助塔作辅助塔7 8 428 3 a b c返址返址 n x y z5 2 a c b5 1 a b c7 1 c a bvoid hanoi (int n, char x, char y, char z) 1 if (n=1)2 m
23、ove(x, 1, z); 3 else 4 hanoi(n-1, x, z, y); 5 move(x, n, z); 6 hanoi(n-1, y, x, z); 7 8 433.3 栈类型的实现栈类型的实现顺序栈链栈44/- 栈的顺序存储表示栈的顺序存储表示 - #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct ElemType *base; ElemType *top; int stacksize; SqStack; 类似于线性表的顺序映象实现，类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶
24、指针。指向表尾的指针可以作为栈顶指针。45Status InitStack (SqStack &S) / 构造一个空栈构造一个空栈S S.base=(ElemType*)malloc( STACK_INIT_SIZE * sizeof(ElemType); if (!S.base) exit (OVERFLOW); /存储分配失败存储分配失败 / 或：或：return ERROR; S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;46Status Push (SqStack &S, ElemType e) if (S.top -
25、 S.base = S.stacksize) /栈满栈满,存储扩容存储扩容 S.base = (ElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (ElemType); if (!S.base) exit (OVERFLOW); /分配失败分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK;47Status Pop (SqStack &S, ElemType &e) / 若栈不空，
26、则删除若栈不空，则删除S的栈顶元素，的栈顶元素， / 用用e返回其值，并返回返回其值，并返回OK； / 否则返回否则返回ERROR if (S.top = S.base) return ERROR; e = *-S.top; return OK;48栈顶指针栈顶指针链栈链栈a1an注意注意: 链栈中链栈中指针的方向指针的方向an-149 ADT Queue 数据对象：数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系：数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中约定其中a1 端为队列头端为队列头，an 端为队列尾端为队列尾基本操作：基本
27、操作：3.4 队列的类型定义队列的类型定义 ADT Queue50队列的基本操作：队列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTravers(Q, visit()51InitQueue(&Q) 操作结果：操作结果：构造一个空队列Q。DestroyQueue(&Q) 初始条件：初始条件：队列Q已存在。 操作结果：操作结果：队列Q被销毁， 不再存在。52 QueueEmpty(Q) 初始条件
28、：初始条件：队列Q已存在。 操作结果：操作结果：若Q为空队列， 则返回TRUE， 否则返回FALSE。53 QueueLength(Q) 初始条件：初始条件：队列Q已存在。 操作结果：操作结果：返回Q的元素个数， 即队列的长度。54 GetHead(Q, &e) 初始条件：初始条件：Q为非空队列。 操作结果：操作结果：用e返回Q的队头元素。a1a2an 55 ClearQueue(&Q) 初始条件：初始条件：队列Q已存在。 操作结果：操作结果：将Q清为空队列。56 EnQueue(&Q, e) 初始条件：初始条件：队列Q已存在。 操作结果：操作结果：插入元素e为Q的 新的队尾元素。a1a2an
29、e 57 DeQueue(&Q, &e) 初始条件：初始条件：Q为非空队列。 操作结果：操作结果：删除Q的队头元素， 并用e返回其值。a1a2an 58链队列链队列链式映象循环队列循环队列顺序映象3.5 队列类型的实现队列类型的实现59 typedef struct QNode / 结点类结点类型型 ElemType data; struct QNode *next; QNode, *QueuePtr;链队列链队列链式映象链式映象60typedef struct / 链队列类型链队列类型 QueuePtr front; / 队头指针队头指针 QueuePtr rear; / 队尾指针队尾指针
30、LinkQueue;a1anQ.frontQ.rearQ.frontQ.rear空队列空队列61 Status InitQueue (LinkQueue &Q) / 构造一个空队列构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存储分配失败存储分配失败 Q.front-next = NULL; return OK;62 Status EnQueue (LinkQueue &Q, ElemType e) / 插入元素插入元素e为为Q的新的队尾元素的新的队尾元素
31、p = (QueuePtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); /存储分配失败存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK;63 Status DeQueue (LinkQueue &Q, ElemType &e) / 若队列不空，则删除若队列不空，则删除Q的队头元素，的队头元素， /用用 e 返回其值，并返回返回其值，并返回OK; 否则返回否则返回ERROR if (Q.front = Q.rear) return ERROR;
32、p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = p) Q.rear = Q.front; free (p); return OK;64顺序队列顺序队列链队列链队列a1anQ.frontQ.reara1 0 1 2 n-1 n Q.frontQ.reara2a3anQ.baseQ.frontQ.reara1a2an65顺序队列顺序队列a1 0 1 2 n-1 n Q.frontQ.reara2a3anQ.baseQ.frontQ.reara1a2anQ.baseQ.frontQ.rearana2a166#defi
33、ne MAXQSIZE 100 /最大队列长度最大队列长度typedef struct ElemType *base; / 动态分配存储空间动态分配存储空间 int front; / 头指针，若队列不空，头指针，若队列不空， / 指向队列头元素指向队列头元素 int rear; / 尾指针，若队列不空，指向尾指针，若队列不空，指向 / 队列尾元素队列尾元素 的下一个位置的下一个位置 SqQueue;循环队列循环队列顺序映象顺序映象67 Status InitQueue (SqQueue &Q) / 构造一个空队列构造一个空队列Q Q.base = (ElemType *) malloc (MA
34、XQSIZE *sizeof (ElemType); if (!Q.base) exit (OVERFLOW); / 存储分配失败存储分配失败 Q.front = Q.rear = 0; return OK; 68Status EnQueue (SqQueue &Q, ElemType e) / 插入元素插入元素e为为Q的新的队尾元素的新的队尾元素 if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR; /队列满队列满 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK;69 Sta
35、tus DeQueue (SqQueue &Q, ElemType &e) / 若队列不空，则删除若队列不空，则删除Q的队头元素，的队头元素， / 用用e返回其值，并返回返回其值，并返回OK; 否则返回否则返回ERROR if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK;70第第 1 行行 1 1第第 2 行行 1 2 1 第第 3 行行 1 3 3 1第第 4 行行 1 4 6 4 1设第设第 i-1行的值行的值：(a0=0) a1.ai (ai
36、+1=0)则第则第 i 行的值行的值：bj = aj-1+aj, j=1,2,i+1例 二项式系数值（杨辉三角）二项式系数值（杨辉三角）71利用循环队列计算二项式的过程：利用循环队列计算二项式的过程：假设只计算四行，则队列的最大容量为假设只计算四行，则队列的最大容量为 5。1 1 00q.frontq.rear1 1 001q.frontq.rear1 1 021q.frontq.rear1 1 021q.frontq.rear1 0 021q.frontq.rear1 0 121q.frontq.rear721 0 121q.frontq.rear1 0 123q.frontq.rear1
37、0 133q.frontq.rear1 0 131q.frontq.reardo DeQueue(Q, S); GetHead(Q, e); if (e!=0) printf (“%d”, e); EnQueue(Q, s+e); while (e!=0);731. 1. 掌掌握握栈栈和和队队列列类类型型的的特特点点，并并能能在在相相应的应用问题中正确选用它们。应的应用问题中正确选用它们。2. 2. 熟熟练练掌掌握握栈栈类类型型的的两两种种实实现现方方法法，特特别别应应注注意意栈栈满满和和栈栈空空的的条条件件以以及及它它们们的的描述方法。描述方法。3. 3. 熟熟练练掌掌握握循循环环队队列列和和链链队队列列的的基基本本操操作作实实现现算算法法，特特别别注注意意队队满满和和队队空空的的描描述方法。述方法。 4. 4. 理理解解递递归归算算法法执执行行过过程程中中栈栈的的状状态态变化过程。变化过程。本章小结74
