数据结构第3章栈和队列.pptVIP

第三章栈和队列栈的定义及操作栈的定义及操作栈的定义及操作3.1.2栈的顺序存储结构顺序栈运算栈的共享3.1.3栈的链式存储结构链式栈操作3.2栈应用举例栈应用举例（数制转换）栈应用举例（括号匹配）栈应用举例（表达式）栈应用举例（表达式）栈应用举例（表达式）栈应用举例（表达式）栈应用举例（表达式）栈应用举例（表达式）栈应用举例（表达式）栈应用举例（表达式）3.3栈与递归函数栈与递归栈与递归（递归函数）栈与递归（hanoi塔）栈与递归（hanoi塔）栈与递归 编译系统在处理递归时，最重要的是设置一个栈S。在递归调用时，调用语句的返回地址和当前调用层的参数进栈，然后程序控制转向调用语句对应函数；而当调用返回时，退栈，使程序控制能返回到相应调用点的下一语句处往下执行。故有了LIFO这个特点的栈，递归函数调用与返回的实现就很方便了。3.3.2递归函数到非递归的转换 递归函数有算法简洁，清晰，可读性好和便于验证等优点。但递归到非递归的函数转换是基于以下两个方面的考虑：（1）有些算法语言（如FORTRAN）无递归功能；（2）递归函数的时间和空间复杂度一般较差，因系统内部需反复的进栈和出栈。故对一些常驻内存或对时间、空间复杂度有特别要求的程序，先用递归形式描述，然后将其转换成非递归的程序来运行。 递归到非递归函数的转换是一项较复杂的工作，尤其是间接递归的情况。但转换中一般都要用栈技术。下面讨论较为简单例子的转换。 递归函数到非递归的转换递归到非递归的转换3.4队列的定义及运算2．队列的抽象数据类型队列的抽象数据类型循环队列循环队列的操作循环队列的操作循环队列的操作循环队列的操作3.4.2链式队列及相关算法链式队列及相关操作链式队列及相关操作3.5队列应用举例迷宫问题迷宫问题迷宫问题3.5.2离散事件模拟离散事件模拟离散事件模拟离散事件模拟第三章小结GetHead(Q) 初始条件：队列Q已经存在且非空。操作结果：返回队头元素的值。QueueTraverse(Q)初始条件：队列Q已经存在且非空。操作结果：从队头到队尾依次调用Visit()函数访问Q中的每一个元素。}ADTQueue；3.4.2队列的顺序存储结构1．顺序队列的描述 队列的顺序存储结构主要以循环队列的形式体现。因为队列逻辑上也是线性表，故其存储结构基本上同线性表的顺序存储结构。描述如下： typedefstruct {datatypedata[maxsize];//队列的存储空间 intfront,rear;//队头，队尾指针 }squeue,*squlink;若说明squlinkQ;Q=(squlink)malloc(sizeof(squeue));则指针变量Q指向一个顺序队列，如图3.14、3.15所示。当要反复作进队操作时，Q-rear会达到maxsize-1，再进队就进不去了。但队的存储空间并不一定满，称这种现象为“假溢出”。为了克服假溢出（即只要队中有空余空间，就可以进队），将数组data首尾相连，构成所谓的循环队列，同时，为使队列的运算方便，设指针Q-front所指单元为引导节点，其下一位才是当前的队头元素a0，而Q-rear仍指向当前队列的队尾元素，其结构如图所示。a0an-1maxsize-1…Qrearj…Qfronti…Qdata[0]图3.15Qfronta0maxsize-10Qrearan-1头2．循环队列基本操作的算法实现进队、出队运算模运算m%n（m除以n的余数），如3%5=3，7%5=2，(x+1)%x=1等等。 进队运算是在队尾插入一元素e。先将Q-rear加1，然后e进入Q-rear所指单元，但当Q-rear已为maxsize-1时，加1后应回到0单元，故进队运算基本操作为： Q-rear=(Q-rear+1)%maxsize;Q-data[Q-rear]=e;出队运算是返回当前队头元素。先将Q-front加1，然后取队头；但当Q-front已为maxsize-1时，加1后应指向0号单元，故出队基