[工學]9抽象數(shù)據(jù)類型和算法(編輯修改稿)
2025-02-15 10:50 本頁面
【文章內(nèi)容簡介】 nked lists are also called unbounded lists because the nodes are created at run time ? In a linked list, it is not necessary to keep track of the number of items in the list explicitly 2022/2/16 Fundamentals of Computer Science Hai Mo Page 24 Lists(列表 ) ? Three properties of lists ? The items are homogeneous ? The items are linear ? Lists have varying length 2022/2/16 Fundamentals of Computer Science Hai Mo Page 25 Lists ? Basic List Operations ? create itself ? insert an item ? delete an item ? print itself ? know the number of items it contains 2022/2/16 Fundamentals of Computer Science Hai Mo Page 26 Lists ? Generic 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 2022/2/16 Fundamentals of Computer Science Hai Mo Page 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 2022/2/16 Fundamentals of Computer Science Hai Mo Page 28 Unsorted Lists Print While (more items) Get next item Print Item Know Length return length 2022/2/16 Fundamentals of Computer Science Hai Mo Page 29 Sorted Lists From the application view, how do the sorted an unsorted list differ? The deposition of which algorithm steps must be different? List,Stack,Queue,Array,link List stack queue Arraybased implementation Linkedbased implementation 2022/2/16 Fundamentals of Computer Science Hai Mo Page 31 Sorting ? Selection Sort(選擇排序 ) 1. Find the name that es 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. 2022/2/16 Fundamentals of Computer Science Hai Mo Page 32 Selection Sort 2022/2/16 Fundamentals of Computer Science Hai Mo Page 33 Selection Sort Selection Sort 2022/2/16 Fundamentals of Computer Science Hai Mo Page 34 Question ? How many parisons are needed to finish a selection sort for a list of n elements? 2022/2/16 Fundamentals of Computer Science Hai Mo Page 35 2022/2/16 Fundamentals of Computer Science Hai Mo Page 36 Sorting ? Bubble Sort(冒泡排序 ) － Starting with the last element of a list, we pare successive pairs of elements, swapping whenever the bottom element of the pair is smaller than the one above it 2022/2/16 Fundamentals of Computer Science Hai Mo Page 37 Bubble Sort 2022/2/16 Fundamentals of Computer Science Hai Mo Page 38 2022/2/16 Fundamentals of Computer Science Hai Mo Page 39 Sorting ? Quicksort － 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 i
教學課件相關推薦
鄂ICP備17016276號-1