Cấu Trúc Dữ Liệu: Khái Niệm, Thuật Toán và Ứng Dụng

Cấu trúc dữ liệu là một khái niệm quan trọng trong lập trình và khoa học máy tính. 59 trang · Đại Học Đà Nẵng · 2022.

• Tác giả: Phan Chí Tùng
• Trường học: Đại Học Đà Nẵng
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Cấu Trúc Dữ Liệu
• Loại tài liệu: bài giảng
• Năm xuất bản: 2022
• Địa điểm: Đà Nẵng

Mục lục chi tiết

• 1. CHƯƠNG 1: CÁC KHÁI NIỆM CƠ BẢN
• 1.1. Thuật toán và cấu trúc dữ liệu
• 1.2. Các kiểu dữ liệu cơ bản trong ngôn ngữ C
• 1.2.1. Kiểu dữ liệu đơn giản
• 1.2.1.1. Kiểu ký tự
• 1.2.1.2. Kiểu số nguyên
• 1.2.1.3. Kiểu số thực
• 1.2.2. Kiểu dữ liệu có cấu trúc
• 1.2.2.1. Kiểu mảng
• 1.2.2.2. Kiểu chuỗi ký tự
• 1.2.2.3. Kiểu bản ghi
• 1.2.3. Kiểu con trỏ
• 1.2.3.1. Hàm địa chỉ
• 1.2.3.2. Các phép toán trên kiểu con trỏ
• 1.2.3.3. Hằng con trỏ NULL
• 1.2.3.4. Phép cấp phát vùng nhớ
• 1.2.3.5. Phép thu hồi vùng nhớ
• 1.2.4. Kiểu tham chiếu
• 1.2.4.1. Định nghĩa
• 1.2.4.2. Khai báo biến kiểu tham chiếu
• 1.2.4.3. Ứng dụng kiểu tham chiếu
• 1.3. Các nguyên lý khi dùng kỹ thuật đệ qui
• 1.3.1. Tham số hóa bài toán
• 1.3.2. Tìm trường hợp dễ nhất
• 1.3.3. Tìm trường hợp tổng quát
• 2. CHƯƠNG 2: DANH SÁCH
• 2.1. Khái niệm
• 2.2. Danh sách đặc
• 2.2.1. Định nghĩa
• 2.2.2. Biểu diễn danh sách đặc
• Tài liệu tham khảo

Tóm tắt

I. Tổng Quan Về Cấu Trúc Dữ Liệu Khái Niệm Cơ Bản

Cấu trúc dữ liệu là một khái niệm quan trọng trong lập trình và khoa học máy tính. Nó đề cập đến cách tổ chức và lưu trữ dữ liệu trong bộ nhớ máy tính. Việc hiểu rõ về cấu trúc dữ liệu giúp lập trình viên tối ưu hóa thuật toán và cải thiện hiệu suất của ứng dụng. Các kiểu dữ liệu cơ bản bao gồm kiểu số nguyên, số thực, chuỗi ký tự và kiểu dữ liệu có cấu trúc. Mỗi kiểu dữ liệu có những đặc điểm riêng và ứng dụng khác nhau trong lập trình.

1.1. Các Kiểu Dữ Liệu Cơ Bản Trong Ngôn Ngữ C

Trong ngôn ngữ C, các kiểu dữ liệu cơ bản bao gồm kiểu số nguyên, số thực và ký tự. Kiểu số nguyên có thể là int, long, và unsigned int. Kiểu số thực bao gồm float và double. Kiểu ký tự được định nghĩa bằng char. Mỗi kiểu dữ liệu này có kích thước và miền giá trị khác nhau, ảnh hưởng đến cách lưu trữ và xử lý dữ liệu.

1.2. Mối Quan Hệ Giữa Thuật Toán và Cấu Trúc Dữ Liệu

Cấu trúc dữ liệu và thuật toán có mối quan hệ chặt chẽ. Một cấu trúc dữ liệu hợp lý sẽ giúp thuật toán hoạt động hiệu quả hơn. Khi thay đổi cấu trúc dữ liệu, thuật toán cũng cần được điều chỉnh để phù hợp. Việc lựa chọn cấu trúc dữ liệu phù hợp là rất quan trọng trong việc phát triển phần mềm.

II. Vấn Đề và Thách Thức Trong Cấu Trúc Dữ Liệu

Mặc dù cấu trúc dữ liệu rất quan trọng, nhưng việc lựa chọn và triển khai chúng cũng gặp nhiều thách thức. Một số vấn đề phổ biến bao gồm việc tối ưu hóa bộ nhớ, tốc độ truy cập dữ liệu và khả năng mở rộng. Các lập trình viên cần phải cân nhắc giữa hiệu suất và độ phức tạp khi thiết kế cấu trúc dữ liệu.

2.1. Tối Ưu Hóa Bộ Nhớ Trong Cấu Trúc Dữ Liệu

Tối ưu hóa bộ nhớ là một trong những thách thức lớn nhất khi làm việc với cấu trúc dữ liệu. Việc sử dụng bộ nhớ không hiệu quả có thể dẫn đến tình trạng tràn bộ nhớ hoặc giảm hiệu suất. Các kỹ thuật như sử dụng danh sách liên kết thay vì mảng có thể giúp tiết kiệm bộ nhớ.

2.2. Tốc Độ Truy Cập Dữ Liệu và Ảnh Hưởng Đến Hiệu Suất

