《《数据结构》(C语言版)第三章 栈和队列》由会员分享，可在线阅读，更多相关《《数据结构》(C语言版)第三章 栈和队列（77页珍藏版）》请在金锄头文库上搜索。
1、 通常称，栈和队列是限定插入和删除只 能在表的“端点”进行的线性表。线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x)1in+1Delete(L, i) Delete(S, n) Delete(Q, 1)1in栈和队列是两种常用的数据类型第三章第三章 栈和队列栈和队列3.1 3.1 栈栈 3.2 3.2 栈的应用举例栈的应用举例3.4 3.4 队列队列3.3 3.3 栈与递归的实现栈与递归的实现学习提要：1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法，特别应 注
2、意栈满和栈空的条件以及它们的描述方法。3.熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。4.理解递归算法执行过程中栈的状态变化过程。重难点内容：顺序栈的相关操作、循环队列的判空判满 3.1 3.1 栈（栈（stackstack）3.1.13.1.1 栈的类型定义栈的类型定义3.1.23.1.2 栈的表示和实现栈的表示和实现栈的定义：限定仅在表尾进行插入或删除操作的线性表。不含元素的空表称空栈。ana1a2.栈底栈顶.出栈进栈栈s=(a1,a2,an)特点：后进先出（LIFO）3.1.1 3.1.1 栈的类型定义栈的类型定义表尾栈顶 表头栈底ADT Stack 数据对
3、象：D ai | ai ElemSet, i=1,2,.,n, n0 数据关系：R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作： ADT Stack栈的抽象数据类型定义：InitStack( #define STACKINCREMENT 10; typedef struct SElemType *base; /栈底指针 SElemType *top; /栈顶指针 int stacksize; SqStack;实现：一维数组sMtop123450进栈 Push(if (!S.base) exit (OVERFLOW); /存储分配失败S.top =
4、 S.base;S.stacksize = STACK_INIT_SIZE;return OK; Status Push (SqStack if (!S.base) exit (OVERFLOW); /存储分配失败S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT; *S.top + + = e;return OK;Status Pop (SqStack e = *- -S.top;return OK; 0M-1栈1底栈1顶栈2底栈2顶在一个程序中同时使用两个栈二、链栈栈的链式存储结构。栈顶指针就是链表的头指针。注意: 链栈中
5、指针的方向栈顶指针a1anan-1v入栈操作push( top=p q=top ; top=top-next 3.2 3.2 栈的应用栈的应用3.2.1 3.2.1 数制转换数制转换 3.2.2 3.2.2 括号匹配的检验括号匹配的检验 3.2.3 3.2.3 行编辑程序问题行编辑程序问题 3.2.4 3.2.4 迷宫求解迷宫求解 3.2.5 3.2.5 表达式求值表达式求值3.2.1 数制转换十进制N和其他d进制数的转换原理:N=( N div d )*d + N mod d其中：div为整除运算，mod为求余运算toptop 4top40top405例如： (1348)10=(2504)8
6、，其运算过程如下：N N div 8 N mod 81348 168 4168 21 021 2 52 0 2计算顺序输出顺序top4052void conversion( ) /对于输入的任意一个非负十进制整数，/打印输出与其等值的八进制数initstack ( S );scanf (“%d”,N);while ( N ) push (S，N%8);N = N / 8;while ( ! Stackempty(s) )pop ( S,e );printf ( “%d”, e );/conversion3.3.2 括号匹配的检验则 检验括号是否匹配的方法可用 “期待的急迫程度”这个概念来描述。
7、假设在表达式中 （）或（ ） 等为正确的格式， （ ）或（ ）或 （）)均为不正确的格式。分析可能出现的不匹配的情况:到来的右括弧并非是所“期待”的；例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8到来的是“不速之客”； 直到结束，也没有到来所“期 待”的括弧。算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈” ，否则表明不匹配。3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。3.2.3 行编辑程序问题如何实现？“每接受一个字符即存入存储器” ?
8、 不恰当!合理的作法是：设立一个输入缓冲区，用以接受用 户输入的一行字符，然后逐行存入用 户数据区，并假设“#”为退格符，“” 为退行符。假设从终端接受了这样两行字符：whli#ilr#e（s#*s)outchaputchar(*s=#+);则实际有效的是下列两行：while (*s)putchar(*s+);while (ch != EOF break;case : ClearStack(S); break;/ 重置S为空栈default : Push(S, ch); break; ch = getchar(); / 从终端接收下一个字符ClearStack(S); / 重置S为空栈 if
9、(ch != EOF) ch = getchar();while (ch != EOF) /EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的 数据区；3.2.4 迷宫求解通常用的是“穷举求解”的方法。求迷宫路径算法的基本思想是：v若当前位置“可通”，则纳入路径， 继续前进; v若当前位置“不可通”，则后 退，换方向继续探索; v若四周“均无通路”，则将当 前位置从路径中删除出去。设定当前位置的初值为入口位置；do若当前位置可通，则将当前位置插入栈顶； 若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为新的当前位置；否则 while (栈不空）；求迷宫中一条从入口到出口的路径的
10、算法： 若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通， 则删去栈顶位置；/ 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；若栈空，则表明迷宫没有通路。typedef struct int ord; / 通道块在路径上的“序号”PosType seat; / 通道块在迷宫中的 “坐标位置”int di; / 从此通道块走向下一通道块的“方向” SElemType; / 栈的元素类型Status MazePath ( MazeType maze, Pos
11、Type start, PosType end ) InitStack(S); curpos = start; / 设定“当前位置”为“入口位置”curstep = 1; / 探索第一步do if (Pass (curpos) / 当前位置可以通过，即是未曾走到过的通道块else while ( !StackEmpty(S) ); return (FALSE); / MazePath FootPrint (curpos); e = ( curstep, curpos, 1 ); Push (S,e); / 加入路径 if ( curpos = end ) return (TRUE); / 到达
12、终点 curpos = NextPos ( curpos, 1 ); / 下一位置是当前位置的东邻 curstep+;else / 当前位置不能通过if (!StackEmpty(S) Pop (S,e);while (e.di=4 Pop (S,e); / 留下不能通过的标记，并退回一步 / whileif (e.di : / 退栈并将运算结果入栈Pop(OPTR, theta);Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch表达式的三种标识方法：设 Exp = S1 + OP + S2
13、则称 OP + S1 + S2 为前缀表示法 S1 + OP + S2 为中缀表示法 S1 + S2 + OP 为后缀表示法 例如: Exp = a b + (c d / e) f 前缀式: + a b c / d e f 中缀式: a b + c d / e f 后缀式: a b c d e / f + 结论:1）操作数之间的相对次序不变;2）运算符的相对次序不同;3）中缀式丢失了括弧信息，致使运算的次序不确定;4)前缀式的运算规则为: 连续出现的两个操作数和在它们 之前且紧靠它们的运算符构成一 个最小表达式;5)后缀式的运算规则为:运算符在式中出现的顺序恰为 表达式的运算顺序;每个运算符和
14、在它之前出现 且紧靠它的两个操作数构成一个最小表达式。以上讨论的表达式一般都是运算符在两个操作数中间（除单 目运算符外），这种表达式被称为中缀表达式。中缀表达式 有时必须借助括号才能将运算顺序表达清楚，处理起来比较 复杂。在编译系统中，对表达式的处理采用的是另外一种方法 ，即将中缀表达式转变为后缀表达式，然后对后缀式表达式 进行处理，后缀表达式也称为逆波兰式。波兰表示法（也称为前缀表达式）是由波兰逻辑学家 （Lukasiewicz）提出的，其特点是将运算符置于运算对象的 前面，如a+b表示为 +ab；逆波兰式则是将运算符置于运算对 象的后面，如a+b表示为ab+。中缀表达式经过上述处理后， 运算时按从左到右的顺序进行，不需要括号。得到后缀表达式后，我们在计算表达式时，可以设置一 个栈，从左到右扫描后缀表达式，每读到一个操作数就将其 压入栈中；每到一个运算符时，则从栈顶取出两个操作数进 行运算，并将结果压入栈中，一直到后缀表达式读完。最后 栈顶就是计算结果。r主程序s rrrs子过程1rst子过程2rst子过程3 3.3 3.3 栈栈与递归的实现与递归的实现当在一个函数的运行期间调用另一个函数时，在运行该被
