Giáo trình môn học cấu trúc dữ liệu và giải thuật

Giáo trình cấu trúc dữ liệu và giải thuật hiệu quả cung cấp kiến thức cơ bản và nâng cao giúp phát triển kỹ năng lập trình và tối ưu thuật toán.

• Trường học: Trường Cao Đẳng Kỹ Thuật Lý Tự Trọng
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Giáo Trình Môn Học Cấu Trúc Dữ Liệu & Giải Thuật
• Loại tài liệu: Giáo Trình

Mục lục chi tiết

• CHƯƠNG 0: MỞ ĐẦU
• 0.1. I. Cấu Trúc Dữ Liệu (Data Structure)
• 0.2. II. Giải Thuật (Algorithm)
• 0.3. III. Mối Quan Hệ Giữa Cấu Trúc Dữ Liệu Và Giải Thuật
• 1. CHƯƠNG 1: TÌM KIẾM VÀ SẮP XẾP
• 1.1. Bài 1: Tìm Kiếm (Searching)
• 1.1.1. I. Tìm Tuyến Tính (Linear Search)
• 1.1.2. II. Tìm Nhị Phân (Binary Search)
• 1.2. Bài 2: Sắp Xếp (Sorting)
• 1.2.1. I. Phương Pháp Đổi Chỗ Trực Tiếp (Interchange Sort)
• 1.2.2. II. Phương Pháp Chọn Trực Tiếp (Selection Sort)
• 1.2.3. III. Phương Pháp Chèn Trực Tiếp (Insertion Sort)
• 1.2.4. IV. Phương Pháp Nổi Bọt (Bubble Sort)
• 1.2.5. V. Phương Pháp Sắp Xếp Bằng Cách Phân Hoạch (Quick Sort)
• 2. CHƯƠNG 2: CẤU TRÚC DỮ LIỆU ĐỘNG
• 2.1. Bài 1: Danh Sách Liên Kết
• 2.2. Bài 2: Danh Sách Liên Kết Đơn
• 2.3. Bài 3: Sắp Xếp Trên Danh Sách Liên Kết Đơn
• 2.4. Bài 4: Danh Sách Hạn Chế
• 4. CHƯƠNG 4: CÂY
• 4.1. Bài 1: Cấu Trúc Cây
• 4.2. Bài 2: Cây Nhị Phân Tìm Kiếm

Tóm tắt

I. Tổng quan về giáo trình cấu trúc dữ liệu và giải thuật hiệu quả

Giáo trình cấu trúc dữ liệu và giải thuật đóng vai trò cốt lõi trong chương trình đào tạo kỹ sư công nghệ thông tin. Tài liệu này hệ thống hóa các nguyên lý tổ chức dữ liệu và phương pháp xử lý logic trên máy tính. Một cấu trúc dữ liệu tốt phải phản ánh chính xác bài toán thực tế. Đồng thời, cấu trúc đó cần đáp ứng tốt các thao tác truy xuất, thêm, xóa phần tử. Mối quan hệ giữa cấu trúc dữ liệu và thuật toán được thể hiện qua công thức kinh điển: Thuật toán cộng Cấu trúc dữ liệu tạo nên Chương trình. Việc lựa chọn mô hình lưu trữ quyết định trực tiếp đến hiệu năng của toàn bộ hệ thống. Chương trình sử dụng tài nguyên tối ưu sẽ chạy nhanh và tiết kiệm bộ nhớ. Ngược lại, thiết kế sai lầm dẫn đến lãng phí phần cứng và gây tắc nghẽn tiến trình. Tài liệu chuẩn mực giúp sinh viên tiếp cận ngôn ngữ C và C++ một cách bài bản. Ngôn ngữ lập trình này hỗ trợ quản lý bộ nhớ trực tiếp thông qua con trỏ. Giáo trình cung cấp nền tảng vững chắc phục vụ phát triển ứng dụng công nghệ thông tin hiện đại.

1.1. Bản chất khoa học của cấu trúc dữ liệu

Cấu trúc dữ liệu là tập hợp các phần tử dữ liệu cùng mối quan hệ giữa chúng trong máy tính. Mỗi cấu trúc phản ánh trực tiếp một khía cạnh của bài toán thực tế. Ví dụ, việc lưu trữ hồ sơ nhân viên yêu cầu kết hợp nhiều trường thông tin như mã định danh, họ tên và hệ số lương. Thiết kế cấu trúc đúng giúp dữ liệu luôn nhất quán và an toàn. Cấu trúc dữ liệu còn quy định các phép toán hợp lệ trên tập dữ liệu. Các thao tác cơ bản bao gồm tìm kiếm, chèn, xóa và duyệt phần tử. Khi tổ chức dữ liệu khoa học, thuật toán thao tác trở nên đơn giản và mạch lạc. Kỹ sư dễ dàng kiểm soát luồng dữ liệu và hạn chế lỗi phát sinh trong mã nguồn. Đây là nền tảng cốt lõi cấu thành mọi phần mềm máy tính chất lượng cao.

1.2. Mối quan hệ giữa giải thuật và hiệu năng phần mềm

Giải thuật là chuỗi các chỉ dẫn logic hữu hạn nhằm giải quyết một vấn đề xác định. Một giải thuật chính xác phải đảm bảo tính dừng, tính xác định và tính hiệu quả. Thuật toán hoạt động trực tiếp trên cấu trúc dữ liệu đã được định nghĩa. Sự kết hợp này quyết định tốc độ phản hồi của toàn bộ ứng dụng. Độ phức tạp thời gian và không gian là hai thước đo quan trọng của giải thuật. Ký hiệu Big-O biểu diễn sự tăng trưởng tài nguyên khi kích thước dữ liệu tăng. Một giải thuật kém khiến hệ thống sụt giảm hiệu năng khi lưu lượng truy cập cao. Ngược lại, giải thuật tối ưu duy trì độ ổn định trên máy chủ phân tán. Kỹ sư phần mềm luôn phải phân tích thuật toán trước khi triển khai hệ thống.

II. Rào cản học giáo trình cấu trúc dữ liệu và giải thuật hiệu quả

Người học công nghệ thông tin thường gặp nhiều trở ngại lớn khi nghiên cứu môn cấu trúc dữ liệu và giải thuật. Nguyên nhân hàng đầu xuất phát từ tính chất trừu tượng cao của các mô hình toán học và lý thuyết thuật toán. Nhiều sinh viên chỉ ghi nhớ cú pháp mã nguồn thay vì hiểu rõ bản chất vận hành bên dưới bộ nhớ máy tính. Vấn đề quản lý bộ nhớ động và con trỏ trong ngôn ngữ C/C++ là rào cản kỹ thuật phổ biến nhất. Các lỗi rò rỉ bộ nhớ, truy cập vùng nhớ rác hoặc giải phóng sai địa chỉ con trỏ thường xuyên xảy ra. Những sai sót này rất khó phát hiện và dễ làm sụp đổ chương trình khi biên dịch. Bên cạnh đó, việc thiếu hụt bài tập thực hành chuyên sâu khiến kiến thức lý thuyết nhanh chóng bị lãng quên. Người học khó hình dung cách áp dụng cấu trúc dữ liệu vào các dự án phần mềm quy mô lớn. Sự thiếu hụt tư duy phân tích độ phức tạp thuật toán cũng dẫn đến việc viết mã nguồn kém tối ưu. Hệ quả là chương trình tiêu tốn quá nhiều tài nguyên phần cứng và xử lý rất chậm chạp.

2.1. Cạm bẫy khi quản lý con trỏ và cấp phát bộ nhớ động

Con trỏ là công cụ mạnh mẽ nhưng chứa đựng nhiều rủi ro nghiêm trọng trong lập trình C/C++. Khi thao tác trên danh sách liên kết, việc đứt gãy liên kết con trỏ sẽ phá hủy toàn bộ dữ liệu. Lỗi con trỏ hoang xuất hiện khi giải phóng vùng nhớ nhưng không gán con trỏ về giá trị NULL. Hiện tượng rò rỉ tài nguyên nảy sinh do cấp phát bộ nhớ nhưng quên thu hồi sau khi dùng. Máy tính dần cạn kiệt RAM, dẫn đến tình trạng treo chương trình và đóng băng tiến trình hệ điều hành. Kỹ sư phần mềm thiếu kinh nghiệm thường gặp bế tắc khi xử lý các lỗi truy cập bộ nhớ bất hợp pháp. Việc gỡ lỗi con trỏ đòi hỏi sự tỉ mỉ, công cụ chuyên biệt và kiến thức cấu trúc sâu sắc.

2.2. Khó khăn trong việc đánh giá độ phức tạp thuật toán

Đánh giá độ phức tạp tính toán đòi hỏi tư duy phân tích toán học vô cùng chặt chẽ. Nhiều sinh viên chỉ chú trọng tính đúng đắn của kết quả mà bỏ qua chi phí tài nguyên phần cứng. Việc lạm dụng các vòng lặp lồng nhau vô tình đẩy độ phức tạp thời gian lên cấp số nhân. Hệ thống ứng dụng trở nên quá tải khi số lượng bản ghi tăng từ hàng nghìn lên hàng triệu. Thuật toán tìm kiếm tuần tự hoặc sắp xếp nổi bọt bộc lộ rõ sự yếu kém trên tập dữ liệu lớn. Thiếu kỹ năng tính toán tiệm cận khiến người lập trình không dự đoán được ngưỡng chịu tải của phần mềm. Đây là nguyên nhân chính dẫn đến sự cố sập máy chủ khi lưu lượng người dùng tăng đột biến.

III. Phương pháp học giáo trình cấu trúc dữ liệu và giải thuật hiệu quả

Để tiếp thu trọn vẹn giáo trình cấu trúc dữ liệu và giải thuật, người học cần áp dụng phương pháp kết hợp lý thuyết và thực hành. Bước khởi đầu quan trọng là vẽ sơ đồ minh họa cơ chế vận hành của cấu trúc dữ liệu trên giấy hoặc bảng vẽ. Việc trực quan hóa đường đi của con trỏ hay cách dữ liệu vào ra giúp hiểu sâu bản chất vấn đề. Kế tiếp, sinh viên nên tự tay lập trình từng cấu trúc dữ liệu từ con số không bằng ngôn ngữ C/C++. Từng thao tác cấp phát, liên kết và giải phóng vùng nhớ phải được kiểm tra tỉ mỉ qua trình gỡ lỗi debugger. Quá trình này loại bỏ hoàn toàn các giả định sai lầm và xây dựng phản xạ lập trình an toàn. Bên cạnh đó, việc giải quyết các bài toán cổ điển như đảo chuỗi, duyệt cây nhị phân và đổi cơ số là bắt buộc. Áp dụng thuật toán vào các dự án phần mềm mini giúp chuyển hóa kiến thức trừu tượng thành kỹ năng kỹ thuật vững chắc. Luyện tập thường xuyên trên các hệ thống chấm mã tự động là chìa khóa then chốt để thành thạo môn học này.

