Đăng ký Đăng nhập

Tài liệu Chuong4_tim kiem

.PDF
40
333
74

Mô tả:

CHƯƠNG 4- TÌM KIẾM 1 CHƯƠNG 4. TÌM KIẾM 4.1 Các phương pháp tìm kiếm trong danh sách 4.1.1 Tìm kiếm tuyến tính 4.1.2 Tìm kiếm nhị phân 4.1.1 Tìm kiếm nội suy 4.2 Cây nhị phân tìm kiếm 4.2.1 Định nghĩa 4.2.2 Các phép toán 2 4.1 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? 3 4.1 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. 4 4.1.1 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. 5 4.1.1 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; 6 4.1.1 Tìm kiếm tuần tự (sequential searching)  Giải thuật 2 (giải thuật đệ quy-tìm trong danh sách liên kết): Node *timdequy(struct node *first, element_type e) { if (first == NULL) return NULL; else if (first->element == e) return first; else return timdequy(first->next, e); } 7 4.1.1 Tìm kiếm tuần tự (sequential searching)  Đánh giá giải thuật: Trường hợp tốt nhất: Tmin = 1; Trường hợp xấu nhất: Tmax = O(n); Trung bình Ttb= O(n) 8 4.1.2. Tìm kiếm nhị phân (Binary Serching)  Là phương pháp tìm kiếm thông dụng.  Ý tưởng: – – – – Dãy khóa đã được sắp xếp theo thứ tự (tăng dần hoặc giảm dần). Giả sử dãy khóa đang xét là kl và kr thì khóa ở giữa dãy sẽ là ki với i = (l+r)/2. Tìm kiếm sẽ kết thúc nếu x=ki. Ngược lại, nếu xki, phép tìm kiếm sẽ được thực hiện tiếp với ki+1 với kr. Quá trình tìm kiếm sẽ dừng khi tìm thấy khóa hoặc dãy đang xét trở nên rỗng. 9 4.1.2. Tìm kiếm nhị phân (Binary Serching)  Giải thuật 1: BINARY-SEARCH(k,n,x) b1. l=1; r=n;//khởi đầu b2. while (l<=r) do //tìm {m = (l+r)/2; //tính chỉ số giữa if x k[m] then l = m+1; else return m; } b3. return 0; // tìm không thấy. 10 4.1.2. Tìm kiếm nhị phân (Binary Serching)  Giải thuật 2(giải thuật đệ quy): RBINARY-SEARCH(l,r,k,x) b1. if lk[m] then loc = RBINARY-SEARCH(m+1,r,k,x) else loc=m; B2: Return loc; 11 4.1.2. Tìm kiếm nhị phân (Binary Serching)  Đánh giá giải thuật: – – – Trường hợp tốt nhất Tmin =1, tìm được ngay lần đầu tiên. Trường hợp xấu nhất Tmax = k+w[n/2k) Chứng minh được Ttb = O(log2n). Trong tất cả các giải thuật tìm kiếm, tìm kiếm nhị phân là nhanh nhất, nhưng nó có nhược điểm là dãy phải được sắp xếp. 12 Bài tập về nhà B1. Viết chương trình thực hiện các việc sau: a. Nhập các giá trị nguyên dương từ bàn phím (tổ chức theo kiểu danh sách liên kết). b. In ra màn hình dãy số đã nhập c. Nhập một giá trị X từ bàn phím, kiểm tra X có trong danh sách hay không. Nếu có thì trả về vị trí của X, nếu không chèn X vào vị trí cuối của danh sách.(Viết cả 2 giải thuật Tìm kiếm tuần tự và tìm kiếm nhị phân). 13 4.2. Cây nhị phân tìm kiếm  Việc tổ chức tập hợp khóa theo cấu trúc danh sách thì phép tìm kiếm nói chung là chi phí cao, nếu khóa đã sắp xếp thì phép tìm kiếm nhị phân hiệu quả hơn nhưng bất tiện trong việc thêm, bớt phần tử.  Cấu trúc cây nhị phân tìm kiếm được xây dựng để khắc phục các nhược điểm trên. 14 4.2.1 Định nghĩa Định nghĩa: Cây nhị phân tìm kiếm là cây nhị phân mà tại mỗi nút có một giá trị khóa thuộc kiểu dữ liệu có thứ tự nào đó, đồng thời thỏa mãn điều kiện sau: – Mọi khóa thuộc cây con trái đều nhỏ hơn khóa ở nút cha. – Mọi khóa thuộc cây con phải đều lớn hơn khóa ở nút cha. Theo định nghĩa, bất kỳ cây con nào của cây nhị phân tìm kiếm đều là cây tìm kiếm. 15 4.2.1 Định nghĩa Ví dụ: 34 66 17 25 50 71 68 75 16 4.2.1 Định nghĩa Bài tập tại lớp – Vẽ 4 cây nhị phân tìm kiếm với các giá trị sau: 3, 4, 6, 8, 9, 10, 14, 15, 17. – Vẽ cây nhị phân tìm kiếm cân đối cho các giá trị trên với số nút rỗng là ít nhất. 17 4.2.2 Các phép toán Phép tìm kiếm Phép chèn thêm một nút Phép gỡ loại bỏ một nút 18 4.2.2.1 Phép tìm kiếm Mô tả các bước:  Bắt đầu từ gốc của cây, gọi nút đang xét là V.  Nếu V rỗng, kết thúc và tìm không thấy.  Ngược lại, so sánh x với khóa của nút hiện tại V: – Nếu x< khóa của V, lặp lại bước tìm kiếm với cây con trái; – Nếu x> khóa của V, lặp lại bước tìm kiếm với cây con phải; – Nếu x = khóa của V, kết thúc và tìm thấy 19 4.2.2.1 Phép tìm kiếm Thủ tục đệ quy: int timdequy(int x,NODE *root) { int timthay =0; if ((root ==NULL) || (timthay)) return timthay; else { if (x < root->element) timdequy(x,root->left); else if (x>root->element) timdequy (x,root->right); else timthay =1; } 20
- Xem thêm -

Tài liệu liên quan