Giáo Trình Cấu Trúc Dữ Liệu

Đh Khoa Học tự nhiên và thoải mái Hcm - Văn Chí Nam, Nguyễn Thị Hồng Nhung, Đặng Nguyễn Đức Tiến - kim chỉ nan - bài xích tập, thực hành thực tế

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, nội dung môn học tập

Môn học tập nhằm hỗ trợ 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à đánh giá được các giải thuật thao tác làm việ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 trưng là cấu tạo 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ới sự so sánh chúng: danh sách; ông xã và hàng; cây, cây nhị phân, cây nhị phân kiếm tìm kiếm, AVL với đa phân; heap; lời giải sắp xếp; bảng băm; và đồ thị.

Bạn đang xem: Giáo trình cấu trúc dữ liệu

kết quả cần có được

Phân tích giải thuật L.O.1.1 – Định nghĩa được những khái niệm độ tinh vi và độ tinh vi trong những trường vừa lòng “tốt nhất”, “xấu nhất”, cùng “trung bình”.L.O.1.2 – phân tích được những giải thuật và sử dụng được ký hiệu “Big O” nhằm ghi ra độ phức hợ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ới lặp.L.O.1.3 – Liệt kê được, đến được lấy 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 – nhận thức được sự cân đối giữa bộ lưu trữ và thời gian trong giải thuật.L.O.1.5 – diễn đạt được những chiến lược kiến thiết 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, ông chồng và hàngL.O.2.1 – vạc 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) mang đến chồng; cùng (c) mang đến hàng đợi và hàng chờ vòng (mức logic).L.O.2.2 – Viết được bởi mã giả mô tả cấu tạo lưu trữ cho: (a) list hiện thực bởi mảng và bằng liên kết; (b) cho chồng; và (c) mang đến hàng đợi và hàng hóng vòng (mức logic).L.O.2.3 – Liệt kê được những phương thức cần thiết cho từng kết cấu 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ã giả (mức logic).L.O.2.4 – lúc này được các cấu trúc danh sách, ck và mặt hàng đợi bằng C/C++ (mức physics)L.O.2.5 – áp dụng đượ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 kiểu hiện thực về tối ưu.L.O.2.6 – so với được và làm cho thí nghiệm reviews các phương thức đã hổ trợ đến các cấu trúc danh sánh, chồng, và hàng.Sử dụng kết cấu câyL.O.3.1 – phân 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 nặng 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ã trả 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 những phương thức cần thiết cho đến các kết cấu cây; tương tự như mô tả được chúng bởi mã trả (mức logic).L.O.3.4 – đã cho thấy đượ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 rằng được và vẽ hình minh họa về toàn bộ các 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 từng bước một để tái cân bằng chúng trên hình vẽ (mức logic).L.O.3.6 – thực tại đượ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 – áp dụng được cây nhị phân và cây AVL để giải quyết và xử lý 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à có tác dụng thực nghiệm reviews được các phương thức đang hổ trợ cho các cấu tạo cây nhị phân với cây AVL.Sử dụng HeapL.O.4.1 – chỉ ra rằng được những áp dụng cần mang lại HeapL.O.4.2 – phác họa được bằng hình hình ảnh cho cấu tạo Heap với nêu ra sự tương quan đến tàng trữ ở dạng mảng.L.O.4.3 – Liệt kê được các phương thức quan trọng cho cho kết cấu heap; tương tự như mô tả được chúng bằng mã đưa (mức logic).L.O.4.4 – phác họa được bởi hình hình ảnh các thủ tục để đảm bảo an toàn tính chất của cấu trúc Heap khi chuyển vào hay rước ra thành phần trong heap (mức logic).L.O.4.5 – lúc này được cấu tạo heap bằng C/C++.L.O.4.6 – đối chiếu được và có tác dụng thực nghiệm nhận xét được các 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 thuộc với khái niệm về khóa, đụng độ và xử lý đụng độ.L.O.5.2 – biểu thị được bằng mã trả và mang lại ví dụ minh họa cho những hàm băm cơ bản.L.O.5.3 – bộc lộ được bằng mã giả và mang lại ví dụ minh họa cho những phương thức xử lý đụng độ.L.O.5.4 – hiện thực được kết cấu bảng băm bởi C/C++.L.O.5.5 – so sánh được và có tác dụng thực nghiệm đánh giá đượ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 đến xếpL.O.6.1 – Minh họa được bởi hình vẽ từng bước buổi giao lưu của các giải mã sắp xếp.L.O.6.2 – mô tả được bởi mã giả cho các giải thuật sắp tới xếp. L.O.6.3 – thực tại được các giải thuật bố trí 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 mã sắp xếp.L.O.6.5 – sử dụng được giải mã sắp xếp trong câu hỏi thực.Hiểu biết cơ bản về trang bị thịL.O.7.1 – vạc họa được bởi hình ảnh cho những khái niệm như vật dụng thị liên thông cùng không liên thông, thứ thị được đặt theo hướng và ko hướng, chu trình, v.v.L.O.7.2 – Vẽ được hình minh họa với 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ởi mã mang (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 kết cấu đồ thị; cũng tương tự mô tả được chúng bằng mã giả (mức logic).L.O.7.4 – Minh họa được bằng hình hình ảnh các cách thức duyệt thiết bị thị cơ phiên bản (depth first & bread-first).L.O.7.5 – thực tại được kết cấu lưu trữ đồ gia dụng 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ở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 hoạt động vui chơi của các giải thuật tìm đường ngắn nhất bởi Dijktra và giải mã tìm cây phủ tối tiểu bằng giải thuật Prim.Sử dụng đệ quyL.O.8.1 – diễn tả được những 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 mô tả các lần hotline hàm và 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 call đệ quy viết bằng C/C++.L.O.8.4 – cách tân và phát triển được giải thuật đệ 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 trên cây với tìm kiếm nhị phân, và đồ thị.L.O.8.5 – làm cho được xem sét để đối chiếu cách tiếp cận đệ quy và cách lặp.L.O.8.6 – mang lại được lấy ví dụ như minh họa sự tương quan giữa Backtracking cùng đệ 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 & 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.

Xem thêm: Cách Trị Mùi Hôi Vùng Kín - 6 Cách Loại Bỏ Mùi Hôi Vùng Kín Hiệu Quả

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