- 1、本文档共46页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
数据结构与算法ppt课件
队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。Rear指针指向队尾,front指针指向队头。 队列是“先进先出”(FIFO)或“后进后出”(LILO)的线性表。 队列运算包括 (1)入队运算:从队尾插入一个元素; (2)退队运算:从队头删除一个元素。 循环队列:在循环队列中,用队尾指针r指向队尾,用排头指针f指向队头的前一个位置 *循环对队中的元素的个数=rear-front(rf) =rear-front+容量(rf) m=50 r=20 f=35 线性表的链式存储结构简称线性链表 线性表的链式存储结构是指用一组任意的存储单元(可以连续,也可以不连续)存储线性表中的数据元素。因此,链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示数据元素间的逻辑关系,对于每个数据元素不仅要表示它的具体内容,还要附加一个表示它的直接后继元素存储位置的信息。这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构: 例如 :线性表 (a, b,c,d) 术语 表示每个数据元素的两部分信息组合在一起被称为结点; 其中表示数据元素内容的部分被称为数据域(data); 表示直接后继元素存储地址的部分被称为指针或指针域(next)。 其中,head是头指针,它指向单链表中的第一个结点,这是单链表操作的入口点。由于最后一个结点没有直接后继结点,所以,它的指针域放入一个特殊的值NULL。NULL值在图示中常用(^)符号表示。 带头结点的单链表 为了简化对链表的操作,人们经常在链表的第一个结点之前附加一个结点,并称为头结点。这样可以免去对链表第一个结点的特殊处理。如下图所示: 结点: 数据元素的内容及其指向其子树根的分支统称为结点。 结点的度 (Degree): 结点的分支数,即结点拥有的子树数。 终端结点(叶子leaf): 度为0的结点。 非终端结点: 度不为0的结点。 结点的层次: 树中根结点的层次为1,根结点子树的根为第2 层,以此类推。 树的度: 树中所有结点度的最大值。 树的深度: 树中所有结点层次的最大值。 有序树、无序树: 如果树中每棵子树从左向右的排列拥有一定的顺序,不得互换,则称为有序树,否则称为无序树。 1.6.2 二叉树及其基本性质 1、什么是二叉树 二叉树具有以下两个特点: (1)非空二叉树只有一个根结点; (2)每一个根结点最多只有两棵子树,且分别为该结点的左子树和右子树。(子树有左右之分,左右树不能互换) 二叉树的五种基本形态 空二叉树 仅有 根结点 右子树为空 左子树为空 左右子树均非空 两棵不同的二叉树 2、二叉树的基本性质 (1)在二叉树的K层上,最多有2k-1(k=1)个结点; (2)深度为m的二叉树最多有2m-1个结点; (3)在任意一棵二叉树中,度为0的结点(即叶子结点)总是比度为2的结点数多一个; (4)具有n个结点的二叉树,其深度至少为[log2n]+1,其中[log2n]表示取不大于log2n的最大整数。 [2007.9.8]题:一棵二叉树中共有70个叶子结点和80个度为1的结点,则二叉树中总结点数为: A.219 B.221 C.229 D.231 3、满二叉树和完全二叉树 (1)满二叉树 除最后一层外,每一层上的所有结点都有两个子结点。 即在第K层上有2k-1个结点。 深度为m的满二叉树有2m-1个结点 4 2 3 1 6 7 8 9 10 11 12 13 14 15 5 特点:每一层上都含有最大结点数。 (2)完全二叉树 除最后一层外,每一层上的结点数都达到最大值;在最后一层上只缺少右边的若干结点。 4 2 3 1 6 7 8 9 10 11 12 5 非完全二叉树 4 2 3 1 6 7 8 9 10 11 12 5 完全二叉树 特点:除最后一层外,每一层都取最大结点数, 最后一层结点都集中在该层最左边的若干位置。 8 9 10 11 12 4 5 6 7 2 3 1 7 8 9 4 5
文档评论(0)