Cấu trúc dữ liệu và thuật toán

Cấu trúc dữ liệu và thuật toán là một giáo trình về cấu trúc dữ liệu và thuật toán, bao gồm các phần chính sau:

• Lời nói đầu: Giới thiệu môn học là kiến thức cơ sở ngành quan trọng trong công nghệ thông tin, yêu cầu tư duy logic toán học và kỹ năng lập trình. Giáo trình được tái bản từ năm 2006, chia thành hai học phần “Nhập môn Cấu trúc dữ liệu và thuật toán” và “Cấu trúc dữ liệu và thuật toán nâng cao” (mỗi học phần 2 tín chỉ) tại Trường Đại học Xây dựng từ năm 2009. Giáo trình cũng đề cập đến các chương trình ví dụ và ứng dụng thực tế do tác giả phát triển qua nhiều năm nghiên cứu và giảng dạy.
• Phần I: Cấu trúc dữ liệu
  • Chương 1: Nhập môn Cấu trúc dữ liệu
    • Khái niệm Cấu trúc dữ liệu: Giải thích tầm quan trọng của cấu trúc dữ liệu và thuật toán, coi chúng là cốt lõi của ngành Công nghệ thông tin. Dữ liệu trong máy tính được lưu trữ dưới dạng bit, tổ chức thành “Từ máy” (word).
    • Kiểu dữ liệu: Trình bày các khái niệm Kiểu dữ liệu, Cấu trúc dữ liệu, Cấu trúc dữ liệu tĩnh, Cấu trúc dữ liệu động. Chi tiết về các kiểu dữ liệu cơ bản trong Pascal như Integer, Real, Char, Boolean, và các phép toán tương ứng.
    • Cấu trúc dữ liệu – Data Structure: Định nghĩa cấu trúc dữ liệu là cách tổ chức dữ liệu trong bộ nhớ máy tính, phân loại thành cấu trúc đơn giản, phức tạp, tĩnh, động, tuyến tính và phi tuyến.
    • Các mô hình dữ liệu: Giới thiệu các mô hình dữ liệu để trừu tượng hóa và biểu diễn dữ liệu, bao gồm: Mô hình quan hệ (Relational Model), Mô hình mạng lưới (Network Model), Mô hình phân cấp (Hierarchical Model), Mô hình đối tượng/quan hệ (Object/Relational Model), Mô hình định hướng đối tượng (Object – Oriented Model), Mô hình nửa cấu trúc (Semistructured Model), Mô hình dữ liệu liên kết (Associative Model), Mô hình thực thể – thuộc tính – giá trị (EAV) và Mô hình ngữ cảnh (Context Model).
  • Chương 2: Cấu trúc dữ liệu tuyến tính
    • Mảng – Arrays: Khái niệm, cách khai báo trong Pascal, công thức tính địa chỉ phần tử. Các trường hợp đặc biệt của mảng như mảng của mảng, ma trận thưa (bao gồm ma trận tam giác dưới, tam giác trên, ma trận băng, ma trận thưa không theo quy luật), cùng các phép toán hoán vị, nhân và cộng ma trận thưa.
    • Ngăn xếp – Stacks: Khái niệm (Last In First Out – LIFO), ví dụ ứng dụng (chuyển đổi cơ số), các phép toán cơ bản (Create, Add, Delete, Top, IsEmpty). Trình bày cách cài đặt ngăn xếp bằng mảng và bản ghi, cùng với thư viện Stack.tpu.
    • Hàng đợi – Queue: Khái niệm (First In First Out – FIFO), ví dụ ứng dụng, các phép toán cơ bản (CreateQ, AddQ, DeleteQ, IsEmptyQ, Front). Trình bày cách cài đặt hàng đợi bằng mảng và thư viện Queue.tpu.
    • Danh sách – List: Khái niệm, các thao tác cơ bản (tạo, kiểm tra rỗng, duyệt, thêm, xóa). Trình bày cách cài đặt danh sách bằng mảng và ví dụ áp dụng (cộng hai đa thức thưa).
    • Bài tập: Các bài tập về mảng, ngăn xếp, hàng đợi và danh sách.
  • Chương 3: Cấu trúc dữ liệu phi tuyến
    • Bản ghi – Record: Khái niệm bản ghi (record) để tổ chức dữ liệu không thuần nhất, cách khai báo kiểu record, truy nhập bản ghi và sử dụng câu lệnh with. Giới thiệu bản ghi có cấu trúc thay đổi để tối ưu bộ nhớ.
    • Kiểu dữ liệu tệp: Khái niệm tệp (tập hợp dữ liệu có cấu trúc xác định), phân biệt tệp chương trình và tệp dữ liệu. Các phương pháp truy nhập tệp (tuần tự, trực tiếp/ngẫu nhiên). Phân loại tệp thành tệp mã, tệp văn bản và tệp không định kiểu. Cách khai báo tệp mã và các thao tác cơ bản với tệp mã (mở tệp mới để ghi, đọc, đóng tệp).