3.1. Kỹ thuật trực quan hóa mô hình dữ liệu động

Trực quan hóa là phương pháp tối ưu nhất để nắm bắt cấu trúc dữ liệu động. Trước khi viết mã danh sách liên kết, người học cần vẽ sơ đồ từng ô nhớ gồm trường dữ liệu và trường con trỏ link. Khi thao tác chèn hoặc xóa node, việc vẽ lại các mũi tên liên kết giúp ngăn ngừa triệt để lỗi đứt mạch dữ liệu. Các công cụ mô phỏng thuật toán trực quan cung cấp góc nhìn sinh động về tiến trình xử lý thông tin. Người học quan sát tường tận quá trình hoán đổi vị trí mảng, đẩy dữ liệu vào ngăn xếp và lấy dữ liệu khỏi hàng đợi. Nhờ việc hình tượng hóa bộ nhớ máy tính, tư duy logic được nâng cao và hạn chế tối đa sai sót cú pháp. Phương pháp trực quan biến các khái niệm trừu tượng thành kiến thức trực quan dễ nhớ và dễ ứng dụng.

3.2. Lộ trình thực hành qua các bài toán kinh điển

Thực hành có hệ thống là con đường ngắn nhất để làm chủ cấu trúc dữ liệu và giải thuật. Bắt đầu bằng việc cài đặt danh sách liên kết đơn để quản lý danh sách hồ sơ sinh viên gồm mã số, họ tên. Tiếp theo, ứng dụng cấu trúc ngăn xếp để giải quyết bài toán đổi hệ thập phân sang hệ nhị phân và thập lục phân. Cấu trúc hàng đợi được đưa vào mô phỏng các hàng đợi xử lý lệnh in hoặc điều phối tác vụ hệ điều hành. Nâng cao hơn, người học tiến hành xây dựng cây nhị phân tìm kiếm để tối ưu hóa thao tác tra cứu dữ liệu. Bài tập cộng và nhân đa thức nhiều biến trên danh sách liên kết là phép thử xuất sắc cho năng lực lập trình. Lộ trình từng bước giúp tích lũy phản xạ phân tích thuật toán chuyên nghiệp cho kỹ sư phần mềm.

IV. Ứng dụng từ giáo trình cấu trúc dữ liệu và giải thuật hiệu quả

Cấu trúc dữ liệu và giải thuật không đơn thuần là môn học lý thuyết trên giảng đường đại học mà là linh hồn của mọi hệ thống công nghệ. Mọi giải pháp phần mềm hiện đại, từ ứng dụng di động nhỏ gọn đến nền tảng đám mây khổng lồ, đều vận hành dựa trên các nguyên lý này. Việc nắm vững giáo trình tạo ra bước nhảy vọt về tư duy thiết kế phần mềm cho các kỹ sư công nghệ. Trong thực tế, cấu trúc ngăn xếp stack điều khiển cơ chế hoàn tác Undo/Redo và quản lý luồng thực thi hàm trong trình biên dịch. Cấu trúc hàng đợi queue chịu trách nhiệm điều phối hàng đợi tác vụ hệ điều hành và cân bằng tải hệ thống mạng. Cây nhị phân tìm kiếm đóng vai trò cốt lõi trong cơ chế đánh chỉ mục của các hệ quản trị cơ sở dữ liệu quan hệ. Đồng thời, đồ thị tối ưu hóa các thuật toán định tuyến gói tin viễn thông và gợi ý kết nối mạng xã hội. Năng lực lựa chọn cấu trúc dữ liệu chuẩn xác quyết định trực tiếp khả năng chịu tải hàng triệu người dùng cùng lúc. Nắm vững nền tảng học thuật này đảm bảo sự thăng tiến vững chắc trên con đường kỹ sư phần mềm cao cấp.

4.1. Ứng dụng cấu trúc dữ liệu tuyến tính trong kỹ thuật phần mềm

Cấu trúc dữ liệu tuyến tính gồm danh sách liên kết, ngăn xếp và hàng đợi xuất hiện rộng khắp trong hệ điều hành máy tính. Danh sách liên kết đơn hỗ trợ cấp phát bộ nhớ động linh hoạt mà không cần các khối nhớ vật lý liên tục. Cấu trúc ngăn xếp quản lý khung gọi hàm, xử lý biểu thức toán học dạng trung tố và kiểm tra tính hợp lệ của dấu ngoặc. Ngăn xếp cũng là hạt nhân của chức năng hoàn tác Undo trong các ứng dụng soạn thảo văn bản. Bên cạnh đó, hàng đợi đảm nhiệm việc điều phối tác vụ in ấn và truyền nhận gói tin mạng Internet. Nắm vững các cấu trúc tuyến tính giúp kỹ sư xây dựng hệ sinh thái phần mềm ổn định và có độ trễ xử lý thấp.

4.2. Tầm quan trọng của cấu trúc phi tuyến trong dữ liệu lớn

