Cấu trúc dữ liệu và giải thuật trong C++
lượt xem 69
download
1. Môn học cung cấp những kiến thức cơ bản, nền tảng về một số cấu trúc dữ liệu và một số thuật tóan. Nó là cơ sở để xây dựng các hệ thống phần mềm lớn và phức tạp. 2. Môn học giúp sinh viên hiểu cách thức tổ chức lưu trữ dữ liệu trong bộ nhớ của máy tính và làm thế nào để sử dụng nó một cách có hiệu quả trong các chương trình. Sử dụng những kiến thức này để xây dựng các cấu trúc dữ liệu phù hợp cho các hệ thống phức tạp khác. 3. Cung cấp cho sinh viên một số...
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Cấu trúc dữ liệu và giải thuật trong C++
- Cấu trúc dữ liệu và giải thuật trong C++ (Data Structures and Algorithms In C++) Giảng viên: Hoàng Văn Thông Mail: thonghoangvan@yahoo.com - 0988113679
- Tổ chức môn học Số tín chỉ: 3 + Bài tập lớn Hình thức thi cuối kỳ: viết Đánh giá kết quả học tập cuối kỳ Kiểm tra giữa kỳ Bài tập lớn Thi cuối kỳ Tổng 10% 20% 70% 100%
- Bài 1. Bài mở đầu
- I. Mục đích môn học 1. Môn học cung cấp những kiến thức cơ bản, nền t ảng về một số cấu trúc dữ liệu và một số thuật tóan. Nó là cơ sở để xây dựng các hệ thống phần mềm lớn và phức tạp. 2. Môn học giúp sinh viên hiểu cách thức tổ chức lưu trữ dữ liệu trong bộ nhớ của máy tính và làm thế nào để sử dụng nó một cách có hiệu quả trong các chương trình. Sử dụng những kiến thức này để xây dựng các cấu trúc dữ liệu phù hợp cho các hệ thống phức tạp khác. 3. Cung cấp cho sinh viên một số thuật toán cơ bản trên các cấu trúc dữ liệu 4. Sinh viên hiểu và biết phân tích thời gian, không gian (bộ nhớ) cần cho một thuật toán.
- II. Thời gian biểu Bài 1: Bài mở đầu (introduction) - Một số bài tập rèn luyện kỹ năng lập trình với 1 Bài 2: Ngôn ngữ lập trình C++ ngôn ngữ C++ Bài 3: Lập trình hướng thủ tục và lập trình hướng đối - Xây dựng một số lớp đơn giản: lớp Time, Date, 2 tượng (Function Oriented Programming and Object student,… Oriented Programming) - Xây dựng lớp trong C++ Bài 4. Xây dựng lớp mẫu, thiết kế mẫu (design pattern) - Làm một số lớp mẫu theo yêu cầu 3 - Sử dụng các lớp đó trong chương trình cụ thể trong C++. Bài 5. Phân tích các thuật toán (Analysis of Algorithms) -Phân tích một số thuật toán được đưa ra 4 -Chứng minh một số thuật toán
- Bài 6. Thuật toán đệ qui (recursive algorithm) - Xây dựng thuật toán đệ qui giải một số bài toán 5 -Xây dựng lớp mẫu Vector 6 Bài 7. Vector -Xây dựng chương trình sử dụng Vector để lưu trữ dữ liệu Bài 8. Danh sách liên kết đơn (single list), danh sách -Xây dựng lớp mẫu danh sách liên kết đơn 7 liên kết kép (double list) -Xây dựng chương trình sử dụng danh sách liên kết đơn để lưu trữ dữ liệu -Xây dựng lớp mẫu danh sách liên kết kép -Xây dựng chương trình sử dụng danh sách liên kết kép để lưu trữ dữ liệu Bài 9. Cấu trúc dữ liệu kiểu ngăn xếp – Stack -Xây dựng lớp mẫu Stack 8 Bài 10. Cấu trúc dữ liệu kiểu hàng đợi – Queue -Xây dựng chương trình sử dụng stack để lưu trữ dữ liệu -Xây dựng lớp mẫu Queue -Xây dựng chương trình sử dụng Queue để lưu trữ dữ liệu -Kiểm tra giữa kỳ 9 -Giao bài tâp lớn Bài 11. Cây nhị phân (binary tree) - Xây dựng lớp mẫu cây nhị phân 10 Bài 12. Cây tổng quát (genaral tree)
- Bài 13. Đồ thị và các thuật toán trên đồ thị (Graph) - Xây dựng lớp đồ thị với các phương thức cho 11 phép chuyển đổi giữa các dạng lưu trữ khác nhau của đồ thị, tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị, kiểm tra đồ thị có liên thông không?, … Bài 14. Các thuật toán sắp xếp (n2) - Cài đặt các hàm sắp xếp một mảng với từng 12 -Nổi bọt (Bubble Sort) phương thức -Chọn (Selection Sort) -Chèn (Insertion Sort) Bài 15. Các thuật toán sắp xếp (nlogn) - Cài đặt các thuật toán sắp xếp cho các lớp 13 -Trộn (Mergere Sort) Vector, List -QuickSort (Quick Sort) Bài 16. Đống – Cây heap - Cài đặt hàm sắp xếp một mảng bằng thuật toán 14 Thuật toán sắp xếp vun đống (Heap Sort) HeapSort Bài 17. Các thuật toán tìm kiếm (Search Algorithms) - Cài đặt thuật toán tìm kiếm nhị phân cho lớp 15 - Tìm kiếm tuần tự (Sequence search) Vector, lớp List. - Tìm kiếm nhị phân (Binary search), cây tìm kiếm nhị - Cài đặt thuật toán tìm kiếm cho lớp cây nhị phân phân (Binary search tree) - Tìm kiếm trên bảng băm – HashTable Nghiêm thu bài tập lớn 16
- III. Các đối tượng nghiên cứu trong môn học Các cấu trúc dữ liệu chuẩn • Vectors, lists, stack, queue,trees, graphs,… Các thuật toán chuẩn • Sắp xếp (Sorting) • Tìm kiếm (Selection) Phân tích độ phức tạp về thời gian và không gian (bộ nhớ) của các thuật toán. Những kỹ năng lựa chọn thuật toán, cấu trúc dữ liệu và cài đặt thuật toán
- IV. Các kiến thức bổ trợ cho môn học Ngôn ngữ lập trình C++ Phương phap lập trình hướng đối tượng (Object ́ Oriented Programming method- OOP)
- V. Tài liệu tham khảo 1. Data structures and Algorithms in C++, Michael T. Goodrich, Roberto Tamassia 2. Cấu trúc dữ liệu hướng đối tượng với C++, Bản dịch của Nguyễn Phúc Trường Sinh, NXB Thống kê 3. Cấu trúc dữ liệu và giải thuật – Nguyễn Văn Long, NXB GTVT 4. Cấu trúc dữ liệu và giải thuật – Đỗ Xuân Lôi, NXB Khoa h ọc kỹ thuật 5. Cẩm nang thuật toán (vol1 + vol2), Robert Sedgewick, NXB KHKT 6. Lập trình hướng đối tượng và C++, Phạm Văn Ất, NXB GTVT Địa chỉ website 1. http://www.Datastructures.net 2. http://www.cplusplus.com 3. http://www.Edu.net.vn …
- VI. Một số mục tiêu của công nghệ phần mềm Tin cậy và chính xác (Reliability – correctness) Hữu dụng (utility) Đạt được những gì mong muốn Đáp ứng đúng thời điểm Mềm dẻo (flexibility) Có khả năng mang chuyển được (Portability), tức là có thể dễ dàng mang cài đặt sang một hệ thống khác. Khả năng tương thích Dễ bảo trì Dễ hiểu Có thể sử dụng lại Hiệu quả (efficiency) Người lập trình (không mất quá nhiều công sức cho việc lập trình) Máy Thời gian Bộ nhớ
- VII. Các nguyên lý của CNPM Trừu tượng (Abstract): Loại bỏ các thành phần mang tính chi tiết trong định nghĩa một vấn đề nào đó Modul hóa (Modularity): Hạn chế độ phức tạp bằng cách phân chia ra thành nhiều phần (Chia để trị). Phân chia bài toán thành các modul nhỏ, thực hiện giải quyết từng modul Kết hợp các modul Che dấu thông tin (Information Hiding): Theo nguyên lý trừu tượng Không cho phép truy nhập từ bên ngoài
- Hết
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Giáo trình cấu trúc dữ liệu và giải thuât part 1
16 p | 825 | 365
-
Giáo trình cấu trúc dữ liệu và giải thuât part 2
16 p | 551 | 286
-
Bài giảng Cấu trúc dữ liệu - Bài 1:Tổng quan về cấu trúc dữ liệu và giải thuật
47 p | 174 | 17
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây đỏ đen - Bùi Tiến Lên
25 p | 76 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Các khái niệm cơ bản về Cấu trúc dữ liệu và giải thuật
20 p | 44 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu
193 p | 57 | 7
-
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)
62 p | 94 | 6
-
Giáo trình Cấu trúc dữ liệu và giải thuật - CĐ Nghề Đắk Lắk
60 p | 44 | 6
-
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 )
62 p | 157 | 6
-
Giáo trình Cấu trúc dữ liệu và giải thuật (Nghề: Công nghệ thông tin - Trung cấp) - Trường Trung cấp Công nghệ và Du lịch Hà Nội
59 p | 14 | 4
-
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
10 p | 66 | 4
-
Giáo trình Cấu trúc dữ liệu và giải thuật (Ngành: Công nghệ thông tin - Cao đẳng) - Trường Cao đẳng Xây dựng số 1
77 p | 9 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 – Trần Minh Thái (2017)
67 p | 105 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Một số khái niệm cơ bản về cấu trúc dữ liệu và giải thuật
12 p | 91 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Tổng quan - Nguyễn Đức Cương
6 p | 99 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Cấu trúc dữ liệu và giải thuật
42 p | 54 | 3
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Th.S Thiều Quang Trung
41 p | 68 | 3
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Ngô Quang Thạch
49 p | 63 | 3
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn