[工学]9 抽象数据类型和算法.ppt

* Fundamentals of Computer Science Hai MoPage 1 Chapter 9 Abstract Data Types and Algorithms n9.1 Abstract Data Types n9.2 Implementation n9.3 Lists n9.4 Sorting n9.5 Binary Search n9.6 Stacks and Queues n9.7 Trees * Fundamentals of Computer Science Hai MoPage 2 Chapter Goals nDefine an abstract data type and discuss its role in algorithm development nDistinguish between a data type and a data structure nDistinguish between an array-based implementation and a linked implementation nDistinguish between an array and a list * Fundamentals of Computer Science Hai MoPage 3 Chapter Goals nDistinguish between an unsorted list and a sorted list nDistinguish between a selection sort and a bubble sort nDescribe the Quicksort algorithm nApply the selection sort, the bubble sort, and the Quicksort to a list of items by hand nApply the binary search algorithm * Fundamentals of Computer Science Hai MoPage 4 Chapter Goals nDistinguish between the behavior of a stack and a queue nDraw the binary search tree that is built from inserting a series of items * Fundamentals of Computer Science Hai MoPage 5 9.1 Abstract Data Types nAbstract data type (ADT) A data type whose properties (data and operations) are specified independently of any particular implementation * Fundamentals of Computer Science Hai MoPage 6 Three Views of Data Application (user) level View of the data within a particular problem View sees data objects in terms of properties and behaviors * Fundamentals of Computer Science Hai MoPage 7 Three Views of Data Logical (abstract) level Abstract view of the data and the set of operations to manipulate them View sees data objects as groups of objects with similar properties and behaviors * Fundamentals of Computer Science Hai MoPage 8 Three Views of Data Implementation level A specific representation of the structure that hold the data items and the coding of the operations in a programming language View sees the properties represented as specific data fields and behaviors represented as methods implemented in code * Fundamentals of Computer Science Hai MoPage 9 9.1 Abstract Data Types Composite data type A data type in which a name is given to a collection of data value Data structures The implementation of a composite data fields in an abstract data type Containers Objects whose role is to hold and manipulate other objects * Fundamentals of Computer Science Hai MoPage 10 9.2 Implementation Two logical implementations of containers Array-based implementation(基于数组的实现) Objects in the container are kept in an array Linked-based implementation(基于链表的实现) Objects in the container are not kept physically together, but each item tells you where to go to get the next one in the structure * Fundamentals of Computer Science Hai MoPage 11 9.2 Implementation Think of the container as a list of items Here are the logical operations that can be applied to lists Add item Put an item into the list Remove itemRemove an item from the list Get next itemGet (look) at the next item more itemsAre there more items? * Fundamentals of Computer Science Hai MoPage 12 Unsorted and Sorted Containers Unsorted container The items in the container are not ordered in any way Sorted container The items in the container are ordered by the value of some field within the items * Fundamentals of Computer Science Hai MoPage 13 Array-based implementation nAn implementation of a container in which the items are stored in an array The array goes from 0 to MAX-LENGTH-1 The items in the container (the list) go from 0 to length-1 * Fundamentals of Computer Science Hai MoPage 14 Array-Based Implementations An unsorted list of integersA sorted list of integers * Fundamentals of Computer Science Hai MoPage 15 Array-based implementation nAdd item means that given an index, shift the items that follow down one slot in the array and store the item at the index position. nRemove the item means that given an index, shift the items that follow up one slot in the array. nGet next item means to increment the value used as an index and access that indexed position. nMore items means that the variable used as an index is less than length. * Fundamentals of Computer Science Hai MoPage 16 9.2 Implementation nLinked implementation An implementation of a container where the items are stored together with information on where the next item can be found * Fundamentals of Computer Science Hai MoPage 17 Linked Implementation Linked implementation An implementation based on the concept of a node Node(节点) A holder for two pieces of information nthe item that the user wants in the list (item) na pointer to the next node in the list (next) * Fundamentals of Computer Science Hai MoPage 18 An unsorted linked list * Fundamentals of Computer Science Hai MoPage 19 A sorted linked list * Fundamentals of Computer Science Hai MoPage 20 Store a node with info of 67 after current * Fundamentals of Computer Science Hai MoPage 21 Remove node next(current) * Fundamentals of Computer Science Hai MoPage 22 Linked implementation nPut item means given current, insert a new node with item in the info part of the node between current and next(current) nRemove item means given current, remove the next(current) nGet next item means to set current to next(current) nMore items means that current does not contain null * Fundamentals of Computer Science Hai MoPage 23 Linked implementation nLinked lists are also called unbounded lists because the nodes are created at run time nIn a linked list, it is not necessary to keep track of the number of items in the list explicitly * Fundamentals of Computer Science Hai MoPage 24 9.3 Lists(列表) nThree properties of lists The items are homogeneous The items are linear Lists have varying length * Fundamentals of Computer Science Hai MoPage 25 9.3 Lists nBasic List Operations create itself insert an item delete an item print itself know the number of items it contains * Fundamentals of Computer Science Hai MoPage 26 9.3 Lists nGeneric data type(class) A data type (or class) in which the operations are defined but the type or class of the objects being manipulated(操作) is not * Fundamentals of Computer Science Hai MoPage 27 Unsorted Lists Create (initialize) Set length to 0 Insert(item) Find where the item belongs Put the item there Increment length Remove(item) Find the item Remove the item Decrement length * Fundamentals of Computer Science Hai MoPage 28 Unsorted Lists Print While (more items) Get next item Print Item Know Length return length * Fundamentals of Computer Science Hai MoPage 29 Sorted Lists From the application view, how do the sorted an unsorted list differ? The decomposition of which algorithm steps must be different? List,Stack,Queue,Array,link List stack queue Array-based implementationLinked-based implementation * Fundamentals of Computer Science Hai MoPage 31 9.4 Sorting nSelection Sort(选择排序) 1. Find the name that comes first in the alphabet, and write it on a second sheet of paper. 2. Cross out the name on the original list. 3. Continue this cycle until all the names on the original list have been crossed out and written onto the second list, at which point the second list is sorted. * Fundamentals of Computer Science Hai MoPage 32 Selection Sort * Fundamentals of Computer Science Hai MoPage 33 Selection Sort Selection Sort * Fundamentals of Computer Science Hai MoPage 34 Question nHow many comparisons are needed to finish a selection sort for a list of n elements? * Fundamentals of Computer Science Hai MoPage 35 * Fundamentals of Computer Science Hai MoPage 36 9.4 Sorting nBubble Sort(冒泡排序) Starting with the last element of a list, we compare successive pairs of elements, swapping whenever the bottom element of the pair is smaller than the one above it * Fundamentals of Computer Science Hai MoPage 37 Bubble Sort * Fundamentals of Computer Science Hai MoPage 38 * Fundamentals of Computer Science Hai MoPage 39 9.4 Sorting nQuicksort Be based on the idea that it is faster and easier to sort two small lists than one larger one. The basic strategy of this sort is to divide and conquer. * Fundamentals of Computer Science Hai MoPage 40 Quicksort Quicksort If (there is more than one item in listfirstlistlast) Select splitVal Split the list so that listfirstlistsplitPoint-1 splitVal Quicksort the left half Quicksort the right half * Fundamentals of Computer Science Hai MoPage 41 Quicksort Split * Fundamentals of Computer Science Hai MoPage 42 Split Set left to first + 1 Set right to last Do Increment left until listleft splitVal OR left right Decrement right until listright right If (left splitVal or leftright 9206101486011 first leftright c Decrement right until listright right 9206101486011 first left right Splitting algorithm(2) * Fundamentals of Computer Science Hai MoPage 44 d Swap listleft and listright ; move left and right toward each other 9861014206011 first leftright e Increment left until listleft splitVal or left right Decrement right until listrightright 9861014206011 first rightleft f left right so no swap occurs within the loop. Swap listfirst and listright 6891014206011 first right (splitPoint) * Fundamentals of Computer Science Hai MoPage 45 9.5 Binary Search(二分查找) nSequential search Looking for an item from the beginning of the list nBinary search Looking for an item in an already sorted list by eliminating large portions of the data on each comparison * Fundamentals of Computer Science Hai MoPage 46 9.5 Binary Search Boolean Binary Search (first, last) If (first last) return false Else Set middle to (first + last)/2 Set result to pareTo(listmiddle) If (result is equal to 0) return true Else If (result 0) Binary Search (first, middle - 1) Else Binary Search (middle + 1, last) * Fundamentals of Computer Science Hai MoPage 47 9.5 Binary Search * Fundamentals of Computer Science Hai MoPage 48 9.5 Binary Search Average Number of Comparisons * Fundamentals of Computer Science Hai MoPage 49 9.6 Stacks and Queues Stack (栈) An abstract data type in which accesses are made at only one end nLIFO, which stands for Last In First Out nThe insert is called Push and the delete is called Pop * Fundamentals of Computer Science Hai MoPage 50 9.6 Stacks and Queues nStacks Last In First Out Push, Pop 90, 65, 80, 95, 75, 60 * Fundamentals of Computer Science Hai MoPage 51 9.6 Stacks and Queues Queue(队列) An abstract data type in which items are entered at one end and removed from the other end nFIFO, for First In First Out nNo standard queue terminology nEnqueue, Enque, Enq, Enter, and Insert are used for the insertion operation nDequeue, Deque, Deq, Delete, and Remove are used for the deletion operation. * Fundamentals of Computer Science Hai MoPage 52 9.6 Stacks and Queues nImplementation of A linked stack * Fundamentals of Computer Science Hai MoPage 53 Implementation of A linked queue * Fundamentals of Computer Science Hai MoPage 54 9.7 Trees nTree At the top of the hierarchy would be the parents, the children would be at the next level, the grandchildren at the next level, and so on. These hierarchical structures are called trees. * Fundamentals of Computer Science Hai MoPage 55 9.7 Trees nBinary tree(二分树) A container object with a unique starting node called the root, in which each node is capable of having two child nodes, and in which a unique path exists from the root to every other node nRoot The top node of a tree structure; a node with no parent nLeaf node A tree node that has no children * Fundamentals of Computer Science Hai MoPage 56 A Binary tree * Fundamentals of Computer Science Hai MoPage 57 A Binary tree Root node Node with two children Node with right child Leaf node Node with left child * Fundamental