Tốc độ truy cập dữ liệu là yếu tố quan trọng ảnh hưởng đến hiệu suất của ứng dụng. Các cấu trúc dữ liệu như cây nhị phân tìm kiếm hoặc bảng băm có thể cải thiện tốc độ truy cập. Tuy nhiên, việc lựa chọn cấu trúc dữ liệu phù hợp cần phải dựa trên yêu cầu cụ thể của ứng dụng.

III. Phương Pháp Chính Trong Cấu Trúc Dữ Liệu

Có nhiều phương pháp để tổ chức và quản lý dữ liệu trong lập trình. Các phương pháp này bao gồm danh sách liên kết, cây, và bảng băm. Mỗi phương pháp có ưu điểm và nhược điểm riêng, và việc lựa chọn phương pháp phù hợp là rất quan trọng.

3.1. Danh Sách Liên Kết Đặc Điểm và Ứng Dụng

Danh sách liên kết là một cấu trúc dữ liệu cho phép lưu trữ các phần tử không liên tiếp trong bộ nhớ. Mỗi phần tử trong danh sách liên kết chứa một con trỏ đến phần tử tiếp theo. Điều này giúp dễ dàng thêm hoặc xóa phần tử mà không cần di chuyển các phần tử khác.

3.2. Cây Nhị Phân Cấu Trúc và Tính Năng

Cây nhị phân là một cấu trúc dữ liệu có thể lưu trữ dữ liệu theo cách phân cấp. Mỗi nút trong cây có tối đa hai con. Cây nhị phân tìm kiếm cho phép tìm kiếm, thêm và xóa phần tử một cách hiệu quả. Cấu trúc này rất hữu ích trong các ứng dụng cần truy cập dữ liệu nhanh.

3.3. Bảng Băm Tối Ưu Hóa Tìm Kiếm Dữ Liệu

Bảng băm là một cấu trúc dữ liệu cho phép truy cập dữ liệu nhanh chóng thông qua một hàm băm. Hàm băm chuyển đổi khóa thành chỉ số trong bảng. Điều này giúp giảm thời gian tìm kiếm xuống còn O(1) trong nhiều trường hợp. Tuy nhiên, việc xử lý xung đột trong bảng băm là một thách thức cần được giải quyết.

IV. Ứng Dụng Thực Tiễn Của Cấu Trúc Dữ Liệu

Cấu trúc dữ liệu có nhiều ứng dụng trong thực tế, từ việc phát triển phần mềm đến quản lý cơ sở dữ liệu. Việc lựa chọn cấu trúc dữ liệu phù hợp có thể cải thiện hiệu suất và khả năng mở rộng của ứng dụng.

4.1. Ứng Dụng Trong Phát Triển Phần Mềm

Trong phát triển phần mềm, cấu trúc dữ liệu được sử dụng để tổ chức và quản lý dữ liệu. Ví dụ, danh sách liên kết có thể được sử dụng để quản lý danh sách người dùng trong một ứng dụng. Cây nhị phân có thể được sử dụng để lưu trữ dữ liệu theo cách phân cấp.

4.2. Ứng Dụng Trong Quản Lý Cơ Sở Dữ Liệu

Cấu trúc dữ liệu cũng rất quan trọng trong quản lý cơ sở dữ liệu. Bảng băm có thể được sử dụng để tối ưu hóa truy vấn dữ liệu. Cây nhị phân tìm kiếm giúp cải thiện tốc độ truy cập dữ liệu trong các hệ thống cơ sở dữ liệu lớn.

V. Kết Luận Tương Lai Của Cấu Trúc Dữ Liệu

Cấu trúc dữ liệu sẽ tiếp tục đóng vai trò quan trọng trong phát triển công nghệ thông tin. Với sự phát triển của trí tuệ nhân tạo và dữ liệu lớn, nhu cầu về các cấu trúc dữ liệu hiệu quả sẽ ngày càng tăng. Việc nghiên cứu và phát triển các cấu trúc dữ liệu mới sẽ giúp cải thiện hiệu suất và khả năng xử lý dữ liệu.

5.1. Xu Hướng Phát Triển Cấu Trúc Dữ Liệu Mới

Trong tương lai, các cấu trúc dữ liệu mới sẽ được phát triển để đáp ứng nhu cầu ngày càng cao về hiệu suất và khả năng mở rộng. Các nghiên cứu về cấu trúc dữ liệu phân tán và cấu trúc dữ liệu động sẽ trở nên phổ biến.

5.2. Tầm Quan Trọng Của Cấu Trúc Dữ Liệu Trong Khoa Học Dữ Liệu

Cấu trúc dữ liệu là nền tảng của khoa học dữ liệu. Việc hiểu rõ về cấu trúc dữ liệu sẽ giúp các nhà khoa học dữ liệu phân tích và xử lý dữ liệu hiệu quả hơn. Điều này sẽ góp phần vào sự phát triển của các ứng dụng thông minh trong tương lai.

Nội dung chính

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

Bài giảng học phần Cấu trúc dữ liệu do tác giả Phan Chí Tùng biên soạn, thuộc Khoa Công nghệ Thông tin – Trường Đại học Bách Khoa (Đại học Đà Nẵng), xuất bản dưới dạng lưu hành nội bộ năm 2022. Trong chương trình đào tạo kỹ sư và cử nhân ngành Công nghệ Thông tin, Cấu trúc dữ liệu giữ vị trí học phần cơ sở ngành bắt buộc, đóng vai trò bản lề kết nối giữa học phần Kỹ thuật lập trình và các môn học chuyên sâu như Cơ sở dữ liệu, Hệ điều hành, Nguyên lý xây dựng chương trình dịch và Thiết kế giải thuật.

