Tổng quan về giáo trình

Tài liệu học tập "Bài 4: Cấu trúc dữ liệu" do ThS. Trịnh Thành Trung (Trường Công nghệ Thông tin và Truyền thông – Đại học Bách khoa Hà Nội, liên hệ qua trungtt@soict.vn) biên soạn. Bài học này thuộc khối kiến thức cơ sở ngành của chương trình đào tạo Cử nhân và Kỹ sư các ngành Khoa học Máy tính, Kỹ thuật Phần mềm và Công nghệ Thông tin.

Mục tiêu học tập của tài liệu tập trung vào việc cung cấp cho người học hiểu biết hệ thống về bản chất dữ liệu, từ mức lưu trữ vật lý đến các cấu trúc dữ liệu trừu tượng. Người học được trang bị khả năng phân biệt kiểu dữ liệu cơ bản với kiểu dữ liệu có cấu trúc; nắm vững nguyên lý hoạt động, ưu nhược điểm của các dạng lưu trữ tuần tự và liên kết; đồng thời có thể tự cài đặt và vận hành các cấu trúc dữ liệu nền tảng như mảng, danh sách kế tiếp, danh sách nối đơn, danh sách nối kép và ngăn xếp bằng ngôn ngữ lập trình C.

Cấu trúc tài liệu được thiết kế theo tiến trình logic chặt chẽ: bắt đầu từ việc phân loại dữ liệu theo mức độ trừu tượng hóa, đi qua các cấu trúc tuyến tính tĩnh, chuyển tiếp sang cấu trúc tuyến tính động, và cuối cùng là cấu trúc dữ liệu trừu tượng có kiểm soát truy cập (ngăn xếp). Cách tiếp cận này giúp người học hiểu rõ nguyên nhân xuất hiện của các cấu trúc dữ liệu mới nhằm khắc phục hạn chế về bộ nhớ và hiệu năng của cấu trúc trước đó.

Điểm đặc thù của bài giảng là việc kết hợp song song giữa giải thuật dạng mã giả (pseudocode) với các đoạn mã nguồn C hoàn chỉnh, xử lý trực tiếp trên con trỏ và bộ nhớ động (malloc, free), đồng thời minh họa giải thuật bằng các bài toán chuyển đổi cơ số cụ thể.

Nội dung kiến thức cốt lõi

Các chương/chủ đề chính