Cấu trúc dữ liệu phi tuyến như cây nhị phân tìm kiếm, cây B-Tree và đồ thị là giải pháp cho bài toán dữ liệu quy mô lớn. Trong cơ sở dữ liệu quan hệ, cây chỉ mục giúp giảm số lần đọc ghi ổ cứng từ hàng triệu bản ghi xuống vài thao tác. Tốc độ truy vấn dữ liệu được tăng tốc vượt trội so với phương pháp tìm kiếm tuần tự. Trên không gian mạng, cấu trúc đồ thị biểu diễn liên kết giữa hàng tỷ người dùng mạng xã hội hoặc mạng lưới giao thông. Các thuật toán tìm đường đi ngắn nhất hỗ trợ điều hướng phương tiện theo thời gian thực. Nắm vững cấu trúc phi tuyến trang bị năng lực xây dựng các nền tảng dữ liệu lớn hiện đại.

Nội dung chính

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

Giáo trình môn học Cấu trúc dữ liệu & Giải thuật là tài liệu học tập lưu hành nội bộ do Thạc sĩ Nguyễn Văn Giang biên soạn ngày 14 tháng 05 năm 2007, trực thuộc Khoa Công nghệ Thông tin – Trường Cao đẳng Kỹ thuật Lý Tự Trọng. Trong chương trình đào tạo, học phần này giữ vị trí thuộc khối Kiến thức cơ sở ngành, đóng vai trò bản lề kết nối giữa kiến thức lập trình cơ bản với các môn chuyên ngành tiếp theo.

Mục tiêu học tập trọng tâm của giáo trình bao gồm:

• Cung cấp hệ thống lý thuyết nền tảng về các mô hình tổ chức dữ liệu và nguyên lý hoạt động của các thuật toán kinh điển.
• Rèn luyện kỹ năng hiện thực hóa giải thuật thông qua mã nguồn cài đặt cụ thể bằng ngôn ngữ C/C++.
• Hình thành tư duy tối ưu hóa hiệu năng chương trình dựa trên việc đánh giá mức độ chiếm dụng tài nguyên hệ thống (bộ nhớ và thời gian thực thi).

Về mặt cấu trúc, tài liệu được triển khai theo tiến trình từ tư duy trừu tượng đến hiện thực cụ thể: bắt đầu từ khái niệm nhập môn ở Chương 0, các kỹ thuật xử lý trên mảng tĩnh ở Chương 1, chuyển tiếp sang cấu trúc cấp phát động và danh sách hạn chế ở Chương 2, đồng thời định hướng sang cấu trúc phân nhánh ở phần kế tiếp. Cách tiếp cận của giáo trình lấy luận điểm của nhà khoa học máy tính Niklaus Wirth làm trục định hướng: "Data structures + Algorithms = Programs" (Cấu trúc dữ liệu + Giải thuật = Chương trình).

Đặc điểm đặc sắc của tài liệu nằm ở tính trực quan và gắn liền với mã lệnh: mỗi giải thuật đều được phân tích theo 4 bước gồm phát biểu ý tưởng, bảng mô phỏng từng bước (trace table), mã cài đặt bằng C/C++ và bảng tổng kết độ phức tạp định lượng cho từng trường hợp.

---

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

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

Căn cứ theo đề cương và văn bản tài liệu, hệ thống kiến thức được phân bổ theo trình tự logic chặt chẽ:

• Chương 0: Mở đầu: Trình bày định nghĩa cấu trúc dữ liệu như một tập hợp các biến và kiểu dữ liệu có liên kết. Xác lập 3 tiêu chuẩn cốt lõi của một cấu trúc dữ liệu tốt: phản ánh đúng thực tế, phù hợp với thao tác xử lý, và tiết kiệm tài nguyên hệ thống (thời gian xử lý đối lập với dung lượng bộ nhớ). Mối quan hệ giữa cấu trúc dữ liệu và giải thuật được minh họa qua bài toán đảo ngược số tự nhiên $N$ (tối đa 9 chữ số) thông qua hai giải pháp: xử lý số học toán tử %, / trên biến kiểu unsigned long hoặc thao tác xử lý chuỗi ký tự bằng hàm strrev.
• Chương 1: Tìm kiếm và sắp xếp:
  • Bài 1 - Tìm kiếm: Phân định giữa tìm kiếm nội (bộ nhớ trong RAM) và tìm kiếm ngoại (bộ nhớ ngoài). Tập trung chi tiết vào hai thuật toán tìm kiếm nội: Tìm kiếm tuyến tính (Linear Search – cài đặt tuần tự và phiên bản cải tiến dùng phần tử cầm canh) cùng Tìm kiếm nhị phân (Binary Search – cài đặt bằng đệ quy và không đệ quy trên dãy đã sắp thứ tự).
  • Bài 2 - Sắp xếp: Trình bày bài toán hoán vị qua hàm Swap(a, b) và khảo sát 5 giải thuật sắp xếp nội trên mảng số nguyên: Đổi chỗ trực tiếp (Interchange Sort), Chọn trực tiếp (Selection Sort), Chèn trực tiếp (Insertion Sort), Nổi bọt (Bubble Sort), và Sắp xếp phân hoạch (Quick Sort sử dụng phần tử mốc ở giữa đoạn $x = a[(l+r)/2]$).
