L11L14算法分析与数据结构.ppt

网络游戏算法设计,第2章 算法分析与数据结构,第2章 算法分析与数据结构,队列树二叉树哈夫曼树,掌握队列了解树掌握二叉树了解哈夫曼树,第2章 算法分析与数据结构,队列二叉树,队列二叉树哈夫曼树,第2章 算法分析与数据结构,2.4 线性表,2.4.4 队列,队列的定义,队列简称队，是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限的线性表。,在表中只允许进行插入的一端称为队尾，只允许进行删除的一端称为队头。,队列的插入操作通常称为入队列或进队列，而队列的删除操作则称为出队列或退队列。当队列中无数据元素时，称为空队列。,第2章 算法分析与数据结构,2.4 线性表,通常用指针front指示队头的位置，用指针rear指向队尾。,队列的操作,第2章 算法分析与数据结构,2.4 线性表,队列的基本运算,队列的基本运算包括以下4种：1）IsFull()队列非空判断：若队列q不空，则返回TRUE；否则，返回FALSE。2）Add(const int&x)入队列：在队列q的尾部插入元素x，使元素x成为新的队尾。3）Delete(int&x)出队列：若队列q不空，则返回队头元素，并从队头删除该元素；否则，抛出异常。4）First()取队头元素：若队列q不空，则返回队头元素；否则抛出异常。,队列是一种特殊的线性表，因此队列可采用顺序存储结构存储，也可以使用链式存储结构存储。,第2章 算法分析与数据结构,2.4 线性表,链队列的表示,用链表表示的队列简称为链队列，在一个链队列中需设定两个指针（头指针和尾指针）分别指向队列的头和尾。,给链队列添加一个头节点，并设定头指针指向头节点。,空队列的判定条件是将头指针和尾指针都指向头节点。,第2章 算法分析与数据结构,2.4 线性表,struct Node int data;Node*link;class Queue Node*front;/指向第一个节点Node*rear;/指向最后一个节点public:Queue()front=rear=0;/构造函数Queue();/析构函数bool IsEmpty()const return(front)?false:true);bool IsFull()const;int First()const;/返回第一个元素int Last()const;/返回最后一个元素Queue,第2章 算法分析与数据结构,2.4 线性表,链队列的主要运算算法,入队列操作：,GameCollege:Queue,第2章 算法分析与数据结构,2.4 线性表,出队列操作为：,GameCollege:Queue,第2章 算法分析与数据结构,2.5 其他常用数据结构,2.5.1 树,树形结构是一类重要的非线性结构。树形结构是节点之间有分支，并具有层次关系的结构。,树的定义,其中“树根”是祖父，树中出现“分支”的节点是父，该家族的其余成员均是“树叶”，而“树枝”则描述了家族成员之间的关系。,第2章 算法分析与数据结构,2.5 其他常用数据结构,树（Tree）是n（n=0）个节点的有限集。在一棵非空树中，有且仅有一个特定的称为根的节点，当n1时其余节点可分为m（m0）个互不相交的有限集T1，T2Tm，其中，每一个集合本身又是一棵树，并且称为根的子树（subtree）。,树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。,树是一种数据结构，可以表示为：Tree=(D，R)。其中，D是具有相同特性的数据元素的集合。若D只含一个数据元素，则R为空集；否则R是D上一个二元关系的集,第2章 算法分析与数据结构,2.5 其他常用数据结构,树的基本操作,树的10种基本运算包括：1）INITIATE(T)初始化操作，置T为空树。2）ROOT(T)ROOT(x)求根函数。求树T的根或求节点x所在的树的根节点。若T是空树或x不在任何一棵树上，则函数值为“空”。3）RARENT(T，x)求双亲函数。求树T中节点x的双亲节点。若节点x是树T的根节点或节点x不在T中，则函数值为“空”。4）CHILD(T，x，i)求孩子节点函数。求树T中节点x的第i个孩子节点。若节点x是树T的叶子或无第i个孩子再或者节点x不在树T中，则函数值为“空”。,第2章 算法分析与数据结构,2.5 其他常用数据结构,5）RIGHT_SINLING(T，x)求右兄弟函数。求树T中节点x右边的兄弟。若节点x是其双亲的最右边的孩子节点或节点x不在树T中，则函数值为“空”。6）CRT_TREE(x，F)建树操作。生成一棵以x节点为根，以树F为子树森林的树。7）INS_CHILD(y，I，x)插入子树操作。8）DEL_CHILD(x，i)删除子树操作。删除节点x的第i棵子树。9）TRAVERSE(T)遍历操作。按某个次序依此访问树中各个节点，并使每个节点只被访问一次。10）CLEAR(T)清除结构操作。将树T置为空树。,第2章 算法分析与数据结构,2.5 其他常用数据结构,树的表示方法,树形图表示法,树形图表示是树结构的主要表示方法。树的树形图表示中：节点用圆圈表示，节点的名字写在圆圈旁边,图中的树由节点的有限集T=A，B，C，D，E，F，G，H，I，J所构成，其中A是根节点，T中其余节点可分成3个互不相交的子集：,T1=B，E，F，I，J，T2=C，T3=D，G，H,第2章 算法分析与数据结构,2.5 其他常用数据结构,嵌套集合表示法,嵌套集合表示法是用集合的包含关系来描述树结构,凹入表表示法,每棵树的根对应着一个条形，子树的根对应着较短的条形，且树根在上，子树的根在下。长度相同的条形是兄弟节点。,第2章 算法分析与数据结构,2.5 其他常用数据结构,广义表表示法,每棵子树构成一个表，每棵树的根的名字作为表的名字放在表的左边，括号内是子树。,（A（B（E，F（I，J），C，D（G，H）,树形结构的基本术语,1）节点的度树中的一个节点拥有的子树称为该节点的度。一棵树的度是指该树中节点的最大度数，度为零的节点称为叶子或终端节点，度不为零的节点称为分支节点或非终端节点。除根节点之外的分支节点统称为内部节点。根节点又称为开始节点。,第2章 算法分析与数据结构,2.5 其他常用数据结构,2）孩子和双亲。树中某个节点的子树之根称为该节点的孩子或儿子，相应地，该节点称为孩子的双亲或父亲。同一个双亲的孩子称为兄弟。,3）祖先和子孙。若树中存在一个节点序列k1，k2，ki，使得ki是ki+1的双亲(1ij)，则称该节点序列是从k1到kj的一条路径（Path）或道路。则称k1是kj的祖先，kj是k1的子孙。,4）节点的层数和树的高度。节点的层数从根算起：根的层数为1，也有很多书中将树根的层数定义为0。其余节点的层数等于其双亲节点的层数加1。双亲在同一层的节点互为堂兄弟。树中节点的最大层数称为树的高度或深度。,第2章 算法分析与数据结构,2.5 其他常用数据结构,5）有序树和无序树。若将树中每个节点的各子树看成是从左到右有次序的（即不能互换），则称该树为有序树；否则称为无序树。,6）森林。森林是m（m0）棵互不相交的树的集合。树和森林的概念相近。删去一棵树的根，就得到一个森林；反之，加上一个节点作树根，森林就变为一棵树。,第2章 算法分析与数据结构,2.5 其他常用数据结构,树形结构的逻辑特征,1）树中任意一节点都可以有零个或多个直接后继（即孩子）节点，但至多只能有一个直接前趋（即双亲）节点。2）树中只有根节点无前趋，它是开始节点；叶节点无后继，它们是终端节点。3）祖先与子孙的关系是对父子关系的延拓，它定义了树中节点之间的纵向次序。4）有序树中，同一组兄弟节点从左到右有长幼之分。,第2章 算法分析与数据结构,2.5 其他常用数据结构,二叉树,二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。,二叉树的5种基本形态,第2章 算法分析与数据结构,2.5 其他常用数据结构,二叉树与无序树不同,二叉树中，每个节点最多只能有两棵子树，并且有左右之分。,在有序树中，虽然一个节点的孩子之间是有左右次序的，但是若该节点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。,第2章 算法分析与数据结构,2.5 其他常用数据结构,二叉树具有以下重要性质：,1）二叉树第i层上的节点数目最多为 2i-1（i1）。2）深度为k的二叉树至多有 个2k-1节点（k1）。3）在任意一棵二叉树中，若终端节点的个数为 n0，度为2的节点数为n2，则n0=n2+1。,第2章 算法分析与数据结构,2.5 其他常用数据结构,满二叉树和完全二叉树,满二叉树一棵深度为k且有 2k-1个节点的二叉树称为满二叉树。,满二叉树和完全二叉树是二叉树的两种特殊情形。,满二叉树的特点：1）每一层上的节点数都达到最大值。2）满二叉树中不存在度数为1的节点，每个分支节点均有两棵高度相同的子树，且树叶都在最下一层上。,第2章 算法分析与数据结构,2.5 其他常用数据结构,完全二叉树：若一棵二叉树最多只有最下面的两层，其节点的度数可以小于2，并且最下一层上的节点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。,完全二叉树的特点：1）满二叉树是完全二叉树，完全二叉树不一定是满二叉树。2）在满二叉树的最下一层上，从最右边开始连续删去若干节点后得到的二叉树仍然是一棵完全二叉树。3）在完全二叉树中，若某个节点没有左孩子，则它一定没有右孩子，即该节点必是叶节点。,第2章 算法分析与数据结构,2.5 其他常用数据结构,4）具有n个节点的完全二叉树的满二叉树深度为：,1+lgn(满二叉树),第2章 算法分析与数据结构,2.5 其他常用数据结构,顺序存储结构,该方法是把二叉树的所有节点按照一定的线性次序存储到一片连续的存储单元中。节点在这个序列中的相互位置还能反映出节点之间的逻辑关系。,完全二叉树节点编号方法：在一棵n个节点的完全二叉树中，从树根起，自上层到下层，每层从左至右，给所有节点编号，能得到一个反映整个二叉树结构的线性序列。,第2章 算法分析与数据结构,2.5 其他常用数据结构,编号特点：完全二叉树中除最下面一层外，各层都充满了节点。每一层的节点个数恰好是上一层节点个数的2倍。,假设编号为i的节点是（1in），则有：1）若i1，则 ki的双亲编号为i/2；若i=1，则 ki是根节点，无双亲。2）若2in，则 ki的左孩子的编号是2i；否则，ki 无左孩子，即 ki必定是叶子。因此完全二叉树中编号in/2的节点必定是叶节点。3）若2i+1n，则 ki的右孩子的编号是2i+1；否则 ki无右孩子。4）若i为奇数且不为1，则 ki的左兄弟的编号是i-1；否则 ki无左兄弟。5）若i为偶数且小于n，则 ki的右兄弟的编号是i+1；否则ki 无右兄弟。,第2章 算法分析与数据结构,2.5 其他常用数据结构,完全二叉树的顺序存储,将完全二叉树中所有节点按编号顺序依次存储在一个向量bt0n中。其中：bt1n用来存储节点,bt0不使用或只用来存储节点数目。,第2章 算法分析与数据结构,2.5 其他常用数据结构,一般二叉树的顺序存储,1）存储方法,将一般二叉树添上一些“虚节点”，成为“完全二叉树”。将节点按编号存入向量对应分量，其中“虚节点”用“”表示,第2章 算法分析与数据结构,2.5 其他常用数据结构,2）优点和缺点,对完全二叉树而言，顺序存储结构既简单又节省存储空间。,一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。最坏的情况下，一个深度为k且只有k个节点的右单支树需要2k-1个节点的存储空间。,在对顺序存储的二叉树做插入和删除节点操作时，要大量移动节点。,第2章 算法分析与数据结构,2.5 其他常用数据结构,二叉树的链式存储结构类型定义,一个树节点包含一个数据域和两个指针域，指针域被称为“左指针”和“右指针”，它们分别指向节点的左右子树。,二叉树结构是由节点生成的。,二叉树的结构：,第2章 算法分析与数据结构,2.5 其他常用数据结构,哈夫曼树,哈夫曼树（Huffman）又称最优二叉树，是一类带权路径长度最短的树，有着广泛的应用。,树中两个节点之间的路径由一个节点到另一节点的分支构成。,树的路径长度是从根节点到每一个节点的路径长度之和。,设一棵二叉树有 n 个叶子节点，每个叶子节点拥有一个权值1，2，.n，从根节点到每个叶子节点的路径长度分别为 L1，L2.Ln，那么树的带权路径长度为每个叶子的路径长度与该叶子权值乘积之和。通常记作WPL k.k。,第2章 算法分析与数据结构,2.5 其他常用数据结构,图中把带权的叶子节点画成方形，其他非叶子节点仍为圆形。这三棵二叉树叶子节点数相同，它们的权值也相同，但是它们的wpl带权路径长各不相同。最右边的树就是哈曼树，最优树。,第2章 算法分析与数据结构,2.5 其他常用数据结构,哈夫曼树的构造：,对于已知的一组叶子的权值1，2.，n,1）首先把n个叶子节点看作n棵树（仅有一个节点的二叉树），把n棵树看作一个森林,2）在森林中把权值最小和次小的两棵树合并成一棵树，该树根节点的权值是两棵子树权值之和。这时森林中还有n-1棵树。,3）重复第2)步，直到森林中只有一棵树为止。此树就是哈夫曼树。,第2章 算法分析与数据结构,2.5 其他常用数据结构,小结,第2章 算法分析与数据结构,本节介绍了基本数据结构中的队列和树。队列是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限的线性表。树形结构是一类重要的非线性结构。树形结构是节点之间有分支，并具有层次关系的结构。,小测验,第2章 算法分析与数据结构,网游客户端要处理来自服务器的消息，但是经常无法在收到后立即处理，那么应该使用何种数据结构暂存这些消息？（）A.链表B.堆栈C.队列D.树,选择题（单选题）,判断试题,二叉树是一种特殊的树。（）树和二叉树的子节点指针是没有顺序的。（）,小测验答案,第2章 算法分析与数据结构,网游客户端要处理来自服务器的消息，但是经常无法在收到后立即处理，那么应该使用何种数据结构暂存这些消息？（C）A.链表B.堆栈C.队列D.树,选择题（单选题）,判断试题,二叉树是一种特殊的树。（对）树和二叉树的子节点指针是没有顺序的。（错）,课后作业,第2章 算法分析与数据结构,【作业1】实现一个队列算法，完成队列的append、getHead等函数。,【作业2】对于已知的一组叶子的权值，得到一个哈夫曼树。,