Giáo Trình Cấu Trúc Dữ Liệu Và 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 - định hướng - bài xích tập, thực hành
*

*

*

*

*

homework 2_cài đặt lời giải sắp xếp selection sort, heap sort để bố trí một mảng số nguyên theo_thứ trường đoản cú tăng dần.pdf

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

Môn học tập nhằm hỗ trợ cho sinh viên kĩ năng sử dụng các cấu trúc dữ liệu nền tảng. Môn học cũng khuyên bảo sinh viên hiểu, đối chiếu và reviews đượ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 tài liệu trong C/C++, đặc trưng là kết cấu và bé trỏ.Giới thiệu về độ phức tạp đo lường và thống kê và đệ qui.Các kết cấu dữ liệu và sự đối chiếu 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, AVL cùng đa phân; heap; lời giải sắp xếp; bảng băm; cùng đồ thị.

Bạn đang xem: Giáo trình cấu trúc dữ liệu và giải thuật

hiệu quả cần đã đạt được

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

Tài liệu xem thêm

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 & Algorithms in C++”, A. Drozdek, Thomson Learning Inc., 2005.

Xem thêm: Làm Giấy Chứng Nhận Kết Hôn Trên Facebook, Hướng Dẫn Cách Kết Hôn Trên Facebook Mới Nhất

<2> “C/C++: How khổng lồ Program”, 7th Ed. – Paul Deitel & Harvey Deitel, Prentice Hall, 2012.

Xem thêm: Hướng Dẫn Cách Khóa Ảnh Bìa Trên Facebook, Cài Đặt Riêng Tư Avatar Facebook

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