L11-L14 算法分析与数据结构.ppt

1、网络游戏的算法设计，第2章算法分析与数据结构，第2章算法分析与数据结构，队列树二叉树哈夫曼树，掌握队列理解树，第2章算法分析与数据结构，队列二叉树哈夫曼树，第2章算法分析与数据结构，2.4线性表，2.4.4队列，队列定义，队列简称，是在表中，最后只允许插入的称为队列尾部，最后只允许删除的称为队列头部。队列的插入操作通常称为进入或进入队列，而队列的删除操作称为退出或退出队列。当队列中没有数据元素时，它被称为空队列。第2章算法分析和数据结构，2.4线性表，通常用指针前面来指示团队头的位置，指针后面来指向团队尾。队列操作，第2章算法分析和数据结构，2.4线性表，队列的基本操作，包括以下四种：1)Is

2、Full()判断队列不为空：如果队列q不为空，则返回TRUE；否则，返回假。2)添加(常量节点*链接；类队列节点*前端；/指向第一个节点节点*后方；/指向队列：的最后一个节点()前=后=0；/构造函数队列()；/析构函数boolisempty()常量返回()？假：真)；bool IsFull()常量；int First()常量；/返回int Last()常量的第一个元素；/返回队列的最后一个元素，第2章算法分析和数据结构，2.4线性表，链式队列的主要算法，队列入口操作：游戏学院：3360队列，第2章算法分析和数据结构，2.4线性表，队列出口操作：游戏学院33603360队列，第2章算法分析和数

3、据结构，2.2树形结构是一种节点间有分支和层次关系的结构。树的定义，其中“根”是祖父，“枝”在树中出现的节点是父亲，其余的家庭成员是“叶”，而“枝”描述家庭成员之间的关系。第2章，算法分析和数据结构，2.5其他常用的数据结构，树是一个有限的n(n=0)个节点的集合。在非空树中，只有一个特定的节点叫做根，当n1时，剩余的节点可以被分成m(m0)个不相交的有限集合T1和T2Tm，其中每个集合本身就是一棵树，被称为根的子树。树的递归定义描述了树的固有特征：非空树由几个子树组成，子树可以由几个较小的子树组成。树是一种数据结构，可以表示为：树=(D，r)。其中d是具有相同特征的数据元素的集合。如果d只包

4、含一个数据元素，r是一个空集合；否则，r是d上二元关系的集合，第2章：算法分析和数据结构，2.5其他常用的数据结构，基本的树操作，10个基本的树操作包括：1)INITIATE(T)初始化操作，将T设置为空树。2)ROOT(T)ROOT(x)函数。寻找树t的根或节点x所在的树的根节点。如果t是一棵空树，或者x不在任何树上，则函数值为“空”。3)通过稀疏(t，x)计算母函数。在树t中查找节点x的父节点。如果节点x是树t的根节点或者节点x不在树t中，函数值为“空”。4)CHILD(T，x，I)找到子节点函数。在树T中寻找节点x的第一个子节点.如果节点x是树t的叶子，或者没有子节点，或者节点x不在树t

5、中，则函数值为“空”。第2章，算法分析和数据结构，2.5其他常见数据结构，5)查找正确的兄弟函数。在树t中的节点x的右侧找到兄弟。如果节点x是其父节点的最右边的子节点，或者节点x不在树t中，则函数值为“空”。6)CRT_TREE(x，f)树构建操作。生成一棵树，以X节点为根，以F节点为子树林。7)INS_CHILD(y，I，x)插入子树操作。8)DEL_CHILD(x，I)删除子树操作。删除节点x. 9的第I个子树。按照一定的顺序访问树中的每个节点，并使每个节点只被访问一次。10)清除(T)清除结构操作。将树t设置为空树。第二章算法分析和数据结构，2.5其他常用的数据结构、树表示、树表示和树表

6、示是树结构的主要表示方法。在树的树形图表示中，节点用圆圈表示，节点的名称写在圆圈旁边。图中的树由有限的一组节点组成，其中A是根节点，而T中的其他节点可以被分成三个不相交的子集：T1=B，E，F，I。嵌套集表示法是一种凹表表示法，它使用集合的包含关系来描述树的结构，其中每棵树的根对应于一个条， 子树的根对应于较短的条，根在顶部，子树的根在底部。 具有相同长度的条是兄弟节点。第2章，算法分析和数据结构，2.5其他常用的数据结构，广义表记法，每个子树构成一个表，每个树的根的名称放在表的左侧作为表的名称，子树在括号中。树结构的基本术语，1)节点的度树中的一个节点所拥有的子树称为节点的度。树的度是指树中

