数据结构课程的内容.ppt

《数据结构课程的内容.ppt》由会员分享，可在线阅读，更多相关《数据结构课程的内容.ppt（44页珍藏版）》请在三一文库上搜索。

1、1,数据结构课程的内容,2,讨论：,已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，请写出在P结点后插入S结点的核心语句序列。 答：此题答案不唯一。,法二：已知P结点，则不必“顺藤摸瓜”，直接链接即可。 (4) S-next=P-next; (1) P-next=S;,法一：从头“摸”起： (7) Q=P; (11) P=L; (8) while(P-next!=Q)P=P-next; (10) P=Q; (4) S-next=P-next; (1) P-next=S;,3,3.1 栈（Stack）,第三章 栈和队列,3.2 队列（Queue）,1. 定义 2. 逻辑结构

2、3. 存储结构 4. 运算规则 5. 实现方式,1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式,4,1. 定义,3.1 栈,与同线性表相同，仍为一对一关系。,用顺序栈或链栈存储均可，但以顺序栈更常见,只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。,关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同。 基本操作有入栈、出栈、读栈顶元素值、建栈、或判断栈满、栈空等。,限定只能在表的一端进行插入和删除运算的线性表（只能在栈顶操作）,5,问：堆栈是什么？它与一般线性表有什么不同？,3.1 栈,答：堆栈是一种特殊的线性表，它只能在

3、表的一端（即栈顶）进行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同。,一般线性表 堆栈 逻辑结构：一对一 逻辑结构：一对一 存储结构：顺序表、链表 存储结构：顺序栈、链栈 运算规则：随机存取 运算规则：后进先出(LIFO),“进” 压入=PUSH（x) “出” 弹出=POP ( y ),6,栈 是仅在表尾进行插入、删除操作的线性表。 表尾(即 an 端)称为栈顶 top ; 表头(即 a1 端)称为栈底base,例如： 栈 s= (a1 , a2 , a3 , .,an-1 , an ),a1 称为 栈底元素 an 称为 栈顶元素,插入元素到栈顶（即表尾）的操作，称为入栈。 从栈顶

4、（即表尾）删除最后一个元素的操作，称为出栈。,教材P44对栈有更详细定义：,强调：插入和删除都只能在表的一端（栈顶）进行！,7,顺序栈示意图,8,表和栈的操作区别对线性表 s= (a1 , a2 , . , an-1 , an ),写入：vi= ai 读出： x= vi,压入：PUSH (an+1) 弹出： POP (x),前提：一定要预设栈顶指针top！,an+1,9,入栈操作例如用堆栈存放（A，B，C，D） （注意要遵循“后进先出” 原则）,A,A,C B A,B A,核心语句： top=L;,顺序栈中的PUSH函数 status Push(ElemType x) if(topM)上溢 e

5、lse vtop+=x; ,Push (B);,Push (C);,Push (D);,低地址L,Push (A);,高地址M,B,C,D,10,出栈操作例如从栈中取出B （注意要遵循“后进先出” 原则）,核心语句： Pop ( ); Pop ( ); Printf( Pop () );,顺序栈中的POP函数 status Pop( ) if(top=L) 下溢 else y=v-top; return(y); ,11,例1：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？,43512不可能实现，主要是其中的12顺序不能实现； 1

6、2345的输出可以实现，只需压入一个立即弹出一个即可。,435612中到了12顺序不能实现； 135426可以实现。,例2：如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？,答：,答：,12,例3（严题集3.1）一个栈的输入序列为123，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？,答：,可以通过穷举所有可能性来求解： 1入1出， 2入2出，3入3出， 即123； 1入1出， 2、3入3、2出， 即132； 1、2入，2出， 3入3出， 即231； 1、2入，2、1出，3入3出， 即213； 1、2、3入，3、2、1出， 即321； 合计有5种可能性

7、。,13,例4：计算机系2001年考研题（程序设计基础）,设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，b,A、D可以（ B、C不行）。,讨论：有无通用的判别原则？ 有。在可能的输出序列中，不存在这样的输入序列i，j，k，能同时满足 ijk 和 PjPkPi,答：,14,补充1： 若入栈动作使地址向高端增长，称为“向上生成”的栈； 若入栈动作使地址向低端增长，称为“向下生成”的栈； 对于向上生成的栈 入栈口诀：堆栈指针top先压后加（vtop+=x）； 出栈口诀：堆栈指针top先减后弹（y=v-top

