概要集合与数据结构动态表示队列与堆栈树与图-天津大学计算机学院.PPT

概要集合与数据结构动态表示队列与堆栈树与图-天津大学计算机学院.PPT

  1. 1、本文档共31页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
概要集合与数据结构动态表示队列与堆栈树与图-天津大学计算机学院

第12章 集合 概要 集合 集合是一个对象,用于存储其他对象 集合通常提供增加、删除以及其他一些管理所包含元素的服务 集合中的元素有时是有序的,有时是无序的 有些集合是同构的,即这些集合中存储的对象类型相同;有些集合是异构的。 抽象 有许多不同的方法来实现集合 数据结构应该是抽象的 即, 应该隐藏不必要的细节 我们需要分离结构的界面(接口)与底层的实现 这有助于管理复杂并且可以在不必修改接口的情况下改变实现 抽象数据类型 抽象数据类型 (ADT)是一个有组织的信息集合与管理这些信息的一系列操作。 这些操作定义了抽象数据类型的接口 从某种意义上说,抽象数据类型的实现并不重要,只要它完成了接口 由于内部细节的采用封装机制,所以对象是建立抽象数据类型的完美机制 概要 动态结构 静态数据结构具有固定的长度 这与静态修饰符的含义有所不同 数组是静态的;当你定义了数组包含的元素的个数后,数组大小不允许改变 动态数据结构在运行期间可以更具需要增加和减少 通过链表来实现动态数据结构 对象引用 回顾一下,对象引用是一个存储对象地址的变量 引用也被称为指针 下面是一个引用的图形化描述: 对象引用 对象引用常用于创建对象间的链接 假设一个Student类包含指向另一个Student对象的引用: 对象引用 引用可以创建很多链式结构,例如 链表: Magazine 集合 我们来看一个Magazine 对象集合,由MagazineList 类管理,MagazineList类包含一个名为MagazineNode的私有的内部类 由于MagazineNode类对于MagazineList而言是私有的,所以MagazineList 的方法可以直接访问MagazineNode的数据而不违反封装 参见 MagazineRack.java (第418页) 参见MagazineList.java (第419页) 参见Magazine.java (第420页) 其他动态列表 某些情况,使用双向链表会更加方便 其他动态列表 有时,在链表中增加一个头节点会使处理过程更加方便 头节点包含指向链表第一个节点和最后一个的引用以及链表中节点的数目 概要 典型数据结构 现在我们来了解其他一些典型的数据结构 典型的线性数据结构包括队列和栈 典型的非线性数据结构包括树和图 队列 队列与链表类似,但是只能在队尾增加元素并且只能从队首删除元素 称作FIFO数据结构:先进,先出(First-In, First-Out) 类似:银行柜台窗口前排队 队列 通常队列可以有如下操作: 入队:在队尾增加一个元素 出对:从队首移出一个元素 清空:如果队列为空,返回true 可以使用单链表实现队列;如果引用从前指向后,那么效率非常高 队列也可以使用数组实现 堆栈 堆栈抽象数据类型也是线性的,这与队列或者链表类似。 但是只能在堆栈顶部删除或者增加元素 因此称作LIFO :后进,先出(Last-In, First-Out) 类似:橱柜中的一堆盘子,将要支付的一堆帐单,仓库中的一堆干草捆 堆栈 堆栈数据结构: 堆栈 堆栈的一些操作: 压入 – 将一个元素压入栈顶 弹出 – 从栈顶移出一个元素 读栈顶元素 – 读取栈顶元素,但书并不从栈顶移出 清空 – 如果堆栈为空,返回 true 堆栈可以使用单链表实现;引用指针从头指向尾或者从后指向前并不重要 堆栈也可以使用数组实现,但是新元素应该移入数组下一个可用位置而不是数组尾部 堆栈 java.util 包中包含了一个实现堆栈数据结构的Stack类 类似于ArrayList 的操作, Stack的操作也是对象引用 参考 Decode.java (第424页) 概要 树 树是非线性数据结构,由根节点和其他形成层次结构多级附加节点构成 没有子节点称作叶子节点 除根节点和叶子节点外,其他节点称作内部节点 通常一棵树中,每个节点都有很多子节点 二叉树 二叉树中,每一个节点不能有超过两个的子节点 二叉树可以被递归定义。即使它是空二叉树(基本事件)或者由一个根节点和两个二叉树子树构成 树可以使用动态链表来实现,也可以使用数组实现 对于二叉树而言,只需要存储两个链接,分别指向左节点和右节点 图 图是一个非线性结构 与树或者二叉树不同,图没有根 图中的任意一个节点通过边可以与其他节点相连 类似:地图上的告诉公路系统连接着城市 图 在一个有向图或者图表上,每个边都有一个特定的方向 带有方向的边有时称为弧 类似:机场间的航线 图 图或表都可以通过动态链表或者数组实现 通常,应该选择方便操作并且使实现更加方便的方式 概要 集合类 Java标准类库包含一些类来表示集合,通常我们可以参考Java 集合API 大多数类名表明了集合类型以及基本实现方法,例如 ArrayList类与Lin

文档评论(0)

2105194781 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档