tailieunhanh - 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

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. | 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@ https 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 https 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@ https 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 https 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 https 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 https 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