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

Đh Khoa Học Tự Nhiên Hcm - Văn Chí Nam, Nguyễn Thị Hồng Nhung, Đặng Nguyễn Đức Tiến - Lý thuyết - Bài tập, thực hành





homework 2_cài đặt giải thuật sắp xếp selection sort, heap sort để sắp xếp một mảng số nguyên theo_thứ tự tăng dần.pdf

Giới thiệu, nội dung môn học

Môn học nhằm cung cấp cho sinh viên khả năng sử dụng các cấu trúc dữ liệu nền tảng. Môn học cũng hướng dẫn sinh viên hiểu, phân tích và đánh giá được các giải thuật làm việc với các cấu trúc dữ liệu đó.Ôn lại về lập trình, các kiểu dữ liệu trong C/C++, đặc biệt là cấu trúc và con trỏ.Giới thiệu về độ phức tạp tính toán và đệ qui.Các cấu trúc dữ liệu và sự phân tích chúng: danh sách; chồng và hàng; cây, cây nhị phân, cây nhị phân tìm kiếm, AVL và đa phân; heap; giải thuật sắp xếp; bảng băm; và đồ thị. Bạn đang xem: Cấu trúc dữ liệu giải thuật

Kết quả cần đạt được

Phân tích giải thuật L.O.1.1 – Định nghĩa được các khái niệm độ phức tạp và độ phức tạp trong các trường hợp “tốt nhất”, “xấu nhất”, và “trung bình”.L.O.1.2 – Phân tích được các giải thuật và sử dụng được ký hiệu “Big O” để ghi ra độ phức tạp của giải thuật cấu thành từ các cấu trúc điều khiển: tuần tự, rẽ nhánh và lặp.L.O.1.3 – Liệt kê được, cho được ví dụ và so sánh được các lớp độ phức tạp, như, hằng số, log, tuyến tính, etc.L.O.1.4 – Nhận thức được sự cân bằng giữa bộ nhớ và thời gian trong giải thuật.L.O.1.5 – Mô tả được các chiến lược thiết kế giải thuật và giải quyết bài toán.Sử dụng cấu trúc dữ liệu danh sách, chồng và hàngL.O.2.1 – Phát họa được bằng hình ảnh cho: (a) danh sách hiện thực bằng mảng và bằng liên kết (con trỏ); (b) cho chồng; và (c) cho hàng đợi và hàng đợi vòng (mức logic).L.O.2.2 – Viết được bằng mã giả mô tả cấu trúc lưu trữ cho: (a) danh sách hiện thực bằng mảng và bằng liên kết; (b) cho chồng; và (c) cho hàng đợi và hàng đợi vòng (mức logic).L.O.2.3 – Liệt kê được các phương thức cần thiết cho từng cấu trúc như danh sách, chồng và hàng đợi; cũng như mô tả được chúng bằng mã giả (mức logic).L.O.2.4 – Hiện thực được các cấu trúc danh sách, chồng và hàng đợi bằng C/C++ (mức physics)L.O.2.5 – Sử dụng được danh sách, chồng, và hàng để giải quyết bài toán thực, cũng như cân nhắc chọn lựa kiểu hiện thực tối ưu.L.O.2.6 – Phân tích được và làm thí nghiệm đánh giá các phương thức đã hổ trợ cho các cấu trúc danh sánh, chồng, và hàng.Sử dụng cấu trúc câyL.O.3.1 – Phát họa được bằng hình ảnh cho các cây tiêu biểu, như, cây nhị phân, cây nhị phân đầy đủ, cây nhị phân cân bằng, cây AVL, cây đa phân, v.v. (mức logic).L.O.3.2 – Viết được bằng mã giả mô tả cấu trúc lưu trữ cho các loại cây (mức logic)L.O.3.3 – Liệt kê được các phương thức cần thiết cho cho các cấu trúc cây; cũng như mô tả được chúng bằng mã giả (mức logic).L.O.3.4 – Chỉ ra được và cho ví dụ minh họa về tầm quan trọng của tính cân bằng trong cây.L.O.3.5 – Chỉ ra được và vẽ hình minh họa về tất cả các trường mất cân bằng trong cây AVL và cây B, cũng như thực hiện từng bước để tái cân bằng chúng trên hình vẽ (mức logic).L.O.3.6 – Hiện thực được các cấu trúc cây nhị phân và cây AVL bằng C/C++L.O.3.7 – Sử dụng được cây nhị phân và cây AVL để giải quyết bài toán thực, đặc biệt là liên quan đến tìm kiếm.L.O.3.8 – Phân tích được và làm thực nghiệm đánh giá được các phương thức đã hổ trợ cho các cấu trúc cây nhị phân và cây AVL.Sử dụng HeapL.O.4.1 – Chỉ ra được những ứng dụng cần đến HeapL.O.4.2 – Phác họa được bằng hình ảnh cho cấu trúc Heap và nêu ra sự liên quan đến lưu trữ ở dạng mảng.L.O.4.3 – Liệt kê được các phương thức cần thiết cho cho cấu trúc heap; cũng như mô tả được chúng bằng mã giả (mức logic).L.O.4.4 – Phác họa được bằng hình ảnh các phương thức để đảm bảo tính chất của cấu trúc Heap khi đưa vào hay lấy ra phần tử trong heap (mức logic).L.O.4.5 – Hiện thực được cấu trúc heap bằng C/C++.L.O.4.6 – Phân tích được và làm thực nghiệm đánh giá được các phương thức đã hổ trợ cho cấu trúc Heap.Sử dụng bảng băm L.O.5.1 – Vẽ được hình minh họa một bảng băm cùng với khái niệm về khóa, đụng độ và giải quyết đụng độ.L.O.5.2 – Mô tả được bằng mã giả và cho ví dụ minh họa cho các hàm băm cơ bản.L.O.5.3 – Mô tả được bằng mã giả và cho ví dụ minh họa cho các phương thức giải quyết đụng độ.L.O.5.4 – Hiện thực được cấu trúc bảng băm bằng C/C++.L.O.5.5 – Phân tích được và làm thực nghiệm đánh giá được các phương thức đã hổ trợ cho cấu trúc bảng băm.Phát triển các giải thuật sắp xếpL.O.6.1 – Minh họa được bằng hình vẽ từng bước hoạt động của các giải thuật sắp xếp.L.O.6.2 – Mô tả được bằng mã giả cho các giải thuật sắp xếp. L.O.6.3 – Hiện thực được các giải thuật sắp xếp bằng C/C++ .L.O.6.4 – Phân tích được và làm thực nghiệm đánh giá các giải thuật sắp xếp.L.O.6.5 – Sử dụng được giải thuật sắp xếp trong bài toán thực.Hiểu biết cơ bản về đồ thịL.O.7.1 – Phát họa được bằng hình ảnh cho các khái niệm như đồ thị liên thông và không liên thông, đồ thị có hướng và không hướng, chu trình, v.v.L.O.7.2 – Vẽ được hình minh họa và mô tả cấu trúc lưu trữ cho đồ thị ở các dạng ma trận kề và danh sách kề bằng mã giả (mức logic).L.O.7.3 – Liệt kê được các phương thức cần thiết cho cho các cấu trúc đồ thị; cũng như mô tả được chúng bằng mã giả (mức logic).L.O.7.4 – Minh họa được bằng hình ảnh các phương pháp duyệt đồ thị cơ bản (depth first and bread-first).L.O.7.5 – Hiện thực được cấu trúc lưu trữ đồ thì bằng C/C++.L.O.7.6 – Hiện thực được các phương pháp duyệt nói trên bằng C/C++ và sử dụng chúng giải quyết bài toán thực.L.O.7.7 – Minh họa bằng hình vẽ từng bước hoạt động của các giải thuật tìm đường ngắn nhất bằng Dijktra và giải thuật tìm cây phủ tối tiểu bằng giải thuật Prim.Sử dụng đệ quyL.O.8.1 – Mô tả được các thành phần cơ bản của một giải thuật đệ quy.L.O.8.2 – Vẽ được cây mô tả các lần gọi hàm và giá trị của các tham số được truyền vào các hàm đó.L.O.8.3 – Cho được ví dụ về một hàm gọi đệ quy viết bằng C/C++.L.O.8.4 – Phát triển được giải thuật đệ quy cho các phương thức cần thiết của các cấu trúc: danh sách, cây, heap, tìm kiếm trên cây và tìm kiếm nhị phân, và đồ thị.L.O.8.5 – Làm được thí nghiệm để so sánh cách tiếp cận đệ quy và cách lặp.L.O.8.6 – Cho được ví dụ minh họa sự liên quan giữa Backtracking và đệ quy.

Tài liệu tham khảo

Sách, Giáo trình chính:<1>. “Data Structures: a Pseudocode Approach with C++”, R.F.Gilberg and B.A. Forouzan, Thomson Learning Inc., 2001.Sách tham khảo:<1> “Data Structures and Algorithms in C++”, A. Drozdek, Thomson Learning Inc., 2005. Xem thêm: Usb 2Gb Giá Rẻ Tphcm - Usb Kingston Loại 2Gb Đến 32 Gb Chất Liệu Vở Thép <2> “C/C++: How to Program”, 7th Ed. – Paul Deitel and Harvey Deitel, Prentice Hall, 2012.<3> Internet.<4> Minh họa cấu trúc dữ liệu và giải thuật