• Chương 2: Cấu trúc dữ liệu động:
  • Bài 1 & Bài 2 - Danh sách liên kết và Danh sách liên kết đơn: Đối chiếu bản chất giữa biến không động (tĩnh, tường minh, cấp phát tại Data segment/Stack, kích thước cố định) và biến động (không tường minh, cấp phát trên Heap qua con trỏ, kích thước biến đổi). Định nghĩa danh sách kề (danh sách đặc) và danh sách liên kết (đơn, kép, vòng). Xây dựng cấu trúc danh sách liên kết đơn gồm các node chứa vùng data và con trỏ link, quản lý thông qua hai con trỏ first và last. Cung cấp mã nguồn các thao tác cơ bản: khởi tạo InitList, cấp phát động GetNode dùng malloc, chèn (InsertFirst, InsertLast, InsertAfter), duyệt hiển thị, tìm kiếm, và thu hồi bộ nhớ (RemoveFirst, RemoveAfter, RemoveAll).
  • Bài 3 - Sắp xếp trên danh sách liên kết đơn: Phân tích hai hướng tiếp cận: hoán vị vùng data (áp dụng cho Interchange, Selection, Bubble Sort) và thay đổi liên kết link (áp dụng cho Quick Sort thông qua việc phân tách danh sách ban đầu thành hai danh sách con l1, l2 dựa trên node mốc x, sau đó đệ quy và nối danh sách).
  • Bài 4 - Danh sách hạn chế: Khảo sát cấu trúc Stack (nguyên lý LIFO: Push, Pop, Empty) và Queue (nguyên lý FIFO: EnQueue, DeQueue, Empty). Cả hai cấu trúc đều được hướng dẫn cài đặt qua hai cơ chế: mảng một chiều (mảng xoay vòng đối với Queue, kiểm soát tràn UNDERFLOW) và danh sách liên kết đơn. Minh họa giải thuật khử đệ quy bài toán Tháp Hà Nội bằng Stack mảng.
• Chương 4: Cấu trúc Cây: Giới thiệu cấu trúc phi tuyến tính, trọng tâm là Cây nhị phân tìm kiếm.

Progression logic của giáo trình đi từ cấu trúc tuần tự trên bộ nhớ tĩnh (mảng 1 chiều) sang cấu trúc động tuyến tính trên bộ nhớ Heap (con trỏ, danh sách liên kết), tiếp tục khái quát hóa thành cấu trúc tuyến tính có kỷ luật truy xuất riêng biệt (Stack, Queue), và mở rộng lên cấu trúc phân nhánh phân cấp (Cây).

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

• Fundamental theories: Lý thuyết tổ chức và phân vùng bộ nhớ máy tính, phân định rõ ràng cơ chế hoạt động của Data segment, Call Stack và Heap. Khái niệm kiểu dữ liệu trừu tượng (ADT) biểu diễn thông qua cấu trúc struct trong ngôn ngữ lập trình.
• Core principles: Nguyên lý đánh đổi tài nguyên (Space-Time Tradeoff), nhận thức rằng việc tiết kiệm dung lượng bộ nhớ và việc tối ưu thời gian thực thi thường có mối quan hệ mâu thuẫn (như minh họa tại Chương 0 khi sử dụng biến tạm trong sắp xếp). Nguyên lý truy xuất dữ liệu tuần tự (Sequential Access) so với truy xuất trực tiếp qua chỉ mục (Random/Indexed Access).
• Essential frameworks: Khung lý thuyết đánh giá độ phức tạp thuật toán thời gian $T(n)$ theo ký pháp Big-O ($O(1)$, $O(\log_2 n)$, $O(n)$, $O(n^2)$, $O(n \log n)$). Hệ thống đánh giá dựa trên việc đếm số phép so sánh và số phép hoán vị/phép gán trong ba trạng thái: Tốt nhất, Xấu nhất, và Trung bình.

Kỹ năng phát triển

• Technical skills: Kỹ năng lập trình ngôn ngữ C/C++ ở cấp độ thao tác con trỏ, quản lý bộ nhớ động thông qua hàm malloc và free, định nghĩa cấu trúc dữ liệu nhiều trường thông qua từ khóa typedef struct.
• Analytical skills: Khả năng phân tích bài toán thực tế để lựa chọn kiểu dữ liệu phù hợp (ví dụ lựa chọn kiểu chuỗi ký tự thay cho số nguyên để lưu mã sinh viên khi có ký tự chữ); kỹ năng chạy tay giải thuật (dry run) để theo dõi biến qua từng vòng lặp.
• Practical competencies: Năng lực tổ chức dữ liệu ứng dụng, cài đặt các module tìm kiếm, sắp xếp đa tiêu chí cho các hệ thống quản lý dữ liệu bảng, và xây dựng các cấu trúc điều phối trạng thái.

---

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

Giáo trình sử dụng phương pháp sư phạm diễn dịch kết hợp minh họa trực quan: mỗi giải thuật được mở đầu bằng việc phát biểu ý tưởng toán học, tiếp nối bằng ví dụ bằng số cụ thể được thể hiện qua các bảng trạng thái từng bước, sau đó là mã nguồn C/C++ hoàn chỉnh, và kết thúc bằng việc chứng minh độ phức tạp toán học.

Hệ thống bài tập và tình huống thực hành được bố trí phong phú sau mỗi chương:

