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

Cấu Trúc Dữ Liệu Và Giải Thuật - Cao Hoàng Trụ - Đh Bách Khoa Hcm - Lý thuyết - Bài tập, thực hành - Đề thi

Giáo trình Tiếng Anh

Mathematics - algorithms - ROBERT SEDGEWICK.pdf
CO2003_CauTrucDuLieuvaGiaiThuat_Data Structures and Program Design in C++ - Robert L. Kruse.pdf
CO2003_CauTrucDuLieuvaGiaiThuat_Data Structures and Algorithms in C++ A. Drozdek.pdf
CO2003_CauTrucDuLieuvaGiaiThuat_Data Structure And Algorithms In C++ 2nd ed - Adam Drozdek.pdf
CO2003_CauTrucDuLieuvaGiaiThuat_Algorithms and Data Structures - Thin Book- Niklaus Wirth.pdf
CO2003_CauTrucDuLieuvaGiaiThuat_Algorithms - Robert Sedgewick and Kevin Wayne.pdf
CO2003_CauTrucDuLieuvaGiaiThuat.pdf

Giáo trình, bài giảng

ch0_thông tin chung.pdf
ch8-p2_đồ thị (phần 2).pdf
ch8-p1_cấu trúc đồ thị.pdf
ch7-p2_tìm kiếm - ii.pdf
ch7-p1_tìm kiếm.pdf
ch6_sắp xếp.pdf
ch5_cấu trúc cây.pdf
ch4_stack và queue.pdf
ch3_mảng và danh sách.pdf
ch2_giải thuật đệ qui.pdf
ch1_các kiến thức cơ bản.pdf
chuong6 tìm kiếm.pdf
chuong6.pdf
chuong5 các thuật toán sắp xếp.pdf
chuong5.pdf
chuong4 cây.pdf
chuong4.pdf
chuong3 các cấu trúc dữ liệu cơ bản.pdf
chuong3.pdf
chuong2.new.pdf
chuong2.các thuật toán đệ quy.pdf
chuong1_các khái niệm cơ bản.pdf
chuong1_cackhainiemcoban2.pdf
chap07graph.pdf
chap07 graph.pdf
ctdlgt_ptit-hcm.pdf
GiaoTrinh.pdf
CTDLGT_LT.pdf
CTDLGT.pdf
15. chuong 6 - các thuật toán nén dữ liệu.pdf
14. chuong 5 - b-tree.pdf
13. chuong 5 - cây do-den + aa.pdf
12. chuong 5 - cây avl + hash table.pdf
11. chuong 5 - bst + priority queue.pdf
10. chuong 5 - cây nhị phân.pdf
9. chuong 5 - các cấu trúc dữ liệu.pdf
8. chuong 4 - các khái niệm cơ bản.pdf
7. chuong 3 - thuật toán rabin karp.pdf
6. chuong 3 - brute force + kmp - các thuật toán tìm kiếm chuỗi.pdf
5. chuong 3 - tìm kiếm tuần tự - tìm kiếm nhị phân.pdf
4. chuong 2 - các thuật toán sắp xếp.pdf
3. chuong 1 - phân tích độ phức tạp của giải thuật.pdf
2. ctdl> -đề cương môn học.pdf
1. ctdl> - qui dinh can biet.pdf
ctdl-11-hash.pdf
ctdl-10-string matching.pdf
ctdl-09-data compression.pdf
ctdl-08-b cay.pdf
ctdl-07-23-234 tree.pdf
ctdl-06-tree.pdf
ctdl-05-basic data structures.pdf
ctdl-04-basic concepts-adt.pdf
ctdl-03-sort.pdf
ctdl-02-search.pdf
ctdl-01-basic concepts-bigo.pdf
ctdl-00-introduction-2017.pdf
chap 12 - multiway trees.pdf
chap 12 - multiway tree.pdf
chap 11- hash.pdf
chap 10 - sort.pdf
chap 9 - graph.pdf
chap 8 - heaps.pdf
chap 7b - avl.pdf
chap 7a - tree.pdf
chap 6 - recursion.pdf
chap 5 - searching.pdf
chap 4 - queue - 2009[1].pdf
chap 3b - stackapp.pdf
chap 3a - stack.pdf
chap 2 - list.pdf
chap 1_introduction.pdf
giáo trình ctdl & gt - đh cần thơ.pdf
mucluc.pdf
giáo trình ctdl & gt - đh bk tphcm.pdf
giai thuat va lap trinh(rat hay).pdf
ctdl 2005 chuong 18_ứng dụng danh sách liên kết và bảng băm .pdf
ctdl 2005 chuong 17_ứng dụng sinh các hoán vị.pdf
ctdl 2005 chuong 16_ứng dụng xử lý văn bản.pdf
ctdl 2005 chuong 15_ứng dụng của hàng đợi.pdf
ctdl 2005 chuong 13_đồ thị.pdf
ctdl 2005 chuong 12_bảng và truy xuất thông tin.pdf
ctdl 2005 chuong 11_hàng ưu tiên.pdf
ctdl 2005 chuong 10_cây nhiều nhánh.pdf
ctdl 2005 chuong 7_khóa.pdf
ctdl 2005 chuong 6_đệ quy.pdf
ctdl 2005 chuong 5_chuỗi ký tự.pdf
ctdl 2005 chuong 4_danh sách.pdf
ctdl 2005 chuong 3_hàng đợi.pdf
ctdl 2005 chuong 2_các cấu trúc dữ liệu.pdf
ctdl 2005 chuong 1_giới thiệu.pdf
ctdl_08_caynhiphancb.pdf
ctdl_07_caynhiphantimk.pdf
ctdl_06_cay.pdf
ctdl_05_listkep.pdf
ctdl_04_listdon.pdf
ctdl_03_ctdulieudong.pdf
ctdl_02_sxtk.pdf
ctdl_01_tquan.pdf
0courseintro new.pdf
slidectdl_phanthiha.pdf
chap00introduction_decrypted.pdf
chap00 introduction_decrypted.pdf
chap07graph_decrypted.pdf
chap07 graph_decrypted.pdf
chap06 searching_decrypted.pdf
chap06searching_decrypted.pdf
chap05sorting_decrypted.pdf
chap05 sorting_decrypted.pdf
chap04trees_decrypted.pdf
chap04 trees_decrypted.pdf
chap03 basic ds_decrypted.pdf
chap03basicds_decrypted.pdf
chap02 recur_decrypted.pdf
chap02recur_decrypted.pdf
chap01 fundamentals_decrypted.pdf
chap01fundamentals_decrypted.pdf
ref_red-black trees.pdf
ref_quicksort.pdf
ref_hash tables.pdf
ref_binary search trees.pdf
ref_b-tree.pdf
chapter07-compression.pdf
chapter06-hash_table.pdf
chapter05-adt_tree.pdf
chapter05-adt_stack_queue.pdf
chapter05-adt_red_black_tree.pdf
chapter05-adt_priority_queue.pdf
chapter05-adt_m-tree.pdf
chapter05-adt_avl_tree.pdf
chapter05-adt_array_vs_list.pdf
chapter05-adt_aa_tree.pdf
chapter04-sorting.pdf
chapter03-searching.pdf
chapter02-complexity_analysis.pdf
chapter01-introduction.pdf
exercisechapter7.pdf
exercise.chapter7.graph.pdf
exercise.chapter6.advanced.searching.pdf
exercise.chapter5.sorting.pdf
exercise.chapter5.function.pdf
examples.chapter7.pdf
examples.chapter5.pdf
chapterxx.review.pointer.pdf
chapter7.struct.pdf
chapter7.graph.pdf
chapter6.searching(advanced).pdf
chapter5.sorting.pdf
chapter5.function.pdf
chapter4.searching.(basic).pdf
chapter4.3.avl.splay.2_3tree.pdf
chapter4.2.binary search tree.pdf
chapter4.2.binarysearchtree.pdf
chapter4.2.avl.splay.2-3.tree.pdf
chapter4.1.searching(basic).pdf
chapter3.tree.pdf
chapter2.5._2.6.stack.queue.pdf
chapter2.2.stack.queue.pdf
chapter2.1.pdf
chapter2.1-2.4.basic data structures.pdf
chapter2.1-2.4.basicdatastructures.pdf
chapter1.3.recursion.pdf
chapter1.2.analysis.algorithm.pdf
chapter1.1.principle.concepts.pdf
chapter0.intro.pptx
chapter0.intro.pdf
chapter.3.tree.pdf
chapter.1.3.recursion.pdf
chapter.1.3.pdf
chapter.1.2.pdf
chapter.1.2.analysis.algorithm.pdf
chapter.1.1.principle.concepts.pdf
chapter.1.1.pdf
lecture - avl tree.pdf
hashing-2007.pdf
chapter12 - multiway trees - 2009.pdf
chapter10 - sort - 2009.pdf
chapter9 - graph - 2009.pdf
chapter8 - heaps - 2009.pdf
chapter6-2008-multiway tree.pdf
chapter3_part2_queue_implementation.pdf
chapter3_part1_stack_implementation.pdf
chapter2_linkedlist_implementation.pdf
chapter1_introduction.pdf