Mục tiêu học tập của tài liệu tập trung trang bị cho người học:

• Khả năng phân biệt và phân loại các kiểu dữ liệu từ đơn giản (số nguyên, số thực, ký tự) đến có cấu trúc (mảng, chuỗi ký tự, bản ghi struct, con trỏ, tham chiếu).
• Kỹ năng thiết kế, biểu diễn và thao tác trên các cấu trúc dữ liệu tuyến tính (danh sách đặc, danh sách liên kết đơn, kép, vòng, đa liên kết; ngăn xếp; hàng đợi) và phi tuyến tính (cây tổng quát, cây nhị phân, cây nhị phân tìm kiếm, cây cân bằng AVL).
• Năng lực phân tích, cài đặt các giải thuật sắp xếp nội (Selection Sort, Insertion Sort, Bubble Sort, Merge Sort, Heap Sort, Quick Sort), sắp xếp ngoại (phương pháp trộn RUN, trộn tự nhiên) và các giải thuật tìm kiếm, bảng băm mở.

Cấu trúc giáo trình gồm 5 chương được biên soạn theo trình tự từ bản chất lưu trữ vật lý trong bộ nhớ RAM đến các cấu trúc dữ liệu trừu tượng hóa và thuật toán tối ưu hóa. Điểm đặc sắc của tài liệu là phương pháp tiếp cận gắn liền với việc mô hình hóa địa chỉ ô nhớ cụ thể (ví dụ: các nhãn địa chỉ 7TĐT, 8NLB, 5TĐT), minh họa thao tác con trỏ qua mã nguồn C/C++ trực quan và đưa các dữ liệu thực tế (như chuỗi bài báo về dịch bệnh COVID-19 năm 2020) vào việc giải thích nguyên lý phân mảnh và liên kết bộ nhớ.

---

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

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

Nội dung bài giảng được tổ chức thành 5 chương trọng tâm với progression logic đi từ thấp lên cao:

[Chương 1: Kiểu dữ liệu, Con trỏ, Đệ quy] 

• Chương 1: Các khái niệm cơ bản: Thiết lập định nghĩa về dữ liệu, kiểu dữ liệu, cấu trúc dữ liệu và mối quan hệ giữa thuật toán với cấu trúc dữ liệu. Trình bày chi tiết các kiểu dữ liệu cơ bản trong ngôn ngữ C: kiểu đơn giản (char, int, long, float, double), kiểu có cấu trúc (mảng, chuỗi ký tự, bản ghi struct), kiểu con trỏ (toán tử địa chỉ &, toán tử giải tham chiếu *, cấp phát new, thu hồi delete), kiểu tham chiếu (&) và kỹ thuật đệ quy dựa trên 3 nguyên lý (tham số hóa, trường hợp dễ nhất, trường hợp tổng quát) qua bài toán giai thừa fact(n) và ước số chung lớn nhất uscln(x, y).
• Chương 2: Danh sách: Khảo sát các hình thức biểu diễn danh sách:
  • Danh sách đặc: Lưu trữ kế tiếp bằng mảng một chiều với kích thước tĩnh Nmax.
  • Danh sách liên kết đơn: Cài đặt qua cấu trúc nút chứa dữ liệu và con trỏ next.
  • Danh sách đa liên kết: Nút chứa nhiều liên kết độc lập (ví dụ con trỏ next1 liên kết theo thứ tự họ tên, next2 theo thứ tự chiều cao).
  • Danh sách liên kết kép: Nút chứa đồng thời con trỏ liên kết trước pPrev và liên kết sau pNext.
  • Danh sách liên kết vòng: Nút cuối trỏ quay về nút đầu danh sách.
  • Danh sách hạn chế: Ngăn xếp (Stack - LIFO) và Hàng đợi (Queue - FIFO) được cài đặt bằng danh sách liên kết.
• Chương 3: Cây: Nghiên cứu mô hình phân cấp phi tuyến tính:
  • Định nghĩa cây: Nút gốc (Root), nút lá, cấp của nút, cấp của cây, mức, chiều cao, đường đi.
  • Cây nhị phân: Định nghĩa, tính chất toán học ($2^{i-1}$ nút ở mức $i$), cây hoàn chỉnh, cây đầy đủ, biểu diễn bằng mảng và con trỏ. Ba phép duyệt cây: Duyệt trước (Pre-order), Duyệt giữa (In-order), Duyệt sau (Post-order).
  • Cây nhị phân tìm kiếm (BST): Cấu trúc định hướng khóa, các thao tác tìm kiếm, chèn nút và xóa nút sử dụng phần tử thế mạng.
  • Cây cân bằng hoàn toàn và Cây cân bằng AVL (Adelson-Velskii & Landis, 1962): Định nghĩa chỉ số cân bằng balFactor (LH, EH, RH), giới hạn chiều cao cây $h \approx \log_2 n$ để giữ chi phí tìm kiếm ở mức $O(\log_2 n)$.
  • Cây tổng quát và Cây biểu thức: Biến đổi cây tổng quát thành cây nhị phân tương đương (nguyên tắc con trái - em phải); biểu diễn biểu thức tiền tố (prefix), trung tố (infix) và hậu tố (postfix) Balan.
