新计算机软件技术基础 教学课件 978 7 302 22362 7 第4章 算法与数据结构.ppt

4.7.5 队列 排队是一种常见的社会现象。去银行办理业务、超市的收银台、高速路口的收费站、在大学里的餐厅就餐、打印机发出的打印请求等，都会遇到这种先到先接收服务的排队现象。 在计算机领域，只要符合先进先出(first in first out，FIFO)的原则，就可以采用队列结构来处理。 队列(queue)是一种具有先进先出特征的线性数据结构，元素的增加只能在一端进行，元素的删除只能在另一端进行。能够增加元素的队列一端称为队尾，可以删除元素的队列一端则称为队首。 队列的结构示意图如图4-22所示。 队列的基本操作 队列的基本操作包括入队和出队。 入队表示在队列中增加元素，出队表示从队列中删除元素。 除此之外，基本操作还包括判断队列是否为空、返回队列的第一个元素、判断队列是否已满等。 4.8 树 4.8 树 在计算机科学领域，树(tree)是一种被广泛使用的数据结构，它由多个互相链接的节点形成的层次结构。 树结构类似于自然界中的树，但是是倒立的。 树有多种类型，人们最关心的是二叉树。 下面分别介绍树和二叉树的基本特点。 4.8.1 树的特点 树结构中有许多节点。每个节点既可以是一个值，也可以是包含了一组值，甚至可以是另外一个独立的数据结构。 在树结构中，根(root)是起始节点。 每个节点有零个或一个或多个子节点(child node)。 有子节点的节点称为子节点的父节点(parent node)。 一般地，在通常绘制的树结构图中，子节点总是位于父节点之下。 一个子节点最多只能有一个父节点。 没有子节点的节点就好象大自然中的树叶一样，被称为叶子节点(leaf node)。 树的主要运算 创建树； 列出树的所有数据元素； 列出树的部分数据元素； 在树中有哪些信誉好的足球投注网站指定的数据元素； 在树的指定位置增加数据元素； 在树中找到指定节点的父节点； 在树中找到指定节点的子节点； 删除指定的某个数据元素； 删除指定的子树； 增加一个数据元素； 增加一个子树； 计算树的高度。 4.8.2 二叉树的特点 虽然普通的树有许多应用，但是人们更关心的是二叉树(binary tree)。 这是因为大多数普通树都具有等价的二叉树表示，二叉树的结构和插入、删除、有哪些信誉好的足球投注网站等处理算法更容易用于程序设计语言实现。 简单地说，二叉树是指父节点最多有两个被称为左、右子节点的树。 二叉树的递归定义 下面给出二叉树的递归定义。二叉树T或者为空或者符合下面的描述： (1) T有一个特殊的节点，称为根节点； (2) T有两个节点集合，LT和RT，分别称为T的左子树和右子树； (3) LT和RT都是二叉树。 二叉树的递归 二叉树的运算 判断二叉树是否为空； 有哪些信誉好的足球投注网站二叉树中的某一个数据元素； 在二叉树中插入一个数据元素； 从二叉树中删除一个数据元素； 计算二叉树的高度； 计算二叉树的节点数量； 计算二叉树的叶节点数量； 遍历二叉树； 复制二叉树。 遍历二叉树 数据元素的插入、删除、有哪些信誉好的足球投注网站等操作均需要对二叉树进行遍历(traversal)。 遍历二叉树是指访问二叉树中的每一个节点。可以使用链表结构来存储二叉树。 有3种遍历二叉树的方法：中序遍历、前序遍历和后序遍历。 示例 4.9 图 4.9 图 图也是一种常见的数据结构，在许多领域例如电路、交通、物流、项目计划、社会科学等都有广泛的应用。 下面，主要介绍有关图的定义和特点、图的表示方法、图的主要操作等内容。 4.9.1 图的定义和特点 图(graph)是由一个顶点集V和一个边集E组成的数据结构，其中E是顶点连接对。 如果用G表示图，则G=(V, E)。其中，V={v1, v2, …, vm}，E={e1, e2, …, en}，e=(vi, vj)。如图4-26所示的示例都是图。 4.9.2 图的表示方法 如果希望编写程序对图进行处理和操作，则必须将图存储在计算机的内存中。在计算机科学领域，有多种存储图数据的方式。最常用的方法是邻接矩阵与邻接表。 首先介绍邻接矩阵方法。设G是一个有n(n0)个顶点的图，V(G)={v1, v2, …, vn}，则邻接矩阵AG是一个n阶二维矩阵。在该矩阵中，如果vi至vj有一条边，则(i, j)项的值为1，否则为0，即： 邻接表方法 设G是一个有n(n0)个顶点的图，V(G)={v1, v2, …, vn}。在邻接表中，每个顶点v都对应着一个链表，该链表的每个节点都包含一个顶点u，且(v, u)∈E(G)。 因为图中有n个顶点，所以可以利用一个长度为n的数组A，A(i)指向第i个顶点对应的链表的第一个节点，链表由顶点vi的全部邻接顶点组成。 图的基本操作 创建图，采用某种方法将图存储在计算机中； 判断图是否为空； 找到某个顶点； 找到某个顶点的全部邻接顶点； 找到某个顶点的一个邻接