Bài tập, thực hành

btl-chuong4.pdf
bt04-sol.pdf
baitapdequi.pdf
homework 6_run-length encoding, nén huffman tĩnh.pdf
homework 5.5_b-tree.pdf
homework 5.4_cây avl, cây đỏ-đen, cây aa.pdf
homework 5.3_cây nhị phân tìm kiếm, priority queue.pdf
homework 5.2_ngăn xếp, hàng đợi.pdf
homework 5.1_danh sách liên kết.pdf
homework 3_giải thuật brute-force.pdf
homework 2_cài đặt giải thuật 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
homework 1_tính độ phức tạp f(n) của các giải thuật.pdf
bài tập ôn r-3.pdf
bài tập ôn r-2.pdf
bài tập ôn r-1.pdf
[paper] aa - balanced search trees made simple.pdf
[huong dan] thuật toán tính giá trị biểu thức postfix.pdf
[huong dan] thuật toán balan ngược reverse polish notation.pdf
[huong dan] nmlt_cài đặt tham số dòng lệnh trên visual c++ 6.0.pdf
ctdl-lab10-string_matching.pdf
ctdl-lab09-bang_bam.pdf
ctdl-lab08-tim_kiem.pdf
ctdl-lab07-cac_thuat_toan_sap_xep.pdf
ctdl-lab06-nen_huffman.pdf
ctdl-lab05-cay_can_bang-avl.pdf
ctdl-lab04-cay_nhi_phan_tim_kiem.pdf
ctdl-lab03-stack_va_queue.pdf
ctdl-lab02-danh_sach_lien_ket.pdf
ctdl-lab01-on_tap.pdf
tut4.pdf
tut4-solution.pdf
solution_tut_5.pdf
sol lab 5 - week 13.pdf
sol lab 4 - week 11.pdf
sol exer 6 - week 14.pdf
listsample.cpp
lab6.pdf
lab5.pdf
lab4.pdf
lab3_v2.pdf
lab3-solution.pdf
lab2.pdf
assignment3_v1.1.pdf
assignment2_v1.2.pdf
assignment2_v1.1.pdf
assignment+3_log.pdf
assignment+2_log.pdf
assignment+2_log-1.pdf
14_tut6_sorting.pdf
10_tut5_graph.pdf
06_tut3_queuerecursion_solution.pdf
06_tut3_queuerecursion.pdf
05_lab2_solution-new.pdf
04_tut2_solution.pdf
04_tut2_linkedliststack.pdf
03_lab1_v3.pdf
03_lab1_solution-new.pdf
02_tut1_solution.pdf
02_tut1_complexity.pdf
rpn.pdf
hdth buoi 2.pdf
de th.pdf
ctdl.pdf
ctdl-lab01-on_tap.pdf
balan nguoc.pdf
bai tap cay nhi phan.pdf
b1.pdf
6.phuongphapchiadetri.pdf
exercise.chapter7.pdf
exercise.chapter7.graph.pdf
exercise.chapter6.advanced.searching.pdf
exercise.chapter5.sorting.pdf
exercise.chapter5.function.pdf
exercise.chapter4.searching.(basic).pdf
exercise.chapter3.tree.pdf
exercise.chapter2.1.pdf
exercise.chapter.1.3.pdf
exercise.chapter.1.2.pdf
exercise.chapter.1.1.pdf
tutorial+6+-+hashing+and+multi-way+tree+-+solution.pdf
tutorial+6+-+hashing+_+multiwaytree.pdf
tutorial+5+-+sorting.pdf
tutorial+5+-+sorting+-+solution.pdf
tutorial+4+-+bst+avl.pdf
tutorial+4+-+bst+avl+-+solution.pdf
tutorial+3+-+stack+and+queue+-+solution.pdf
tutorial+2+-+linked+list+-+solution.pdf
tutorial+1.pdf
tutorial+1+-+c+primer+-+solution.pdf
tut+3.pdf
tut+3-1.pdf
tut+2_v1.1.pdf
lab4.pdf
lab3_binarytree.pdf
lab+5+-+sorting+_+heap.pdf
lab+5+-+sorting+_+heap+-+solution.pdf
lab+4+-+binary+search+tree+-+solution.pdf
lab+3+-+binary+tree+-+solution.pdf
lab+2+-+linked+list.pdf
lab+2+-+linked+list+-+solution.pdf
lab+1+-+cc+++primer.pdf
assignment1.pdf