• Chương 4: Sắp xếp thứ tự dữ liệu:
  • Sắp xếp nội: Trình bày giải thuật, phân tích độ phức tạp và mã nguồn C của các phương pháp: Lựa chọn trực tiếp (Selection Sort), Chèn trực tiếp (Insertion Sort), Chèn nhị phân, Nổi bọt (Bubble Sort), Trộn trực tiếp (Merge Sort - chi phí $O(n \log_2 n)$), Vun đống (Heap Sort của J. Williams trên cấu trúc mảng biểu diễn cây nhị phân hoàn chỉnh với hàm Shift), Sắp xếp nhanh (Quick Sort sử dụng kỹ thuật phân hoạch với phần tử chốt ở giữa).
  • Sắp xếp ngoại: Xử lý tập tin tuần tự và truy xuất ngẫu nhiên khi kích thước vượt quá bộ nhớ trong, tập trung vào phương pháp trộn RUN trên các tập tin trung gian $f_1, f_2$ và phương pháp trộn tự nhiên qua biến cờ eor (end of run).
• Chương 5: Tìm kiếm dữ liệu: Khảo sát nhu cầu tìm kiếm, giải thuật tìm kiếm tuần tự ($O(n)$), tìm kiếm nhị phân ($O(\log_2 n)$) và cấu trúc dữ liệu bảng băm mở (Open Hash Table).

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

• Lý thuyết trừu tượng hóa dữ liệu (Data Abstraction): Phân tách rõ ràng giữa định nghĩa toán học trừu tượng của một kiểu dữ liệu (ADT) với việc hiện thực hóa vật lý của nó trong bộ nhớ máy tính.
• Nguyên lý quản lý tài nguyên bộ nhớ: Cơ chế cấp phát động trên vùng nhớ Heap (new, delete), quản trị địa chỉ ô nhớ qua con trỏ, và kỹ thuật giảm thiểu không gian lưu trữ phụ trợ trong các giải thuật sắp xếp tại chỗ (in-place sorting).
• Phân tích tiệm cận thuật toán: Xác định cận trên và trường hợp tốt nhất/xấu nhất của thời gian thực thi thuật toán theo ký hiệu Big-$O$ ($O(1)$, $O(\log_2 n)$, $O(n)$, $O(n \log_2 n)$, $O(n^2)$) qua số lượng phép so sánh và phép gán/hoán vị.

Kỹ năng phát triển

• Kỹ năng kỹ thuật (Technical skills): Cài đặt thuần thục các cấu trúc dữ liệu và giải thuật bằng ngôn ngữ C/C++; quản lý con trỏ, thao tác địa chỉ cấp thấp; thao tác vào/ra dữ liệu trên file nhị phân và file văn bản (FILE *, fopen, fscanf, fprintf).
• Kỹ năng phân tích (Analytical skills): Khả năng so sánh đánh giá ưu nhược điểm giữa cấu trúc liên tục (mảng) và cấu trúc liên kết (con trỏ); lựa chọn giải thuật sắp xếp và tìm kiếm phù hợp với quy mô dữ liệu và giới hạn tài nguyên bộ nhớ.
• Năng lực giải quyết vấn đề (Practical competencies): Xây dựng các chương trình ứng dụng hoàn chỉnh như quản lý hồ sơ sinh viên, chuyển đổi hệ cơ số bằng ngăn xếp, tính giá trị biểu thức số học qua cây biểu thức, và xử lý sắp xếp tập tin dữ liệu lớn trên đĩa từ.

---

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

Phương pháp tiếp cận sư phạm của giáo trình được xây dựng trên nguyên tắc kết hợp giữa giải thích hình thức toán học, trực quan hóa cấu trúc bộ nhớ và cung cấp mã nguồn mẫu C/C++ có thể thực thi ngay. Mỗi cấu trúc dữ liệu hoặc giải thuật đều tuân thủ tiến trình 4 bước:

1. Nêu định nghĩa và điều kiện ràng buộc lý thuyết.
2. Trực quan hóa cấu trúc dữ liệu trên sơ đồ bộ nhớ hoặc bảng trace trạng thái từng bước.
3. Cài đặt các hàm thao tác chuẩn bằng ngôn ngữ lập trình C/C++.
4. Đánh giá chi phí thuật toán (số phép so sánh, số phép gán, độ phức tạp $O$).

[1. Định nghĩa lý thuyết] 

Tài liệu sử dụng nhiều ví dụ và bài tập thực hành gắn với việc xây dựng kiểu dữ liệu người dùng tự định nghĩa:

• Ví dụ quản lý sinh viên với bản ghi struct SVIEN (chứa các trường ht, cc, ns, t) và tính cân nặng tiêu chuẩn cntc theo công thức: $$\text{Cân nặng tiêu chuẩn (kg)} = \text{Chiều cao} \times 100 - 105$$
• Ví dụ kiểu bản ghi hình chữ nhật struct HCN với các trường d, r, cv.
• Ví dụ tính toán giá trị biểu thức toán học phức tạp thông qua cây biểu thức: $$(3 + 1)^3 / (9 - 5 + 2) - (3(7 - 4) + 6) = -13$$
• Ví dụ về cơ chế xâu chuỗi thông tin dựa trên bài toán theo dõi các ca nhiễm dịch bệnh COVID-19 tại Việt Nam để giải thích tính chất lưu trữ phân tán của danh sách liên kết.

Phương pháp đánh giá trong học phần tập trung vào hai tiêu chí:

• Đánh giá lý thuyết: Khả năng tái hiện các bước của thuật toán trên giấy thông qua bảng phân tích từng bước (như trace vòng lặp thuật toán Selection Sort, Quick Sort, dựng cây nhị phân tìm kiếm khi lần lượt thêm các khóa $50, 30, 40, 70, 20$).
• Đánh giá kỹ năng lập trình: Khả năng viết đúng cú pháp các hàm thêm nút (InsertHead, AddTail, AddAfter, InsertStack), xóa nút (RemoveHead, RemoveTail, RemoveNode, delNode), giải phóng vùng nhớ và xử lý triệt để các trường hợp biên (danh sách rỗng, cây rỗng, con trỏ NULL).

Để tự học hiệu quả, người học được khuyến nghị vẽ lại mô hình liên kết của các con trỏ trước khi viết mã nguồn, gõ và biên dịch lại từng khối hàm con độc lập, kiểm tra các điều kiện dừng của đệ quy và tự chạy tay các trường hợp xấu nhất của giải thuật.

---

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

• Nguồn gốc học thuật chuẩn mực: Giáo trình kế thừa và hệ thống hóa kiến thức từ các tài liệu tham khảo kinh điển trong và ngoài nước, bao gồm:
  • Data Structures and Algorithms của Alfred V. Aho & Jeffrey D. Ullman (1983).
  • Data Structures Using C and C++ của Yedidyah Langsam, Moshe J. Augenstein & Aaron M. Tenenbaum (1996).
  • Các công trình của các tác giả chuyên ngành tại Việt Nam: Đỗ Xuân Lôi (2003), Nguyễn Hồng Chương (2003), Lê Xuân Trường (1999), Đinh Mạnh Tường (2000), Nguyễn Trung Trực (2000).
• Bổ sung nội dung sắp xếp ngoại (External Sort): Khác với nhiều bài giảng chỉ dừng lại ở sắp xếp nội trên mảng RAM, tài liệu của tác giả Phan Chí Tùng dành toàn bộ nửa sau Chương 4 để hướng dẫn chi tiết thuật toán sắp xếp ngoại với phương pháp trộn RUN và trộn tự nhiên. Phần này cung cấp đầy đủ mã nguồn C thao tác trực tiếp với các luồng tập tin (FILE *a, FILE *b, FILE *c, fopen, fscanf, fprintf), phục vụ trực tiếp cho việc xử lý các tập dữ liệu có kích thước vượt quá dung lượng bộ nhớ trong.
• Trực quan hóa cấu trúc dữ liệu bộ nhớ RAM: Tài liệu thể hiện chi tiết cách thức các con trỏ lưu trữ địa chỉ của nhau trong bảng dữ liệu thực tế (như các địa chỉ ô nhớ giả định 7TĐT, 8NLB, 9TĐT, 5TĐT, 6NLB), giúp người học hình dung chính xác cách thức phân bổ bộ nhớ động khi liên kết đơn, liên kết kép hoặc liên kết vòng hoạt động.
• Ứng dụng công nghệ thực tế: Trình bày rõ ràng các ứng dụng của cấu trúc dữ liệu trong việc xây dựng hệ điều hành (cây thư mục quản lý tập tin), trình biên dịch (cây cú pháp, chuyển đổi biểu thức trung tố sang tiền tố/hậu tố Balan) và hệ thống quản trị cơ sở dữ liệu (cây cân bằng AVL, bảng băm).

---

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

• Sinh viên đại học chuyên ngành: Phù hợp cho sinh viên năm thứ nhất (học kỳ 2) hoặc năm thứ hai thuộc các ngành Công nghệ Thông tin, Kỹ thuật Phần mềm, Khoa học Máy tính, Hệ thống Thông tin, Kỹ thuật Máy tính và Mạng máy tính.
• Kiến thức tiên quyết (Prerequisites): Người học cần hoàn thành học phần Nhập môn Lập trình hoặc Kỹ thuật Lập trình với ngôn ngữ C/C++. Cần nắm vững kiến thức về cú pháp cơ bản, các cấu trúc điều khiển rẽ nhánh (if-else, switch-case), vòng lặp (for, while, do-while), kỹ thuật viết và truyền tham số cho hàm, cấu trúc mảng một chiều và các toán tử số học.
• Giảng viên đại học và cao đẳng: Sử dụng bài giảng làm tài liệu chuẩn để xây dựng đề cương môn học, biên soạn slide giảng dạy, thiết kế bài tập thực hành trên phòng máy và xây dựng ngân hàng câu hỏi kiểm tra, thi kết thúc học phần.
• Kỹ sư phần mềm và người tự học: Phục vụ làm tài liệu tham khảo cho các lập trình viên cần củng cố lại nền tảng khoa học máy tính, nắm vững bản chất tổ chức bộ nhớ và cơ chế thực thi của các thuật toán kinh điển phục vụ cho việc tối ưu hóa hiệu năng phần mềm hoặc chuẩn bị cho các kỳ đánh giá kỹ thuật chuyên môn.

---

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

1. Giáo trình này phù hợp với đối tượng nào?

Tài liệu được biên soạn phục vụ đào tạo bậc đại học khối ngành Công nghệ Thông tin và Kỹ thuật Phần mềm. Giáo trình phù hợp cho sinh viên đang theo học môn Cấu trúc dữ liệu và giải thuật, cũng như kỹ sư phần mềm cần củng cố kiến thức nền tảng về tổ chức bộ nhớ và thuật toán.

2. Cần chuẩn bị những kiến thức nền tảng nào trước khi học?

Người học cần có kiến thức cơ bản về ngôn ngữ lập trình C hoặc C++, bao gồm cú pháp câu lệnh, cấu trúc điều khiển, kiểu dữ liệu mảng, và hiểu biết ban đầu về hàm. Các khái niệm phức tạp hơn như con trỏ, tham chiếu và đệ quy đã được hệ thống hóa lại chi tiết ngay trong Chương 1 của tài liệu.