Nội dung của bài giảng được chia thành 4 chủ đề kỹ thuật trọng tâm:

  1. Khái niệm dữ liệu, kiểu dữ liệu và cấu trúc dữ liệu: Tài liệu thiết lập thang phân cấp lưu trữ dữ liệu từ mức máy (Machine Level Data Storage – chuỗi bit nhị phân 01001100...), qua kiểu dữ liệu cơ bản (Primitive Data Types như 28, 3.1415, 'A'), đến cấu trúc dữ liệu cơ bản (Basic Data Structures gồm array, list, stack, queue) và cấu trúc dữ liệu bậc cao (High-Level Data Structures gồm hash table, tree). Bài học phân định rõ:

    • Kiểu dữ liệu cơ bản: Biểu diễn dữ liệu nguyên tử không thể phân chia (trong C/C++ gồm int, long, char, bool với các phép toán +, -, *, /).
    • Kiểu dữ liệu có cấu trúc: Được xây dựng từ các kiểu cơ bản hoặc kiểu cấu trúc khác, do ngôn ngữ định nghĩa sẵn hoặc do lập trình viên thiết lập.

  2. Mảng (Array) và Danh sách kế tiếp (Sequential List):

    • Mảng: Là dãy hữu hạn các phần tử liên tiếp cùng kiểu và cùng tên, gồm một hoặc nhiều chiều (DataType ArrayName[size]; hoặc DataType ArrayName[size 1]...[size n];), kích thước cố định tại thời điểm biên dịch.
    • Danh sách: Tập hợp các phần tử cùng kiểu với số lượng biến động, phân chia thành tuyến tính (có phần tử đầu/cuối, thứ tự trước/sau cố định) và phi tuyến tính.
    • Danh sách kế tiếp: Lưu trữ trên vector các ô nhớ liền kề. Tài liệu định nghĩa 10 thao tác chuẩn: create, isEmpty, isFull, sizeOf, clear, insert, remove, retrieve, replace, traverse. Giải thuật chèn (Insert) và xóa (Remove) được chi tiết hóa bằng mã giả với các điều kiện kiểm tra biên: tràn danh sách (overflow), rỗng danh sách (underflow), và lỗi chỉ số (range_error).

  3. Danh sách móc nối (Linked List):

    • Danh sách nối đơn: Mỗi phần tử là một nút (Node) gồm thành phần dữ liệu (INFO hoặc struct hoso data) và con trỏ NEXT trỏ đến nút kế tiếp. Quản lý danh sách thông qua con trỏ đầu Head. Cài đặt mã nguồn C cho các hàm: FindNode (tìm kiếm phần tử x), InsertNode (chèn nút mới với con trỏ cấp hai Node **head), DeleteNode (xóa nút có giá trị x), và DestroyList (giải phóng toàn bộ vùng nhớ bằng free).
    • Danh sách nối kép: Mỗi nút có hai con trỏ prev và next, cho phép duyệt hai chiều. Tài liệu cung cấp kỹ thuật sử dụng nút đầu giả (dummy head) với trạng thái rỗng Head->next = Head; Head->prev = Head; nhằm chuẩn hóa các thao tác insertNode và deleteNode mà không cần xử lý riêng biệt các trường hợp biên tại đầu hoặc cuối danh sách.

  4. Ngăn xếp (Stack) và Cài đặt mảng động: Ngăn xếp là danh sách tuyến tính tuân thủ nguyên tắc LIFO (Last In, First Out), trong đó thao tác thêm (Push) và xóa (Pop) chỉ thực hiện tại một đầu duy nhất gọi là đỉnh (top). Tài liệu định nghĩa cấu trúc dữ liệu IntStack trên mảng động gồm các trường: con trỏ stackArr, biến đếm count, giới hạn stackMax, và chỉ số top. Toàn bộ các thao tác CreateStack, PushStack, PopStack, TopStack, IsEmptyStack, IsFullStack được cài đặt chi tiết bằng ngôn ngữ C.

Kiến thức nền tảng được xây dựng

  • Lý thuyết phân loại và tổ chức dữ liệu: Mô hình hóa mối liên kết giữa dữ liệu thành phần và hệ thống thao tác đặc trưng cho từng kiểu dữ liệu.
  • Nguyên lý quản trị bộ nhớ máy tính: Phân biệt cơ chế cấp phát tĩnh trên vùng nhớ liên tục (độ phức tạp truy cập $O(1)$ nhưng cố định kích thước) với cấp phát động rời rạc thông qua con trỏ (kích thước linh hoạt, giảm thiểu chi phí dịch chuyển bộ nhớ khi chèn/xóa).
  • Nguyên tắc thiết kế giải thuật cơ bản: Cơ chế kiểm tra điều kiện tiên quyết (preconditions) và điều kiện hậu nghiệm (postconditions), kiểm soát lỗi tràn bộ nhớ và giải phóng tài nguyên.

Kỹ năng phát triển

  • Kỹ năng kỹ thuật (Technical skills): Cài đặt cấu trúc dữ liệu bằng ngôn ngữ C; thao tác trực tiếp với con trỏ đơn, con trỏ kép (Node **head), cấu trúc tự trỏ (struct Node*); sử dụng các hàm cấp phát bộ nhớ chuẩn malloc và free.
  • Kỹ năng phân tích (Analytical skills): Đánh giá và so sánh chi phí tính toán giữa danh sách kế tiếp (tốn kém thao tác dời phần tử entry[i+1] = entry[i]) và danh sách móc nối (chỉ cần tái cấu trúc liên kết con trỏ).
  • Kỹ năng thực hành giải quyết bài toán (Practical competencies): Vận dụng cấu trúc dữ liệu ngăn xếp để hiện thực hóa thuật toán chuyển đổi hệ cơ số từ thập phân sang các hệ cơ số khác (cơ số 8, cơ số 4, cơ số 2).

Phương pháp giảng dạy và học tập

Tài liệu áp dụng phương pháp sư phạm tiếp cận từ dưới lên (Bottom-Up Approach), xuất phát từ cấu trúc lưu trữ nhị phân ở tầng phần cứng, đi qua các kiểu dữ liệu nguyên thủy của ngôn ngữ lập trình, sau đó xây dựng nên các cấu trúc dữ liệu trừu tượng.

