Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (2016)

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan về giải thuật và cấu trúc dữ liệu" cung cấp cho người học các kiến thức về vai trò của cấu trúc dữ liệu, các tiêu chuẩn đánh giá cấu trúc dữ liệu, kiểu dữ liệu, định nghĩa kiểu dữ liệu, các kiểu dữ liệu cơ bản, các kiểu dữ liệu có cấu trúc,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (2016) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Trần Minh Thái Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn 1 Nội dung Chương 1. Tổng quan về giải thuật & cấu trúc dữ liệu 1.1. Vai trò của cấu trúc dữ liệu 1.2. Các tiêu chuẩn đánh giá cấu trúc dữ liệu 1.3. Kiểu dữ liệu 1.3.1. Định nghĩa kiểu dữ liệu 1.3.2. Các kiểu dữ liệu cơ bản 1.3.3. Các kiểu dữ liệu có cấu trúc 1.3.4. Một số kiểu dữ liệu có cấu trúc cơ bản 1.4. Đánh giá độ phức tạp giải thuật2 Nội dung Chương 2. Tìm kiếm và sắp xếp 2.1. Nhu cầu tìm kiếm, sắp xếp dữ liệu trong một hệ thống thông tin 2.2. Các giải thuật tìm kiếm nội 2.2.1. Tìm kiếm tuyến tính 2.2.2. Tìm kiếm nhị phân 2.3. Các giải thuật sắp xếp nội 2.3.1. Định nghĩa bài toán sắp xếp 2.3.2. Phương pháp chọn trực tiếp 3 Nội dung Các phương pháp sắp xếp do sinh viên tự nghiên cứu và thuyết trình 1. Phương pháp Shaker sort 2. Phương pháp sắp xếp cây (Heap sort) 3. Phương pháp sắp xếp với độ dài bước giảm dần (Shell sort) 4. Phương pháp sắp xếp theo phương pháp trộn trực tiếp (Merge sort) 5. Phương pháp sắp xếp theo phương pháp cơ số (Radix sort) 6. Phương pháp sắp xếp đếm phân khối 4 Nội dung Chương 3. Tổ chức ngăn xếp (Stack) & Hàng đợi (Queue) trên mảng một chiều 3.1. Ngăn xếp 3.1.1. Giới thiệu 3.1.2. Các thao tác trên ngăn xếp 3.1.3. Các ứng dụng - Tính các biểu thức đại số - Quản lý bộ nhớ khi thi hành chương trình 3.2. Hàng đợi 3.2.1. Giới thiệu 3.2.2. Các thao tác trên hàng đợi 5 Nội dung 3.2.3. Các ứng dụng • Tổ chức bộ đệm bàn phím • Quản lý các tiến trình trong các hệ điều hành • Vét cạn Nội dung sinh viên tự nghiên cứu và thuyết trình • Khử đệ quy • Tổ chức lưu vết các quá trình tìm kiếm theo chiều rộng và quay lui 6 Nội dung Chương 4. Cấu trúc dữ liệu động 4.1. Đặt vấn đề 4.2. Kiểu dữ liệu con trỏ 4.2.1. Biến không động 4.2.2. Kiểu con trỏ 4.2.3. Biến động 4.3. Danh sách liên kết 4.3.1. Định nghĩa 4.3.2. Các hình thức tổ chức danh sách 7 Nội dung 4.4. Danh sách đơn 4.4.1. Tổ chức danh sách đơn theo cấp phát liên kết 4.4.2. Các thao tác cơ bản trên danh sách đơn 4.4.3. Sắp xếp danh sách 4.4.4. Các cấu trúc đặc biệt của danh sách đơn 4.5. Một số cấu trúc dữ liệu dạng danh sách liên kết khác 4.5.1. Danh sách liên kết kép 4.5.2. Danh sách liên kết vòng 4.5.3. Danh sách có nhiều mối liên kết 4.5.4. Danh sách tổng quát 8 Nội dung Nội dung sinh viên tự nghiên cứu & thuyết trình • Hàng đợi • Ngăn xếp 9 Nội dung Chương 5. Cấu trúc cây 5.1. Cấu trúc cây 5.1.1. Một số khái niệm cơ bản 5.1.2. Một số ví dụ về đối tượng các cấu trúc dạng cây 5.2. Cây nhị phân 5.2.1. Một số tính chất của cây nhị phân 5.2.2. Biểu diễn cây nhị phân T 5.2.3. Duyệt cây nhị phân 5.2.4. Biểu diễn cây tổng quát bằng cây nhị phân 5.2.5. Một cách biểu diễn cây nhị phân khác 10 Nội dung 5.3. Cây nhị phân tìm kiếm. Các thao tác trên cây nhị phân tìm kiếm 5.4. Cây nhị phân cây cân bằng 5.4.1. Cây nhị phân cân bằng hoàn toàn 5.4.2. Cây nhị phân cân bằng 11 Nội dung Chương 6: Bảng băm (Hash Table) Nội dung sinh viên tự nghiên cứu & thuyết trình 6.1. Phương pháp băm 6.2. Các hàm băm 6.3. Phương pháp giải quyết đụng độ 6.4. Phân tích bảng băm 6.5. Kết luận so sánh các phương pháp 12 Chương 1 Tổng quan về giải thuật và cấu trúc dữ liệu 13 Mục tiêu • Giới thiệu tổng quan • Vai trò của tổ chức dữ liệu • Mối quan hệ giữa GT & CTDL • Các khái niệm và yêu cầu về CTDL • Nhắc lại các kiểu dữ liệu trong C# • Tổng quan về đánh giá độ phức tạp GT 14 Phân tích thiết kế hướng đối tượng • Nguyên tắc là chia nhỏ vấn đề à Xây dựng các lớp phù hợp: cung cấp các đối tượng có hành vi được mong đợi • Chương trình là một kịch bản gồm các lời gọi các hành vị của đối tượng lúc cần thiết à Các lớp đóng vai trò trung tâm trong việc hiện thực giải thuật 15 Phân tích thiết kế hướng đối tượng • Điểm mạnh: tính đóng gói và tính kế thừa • Gồm các lớp: CTDL, lớp đồ hoạ, lớp điều khiển, … • Đặc trưng của lớp CTDL: lưu trữ và trả về dữ liệu, gồm các thao tác: thêm, xoá, tìm kiếm và truy xuất 16 Vai trò của CTDL & GT Cấu Giải trúc dữ thuật liệu Phương thức 17 Quá trình phân tích hướng đối tượng • Xác định các lớp với các chức năng mong đợi • Xác định kịch bản/ giải thuật chính: sự tương tác giữa các đối tượng • Hiện thực các lớp 18 Xây dựng lớp CTDL 1. Từ mô hình/ nhu cầu thực tế à các chức năng cần có của lớp 2. Đặc tả các phương thức giao tiếp với bên ngoài: • Kiểu dữ liệu trả về của phương thức • Các thông số vào / ra • Các tiền kiện (precondition) • Các hậu kiện (postcondition) • Các lớp, hàm có sử dụng trong phương thức (uses) 3. Tìm hiểu phương án hiện thực lớp: phụ thuộc cách thức tổ chức dữ liệu bên trong, các giải thuật liên quan 4. Chọn phương án hiện thực 19 Các tiêu chuẩn đánh giá CTDL • Phản ánh đúng thực tế • Phù hợp với thao tác • Tiết kiệm tài nguyên hệ thống ...