7、节点的最大度，零度的节点称为叶子或末端节点，非零度的节点称为分支节点或非末端节点。根节点以外的分支节点统称为内部节点。根节点也称为起始节点。第2章算法分析和数据结构，2.5其他常见数据结构，2)孩子和父母。树中某个节点的子树的根被称为该节点的子节点或子节点，因此，该节点被称为该子节点的父节点或父节点。父母相同的孩子被称为兄弟。3)祖先和后代。如果在树中有一个节点序列k1，k2，ki，因此ki是ki 1的父(1ij)，那么节点序列是从k1到kj的路径或道路。那么k1是kj的祖先，kj是k1的后代。4)节点层数和树高。节点的数量从根开始：根的数量是1，许多书将根的数量定义为0。其他节点的层数等于其

8、父节点的层数加1。父母是同级的表亲。树的最大节点数称为树的高度或深度。第2章算法分析和数据结构，2.5其他常见数据结构，5)有序树和无序树。如果树中每个节点的子树被认为是从左到右有序的(即它们不能互换)，那么树被称为有序树；否则，它被称为无序树。6)森林。森林是m(m0)棵不相交的树的集合。树木和森林有相似的概念。删除树根，得到一片森林；相反，如果您添加一个节点作为根，该林将变成一棵树。第2章，算法分析和数据结构，2.5其他常用的数据结构，以及树结构的逻辑特征，1)树中的任何节点都可以有零个或多个直接后继节点，但最多只能有一个直接前导节点。2)树中只有根节点没有趋势，它是起始节点；叶节点没有后

9、继节点，它们是终端节点。3)祖先和后代之间的关系是父子关系的扩展，父子关系定义了树中节点之间的垂直顺序。4)在有序树中，同一组兄弟节点可以从左到右分为年轻节点和年老节点。第二章算法分析和数据结构，2.5其他常用的数据结构，二叉树，二叉树的存储结构及其算法都比较简单，所以二叉树尤为重要。二叉树的五种基本形式，第2章算法分析和数据结构，2.5其他常用的数据结构，二叉树不同于无序树，在二叉树中，每个节点最多只能有两个子树，并且有左右两个分支。在有序树中，虽然节点的子节点之间有一个从左到右的顺序，但是如果节点只有一个子节点，就不需要区分它的从左到右的顺序。在二叉树中，即使一个孩子也有左点和右点。在第2

10、章，算法分析和数据结构，2.5其他常用的数据结构中，二叉树具有以下重要的性质：1)二叉树的I层上的最大节点数是2i-1(i1)。2)深度为k的二叉树最多有2k-1个节点(k1)。3)在任何二叉树中，如果终端节点的数量是n0，并且具有2度的节点的数量是n2，那么n0=N2 1。第二章算法分析和数据结构，2.5其他常用的数据结构，全二叉树和全二叉树，全二叉树深度为k和2k-1节点的二叉树称为全二叉树。完全二叉树和完全二叉树是二叉树的两种特殊情况。全二叉树的特点如下：1)每层节点数达到最大。2)全二叉树中没有1度的节点，每个分支节点有两个高度相同的子树，叶子在底层。第2章，算法分析和数据结构，2.5

11、其他常见数据结构，完整二叉树：如果一个二叉树最多只有最底层的两层，它的节点度可以小于2，并且最底层的节点集中在该层最左边的位置，那么这个二叉树称为完整二叉树。完全二叉树的特征：1)完全二叉树是完全二叉树，它不一定是完全二叉树。2)在完全二叉树的底层，从最右边连续删除几个节点得到的二叉树仍然是完全二叉树。3)在一个完整的二叉树中，如果一个节点没有左子节点，它必须没有右子节点，也就是说，该节点必须是一个叶节点。第2章：算法分析和数据结构，2.5其他常见数据结构，4)具有N个节点的全二叉树：0.1长(全二叉树)，第2章：算法分析和数据结构，2.5其他常见数据结构，顺序存储结构。该方法将二叉树的所有节

