BÀI GIẢNG 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 - triết lý - bài 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ừ bỏ tăng dần.pdf

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

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

kết quả cần đã có đượ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 tạp và độ tinh vi trong những trường hợp “tốt nhất”, “xấu nhất”, và “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” để ghi ra độ phức tạp của giải thuật cấu thành từ bỏ các kết cấu đ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 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 đối giữa bộ nhớ và thời hạn trong giải thuật.L.O.1.5 – miê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, ck và hàngL.O.2.1 – phạt họa được bởi hình ảnh cho: (a) list hiện thực bằng mảng cùng bằng links (con trỏ); (b) đến chồng; cùng (c) cho hàng chờ 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) danh sách hiện thực bằng mảng và bởi liên kết; (b) cho chồng; và (c) mang lại hàng chờ và hàng chờ 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 cấu tạo như danh sách, ông xã và hàng đợi; tương tự như mô tả được chúng bởi mã mang (mức logic).L.O.2.4 – thực tại được các kết cấu danh sách, ông xã và hàng đợ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ư suy xét chọn lựa hình dáng hiện thực về tối ưu.L.O.2.6 – so với được và làm thí nghiệm reviews các cách tiến hành đã hổ trợ mang lại các cấu trúc 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ằng hình ảnh cho những 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ằng mã trả mô tả cấu tạo 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 cần thiết cho cho các cấu trúc cây; cũng giống như mô tả được chúng bởi mã trả (mức logic).L.O.3.4 – chỉ ra rằng được và đến ví dụ minh họa về tầm quan trọng đặc biệt của tính thăng bằng trong cây.L.O.3.5 – chỉ ra được cùng vẽ hình minh họa về toàn bộ các trường mất thăng bằng trong cây AVL cùng cây B, cũng giống như thực hiện từng bước một để tái cân 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ởi C/C++L.O.3.7 – áp dụng được cây nhị phân cùng 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 – so với được và có tác dụng thực nghiệm reviews được các phương thức sẽ hổ trợ mang đến các cấu tạo cây nhị phân và cây AVL.Sử dụng HeapL.O.4.1 – đã cho thấy được những vận dụng cần cho HeapL.O.4.2 – demo được bằng hình hình ảnh cho cấu tạo Heap cùng nêu ra sự tương quan đến tàng trữ ở dạng mảng.L.O.4.3 – Liệt kê được những phương thức quan trọng cho cho kết cấu heap; cũng tương tự mô tả được chúng bởi mã trả (mức logic).L.O.4.4 – demo được bằng hình hình ảnh các thủ tục để bảo đảm an toàn tính hóa học của cấu trúc Heap khi chuyển vào hay đem ra thành phần trong heap (mức logic).L.O.4.5 – hiện tại đượ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 reviews được các phương thức vẫn 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, chạm độ và giải quyết và xử lý đụng độ.L.O.5.2 – bộc lộ được bởi mã giả và mang lại ví dụ minh họa cho những hàm băm cơ bản.L.O.5.3 – diễn tả được bởi mã trả và cho ví dụ minh họa cho những phương thức xử lý đụng độ.L.O.5.4 – hiện tại được cấu tạo bảng băm bởi C/C++.L.O.5.5 – so sánh được và làm thực nghiệm reviews được những phương thức vẫn hổ trợ cho kết cấu 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ở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 đạt được bởi mã giả cho những giải thuật sắp đến xếp. L.O.6.3 – thực tại được những 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ận xét các lời giải sắp xếp.L.O.6.5 – sử dụng được giải mã sắp xếp trong việc thực.Hiểu biết cơ bản về đồ vật thịL.O.7.1 – phân phát họa được bởi 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, vật 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ới mô tả cấu trúc lưu trữ mang đến đồ thị ở những 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 quan trọng cho cho các cấu trúc đồ thị; cũng tương tự mô tả được chúng bằng mã mang (mức logic).L.O.7.4 – Minh họa được bởi hình ảnh các cách thức duyệt vật thị cơ bạn dạng (depth first and bread-first).L.O.7.5 – hiện thực được cấu trúc lưu trữ trang bị thì bằng C/C++.L.O.7.6 – lúc này được các phương pháp 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 của các lời giải tìm con đường ngắn nhất bởi Dijktra và lời giải tìm cây phủ buổi tối tiểu bằng giải mã Prim.Sử dụng đệ quyL.O.8.1 – trình bày được những 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ả những lần điện thoại tư vấn hàm và giá trị của những tham số được truyền vào những hàm đó.L.O.8.3 – mang đến được lấy ví dụ về một hàm điện thoại tư vấn đệ quy viết bởi C/C++.L.O.8.4 – cải tiến và phát triển được lời giải đệ quy cho các phương thức cần thiết của những 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 được nghiên cứu để so sánh cách tiếp cận đệ quy và bí quyết lặp.L.O.8.6 – cho được lấy ví dụ như 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 và Algorithms in C++”, A. Drozdek, Thomson Learning Inc., 2005.

Xem thêm: Soạn Bài Từ Ngôn Ngữ Chung Đến Lời Nói Cá Nhân Tiếp Theo ) Trang 35

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

Xem thêm: Bài 29 Trang 79 Sgk Toán 9 Tập 2, Bài Tập 29 Trang 79 Sgk Toán 9 Tập 2

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