Quy trình giảng dạy mỗi cấu trúc dữ liệu tuân theo cấu trúc chuẩn hóa 4 bước:

  1. Định nghĩa trừu tượng: Trình bày mô hình toán học và các đặc tính liên kết của cấu trúc.
  2. Thiết kế giải thuật: Trình bày mã giả mô tả luồng điều khiển, điều kiện biên và các phép biến đổi dữ liệu.
  3. Hiện thực hóa mã nguồn: Viết mã C chuẩn xác, minh họa việc định nghĩa struct, cấp phát bộ nhớ và xử lý con trỏ.
  4. Đánh giá hiệu năng và so sánh: Đối chiếu ưu điểm và hạn chế giữa các giải pháp lưu trữ khác nhau.

Hệ thống bài tập và thực hành trong tài liệu được thiết kế bám sát mã nguồn:

  • Bài tập cài đặt: Hiện thực hóa các hàm quản trị danh sách liên kết (FindNode, InsertNode, DeleteNode, DestroyList) và ngăn xếp (CreateStack, PushStack, PopStack).
  • Bài tập ứng dụng thực tế: Cài đặt thuật toán đổi cơ số thập phân sang bát phân, tứ phân và nhị phân sử dụng ngăn xếp.

Phương pháp đánh giá kết quả học tập tập trung vào hai tiêu chí: tính chính xác của giải thuật (không xảy ra lỗi bộ nhớ, xử lý trọn vẹn các trường hợp rỗng, đầy, ngoài khoảng) và hiệu quả cài đặt (tối ưu số lần thay đổi con trỏ, giải phóng bộ nhớ đúng quy cách). Đối với việc tự học, tài liệu cung cấp chỉ dẫn rõ ràng: người học cần vẽ sơ đồ liên kết con trỏ trước khi viết mã và tự cài đặt lại các thuật toán từ mã giả nhằm kiểm tra độ hiểu bản chất.

Điểm nổi bật và cập nhật

Nội dung bài giảng thể hiện tính hệ thống và chuẩn xác về mặt kỹ thuật thông qua các điểm cụ thể:

  • Tính trực quan trong phân loại dữ liệu: Phân tách rành mạch các tầng dữ liệu từ Machine Level (01001100...), Primitive Types, Basic Data Structures đến High-Level Data Structures, giúp người học định vị rõ vai trò của từng cấu trúc trong kiến trúc phần mềm.
  • Kỹ thuật tối ưu hóa mã nguồn với nút đầu giả (Dummy Head Node): Trong phần danh sách nối kép, tài liệu giới thiệu kỹ thuật sử dụng nút đầu giả với liên kết xoay vòng (Head->next = Head; Head->prev = Head;). Kỹ thuật này loại bỏ hoàn toàn sự cần thiết của các câu lệnh rẽ nhánh phức tạp khi thao tác tại các vị trí biên (đầu danh sách, cuối danh sách).
  • Tính chuẩn xác trong quản lý bộ nhớ: Mọi thao tác thêm và xóa phần tử trên danh sách liên kết và ngăn xếp đều gắn liền với việc kiểm tra con trỏ NULL, cấp phát malloc(sizeof(Node)) và thu hồi vùng nhớ free(currNode), rèn luyện tư duy lập trình an toàn bộ nhớ trong C.
  • Minh họa ứng dụng bằng dữ liệu thực tế: Bài toán đổi cơ số thập phân sang các hệ cơ số khác nhau được lượng hóa bằng các phép tính cụ thể:
    • Hệ bát phân: $28_{10} = 3 \times 8^1 + 4 \times 8^0 = 34_8$.
    • Hệ tứ phân: $72_{10} = 1 \times 4^3 + 0 \times 4^2 + 2 \times 4^1 + 0 \times 4^0 = 1020_4$.
    • Hệ nhị phân: $53_{10} = 1 \times 2^5 + 1 \times 2^4 + 0 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 110101_2$.

