›
›

Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 6: Tìm kiếm - Nguyễn Khánh Phương

Download
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI  
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG  
Cấu trúc dữ liệu và giải thuật  
Nguyễn Khánh Phương  
Computer Science department  
School of Information and Communication technology  
E-mail: [email protected].vn  
Nội dung khóa học  
Chương 1. Các kiến thức cơ bản  
Chương 2. Thuật toán đệ quy  
Chương 3. Các cấu trúc dữ liệu cơ bản  
Chương 4. Cây  
Chương 5. Sắp xếp  
Chương 6. Tìm kiếm  
Chương 7. Cấu trúc dữ liệu đồ thị  
2
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI  
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG  
Chương 6. Tìm kiếm (Searching)  
Nguyễn Khánh Phương  
Computer Science department  
School of Information and Communication technology  
E-mail: [email protected].vn  
Bài toán tìm kiếm (Searching problem)  
Cho danh sách A gồm n phần tử a1, a2, .., an và 1 số x.  
Câu hỏi: x có mặt trong danh sách A hay không?  
• Nếu x có mặt trong danh sách A, hãy đưa ra vị trí xuất hiện  
của x trong danh sách đã cho, nghĩa là đưa ra chỉ số i sao  
cho ai = x  
4
N i dung  
1. Tìm kiếm tuần tự  
2. Tìm kiếm nhị phân  
3. Cây nhị phân tìm kiếm  
4. Cây AVL  
5. Bảng băm  
5
N i dung  
1. Tìm kiếm tuần tự  
2. Tìm kiếm nhị phân  
3. Cây nhị phân tìm kiếm  
4. Cây AVL  
5. Bảng băm  
6
1. Tìm kiếm tuần tự (Linear Search/Sequential search)  
• Đầu vào:  
– Cho mảng A gồm n phần tử và giá trị tìm kiếm x.  
– Mảng A không cần thiết đã được sắp xếp  
• Thuật toán: Bắt đầu từ phần tử đầu tiên, duyệt qua từng phần tử cho  
đến khi tìm được x hoặc toàn bộ các phần tử của mảng đã được duyệt  
hết  
• Độ phức tạp: O(n)  
-7 9 -5 2 8 3  
A:  
1 2 3 4 5 6  
Target x = 8:  
7
1. Tìm kiếm tuần tự (Linear Search/Sequential search)  
void linearSearch(int a[], int size, int target)  
{ int i;  
for (i = 1; i <= size; i++)  
if (a[i] == target) break;  
if (i <= size)  
printf(“The target is in the list @ index = %d”,i);  
else  
printf(“The target is NOT in the list”);  
}
i=1  
Array A  
9 -5 2 8 3  
1 2 3 4 5 6 = size  
target =
1. Tìm kiếm tuần tự (Linear Search/Sequential search)  
void linearSearch(int a[], int size, int target)  
{ int i;  
for (i = 1; i <= size; i++)  
if (a[i] == target) break;  
if (i <= size)  
printf(“The target is in the list @ index = %d”,i);  
else  
printf(“The target is NOT in the list”);  
}
i=2  
Array A  
-7 -5 2 8 3  
1 2 3 4 5 6 = size  
target =
1. Tìm kiếm tuần tự (Linear Search/Sequential search)  
void linearSearch(int a[], int size, int target)  
{ int i;  
for (i = 1; i <= size; i++)  
if (a[i] == target) break;  
if (i <= size)  
printf(“The target is in the list @ index = %d”,i);  
else  
printf(“The target is NOT in the list”);  
}
i=3  
Array A  
-7 9 2 8 3  
1 2 3 4 5 6 = size  
target =
1. Tìm kiếm tuần tự (Linear Search/Sequential search)  
void linearSearch(int a[], int size, int target)  
{ int i;  
for (i = 1; i <= size; i++)  
if (a[i] == target) break;  
if (i <= size)  
printf(“The target is in the list @ index = %d”,i);  
else  
printf(“The target is NOT in the list”);  
}
i=4  
Array A  
-7 9 -5 8 3  
1 2 3 4 5 6 = size  
target =
1. Tìm kiếm tuần tự (Linear Search/Sequential search)  
void linearSearch(int a[], int size, int target)  
{ int i;  
for (i = 1; i <= size; i++)  
if (a[i] == target) break;  
if (i <= size)  
printf(“The target is in the list @ index = %d”,i);  
else  
printf(“The target is NOT in the list”);  
}
i=5  
Array A  
-7 9 -5 2 3  
1 2 3 4 5 6 = size  
target =
1. Tìm kiếm tuần tự (Linear Search/Sequential search)  
void linearSearch(int a[], int size, int target)  
{ int i;  
for (i = 1; i <= size; i++)  
if (a[i] == target) break;  
if (i <= size)  
printf(“The target is in the list @ index = %d”,i);  
else  
printf(“The target is NOT in the list”);  
}
i=5  
Array A  
-7 9 -5 2 3  
1 2 3 4 5 6 = size  
target =
The target is in the list @ index = 5  
1. Tìm kiếm tuần tự (Linear Search/Sequential search)  
void linearSearch(int a[], int size, int target)  
{ int i;  
for (i = 1; i <= size; i++)  
if (a[i] == target) break;  
if (i <= size)  
printf(“The target is in the list @ index = %d”,i);  
else  
printf(“The target is NOT in the list”);  
}
i=1  
Array A  
9 -5 2 8 3  
1 2 3 4 5 6 = size  
target =
1. Tìm kiếm tuần tự (Linear Search/Sequential search)  
void linearSearch(int a[], int size, int target)  
{ int i;  
for (i = 1; i <= size; i++)  
if (a[i] == target) break;  
if (i <= size)  
printf(“The target is in the list @ index = %d”,i);  
else  
printf(“The target is NOT in the list”);  
}
i=2  
Array A  
-7 -5 2 8 3  
1 2 3 4 5 6 = size  
target =
1. Tìm kiếm tuần tự (Linear Search/Sequential search)  
void linearSearch(int a[], int size, int target)  
{ int i;  
for (i = 1; i <= size; i++)  
if (a[i] == target) break;  
if (i <= size)  
printf(“The target is in the list @ index = %d”,i);  
else  
printf(“The target is NOT in the list”);  
}
i=3  
Array A  
-7 9 2 8 3  
1 2 3 4 5 6 = size  
target =
1. Tìm kiếm tuần tự (Linear Search/Sequential search)  
void linearSearch(int a[], int size, int target)  
{ int i;  
for (i = 1; i <= size; i++)  
if (a[i] == target) break;  
if (i <= size)  
printf(“The target is in the list @ index = %d”,i);  
else  
printf(“The target is NOT in the list”);  
}
i=4  
Array A  
-7 9 -5 8 3  
1 2 3 4 5 6 = size  
target =
1. Tìm kiếm tuần tự (Linear Search/Sequential search)  
void linearSearch(int a[], int size, int target)  
{ int i;  
for (i = 1; i <= size; i++)  
if (a[i] == target) break;  
if (i <= size)  
printf(“The target is in the list @ index = %d”,i);  
else  
printf(“The target is NOT in the list”);  
}
i=5  
Array A  
-7 9 -5 2 3  
1 2 3 4 5 6 = size  
target =
1. Tìm kiếm tuần tự (Linear Search/Sequential search)  
void linearSearch(int a[], int size, int target)  
{ int i;  
for (i = 1; i <= size; i++)  
if (a[i] == target) break;  
if (i <= size)  
printf(“The target is in the list @ index = %d”,i);  
else  
printf(“The target is NOT in the list”);  
}
i=6  
Array A  
-7 9 -5 2 8
1 2 3 4 5 6 = size  
target =
1. Tìm kiếm tuần tự (Linear Search/Sequential search)  
void linearSearch(int a[], int size, int target)  
{ int i;  
for (i = 1; i <= size; i++)  
if (a[i] == target) break;  
if (i <= size)  
printf(“The target is in the list @ index = %d”,i);  
else  
printf(“The target is NOT in the list”);  
}
i=7  
Array A  
-7 9 -5 2 8 3  
1 2 3 4 5 6 = size  
target =
The target is NOT in the list  
Tải về để xem bản đầy đủ
pdf 186 trang yennguyen 19440 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 6: Tìm kiếm - Nguyễn Khánh Phương", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_cau_truc_du_lieu_va_thuat_toan_chuong_6_tim_kiem_n.pdf