8、) 。,3.1 栈,补充2： 栈不存在的条件： base=NULL; 栈为空 的条件 ： base=top; 栈满的条件 ： top-base=stacksize;,15,补充3：链栈 链栈示意图,16,链栈的入栈函数、出栈函数 （以头指针为栈顶，在头指针处插入或删除！）,公共说明部分： typedef struct snode SElemType data; struct snode *link; NODE; NODE *st, *p; int m=sizeof(NODE);,17,Push (SElemType x) p=(NODE*)malloc(m); if(!p)上溢 else p-

9、data=x; p-link=st; st=p; ,Status pop( ) if(st=NULL)下溢 elsey=st-data;p=st;st=st-link; free(p); return(y); ,链栈 入栈函数,链栈 出栈函数,插入表头,从表头删除,18, 链栈不必设头结点，因为栈顶（表头）操作频繁； 采用链栈存储方式，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。,说 明,19,问：为什么要设计堆栈？它有什么独特用途？,调用函数或子程序非它莫属； 递归运算的有力工具； 用于保护现场和恢复现场； 简化了程序设计的问题。,答：,20,数

10、制转换（十转N） P48 设计思路：用栈暂存低位值 例2：括号匹配的检验P49 设计思路：用栈暂存左括号 例3 ：表达式求值 -P52 设计思路：用栈暂存运算符 例4：汉诺仪（Hanoi）塔-P55 设计思路：用栈实现递归调用,例1：,21,例3 表达式求值 ( 这是栈应用的典型例子 ) 这里，表达式求值的算法是 “算符优先法”。,例如：3*（7 2 ） （1）要正确求值，首先了解算术四则运算的规则： a. 从左算到右 b. 先乘除，后加减 c. 先括号内，后括号外 由此，此表达式的计算顺序为： 3*（7 2 ）= 3 * 5 = 15,22,（2）根据上述三条运算规则，在运算的每一步中，对任

11、意相继出现的算符1和2 ，都要比较优先权关系。 算符优先法所依据的算符间的优先关系见教材P53表3.1 （是提供给计算机用的表！） 由表可看出，右括号 ) 和井号 # 作为2时级别最低； 由c 规则得出： * ，/， + ，-为1时的优先权低于（，高于） 由a规则得出：（=） 表明括号内运算，已算完。 # = # 表明表达式求值完毕。,栈的应用（表达式求值）,23,（3）算法思想： 设定两栈：操作符栈 OPTR ，操作数栈 OPND 栈初始化：设操作数栈 OPND 为空；操作符栈 OPTR 的栈底元素为表达式起始符 #； 依次读入字符：是操作数则入OPND栈，是操作符则要判断： if 操作符

