Data Structure教学课件（华南理工）Ch09-Searching.pdfVIP

Data Structure Chapter 9 Searching Dr. Patrick Chan School of Computer Science and Engineering South China University of Technology Outline Introduction (Ch9) Sequential and List Method (Ch 9.1 – 9.2) Sequential Sort Jump Sort Dictionary Sort Direct Access by Key Value (Ch 9.4) Hashing Lec 9: Searching 2 Searching Given: Distinct keys k , k , …, k and collection T of n records 1 2 n of the form (k , I ), (k , I ), …, (k , I ), where I is the 1 1 2 2 n n j information associated with key k for 1 ≤j ≤ n j Search Problem: For key value K , locate the record (k , I ) in T such that k = K j j j Searching is a systematic method for locating the record(s) with key value k = K j Lec 9: Searching 3 Searching The following operations are related to the searching: Insertions Deletions These operations will maintain the records in a particular structure Lec 9: Searching 4 Type of Search Successful Search A record with key k = K is found j Unsuccessful Search No record with k = K is found j (Assume no such record exists) Highest cost usually Le