Chapter 9 Abstract Data Typesand Algorithmsn9.1 Abstract Data Typesn9.2 Implementationn9.3 Listsn9.4 Sortingn9.5 Binary Searchn9.6 Stacks and Queuesn9.7 Trees2024/7/1919 抽象数据类型和算法2024/7/19 Fundamentals of Computer Science Hai MoPage 2Chapter GoalsnDefine an abstract data type and discuss its role in algorithm developmentnDistinguish between a data type and a data structurenDistinguish between an array-based implementation and a linked implementationnDistinguish between an array and a list9 抽象数据类型和算法2024/7/19 Fundamentals of Computer Science Hai MoPage 3Chapter GoalsnDistinguish between an unsorted list and a sorted listnDistinguish between a selection sort and a bubble sortnDescribe the Quicksort algorithmnApply the selection sort, the bubble sort, and the Quicksort to a list of items by handnApply the binary search algorithm9 抽象数据类型和算法2024/7/19 Fundamentals of Computer Science Hai MoPage 4Chapter GoalsnDistinguish between the behavior of a stack and a queuenDraw the binary search tree that is built from inserting a series of items9 抽象数据类型和算法9.1 Abstract Data TypesnAbstract data type (ADT) A data type whose properties (data and operations) are specified independently of any particular implementation2024/7/1959 抽象数据类型和算法2024/7/19 Fundamentals of Computer Science Hai MoPage 6Three Views of DataApplication (user) levelView of the data within a particular problemView sees data objects in terms of properties and behaviors9 抽象数据类型和算法2024/7/19 Fundamentals of Computer Science Hai MoPage 7Three Views of DataLogical (abstract) levelAbstract view of the data and the set of operations to manipulate themView sees data objects as groups of objects with similar properties and behaviors9 抽象数据类型和算法2024/7/19 Fundamentals of Computer Science Hai MoPage 8Three Views of DataImplementation levelA specific representation of the structure that hold the data items and the coding of the operations in a programming languageView sees the properties represented as specific data fields and behaviors represented as methods implemented in code9 抽象数据类型和算法2024/7/19 Fundamentals of Computer Science Hai MoPage 99.1 Abstract Data TypesComposite data typeA data type in which a name is given to a collection of data valueData structures The implementation of a composite data fields in anabstract data typeContainers Objects whose role is to hold and manipulate otherobjects9 抽象数据类型和算法9.2 ImplementationTwo logical implementations of containersArray-based implementation(基于数组的实现)Objects in the container are kept in an arrayLinked-based implementation(基于链表的实现)Objects in the container are not kept physicallytogether, but each item tells you where to goto get the next one in the structure 2024/7/19109 抽象数据类型和算法2024/7/19 Fundamentals of Computer Science Hai MoPage 119.2 ImplementationThink of the container as a list of itemsHere are the logical operations that can be applied to listsAdd item Put an item into the listRemove itemRemove an item from the listGet next itemGet (look) at the next itemmore itemsAre there more items?9 抽象数据类型和算法2024/7/19 Fundamentals of Computer Science Hai MoPage 12Unsorted and Sorted ContainersUnsorted containerThe items in the container are not ordered in any waySorted containerThe items in the container are ordered by the value of some field within the items9 抽象数据类型和算法Array-based implementationnAn implementation of a container in which the items are stored in an arrayThe array goesfrom 0 toMAX-LENGTH-1The items in the container(the list) gofrom 0 tolength-12024/7/19139 抽象数据类型和算法Array-Based ImplementationsAn unsorted list of integersA sorted list of integers2024/7/19149 抽象数据类型和算法Array-based implementationnAdd 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.2024/7/19159 抽象数据类型和算法9.2 ImplementationnLinked implementation An implementation of a container where the items are stored together with information on where the next item can be found2024/7/19169 抽象数据类型和算法2024/7/19 Fundamentals of Computer Science Hai MoPage 17Linked ImplementationLinked implementation An implementation based on the concept of a nodeNode(节点节点) A holder for two pieces of informationnthe item that the user wants in the list (item)na pointer to the next node in the list (next)9 抽象数据类型和算法An unsorted linked list2024/7/19189 抽象数据类型和算法A sorted linked list2024/7/19199 抽象数据类型和算法Store a node with info of 67 after current2024/7/19209 抽象数据类型和算法Remove node next(current)2024/7/19219 抽象数据类型和算法Linked implementationnPut 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 null2024/7/19229 抽象数据类型和算法Linked implementationnLinked lists are also called unbounded lists because the nodes are created at run timenIn a linked list, it is not necessary to keep track of the number of items in the list explicitly2024/7/19239 抽象数据类型和算法9.3 Lists(列表列表)nThree properties of listsThe items are homogeneousThe items are linearLists have varying length2024/7/19249 抽象数据类型和算法9.3 ListsnBasic List Operations create itself insert an item delete an item print itself know the number of items it contains2024/7/19259 抽象数据类型和算法9.3 ListsnGeneric 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 not2024/7/19269 抽象数据类型和算法Unsorted ListsCreate (initialize) Set length to 0Insert(item)Find where the item belongsPut the item thereIncrement lengthRemove(item) Find the itemRemove the itemDecrement length2024/7/19279 抽象数据类型和算法Unsorted ListsPrint While (more items)Get next itemPrint ItemKnow Length return length2024/7/19289 抽象数据类型和算法Sorted ListsFrom the application view, how do the sorted an unsorted list differ?The decomposition of which algorithm steps must be different?2024/7/19299 抽象数据类型和算法List,Stack,Queue,Array,linkListstackqueueArray-based implementationLinked-based implementation9 抽象数据类型和算法9.4 SortingnSelection 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.2024/7/19319 抽象数据类型和算法Selection Sort2024/7/19329 抽象数据类型和算法Selection Sort2024/7/19339 抽象数据类型和算法Selection Sort2024/7/19349 抽象数据类型和算法QuestionnHow many comparisons are needed to finish a selection sort for a list of n elements?2024/7/19359 抽象数据类型和算法9.4 SortingnBubble Sort(冒泡排序)Starting with the last element of a list, we compare successive pairs of elements, s whenever the bottom element of the pair is smaller than the one above it2024/7/19369 抽象数据类型和算法2024/7/19379 抽象数据类型和算法Bubble Sort2024/7/19389 抽象数据类型和算法9.4 SortingnQuicksort 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.2024/7/19399 抽象数据类型和算法QuicksortQuicksortIf (there is more than one item in listfirst.listlast)Select splitValSplit the list so thatlistfirst.listsplitPoint-1 splitValQuicksort the left halfQuicksort the right half2024/7/19409 抽象数据类型和算法2024/7/19 Fundamentals of Computer Science Hai MoPage 41Quicksort9 抽象数据类型和算法SplitSplit Set left to first + 1Set right to lastDoIncrement left until listleft splitVal OR left rightDecrement right until listright right If (left right)Sleft and listrightWhile (left splitVal or leftright 9206101486011firstleftrightc Decrement right until listright right 9206101486011firstleftright2024/7/19439 抽象数据类型和算法Splitting algorithm(2)d Swap listleft and listright ; move left and right toward each other9861014206011firstleftrighte Increment left until listleft splitVal or left right Decrement right until listrightright9861014206011firstrightleftf left right so no s within the loop. Swap listfirst and listright6891014206011firstright(splitPoint)2024/7/19449 抽象数据类型和算法9.5 Binary Search(二分查找二分查找)nSequential searchLooking for an item from the beginning of the listnBinary search Looking for an item in an already sorted list by eliminating large portions of the data on each comparison2024/7/19459 抽象数据类型和算法9.5 Binary SearchBoolean Binary Search (first, last)If (first last)return falseElseSet middle to (first + last)/2Set result to item.compareTo(listmiddle)If (result is equal to 0)return trueElseIf (result 0)Binary Search (first, middle - 1)ElseBinary Search (middle + 1, last) 2024/7/19469 抽象数据类型和算法9.5 Binary Search2024/7/19479 抽象数据类型和算法9.5 Binary SearchAverage Number of Comparisons2024/7/19489 抽象数据类型和算法2024/7/19 Fundamentals of Computer Science Hai MoPage 499.6 Stacks and QueuesStack (栈)An abstract data type in which accesses are made at only one endnLIFO, which stands for Last In First OutnThe insert is called Push and the delete is called Pop9 抽象数据类型和算法9.6 Stacks and QueuesnStacksLast In First OutPush, Pop90, 65, 80, 95, 75, 602024/7/19509 抽象数据类型和算法9.6 Stacks and QueuesQueue(队列队列) An abstract data type in which items are entered at one end and removed from the other endnFIFO, for First In First OutnNo standard queue terminologynEnqueue, Enque, Enq, Enter, and Insert are used for the insertion operationnDequeue, Deque, Deq, Delete, and Remove are used for the deletion operation.2024/7/19519 抽象数据类型和算法9.6 Stacks and QueuesnImplementation of A linked stack2024/7/19529 抽象数据类型和算法Implementation of A linked queue2024/7/19539 抽象数据类型和算法9.7 TreesnTreeAt 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.2024/7/19549 抽象数据类型和算法9.7 TreesnBinary 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 nodenRoot The top node of a tree structure; a node with no parentnLeaf node A tree node that has no children2024/7/19559 抽象数据类型和算法A Binary tree2024/7/19569 抽象数据类型和算法2024/7/19 Fundamentals of Computer Science Hai MoPage 57A Binary treeRoot nodeNode with two childrenNode with right childLeaf nodeNode with left child9 抽象数据类型和算法Two variations of a binary tree2024/7/19589 抽象数据类型和算法9.7 TreesnBinary Search Tree（二分查找树） a node in a binary search tree can have zero, one, or two children. The value in any node is greater than the value in any node in its left subtree and less than the value in any node in its right subtree.2024/7/19599 抽象数据类型和算法9.7 TreesnBuilding a Binary Search Tree2024/7/19609 抽象数据类型和算法A binary search tree builtfrom strings2024/7/19619 抽象数据类型和算法9.7 TreesnPrinting the Data in a Binary Search TreeBCLNS2024/7/19629 抽象数据类型和算法GraphsnGraph: A data structure that consists of a set of odes and a set of edges that relate the nodes to each othernVertex: A node in a graphnEdge (Arc): A pair of vertices representing a connection between two nodes in a graphnUndirected graph: A graph in which the edges have no directionnDirected graph: A graph in which each edge is directed from one vertex to another (or the same) vertex2024/7/19639 抽象数据类型和算法Examples of graphs2024/7/19649 抽象数据类型和算法Examples of graphs2024/7/19659 抽象数据类型和算法Examples of graphs2024/7/19669 抽象数据类型和算法