TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật 1: Chương 2

Bài giảng Cấu trúc dữ liệu và giải thuật 1: Chương 2 trình bày các nội dung chính sau: Tìm kiếm và sắp xếp nội, tìm kiếm tuyến tính, tìm kiếm nhị phân, đổi chỗ trực tiếp, chèn nhị phân, . Mời các bạn cùng tham khảo để nắm nội dung chi tiết. | CHƯƠNG 2 TÌM KIẾM VÀ SẮP XẾP NỘI CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 1 Nội Dung Các giải thuật tìm kiếm nội 1. Tìm kiếm tuyến tính 2. Tìm kiếm nhị phân Các giải thuật sắp xếp nội CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 1. Đổi chỗ trực tiếp Interchange Sort 2. Chọn trực tiếp Selection Sort 3. Nổi bọt Bubble Sort 2 Nội Dung Tt 4. Chèn trực tiếp Insertion Sort 5. Chèn nhị phân Binary Insertion Sort 6. Shaker Sort 7. Shell Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix Sort 3 Bài Toán Tìm Kiếm Cho danh sách có n phần tử a0 a1 a2 an-1. Để đơn giản trong việc trình bày giải thuật ta dùng mảng 1 chiều a để lưu danh sách các phần tử nói trên trong bộ nhớ chính. Tìm phần tử có khoá bằng X trong mảng CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Giải thuật tìm kiếm tuyến tính tìm tuần tự Giải thuật tìm kiếm nhị phân Lưu ý Trong quá trình trình bày thuật giải ta dùng ngôn ngữ lập trình C. 4 Tìm Kiếm Tuyến Tính Ý tưởng So sánh X lần lượt với phần tử thứ 1 thứ 2 của mảng a cho đến khi gặp được khóa cần tìm hoặc tìm hết mảng mà không thấy. Các bước tiến hành Bước 1 Khởi gán i 0 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Bước 2 So sánh a i với giá trị x cần tìm có 2 khả năng a i x tìm thấy x. Dừng a i x sang bước 3 Bước 3 i i 1 Xét tiếp phần tử kế tiếp trong mảng Nếu i N Hết mảng. Dừng Ngược lại Lặp lại bước 2 5 Thuật Toán Tìm Kiếm Tuyến Tính Hàm trả về 1 nếu tìm thấy ngược lại trả về 0 int LinearSearch int a int n int x int i 0 while i Minh Họa Thuật Toán Tìm Kiếm Tuyến Tính X 6 Tìm thấy 6 tại vị trí 4 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 2 8 5 1 6 4 6 0 1 2 3 4 5 6 7 Minh Họa Thuật Toán Tìm Kiếm Tuyến Tính tt X 10 i 7 không tìm thấy i 2 8 5 1 6 4 6 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 0 1 2 3 4 5 6 8 Ðánh Giá Thuật Toán Tìm Tuyến Tính Trường hợp Css Tốt nhất 1 Xấu nhất N CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Trung bình N 1 2 Độ phức tạp O N 9 Cải Tiến Thuật Toán Tìm Tuyến Tính Nhận xét Số phép so sánh của thuật toán trong trường hợp xấu nhất là 2 n. Để giảm thiểu số phép so .

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Giải thuật 1
• Sắp xếp nội
• Tìm kiếm tuyến tính
• Tìm kiếm nhị phân
• Đổi chỗ trực tiếp
• Chèn nhị phân
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp