公共基础课件二.ppt

全国计算机等级考试 二级公共基础 计算机科学与技术系 董 再 秀 1数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A线性结构 B非线性结构 A 顺序存储 B 链式存储 线性表 栈 队 树形结构 图形结构 数据结构的三个方面 (亦称物理结构) 栈 栈是一种特殊的线性表。其特殊性在于限定插入和删 除数据元素的操作只能在线性表的表尾端进行。如下 所示： 进行插入和删除的表尾端是浮动端，通常被称为栈顶 ， an 为栈顶元素， 并用一个“栈顶指针”指示；而 表头端是固定端，通常被称为栈底，a1为栈底元素。 我们经常将栈用下图的形式描述： a1, a2, a3, ., an 插入和删除端 栈的特征 结论：后进先出（Last In First Out），简称为LIFO线 性表。 举例1：家里吃饭的碗，通常在洗干净后一个一个地 落在一起存放，在使用时，若一个一个地拿，一定最 先拿走最上面的那只碗，而最后拿出最下面的那只碗 。 举例2：在建筑工地上，使用的砖块从底往上一层一 层地码放，在使用时，将从最上面一层一层地拿取。 举例3：子弹夹。 栈的基本运算 （1）插入元素称为入栈运算； （2）删除元素称为退栈运算； （3）读栈顶元素是将栈顶元素赋给一个指定的变量， 此时指针无变化 bottom A B C D E top top=0 栈空 Top=m 栈满 （m为栈的最大容量 ） bottom top B A 1 2 3 4 5 1 2 3 4 5 bottom top B A 1 2 3 4 5 C D 1.4.2 队列及其基本运算 队列(Queue)也是一种运算受限的线性表。它只允许在 表的一端进行插入，而在另一端进行删除。允许删除 的一端称为队头(front)，允许插入的一端称为队尾 (rear)。 例如：排队购物。操作系统中的作业排队。先进入队 列的成员总是先离开队列。因此队列亦称作先进先出 (First In First Out)的线性表，简称FIFO表。 当队列中没有元素时称为空队列。在空队列中依次加 入元素a1,a2,an之后，a1是队头元素，an是队尾元素 。显然退出队列的次序也只能是a1,a2,an ，也就是 说队列的修改是依先进先出的原则进行的。 下图是队列的示意图： a1 a2 an 出队入队 队列的顺序存储结构 front=-1 rear=-1 1 2 3 4 5 0 队空 1 2 3 4 5 0 front J1,J1,J3入队 J1 J2 J3 rear rear 1 2 3 4 5 0 J4,J5,J6入队 J4 J5 J6 front 设两个指针front,rear,约定： rear指示队尾元素； front指示队头元素前一位置 初值front=rear=-1 空队列条件：front=rear 入队列：sq+rear=x; 出队列：x=sq+front; rear rear front rear 1 2 3 4 5 0 J1,J2,J3出队 J1 J2 J3 front front front 实现：用一维数组实现sqM 存在问题 设数组维数为M，则： v 当front=-1,rear=M-1时，再有元素入队发生溢出真 溢出 v 当front-1,rear=M-1时，再有元素入队发生溢出假 溢出 解决方案 v 队首固定，每次出队剩余元素向下移动浪费时间 v 循环队列 基本思想：把队列设想成环形，让sq0接在sqM-1 之后，若rear+1=M,则令rear=0; 1 M 2 front rear . . 入队运算是指在循环队列的队尾加入一 个新元素 (1)首先将队尾指针进一,即rear=rear+1,并 当rear=m+1时置rear=1。 (2)然后将新元素插入到队尾指针指向的位 置。 出队运算是指在循环队列的排头位置退 出一个元素并赋给指定变量。 (1)首先将排头指针进一，即front=front+1, 并且当front=m+1时置front=1 (2)然后将排头指针指向的元素赋值给指定 变量 1 2 3 4 5 6 rear front J4 J5 J6 1 2 3 4 5 6 rear front J9 J8 J7 J4 J5 J6 1 2 3 4 5 6 rear front 初始状态 J4,J5,J6出队 J7,J8,J9入队 队空：front=rear 队满：front=rear 解决方案： 另外设一个标志以区别队空、队满 S=0 (队空) S=1 (队满) 队列是指允许在一端（队尾）进入插入，而在另一端 （队头）进行删除的线性表。Rear指针指向队尾， front指针指向队头。 队列是“先进先出”（FIFO）或“后进后出”（LILO ）的线性表。 队列运算包括 （1）入队运算：从队尾插入一个元素； （2）退队运算：从队头删除一个元素。 循环队列： s=0表示队列空 s=1且front=rear表示队列满 队列特征总 结 1.5.1 线性链表的基本概念 线性表顺序存储结构的特点：是一种简单、方便的存储方式 。它要求线性表的数据元素依次存放在连续的存储单元中， 从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存 储方式属于静态存储形式。 线性表顺序存储结构暴露的问题 v 在做插入或删除元素的操作时，会产生大量的数据元 素移动； v 对于长度变化较大的线性表，要一次性地分配足够的 存储空间，但这些空间常常又得不到充分的利用； v 线性表的容量难以扩充。 1.5 线性链表 线性表的链式存储结构 线性表的链式存储结构： 指用一组任意的存储单元（可以连续，也可以不连续 ）存储线性表中的数据元素。 链表中结点的逻辑次序和物理次序不一定相同 为了存储线性表中的每一个元素，一方面要存储数据 元素的值，另一方面要存储各数据元素之间的前后件 关系 数据结构中的每一个元素对应于一个存储单元，这种 存储单元称为存储结点，简称结点。 存储空间中的每一个结点分两部分：一部分用于存储 元素的值，称数据域；另一部分用于存放下一个数据 元素的 存储序号（存储结点的地址），即指向后件结 点，称为指针域。 data Next/lin k 指针域，用来存放结点 的直接后继的地址 数据域，用来 存放结点的值 例如 ：线性表 （a, b,c,d) 在链式存储结构中，存储数据结构的存储空间可以不连续 ，各数据结点的存储顺序与数据元素之间的逻辑关系可以 不一致，而数据元素之间的逻辑关系是由指针域来确定的 。 链式存储方式即可用于表示线性结构，也可用于表示非线 性结构。 headd c b a 线性（单）链表的逻辑结构 null 其中，head是头指针，它指向单链表中的第一个结点，这是 单链表操作的入口点。由于最后一个结点没有直接后继结点 ，所以，它的指针域放入一个特殊的值NULL。NULL值在图示 中常用（）符号表示。 L 双向链表： R 110 hat 200 130 cat 135 135 eat 170 160 mat NULL 165 bat 130 170 fat 110 200 jat 205 205 lat 160 165 head 头指针 数据域 指针域 例如：线性表 （bat,cat,eat,fat,hat,jat,lat,mat ） bat cat eat mat head 链式存储结构的特点 （1）线性表中的数据元素在存储单元中的存放顺序 与逻辑顺序不一定一致； （2）在对线性表操作时，只能通过头指针进入链表 ，并通过每个结点的指针域向后扫描其余结点，这样就 会造成寻找第一个结点和寻找最后一个结点所花费的时 间不等，具有这种特点的存取方式被称为顺序存取方式 。 1.5.2 线性链表的基本运算 1、在线性链表中查找指定元素 在对线性链表进行插入或删除的运算中，总是首先需 要找到插入或删除的位置，这就需要对线性链表进行 扫描查找，要找到线性链表中指定值的前一个结点。 查找：查找单链表中是否存在结点X，若有则返回指 向X结点的指针；否则返回NULL 算法评价 pab xs 插入：在线性表两个数据元素a和b间插入x，已知p指向a s-link=p-link; p-link=s; v算 法评价 pabc 删除：删除链表中b结点，已知p指向a结点 p-link=p-link-link v算 法评价 若是栈中元素的数目变化范围较大或不清楚栈元素的 数目，就应该考虑使用链式存储结构。 人们将用链式存储结构表示的栈称作“链栈”。链栈 通常用一个无头结点的单链表表示。如图所示。 由于栈的插入删除操作只能在一端进行，而对于单链 表来说，在首端插入删除结点要比尾端相对地容易一 些，所以，我们将单链表的首端作为栈顶端，即将单 链表的头指针作为栈顶指针。 栈的链式存储 top 队列的链式存储结构简称为链队列，它是限制仅在表头 删除和表尾插入的单链表。 frontrear 队列的链式存储 循环链表是表中最后一个结点的指针指向头结点，使链 表构成环状 特点：从表中任一结点出发均可找到表中其他结点，提 高查找效率 操作与单链表基本一致，它可以使空表和非空表的运算 统一 单链表p或p-link=NULL 循环链表p或p-link=H h h 空表 1.5.2 循环链表的基本运算 例题讲解 线性表的顺序存储结构和线性表的链式存储结构分别 是 A) 顺序存取的存储结构、顺序存取的存储结构 B) 随机存取的存储结构、顺序存取的存储结构 C) 随机存取的存储结构、随机存取的存储结构 D) 任意存取的存储结构、任意存取的存储结构 链表不具有的特点是 A) 不必事先估计存储空间 B) 可随机访问任一 元素 C) 插入删除不需要移动元素 D) 所需空间与线性 表长度成正比 线性表若采用链式存储结构时，要求内存中可用存储 单元的地址 A) 必须是连续的 B) 部分地址必须是连续 的 C) 一定是不连续的 D) 连续不连续都可以 栈和队列的共同特点是 A)都是先进先出 B) 都是先进后出 C)只允许在端点处插入和删除元素 D) 没有共同 点 如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是 A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e1,e2D) 任意顺序 一些重要的程序语言(如C语言和Pascal语言) 允许过程的 递归调用。而实现递归调用中的存储分配通常用 A) 栈 B) 堆 C) 数组 D) 链表 当循环队列非空且队尾指针等于队头指针时，说明循环队列 已满，不能进行入队运算。这种情况称为 【2】 。 栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入 栈前，栈中元素可以出栈，则出栈序列可能是 A) ABCED B) DCBEA C) DBCEA D) CDABE 栈通常采用的两种存储结构是 A) 顺序存储结构和链表存储结构B) 散列方式和索引方式 C) 链表存储结构和数组 D) 线性存储结构和非线性存储结 构 栈和队列通常采用的存储结构是 【1】 。 下列数据结构中，按先进后出原则组织数据的是 A) 线性链表 B) 栈 C) 循环链表 D) 顺序 表 由两个栈共享一个存储空间的好处是 A) 减少存取时间，降低下溢发生的机率 B) 节省存储空间，降低上溢发生的机率 C) 减少存取时间，降低上溢发生的机率 D) 节省存储空间，降低下溢发生的机率 下列关于栈的叙述中正确的是 ）在栈中只能插入数据 B）在栈中只能删除数 据 C）栈是先进先出的线性表 D）栈是后进先出的线 性表 下列关于队列的叙述中正确的是 ）在队列中只能插入数据 B）在队列中只能删除 数据 C）队列是先进先出的线性表 D）队列是后进先出的 线性表 1.6 树与二叉树 树是一种简单的非线性结构，所有元素之间具有 明显的层次特性。 例如家谱、行政组织机构都可用树形象地表示 在树结构中，每一个结点只有一个前件，称为父结点 ，没有前件的结点只有一个，称为树的根结点，简称 树的根。每一个结点可以有多个后件，称为该结点的 子结点。没有后件的结点称为叶子结点。 一棵非空树是由若干棵子树构成的，而子树又可由若 干棵更小的子树构成。 本例是有13个结点的树，其中A是根，其余结点分成3个子 集： T1 、T2 、T3 。都是根A的子树，且本身也是一棵树。例 如： T1 其根为B，两棵子树为 T11 = F ， T12 = E, K, L ， T12 又是一棵子树，树根为F，K 和 L是E的两个互不 相交的子集。 结点：数据元素的内容及其指向其子树根的分支统称为结点 。 结点的度 （Degree): 结点的分支数，即结点拥有的子树数 。 终端结点（叶子leaf）:度为0的结点。 非终端结点:度不为0的结点。 结点的层次:树中根结点的层次为1，根结点子树的根为第2 层，以此类推。 树的度:树中所有结点度的最大值。 树的深度:树中所有结点层次的最大值。 有序树、无序树:如果树中每棵子树从左向右的排列拥有一 定的顺序，不得互换，则称为有序树，否则称为无序树。 术语 1.6.2 二叉树及其基本性质 二叉树是树形结构的一个重要类型 。特征： （1）每个结点最多有两棵子树； （2）子树有左右之分。 G H D E F B C A (a)(b) (c)(d)(e) (a)空树 (b)只有根结点的二叉树 (c) 右子树为空的二叉树 (d) 左子树为空的二叉树 (e) 左、右子树均非空的二叉树 二叉树的5种形态 二叉树具有下列5个重要的性质。 【性质1】 在二叉树的第i层上最多有2i-1个结点（i1）。 二叉树的第1层只有一个根结点，所以，i=1时， 2i-1=21-1=20=1成立。 假设对所有的j，1j 1其双亲结点的编号为 i/2。 （2）如果2in，则结点i没有左孩子（结点i为叶子结点）；否则 其左孩子结点的编号为2i。 （3）如果2i+1n，则结点i没有右孩子；否则其右孩子结点的编 号为2i+1。 2i +2 2i 2i+1 2i+2 2i+3 i+1 2i 2i+1 i i i+1 1.6.3 二叉树的存储结构 二叉树通常使用链式存储结构。 常见的二叉树结点结构如下所示： G H D E F B C A G H D E F B C A BT 1.6.4 二叉树的遍历 二叉树是一种非线性的数据结构，在对它进行操作时 ，总是需要逐一对每个数据元素实施操作，这样就存 在一个操作顺序问题，由此提出了二叉树的遍历操作 。所谓遍历二叉树就是按某种顺序访问二叉树中的每 个结点一次且仅一次的过程。这里的访问可以是输出 、比较、更新、查看元素内容等等各种操作。 二叉树的遍历方式为：按根、左子树和右子树三个部 分进行访问； 遍历二叉树的顺序存在下面三种顺序DLR、LDR和LRD， 根据根访问的位置不同分别被称为先序遍历、中序遍 历和后序遍历。下面我们将分别进行讨论。 （1）先序遍历 v若二叉树为空，则结束遍历操作；否则 v访问根结点； v先序遍历左子树； v先序遍历右子树。 （2）中序遍历 v若二叉树为空，则结束遍历操作；否则 v中序遍历左子树； v访问根结点； v中序遍历右子树。 （3）后序遍历 v若二叉树为空，则结束遍历操作；否则 v后序遍历左子树； v后序遍历右子树； v访问根结点。 G H B C A D E F 先序序列：ABDGCEFH 中序序列：DGBAECHF 后序序列：GDBEHFCA 下面是一棵二叉树及其经过三种遍历得到的相应序列。 例题讲解 具有3个结点的二叉树有 A) 2种形态 B) 4种形态 C) 7种形态 D) 5 种形态 设有下列二叉树： 对此二叉树前序遍历的结果为 A) ZBTTCPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT 设一棵二叉树中有3个叶子结点，有8个度为1的结点，则 该二叉树中总的结点数为 A) 12 B) 13 C) 14D) 15 设有下列二叉树： 对此二叉树的中序遍历的结果为 A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA 已知二叉树后序遍历序列是dabec，中序遍历序列是debac ，它的前序遍历序列是 cedba A) acbed B) decab C) deabc D) cedb