L11-L14算法分析与数据结构.ppt
《L11-L14算法分析与数据结构.ppt》由会员分享,可在线阅读,更多相关《L11-L14算法分析与数据结构.ppt(41页珍藏版)》请在三一文库上搜索。
1、网络游戏算法设计,第2章 算法分析与数据结构,第2章 算法分析与数据结构,队列 树 二叉树 哈夫曼树,掌握队列 了解树 掌握二叉树 了解哈夫曼树,第2章 算法分析与数据结构,队列 二叉树,队列 二叉树 哈夫曼树,第2章 算法分析与数据结构,2.4 线性表,2.4.4 队列, 队列的定义,队列简称队,是一种只允许在一端进行插入,而在另一端进行删除的线性表,它是一种操作受限的线性表。,在表中只允许进行插入的一端称为队尾,只允许进行删除的一端称为队头。,队列的插入操作通常称为入队列或进队列,而队列的删除操作则称为出队列或退队列。当队列中无数据元素时,称为空队列。,第2章 算法分析与数据结构,2.4
2、线性表,通常用指针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不空,则返回队头元素;否则抛出异常。,队列是一种特殊的线性表,因此队列可采用顺序存储结构存
3、储,也可以使用链式存储结构存储。,第2章 算法分析与数据结构,2.4 线性表,链队列的表示,用链表表示的队列简称为链队列,在一个链队列中需设定两个指针(头指针和尾指针)分别指向队列的头和尾。,给链队列添加一个头节点,并设定头指针指向头节点。,空队列的判定条件是将头指针和尾指针都指向头节点。,第2章 算法分析与数据结构,2.4 线性表,struct Node int data; Node *link; ; class Queue Node *front; / 指向第一个节点 Node *rear; /指向最后一个节点 public: Queue() front = rear = 0; / 构造函
4、数 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 树,
5、树形结构是一类重要的非线性结构。树形结构是节点之间有分支,并具有层次关系的结构。, 树的定义,其中“树根”是祖父,树中出现“分支”的节点是父,该家族的其余成员均是“树叶”,而“树枝” 则描述了家族成员之间的关系。,第2章 算法分析与数据结构,2.5 其他常用数据结构,树(Tree)是n(n=0)个节点的有限集。在一棵非空树中,有且仅有一个特定的称为根的节点,当n1时其余节点可分为m(m0)个互不相交的有限集T1,T2Tm,其中,每一个集合本身又是一棵树,并且称为根的子树(subtree)。,树的递归定义刻画了树的固有特性:一棵非空树是由若干棵子树构成的,而子树又可由若干棵更小的子树构成。,树是
6、一种数据结构,可以表示为: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) 求孩子节
7、点函数。求树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) 遍历操作。按某个次序依此访问树
8、中各个节点,并使每个节点只被访问一次。 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 其他常用数据结构,嵌套集合表示法,嵌套集合表示法是用集合的包含关系来描述树结构,凹入表表示法,每棵树的根对应着
9、一个条形,子树的根对应着较短的条形,且树根在上,子树的根在下。长度相同的条形是兄弟节点。,第2章 算法分析与数据结构,2.5 其他常用数据结构,广义表表示法,每棵子树构成一个表,每棵树的根的名字作为表的名字放在表的左边,括号内是子树。,(A(B(E,F(I,J),C,D(G,H), 树形结构的基本术语,1)节点的度 树中的一个节点拥有的子树称为该节点的度。一棵树的度是指该树中节点的最大度数,度为零的节点称为叶子或终端节点,度不为零的节点称为分支节点或非终端节点。除根节点之外的分支节点统称为内部节点。根节点又称为开始节点。,第2章 算法分析与数据结构,2.5 其他常用数据结构,2)孩子和双亲。
10、树中某个节点的子树之根称为该节点的孩子或儿子,相应地,该节点称为孩子的双亲或父亲。同一个双亲的孩子称为兄弟。,3)祖先和子孙。 若树中存在一个节点序列k1,k2,ki,使得ki是ki+1的双亲(1ij),则称该节点序列是从k1到kj的一条路径(Path)或道路。则称k1是kj的祖先,kj是k1的子孙。,4)节点的层数和树的高度。 节点的层数从根算起:根的层数为1,也有很多书中将树根的层数定义为0。其余节点的层数等于其双亲节点的层数加1。双亲在同一层的节点互为堂兄弟。树中节点的最大层数称为树的高度或深度。,第2章 算法分析与数据结构,2.5 其他常用数据结构,5)有序树和无序树。 若将树中每个节
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- L11 L14 算法 分析 数据结构
链接地址:https://www.31doc.com/p-2201985.html