Chuong4 tim kiem

  • 40 trang
  • file .pdf
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 x phép tìm kiếm sẽ được thực hiện tiếp với kl, ..ki-1,
nếu x>ki, 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 else 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 l then loc=0// loc chứa chỉ số tương ứng của
//khóa cần tìm
else m = (l+r)/2;
if x then loc = RBINARY-SEARCH(l,m-1,k,x)
else if x>k[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
17 66
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