Bài Giảng Cấu Trúc Dữ Liệu Và Giải Thuật

     

Giới thiệu, câu chữ 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 kết cấu dữ liệu nền tảng. Môn học tập cũng hướng dẫn 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 tạo dữ liệu đó.Ôn lại về lập trình, những 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 thống kê giám sát và đệ qui.Các cấu trúc dữ liệu cùng sự phân tích chúng: danh sách; ông xã và hàng; cây, cây nhị phân, cây nhị phân tìm kiếm, AVL và đ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

tác dụng cần dành được

Phân tích lời giải L.O.1.1 – Định nghĩa được những khái niệm độ tinh vi và độ phức hợp trong các trường phù hợp “tốt nhất”, “xấu nhất”, và “trung bình”.L.O.1.2 – đối chiếu được những giải thuật và sử dụng được cam kết hiệu “Big O” để ghi ra độ phức tạp của giải mã cấu thành từ bỏ 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 ví dụ như và đối chiếu đượ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 gian trong giải thuật.L.O.1.5 – diễn tả được các chiến lược kiến tạo giải thuật và giải quyết bài toán.Sử dụng kết cấu dữ liệu danh sách, ông chồng và hàngL.O.2.1 – vạc họa được bởi hình hình ảnh cho: (a) danh sách hiện thực bởi mảng với bằng liên kết (con trỏ); (b) mang lại chồng; với (c) mang lại hàng chờ và hàng ngóng vòng (mức logic).L.O.2.2 – Viết được bằng mã mang mô tả cấu tạo lưu trữ cho: (a) list hiện thực bằng mảng và bởi liên kết; (b) mang đến chồng; với (c) mang lại hàng đợi 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 cấu trúc như danh sách, chồng và mặt hàng đợi; tương tự như mô tả được chúng bằng mã đưa (mức logic).L.O.2.4 – hiện nay được các cấu trúc danh sách, ông xã và mặt hàng đợi bởi C/C++ (mức physics)L.O.2.5 – thực hiện được danh sách, chồng, cùng hàng để xử lý bài toán thực, cũng như xem xét chọn lựa dạng hình hiện thực buổi tối ưu.L.O.2.6 – phân tích được và làm cho thí nghiệm reviews các cách tiến hành đã hổ trợ cho các kết cấu danh sánh, chồng, với hàng.Sử dụng cấu trúc câyL.O.3.1 – phân phát họa được bởi 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ã trả mô tả cấu trúc 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 mang lại các kết cấu cây; cũng giống như mô tả được chúng bằng mã đưa (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 – đã cho thấy được cùng vẽ hình minh họa về tất cả các trường mất cân bằng trong cây AVL cùng cây B, cũng giống như thực hiện từng bước để tái cân đối chúng trên hình mẫu vẽ (mức logic).L.O.3.6 – hiện thực được các cấu tạo cây nhị phân và 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 mang lại tìm kiếm.L.O.3.8 – so sánh được và làm thực nghiệm đánh giá được những phương thức vẫn 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 – chỉ ra rằng được những vận dụng cần mang đến HeapL.O.4.2 – tổng quát được bởi hình hình ảnh cho kết cấu 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 quan trọng cho cho cấu tạo heap; cũng tương tự mô tả được chúng bởi mã mang (mức logic).L.O.4.4 – demo được bằng hình ảnh các phương thức để đảm bảo an toàn tính chất của cấu trúc Heap khi chuyển vào hay mang ra bộ phận trong heap (mức logic).L.O.4.5 – hiện nay được cấu tạo heap bằng C/C++.L.O.4.6 – phân tích được và làm cho thực nghiệm đánh giá được các phương thức sẽ hổ trợ cho cấu tạo 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 định nghĩa về khóa, chạm độ và xử lý đụng độ.L.O.5.2 – biểu lộ được bởi mã đưa và mang đến ví dụ minh họa cho các hàm băm cơ bản.L.O.5.3 – mô tả được bằng mã mang và đến ví dụ minh họa cho những phương thức giải quyết đụ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 – phân tích được và có tác dụng thực nghiệm reviews được những phương thức sẽ hổ trợ cho kết cấu bảng băm.Phát triển những 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 mã sắp xếp.L.O.6.2 – thể hiện được bằng mã giả cho những giải thuật sắp xếp. L.O.6.3 – thực tại được các giải thuật thu xếp bằng C/C++ .L.O.6.4 – phân tích được và làm cho thực nghiệm review 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ơ phiên bản về đồ dùng thịL.O.7.1 – phát họa được bằng hình hình ảnh cho những khái niệm như thiết bị thị liên thông cùng không liên thông, đồ thị có hướng và không 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ữ mang lại đồ thị ở các dạng ma trận kề và list kề bởi mã trả (mức logic).L.O.7.3 – Liệt kê được các phương thức quan trọng cho đến các cấu trúc đồ 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ởi hình ảnh các cách thức duyệt vật thị cơ bạn dạng (depth first và bread-first).L.O.7.5 – hiện tại được cấu tạo lưu trữ đồ vật thì bằng C/C++.L.O.7.6 – lúc này được các phương thức duyệt nói trên bằng C/C++ và thực hiện 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à 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 – bộc lộ được các thành phần cơ phiên bản của một giải mã đệ quy.L.O.8.2 – Vẽ được cây mô tả những lần call 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 ví dụ như về một hàm điện thoại tư vấn đệ quy viết bởi C/C++.L.O.8.4 – phát triển được giải mã đệ quy cho những phương thức cần thiết của các cấu trúc: danh sách, cây, heap, tra cứu kiếm trên cây và tìm tìm nhị phân, với đồ thị.L.O.8.5 – có tác dụng được xem sét để đối chiếu cách tiếp cận đệ quy và cách lặp.L.O.8.6 – mang đến được lấy ví dụ minh họa sự liên 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 & 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: Top 7 Ứng Dụng Định Vị Bằng Số Điện Thoại, Theo Dõi Điện Thoại Theo Số

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

Xem thêm: Xem Tử Vi Tuổi Bính Tý 1996 Năm 2022 Nữ Mạng, Tử Vi Tuổi Bính Tý Năm 2022

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