Đề thi

img_0460.jpg
img_0459.jpg
img_0458.jpg
img_0456.jpg
14 đề thi thực hành ctdl+gt.pdf
14 đề thi thực hành ctdl+gt.doc
solution.dsa.test02.pdf
solution.dsa.test01.pdf
solution.dsa.test.02.10.12.2010.pdf
solution.dsa.test.01.10.12.2010.pdf
solution.chap.3.pdf
solution.chap.3.docx
dsa.test02.pdf
dsa.test01.pdf
dsa.final.03_reexam.pdf
dsa.exam.20132.01.pdf
ctdl _ gt 17 - 18 cntn.pdf
ctdl _ gt 17 - 18 clc.pdf
ctdl _ gt 16 - 17 cntn.pdf
ctdl _ gt 16 - 17.pdf
ctdl _ gt 15 - 16.pdf
ctdl _ gt 14 - 15.pdf
đề cuối kỳ 2017_2.jpg
đề cuối kỳ 2017.jpg
hk1 2018-2019_p2.jpg
hk1 2018-2019.jpg
đề thi giữa kỳ hk1 2009.pdf
đề thi giữa kỳ hk1 2009 +solution.pdf
đề thi cuối học kỳ 1 2012 – 2013_datastructure_241112_updated.pdf
đề kiểm tra giữa học kỳ 1 2011 – 2012.pdf
đề kiểm tra giữa học kỳ 1 2011 – 2012+ solution.pdf
đề kiểm tra giữa học kỳ 1 2010 – 2011.pdf
đề kiểm tra giữa học kỳ 1 2010 – 2011 +solution.pdf
kiểm tra giữa kỳ 2012-2013_solution.pdf
kiểm tra giữa kỳ 2012-2013.pdf

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

