计算机科学概论原书第5版制作 中英文PPT教师手册习题等65739_PPTx_Chapter08.ppt 52页

第八章抽象数据类型和子程序 2章节目标区分基于数组的可视化和链接的可视化区分数组和列表区分未排序列表和排序列表区分栈和队列的行为区分二叉树和二叉搜索树 3章节目标绘制通过插入一系列项目构建的二叉搜索树理解树和图之间的区别解释子程序和参数的概念，并区分值和引用参数 4抽象数据类型抽象数据类型一种数据类型，其属性（数据和操作）独立于任何特定实现而指定还记得管理复杂性最强大的工具是什么吗？ 5三种数据视图应用程序（用户）级别查看特定问题内的数据视图根据属性和行为查看数据对象 6三种数据视图逻辑（抽象）级别数据的抽象视图和操作它们的操作集视图将数据对象视为具有相似属性和行为的对象组 7三种数据视图实现级别以编程语言保存数据项和操作编码的结构的一种特定表示视图将展现以特定数据字段表示的属性和以代码实现的方法表示的行为 8三种数据视图从三个视图描述文字处理器 9三种数据视图复合数据类型一种数据类型，其中为数据值集合指定了名称数据结构在抽象数据类型中实现复合数据字段容器对象的整个角色是保存和操作其他对象 10逻辑实现容器的两种逻辑实现：基于数组的实现容器中的对象保存在一个数组中基于链接的实现容器中的对象不是物理上保持在一起，但是每个项目都告诉您去哪里获取结构中的下一个对象你有没有玩过寻宝游戏，每个线索都会告诉你去哪里获取下一个线索？ 11栈栈一个抽象数据类型，只能在一端进行访问LIFO,后进先出（LastInFirstOut）插入被称为Push，删除被称为Pop说出三个属于栈的日常结构 12栈WHILE(moredata)ReadvaluePush(myStack,value)WHILE(NOTIsEmpty(myStack))Pop(myStack,value)Writevalue你能手工模拟这个算法吗？ 13队列队列一种抽象数据类型，其中项目在一端输入并从另一端删除FIFO,先进先出（FirstInFirstOut）没有标准的队列术语Enqueue,Enque,Enq,Enter以及Insert用于插入操作Dequeue,Deque,Deq,Delete以及Remove用于删除操作说出三个属于队列的日常结构 队列WHILE(moredata)ReadvalueEnque(myQueue,value)WHILE(NOTIsEmpty(myQueue))Deque(myQueue,value)Writevalue你能手工模拟这个算法吗？ 15栈和队列堆栈和队列可视化为链式结构 16列表将列表视为项目的容器以下是可以应用于列表的逻辑操作添加项目把一个项目放进列表移除项目从列表中移除项目获得下一个项目获得（查看）下一个项目更多的项目有更多的项目吗？ 17基于数组的实现 18链式实现 19用于在列表中创建并打印项目的算法WHILE(moredata)ReadvalueInsert(myList,value)Reset(myList)Write"Itemsinthelistare"WHILE(moreItems(myList))GetNext(myList,nextItem)WritenextItem,""哪种实现？ 20逻辑层次使用该列表的算法不需要知道它是如何实现的我们使用栈，队列和列表编写算法，而不知道这些容器上的操作的内部工作 21树列表，栈和队列等结构本质上是线性的;只建立了一种关系更复杂的关系需要更复杂的结构你能说出三个更复杂的关系吗？ 22树二叉树一个链接容器，具有一个称为根的唯一起始节点，其中每个节点都能够有两个子节点，并且其中存在从根到每个其他节点的唯一路径（一系列节点）一图胜千言 23树根节点有两个子节点的根节点有右子树的节点叶节点有左子树的节点去往节点5的唯一路径是什么，9呢，7呢？ 24二叉搜索树二叉搜索树(BST)二叉树（形状属性），具有表征树节点中值的（语义）属性：任何节点中的值都大于其左子树中任何节点中的值，并且小于其右子树中任何节点中的值 25二叉搜索树图8.7一个二叉搜索树每个节点都是由其左右子节点组成的子树的根证明这棵树是二叉搜索树 26二叉搜索树 27二叉搜索树BooleanIsThere(current,item)If(currentisnull)returnfalseElseSetresulttoitem.compareTo(info(current))If(resultisequalto0)returntrueElseIf(result<0)IsThere(item,left(current))ElseIsThere(item,right(current)) 28二叉搜索树在搜索18,8,5,4,9和15时跟踪传递的节点当你找到空（null）时，你的位置有什么特别之处？ 29二叉搜索树IsThere(tree,item)IF(treeisnull)RETURNFALSEELSEIF(itemequalsinfo(tree))RETURNTRUEELSEIF(item