资源预览内容
第1页 / 共92页
第2页 / 共92页
第3页 / 共92页
第4页 / 共92页
第5页 / 共92页
第6页 / 共92页
第7页 / 共92页
第8页 / 共92页
第9页 / 共92页
第10页 / 共92页
亲,该文档总共92页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第三章第三章 栈和队列栈和队列中国海洋大学信息学院 魏振钢 Tel:0532-66781226 Email:wzgwzqouc.edu.cn通常称,栈和队列是限定插入和删除只能在表 的“端点”进行的线性表。线性表 栈 队列 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)是限定仅在表尾进行插入或删除操 作的线性表。通常称其表尾为栈顶(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 端为栈底。 基本操作: 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的表示与实现- /-栈的顺序存储表示- #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 / 销毁栈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 = (SElemType*) 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; 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 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 (!StackEmpty(S) Pop(S,e);printf ( “%d“, e ); / conversion算法 3.1则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。3.2.2 括号匹配的检验 假设在表达式中,()或 ( ),等为正确的格式,( )或( )或 ()) 均为不正确的 格式。分析可能出现的不匹配的情况: 到来的右括弧并非是所“期待”的;例如:考虑下列括号序列: ( ) 1 2 3 4 5 6 7 8 到来的是“不速之客”; 直到结束,也没有到来所“期待”的括弧 。算法的设计思想:1)凡出现左括弧,则进栈; 2)凡出现右括弧,首先检查栈是否空, 若栈空 ,则表明该“右括弧”多余,否则和栈顶元素比 较,若相匹配,则“左括弧出栈” ,否则表明 不匹配。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、递归一个对象如果部分地由它自身来定义(或描述 ),则称其为递归。例如:Fact(n)=1 n=0n*Fact(n-1) n=1 二阶Fibonacci数列:Fib(n)=0 n=01 n=1Fib(n-1)+ Fib(n-2) n12、递归函数一个直接调用自己或通过一系列的调用语句间 接地调用自己的函数,称作递归函数。 将所有的实在参数、返回地址等信息传递给被 调用函数保存; 为被调用函数的局部变量分配存储区; 将控制转移到被调用函数的入口。当在一个函数的运行期间调用另一个函数时,在运行该被调用函数之前,需先完成三项任务: 保存被调函数的计算结果; 释放被调函数的数据区; 依照被调函数保存的返回地址将控制转移到调 用函数。从被调用函数返回调用函数之前,应该完成 下列三项任务:多个函数嵌套调用的规则是:此时的内存管理实行“栈式管理”后调用先返回 !例如:void main( ) void a( ) void b( ) a( ); b( ); /main / a / bMain的数据区函数a的数据区函数b的数据区递归工作栈:递归过程执行过程中占用的数据区。递归工作记录:每一层的递归参数合成一个记录。当前活动记录:栈顶记录指示当前层的执行情况。当前环境指针:递归工作栈的栈顶指针。递归函数执行的过程可视为同一函数进行嵌套 调用,例如:一、问题的定义是递归的。例如,数学中的阶 乘函数、二阶Fibonacci函数等。递归是程序设计中一个强有力的工具。那么, 如何设计递归过程呢?可根据以下几种情况考虑:二、有的数据结构,如二叉树、广义表等,由 于结构本身固有的递归特性,则它们的操作可递归 的描述。三、有些问题,虽然问题本身没有明显的递归 结构,但用递归求解比迭代求解更简单。如八皇后 问题、Hanoi塔问题等。1、每次只能移动一个圆盘;例3-2 (n阶Hanoi塔问题)假设有三个分别命名为X 、Y和Z的塔座,在X上插有n个直径大小各不相同 、依小到大编号为1,2,n的圆盘(如图3.5所示 )。现要求将X轴上的n个圆盘移至Z上并仍按同样 的顺序叠排,圆盘移动时必须遵循下列规则:2、圆盘可以插在X、Y和Z中的 任一塔座上;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个圆盘
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号