第 3 章栈和队列 第 3 章栈和队列 3.1 栈 3.2 栈的应用举例 3.3 队列 哈尔滨工业大学 ( 威海 ) 计算机科学与技术学院 (2014/2015 学年秋季版 ) 1 本章重点难点 第 3 章栈和队列 重点 : (1) 栈 队列的定义 特点 性质和应用 ;(2)AT 栈 AT 队列的设计和实现以及基本操作及相关算法 难点 : (1) 循环队列中对边界条件的处理 ;(2) 分析栈和队列在表达式求值 括号匹配 数制转换 迷宫求解中的应用实例, 提高利用栈和队列解决实际问题的应用水平 3.1 栈 3.2 栈的应用举例 3.3 队列 2 3
3.1 栈 3.1.1 抽象数据类型栈的定义 3.1.1 抽象数据类型栈的定义 栈的定义栈 (Stack) 是一种特殊的线性表, 其插入和删除操作均在表的一端进行, 是一种运算受限的线性表 栈的术语栈顶 (top) 是栈中允许插入和删除的一端 栈底 (bottom) 是栈顶的另一端 4 5 3.1.1 抽象数据类型栈的定义 3.1.1 抽象数据类型栈的定义 栈的示意图 出栈 入栈 抽象数据类型 栈 AT Stack { 栈的特点 a n 后进先出 (Last In First Out, 简称 LIFO) 又称栈为后进先出表 ( 简称 LIFO 结构 ) a 2 a 1 栈顶 栈底 数据对象 : ={ a i a i ElemSet, i=1,2,...,n, n 0 数据关系 : R1={ <a i-1, a i > a i-1, a i, i=2,...,n 约定 a n 端为栈顶,a 1 端为栈底 基本操作 : AT Stack 见下页 6 7
3.1.1 抽象数据类型栈的定义 栈的基本操作 InitStack(&S) // 初始化栈 estroystack(&s) // 销毁栈 learstack(&s) // 清空栈 StackEmpty(S) // 判栈空 StackLength(S) // 求栈长度 GetTop(S, &e) // 取栈顶元素 Push(&S, e) // 入栈 Pop(&S, &e) // 出栈 StackTravers(S, visit()) // 遍历栈 3.1 栈 3.1.1 抽象数据类型栈的定义 8 9 顺序栈的 语言实现 //----- 栈的顺序存储表示 ----- #define STAK_INIT_SIZE 100; // 栈容量 #define STAKINREMENT 10; // 栈增量 typedef struct { SElemType *base; // 基地址 SElemType *top; // 栈顶指针 int stacksize; // 栈容量 SqStack; SqStack S; 栈初始化过程演示 (1) 给栈 S 申请栈空间 (2) 设置基地址 S.base 和栈顶地址 S.top (3) 设置栈容量 S.stacksize=STAK_INIT_SIZE S.base S.top 10 11
栈初始化算法 Status InitStack (SqStack &S){ // 构造一个空栈 S S.base=(ElemType*)malloc(STAK_INIT_SIZE* sizeof(elemtype)); if (!S.base) exit (OVERFLOW); // 存储分配失败 S.top = S.base; S.stacksize = STAK_INIT_SIZE; return OK; 入栈操作演示 (1) 如果栈满, 给栈增加容量 (2) 将数据存入栈顶位置, 栈顶后移一位 S.base a b c d e f e S.top S.top 12 13 入栈操作演示 Status Push (SqStack &S, SElemType e) { if (S.top - S.base >= S.stacksize) { S.base = (ElemType *) realloc ( S.base, (S.stacksize + STAKINREMENT) * sizeof (ElemType)); if (!S.base) exit (OVERFLOW); // 存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STAKINREMENT; *S.top++ = e; return OK; 其它栈操作讨论 estroystack(&s) // 销毁栈 learstack(&s) // 清空栈 StackEmpty(S) // 判栈空 StackLength(S) // 求栈长度 GetTop(S, &e) // 取栈顶元素 Pop(&S, &e) // 出栈 StackTravers(S, visit()) // 遍历栈 14 15
链栈的实现与链表的实现基本相同, 头结点作为栈顶位置 链栈的 语言类型定义 Typedef struct SNode { ElemType data; struct Snode *next; SNode, *LinkStack; // 数据域 // 链域 讨论链栈基本操作的实现 InitStack(&S) // 初始化栈 estroystack(&s) // 销毁栈 learstack(&s) // 清空栈 StackEmpty(S) // 判栈空 StackLength(S) // 求栈长度 GetTop(S, &e) // 取栈顶元素 Push(&S, e) // 入栈 Pop(&S, &e) // 出栈 StackTravers(S, visit()) // 遍历栈 16 17 第 3 章栈和队列 3.2 栈的应用举例 3.1 栈 3.2 栈的应用举例 3.3 队列 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.3 行编辑程序问题 3.2.5 表达式求值 18 19
计算顺出顺序 进制转换原理 : 任何 X 进制数 N 转换成 Y 进制数其结果都是要化成如下形式 N X a Y n 3.2.1 数制转换 n 2 0... a2 Y a1 Y a0 Y 转换的过程就是通过取余运算求出 a 0,a 1,, a n, 而先求出的是个位, 十位, 与我们写数的习惯先从高位写正好相反, 通过栈先进后出的特点, 很容易实现倒过来的过程 3.2.1 数制转换 将 10 进制 1348 转换成 8 进制. 过程如下 : N N div 8 N mod 8 输1348 168 4 序例 168 21 0 21 2 5 2 0 2 20 21 3.2.1 数制转换 10 进制数 N 转换成 8 进制的算法 void conversion () { InitStack(S); scanf ("%d", &N); while (N) { Push(S, N%8); N = N/8; while (!StackEmpty(S)) { Pop(S,e); printf ( "%d", e ); // conversion 3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.3 行编辑程序问题 3.2.5 表达式求值 22 23
问题描述 一个表达式中, 包含三种括号 ( 和 ), [ 和 ] 和 { 和, 这三种括号可以按任意的合法次序嵌套使用 ( 如 : [ { [ ] ] [ ] ( ) ) 设计算法检验表达式中所使用括号的合法性 问题讨论 3.2.2 括号匹配的检验 讨论 : 如果第一次遇到的右括号是 ], 那么前面出现的左括号有什么特点 结论 : 如果第一次遇到的右括号是 ], 那么急迫期待前面出现的最后一个左括号是 [ 算法过程 3.2.2 括号匹配的检验 (1) 当遇到左括号时, 进栈, 遇到右括号时出栈 ; (2) 当遇到某一个右括号时, 栈已空, 说明到目前为止, 右括号多于左括号 ; (3) 从栈中弹出的左括号与当前检验的右括号类型不同, 说明出现了括号交叉情况 ; (4) 算术表达式输入完毕, 但栈中还有没有匹配的左括号, 说明左括号多于右括号 期待的急迫程度 24 25 3.2.2 括号匹配的检验 括号匹配检验算法 Status check( ) { char ch; InitStack(S); while ((ch=getchar())!= #') { switch (ch) { case (ch=='(' ch=='[' ch=='{'):push(s,ch);break; case (ch== ')'): if (StackEmpty(S)) retrun FALSE; else { Pop(S,e); if(e!= '(') return FALSE; break; 26 3.2.2 括号匹配的检验 括号匹配检验算法 case (ch== ]'): if (StackEmpty(S)) retrun FALSE; else {Pop(S,e);if(e!= [') return FALSE; break; default:break; if (StackEmpty(S)) return TRUE; else return FALSE; 27
3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.3 行编辑程序问题 3.2.5 表达式求值 问题描述 3.2.3 行编辑程序问题 在用户输入一行的过程中, 允许用户输入出差错, 并在发现有误时可以及时更正 解决办法设立一个输入缓冲区, 用以接受用户输入的一行字符, 然后逐行存入用户数据区, 并假设 # 为退格符, @ 为退行符 28 29 3.2.3 行编辑程序问题例假设从终端接受了这样两行字符 : whli##ilr#e(s#*s) outcha@putchar(*s=#++); 则实际有效的是下列两行 : while (*s) putchar(*s++); 解决方案 : 栈作为输入缓冲区 ; 对接受字符判断, 非 # 非 @ 则压栈 ; 若为 # 则弹栈 ; 若为 @ 则清空栈 行编辑问题算法 void LineEdit(){ // 利用字符栈 S, 从终端接收一行并传送至调用过程的数据区 InitStack(S); ch=getchar(); while (ch!= EOF) { //EOF 为全文结束符 while (ch!= EOF && ch!= \n ) { 3.2.3 行编辑程序问题 estroystack(s); 30 31
switch (ch) { case '#' : Pop(S, c); break; case '@': learstack(s); break;// 重置 S 为空栈 default : Push(S, ch); break; ch = getchar(); // 从终端接收下一个字符 3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.3 行编辑程序问题 栈中字符传送至调用过程的数据区 ; learstack(s); // 重置 S 为空栈 if (ch!= EOF) ch = getchar(); 3.2.5 表达式求值 32 33 问题描述 如图表示一个迷宫, 有一个入口, 一个出口, 从一个位置可以向 8 个方向走,0 表示能走通,1 表示走不通, 求从入口到出口的路径 入口 0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 0 出口 用栈实现迷宫路径求解的过程 (1) 入口位置入栈, 作标记以免重复进入 (2) 从栈顶位置任选一个可以进的位置, 并将此位置作标记避免重复, 新进位置入栈 (3) 重复 (2), 若栈顶位置无路可走, 则退栈, 从新的栈顶重复 (2) (4) 直到找到出口, 从栈底到栈顶即是路径, 或者栈空, 表示从入口到出口没通路 34 35
四周墙壁解决办法如图 从某一点 [x][y] 出发搜索其四周的邻点 0 1 2 3 4 5 0 1 2 3 4 5 6 7 0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 0 maze[6][8] 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 maze[8][10] 36 [x-1][y-1] [x-1][y] [x-1][y+1] [x][y-1] [x][y] [x][y+1] [x+1][y-1] [x+1][y] [x+1][y+1] struct moved { int x,y; move[0].x=0 move[0].y=1... move[8]; move[1].x=1 move[7].x=-1 move[1].y=1 move[7].y=1 37 如何防止重复到达某位置 0 1 2 3 4 5 6 7 8 9 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 2 1 1 0 1 0 1 0 1 0 1 3 1 0 1 0 0 1 1 1 1 1 4 1 0 1 1 1 0 0 1 1 1 5 1 1 0 0 1 1 0 0 0 1 6 1 0 1 1 0 0 1 1 0 1 7 1 1 1 1 1 1 1 1 1 1 到达某点后, 将此点的值改为 -1 迷宫路径求解算法 设定当前位置的初值为入口位置 ; do{ 若当前位置可通, 则 { 将当前位置插入栈顶 ; 若该位置是出口位置, 则算法结束 ; 否则切换当前位置的东邻方块为新的当前位置 ; 否则 {. while ( 栈不空 ); maze[8][10] 38 39
迷宫路径求解算法 若栈不空且栈顶位置尚有其他方向未被探索, 则设定新的当前位置为 : 沿顺时针方向旋转找到的栈顶位置的下一相邻块 ; 若栈不空但栈顶位置的四周均不可通, 则 { 删去栈顶位置 ; 若栈不空, 则重新测试新的栈顶位置, 直至找到一个可通的相邻块或出栈至栈空 ; 3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.3 行编辑程序问题 3.2.5 表达式求值 若栈空, 则表明迷宫没有通路 40 41 3.2.5 表达式求值 3.2.5 表达式求值 问题描述 一个表达式由操作数 (operand) 运算符 (operator) 界限符 (delimiter) 组成 运算符和界限符统称为 算符, 写出 算符优先法 求值的算法 例 求 3*(2+3*5)+6 的值 算法求解过程设置两个栈, 一个存操作数, 栈名为 OPN, 一个存操作符, 栈名为 OPTR 栈 (1) 首先置操作数栈为空, 表达式起始符 # 为运算符栈的栈底元素 ; (2) 依次读入表达式中每个字符, 若是操作数则进 OPN 栈, 若是运算符则和 OPTR 栈的栈顶运算符比较优先权后作相应操作, 直到整个表达式操作完毕 42 43
3.2.5 表达式求值 算法求解过程 (1) 若栈顶运算符小于输入运算符, 输入运算符进栈 OPTR; (2) 若栈顶运算符等于输入运算符 ( 只有栈顶是 (, 输入是 ), 或者栈顶是 #, 输入是 #) 两种情况, 分别去除一对括号, 或结束 (3) 若栈顶运算符大于输入运算符, 弹出栈顶运算符, 从 OPN 中弹出两个操作数与弹出运算符计算后再存入 OPN 栈, 继续 3.2.5 表达式求值 表达式求值算法 OperandType EvaluateExpression(){ initstack(optr);push(optr, # ); initstack(opn);c=getchar(); while(c!= # ) GetTop(OPTR)!= # ){ if(!in(c,op)) { Push((OPN,c);c=getchar(); else switch(precede(gettop(optr),c)){ 44 45 case < : Push(OPTR,c);c=getchar();break; case = : Pop(OPTR,x);c=getchar;break; case > : Pop(OPTR,theta); Pop(OPN,a); Pop(OPN,b); Push(OPN,Operate(a,theta,b)); break; //switch 语句结束 //while 语句结束 return(gettop(opn)); // 算法结束 第 3 章栈和队列 3.1 栈 3.2 栈的应用举例 3.3 队列 46 47
队列的定义 3.3.1 抽象数据类型队列的定义 队列示意图 3.3.1 抽象数据类型队列的定义 队列 (Queue) 是一种运算受限的特殊的线性表, 它只允许在表的一端进行插入, 而在表的另一端进行删除 出队 a 1 a 2 a 3 a n 队头 队尾 入队 队列的术语 队尾 (rear) 是队列中允许插入的一端 队头 (front) 是队列中允许删除的一端 队列的特点 先进先出 (First In First Out, 简称 FIFO) 又称队列为先进先出表 48 49 抽象数据类型队列 AT Queue { 数据对象 : ={a i a i ElemSet, i=1,2,...,n, n 0 数据关系 : R1={ <a i-1,a i > a i-1, a i, i=2,...,n 约定其中 a 1 端为队列头, a n 端为队列尾 基本操作 : 3.3.1 抽象数据类型队列的定义 AT Queue 见下页 3.3.1 抽象数据类型队列的定义 队列的基本操作 InitQueue(&Q) // 初始化队列 estroyqueue(&q) // 销毁队列 QueueEmpty(Q) // 判队列是否空 QueueLength(Q) // 求队列长度 GetHead(Q, &e) // 取队头元素 learqueue(&q) // 清空队列 EnQueue(&Q, e) // 入队列 equeue(&q, &e) // 出队列 QueueTravers(Q, visit()) // 遍历队列 50 51
3.3.2 链队列 链队列结点实现 typedef struct QNode { // 结点类型 QElemType data; struct QNode *next; QNode, *QueuePtr; 带头结点的链队列示意图 Q.front Q.rear 3.3.2 链队列 ^ 头结点 空队列 链队列数据类型实现 typedef struct { // 链队列类型 QueuePtr front; // 队头指针 QueuePtr rear; // 队尾指针 LinkQueue; Q.front Q.rear a 1 a 2 a n ^ 52 53 3.3.2 链队列 带头结点的链队列初始化 Status InitQueue (LinkQueue &Q) { // 构造一个空队列 Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if (!Q.front) exit (OVERFLOW); // 存储分配失败 Q.front->next = NULL; return OK; 3.3.2 链队列 带头结点的链队列入队算法 Status EnQueue (LinkQueue &Q, QElemType e) { // 插入元素 e 为 Q 的新的队尾元素 p = (QueuePtr) malloc (sizeof (QNode)); if (!p) exit (OVERFLOW); // 存储分配失败 p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK; 54 55
3.3.2 链队列 带头结点的链队列出队算法 Status equeue (LinkQueue &Q, QElemType &e) { // 若队列不空, 则删除 Q 的队头元素, // 用 e 返回其值, 并返回 OK; 否则返回 ERROR if (Q.front == Q.rear) return ERROR; p = Q.front->next; e = p->data; Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front; free (p); return OK; 3.3.2 链队列 带头结点的链队列其它操作讨论 estroyqueue(&q) // 销毁队列 QueueEmpty(Q) // 判队列是否空 QueueLength(Q) // 求队列长度 GetHead(Q, &e) // 取队头元素 learqueue(&q) // 清空队列 QueueTravers(Q, visit()) // 遍历队列 56 57 顺序队列讨论 顺序队列讨论 循环队列属于顺序队列的一种, 讨论在采用一般顺序队列时出现的问题 4 3 E E E 4 3 2 E 2 1 0 B A B 1 0 A B A B A Sq.rear=5 sq.front=0 Sq.rear=5 Sq.front=1 Sq.rear=5 Sq.front=2 Sq.rear=5 Sq.front=5 Sq.rear=0 Sq.front=0 Sq.rear=1 Sq.front=0 Sq.rear=2 Sq.front=0 Sq.rear=5 Sq.front=0 讨论 : 在采用一般顺序队列时出现假上溢现象. 58 59
循环队列的定义 循环队列是顺序队列的一种特例, 它是把顺序队列构造成一个首尾相连的循环表 指针和队列元素之间关系不变 Sq.rear=4 Sq.front=2 E Sq.rear=0 Sq.front=2 E F Sq.rear=1 Sq.front=2 循环队列空状态和满状态的讨论 空状态 Sq.rear=0 Sq.front=0 满状态 E B A Sq.rear=0 Sq.front=0 讨论结论 : 循环队列空状态和满状态都满足 Q.front=Q.rear 60 61 循环队列空状态和满状态的判别 方案 1: 另设一个标志区别队列是空还是满 ; 例如 : 设一个变量 count 用来记录队列中元素个数, 当 count==0 时队列为空, 当 count== MAXQSIZE 时队列为满 循环队列空状态和满状态的判别 方案 2: 以 队头指针在队列尾指针的下一位置 ( 指环状的下一位置 ) 上 作为队列呈满状态的标志, 牺牲一个元素存储空间 ; 队满条件为 : (sq.rear+1) mod maxsize==sq.front 队空条件为 : sq.rear==sq.front 62 63
循环队列数据类型实现 #define MAXQSIZE 100 // 最大队列长度 typedef struct { QElemType *base; // 动态分配存储空间 int front; // 头指针, 若队列不空, // 指向队列头元素 int rear; // 尾指针, 若队列不空, 指向队列尾元素的下一个位置 SqQueue; SqQueue Sq; 循环队列初始化算法 Status InitQueue (SqQueue &Q) { // 构造一个空队列 Q Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType)); if (!Q.base) exit (OVERFLOW); // 存储分配失败 Q.front = Q.rear = 0; return OK; 64 65 循环队列入队算法 Status EnQueue (SqQueue &Q, ElemType e) { // 插入元素 e 为 Q 的新的队尾元素 if ((Q.rear+1) % MAXQSIZE == Q.front) return ERROR; // 队列满 Q.base[Q.rear] = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; 循环队列出队算法 Status equeue (SqQueue &Q, ElemType &e) { // 若队列不空, 则删除 Q 的队头元素, // 用 e 返回其值, 并返回 OK; 否则返回 ERROR if (Q.front == Q.rear) return ERROR; e = Q.base[Q.front]; Q.front = (Q.front+1) % MAXQSIZE; return OK; 66 67
分析以下两种状态如何求队列长度 求循环队列长度算法 int QueueLength(SqQueue Q) { return (Q.rear-Q.front+MaxSize)%MaxSize; sq->rear=4 sq->front=2 sq->rear=1 sq->front=4 68 69 本章小结 熟练掌握 : (1) 栈 队列的定义 特点和性质 ; (2) AT 栈 AT 队列的设计和实现以及基本操作及相关算法 重点学习 : AT 栈和队列在表达式求值 括号匹配 数制转换 迷宫求解中的应用, 提高利用栈和队列解决实际问题的应用水平 70