12、栈顶元素，压入OPTR栈。,栈的应用（表达式求值）,24,栈的应用（表达式求值）,25,Status EvaluateExpression( OperandType /EvaluateExpression,此函数在哪里？,26,例4 汉诺仪（ Hanoi）塔 传说在创世纪时，在一个叫Brahma的寺庙里，有三个柱子，其中一柱上有64个盘子从小到大依次叠放，僧侣的工作是将这64个盘子从一根柱子移到另一个柱子上。 移动时的规则： 每次只能移动一个盘子； 只能小盘子在大盘子上面； 可以使用任一柱子。 当工作做完之后，就标志着世界末日到来。,分析： 设三根柱子分别为 x，y, z , 盘子在 x 柱上

13、，要移到 z 柱上。 1、当 n=1 时，盘子直接从 x 柱移到 z 柱上； 2、当 n1 时, 则设法将 前 n 1 个盘子 借助 z ，从 x 移到 y 柱上，把 盘子 n 从 x 移到 z 柱上； 把n 1 个盘子 从 y 移到 z 柱上。,n,n 1,27,Void Hanoi ( int n, char x, char y, char z ) /将 n 个 编号从上到下为 1n 的盘子从 x 柱，借助 y 柱移到 z 柱 if ( n = = 1 ) move ( x , 1 , z ) ; /将编号为 1 的盘子从 x 柱移到 z 柱 else /将 n -1个 编号从上到下为1n

14、-1的盘子从 x 柱，借助 y 柱移到 z 柱 Hanoi ( n-1 , x , z , y ) ; move ( x , n, z) ; /将编号为 n 的盘子从 x 柱移到 z 柱 /将 n -1个 编号从上到下为 1n-1的盘子从 y 柱，借助 x 柱移到 z 柱 Hanoi ( n-1 , y , x , z ); /Hanoi,28,定 义,3.2 队列,与同线性表相同，仍为一对一关系。,顺序队或链队，以循环顺序队更常见。,只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。,关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。 基本操作有入队或出队，建空队

15、列，判队空或队满等操作。,只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表 （头删尾插）,29,队列 （Queue）是仅在表尾进行插入操作，在表头进行删除操作的线性表。 表尾即 an 端，称为 队尾 ； 表头即 a1 端，称为队头。 它是一种先进先出（）的线性表。,例如：队列 Q= (a1 , a2 , a3 , .,an-1 , an ),插入元素称为入队；删除元素称为出队。,队头,队尾,教材P59对队列有更详细定义：,队列的抽象数据类型定义见教材5960 队列的存储结构为链队或顺序队 （常用循环顺序队）,30,链队列示意图,讨论： 空队列的特征？, 怎样实现入队和出队操作？ 入

16、队（尾部插入）：rear-next=S; rear=S; 出队（头部删除）：front-next=p-next;,完整动作设计参见教材P61-62, 队列会满吗？,front=rear,一般不会，因为删除时有free动作。除非内存不足！,31,顺序队示意图,(队尾),(队首), 队列会满吗？ 很可能会，因为数组前端空间无法释放。因此数组应当有长度限制。, 空队列的特征？ 约定：front=rear,队尾后地址,入队(尾部插入)：vrear=e; rear+; 出队(头部删除)：x=vfront; front+;,讨论：,假溢出,有缺陷, 怎样实现入队和出队操作？,3.2 队列,32,问：什么叫

17、“假溢出” ？如何解决？,答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。,3.2 队列,解决假溢出的途径采用循环队列,33,循环队列（臆造）,顺序队列,新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！ 解决方案有三： 加设标志位，让删除动作使其为1,插入动作使其为0,则可识别当前 front=rear 使用一个计数器记录队列中元素个数（即队列长度）； 人为浪费一个单元，令队满特征为front=(rear+1)%N；,34,队空条件 : front = rear (初始化时：f

18、ront = rear ) 队满条件： front = (rear+1) % N (N=maxsize) 队列长度：L=（Nrearfront）% N,选用空闲单元法：即front和rear之一指向实元素，另一指向空闲元素。,问2： 在具有n个单元的循环队列中，队满时共有多少个元素？,n-1个,6,问1：左图中队列长度L=？,35,例1： 一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置?,解：由图可知，队头和队尾指针的初态分别为front=1和rear=6。,删除4个元素后front=5；再插入4个元素后，r=(6+4)%6=4,36,例2 ：数

19、组n用来表示一个循环队列，f 为当前队列头元素的前一位置，r 为队尾元素的位置。假定队列中元素的个数小于n，计算队列中元素的公式为:,（） rf （）（nfr）% n （）nrf （） （nrf）% n,4种公式哪种合理？ 当 r f 时（A）合理； 当 r f 时（C）合理；,分析 ：,综合2种情况，以（D）的表达最为合理,例3：在一个循环队列中，若约定队首指针指向队首元素的前一个位置。那么，从循环队列中删除一个元素时，其操作是 先 ，后 。,移动队首指针,取出元素,37,问：为什么要设计队列？它有什么独特用途？,离散事件的模拟（模拟事件发生的先后顺序）； 操作系统中多道作业的处理（一个CP

20、U执行多个作业）； 3. 简化程序设计。,答：,循环队列的操作实现见教材P64,38,循环队列的操作实现,1）初始化一空队列,算法要求：生成一空队列 算法操作：为队列分配基本容量空间 设置队列为空队列， 即 front=rear=0（也可为任意单元，如 2，或 4）;,39,算法：,Status InitQueue ( SqQueue ,新开单元的地址为0则表示内存不足,40,算法说明：向循环队列的队尾插入一个元素 分 析： (1) 插入前应当先判断队列是否满 if ( q . rear + 1 ) % QUEUE_MAXSIZE )=q.front) return ERROR; (2）插入动

21、作 q.base q.rear = e; q.rear = ( q . rear + 1 ) % QUEUE_MAXSIZE;,2） 入队操作,41,Status EnQueue(SqQueue ,2） 入队操作（完整函数）,42,3）出队操作,算法说明：删除队头元素，返回其值 e 分 析： （1） 在删除前应当判断队列是否空； if (q.front = q.rear ) return ERROR; （2）插入动作分析； 因为队头指针front指向队头元素的位置，所以： e = q.base q.front ; q.front = ( q . front + 1 ) % QUEUE_MAXSIZE;,43,Status DeQueue ( SqQueue / DeQueue,算法：,44,讨论（代本章小结）,线性表、栈与队的异同点 相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。 不同点： 运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。,