• Bài tập giải thuật cơ sở: Yêu cầu tính toán số phép so sánh cụ thể cho một dãy số cho trước (ví dụ: tìm $x=1$ trong dãy bằng Linear Search và Binary Search; sắp xếp dãy $5, 15, 12, 2, 10, 12, 7, 0, 7$); xây dựng chương trình menu cho phép người dùng lựa chọn thuật toán sắp xếp tăng dần hoặc giảm dần và in ra màn hình kết quả sau từng bước hoán vị.
• Bài toán quản lý hồ sơ thực tế: Thiết kế kiểu dữ liệu hồ sơ nhân viên gồm các trường: mã số nhân viên, họ, lót, tên, tuổi, số điện thoại. Yêu cầu hiện thực hóa các chức năng: nhập/xuất bảng, tìm kiếm theo mã, sắp xếp giảm dần theo mã, sắp xếp tăng dần theo tên (nếu trùng tên thì sắp theo họ lót), thêm mới có kiểm tra trùng lặp, và xóa nhân viên theo mã. Bài toán này được yêu cầu thực hiện trên mảng (Chương 1) và cài đặt lại hoàn chỉnh trên danh sách liên kết đơn (Chương 2).
• Bài toán mô phỏng hệ thống và cấu trúc hạn chế:
  • Mô phỏng chuỗi thao tác trên Stack và Queue thông qua chuỗi ký tự thử nghiệm: EAS*Y**QUE***ST***I*ON (trong đó chữ cái đại diện cho phép nạp, dấu * đại diện cho phép lấy ra).
  • Ứng dụng Stack để chuyển đổi số nguyên hệ thập phân sang các hệ cơ số nhị phân (binary), bát phân (octal), thập lục phân (hexadecimal) bằng thuật toán chia lấy dư liên tiếp.
  • Ứng dụng Stack kiểm tra tính hợp lệ của các cặp dấu ngoặc và tính toán giá trị biểu thức toán học dạng infix, ví dụ: (((b + a) / 3) * (b - a)).
  • Khử đệ quy bài toán Tháp Hà Nội bằng Stack mảng để lưu trữ trạng thái các tham số và địa chỉ trở về giữa các mức gọi hàm.
• Bài toán xử lý đại số: Biểu diễn đa thức $P(x) = a_n X^n + a_{n-1} X^{n-1} + \dots + a_1 X + a_0$ bằng danh sách liên kết (mỗi node gồm 3 trường: hệ số, số mũ, con trỏ liên kết) với trật tự số mũ giảm dần; lập trình các phép toán: cộng hai đa thức, nhân hai đa thức, và tính đạo hàm.

Về phương pháp đánh giá và tự học, giáo trình yêu cầu người học thực hành đối chiếu trực tiếp giữa hai phương án cài đặt: cùng một yêu cầu xử lý (như chèn có thứ tự, loại bỏ phần tử trùng lặp) phải thực hiện bằng cả mảng tĩnh và con trỏ động để tự rút ra kết luận về ưu nhược điểm của từng phương án.

---

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

• Tích hợp các tài liệu tham khảo học thuật chuẩn mực: Giáo trình kế thừa có chọn lọc các nội dung học thuật từ 4 tài liệu chuyên khảo uy tín:
  1. Nhập môn cấu trúc dữ liệu và thuật toán – Trần Hạnh Nhi & Dương Anh Đức (Giáo trình ĐH Khoa học Tự nhiên TP.HCM).
  2. Cấu trúc dữ liệu và giải thuật – Đỗ Xuân Lôi (NXB Đại học Quốc gia Hà Nội).
  3. Cấu trúc dữ liệu và giải thuật – Nguyễn Trung Trực (Giáo trình ĐH Bách khoa TP.HCM).
  4. Algorithms + Data Structures = Programs – Niklaus Wirth (bản dịch của Nguyễn Quốc Cường, NXB Đại học và Giáo dục chuyên nghiệp).
• Tính chuẩn xác trong thống kê độ phức tạp thuật toán: Mọi thuật toán tìm kiếm và sắp xếp trong Chương 1 đều có bảng lượng hóa chi tiết số lần so sánh và số lần hoán vị:
  • Linear Search: Tốt nhất 1 lần, Xấu nhất $n+1$ lần, Trung bình $(n+1)/2$ lần, độ phức tạp $O(n)$.
  • Binary Search: Tốt nhất 1 lần, Xấu nhất $\log_2 n$ lần, Trung bình $\log_2 n / 2$ lần, độ phức tạp $O(\log_2 n)$.
  • Interchange Sort: Số lần so sánh cố định $\frac{n(n-1)}{2}$; hoán vị tốt nhất 0, xấu nhất $\frac{n(n-1)}{2}$, độ phức tạp $O(n^2)$.
  • Selection Sort: Số lần so sánh cố định $\frac{n(n-1)}{2}$; số lần hoán vị luôn bằng $n-1$, độ phức tạp $O(n^2)$.
  • Insertion Sort: Tốt nhất $2(n-1)$ phép so sánh và $3(n-1)$ phép gán; xấu nhất $\frac{n(n-1)}{2}$ phép so sánh, độ phức tạp $O(n^2)$.
  • Bubble Sort: Số lần so sánh cố định $\frac{n(n-1)}{2}$; hoán vị tốt nhất 0, xấu nhất $\frac{n(n-1)}{2}$, độ phức tạp $O(n^2)$.
  • Quick Sort: Trường hợp trung bình đạt độ phức tạp $O(n \log n)$.
• Liên hệ sâu với kiến trúc hệ điều hành và phần cứng: Tài liệu không dừng lại ở mức mô tả cú pháp mà giải thích ứng dụng thực tế của cấu trúc dữ liệu trong máy tính:
  • Stack được chỉ rõ vai trò lưu trữ kết quả tạm thời khi xuất hiện ngắt (Interrupt) và quản lý lời gọi hàm con.
  • Queue được phân tích như cơ chế cốt lõi để hệ điều hành quản lý tiến trình (chuyển trạng thái giữa ready và running để nhận CPU) cũng như thiết lập hàng đợi tác vụ in ấn (print jobs).
  • Vấn đề rò rỉ bộ nhớ (memory leak) được giải quyết cụ thể bằng việc bắt buộc viết hàm thu hồi vùng nhớ Heap (RemoveAll bằng vòng lặp gọi free) khi giải phóng danh sách liên kết.