Đối tượng sử dụng giáo trình

  • Sinh viên đại học: Sinh viên năm thứ nhất hoặc năm thứ hai theo học các ngành Công nghệ Thông tin, Khoa học Máy tính, Kỹ thuật Máy tính và Hệ thống Thông tin đang học phần "Cấu trúc dữ liệu và giải thuật".
  • Yêu cầu kiến thức tiên quyết (Prerequisites):
    • Nắm vững lập trình C cơ bản: cú pháp, các kiểu dữ liệu cơ bản (int, float, char), câu lệnh rẽ nhánh (if-else), vòng lặp (for, while).
    • Hiểu nguyên lý con trỏ (pointer), địa chỉ bộ nhớ và các thao tác cấp phát động (malloc, free, sizeof).
    • Khái niệm về kiểu dữ liệu do người dùng định nghĩa (struct, typedef).
  • Giảng viên: Sử dụng tài liệu làm khung bài giảng lý thuyết và giáo án thực hành phòng máy; sử dụng các đoạn mã nguồn chuẩn và mã giả trong tài liệu để xây dựng ngân hàng đề thi và bài tập lớn.
  • Người tự học và lập trình viên: Dùng làm tài liệu tham khảo kỹ thuật để củng cố nền tảng cấu trúc dữ liệu mức thấp, hiểu rõ cơ chế vận hành bộ nhớ bên dưới các thư viện trừu tượng hóa bậc cao.

Câu hỏi thường gặp

1. Giáo trình này phù hợp với ai?

Tài liệu được biên soạn cho sinh viên bậc đại học thuộc khối ngành Công nghệ Thông tin và Khoa học Máy tính cần học lý thuyết và thực hành cấu trúc dữ liệu cơ sở, cũng như lập trình viên cần ôn tập kỹ thuật quản trị bộ nhớ và cài đặt cấu trúc dữ liệu bằng C.

2. Cần kiến thức nền nào để học?

Người học cần hoàn thành môn học Nhập môn lập trình hoặc Kỹ thuật lập trình C/C++, hiểu rõ cơ chế hoạt động của biến con trỏ, mảng, kiểu cấu trúc (struct), và việc cấp phát/thu hồi bộ nhớ động qua malloc và free.

3. Điểm khác biệt với giáo trình khác?

Tài liệu trình bày song song cả hai dạng biểu diễn: mã giả thuật toán tổng quát và mã nguồn C chi tiết; cung cấp giải pháp xử lý danh sách nối kép bằng nút đầu giả; phân tích cụ thể các điều kiện lỗi hệ thống (overflow, underflow, range_error).

4. Làm sao để tự học hiệu quả?

Người học nên đọc hiểu mã giả của các thao tác Insert, Remove, Traverse; tự vẽ sơ đồ dịch chuyển phần tử trên mảng hoặc sơ đồ nối lại con trỏ trên danh sách liên kết ra giấy; sau đó tự gõ lại mã nguồn C và biên dịch kiểm thử thay vì chỉ đọc thụ động.

5. Có tài liệu bổ trợ nào kèm theo?

Nội dung bài học nằm trong chuỗi bài giảng về Cấu trúc dữ liệu của tác giả (ThS. Trịnh Thành Trung, SoICT), kết nối tiếp theo với các chủ đề cấu trúc dữ liệu tuyến tính mở rộng (Hàng đợi - Queue) và cấu trúc dữ liệu phi tuyến tính (Bảng băm - Hash Table, Cây - Tree).

Kết luận

Tài liệu "Bài 4: Cấu trúc dữ liệu" cung cấp cơ sở lý thuyết và phương pháp cài đặt chuẩn xác cho các cấu trúc dữ liệu tuyến tính cơ bản bao gồm mảng, danh sách kế tiếp, danh sách liên kết đơn/kép và ngăn xếp. Lộ trình học tập đề xuất bắt đầu từ việc nắm vững mô hình lưu trữ và phân loại dữ liệu, tiến hành cài đặt danh sách kế tiếp để nhận biết giới hạn của mảng tĩnh, sau đó phát triển kỹ năng với danh sách móc nối động và áp dụng cấu trúc ngăn xếp vào các bài toán thuật toán cụ thể. Người học có thể mở rộng nghiên cứu sang các cấu trúc dữ liệu bậc cao như cây và bảng băm thông qua hệ thống học liệu thuộc Viện Công nghệ Thông tin và Truyền thông (SoICT).