Cấu trúc dữ liệu và thuật giải

Để giải một bài toán trong thực tế bằng máy tính ta phải bắt đầu từ việc xác định bàitoán. Nhiều thời gian và công sức bỏ ra để xác định bài toán cần giải quyết, tức là phảitrả lời rõ ràng câu hỏi "phải làm gì?" sau đó là "làm như thế nào?". Thông thường, khikhởi đầu,
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và thuật giải Cấu trúc dữ liệu và thuật giải 1 TRƯỜNG ĐẠI HỌC ĐÀ LẠT KHOA CÔNG NGHỆ THÔNG TIN NGUYỄN THỊ THANH BÌNH TRẦN TUẤN MINH BÀI GIẢNG TÓM TẮTCẤU TRÚC DỮ LIỆU VÀ THUẬT GIẢI 1 Dành cho sinh viên ngành công nghệ thông tin (Lưu hành nội bộ) Đà Lạt 2008 1 Cấu trúc dữ liệu và thuật giải 1 MỤC LỤCMỤC LỤCLỜI NÓI ĐẦUCHƯƠNG 1:GIỚI THIỆU CẤU TRÚC DỮ LIỆU VÀ PHÂN TÍCH THUẬT GIẢI ......5 1.1 Từ bài toán đến chương trình .................................................................................. 5 1.1.1 Mô hình hóa bài toán thực tế ........................................................................... 5 1.1.2 Thuật giải (algorithms) .................................................................................... 8 1.2 Kiểu dữ liệu trừu tượng (Abstract Data Type - ADT) .......................................... 13 1.2.1 Khái niệm trừu tượng hóa .............................................................................. 13 1.2.2 Trừu tượng hóa chương trình ......................................................................... 13 1.2.3 Trừu tượng hóa dữ liệu .................................................................................. 14 1.2.4 Kiểu dữ liệu, cấu trúc dữ liệu và kiểu dữ liệu trừu tượng (Data Types, Data Structures, Abstract Data Types) .................................................................................. 15 1.3 PHÂN TÍCH THUẬT GIẢI.................................................................................. 16 1.3.1 Thuật giải và các vấn đề liên quan................................................................. 16 1.3.2 Tính hiệu quả của thuật giải........................................................................... 17 1.3.3 Ký hiệu O và biểu diễn thời gian chạy bởi ký hiệu O ................................... 20 1.3.4 Đánh giá thời gian chạy của thuật giải .......................................................... 24CHƯƠNG 2: TÌM KIẾM VÀ SẮP XẾP TRONG ............................................................33 2.1 Các phương pháp tìm kiếm trong .......................................................................... 33 2.1.1 Phương pháp tìm kiếm tuyến tính .................................................................. 33 2.1.2 Tìm kiếm nhị phân ......................................................................................... 35 2.2 Các phương pháp sắp xếp trong ............................................................................ 37 2.2.1 Thuật giải sắp xếp chọn (Selection Sort) ....................................................... 38 2.2.2 Thuật giải sắp xếp chèn (Insertion Sort) ........................................................ 41 2.2.3 Thuật giải sắp xếp đổi chỗ trực tiếp (Interchange Sort) ................................ 44 2.2.4 Thuật giải sắp xếp nổi bọt (Bubble Sort) ....................................................... 46 2.2.5 Thuật giải shaker (Shaker Sort) ..................................................................... 48 2.2.6 Thuật giải Shell (Shell Sort) .......................................................................... 49 2.2.7 Thuật giải vun đống (Heap Sort) ................................................................... 51 2.2.8 Thuật giải sắp xếp nhanh (Quick Sort) .......................................................... 55 2.2.9 Thuật giải sắp xếp trộn (Merge Sort) ............................................................. 59 2.2.10 Phương pháp sắp xếp theo cơ số (Radix Sort) ............................................... 64CHƯƠNG 3: CẤU TRÚC DANH SÁCH LIÊN KẾT ......................................................72 3.1 Giới thiệu đối tượng dữ liệu con trỏ ...................................................................... 72 3.1.1 Cấu trúc dữ liệu tĩnh và cấu trúc dữ liệu động............................................... 72 3.1.2 Kiểu con trỏ ................................................................................................... 72 3.2 Danh sách liên kết ................................................................................................. 75 3.2.1 Định nghĩa...................................................................................................... 75 2 ...