3. Điểm khác biệt của giáo trình này so với các tài liệu khác là gì?

Tài liệu tích hợp đầy đủ cả hai mảng: lý thuyết thuật toán và mã nguồn C/C++ hoàn chỉnh. Đặc biệt, giáo trình không chỉ dừng lại ở các thuật toán sắp xếp trên RAM (sắp xếp nội) mà còn đi sâu vào sắp xếp trên tập tin đĩa (sắp xếp ngoại qua phương pháp trộn RUN), đồng thời trực quan hóa cơ chế bộ nhớ thông qua các mô hình ô nhớ RAM cụ thể.

4. Phương pháp tự học giáo trình này như thế nào để đạt hiệu quả cao?

Người học nên kết hợp đọc lý thuyết, vẽ lại sơ đồ cấu trúc dữ liệu trên giấy, sau đó tự tay nhập và thực thi các đoạn mã nguồn mẫu trong giáo trình bằng các trình biên dịch C/C++ tiêu chuẩn. Tiếp theo, cần tự thực hiện bảng trace từng bước của các giải thuật (Selection Sort, Merge Sort, Quick Sort, Heap Sort) với các bộ dữ liệu nhỏ trước khi cài đặt giải thuật hoàn chỉnh.

5. Có những tài liệu tham khảo bổ trợ nào được khuyến nghị?

Người học có thể tham khảo thêm 8 tài liệu kinh điển được tác giả trích dẫn trong phần danh mục tham khảo, tiêu biểu như giáo trình của Đỗ Xuân Lôi (2003), Đinh Mạnh Tường (2000), Nguyễn Trung Trực (2000), cùng các sách quốc tế của Alfred V. Aho & Jeffrey D. Ullman (1983) và Yedidyah Langsam & Moshe J. Augenstein & Aaron M. Tenenbaum (1996).

---

Kết luận

Bài giảng Cấu trúc dữ liệu của tác giả Phan Chí Tùng (Khoa Công nghệ Thông tin – Trường Đại học Bách Khoa, Đại học Đà Nẵng, 2022) là tài liệu học thuật hoàn chỉnh, cung cấp hệ thống kiến thức nền tảng về việc mô hình hóa, tổ chức dữ liệu và thiết kế giải thuật trên ngôn ngữ lập trình C/C++.

Lộ trình học tập đề xuất theo tài liệu gồm:

1. Củng cố bản chất con trỏ, kiểu dữ liệu bản ghi và đệ quy (Chương 1).
2. Làm chủ các cấu trúc dữ liệu tuyến tính và danh sách hạn chế (Chương 2).
3. Nghiên cứu cấu trúc phân cấp phi tuyến tính và cây cân bằng AVL (Chương 3).
4. Cài đặt các giải thuật sắp xếp nội, sắp xếp ngoại và đánh giá độ phức tạp tính toán (Chương 4).
5. Làm chủ các giải thuật tìm kiếm và cấu trúc bảng băm mở (Chương 5).

Người học nên kết hợp nghiên cứu bài giảng với việc thực hành cài đặt mã nguồn thực tế và tham khảo các tài liệu chuyên khảo được trích dẫn trong giáo trình để phát triển toàn diện tư duy giải thuật trong kỹ thuật phần mềm.

Trích đoạn nội dung tài liệu

CHƯƠNG 1--- ------------------------------------------------------------------------------------------------------------ Cấu trúc dữ liệu – Trang 11 Chương 2: DANH SÁCH 2. Khái niệm: - Danh sách: là một dãy các phần tử a1, a2, a3,. an trong đó nếu biết được phần tử đứng trước thì sẽ biết được phần tử đứng sau. - n: là số phần tử của danh sách.

- Danh sách rỗng: là danh sách không có phần tử nào cả, tức n=0 - Danh sách là khái niệm thường gặp trong cuộc sống, như danh sách các sinh viên trong một lớp, danh sách các môn học trong một học kỳ. - Có 2 cách cơ bản biểu diễn danh sách: + Danh sách đặc: các phần tử được lưu trữ kế tiếp nhau trong bộ nhớ, phần tử thứ i được lưu trữ ngay trước phần tử thứ i+1 dưới hình thức một mảng. + Danh sách liên kết: các phần tử được lưu trữ tại những vùng nhớ khác nhau trong bộ nhớ, nhưng chúng được kết nối với nhau nhờ các vùng liên kết. - Các phép toán thường dùng trên danh sách: + Khởi tạo danh sách (tức là làm cho danh sách có, nhưng là danh sách rỗng).

+ Kiểm tra xem danh sách có rỗng không. + Liệt kê các phần tử có trong danh sách. + Tìm kiếm phần tử trong danh sách. + Thêm phần tử vào danh sách.

+ Xóa phần tử ra khỏi danh sách. + Sửa các thông tin của phần tử trong danh sách. + Thay thế một phần tử trong danh sách bằng một phần tử khác. + Sắp xếp thứ tự các phần tử trong danh sách.

+ Ghép một danh sách vào một danh sách khác. + Trộn các danh sách đã có thứ tự để được một danh sách mới cũng có thứ tự. + Tách một danh sách ra thành nhiều danh sách. - Trong thực tế một bài toán cụ thể chỉ dùng một số phép toán nào đó, nên ta phải biết cách biểu diễn danh sách cho phù hợp với bài toán.

