第9章计算机学科基础.pptVIP

Chapter 9 Abstract Data Types and Algorithms 抽象数据类型和算法 Chapter Goals本章目标 Define an abstract data type and discuss its role in algorithm development 定义抽象数据类型并讨论它在算法开发中的角色 Distinguish between a data type and a data structure 区别数据类型和数据结构 Distinguish between an array-based implementation and a linked implementation 区别数组的实现和链式实现 Chapter Goals Distinguish between an array and a list 区别数组和列表 Distinguish between an unsorted list and a sorted list 区别无序列表和有序列表 Distinguish between a selection sort and a bubble sort 区别选择排序和冒泡排序 Describe the Quicksort algorithm 描述快速排序算法 Chapter Goals Apply the selection sort, the bubble sort, and the Quicksort to a list of items by hand 对列表手动应用选择排序法、冒泡排序法和快速排序法 Apply the binary search algorithm 应用二分检索法 Distinguish between the behavior of a stack and a queue 区别堆栈和队列的行为 Abstract Data Types抽象数据类型 Abstract data type A data type whose properties (data and operations) are specified independently of any particular implementation 属性（数据和操作）明确地与实现分离的数据类型。 The goal in design is to reduce complexity through abstraction Abstract Data Types抽象数据类型 In computing, we view data from three perspectives Application level 应用层 View of the data within a particular problem Logical level 逻辑层 An abstract view of the data values (the domain) and the set of operations to manipulate them Implementation level 实现层 A specific representation of the structure to hold the data items and the coding of the operations in a programming language Abstract Data Types抽象数据类型 Data structures 数据结构 The implementation of a composite data fields in an abstract data type 一种抽象数据类型中的复合数据域的实现 Containers 容器 Objects whole role is to hold and anipulate other objects 存放和操作其他对象的对象 Array-Based Implementations基于数组的实现 Recall that an array is a named collection of homogeneous items 数组是同构项目的有名集合。 An item’s place within the collection is called an index 通过每个项目在集合中的位置可以单独访问它。 If there is no ordering on the items in the container, we call the container unsorted 如果容器中的项目是无序的，就称这个容器是无序