CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT C++

Đh Khoa Học thoải mái và 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 lời giải sắp xếp selection sort, heap sort để thu 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 ứng 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 tập cũng lí giải sinh viên hiểu, đối chiếu và đánh giá được các giải thuật thao tác với các kết cấu dữ liệu đó.Ôn lại về lập trình, những kiểu dữ liệu trong C/C++, đặc biệt quan trọng là cấu tạo và nhỏ trỏ.Giới thiệu về độ phức tạp giám sát và đo lường và đệ qui.Các cấu tạo dữ liệu và sự phân tích chúng: danh sách; ck và hàng; cây, cây nhị phân, cây nhị phân kiếm tìm kiếm, AVL và đa phân; heap; giải mã sắp xếp; bảng băm; và đồ thị.

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

tác dụng cần đạt được

Phân tích lời giải L.O.1.1 – Định nghĩa được các khái niệm độ phức hợp và độ phức hợ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 những giải thuật và thực hiện được ký kết hiệu “Big O” nhằm ghi ra độ phức tạp của lời giải cấu thành từ các kết cấu điều khiển: tuần tự, rẽ nhánh cùng lặp.L.O.1.3 – Liệt kê được, đến được 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 – nhấn thức được sự cân đối giữa bộ nhớ lưu trữ và thời gian trong giải thuật.L.O.1.5 – biểu đạt được những chiến lược xây dựng giải thuật và giải quyết và xử lý bài toán.Sử dụng cấu trúc dữ liệu danh sách, ông chồng và hàngL.O.2.1 – phân phát họa được bằng hình ảnh cho: (a) list hiện thực bằng mảng và bằng link (con trỏ); (b) cho chồng; và (c) cho hàng ngóng và hàng đợi vòng (mức logic).L.O.2.2 – Viết được bằng mã đưa mô tả cấu tạo lưu trữ cho: (a) danh sách hiện thực bởi mảng và bằng liên kết; (b) mang lại chồng; và (c) cho hàng chờ và hàng ngóng 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, ông xã 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 – hiện nay được các cấu trúc danh sách, ông chồng 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, và hàng để giải quyết bài toán thực, cũng như quan tâm đến chọn lựa hình dáng hiện thực về tối ưu.L.O.2.6 – so sánh được và làm thí nghiệm nhận xét các thủ tục đã hổ trợ đến các cấu trúc danh sánh, chồng, cùng hàng.Sử dụng cấu trúc câyL.O.3.1 – phân 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 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ã đưa mô tả kết cấu lưu trữ cho các loại cây (mức logic)L.O.3.3 – Liệt kê được những phương thức quan trọng cho đến các cấu tạo cây; cũng giống như mô tả được chúng bằng mã đưa (mức logic).L.O.3.4 – đã cho thấy được và mang đế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ới vẽ hình minh họa về toàn bộ các trường mất thăng 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 vẽ (mức logic).L.O.3.6 – lúc này được các cấu tạo cây nhị phân với cây AVL bằng C/C++L.O.3.7 – thực hiện được cây nhị phân với cây AVL để giải quyết và xử lý bài toán thực, nhất là liên quan mang lại tìm kiếm.L.O.3.8 – phân tích được và làm thực nghiệm nhận xét được những phương thức đã hổ trợ mang lại 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 rằng được những ứng dụng cần đến HeapL.O.4.2 – demo được bởi hình hình ảnh cho cấu trúc 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 những 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 cách tiến hành để đảm bảo an toàn tính chất của kết cấu Heap khi đưa vào hay rước ra bộ phận trong heap (mức logic).L.O.4.5 – hiện tại được cấu tạo heap bởi C/C++.L.O.4.6 – so sánh được và có tác dụng 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 thuộc với có mang về khóa, chạm độ và giải quyết đụng độ.L.O.5.2 – bộc lộ được bởi mã đưa và mang lại ví dụ minh họa cho những hàm băm cơ bản.L.O.5.3 – miêu tả được bởi mã đưa và đến ví dụ minh họa cho những phương thức giải quyết và xử lý đụng độ.L.O.5.4 – hiện tại được cấu trúc bảng băm bởi C/C++.L.O.5.5 – so với được và làm cho thực nghiệm reviews được những 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 sắp đến 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 giải thuật sắp xếp.L.O.6.2 – biểu lộ được bởi mã giả cho những giải thuật sắp tới xếp. L.O.6.3 – thực tại được những giải thuật thu 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 câu hỏi 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ởi 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à ko hướng, chu trình, v.v.L.O.7.2 – Vẽ được hình minh họa và mô tả kết cấu lưu trữ đến đồ thị ở những dạng ma trận kề và list kề bằng mã đưa (mức logic).L.O.7.3 – Liệt kê được các phương thức quan trọng cho mang lại 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 ảnh các phương thức duyệt trang bị thị cơ phiên bản (depth first and bread-first).L.O.7.5 – thực tại được kết cấu lưu trữ đồ thì bởi C/C++.L.O.7.6 – hiện tại được các cách thức 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ởi hình vẽ từng bước hoạt động vui chơi 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ủ tối tiểu bằng giải mã Prim.Sử dụng đệ quyL.O.8.1 – trình bày được các thành phần cơ bản của một lời giải đệ quy.L.O.8.2 – Vẽ được cây tế bào tả những lần gọi hàm với giá trị của các tham số được truyền vào những hàm đó.L.O.8.3 – đến được ví dụ như về một hàm gọi đệ quy viết bởi C/C++.L.O.8.4 – cách tân và phát triển được giải mã đệ 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 bên trên cây cùng tìm tìm nhị phân, cùng đồ thị.L.O.8.5 – làm cho được thí điểm để đối chiếu cách tiếp cận đệ quy và cách lặp.L.O.8.6 – cho được lấy ví dụ minh họa sự tương quan giữa Backtracking cùng đệ 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 và 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: Top 6 Sữa Tắm Thơm Lâu Của Nhật Trắng Da, Thơm Lâu Tốt Nhất 2020

<2> “C/C++: How to lớn Program”, 7th Ed. – Paul Deitel và Harvey Deitel, Prentice Hall, 2012.<3> Internet.<4> Minh họa cấu tạo dữ liệu với giải thuật