Danh sách đặc: 2. Định nghĩa: Danh sách đặc là danh sách mà các phần tử được lưu trữ kế tiếp nhau trong bộ nhớ dưới hình thức một mảng. Biểu diễn danh sách đặc: Xét danh sách có tối đa 100 sinh viên gồm các thông tin: họ tên, chiều cao, cân nặng tiêu chuẩn, như : 1 LÊ LI 1.5 45 Trong đó cân nặng tiêu chuẩn được tính theo công thức: Cân nặng tiêu chuẩn (kg) = Chiều cao x 100 – 105 Khai báo: const int Nmax=100; typedef char infor1[15]; typedef float infor2; typedef int infor3; struct element { infor1 ht; infor2 cc; infor3 cntc; }; ------------------------------------------------------------------------------------------------------------ Cấu trúc dữ liệu – Trang 12 typedef element DS[Nmax]; DS A; int n; Hằng Nmax kiểu int chứa số phần tử tối đa có thể có của danh sách. Biến n kiểu int chứa số phần tử thực tế hiện nay của danh sách, ví dụ n=5.

Kiểu bản ghi element gồm các trường ht, cc, cntc lần lượt chứa họ tên, chiều cao, cân nặng tiêu chuẩn của một sinh viên. infor1, infor2, infor3 lần lượt là các kiểu dữ liệu của các trường ht, cc, cntc. DS là kiểu mảng gồm Nmax phần tử kiểu element. Biến A kiểu DS là biến mảng gồm Nmax phần tử kiểu element.

Các phép toán trên danh sách đặc: - Khởi tạo danh sách: Khi mới khởi tạo danh sách là rỗng, ta cho n nhận giá trị 0. void Create(DS A, int &n) { n=0; } - Liệt kê các phần tử trong danh sách: Ta liệt kê các phần tử từ phần tử đầu tiên trở đi. void Display(DS A, int n) { int i; for (i=1; i<=n; i++) printf("\n %15s %7.cntc); } - Tìm kiếm một phần tử trong danh sách: Tìm phần tử có họ tên x cho trước. Ta tìm bắt đầu từ phần tử đầu tiên trở đi, cho đến khi tìm được phần tử cần tìm hoặc đã kiểm tra xong phần tử cuối cùng mà không có thì dừng.

Hàm Search(A, n, x) tìm và trả về giá trị kiểu int, là số thứ tự của phần tử đầu tiên tìm được hoặc trả về giá trị -1 nếu tìm không có.ht,x)!=0) ) i++; if (i<=n) return i; else return -1; } - Thêm một phần tử có họ tên x, chiều cao y, cân nặng tiêu chuẩn z vào vị trí thứ t trong danh sách. Điều kiện: n<Nmax và 1 ≤ t ≤ n+1 Khi đó các phần tử từ thứ t đến thứ n được dời xuống 1 vị trí trong đó phần tử ở dưới thì dời trước, phần tử ở trên dời sau. Sau đó chèn phần tử mới vào vị trí thứ t, cuối cùng tăng giá trị n lên 1 đơn vị.cntc=z; n++; } } - Xóa phần tử thứ t trong danh sách, Điều kiện: 1 ≤ t ≤ n Khi đó các phần tử từ thứ t+1 đến thứ n được dời lên 1 vị trí, trong đó phần tử ở trên thì dời trước, phần tử ở dưới dời sau, cuối cùng giảm giá trị của n xuống 1 đơn vị. void DeleteElement(DS A, int &n, int t) { int i; if ( (t>=1) && (t<=n) ) { for (i=t+1; i<=n; i++) A[i-1]=A[i]; ------------------------------------------------------------------------------------------------------------ Cấu trúc dữ liệu – Trang 13 n--; } } 2.

Ưu nhược điểm của danh sách đặc: * Ưu điểm: - Dễ viết chương trình. - Tiết kiệm bộ nhớ cho mỗi phần tử. - Chỉ tiện lợi cho danh sách dùng ít bộ nhớ. * Khuyết điểm: - Không tiện lợi cho danh sách dùng nhiều bộ nhớ.

- Cần vùng nhớ liên tục. - Khai báo trước số lượng cụ thể số phần tử của danh sách. Danh sách liên kết (đơn): 2. Định nghĩa danh sách liên kết: Danh sách liên kết là danh sách mà các phần tử được kết nối với nhau nhờ các vùng liên kết.

Biểu diễn danh sách liên kết: Xét danh sách sinh viên gồm các thông tin: họ tên, chiều cao, cân nặng tiêu chuẩn.5 45 typedef char infor1[15]; typedef float infor2; typedef int infor3; struct element { infor1 ht; infor2 cc; infor3 cntc; element *next; }; typedef element *List; List F; // hoặc element *F; Hỏi F: 2002 ở đâu? int *F; Hỏi F: 1.7 ở đâu ? float *F; Hỏi F: LE LI 1.7 65 ở đâu ? element *F; Kiểu bản ghi element gồm các trường ht, cc, cntc dùng để chứa các thông tin của một phần tử trong danh sách, ngoài ra còn có thêm trường liên kết next chứa địa chỉ của phần tử tiếp theo trong danh sách. Kiểu con trỏ List dùng để chỉ đến một phần tử kiểu element. Biến con trỏ F luôn luôn chỉ đến phần tử đầu tiên trong danh sách liên kết. Bệnh nhân 271 mắc bệnh ngày 2/5 là chuyên gia người Anh.1, Bệnh viện Chợ Rẫy (TP.HCM) xác nhận 2 bệnh nhân số 1 và số 2 tại Việt Nam, là 2 cha con người Trung Quốc, người con làm việc tại Long An.

