[工學(xué)]9抽象數(shù)據(jù)類型和算法-閱讀頁
2025-02-03 10:50本頁面
【正文】 rst] [left] [right] Splitting algorithm(2) 2022/2/16 Fundamentals of Computer Science Hai Mo Page 44 d Swap list[left] and list[right] 。 move left and right toward each other 9 8 6 10 14 20 60 11 [first] [left] [right] e Increment left until list[left] splitVal or left right Decrement right until list[right]= splitVal or left right 9 8 6 10 14 20 60 11 [first] [right] [left] f left right so no swap occurs within the loop. Swap list[first] and list[right] 6 8 9 10 14 20 60 11 [first] [right] (splitPoint) 2022/2/16 Fundamentals of Computer Science Hai Mo Page 45 Binary Search(二分查找 ) ? Sequential search － Looking for an item from the beginning of the list ? Binary search － Looking for an item in an already sorted list by eliminating large portions of the data on each parison 2022/2/16 Fundamentals of Computer Science Hai Mo Page 46 Binary Search Boolean Binary Search (first, last) If (first last) return false Else Set middle to (first + last)/2 Set result to (list[middle]) If (result is equal to 0) return true Else If (result 0) Binary Search (first, middle 1) Else Binary Search (middle + 1, last) 2022/2/16 Fundamentals of Computer Science Hai Mo Page 47 Binary Search 2022/2/16 Fundamentals of Computer Science Hai Mo Page 48 Binary Search Average Number of Comparisons 2022/2/16 Fundamentals of Computer Science Hai Mo Page 49 Stacks and Queues Stack (棧 ) An abstract data type in which accesses are made at only one end ? LIFO, which stands for Last In First Out ? The insert is called Push and the delete is called Pop 2022/2/16 Fundamentals of Computer Science Hai Mo Page 50 Stacks and Queues ? Stacks － Last In First Out － Push, Pop 90, 65, 80, 95, 75, 60 2022/2/16 Fundamentals of Computer Science Hai Mo Page 51 Stacks and Queues Queue(隊(duì)列 ) An abstract data type in which items are entered at one end and removed from the other end ? FIFO, for First In First Out ? No standard queue terminology ? Enqueue, Enque, Enq, Enter, and Insert are used for the insertion operation ? Dequeue, Deque, Deq, Delete, and Remove are used for the deletion operation. 2022/2/16 Fundamentals of Computer Science Hai Mo Page 52 Stacks and Queues ? Implementation of A linked stack 2022/2/16 Fundamentals of Computer Science Hai Mo Page 53 Implementation of A linked queue 2022/2/16 Fundamentals of Computer Science Hai Mo Page 54 Trees ? Tree － 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. 2022/2/16 Fundamentals of Computer Science Hai Mo Page 55 Trees ? Binary 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 ? Root － The top node of a tree struct
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1