《计算机科学导论》配套教学课件.ppt

术语 从任意给定节点可以直接到达的节点称为其子节点；出发节点为对应子节点的双亲 具有相同双亲的节点称为兄弟节点 从某个节点出发，可以到达的节点为其子孙；出发节点为对应子孙的祖先。 树中每个节点都有可能包含子树，某个节点的子树是它的一个子节点及其子孙构成的整体。 节点包含的子树数量为其出弧的数量（子节点的数量） -*- 术语 -*- 树的应用 树在计算机科学中的应用非常广泛，如索引文件，其细节超出本门课程的范畴。 下面学习特殊的树——二叉树 -*- 本章内容安排 背景 栈 队列 广义线性表 树 二叉树 二叉有哪些信誉好的足球投注网站树 图 -*- 二叉树 二叉树是一种树，树中没有一个节点包含两个以上子树。任何一个节点只能有0、1或2棵子树。节点的子树分别被称为左子树和右子树。 -*- 二叉树的递归定义 定义：二叉树是一棵空树，或由1个根节点和2棵子树构成，而每棵子树也是二叉树。 -*- 二叉树的操作 二叉树的操作 建树 插入 删除 检索 是否为空 遍历 本课程只讨论二叉树的遍历 -*- 二叉树的遍历 二叉树的遍历是按照预定的顺序处理每一个节点且仅处理一次。常用的遍历次序有两种： 深度优先遍历：又可分为6种方式，其中的三种标准方式是前序遍历、中序遍历和后序遍历 广度优先遍历 -*- 2、入列 入列操作将数据插入队尾，新元素成为队尾。 enqueue(queueName,dataItem) -*- 3、出列 出列操作删除队列前端的数据项。 dequeue(quenueName,dataItem) -*- 4、是否为空empty 检验队列是否为空。如果队列中没有数据，队列为空，返回真；否则返回假。 empty(quenueName) -*- 队列的抽象数据类型 -*- 示例：队列操作及状态 -*- 队列的应用 队列的应用非常广泛，在操作系统、网络等领域中都有应用。 队列应用于在线电子商务应用，如处理用户需求、任务和指令。 在计算机系统中，使用队列完成对作业或系统设备的排队处理。 -*- 队列用于数据分类 如要对一组数进行分组，如分成小于1000和大于1000，可以先读取数据，然后创建2个队列，判断某个数并将其插入到合适的队列中，分类的同时保持了原始顺序 -*- 队列用于数据分类 -*- 队列用于数据分类 -*- 队列用于速度匹配 队列可用于调节数据快速生成和数据缓慢消费之间的平衡 假设CPU和打印机相连，CPU速度非常快，造成CPU等待打印的缓慢输出，造成CPU的空闲和浪费 CPU生成队列能容纳的数据块，将数据保存到队列中，CPU转向执行其他任务，打印机从队列中缓慢去除数据并打印输出，称为“假脱机队列”。 -*- 队列的实现 队列可以用数组或链表实现。 数组实现 数组 辅助记录：包含3个域，1个域用于记录队列内的数据项数，2个域分别指示队首和队尾在数组中的位置 链表实现 链表 辅助记录：包含3个域，1个于用于记录数据项数，1个指向链表表头的指针和1个指向链表表尾的指针。入列时从表头插入元素，出列时从表尾删除元素（或反之）。 -*- 队列的实现 -*- 本章内容安排 背景 栈 队列 广义线性表 树 二叉树 二叉有哪些信誉好的足球投注网站树 图 -*- 广义线性表 栈和队列属于限制线性表。广义线性表是插入和删除等操作可以在表中任意地方进行的表。 广义线性表是具有如下特性的元素集合 元素具有相同的类型； 元素按顺序排列，存在第一个元素和最后一个元素； 除第一个元素外每个元素都有唯一的前驱；除最后一个元素外每个元素都有后继元素； 每个元素是一个带有关键字字段的记录； 元素按关键字值排序。 -*- 广义线性表的操作 可以为广义线性表定义许多操作。此处仅讨论6种常用的操作： 建表：list 插入：insert 删除：delete 检索：retrieve 遍历：traverse 是否为空：empty -*- 1、建表 创建一个空表。 list(listName) -*- 2、插入 多数情况下，要将数据插入在有序列表中间，保持按键值排序。此种情况下，需要使用有哪些信誉好的足球投注网站算法确定插入位置。 insert(listName,element) -*- 3、删除 执行删除操作，首先要定位到要删除的目标。删除线性表中关键字值与target相等的元素，删除的元素通过element返回。 修改元素通过删除，修改值并重新插入实现。 delete(listName,target,element) -*- 4、检索 检索是对单个元素的存取，在列表中定位数据然后得到数据的副本。 关键字匹配target的元素，被复制到element中并返回，原始表中的元素保持不变。 retrieve(listName,target,element) -*- 5、遍历 遍历是对线性表表中所有元素顺序逐一进行处理的操作。