Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2.1 - Trần Minh Thái

Mục tiêu của bài giảng này nhằm giúp người học xác định được vai trò của tìm kiếm và sắp xếp trong hệ thống thông tin, nắm vững và minh họa được giải thuật tìm kiếm tuyến tính và tìm kiếm nhị phân trên mảng một chiều, cài đặt được giải thuật tìm kiếm bằng ngôn ngữ C/C++. Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2.1 - Trần Minh Thái Chương 2.1. Giải thuật tìm kiếmTrầnMinhTháiEmail:minhthai@itc.edu.vnWebsite:www.minhthai.edu.vn 1Mục tiêu• Xác định được vai trò của tìm kiếm và sắp xếp trong hệ thống thông tin• Nắm vững và minh họa được giải thuật tìm kiếm tuyến tính và tìm kiếm nhị phân trên mảng một chiều• Cài đặt được giải thuật tìm kiếm bằng ngôn ngữ C/C++ 2Suy nghĩ ? Tại sao hầu hết phần mềm phải cóchức năng tìm kiếm và sắp xếp, mối quan hệ giữa tìm kiếm và sắp xếp? 3Nhu cầu tìm kiếm và sắp xếp• Tìm kiếm: Có trong hầu hết trong các hệ thống thông tin• Muốn tìm kiếm nhanh và hiệu quả  dữ liệu có thứ tự  sắp xếp 4Các giải thuật tìm kiếm• Có 2 giải thuật thường được áp dụng: Tìm tuyến tính và tìm nhị phân.• Đặc tả: a1 • Tập a2 dữ liệua3 được a4 lưu trữa5 là dãy số a1, … a2, ... ,aN. an- aN 1 • Khai báo: int a[N]; • Khóa cần tìm: int x; 5Tìm kiếm tuyến tính (Linear Search)Ý tưởng Lần lượt so sánh x với phần tử thứ nhất, thứ hai, ... của mảng acho đến khi gặp được phần tử cần tìm, hoặc hết mảng 6Tìm kiếm tuyến tính• Minh họa tìm x =10 10 Đã tìm Chưa hết thấy mảng tại 7 5 12 41 10 32 13 9 15 3 vị trí 5• 1 họa Minh 2 tìm 3x =254 5 6 7 8 9 10 25 Đã hết Chưa hết mảng mảng 7 5 12 41 10 32 13 9 15 3 1 2 3 4 5 6 7 8 9 10 7Giải thuậtBước 1: i=1;//bắtđầutừphầntửđầutiên củadãyBước 2: Sosánha[i]vớix,có2khảnăng:• a[i]=x:Tìmthấy.Dừng• a[i]!=x:SangBước3.Bước 3:• i=i+1;//xéttiếpphầntửkếtrongmảng• Nếui>N:Hếtmảng,khôngtìmthấy.Dừng Ngượclại:LặplạiBước2.8Nguyên tắc cài đặt hàm tìm kiếm• Nếu có xuất hiện phần tử có giá trị x thì trả về vị trí tìm được• Ngược lại thì trả về -1 9Cài đặtintLinearSearch(inta[],intN,intx){ inti=0; while((iCải tiếnDùng lính canh giúp giảm bớt phép so sánh• Minh họa tìm x =10 10 7 5 12 41 10 32 13 9 15 3 10• 1 họa Minh 2 tìm3x = 25 4 5 6 7 8 9 10 11 25 7 5 12 41 10 32 13 9 15 3 25 25 1 2 3 4 5 6 7 8 9 10 11 11Cài đặtintLinearSearch2(inta[],intN,intx){ inti=0; a[N]=x;//thêmphầntửxsaumảng while(a[i]!=x) i++; if(i==N) return-1;//tìmhếtmảng else returni; //tìmthấyxtạivịtríi}Độ phức tạp tính toán cấp n: T(n)=O(n) 12Q&A 13Tìm kiếm nhị phân (Binary Search)Ý tưởng• Áp dụng đối với dãy số đã có thứ tự• Mỗi bước tiến hành so sánh x với phần tử ở giữa của dãy hiện hành để quyết định phạm vi tìm kế tiếp 14Minh họa tìm x = 41 x x x 3 14 16 19 22 41 46 51 63 71 1 2 3 4 5 6 7 8 9 10 Tìm thấy x tại vị trí 6 l m m r m 15Minh họa tìm x = 45 x x x x 3 14 16 19 22 41 46 51 63 71 1 2 3 4 5 6 7 8 9 10 ...