---

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

• Sinh viên mục tiêu:
  • Đối tượng đào tạo chính: Sinh viên bậc Cao đẳng Kỹ thuật chuyên ngành Công nghệ phần mềm và Mạng máy tính. Giáo trình được dùng cho học phần thuộc khối kiến thức cơ sở ngành (thường bố trí ở học kỳ 2 năm thứ nhất hoặc năm thứ hai).
  • Đối tượng đào tạo mở rộng: Học sinh, sinh viên hệ Trung cấp chuyên ngành Công nghệ phần mềm. Đối với hệ này, các nội dung nâng cao (như khử đệ quy bằng Stack, Quick Sort trên danh sách liên kết, các bài toán thao tác con trỏ phức tạp) được định vị là phần tài liệu tham khảo mở rộng.
• Kiến thức tiên quyết (Prerequisites):
  • Môn Toán ứng dụng cho tin học: Người học cần nắm vững phương pháp biểu diễn giải thuật, logic toán học và phương pháp tính toán độ phức tạp thuật toán.
  • Ngôn ngữ lập trình C/C++: Người học cần thành thạo cú pháp cơ sở, các cấu trúc điều khiển vòng lặp, mảng dữ liệu, cấu trúc bản ghi struct, cú pháp vào/ra (cin/cout, printf) và kiến thức cơ bản về địa chỉ con trỏ.
• Giảng viên và hình thức giảng dạy:
  • Giảng viên sử dụng làm đề cương bài giảng lý thuyết trên lớp kết hợp hướng dẫn thực hành tại phòng máy. Các ví dụ minh họa và bài tập cuối chương cung cấp sẵn nguồn bài thực hành và câu hỏi kiểm tra kỹ năng lập trình.
• Tự học và tra cứu:
  • Tài liệu thích hợp cho người học muốn củng cố bản chất hoạt động của bộ nhớ máy tính (Heap, Stack), nắm chắc kỹ thuật xử lý liên kết con trỏ, và rèn luyện kỹ năng phân tích hiệu năng thuật toán.

---

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

1. Giáo trình này được thiết kế phù hợp nhất với những ai?

Giáo trình được biên soạn phục vụ trực tiếp cho sinh viên bậc Cao đẳng Kỹ thuật chuyên ngành Công nghệ phần mềm và Mạng máy tính thuộc Khoa Công nghệ Thông tin – Trường Cao đẳng Kỹ thuật Lý Tự Trọng. Ngoài ra, tài liệu cũng được sử dụng cho hệ Trung cấp chuyên ngành Công nghệ phần mềm làm tài liệu học tập và tham khảo.

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

Người học cần hoàn thành hai khối kiến thức tiên quyết: kiến thức toán học từ môn Toán ứng dụng cho tin học (đặc biệt là logic biểu diễn giải thuật và cách tính độ phức tạp) cùng kỹ năng lập trình ngôn ngữ C/C++ (sử dụng con trỏ, cấp phát bộ nhớ, khai báo cấu trúc struct và các câu lệnh điều khiển).

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

Giáo trình tập trung vào việc hiện thực hóa bằng mã nguồn thực tế: toàn bộ các giải thuật tìm kiếm, sắp xếp, thao tác danh sách liên kết, ngăn xếp và hàng đợi đều có code cài đặt C/C++ chi tiết. Đi kèm với đó là các bảng chạy tay (trace table) và bảng đánh giá độ phức tạp định lượng độc lập giữa số phép so sánh và số phép hoán vị.

4. Làm thế nào để tự học giáo trình này đạt hiệu quả cao?

Người học nên tuân thủ tiến trình 3 bước:

1. Đọc hiểu ý tưởng giải thuật và tự vẽ lại bảng mô phỏng từng bước (trace table) theo các ví dụ mẫu số học trong giáo trình.
2. Tự gõ lại và biên dịch mã nguồn C/C++, kiểm tra cơ chế cấp phát (malloc) và giải phóng (free) con trỏ.
3. Giải quyết toàn bộ hệ thống bài tập thực hành cuối mỗi chương, đặc biệt là các bài tập so sánh hiệu năng giữa hai cách cài đặt (mảng tĩnh và danh sách liên kết).

5. Giáo trình có những tài liệu bổ trợ hoặc tham khảo nào kèm theo?

Tài liệu biên soạn dựa trên 4 nguồn tài liệu tham khảo chính thống được công bố ở phần mở đầu: giáo trình của Đại học Khoa học Tự nhiên TP.HCM (Trần Hạnh Nhi & Dương Anh Đức), Đại học Bách khoa TP.HCM (Nguyễn Trung Trực), NXB Đại học Quốc gia Hà Nội (Đỗ Xuân Lôi), và công trình chuyên khảo của Niklaus Wirth do Nguyễn Quốc Cường dịch.

---

Kết luận

Giáo trình môn học Cấu trúc dữ liệu & Giải thuật của Trường Cao đẳng Kỹ thuật Lý Tự Trọng cung cấp một hệ thống kiến thức cơ sở ngành hoàn chỉnh, chặt chẽ và chuẩn xác về mặt khoa học máy tính. Giá trị cốt lõi của tài liệu thể hiện ở việc cụ thể hóa phương châm kinh điển của Niklaus Wirth: gắn kết hữu cơ cấu trúc dữ liệu với thuật toán thông qua mã nguồn C/C++ trực quan, cân bằng giữa lý thuyết độ phức tạp toán học và kỹ thuật quản lý tài nguyên phần cứng.