12、点以一定的线性顺序存储到一个连续的存储单元中。该序列中节点的相互位置也可以反映节点之间的逻辑关系。完全二叉树节点编号方法：在一个有n个节点的完全二叉树中，从树的根开始，从上层到下层，每层从左到右，所有节点都被编号，可以得到反映整个二叉树结构的线性序列。第2章算法分析和数据结构，2.5其他常用的数据结构，编号特征：完整二叉树中的所有层都充满了节点，除了底层。每一层的节点数正好是前一层的两倍。假设编号为I的节点为(1in)，有：1)如果i1，ki的父节点编号为I/2；如果i=1，ki是根节点，没有父节点。2)如果2in，ki的左子代数为2i；否则，ki没有留下孩子，也就是说，ki必须是一片叶子。因

13、此，完整二叉树中编号为/2的节点必须是叶节点。3)如果2i 1n，ki的右子代数为2i 1n否则ki就没有合适的孩子。4)如果I是奇数而不是1，则ki的左兄弟的数目是I-1；否则他就没有兄弟了。5)如果I为偶数且小于n，则ki的右兄弟数为I 1；否则基就没有合适的兄弟。第二章，算法分析和数据结构，2.5其他常用的数据结构，完整二叉树的顺序存储，完整二叉树中的所有节点按照编号顺序依次存储在一个向量bt0n中。Bt1n用于存储节点，bt0不用于或仅用于存储节点数量。第二章，算法分析和数据结构，2.5其他常用的数据结构，一般二叉树的顺序存储，1)存储方法，在一般二叉树中加入一些“虚拟节点”成为“完全

14、二叉树”。节点根据数字存储在向量的相应分量中，其中“虚拟节点”由“”表示。第2章：算法分析和数据结构，2.5其他常用的数据结构，2)优缺点。对于完整的二叉树，顺序存储结构简单，节省存储空间。当一般二叉树采用顺序存储结构时，虽然简单，但容易造成存储空间的浪费。在最坏的情况下，深度为k且只有k个节点的右单分支树需要2k-1个节点的存储空间。在顺序存储的二叉树中插入和删除节点时，需要移动大量的节点。第二章，算法分析与数据结构，2.5其他常用的数据结构，定义了二叉树的链式存储结构类型，一个树节点包含一个数据字段和两个指针字段，指针字段称为“左指针”和“右指针”，分别指向节点的左、右子树。二叉树结构由节

15、点生成。二叉树的结构：第2章算法分析和数据结构，2.5其他常用的数据结构，哈夫曼树，也称为最优二叉树，是一种加权路径长度最短的树，应用广泛。树中两个节点之间的路径由从一个节点到另一个节点的分支组成。树的路径长度是从根节点到每个节点的路径长度的总和。假设一棵二叉树有n个叶节点，每个叶节点的权重为1，2，n，从根节点到每个叶节点的路径长度是L2的L1.那么树的加权路径长度就是每片叶子的路径长度和叶子重量的总和。俗称WPL k. k .在第2章，算法分析和数据结构，以及2.5其他常用的数据结构中，加权叶节点被绘制为正方形，而其他非叶节点仍然是圆形的。这三个二叉树有相同数量的叶节点和相同的权重，但是它

16、们的wpl加权路径长度不同。最右边的树是哈曼树，最佳树。第2章算法分析和数据结构，2.5其他常见数据结构，霍夫曼树构造：对于一组已知的叶权重1，2.首先，将N个叶节点视为N棵树(只有一个节点的二叉树)，并将N棵树视为一个森林；2)将两个最小重量和第二个最小重量的树组合成一棵树，即树的根节点。此时，森林中有n-1棵树。3)重复步骤2)，直到森林中只有一棵树。这棵树就是霍夫曼树。第2章算法分析和数据结构，2.5其他常见数据结构，摘要，第2章算法分析和数据结构，本节介绍基本数据结构中的队列和树。队列是一个线性表，只能在一端插入，在另一端删除。这是一个有限操作的线性表。树形结构是一种重要的非线性结构。树形结构是一种节点之间有分支和层次关系的结构。小测验，第2章算法分析和数据结构，网络游戏客户端必须处理来自服务器的消息，但通常不能在收到消息后立即处理它们，那么应该使用什么数据结构来临