tailieunhanh - Bài giảng Cấu trúc dữ liệu - Chương 4: Tìm kiếm

Chương 4: Tìm kiếm trong "Bài giảng Cấu trúc dữ liệu" trình bày những nội dung chính về các phương pháp tìm kiếm trong danh sách, tìm kiếm tuyến tính, tìm kiếm nhị phân, tìm kiếm nội suy và cây nhị phân tìm kiếm. | CHƯƠNG 4- TÌM KIẾM CHƯƠNG 4. TÌM KIẾM Các phương pháp tìm kiếm trong danh sách Tìm kiếm tuyến tính Tìm kiếm nhị phân Tìm kiếm nội suy Cây nhị phân tìm kiếm Định nghĩa Các phép toán Các phương pháp tìm kiếm trong danh sách Mô hình chung của bài toán tìm kiếm: Có một tập n đối tượng. Mỗi đối tượng có nhiều thuộc tính, được thể hiện bằng một kiểu bản ghi gồm nhiều trường. Trong đó có 1 trường mà giá trị của nó đặc trưng cho đối tượng, cho phép xác định hoàn toàn đối tượng, thường gọi là khóa. Bài toán tìm kiếm: Có một tập các đối tượng và cho trước một đối tượng x. Cần tìm xem x có mặt trong tập hợp đã cho hay không? Các phương pháp tìm kiếm trong danh sách Mô hình toán học của bài toán tìm kiếm: Có tập hợp n giá trị khóa k1, k2, kn. Cho giá trị khóa x. Tìm xem x có tồn tại ki=x? Công việc tìm kiếm sẽ | CHƯƠNG 4- TÌM KIẾM CHƯƠNG 4. TÌM KIẾM Các phương pháp tìm kiếm trong danh sách Tìm kiếm tuyến tính Tìm kiếm nhị phân Tìm kiếm nội suy Cây nhị phân tìm kiếm Định nghĩa Các phép toán Các phương pháp tìm kiếm trong danh sách Mô hình chung của bài toán tìm kiếm: Có một tập n đối tượng. Mỗi đối tượng có nhiều thuộc tính, được thể hiện bằng một kiểu bản ghi gồm nhiều trường. Trong đó có 1 trường mà giá trị của nó đặc trưng cho đối tượng, cho phép xác định hoàn toàn đối tượng, thường gọi là khóa. Bài toán tìm kiếm: Có một tập các đối tượng và cho trước một đối tượng x. Cần tìm xem x có mặt trong tập hợp đã cho hay không? Các phương pháp tìm kiếm trong danh sách Mô hình toán học của bài toán tìm kiếm: Có tập hợp n giá trị khóa k1, k2, kn. Cho giá trị khóa x. Tìm xem x có tồn tại ki=x? Công việc tìm kiếm sẽ hoàn thành khi: Tìm được 1 bản ghi có giá trị khóa =x, lúc đó phép tìm kiếm được thành công successful. Không tìm thấy bản ghi nào có khóa bằng x, gọi là tìm kiếm không thành công unsuccessful. Lúc này có thể xuất hiện yêu cầu bổ sung giá trị x vào tập hợp, gọi là tìm kiếm có bổ sung. Tìm kiếm tuần tự (sequential searching) Là phương pháp tìm kiếm đơn giản và cổ điển. Ý tưởng: Bắt đầu từ bản ghi thứ nhất, lần lượt so sánh khóa tìm kiếm với khóa tương ứng của bản ghi trong bảng, cho tới khi tìm được bản ghi mong muốn hoặc đã hết bảng mà chưa tìm thấy. Tìm kiếm tuần tự (sequential searching) Giải thuật 1: SEQUEN-SEARCH(k,n,x) 1. //Khởi đầu i=1; k[i+1]=x 2. // Tìm khóa trong dãy while (k[i] !=x) do i++; 3. // Tìm thấy hay không If (i==n+1) return 0 //không tìm thấy else return i; Tìm kiếm tuần tự (sequential searching) Giải thuật 2 (giải thuật .