Bài giảng môn Cấu trúc dữ liệu - Chương 2: Kỹ thuật tìm kiếm (searching)
Tìm kiếm theo chỉ mục (tt) Phân tích Thuật toán:
• Trường hợp tốt nhất (phần tử đầu tiên trong tập tin chỉ
mục có giá trị = X)
• Số phép gán Gmin = 1
• Số phép so sánh Smin = 2 + 1
• Số lần đọc tập tin Dmin = 1
• Trường hợp xấu nhất (không có phần tử nào trong tập tin
chỉ mục có giá trị = X)
• Số phép gán Gmax = 1
• Số phép so sánh Smax = 2N +1
• Số lần đọc tập tin Dmax = N
• Trung bình
• Số phép gán Gavg = ½(N +5)
• Số phép so sánh Savg = (3 + 2N + 1)/2
• Số lần đọc tập tin Davg = ½(N + 1)
Bạn đang xem trước 20 trang tài liệu Bài giảng môn Cấu trúc dữ liệu - Chương 2: Kỹ thuật tìm kiếm (searching), để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
19
Chương 2:
KỸ THUẬT TÌM KIẾM
(SEARCHING)
20
NỘI DUNG CHƯƠNG 2
2.1. Khái quát về tìm kiếm
2.2. Các giải thuật tìm kiếm nội (Tìm kiếm trên mảng)
• Tìm tuyến tính (Linear Search)
• Tìm nhị phân (Binary Search)
2.3. Các giải thuật tìm kiếm ngoại (Tìm kiếm trên tập
tin)
• Tìm tuyến tính (F Linear Search)
• Tìm nhị phân (Binary Search)
21
2.1. Khái quát về tìm kiếm
• Trong các hệ lưu trữ và quản lý dữ liệu, thao tác tìm kiếm được
thực hiện nhiều nhất để khai thác thông tin một các dễ dàng.
• Số lượng thông tin trong một hệ thống thông tin là đáng kể nên
việc xây dựng các giải thuật tìm kiếm nhanh sẽ có ý nghĩa quan
trọng.
• Nếu tìm kiếm trong một hệ thống đã tổ chức thì việc tìm kiếm dễ
dàng hơn.
• Các giải thuật tìm kiếm được xây dựng nhằm mục tiêu hỗ trợ
ứng dụng có hiệu quả hơn.
• Các giải thuật phụ thuộc vào vào cấu trúc dữ liệu mà nó tác
động đến. Dữ liệu được lưu trữ trên bộ nhớ chính và bộ nhớ
phụ.
22
2.1. Khái quát về tìm kiếm
• Giả sử mỗi phần tử được xem xét có một thành phần khóa
(Key) để nhận diện có kiểu dữ liệu T, các thành phần còn lại
là thông tin (Info), như vậy mỗi phần tử có cấu trúc như sau:
typedef struct DataElement
{
T Key;
InfoData Info;
} DataType;
• Để đơn giản, quan tâm thành phần dữ liệu chỉ là khóa nhận
diện
23
2.2. Các giải thuật tìm kiếm nội
Bài toán đặt ra: Giả sử có một mảng M gồm N phần tử.
Cần xác định có hay không phần tử có giá trị bằng X
trong mảng M?? Nếu có phần tử X thì phần tử bằng phần
tử X là phần tử thứ mấy trong mảng X?
Các giải thuật tìm kiếm nội đưa ra 2 cách tìm kiếm
• Tìm kiếm tuần tự hay (Sequential Search) còn gọi tìm
kiếm tuyến tính (Linear Search)
• Tìm kiếm nhị phân (Binary Search)
24
2.2. Các giải thuật tìm kiếm nội
Tìm tuyến tính (Linear Seach)
Ý tưởng:
So sánh lần lượt các phần tử của mảng M với giá trị X
cần tìm bắt đầu từ phần tử đầu tiên cho đến khi tìm ra
phần tử có giá trị X hoặc đã duyệt hết tất cả các phần tử
của mảng M thì kết thúc.
Thuật toán
B1: k = 1
B2: Nếu M[k] X và k<=N
Thì k++
Ngược lại: Lặp lại B2
B3: Nếu k <= N Thì Tìm thấy phần tử có giá trịX ở vị trí k
B4: Nếu không (k<=N): Thì không tìm thấy phần tử có giá
trị X
B5: Kết thúc
25
2.2. Các giải thuật tìm kiếm nội
Tìm tuyến tính (tt)
Cài đặt thuật toán:
int LinearSearch (T M[], int N, T X)
{
int k = 0;
while (M[k] != X && k <N) // phần tử mảng M tính từ 0
k++;
if (k < N)
return (k);
return (-1);
}
26
2.2. Các giải thuật tìm kiếm nội
Tìm tuyến tính (tt)
Phân tích, đánh giá thuật toán:
• Trường hợp tốt nhất (phần tử đầu tiên của mảng có giá trị
= X)
• Số phép gán Gmin = 1
• Số phép so sánh Smin = 3
• Trường hợp xấu nhất (không có phần tử nào của mảng
có giá trị = X)
• Số phép gán Gmax = 1
• Số phép so sánh Smax = 2N + 1
• Trung bình
• Số phép gán Gavg = 1
• Số phép so sánh Savg = N + 2
27
2.2. Các giải thuật tìm kiếm nội
Tìm tuyến tính (tt)
Cải tiến thuật toán:
• Mỗi bước lặp với thuật toán trên cần thực hiện 2 phép so
sánh ý tưởng giảm bớt phép so sánh bằng cách thêm
vào mảng một phần tử cầm canh (sentinel/stand by) có
giá trị bằng X để nhận diện ra sự hết mảng khi duyệt.
B1: k = 1
B2: M[N+1] = X
B3: Nếu M[k] X
Thì k++
Ngược lại: Lặp lại B3
B4: Nếu k < N Thì Tìm thấy phần tử có giá trịX ở vị trí k
B5: Nguợc lại: Thì không tìm thấy phần tử có giá trị X
B6: Kết thúc
28
2.2. Các giải thuật tìm kiếm nội
Tìm tuyến tính (tt)
Cài đặt thuật toán cải tiến:
int LinearSearchCaiTien (T M[], int N, T X)
{
int k = 0;
M[N] = X; // phần tử mảng M tính từ 0
while (M[k] != X)
k++;
if (k < N)
return (k);
return (-1);
}
29
2.2 Các giải thuật tìm kiếm nội (tt)
Tìm tuyến tính (tt)
Phân tích, đánh giá thuật toán cải tiến:
• Trường hợp tốt nhất (phần tử đầu tiên của mảng có giá trị
= X)
• Số phép gán Gmin = 2
• Số phép so sánh Smin = 2
• Trường hợp xấu nhất (không có phần tử nào của mảng
có giá trị = X)
• Số phép gán Gmax = 2
• Số phép so sánh Smax = (N + 1) + 1
• Trung bình
• Số phép gán Gavg = 2
• Số phép so sánh Savg = N/2 + 2
30
2.2. Các giải thuật tìm kiếm nội
Ví dụ: Tìm tuyến tính
31
2.2. Các giải thuật tìm kiếm nội
Tìm nhị phân (Binary Seach)
Tìm nhị phân đơn giản và thuận tiện trong trường hợp số phần tử
của chuỗi lớn có thứ tự (tăng hay giảm dần) có nghĩa là phần tử
trước nhỏ (lớn) hơn phần tử sau.
Nếu trường hợp X nhỏ hơn phần tử đứng giữa thì X chỉ có thể tìm
trong nửa đầu của dãy, ngược lại tìm trong nửa sau của dãy.
Ý tưởng:
• Phạm vi tìm kiếm là từ phần tử đầu tiên của dãy (First = 1) cho
đến phần tử cuối cùng (Last = N)
• So sánh giá trị X với giá trị phần tử ở giữa của dãy M là M[Mid]
• Nếu X = M[Mid] Tìm thấy
• Nếu X < M[Mid] rút ngắn phạm vi tìm kiếm và Last = Mid –1
• Nếu X > M[Mid] rút ngắn phạm vi tìm kiếm và First = Mid +1
• Lặp lại quá trình cho đến khi tìm thấy phần tử có giá trị = X
32
2.2. Các giải thuật tìm kiếm nội
Tìm nhị phân (tt)
Thuật toán đệ quy (Recursion Algorithm)
B1: First = 1
B2: Last = N
B3: Nếu (First > Last) // hết phạm vi tìm kiếm
Không tìm thấy
Ngược lại: Thực hiện B8
B4: Mid = (First + Last )/2
B5: Nếu (X = M[Mid])
Tìm thấy tại vị trí Mid
Ngược lại: Thực hiện B6
B6: Nếu (X<M[Mid]) Tìm đệ quy từ First đến Last = Mid -1
B7: Nếu (X>M[Mid]) Tìm đệ quy từ First = Mid +1 đến Last
B8: Kết thúc
33
2.2. Các giải thuật tìm kiếm nội
Tìm nhị phân (tt)
Cài đặt Thuật toán đệ quy (Recursion Algorithm)
int RecursiveBinarySearch (T M[], int First, int Last, T X)
{ if (First > Last) return (-1);
int Mid = (First + Last)/2;
if (X == M[Mid])
return Mid;
if (X < M[Mid])
return RecursiveBinarySearch (M, First, Mid -1,X);
else
return RecursiveBinarySearch (M, Mid +1, Last,X);
};
int BinarySearch (T M[], int N, T X) {
return RecursiveBinarySearch (M, 0, N-1,X);
}
34
2.2. Các giải thuật tìm kiếm nội
Tìm nhị phân (tt)
Phân tích, đánh giá thuật toán đệ quy:
• Trường hợp tốt nhất (phần tử đầu tiên của mảng có giá trị
= X)
• Số phép gán Gmin = 1
• Số phép so sánh Smin = 2
• Trường hợp xấu nhất (không có phần tử nào của mảng
có giá trị = X)
• Số phép gán Gmax = log2N +1
• Số phép so sánh Smax =3log2N +1
• Trung bình
• Số phép gán Gavg = 1/2log2N +1
• Số phép so sánh Savg = ½(3log2N + 3)
35
2.2. Các giải thuật tìm kiếm nội
Tìm nhị phân (tt)
Thuật toán không đệ quy (Non-Recursion Algorithm)
B1: First = 1
B2: Last = N
B3: Nếu (First > Last) // hết phạm vi tìm kiếm
Không tìm thấy
Ngược lại: Thực hiện B8
B4: Mid = (First + Last )/2
B5: Nếu (X = M[Mid])
Tìm thấy tại vị trí Mid
Ngược lại: Thực hiện B6
B6: Nếu (X<M[Mid])
Last = Mid –1 và Lặp lại B3
B7: Nếu (X>M[Mid]) First = Mid + 1 và lặp lại B3
B8: Kết thúc
36
2.2. Các giải thuật tìm kiếm nội
Tìm nhị phân (tt)
Cài đặt Thuật toán không đệ quy (Non-Recursion Algorithm)
int NRBinarySearch (T M[], int N, T X)
{ int First = 0;
int Last = N-1;
while (First <= Last)
{ int Mid = (First + Last)/2;
if (X == M[Mid]) return Mid;
if (X < M[Mid])
Last = Mid –1 ;
else
First = Mid + 1;
}
return (-1);
}
37
2.2. Các giải thuật tìm kiếm nội
Tìm nhị phân (tt)
Phân tích, đánh giá thuật toán không đệ quy:
• Trường hợp tốt nhất (phần tử đầu tiên của mảng có giá trị
= X)
• Số phép gán Gmin = 3
• Số phép so sánh Smin = 2
• Trường hợp xấu nhất (không có phần tử nào của mảng
có giá trị = X)
• Số phép gán Gmax = 2log2N +4
• Số phép so sánh Smax =3log2N +1
• Trung bình
• Số phép gán Gavg = log2N +3.5
• Số phép so sánh Savg = ½(3log2N + 3)
38
2.3. Các giải thuật tìm kiếm ngoại
• Các giải thuật tìm kiếm ngoại là giải thuật tìm kiếm trên
tập tin lưu trữ trên đĩa.
• Giả sử có tập tin F lưu trữ N phần tử. Tìm xem có hay
không phần tử có giá trị X được lưu trong F. Nếu có phần
tử có giá trị X nằm ở vị trí nào trong tập tin F?
• Xét 2 giải thuật tìm kiếm ngoại:
• Tìm tuyến tính
• Tìm kiếm theo chỉ mục (Index Search)
39
2.3. Các giải thuật tìm kiếm ngoại
Tìm tuyến tính Với Ý tưởng: Lần lượt đọc các phần trong
tập tin X và so sánh với giá trị X
Thuật toán:
B1: k = 0
B2: Trở về đầu tập tin (rewind(F))
B3: Đọc 1 phần tử trong tập tin (read(F, a))
B4: k = k + sizeof(T)
B5: Kiểm tra Nếu a ≠ X và chưa hết tập tin (!eof(F))
Lặp lại B3
B6: IF Nếu a = X
Tìm thấy phần tử có giá trị X tại vị trí k bytes tính từ
đầu F
B7: ELSE
Không tìm thấy phần tử có giá trị X trong tập tin F
B8: Kết thúc
40
2.3. Các giải thuật tìm kiếm ngoại
Tìm tuyến tính (tt) Cài đặt Thuật toán:
long FLinearSearch (char * FileName, T X)
{ FILE * Fp;
Fp = fopen(FileName, “rb”);
if (Fp == NULL) return (-1);
long k = 0; T a; int SOT = sizeof(T);
while (!feof(Fp)) { if (fread(&a, SOT, 1, Fp) == 0) break;
k = k+ SOT;
if (a == X) break;
}
fclose (Fp);
if (a == X) return (k - SOT);
return (-1);
}
41
2.3. Các giải thuật tìm kiếm ngoại
Tìm tuyến tính (tt) Phân tích Thuật toán:
• Trường hợp tốt nhất (phần tử đầu tiên trong tập tin có giá trị = X)
• Số phép gán Gmin = 2 + 1
• Số phép so sánh Smin = 2 + 1
• Số lần đọc tập tin Dmin = 1
• Trường hợp xấu nhất (không có phần tử nào trong tập tin có giá
trị = X)
• Số phép gán Gmax = 2N + 2
• Số phép so sánh Smax = 2N +1
• Số lần đọc tập tin Dmax = N
• Trung bình
• Số phép gán Gavg = ½(N +5)
• Số phép so sánh Savg = ½(N + 1)
• Số lần đọc tập tin Davg = ½(N + 1)
42
2.3. Các giải thuật tìm kiếm ngoại
Tìm kiếm theo chỉ mục (Index Search)
• Vì lý do kích thước tập tin có thể lớn (có thể do các phần tử
chứa trong tập tin lớn) Thao tác đọc tập tin trên dữ liệu là
lâu & không bảo đảm an toàn dữ liệu.
• Để giúp an toàn dữ liệu, một tập tin thường được đi kèm
theo tập tin chỉ mục (Index File) làm nhiệm vụ điều khiển
thứ tự truy xuất dữ liệu trên tập tin theo một khóa chỉ mục
(Index Key).
• Tập tin chỉ mục sẽ chứa các phần tử gồm 2 thành phần
tương ứng với cấu trúc DL:
typedef struct IdxElement
{
T IdxKey;
long Pos;
} IdxType
• Tập tin chỉ mục luôn sắp xếp theo vị trí tăng của khóa chỉ
mục.
43
2.3. Các giải thuật tìm kiếm ngoại
Tìm kiếm theo chỉ mục (tt)
Ý tưởng
Đọc từ đầu tập tin chỉ mục, so sánh phần tử khóa chỉ mục
với giá trị X cho đến khi đọc đến phần tử có khóa chỉ mục
>= giá trị X hay đọc đến cuối tập tin.
Nếu trong quá trình trên tìm kiếm được phần tử có giá trị =
X, truy xuất tập tin F tại vị trí này để đọc dữ liệu, tránh mất
thời gian.
44
2.3. Các giải thuật tìm kiếm ngoại
Tìm kiếm theo chỉ mục (tt)
Thuật toán
B1: Trở về đầu tập tin chỉ mục IDX(rewind(IDX))
B2: Đọc 1 phần tử trong tập tin (read(IDX, ai))
B3: Kiểm tra Nếu ai.IdxKey < X và chưa hết tập tin
(!eof(IDX))
Lặp lại B3
B4: IF Nếu ai.IdxKey = X
Tìm thấy phần tử có giá trị X tại vị trí ai.Pos bytes
tính từ đầu IDX
B5: ELSE
Không tìm thấy phần tử có giá trị X trong tập tin IDX
B6: Kết thúc
45
2.3. Các giải thuật tìm kiếm ngoại
Tìm kiếm theo chỉ mục (tt)
Cài đặt Thuật toán:
long IndexSearch (char * IdxFileName, T X)
{ FILE * IDXFp;
IDXFp = fopen(IdxFileName, “rb”);
if (IDXFp == NULL) return (-1);
IdxType ai; int SOIE = sizeof(IdxType);
while (!feof(IDXFp)) { if (fread(&ai, SOIE, 1, IDXFp) ==
0) break;
if (ai >= X) break;
}
fclose (IDXFp);
if (ai.IdxKey == X) return (ai.Pos);
return (-1);
}
46
2.3. Các giải thuật tìm kiếm ngoại
Tìm kiếm theo chỉ mục (tt) Phân tích Thuật toán:
• Trường hợp tốt nhất (phần tử đầu tiên trong tập tin chỉ
mục có giá trị = X)
• Số phép gán Gmin = 1
• Số phép so sánh Smin = 2 + 1
• Số lần đọc tập tin Dmin = 1
• Trường hợp xấu nhất (không có phần tử nào trong tập tin
chỉ mục có giá trị = X)
• Số phép gán Gmax = 1
• Số phép so sánh Smax = 2N +1
• Số lần đọc tập tin Dmax = N
• Trung bình
• Số phép gán Gavg = ½(N +5)
• Số phép so sánh Savg = (3 + 2N + 1)/2
• Số lần đọc tập tin Davg = ½(N + 1)
47
Bài tập
• Cài đặt các thuật toán trong lý thuyết
• Bài tập trong giáo trình chương 2
• Bài tập thực hành tuần 2, 3
Các file đính kèm theo tài liệu này:
- cau_truc_du_lieu_c2_4115.pdf