Môn học nhằm cung cấp 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 cũng hướng dẫn sinh viên hiểu, phân tích và đánh giá đượ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 dữ liệu trong C/C++, đặc biệt là cấu trúc và con trỏ. Giới thiệu về độ phức tạp tính toán và đệ qui. Các cấu trúc dữ liệu và sự phân tích chúng: danh sách; chồng 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 thuật sắp xếp; bảng băm; và đồ thị.

Kết quả cần đạt được

Phân tích giải thuật L.O.1.1 – Định nghĩa được các khái niệm độ phức tạp và độ phức tạ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 các giải thuật và sử dụng được ký hiệu “Big O” để ghi ra độ phức tạ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à lặp. L.O.1.3 – Liệt kê được, cho được ví dụ và so sánh đượ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 bằng giữa bộ nhớ và thời gian trong giải thuật. L.O.1.5 – Mô tả được các chiến lược thiết kế 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, chồng và hàng L.O.2.1 – Phát họa được bằng hình ảnh cho: (a) danh sách hiện thực bằng mảng và bằng liên kết (con trỏ); (b) cho chồng; và (c) cho hàng đợi và hàng đợi vòng (mức logic). L.O.2.2 – Viết được bằng mã giả mô tả cấu trúc lưu trữ cho: (a) danh sách hiện thực bằng mảng và bằng liên kết; (b) cho chồng; và (c) cho hàng đợi và hàng đợi 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, chồng và hàng đợi; cũng như mô tả được chúng bằng mã giả (mức logic). L.O.2.4 – Hiện thực được các cấu trúc danh sách, chồng và hàng đợi bằng C/C++ (mức physics) L.O.2.5 – Sử dụng được danh sách, chồng, và hàng để giải quyết bài toán thực, cũng như cân nhắc chọn lựa kiểu hiện thực tối ưu. L.O.2.6 – Phân tích được và làm thí nghiệm đánh giá các phương thức đã hổ trợ cho các cấu trúc danh sánh, chồng, và hàng. Sử dụng cấu trúc cây L.O.3.1 – 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 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ã giả 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 các phương thức cần thiết cho cho 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 được và cho ví dụ minh họa về tầm quan trọng của tính cân bằng trong cây. L.O.3.5 – Chỉ ra được và vẽ hình minh họa về tất cả các trường mất cân bằng trong cây AVL và cây B, cũng như thực hiện từng bước để tái cân bằng chúng trên hình vẽ (mức logic). L.O.3.6 – Hiện thực được các cấu trúc 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à cây AVL để giải quyết 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à làm thực nghiệm đánh giá được các phương thức đã hổ trợ cho các cấu trúc cây nhị phân và cây AVL. Sử dụng Heap L.O.4.1 – Chỉ ra được những ứng dụng cần đến Heap L.O.4.2 – Phác họa được bằng hình ảnh cho cấu trúc Heap và nêu ra sự liên quan đến lưu 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 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 phương thức để đảm bảo tính chất của cấu trúc Heap khi đưa vào hay lấy ra phần tử trong heap (mức logic). L.O.4.5 – Hiện thực được cấu trúc heap bằng C/C++. L.O.4.6 – Phân tích được và làm 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 cùng với khái niệm về khóa, đụng độ và giải quyết đụng độ. L.O.5.2 – Mô tả được bằng mã giả và cho 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ã giả và cho ví dụ minh họa cho các phương thức giải quyết đụng độ. L.O.5.4 – Hiện thực được cấu trúc bảng băm bằng C/C++. L.O.5.5 – Phân tích được và làm thực nghiệm đánh giá được các phương thức đã hổ trợ cho cấu trúc bảng băm. Phát triển các giải thuật sắp xếp L.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 thuật sắp xếp. L.O.6.2 – Mô tả được bằng mã giả cho các giải thuật sắp xếp. L.O.6.3 – Hiện thực được các giải thuật sắp xếp 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 thuật sắp xếp. L.O.6.5 – Sử dụng được giải thuật sắp xếp trong bài toán thực. Hiểu biết cơ bản về đồ thị L.O.7.1 – Phát họa được bằng 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à không hướng, chu trình, v.v. L.O.7.2 – Vẽ được hình minh họa và 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ằng mã giả (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 trúc đồ thị; cũng như mô tả được chúng bằng mã giả (mức logic). L.O.7.4 – Minh họa được bằng hình ảnh các phương pháp duyệt đồ thị cơ bản (depth first and bread-first). L.O.7.5 – Hiện thực được cấu trúc lưu trữ đồ thì bằng C/C++. L.O.7.6 – Hiện thực được các phương pháp 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ằng hình vẽ từng bước hoạt động của các giải thuật tìm đường ngắn nhất bằng Dijktra và giải thuật tìm cây phủ tối tiểu bằng giải thuật Prim. Sử dụng đệ quy L.O.8.1 – Mô tả được các 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ả các lần gọi hàm và giá trị của các tham số được truyền vào các hàm đó. L.O.8.3 – Cho được ví dụ về một hàm gọi đệ quy viết bằng C/C++. L.O.8.4 – Phát triển được giải thuật đệ 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 trên cây và tìm kiếm nhị phân, và đồ thị. L.O.8.5 – Làm được thí nghiệm để so sánh cách tiếp cận đệ quy và cách lặp. L.O.8.6 – Cho được ví dụ minh họa sự liên quan giữa Backtracking và đệ 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 and B.A. Forouzan, Thomson Learning Inc., 2001. Sách tham khảo: [1] “Data Structures and Algorithms in C++”, A. Drozdek, Thomson Learning Inc., 2005. [2] “C/C++: How to Program”, 7th Ed. – Paul Deitel and Harvey Deitel, Prentice Hall, 2012. [3] Internet.