《数据结构第三章 栈和队列》由会员分享，可在线阅读，更多相关《数据结构第三章 栈和队列（92页珍藏版）》请在金锄头文库上搜索。
1、第三章第三章 栈和队列栈和队列中国海洋大学信息学院 魏振钢 Tel:0532-66781226 Email:通常称，栈和队列是限定插入和删除只能在表 的“端点”进行的线性表。线性表 栈 队列 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.2 栈的应用举例3.3 栈与递归的实现3.4 队列3.5 离散事件模拟本章主要内容：3.1 栈栈（Stack）是限定仅在表尾进行插入或删除操 作的线性表。通常称其表尾为栈顶
2、（top），表头端 称为栈底（bottom）。假设栈S= ai | ai ElemSet, i=1,2,.,n, n0 ，则称a1为栈底元素，an为栈顶元素，栈中元 素按a1,a2,an的次序进栈，退栈的第一个元素应为 栈顶元素。换句话说，栈的修改是按后进先出的原则 进行的。因此，栈又称为后进先出（last in first out）的线性表（简称LIFO表）。 3.1.1 抽象数据类型栈的定义ADT Stack 数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 数据关系：R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作：
3、 ADT Stack栈的抽象数据类型定义：数据对象：D=ai| aiElemSet, i=1,2,n, n0 数据关系：R1=|ai-1, aiD, i=1,2,n约定an端为栈顶，a1 端为栈底 基本操作： InitStack( /栈底指针SElemType *top; /栈顶指针int stacksize; SqStack其中， stacksize指示栈的当前可使用的最大 容量。Top为栈顶指针，其初值指向栈底，每当插 入新元素，指针top加1，删除栈顶元素时，指针 top减1。非空栈中，top始终指向栈顶元素的下一 个位置。顺序栈的定义：以下是顺序栈的模块说明。 /-ADT Stack的
4、表示与实现- /-栈的顺序存储表示- #define STACK_ INIT_ SIZE 100; /存储空间初始分配量 #define STACKINCREMENT 10; /存储空间分配增量 typedef struct SElemType *base; /在栈构造之前和销毁之后， base的值为NULLSElemType *top; /栈顶指针int stacksize; /当前已分配的存储空间，以元素为单位 SqStack-基本操作的函数原型说明-Status InitStack (SqStack / 构造一个空栈S Status DestroyStack (SqStack / 销毁栈
5、S，S不再存在 Status ClearStack (SqStack / 重置S 为空栈 Status StackEmpty (SqStack S ); /若栈为空栈，则返回TRUE，否则 返回FALSEint StackLength (SqStack S ); /返回S的元素个数，即栈的长度 Status GetTop (SqStack S , SElemType /从栈底到栈顶依次对栈中每个元素调用函数 visit()。一旦visit()失败，则操作失败/-基本操作的算法描述（部分）- Status InitStack (SqStack / 构造一个空栈SS.base = (SElemTy
6、pe*) malloc (STACK_INIT_SIZEsizeof (ElemType);if (! S.base) exit(OVERFLOW); /存储分配失败S.top =S.base;S.stacksize =STACK_INIT_SIZE;return OK; /InitStackStatus GetTop (SqStack S , SElemType e=*(S.top-1);return OK;/ GetTopStatus Push (SqStack if (! S.base ) exit(OVERFLOW); / 存储分配失败S.top =S.base+S.stacksize
7、; S.stacksize+= STACKINCREMENT /增加存储容量*S.top+=e; return OK; / PushStatus Pop (SqStack e=*-S.top;return OK;/ Pop3.2 栈的应用举例3.2.1 数制转换3.2.2 括号匹配的检验3.2.3 行编辑程序问题3.2.4 迷宫求解3.2.5 表达式求值3.2.1 数制转换十进制数N和其它d进制数的转换的算法基于原 理： N = (N div d)d + N mod d其中，div 相除取整，mod 相除取余。例如：（1348)10 = (2504)8 ，其运算过程如 下：N N div 8
8、N mod 81348 168 4168 21 021 2 52 0 2计算顺序输出顺序由于上述计算过程是从低位到高位顺序产 生八进制数的各个数位，而打印输出，一般来 说应从高位到低位进行，恰好和计算过程相反 。因此，若将计算过程中得到的八进制数的各 位顺序进栈，则按出栈序列打印输出的即为与 输入对应的八进制数。具体方法见算法3.1void conversion () /对于输入的任意一个非负十进制整数，/打印输出与其等值的八进制数InitStack(S); /构造空栈scanf (“%d“,N);while (N) Push(S, N % 8);N = N/8;while (!StackEm
9、pty(S) Pop(S,e);printf ( “%d“, e ); / conversion算法 3.1则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。3.2.2 括号匹配的检验 假设在表达式中，（）或 （ ），等为正确的格式，（ ）或（ ）或 （）) 均为不正确的 格式。分析可能出现的不匹配的情况: 到来的右括弧并非是所“期待”的；例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8 到来的是“不速之客”； 直到结束，也没有到来所“期待”的括弧 。算法的设计思想：1）凡出现左括弧，则进栈； 2）凡出现右括弧，首先检查栈是否空, 若栈空 ，则表明该“右括弧”多余
10、，否则和栈顶元素比 较，若相匹配，则“左括弧出栈” ，否则表明 不匹配。3）表达式检验结束时，若栈空，则表明表达式 中匹配正确，否则表明“左括弧”有余。Status matching(stringwhile (i: /退栈并将运算结果入栈Pop (OPTR, theta);Pop (OPND, b); Pop (OPND, a);Push (OPND, Operate (a, theta, b); break;/switch/whilereturn GetTop(OPND); /EvaluateExpression 算法 3.43.3 栈与递归的实现 阶乘函数：1、递归一个对象如果部分地由它自
11、身来定义（或描述 ），则称其为递归。例如：Fact(n)=1 n=0n*Fact(n-1) n=1 二阶Fibonacci数列：Fib(n)=0 n=01 n=1Fib(n-1)+ Fib(n-2) n12、递归函数一个直接调用自己或通过一系列的调用语句间 接地调用自己的函数，称作递归函数。 将所有的实在参数、返回地址等信息传递给被 调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务： 保存被调函数的计算结果； 释放被调函数的数据区； 依照被调函数保存的返回地址将控制转移到调 用函数
12、。从被调用函数返回调用函数之前，应该完成 下列三项任务：多个函数嵌套调用的规则是：此时的内存管理实行“栈式管理”后调用先返回 ！例如：void main( ) void a( ) void b( ) a( ); b( ); /main / a / bMain的数据区函数a的数据区函数b的数据区递归工作栈：递归过程执行过程中占用的数据区。递归工作记录：每一层的递归参数合成一个记录。当前活动记录：栈顶记录指示当前层的执行情况。当前环境指针：递归工作栈的栈顶指针。递归函数执行的过程可视为同一函数进行嵌套 调用，例如：一、问题的定义是递归的。例如，数学中的阶 乘函数、二阶Fibonacci函数等。递归
13、是程序设计中一个强有力的工具。那么， 如何设计递归过程呢？可根据以下几种情况考虑：二、有的数据结构，如二叉树、广义表等，由 于结构本身固有的递归特性，则它们的操作可递归 的描述。三、有些问题，虽然问题本身没有明显的递归 结构，但用递归求解比迭代求解更简单。如八皇后 问题、Hanoi塔问题等。1、每次只能移动一个圆盘；例3-2 （n阶Hanoi塔问题）假设有三个分别命名为X 、Y和Z的塔座，在X上插有n个直径大小各不相同 、依小到大编号为1，2，n的圆盘（如图3.5所示 ）。现要求将X轴上的n个圆盘移至Z上并仍按同样 的顺序叠排，圆盘移动时必须遵循下列规则：2、圆盘可以插在X、Y和Z中的 任一塔
14、座上；3、任何时候都不能将一个较大 的圆盘压在较小的圆盘之上。XYZ图3.5 3阶 Hanoi塔问题1、将压在编号为n 的圆盘之上的n-1个圆盘从塔 座X（依照上述法则）移至塔座Y上；如何实现移动圆盘的操作呢？当n=1时，问题 比较简单，只需将编号为1的圆盘从塔座X直接移至 塔座Z上即可；当n1时，该如何考虑呢？2、将编号为n 的圆盘从塔座X移至塔座Z上；3、再将塔座Y上的n-1个圆盘（依照上述法则） 移至塔座Z上；其中，将n-1个圆盘从一个塔座移至另一塔座的 问题是一个和原问题相同的问题，只是问题的规模 小1void hanoi (int n, char x, char y, char z) / 将塔座x上按直径由小到大且至上而下编号为1至n/ 的n个圆盘
