Xem mẫu
- TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
om
.c
ng
co
Cấu trúc dữ liệu và giải thuật
an
th
o ng
Nguyễn Khánh Phương
du
u
Computer Science department
cu
School of Information and Communication technology
E-mail: phuongnk@soict.hust.edu.vn
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Nội dung khóa học
Chương 1. Các kiến thức cơ bản
om
Chương 2. Thuật toán đệ quy
.c
ng
Chương 3. Các cấu trúc dữ liệu cơ bản
co
Chương 4. Cây
an
Chương 5. Sắp xếp th
o ng
du
Chương 6. Tìm kiếm
u
cu
Chương 7. Cấu trúc dữ liệu đồ thị
2
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
om
.c
ng
co
Chương 6. Tìm kiếm (Searching)
an
th
o ng
Nguyễn Khánh Phương
du
u
Computer Science department
cu
School of Information and Communication technology
E-mail: phuongnk@soict.hust.edu.vn
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- 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?
om
• Nếu x có mặt trong danh sách A, hãy đưa ra vị trí xuất hiện
.c
của x trong danh sách đã cho, nghĩa là đưa ra chỉ số i sao
ng
co
cho ai = x
an
th
o ng
du
u
cu
4
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- N i dung
1. Tìm kiếm tuần tự
om
2. Tìm kiếm nhị phân
.c
ng
3. Cây nhị phân tìm kiếm
co
4. Cây AVL
an
5. Bảng băm th
o ng
du
u
cu
5
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- N i dung
1. Tìm kiếm tuần tự
om
2. Tìm kiếm nhị phân
.c
ng
3. Cây nhị phân tìm kiếm
co
4. Cây AVL
an
5. Bảng băm th
o ng
du
u
cu
6
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- 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.
om
– Mảng A không cần thiết đã được sắp xếp
.c
• Thuật toán: Bắt đầu từ phần tử đầu tiên, duyệt qua từng phần tử cho
ng
đến khi tìm được x hoặc toàn bộ các phần tử của mảng đã được duyệt
co
hết
an
• Độ phức tạp: O(n)
th
ng
A:
o
-7 9 -5 2 8 3
du
1 2 3 4 5 6
u
cu
Target x = 8:
7
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- 1. Tìm kiếm tuần tự (Linear Search/Sequential search)
void linearSearch(int a[], int size, int target)
{ int i;
om
for (i = 1; i
- 1. Tìm kiếm tuần tự (Linear Search/Sequential search)
void linearSearch(int a[], int size, int target)
{ int i;
om
for (i = 1; i
- 1. Tìm kiếm tuần tự (Linear Search/Sequential search)
void linearSearch(int a[], int size, int target)
{ int i;
om
for (i = 1; i
- 1. Tìm kiếm tuần tự (Linear Search/Sequential search)
void linearSearch(int a[], int size, int target)
{ int i;
om
for (i = 1; i
- 1. Tìm kiếm tuần tự (Linear Search/Sequential search)
void linearSearch(int a[], int size, int target)
{ int i;
om
for (i = 1; i
- 1. Tìm kiếm tuần tự (Linear Search/Sequential search)
void linearSearch(int a[], int size, int target)
{ int i;
om
for (i = 1; i
- 1. Tìm kiếm tuần tự (Linear Search/Sequential search)
void linearSearch(int a[], int size, int target)
{ int i;
om
for (i = 1; i
- 1. Tìm kiếm tuần tự (Linear Search/Sequential search)
void linearSearch(int a[], int size, int target)
{ int i;
om
for (i = 1; i
- 1. Tìm kiếm tuần tự (Linear Search/Sequential search)
void linearSearch(int a[], int size, int target)
{ int i;
om
for (i = 1; i
- 1. Tìm kiếm tuần tự (Linear Search/Sequential search)
void linearSearch(int a[], int size, int target)
{ int i;
om
for (i = 1; i
- 1. Tìm kiếm tuần tự (Linear Search/Sequential search)
void linearSearch(int a[], int size, int target)
{ int i;
om
for (i = 1; i
- 1. Tìm kiếm tuần tự (Linear Search/Sequential search)
void linearSearch(int a[], int size, int target)
{ int i;
om
for (i = 1; i
- 1. Tìm kiếm tuần tự (Linear Search/Sequential search)
void linearSearch(int a[], int size, int target)
{ int i;
om
for (i = 1; i
nguon tai.lieu . vn
