Cấu trúc dữ liệu

Cấu trúc dữ liệu và giải thuật là một trong những môn học cơ bản của sinh viên ngành Công nghệ thông tin. Các cấu trúc dữ liệu và các giải thuật được xem như là 2 yếu tố quan trọng nhất trong lập trình, đúng như câu nói nổi tiếng của Niklaus Wirth: Chương trình = Cấu trúc dữ liệu + Giải thuật (Programs = Data Structures + Algorithms). Nắm vững các cấu trúc dữ liệu và các giải thuật là cơ sở để sinh viên tiếp cận với việc thiết kế và xây dựng phần mềm cũng như sử dụng các công cụ lập trình hiện đại.

Cấu trúc dữ liệu

Mức độ cơ bản:

• Ngăn xếp(stack)
• Hàng đợi(Queue)
• Danh sách liên kết
• Cây nhị phân

Mức độ trung bình:

• Heap
• Priority Queue
• Huffman Tree
• Union Find
• Tries
• Bảng băm – Hash Table
• Tree Map

Trình độ nâng cao:

• Segment Tree
• Binary Indexed Tree
• Suffix Array
• Sparse Table
• Lowest Common Ancestor
• Range Tree.

Giải thuật/ thuật toán

• Searching(Linear search, Binary search, Ternary search)
• Sorting (Bubble sort, Insertion sort, Merge sort, Quick sort, Radix sort, …)
• Các giải thuật tham lam
• Giải thuật đồ thị(BFS, DFS, Luồng cực đại, Cây khung nhỏ nhất, Đường đi ngắn nhất,…)
• Giải thuật string(KMP, Z, String search, …)
• Quy hoạch động
• …

Các tài liệu bổ sung

• Giải thuật và lập trình – thầy Lê Minh Hoàng
• Introduction to Algorithms – bản tiếng Việt