计算机软件就是基础 软件基础之数据结构-栈、队

《计算机软件就是基础 软件基础之数据结构-栈、队》由会员分享，可在线阅读，更多相关《计算机软件就是基础 软件基础之数据结构-栈、队（55页珍藏版）》请在金锄头文库上搜索。

1、作业: P102 2.16 2.17 2.21(1,2) 2.22 2.231第二章 常用数据结构及 其运算-栈与队2主要内容栈队列这两种结构都是特殊的线性表3栈栈的定义栈(stack)是限制线性表中元素的插入和删除只 能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称 为栈顶(Top)，另一端为固定的一端，称为栈底 (Bottom)。4根据栈的定义可知，最先放入栈中的元 素在栈底，最后放入栈中的元素在栈顶， 而删除元素刚好相反，最后放入的元素最 先删除，最先放入的元素最后删除。也就是说，栈是一种后进先出(Last In First Out)的线性表，简称为LIFO

2、表。没有元素时称为空栈5讨论输入序列为1 2 3的有关 情况： 反序： 正序： 其他:ana1退出栈 底栈 顶6栈的运算1、初始化栈：INISTACK(typedef struct elemtype StackStackSize;int top; seqstack; 10设S是seqstack类型的指针变量。若栈底位置 在向量的低端，即sdata0是栈底元素，那 么栈顶指针stop是正向增加的，即进栈时需 将stop加1，退栈时需将stop 减1。因此，s toptop =stacksize-1表示栈满 。当栈满时再做进栈运算必定产生空间溢出，简 称“上溢”;当栈空时再做退栈运算也将产生溢出，

3、 简称“下溢”。上溢是一种出错状态，应该设法避 免之；下溢则可能是正常现象，因为栈在程序中 使用时，其初态或终态都是空栈，所以下溢常常 用来作为程序控制转移的条件.11栈的五种运算（1）初始化栈void inistack(seqstack *s) S-top=-1; 12a3a2a1a4a3a2a1a2a1a5a4a3a2a1toptoptoptoptop进栈退栈栈空栈满13（）进栈void push(seqstack else s-stack+(s-top=x;return 1;14（）退栈elemtype popQstack (qstack *s)if (s-topStack(s-top)

4、-; 15（）取栈顶元素 elemtype gettopQstack (qstack *s) if (s-topStacks-top;16（5）判栈空否int NotemptyQstack (qstack *s) if (s-Toptop=MAXSIZE-1，栈满时 ，不能入栈; 否则出现空间溢出，引起错误，这 种现象称为上溢。 2. 出栈和读栈顶元素操作，先判栈是否为空 ，为空时不能操作，否则产生错误。通常栈空时 常作为一种控制转移的条件。 183、栈的共享存储单元有时，一个程序设计中，需要使用多个同一类型 的栈,这时候，可能会产生一个栈空间过小，容量发生溢 出，而另一个栈空间过大，造成大量

5、存储单元浪费的现 象。 为了充分利用各个栈的存储空间，这时可以采用多 个栈共享存储单元，即给多个栈分配一个足够大的存储 空间，让多个栈实现存储空间优势互补。19链栈链栈结构及数据类型栈的链式存贮结构,也称为链栈，它是一种限制运 算的链表，即规定链表中的插入和删除运算只能在链表 开头进行。链栈结构见图。以下的输入序列为an,an-1,a120栈的应用栈在日常生活中和计算机程序设计中有着许 多应用，下面仅介绍栈在计算机中的应用。算术表达式的求值算术表达式中包含了算术运算符和算术量(常 量、变量、函数)，而运算符之间又存在着优先级， 编译程序在求值时，不能简单地进行从左到右运算 ，必须先算运算级别高

6、的，再算运算级别低的，同 一级运算才从左到右.21因此，要实现表达式求值，必须设置两个栈， 一个栈存放运算符，另一个栈存放操作数（算术 量），在进行表达式求值时，编译程序从左到右 扫描，遇到操作数，一律进入操作数栈，遇到运 算符，则应与运算符栈的栈顶比较，若运算符优 先级高于栈顶则进栈，否则退栈，退栈后，在操 作数栈中退出两个元素(先退出在运算符右，后退 出在运算符左)，然后用运算符栈中退出的栈顶元 素进行运算，运算的结果存入操作数栈中，直到 扫描完毕。这时运算符栈为空，操作数栈中只有 一个元素，即为运算的结果。22算术表达式的两种表示方法，即中缀表示法和后缀表 示法。中缀表达式求值较麻烦（须

7、考虑运算符的优先级 ，甚至还要考虑圆括号），而后缀表达式求值较方便（ 无须考虑运算符的优先级及圆括号）。下面将介绍算术 表达式的中缀表示和后缀表示及它们的求值规律.例如，对于下列各中缀表达式： （1）3/5+8 （2）18-9*(4+3) （3）(25+x)*(a*(a+b)+b)对应的后缀表达式为： （1）3 5 / 8 + （2）18 9 4 3 + * - （3）25 x + a a b + * b + *23计算表达式:A/B*C+D=?ABC;/*AT1 ;/B*CT1AT1 ;/T2;A/ T1 T2T2D ;+ T3;T2+DT324函数的嵌套调用在函数嵌套调用中，一个函数的 执

8、行没有结束，又开始另一个函数的 执行，因此必须用栈来保存函数中中 断的地址，以便调用返回时能从断点 继续往下执行。例 设有一个主程序，它调用函数a ，函数a又调用函数b，函数b又调用函 数c，（见下页），其中r，s，t分别表 示中断地址，我们可以用一个栈来描 述调用情况（见下页）。25一般情况的示意图2627主程序调用函数a，留下一个断点地址r 进栈，然后主函数处于挂起状态，进入函数 a中执行，函数a中再调用函数b，留下一个 断点地址s进栈，然后函数a处于挂起状态， 进入函数b中执行，函数b中调用函数c， 留 下一个断点地址t进栈， 然后函数b处于挂起 状态，进入函数c中执行，函数c执行完后，

9、 要返回断点处继续执行，但返回到那一个断 点呢?根据栈顶元素来决定。返回时，执行 退栈操作，先退出t，故返回t断点继续执行 ， 接着退栈退出s，故返回s断点继续执行， 接着退栈退出r，返回r断点继续执行，最后 栈为空，算法结束。28子程序A子程序B子程序C主过程rs rt s rrs r调用B调用A调用C返回返回返回结束r:s:t:29函数的递归调用函数的递归调用也是一种嵌套, 故 也必须用栈来保存断点信息，但递归 调用相当于同一个函数的嵌套调用， 故除了保存断点信息外，还必须保存 每一层的参数、局部变量等。30Fib(5)Fib(4)Fib(3)Fib(1)Fib(3)Fib(2)Fib(2

10、)Fib(2)Fib(1)123 45678910111612 131415d3,3d4,3d2,4d2,4d2,4d2,4d2,4d5,4d7,3d8,3d1,5d1,5d1,5d1,5d1,5d1,5d1,5d1,5d1,5d6,5d6,5d6,5d6,5d6,512345678910111213141516n=531队列 队列的定义仅允许在一端进行插入，另一端进行删除的线 性表，称为队列(queue)。允许插入的一端称为队尾 (rear)，允许删除的一端称为队头（frort）。 队列是一种先进先出（First In First Out）的特殊 线性表，或称FIFO表。若队列中没有任何元素

11、，则称为空队列，否则称 为非空队列。 32队列在生活中的范例。 队列体现的思想。队列的描述可以用如图所示的方式所描述。33队列的基本运算队列可定义如下五种基本运算：1、初始化队列 INIQUEUE( /定义队列的最大容 量为maxlenstruct seqqueueelemtype queuemaxsize; /将队列中元素定为数组型 ，元素类型为elemtypeint front; /队头指针int rear; /队尾指针;35顺序队列将队列中元素全部存入一个一维数组中,数组 的低下标一端为队头,高下标一端为队尾，将这样 的队列看成是顺序队列。若一维数组中所有位置上都被元素装满，称 为队满，

12、即尾指针rear指向一维数组最后,而头指针 指向一维数组开头，称为队满。 frontrear012初始情况：36但有可能出现这样情况，尾指针指向一维数 组最后，但前面有很多元素已经出队，即空出很多 位置，这时要插入元素，仍然会发生溢出。如下图所示，若队列的最大容量maxsize=9， 此时，再进队时将发生溢出。我们将这种溢出称为 “假溢出”。frontrear 37要克服“假溢出”，1.可以将整个队列中元素向前移动;2.或者每次出队时，都将队列中元素前移一个位置。因此，顺序队列的队满判定条件为rear=maxsize。但 是，在顺序队列中，这些克服假溢出的方法都会引 起大量元素的移动，花费大量

13、的时间，所以在实际 应用中很少采用，一般采用下面的循环队列形式。38a5a4a3a2a1a5a4rear=0 front=0 rear=3 front=3 front=0 rear=5 rear=5 front=3 初始 front=rearfront=rear=0队满rear=m队尾指针指向当前队尾元素实际位置,队 头指针指向当前队头元素的前一位置.39循环队列为了克服顺序队列中假溢出，通常将一维 数组queue0到qmaxsize-1看成是一个首尾相接 的圆环，即queue0与queuemaxsize-1相接在一 起。将这种形式的顺序队列称为循环队列，见 图。4001Maxsize-1fr

14、ontrear2345678循环队列示意图41在循环队列中，若front=rear,则称为 队空， 若(rear+1)%maxsize=front, 则称为队满，这时，循环队列中能装入 的元素个数为maxsize-1,即浪费一个存储 单元，但是这样可以给操作带来较大方 便。424、循环队列上五种运算实现 （1）队列初始化Void INIQUEUE(seqqueue 43（2）进队列Void enqueue (seqqueue s.front=p; s.rear=p;49（2）判队空int empty(linkqueue s) if (s.front= =s.rear) return 1; el

15、se return 0;（3）取队头元素elemtype gethead(linkqueue s) if (s.front= =s.rear) return NULL;else return s.front-next-data;50（4）入队列void push(linkqueue p=(link*)malloc(sizeof(link);p-data=x; p-next= NULL ;s.rear-next=p; s.rear=p;51（5）出队列void pop(linkqueue p=s.front-next; /为了在后面的释放if (p-next= =NULL) /链队列中只有一个队头元 素,无其它元素s.front-next=NULL;s.rear=s.front;else s.front-next =p-next;free (p);52队列的应用 队列在日常生活中和计算机程序设计中， 有着非常重要的作用，在此，仅举出几个例子 来说明它，其它应用在后面章节中将会遇到。53第一个例子就是CPU资源的竞争问题。 在具有多个终端的计算机系统中，有多个 用户需要使用CPU各自运行自己的程序，它