Xem tiếp trang 9.BÀI: TÌNH HÌNH COVID 19 VIỆT NAM: Dịch bệnh Covid-19 bắt đầu bùng phát từ tháng 12.2019 tại thành phố Vũ Hán, Trung Quốc. Đã lan ra 212 quốc gia với 2.703 ca nhiễm, và 184.325 người tử vong. Xem tiếp trang 20.1, có thêm 3 bệnh nhân là số 3, số 4, số 5 thuộc tỉnh Vĩnh Phúc. Các bệnh nhân này ở trong nhóm được một công ty Nhật cử sang Trung Quốc tập huấn.

Xem tiếp trang 3.Tại Việt Nam, ca nhiễm Covid-19 đầu tiên được phát hiện vào ngày 23.1, và tới nay đã có 268 trường hợp nhiễm bệnh. Xem tiếp trang 5.BÀI: TÌNH HÌNH COVID 19 VIỆT NAM: ------------------------------------------------------------------------------------------------------------ Cấu trúc dữ liệu – Trang 14 Dịch bệnh Covid-19 bắt đầu bùng phát từ tháng 12.2019 tại thành phố Vũ Hán, Trung Quốc. Đã lan ra 212 quốc gia với 2.703 ca nhiễm, và 184.325 người tử vong. Xem tiếp trang 20.Tại Việt Nam, ca nhiễm Covid-19 đầu tiên được phát hiện vào ngày 23.1, và tới nay đã có 271 trường hợp nhiễm bệnh.

Xem tiếp trang 5.1, Bệnh viện Chợ Rẫy (TP.HCM) xác nhận 2 bệnh nhân số 1 và số 2 tại Việt Nam, là 2 cha con người Trung Quốc, người con làm việc tại Long An. Xem tiếp trang 9.1, có thêm 3 bệnh nhân là số 3, số 4, số 5 thuộc tỉnh Vĩnh Phúc. Các bệnh nhân này ở trong nhóm được một công ty Nhật cử sang Trung Quốc tập huấn. Xem tiếp trang 3.

Bệnh nhân 271 mắc bệnh ngày 2/5 là chuyên gia người Anh. Các phép toán trên danh sách liên kết: - Khởi tạo danh sách: Khi mới khởi tạo danh sách là rỗng, ta cho F nhận giá trị NULL.next=NULL; thì p đang ở phần tử cuối cùng. p=NULL; thì p đang ở dưới phần tử cuối cùng.7 65 8NLB 2 LÊ BI 1.4 35 6NLB 4 LÊ NI 1.5 45 Thì dữ liệu của các phần tử được lưu trữ trong bộ nhớ RAM là: 5TĐT LÊ VI 1.4 35 9TDT F= 7TĐT LÊ LI 1.7 65 8NLB 9TĐT LÊ HI 1.5 45 NULL 6NLB LÊ NI 1.6 55 9TĐT 8NLB LÊ BI 1.next Before=after; after=(*after).next; - Liệt kê các phần tử trong danh sách: Ta liệt kê các phần tử kể từ phần tử đầu tiên được chỉ bởi biến con trỏ F và dựa vào trường liên kết next để lần lượt liệt kê các phần tử tiếp theo. Biến con trỏ p lần lượt chỉ đến từng phần tử trong danh sách bắt đầu từ phần tử đầu tiên chỉ bởi F trở đi.next; } } - Tìm kiếm một phần tử trong danh sách: Tìm phần tử có họ tên x trong danh sách.

Ta tìm bắt đầu từ phần tử đầu tiên được chỉ bởi F trở đi cho đến khi tìm được phần tử cần tìm hoặc đã kiểm tra xong phần tử cuối cùng mà không có thì dừng. Hàm Search(F, x) kiểu List, tìm và trả về địa chỉ của phần tử đầu tiên tìm được hoặc trả về giá trị NULL nếu tìm không có.ht,x) !=0 ) ------------------------------------------------------------------------------------------------------------ Cấu trúc dữ liệu – Trang 15 p= (*p).next; return p; } - Thêm một phần tử vào đầu danh sách: Thêm một phần tử có họ tên x, chiều cao y, cân nặng tiêu chuẩn z vào đầu danh sách. Biến con trỏ p chỉ đến phần tử mới cần thêm vào.next “chỉ đến phần tử giống” F “chỉ” F = p; // 2 } F=NULL; Nhập LI 1 LI Nhập BI 1 BI 2 LI Nhập VI 1 VI 2 BI 3 L1 - Thêm một phần tử vào danh sách đã có thứ tự: Thêm một phần tử có họ tên x, chiều cao y, cân nặng tiêu chuẩn z vào danh sách trước đó đã có thứ tự họ tên tăng dần. Biến con trỏ p chỉ đến phần tử mới cần thêm vào.

Các biến con trỏ before và after lần lượt chỉ đến phần tử đứng ngay trước và ngay sau phần tử mới. Để tìm after thì ta tìm bắt đầu từ phần tử đầu tiên chỉ bởi F trở đi cho đến khi gặp được phần tử đầu tiên có họ tên lớn hơn x thì dừng, rồi chèn phần tử mới vào giữa.cntc=z; after=F; while ( (after!=NULL) && ( strcmp((*after).ht , x)<0 ) ) { before=after; after=(*after).next=after; // 1 if (F==after) F=p; // 2’ else (*before).