intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:186

Thêm vào BST
Báo xấu
52
lượt xem 22
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 6 - Tìm kiếm. Trong chương này, người học có thể hiểu được một số kiến thức cơ bản về: Tìm kiếm tuần tự, tìm kiếm nhị phân, cây nhị phân tìm kiếm, Cây AVL, bảng băm. Mời các bạn cùng tham khảo để biết thêm các nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 6 - Nguyễn Khánh Phương

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2