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

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 trong một đề án tin học, 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,... 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 (Trường Đại học Hồng Bàng ) 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 trong một đề án tin học 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 2 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 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 Xét đoạn chương trình sau void main() { int n; coutn; if(n%2==0) coutCá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 16 Khái niệm về kiểu dữ liệu T = V = {Tập các giá trị} O = {Tập các thao tác xử lý} Ví dụ: Kiểu dữ liệu số nguyên short trong ngôn ngữ C++ T = short V = {-32768, 32767} O = {+, -, *, /, %} 17 Khái niệm về kiểu dữ liệu • Các thuộc tính của một kiểu dữ liệu gồm: • Tên • Miền giá trị • Kích thước lưu trữ • Tập các thao tác tác động lên kiểu dữ liệu đó • Các loại kiểu dữ liệu • Kiểu dữ liệu cơ bản: Cơ sở, mảng, cấu trúc cơ bản • Kiểu dữ liệu có cấu trúc hướng giải quyết vấn đề: Danh sách liên kết, hàng đợi, ngăn xếp, cây, bảng băm, … 18 Khái niệm về kiểu dữ liệu Tĩnh Động •   Được  định  nghĩa  ở  thời  •   Được  gắn  kết  với  một  điểm biên dịch. con trỏ  (tại thời điểm biên  dịch chưa có). •   Được  cấp  phát  ở  thời  •  Phát sinh lúc thực thi. điểm liên kết. •   Có  thể  có  giá  trị  ban  đầu  •  Không xác định giá trị ban  tùy theo từng ngôn ngữ lập  đầu.  trình. •   Tồn  tại  đến  khi  kết  thúc  •  Được giải phóng khỏi bộ  chương trình. nhớ khi cần. 19 Nhắc lại các kiểu dữ liệu C++ • Kiểu cơ sở: Số nguyên, số thực và kiểu logic • Kiểu dãy (mảng), xâu ký tự • Kiểu có cấu trúc 20 ...