tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Tìm kiếm

Bài giảng Cấu trúc dữ liệu và giải thuật - Tìm kiếm gồm có những nội dung cơ bản sau: Bài toán tìm kiếm, tìm kiếm tuần tự, tìm kiếm nhị phân, cây quyết định. để biết thêm những nội dung chi tiết. | Chương 4 Tìm kiếm phần 1 ffc MỊỊữneí last OoS search c reany Con m rtow bcòSmc f ỈÍXỈ Jma service across results X 1 I t0UỊ Ị SĨS I lV j riccup _____ frtrtt I buri Owfifit tiff pGMail -ạ shared problem . art cĩeịũ IwWW Aa business arỂe removed montfi - ns sone Hiepnd@ Nội dung Bài toán tìm kiếm Tìm kiếm tuần tự Tìm kiếm nhị phân Cây quyết định 3 14 2011 Bài toán tìm kiếm Một số bài toán tìm kiếm Cho tên một người tìm kiếm số điện thoại người đó trong danh bạ Cho tên một tài khoản tìm kiếm các giao dịch của tài khoản đó Cho tên một sinh viên tìm kiếm thông tin về kết quả học tập của sinh viên đó Khóa key là thông tin mà chúng ta dùng để tìm kiếm Tìm kiếm trong và tìm kiếm ngoài Số lượng dữ liệu Tốc độ truy nhập dữ liệu 1 Tìm kiếm tuần tự Tìm kiếm tuân tự Là phương pháp đơn giản nhất Duyệt từ đầu đến cuối danh sách cho đến khi tìm được bản ghi mong muốn Hoặc là đến cuối mà không tìm được Tìm kiếm tuần tự Tìm kiếm trên mảng int sequentialSearch int records int key int position int i for i 0 i MAX Ỉ if records i key position i tim thay return 0 return -l khong tim thay 3 14 2011 Tìm kiếm tuần tự Tìm kiếm trên danh sách móc nối typedef struct node char hoten 30 char diachi 50 float diemTB struct node pNext NODE Tìm kiếm tuần tự int sequentialSearch NODE pHead char key NODE retVal NODE ptr pHead while ptr NULL if strcmp ptr- hoten key 0 retVal ptr return 0 else ptr ptr- pNext return -1 2 Phân tích Giả sử tồn tại bản ghi chứa khóa cần tìm. Trường hợp tốt nhất chỉ cần 1 phép so sánh Trường hợp tồi nhất cần n phép so sánh Trung bình cần 1 2 3 . w n Độ phức tạp ơ w Chỉ phù hợp cho danh sách ít phần tử Tìm kiếm tuần tự Bài tập Viết lại hàm tìm kiếm tuần tự để có thể đếm được số lượng phép so sánh cần thiết trong quá trình tìm kiếm đối với danh sách móc nối . 3 14 2011 0 1 00 000 0000 11 111 1111 111 11111 0000000 00000000 Binary Search Tìm kiếm nhị phân Tìm kiếm nhị phân Trường hợp các bản ghi đã được sắp xếp theo thứ tự tìm kiếm tuần tự không