Đ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 xích tập, thực hành
*

*

*

*

*

homework 2_cài đặt giải mã 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, ngôn từ môn học

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

Bạn đang xem: Học cấu trúc dữ liệu và giải thuật

công dụng cần dành được

Phân tích lời giải L.O.1.1 – Định nghĩa được các khái niệm độ tinh vi và độ phức tạp trong những trường hòa hợp “tốt nhất”, “xấu nhất”, với “trung bình”.L.O.1.2 – so với được những giải thuật và áp dụng được ký kết hiệu “Big O” nhằm ghi ra độ phức hợp của lời giải 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 lấy một ví dụ và so sánh được những lớp độ phức tạp, như, hằng số, log, đường tính, etc.L.O.1.4 – thừa nhận thức được sự cân bằng giữa bộ nhớ và thời hạn trong giải thuật.L.O.1.5 – bộc lộ được những chiến lược kiến tạo giải thuật và xử lý bài toán.Sử dụng cấu tạo dữ liệu danh sách, ông chồng và hàngL.O.2.1 – phát họa được bằng hình hình ảnh cho: (a) list hiện thực bởi mảng cùng bằng link (con trỏ); (b) đến chồng; cùng (c) mang đến hàng chờ và hàng chờ vòng (mức logic).L.O.2.2 – Viết được bởi mã mang mô tả cấu trúc lưu trữ cho: (a) list hiện thực bởi mảng và bởi liên kết; (b) mang đến chồng; và (c) đến hàng đợi và hàng đợi vòng (mức logic).L.O.2.3 – Liệt kê được những phương thức quan trọng cho từng cấu trúc như danh sách, ông chồng và hàng đợi; tương tự như mô tả được chúng bằng mã giả (mức logic).L.O.2.4 – hiện tại được các cấu tạo danh sách, ông xã và sản phẩm đợi bởi C/C++ (mức physics)L.O.2.5 – áp dụng được danh sách, chồng, cùng hàng để giải quyết bài toán thực, cũng như suy xét chọn lựa kiểu dáng hiện thực về tối ưu.L.O.2.6 – đối chiếu được và làm cho thí nghiệm review các cách thức đã hổ trợ mang lại các cấu tạo danh sánh, chồng, cùng hàng.Sử dụng cấu tạo câyL.O.3.1 – phát họa được bằng hình 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ởi mã mang mô tả cấu tạo lưu trữ cho những 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 đến các cấu trúc cây; cũng như mô tả được chúng bởi mã trả (mức logic).L.O.3.4 – chỉ ra rằng được và mang đến ví dụ minh họa về tầm đặc biệt của tính cân đối trong cây.L.O.3.5 – chỉ ra được và vẽ hình minh họa về tất cả các ngôi trường mất thăng bằng trong cây AVL với cây B, cũng tương tự thực hiện từng bước để tái cân đối chúng trên hình vẽ (mức logic).L.O.3.6 – hiện thực được các kết cấu cây nhị phân cùng cây AVL bởi C/C++L.O.3.7 – áp dụng được cây nhị phân và cây AVL để giải quyết bài toán thực, nhất là liên quan đến tìm kiếm.L.O.3.8 – đối chiếu được và có tác dụng thực nghiệm đánh giá được những phương thức đã hổ trợ cho các cấu trúc cây nhị phân cùng 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 tạo Heap cùng nêu ra sự tương quan đến lưu trữ ở dạng mảng.L.O.4.3 – Liệt kê được các phương thức quan trọng cho cho cấu tạo heap; tương tự như mô tả được chúng bởi mã trả (mức logic).L.O.4.4 – demo được bằng hình ảnh các cách tiến hành để đảm bảo an toàn tính hóa học của cấu trúc Heap khi gửi vào hay đem ra bộ phận trong heap (mức logic).L.O.4.5 – hiện thực được cấu trúc heap bởi C/C++.L.O.4.6 – đối chiếu được và làm cho thực nghiệm review được các phương thức vẫn 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 định nghĩa về khóa, đụng độ và xử lý đụng độ.L.O.5.2 – biểu lộ được bởi mã mang và đến ví dụ minh họa cho những hàm băm cơ bản.L.O.5.3 – trình bày được bằng mã mang và mang lại ví dụ minh họa cho các phương thức giải quyết và xử lý đụng độ.L.O.5.4 – lúc này được cấu trúc bảng băm bằng C/C++.L.O.5.5 – so với được và làm thực nghiệm review được các phương thức vẫn hổ trợ cho cấu tạo bảng băm.Phát triển các giải thuật chuẩn bị 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 – miêu tả được bởi mã giả cho những giải thuật sắp đến xếp. L.O.6.3 – hiện tại được các giải thuật sắp xếp bằng C/C++ .L.O.6.4 – so với được và có tác dụng thực nghiệm đánh giá các giải thuật sắp xếp.L.O.6.5 – thực hiện được giải mã sắp xếp trong bài toán thực.Hiểu biết cơ bạn dạng về vật thịL.O.7.1 – phát họa được bằng hình hình ảnh cho các khái niệm như thiết bị thị liên thông với không liên thông, thứ thị được đặt theo hướng và không hướng, chu trình, v.v.L.O.7.2 – Vẽ được hình minh họa với mô tả kết cấu lưu trữ đến đồ thị ở những dạng ma trận kề và list kề bởi mã đưa (mức logic).L.O.7.3 – Liệt kê được các phương thức cần thiết cho đến các kết cấu đồ thị; cũng giống như mô tả được chúng bởi mã đưa (mức logic).L.O.7.4 – Minh họa được bởi hình hình ảnh các cách thức duyệt đồ vật thị cơ bản (depth first & bread-first).L.O.7.5 – lúc này được kết cấu lưu trữ đồ thì bằng C/C++.L.O.7.6 – lúc này được các cách thức duyệt nói trên bởi C/C++ và áp dụng chúng giải quyết bài toán thực.L.O.7.7 – Minh họa bởi hình vẽ từng bước buổi giao lưu của các lời giải tìm mặt đường ngắn nhất bởi Dijktra và giải thuật tìm cây phủ buổi 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 dạng của một lời giải đệ quy.L.O.8.2 – Vẽ được cây tế bào tả các lần hotline hàm cùng giá trị của những tham số được truyền vào các hàm đó.L.O.8.3 – đến được ví dụ về một hàm gọi đệ quy viết bởi C/C++.L.O.8.4 – cải cách và phát triển được lời giải đệ quy cho những phương thức quan trọng của các cấu trúc: danh sách, cây, heap, tìm kiếm kiếm trên cây với tìm tìm nhị phân, với đồ thị.L.O.8.5 – làm được nghiên cứu để so sánh cách tiếp cận đệ quy và biện pháp lặp.L.O.8.6 – mang đến được lấy một ví dụ minh họa sự liên quan giữa Backtracking và đệ quy.

Tài liệu tìm hiểu thêm

Sách, Giáo trình chính:<1>. “Data Structures: a Pseudocode Approach with C++”, R.F.Gilberg và B.A. Forouzan, Thomson Learning Inc., 2001.Sách tham khảo:<1> “Data Structures và Algorithms in C++”, A. Drozdek, Thomson Learning Inc., 2005.<2> “C/C++: How khổng lồ Program”, 7th Ed. – Paul Deitel and Harvey Deitel, Prentice Hall, 2012.

Xem thêm: Cách Cộng Trừ Căn Bậc 2, Công Thức Tính Căn Bậc 2 Và Bài Tập

<3> Internet.<4> Minh họa cấu trúc dữ liệu với giải thuật