第三章_栈和队列.pptVIP

第三章 栈和队列 姚昌辉 为什么学习栈与队列？ 3.1 栈 定 义：限定只能在表的一端进行插入和删除运算的线性表。 3.1 栈 栈的基本操作 InitStack(S)： 构造一个空栈S ClearStack(S)： 清除栈S中的所有元素 StackEmpty(S)：判断栈S是否为空，若为空，则返回 true；否则返回false GetTop(S) ： 返回S的栈顶元素，但不移动栈顶指针 Push(S, x) ：插入元素x为新的栈顶元素（入栈操作) Pop(S) ： 删除S的栈顶元素并返回其值（出栈操作） 顺序栈的入栈操作——例如用堆栈存放（A，B，C，D） 顺序栈出栈操作——例如从栈中取出‘B’ 顺序栈的基本操作 几点说明： 栈空条件：s. top =s. base 此时不能出栈 栈满条件：s.top-s.base=s.stacksize 进栈操作：*s.top++=e; 或*s.top=e; s.top++; 退栈操作：e=*--s.top； 或s.top--； e=*s.top； 当栈满时再做进栈运算必定产生空间溢出， 简称“上溢”; 当栈空时再做退栈运算也将产生溢出，简 称“下溢”。 链 栈 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是____。 A. edcba B. decba C. dceab D. abcde 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为____。 A. i B. n=i C. n-i+1 D. 不确定 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ __。(不带空的头结点) A. HS—＞next=s; B. s—＞next= HS—＞next; HS—＞next=s; C. s—＞next= HS; HS=s; D. s—＞next= HS; HS= HS—＞next; 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行__ __。(不带空的头结点) A. x=HS; HS= HS—＞next; B. x=HS—＞data; C. HS= HS—＞next; x=HS—＞data; D. x=HS—＞data; HS= HS—＞next; 3.2 栈的应用举例 由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。 如何从后缀式求值？ 先找运算符， 再找操作数 原表达式: a + b ? c ? d / e ? f 后缀式: a b c ? + d e / f ? ? 栈与递归的实现 栈与递归的实现 栈与递归的实现 若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。 递归函数执行的过程可视为同一函数进行嵌套调用。 栈与递归的实现 main() { int n = 5; int res = 0; res = fact(n); } 若栈采用链式存储结构，栈顶指针为top，向堆栈插入一个由P指向的新结点的过程是依次执行____________ 删除一个（出栈）执行__________ 中缀表达式A-(B+C/D)*E的后缀形式________ 假设称正读和反读都相同的字符序列为“回文”，例如，“abcddcba”、 “qwerewq”是回文，“ashgash”不是回文。是写一个算法判断读入的一个以‘@’为结束符的字符序列是否为回文。 队列的逻辑结构 定义 队列是只允许在一端删除，在另一端插入的顺序表 允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。 特性 先进先出(FIFO, First In First Out) （1）InitQueue(q) 初始化：初始化一个新的队列。 （2）QueueEmpty(q) 队列非空判断：若队列q不空，则返回TRUE；否则，返回FALSE。 （3）EnterQueue(q,x) 入队列：在队列q的尾部插入元素x，使元素x成为新的队尾。若队列满，则返回FALSE；否则，返回TRUE。 （4）DeleteQueue(q,x) 出队列：若队列q不空，则返回队头元素，并从队头删除该元素，队头指针指向原队头的后继元素；否则，返回空元素NULL。 （5）QueueHead(q) 取队头元素：若队列q不空，则返回队头元素；否则返回空元素NULL。 （6）QueueLength(q)求队列长度：返回队列的长度。 （7）ClearQueue(q) 队列置空，将