公共基础(二).ppt

全国计算机等级考试二级公共基础;;栈;错慷涧兵烁赚曾沪埃扦沉廖憋往澄道康溅战撮尊曲愁录阮墅霓伍况秆缉殉公共基础(二)公共基础(二);栈的特征;栈的基本运算; ;1.4.2 队列及其基本运算;下图是队列的示意图： 　　　　　 　　　　　　 a1　a2　…　an 　　 　　　　　 ;队列的顺序存储结构;存在问题 设数组维数为M，则： 当front=-1,rear=M-1时，再有元素入队发生溢出——真溢出 当front?-1,rear=M-1时，再有元素入队发生溢出——假溢出 解决方案 队首固定，每次出队剩余元素向下移动——浪费时间 循环队列 基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;;1;;队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。 队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。 队列运算包括 （1）入队运算：从队尾插入一个元素； （2）退队运算：从队头删除一个元素。 循环队列： s=0表示队列空 s=1且front=rear表示队列满;1.5.1 线性链表的基本概念 线性表顺序存储结构的特点：是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。 线性表顺序存储结构暴露的问题 在做插入或删除元素的操作时，会产生大量的数据元素移动； 对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用； 线性表的容量难以扩充。;线性表的链式存储结构;为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系 数据结构中的每一个元素对应于一个存储单元，这种存储单元称为存储结点，简称结点。 存储空间中的每一个结点分两部分：一部分用于存储元素的值，称数据域；另一部分用于存放下一个数据元素的 存储序号（存储结点的地址），即指向后件结点，称为指针域。; 例如 ：线性表 （a, b,c,d);在链式存储结构中，存储数据结构???存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。 链式存储方式即可用于表示线性结构，也可用于表示非线性结构。;head;110 hat 200;链式存储结构的特点 （1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致； （2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。;1.5.2 线性链表的基本运算;p;p;若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。 人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如图所示。 由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。; top;队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。;循环链表是表中最后一个结点的指针指向头结点，使链表构成环状 特点：从表中任一结点出发均可找到表中其他结点，提高查找效率 操作与单链表基本一致，它可以使空表和非空表的运算统一 单链表p或p-link=NULL 循环链表p或p-link=H;例题讲解;;; 如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是 A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e1,e2 D) 任意顺序 一些重要的程序语言(如C语言和Pascal语言) 允许过程的递归调用。而实现递归调用中的存储分配通常用 A) 栈 B) 堆 C) 数组 D) 链表 当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为 【2】 。;栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是 A) ABCED B) DCBEA C) DBCEA D) CDABE 栈通常采用的两种存储结构是 A) 顺序存储结构和链表存储结构B) 散列方式和索引方式 C) 链表存储结构和数组