ĐỒ ÁN: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

Thực hiện một đề án tin học là chuyể bài toán thực tế thành bài toán có thể giải quyết trên máy tính. Một bài toán thực tế bất kỳ đềubao gồm các đối tượng dữ liệu và các yêu cầu xử lý trên các đối tượng đó. Vì thế, để xây dựng mộtmô hiình tin học phản ánh được bài toán thực tế cần chú trọng đến hai vấn đề
Nội dung trích xuất từ tài liệu:
ĐỒ ÁN: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬTĐỒ ÁN: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Mục LụcCHƯƠNG 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU & GT 1 • 1.1. Tầm quan trọng của CTDL & GT trong một đề án tin học2 • 1.1.1. Xây dựng cấu trúc dữ liệu5 • 1.1.2. Xây dựng giải thuật10 • 1.1.3. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật12 • 1.2. Đánh giá Cấu trúc dữ liệu & Giải thuật16 • 1.2.1. Các tiêu chuẩn đánh giá cấu trúc dữ liệu18 • 1.2.2. Đánh giá độ phức tạp của thuật toán22 • 1.3. Kiểu dữ liệu25 • 1.3.1. Khái niệm về kiểu dữ liệu28 • 1.3.2. Các kiểu dữ liệu cơ sở29 • 1.3.3. Các kiểu dữ liệu có cấu trúc30 • 1.3.4. Kiểu dữ liệu con trỏ36 • 1.3.5. Kiểu dữ liệu tập tin39 • Câu hỏi và bài tập40CHƯƠNG 2: KỸ THUẬT TÌM KIẾM (Searching)47 • 2.1. Khái quát về tìm kiếm49 • 2.2. Các giải thuật tìm kiếm nội50 • 2.2.1. Đặt vấn đề52 • 2.2.2. Tìm tuyến tính • 2.2.3. Tìm nhị phân • 2.3. Các giải thuật tìm kiếm ngoại • 2.3.1. Đặt vấn đề • 2.3.2. Tìm tuyến tính • 2.3.3. Tìm kiếm theo chỉ mục • Câu hỏi và bài tậpCHƯƠNG 3: KỸ THUẬT SẮP XẾP (SORTING) • 3.1. Khái quát về sắp xếp • 3.2. Các giải thuật sắp xếp nội • 3.2.1 Sắp xếp bằng phương pháp đổi chỗ • 3.2.2. Sắp xếp bằng phương pháp chọn • 3.2.3. Sắp xếp bằng phương pháp chèn • 3.2.4. Sắp xếp bằng phương pháp trộn • 3.3. Các giải thuật sắp xếp ngoại • 3.3.1. Sắp xếp bằng phương pháp trộn • 3.3.2. Sắp xếp theo chỉ mục • Câu hỏi và bài tậpCHƯƠNG 4: DANH SÁCH (LIST) • 4.1. Khái niệm về danh sách • 4.2. Các phép toán trên danh sách • 4.3. Danh sách đặc • 4.3.1. Định nghĩa • 4.3.2. Biểu diễn danh sách đặc • 4.3.3. Các thao tác trên danh sách đặc • 4.3.4. Ưu nhược điểm và Ứng dụng • 4.4. Danh sách liên kết • 4.4.1. Định nghĩa • 4.4.2. Danh sách liên kết đơn • 4.4.3. Danh sách liên kết kép • 4.4.4. Ưu nhược điểm của danh sách liên kết • 4.5. Danh sách hạn chế • 4.5.1. Hàng đợi • 4.5.2. Ngăn xếp • 4.5.3. Ứng dụng của danh sách hạn chế • Câu hỏi và bài tậpCHƯƠNG 5: CÂY (TREE) • 5.1. Khái niệm – Biểu diễn cây • 5.1.1. Định nghĩa cây • 5.1.2. Một số khái niệm liên quan • 5.1.3. Biểu diễn cây • 5.2. Cây nhị phân • 5.2.1. Định nghĩa • 5.2.2. Biểu diễn và Các thao tác • 5.2.3. Cây nhị phân tìm kiếm • 5.3. Cây cân bằng • 5.3.1. Định nghĩa – Cấu trúc dữ liệu • 5.3.2. Các thao tác • Câu hỏi và bài tập chương 1 TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Mục tiêu Giới thiệu vai trò của việc tổ chức dữ liệu trong một đề án tin học Mối quan hệ giữa giải thuật và cấu trúc dữ liệu Các yêu cầu tổ chức dữ liệu Khái niệm kiểu dữ liệu_cấu trúc dữ liệu Tổng quan về đánh giá độ phức tạp giải thuật1.1.VAI TRÒ CỦA CẤU TRÚC DỮ LIỆU TRONG MỘT ĐỀ ÁN TIN HỌC • Thực hiện một đề án tin học là chuyể bài toán thực tế thành bài toán có thể giảiquyết trên máy tính. Một bài toán thực tế bất kỳ đềubao gồm các đối tượng dữ liệu vàcác yêu cầu xử lý trên các đối tượng đó. Vì thế, để xây dựng mộtmô hiình tin học phảnánh được bài toán thực tế cần chú trọng đến hai vấn đề:Tổ chức biểu diễn các đối tượng thực tế Các thành phần dữ liệu thực tế đa dạng, phong phú và thường chứa đựng nhữngquan hệ nào đó với nhau, do đó trong mô hình tin học của bài toán, cần phải tổ chức,xây dựng các cấu trúc dữ liệu thích hợp nhất sao cho vừa có thể phản ánh chính xác cácdữ liệu thực tế này, vừa có thể dễ dàng dùng máy tính để xử lý. Công việc này gọi làxây dựng cấu trúc dữ liệu cho bài toán.Xây dựng các thao tác xử lý dữ liệu Từ những yêu cầu xử lý trong thực tế, cần tìm ra các giải thuật tương ứng để xácđịnh trình tự các thao tác máy tính phải thi hành để cho ra kết quả mong muốn, đây làbước xây dựng giải thuật cho bài toán. • Tuy nhiênkhi giải quyết một bài toán trên máy tính, chúng ta thường có khuynhhướng chỉ chú trọng đến việc xây dựng giải thuật mà quyên đi tầm quan trọng của việctổ chức dữ liệu trong bài toán. Giải thuật phản ánh các phép xử lý, còn đối tượng xử lýcủa giải thuật lại là dữ liệu. Chính dữ liệu chứa đựng các thông tin cần thiết để thựchiện giải thuật. Để xác định được giải thuật phù hợp cần ta cần phải biết nó tác độngđến loại dữ liệu nào và khi lựa chọn cấu trúc dữ liệu cũng cần phải hiểu rõ những thaotác nào tác động lên dữ liệu đó. Như vậy trong một đề án tin học, cấu trúc dữ liệu vàgiải thuật có mối quan hệ chặt chẽ với nhau, được thể hiện qua công thức Cấu trúc dữ liệu + Giải thuật = Chương trình • Với một cấu trúc dữ liệu đã chọn, sẽ có những giải thuật tương ứng, phù hợp. Khicấu trúc dữ liệu thay đổi thường giải thuật cũng phải thay đổi theo để tránh việc xử lýgượng ép, thiếu tự nhiên trên một cấu trúc không phù hợp. Hơn nữa, một cấu trúc dữliệu tốt sẽ giúp giải thuật xử lý trên đó có thể phát huy tác dụng tốt hơn, vừa nhanh vừatiết kiêm vật tư, giải thuật cũng đơn giản và dễ hiểu hơn. Ví dụ 1: Một chương trình quản lý điểm thi của sinhviên cần lưu các điểm số của 3sinh viên. Do mỗi sinh viên có 4 điểm số tương ứng với 4 môn học khác nhaunên dữliệu có dạng như sau: Sinh viên Môn 1 Môn 2 Môn 3 Môn 4 SV1 7 9 7 5 SV2 5 4 2 7 SV3 8 9 6 7 Chỉ xét thao tác xư lý là xuất điểm số các môn của từng sinhviên. Giả sử có các phương án tổ chức lưu trữ như sau: Phương án 1: Sử dụng mảng một chiều có tất cả 3(SV) * 4(Môn) = 12 điểm số cần lưu trữ, do đó ta khai báo mảng như sau: Type mang = array[1..12] of integer; var a: mang Khi đó mảng a các phần tử sẽ được lưu trữ như ...