Lộ trình học tập khuyến nghị bắt đầu từ việc nắm vững 3 tiêu chuẩn đánh giá cấu trúc dữ liệu và mối liên hệ thuật toán tại Chương 0, làm chủ các thuật toán tìm kiếm và sắp xếp trên mảng tĩnh tại Chương 1, trước khi tiến hành làm chủ kỹ thuật thao tác con trỏ động, danh sách liên kết đơn, cấu trúc Stack, Queue tại Chương 2 và mở rộng sang Cây nhị phân tìm kiếm. Kết hợp học tập nội dung giáo trình với việc giải quyết các bài tập chuyên sâu (bài toán nhân viên, Tháp Hà Nội, biểu thức infix, đa thức) và đối chiếu với 4 tài liệu tham khảo chuẩn mực sẽ giúp người học hình thành nền tảng lập trình cấu trúc vững vàng.

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

Chương 1; TÌM KIẾM VÀ SẮP XEP Bài 1: TÌM KIẾM (SEARCHING) Tìm kiếm thông tin là một công việc rất thường gặp trong thực tế và cũng là trong - những ứng dụng quan trọng trong máy tính. Chẳng hạn ta đưa vào tên của một người ta , và yêu cầu may tính đưa ra danh sách các số điện thoai tương ứng. Hoặc ta đưa vào. họ tên hay mã số của một n gười trong cơ quan vA yêu cầu máy tính trích za các (hông ‘tin cá nhân liên quan đến người đó.

‘ Or - Trong bài này, chúng ta sé Om hiểu một sổ di thuật tìm kiếm dữ liệu cơ bắn VÀ - thường được ‹ sử dụng, Các giải thuật ầm kiếm dữ liệu được chủa thành hai nhóm: ." Tìm kiếm nội (internal Searchiag): Khi số lượng các dữ liệu được tìm kiến nhổ. và có thể chứa ở bộ nhớ trong của máy tính (RAM). phải ¡ lưu ở bộ nhớ đngbai iskitape). Tuy nhiên trong chương này, chúng ta chỉ bàn đến các giẢi thuật tim se nội.

ï, BÀI TOÁN 'TÌM KIẾM INPUT: Day (a) gồm n phần tử ao,ä2,., x là giá trị của phân tử cần tìm, gọi là khóa (key) OUTPUT:. 5 GV guia Vin Graig - Trường Cao Đẳng Kỹ Thuật Lý Tự Trọng - Khoa Công Nghệ Thông Tin EL TÌM TUYẾN TÍNH (LINEAR SEARCH) i. ¥ trong của giải thuật Lần lượt sơ sánh x với các a[Ù Œ=9, 1, 2,. : Nếu & afi] = =X chỉ đừng: và trẻ vei Ges ay Neu sng có afi] nào ‘bing x ile av vée-1.

" 'Ví dụ 1: Cho day số ố @) 2 28 5 1,6 8 15 Nếu khóa: cần tim 1a x=8 thi: két quả trả về l2. Nếu khóa cần tìm là x=7 th it quả trả về là 1 Lưu ý: Giải thuật tìm tuyển tính luôn trấ về vị trí xuất hiện đầu tiên của x trong day SỐ, -> , can 2. Cài điặt int LinearSeatch {int all ; int’n, int ~) (. PhwAt toda cải tiến.

` Nếu đặt thêm phần tử cÂm canh. roag mang luôn có phần tử bằng x nên vòng lập: while luôn kết thúc má không cần kiểm tra điều kiện ° ^ i<n. int ¡ = 0;a[n]=x; While (alilisx) | GV 22yã« 2, Gang Trường Cao Đẳng Ay Thuật Lý Tự Trọng - Khoa Công Nghệ Thông Tin itt; if ( i==n) return -1¿ return i; yo. Đánh giá giải thuật: Trường | Sổ lần 7 Gii chú hợp so sánh |' - : Tétnh&t | 1.

| Phẩn tử đầu tiên có giá trịx - Xấu nhất | a+ Không có X trong mảng TU TU i "Trung bình | @+l)/2 | Giả sử xác suất các phân | tử. trong mắng nhận giá trị x là | , : ) như nhau. Độ phức tạp của giải thuật là :Tín)= O(n) WL TIM Nj PHAN @INARY SEARCH) LY tưởng của giải thuật rong trường hợp day (a) đã được sắp thứ tự tăng dần thì ta có thể tìm nhanh phần từ tử có khóa x bằng phươn g pháp tìm nhị phân như sau, giống như cách tra từ trong từ điển: Giả sứ đấy tìm kiếm hiện hành là : a[1], a[H-1},. Thực hiện lại giải thuật với I=m+1 Nếu a[m]>x thì x chỉ có thể xuất hiện ở bên trái afra], pham vi tim kiểm được thu hẹp từ a{H,.

Thực hiện lại giải thuật với r=m-l Giải thuật dừng khi Ï> r và trả về -1, GV 2x „„ău⁄0á« điang Trường Cao Đẳng Kỹ Thuật Lý Tự Trọng - Khỏá Công Nghệ Thông Tïn Vi dy 2: Cho day sé (a) : : 218. Nếu khóa cần tìm là x=10 : sẻ , °k=Ð,r=7im =3, a " sì4, res m= =5, a[5]= BSK HH2 teen k va °]=6,r=7: “m= 6, a{6} = lo= x (in thy).