Giáo Trình Cấu Trúc Dữ Liệu và Giải Thuật cho Ngành Công Nghệ Thông Tin

Giáo trình cấu trúc dữ liệu và giải thuật cung cấp kiến thức cần thiết cho sinh viên ngành công nghệ thông tin cao đẳng liên thông.

• Người hướng dẫn: Trần Thái Mạnh - Chủ Biên
• Trường học: Cao đẳng Xây dựng số 1
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Giáo Trình Cấu Trúc Dữ Liệu và Giải Thuật Ngành Công Nghệ Thông Tin
• Loại tài liệu: giáo trình
• Năm xuất bản: 2022
• Địa điểm: Hà Nội

Mục lục chi tiết

• 1. CHƯƠNG 1: GIẢI THUẬT
• 1.1. Cấu trúc dữ liệu
• 1.2. Các đặc trưng của giải thuật
• 1.3. Dữ liệu vào
• 1.4. Dữ liệu ra
• 1.5. Ngôn ngữ diễn đạt
• 1.5.1. Ngôn ngữ thông thường
• 1.5.2. Lưu đồ
• 1.5.3. Ngôn ngữ lập trình
• 1.6. Phương pháp thiết kế giải thuật
• 1.6.1. Phân rã bài toán thành các bài toán nhỏ hơn
• 1.6.2. Phương pháp tinh chỉnh từng bước
• 2. CHƯƠNG 2: DANH SÁCH
• 2.1. Danh sách tuyến tính
• 2.1.1. Khái niệm chung
• 2.1.2. Kiểu hàng đợi
• 2.1.3. Danh sách liên kết
• 2.1.3.1. Danh sách liên kết đơn (singly linked list)
• 2.1.3.2. Danh sách liên kết vòng (circular linked list)
• 2.2. Kiểu mảng
• 2.3. Kiểu ngăn xếp
• 2.4. Kiểu hàng đợi
• 3. CHƯƠNG 3: MÔ HÌNH CÂY VÀ ĐỒ THỊ
• 4. CHƯƠNG 4: CÁC GIẢI THUẬT SẮP XẾP VÀ TÌM KIẾM
• 4.1. Sắp xếp kiểu đổi chỗ trực tiếp
• 4.2. Sắp xếp kiểu vun đống
• 4.3. Các giải thuật tìm kiếm
• 4.3.1. Bài toán tìm kiếm
• 4.3.2. Tìm kiếm nhị phân
• 4.3.3. 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

Giáo trình Cấu trúc dữ liệu và giải thuật là tài liệu quan trọng cho sinh viên ngành Công nghệ thông tin. Nó cung cấp kiến thức cơ bản về các kiểu cấu trúc dữ liệu và giải thuật, giúp sinh viên nắm vững các khái niệm cốt lõi trong lập trình. Nội dung giáo trình được chia thành nhiều chương, mỗi chương tập trung vào một khía cạnh khác nhau của cấu trúc dữ liệu và giải thuật.

1.1. Mục tiêu của giáo trình Cấu trúc dữ liệu

Giáo trình nhằm cung cấp cho sinh viên kiến thức về các kiểu cấu trúc dữ liệu thông dụng và các giải thuật cơ bản. Mục tiêu là giúp sinh viên có khả năng áp dụng kiến thức vào thực tiễn.

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

Giáo trình này được thiết kế cho sinh viên cao đẳng ngành Công nghệ thông tin, đặc biệt là những người học chuyên ngành ứng dụng phần mềm.

II. Những thách thức trong việc học Cấu trúc Dữ liệu và Giải thuật

Học Cấu trúc dữ liệu và giải thuật không chỉ đơn thuần là việc ghi nhớ lý thuyết mà còn yêu cầu sinh viên phải thực hành và áp dụng vào các bài toán thực tế. Một trong những thách thức lớn nhất là khả năng phân tích và giải quyết vấn đề một cách hiệu quả.

2.1. Khó khăn trong việc áp dụng lý thuyết vào thực tiễn

Nhiều sinh viên gặp khó khăn trong việc chuyển đổi lý thuyết thành thực hành. Việc này đòi hỏi sự tư duy logic và khả năng phân tích bài toán.

2.2. Đánh giá độ phức tạp của giải thuật

Đánh giá độ phức tạp của giải thuật là một kỹ năng quan trọng. Sinh viên cần hiểu rõ các khái niệm như độ phức tạp thời gian và không gian để có thể lựa chọn giải thuật phù hợp.

III. Phương pháp học hiệu quả Cấu trúc Dữ liệu và Giải thuật

Để học tốt môn Cấu trúc dữ liệu và giải thuật, sinh viên cần áp dụng các phương pháp học tập hiệu quả. Việc thực hành thường xuyên và tham gia vào các dự án thực tế sẽ giúp củng cố kiến thức.

3.1. Thực hành qua các bài tập lập trình

Thực hành lập trình là cách tốt nhất để hiểu rõ các khái niệm. Sinh viên nên làm nhiều bài tập và dự án nhỏ để rèn luyện kỹ năng.

3.2. Tham gia vào các nhóm học tập

Tham gia vào các nhóm học tập giúp sinh viên trao đổi kiến thức và giải quyết vấn đề một cách hiệu quả hơn. Học nhóm cũng tạo động lực cho việc học.

IV. Ứng dụng thực tiễn của Cấu trúc Dữ liệu và Giải thuật

Cấu trúc dữ liệu và giải thuật có ứng dụng rộng rãi trong nhiều lĩnh vực của ngành Công nghệ thông tin. Từ phát triển phần mềm đến xử lý dữ liệu lớn, kiến thức này là nền tảng cho nhiều công nghệ hiện đại.

4.1. Ứng dụng trong phát triển phần mềm

Các giải thuật và cấu trúc dữ liệu giúp tối ưu hóa hiệu suất của phần mềm, từ đó nâng cao trải nghiệm người dùng.

4.2. Ứng dụng trong khoa học dữ liệu

Trong khoa học dữ liệu, việc sử dụng cấu trúc dữ liệu phù hợp giúp xử lý và phân tích dữ liệu một cách hiệu quả.

V. Kết luận và tương lai của Cấu trúc Dữ liệu và Giải thuật

Cấu trúc dữ liệu và giải thuật sẽ tiếp tục đóng vai trò quan trọng trong sự phát triển của ngành Công nghệ thông tin. Việc nắm vững kiến thức này sẽ giúp sinh viên có nền tảng vững chắc cho sự nghiệp sau này.

5.1. Tầm quan trọng của việc học Cấu trúc Dữ liệu

Việc học Cấu trúc dữ liệu không chỉ giúp sinh viên có kiến thức chuyên môn mà còn phát triển tư duy logic và khả năng giải quyết vấn đề.

5.2. Xu hướng phát triển trong tương lai

Với sự phát triển của công nghệ, các giải thuật và cấu trúc dữ liệu sẽ ngày càng trở nên phức tạp và đa dạng hơn, đòi hỏi sinh viên phải không ngừng học hỏi và cập nhật kiến thức.

Nội dung chính

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

Giáo trình Cấu trúc dữ liệu và giải thuật (Mã môn học: MH09) do tác giả Trần Thị Mơ chủ biên, được ban hành chính thức kèm theo Quyết định số 374ĐT/QĐ-CĐXD1 ngày 16 tháng 08 năm 2022 của Hiệu trưởng Trường Cao đẳng Xây dựng số 1 (Hà Nội, 2022). Tài liệu được biên soạn phục vụ công tác giảng dạy và học tập cho trình độ Cao đẳng liên thông ngành Công nghệ thông tin (chuyên ngành Ứng dụng phần mềm).

Trong chương trình đào tạo nghề Công nghệ thông tin, Cấu trúc dữ liệu và giải thuật là môn học bắt buộc thuộc nhóm các môn học cơ sở ngành. Môn học có tổng thời lượng thực hiện là 45 giờ, bao gồm: 15 giờ lý thuyết; 28 giờ thực hành, thí nghiệm, thảo luận, bài tập; và 02 giờ kiểm tra định kỳ.

Mục tiêu học tập của giáo trình được xác định trên ba phương diện cụ thể:

• Về kiến thức: Cung cấp các khái niệm cơ bản về giải thuật, phương pháp đánh giá độ phức tạp của giải thuật; các kiểu cấu trúc dữ liệu thông dụng (mảng, ngăn xếp, hàng đợi, danh sách liên kết, cây, đồ thị) và các giải thuật thao tác trên các kiểu cấu trúc dữ liệu đó.
• Về kỹ năng: Giúp người học thiết kế được các giải thuật sắp xếp, tìm kiếm; vận dụng các kiểu cấu trúc dữ liệu thông dụng và giải thuật tương ứng để giải quyết các bài toán thực tiễn bằng ngôn ngữ lập trình.
• Về năng lực tự chủ và trách nhiệm: Rèn luyện ý thức chấp hành kỷ luật học tập và lao động, phát huy tinh thần chủ động nghiên cứu, khả năng sáng tạo và tính chính xác khoa học trong quá trình thao tác dữ liệu.

Cấu trúc giáo trình được thiết kế gồm 04 chương:

• Chương 1: Giải thuật
• Chương 2: Danh sách
• Chương 3: Mô hình cây và đồ thị
• Chương 4: Các giải thuật sắp xếp và tìm kiếm

Điểm đặc trưng trong cách tiếp cận của giáo trình là việc kết hợp chặt chẽ giữa lý thuyết hình thức (định nghĩa, tính chất, phân loại) với biểu diễn thuật toán qua sơ đồ khối và cài đặt mã nguồn mẫu bằng ngôn ngữ lập trình C/C++, trong đó thời lượng thực hành và bài tập chiếm tới 62,2% tổng quỹ thời gian đào tạo.

---

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

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

Nội dung giáo trình được triển khai qua 04 chương chuyên đề theo tiến trình logic từ tổng quan lý thuyết giải thuật đến các cấu trúc dữ liệu cụ thể và thuật toán xử lý:

• Chương 1: Giải thuật: Trình bày định nghĩa giải thuật và thiết lập mối quan hệ nền tảng: $\text{Cấu trúc dữ liệu} + \text{Giải thuật} = \text{Chương trình}$. Phân tích các đặc trưng bắt buộc của giải thuật bao gồm: tính xác định, tính khả thi và tính dừng (minh họa qua giải thuật Euclid). Chương 1 cũng quy định các hình thức diễn đạt giải thuật qua ngôn ngữ tự nhiên, sơ đồ khối (với các nút thao tác, nút điều khiển, nút khởi đầu/kết thúc, cung liên kết) và ngôn ngữ lập trình (mã giả, C/Pascal). Hai phương pháp thiết kế giải thuật trọng tâm được giới thiệu gồm: thiết kế từ trên xuống (Top-down design) và phương pháp tinh chỉnh từng bước (Stepwise refinement).

• Chương 2: Danh sách: Khảo sát các cấu trúc dữ liệu tuyến tính.

  • Kiểu mảng: Đánh giá ưu điểm truy cập ngẫu nhiên qua chỉ số và nhược điểm cố định kích thước bộ nhớ, tốn chi phí dời phần tử khi thêm/xóa.
  • Kiểu ngăn xếp (Stack): Hoạt động theo cơ chế LIFO (Last In First Out - Vào sau ra trước), với các thao tác push (đẩy vào đỉnh), pop (lấy ra từ đỉnh), kiểm tra rỗng, kiểm tra đầy; ứng dụng đổi cơ số 10 sang cơ số 2.
  • Kiểu hàng đợi (Queue): Hoạt động theo cơ chế FIFO (First In First Out - Vào trước ra trước), với các thao tác put (thêm vào đuôi), get (lấy ra từ đầu).
  • Danh sách liên kết: Gồm danh sách liên kết đơn (Singly linked list), danh sách liên kết kép (Doubly linked list) có thêm con trỏ pre, và danh sách liên kết vòng (Circular linked list). Chương này cung cấp mã nguồn C++ chi tiết cho các thao tác: createList(), createNode(), insertHead(), insertTail(), insertAfter(), processList(), searchList(), deleteList(), DeleteFirst(), DeleteEnd(), List_Selection_Sort(), List_Interchange_Sort().

• Chương 3: Mô hình cây và đồ thị: Giới thiệu các cấu trúc dữ liệu phi tuyến.

  • Mô hình cây và cây nhị phân: Định nghĩa quan hệ cha - con, nút gốc (root), cây con. Khảo sát cây nhị phân với tính chất: số nút ở mức $i \le 2^{i+1}$, số nút tối đa $2^h - 1$, chiều cao $n \ge h \ge \log_2(n+1)$. Triển khai cấu trúc động với hai con trỏ Lchild và Rchild. Ba phép duyệt cây nhị phân gồm: Duyệt tiền thứ (Node-Left-Right), Duyệt trung thứ (Left-Node-Right), và Duyệt hậu thứ (Left-Right-Node).
  • Mô hình đồ thị: Định nghĩa đồ thị có hướng $G = \langle V,E \rangle$, đồ thị vô hướng, đồ thị có trọng số, khái niệm bậc trong $|I(v)|$, bậc ngoài $|A(u)|$, đường đi, chu trình và tính liên thông. Hai phương pháp biểu diễn đồ thị: Ma trận kề kích thước $n \times n$ và Danh sách kề. Hai thuật toán duyệt đồ thị cơ bản: Duyệt theo chiều sâu (DeepFirstSearch - DFS sử dụng đệ quy và mảng đánh dấu daxet[]), Duyệt theo chiều rộng (BreadthFirstSearch - BFS sử dụng hàng đợi Queue).

• Chương 4: Các giải thuật sắp xếp và tìm kiếm: Phân tích bản chất bài toán sắp xếp, khóa sắp xếp, tính ổn định (stability) của giải thuật, và hai nhóm thuật toán theo độ phức tạp thời gian ($O(N^2)$ và $O(N\log N)$). Cài đặt và phân tích các giải thuật: Sắp xếp đổi chỗ trực tiếp (Exchange Sort), Sắp xếp kiểu chèn (Insertion Sort với độ phức tạp trung bình $O(N^2)$), Sắp xếp kiểu chọn (Selection Sort), giới thiệu Sắp xếp vun đống (Heap Sort) và Sắp xếp nhanh (Quick Sort). Trình bày các giải thuật tìm kiếm: Tìm kiếm tuần tự, Tìm kiếm nhị phân và Cây nhị phân tìm kiếm.

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

Giáo trình hình thành nền tảng khoa học máy tính thông qua các khối kiến thức:

• Lý thuyết giải thuật và độ phức tạp: Khái niệm bước toán học, điều kiện dừng, đánh giá hiệu quả thuật toán thông qua số lượng thao tác và dung lượng bộ nhớ.
• Nguyên lý cấu trúc dữ liệu trừu tượng (ADT): Phân định rõ ràng giữa cấu trúc lưu trữ vật lý (mảng, con trỏ động) và hành vi logic của kiểu dữ liệu trừu tượng (LIFO của Stack, FIFO của Queue).
• Lý thuyết cấu trúc phân cấp và mạng lưới: Nền tảng toán rời rạc về cây phân cấp và đồ thị liên thông ($V$ đỉnh, $E$ cạnh).
• Mô hình thiết kế phần mềm có cấu trúc: Nguyên lý phân rã Top-down và phương pháp tinh chỉnh từng bước trong lập trình hàm.

Kỹ năng phát triển

Thông qua hệ thống bài học và bài tập thực hành, người học được rèn luyện các nhóm kỹ năng:

• Kỹ năng kỹ thuật (Technical skills): Cài đặt cấu trúc dữ liệu bằng con trỏ và struct trong C/C++; quản lý cấp phát (new) và giải phóng (delete) vùng nhớ động; xây dựng các hàm đệ quy và cấu trúc dữ liệu lồng nhau.
• Kỹ năng phân tích (Analytical skills): Phân tích ưu/nhược điểm giữa mảng tĩnh và danh sách liên kết; lựa chọn cấu trúc biểu diễn đồ thị phù hợp (ma trận kề cho đồ thị dày, danh sách kề cho đồ thị thưa); so sánh chi phí thời gian thực hiện giữa các thuật toán sắp xếp và tìm kiếm.
• Kỹ năng ứng dụng thực tế (Practical competencies): Xây dựng các chương trình quản lý dữ liệu cụ thể (như quản lý danh sách hồ sơ sinh viên với các trường mã SV, họ tên, năm sinh, điểm trung bình; thực hiện tìm kiếm, sắp xếp theo nhiều tiêu chí).

---

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

Phương pháp tiếp cận sư phạm

Giáo trình áp dụng mô hình sư phạm kết hợp giữa diễn dịch lý thuyết và quy nạp thực hành:

1. Hình thành khái niệm: Đưa ra định nghĩa toán học và mô hình trừu tượng.
2. Mô hình hóa trực quan: Diễn giải quy trình hoạt động bằng lưu đồ khối (Flowchart) hoặc sơ đồ trạng thái từng bước (Trace table).
3. Hiện thực hóa mã nguồn: Chuyển đổi thuật toán thành các hàm/thủ tục hoàn chỉnh bằng ngôn ngữ C/C++.
4. Hệ thống hóa kiến thức: Bảng tổng kết yêu cầu lý thuyết và bài tập ở cuối mỗi chương.

Hệ thống bài tập và thực hành

Mỗi chương đều đi kèm hệ thống bài tập đa dạng:

• Bài tập lý thuyết: Câu hỏi tự luận kiểm tra khả năng phân biệt cơ chế hoạt động (so sánh Stack và Queue, phân tích ưu nhược điểm của mảng so với danh sách liên kết, tính chất cây nhị phân, phân loại đồ thị).
• Bài tập thuật toán: Viết thuật toán kiểm tra số nguyên tố, tìm số hạng thứ $n$ của dãy Fibonacci, xác định thứ tự thăm nút trong các phép duyệt cây (tiền thứ, trung thứ, hậu thứ) và duyệt đồ thị (DFS, BFS).
• Bài tập lập trình thực hành: Cài đặt các ứng dụng cụ thể như đổi số nguyên sang hệ nhị phân bằng Stack; xây dựng chương trình quản lý danh sách liên kết đơn/kép chứa cấu trúc dữ liệu sinh viên; thực hiện các thao tác chèn nút, xóa nút, tìm kiếm theo tên/mã, sắp xếp tăng/giảm theo điểm trung bình và giải phóng toàn bộ bộ nhớ.

Phương pháp đánh giá và hướng dẫn tự học

• Đánh giá học tập: Kết quả môn học được đánh giá qua 28 giờ thực hành/thảo luận trên lớp và 02 giờ làm bài kiểm tra chính thức nhằm đo lường khả năng tư duy thuật toán độc lập và kỹ năng viết code chuẩn xác.
• Hướng dẫn tự học: Người học cần thực hiện đầy đủ tiến trình: đọc hiểu các đặc trưng thuật toán -> tự vẽ sơ đồ khối của bài toán -> viết mã chương trình trên môi trường C/C++ -> đối chiếu kết quả thực thi với các ca kiểm thử mẫu được cung cấp trong giáo trình.

---

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

• Tính pháp lý và chuẩn hóa đào tạo: Giáo trình được biên soạn dựa trên đề cương môn học chính thức và ban hành theo Quyết định số 374ĐT/QĐ-CĐXD1 ngày 16/08/2022 của Hiệu trưởng Trường Cao đẳng Xây dựng số 1, đáp ứng chuẩn đầu ra của chương trình đào tạo nghề trong giai đoạn mới.
• Chuẩn hóa ngôn ngữ cài đặt C/C++: Giáo trình chuyển hóa toàn bộ các thuật toán kinh điển sang mã nguồn C/C++ tường minh, sử dụng đầy đủ các cú pháp quản lý bộ nhớ hiện đại (new, delete), con trỏ cấu trúc (node *next, node *pre), và các thao tác xuất nhập luồng (cin, cout).
• Tích hợp đa dạng phương thức biểu diễn giải thuật: Mọi giải thuật chính đều được trình bày song song qua ba lớp biểu diễn: ngôn ngữ tự nhiên, sơ đồ khối với các hình khối quy chuẩn (khối thao tác, khối điều kiện, khối bắt đầu/kết thúc), và mã nguồn thực thi, giúp người học nắm bắt thuật toán ở nhiều mức độ trừu tượng khác nhau.
• Gắn kết trực tiếp với các bài toán thực tiễn: Hệ thống ví dụ và bài tập được liên hệ trực tiếp với các ứng dụng thực tế trong công nghệ thông tin: cấu trúc Stack trong đảo chuỗi/chuyển đổi cơ số, cấu trúc Queue trong điều phối hàng đợi in ấn và máy bay cất cánh, danh sách liên kết trong quản lý danh bạ và hồ sơ nhân sự, mô hình đồ thị trong bài toán mạng lưới giao thông và chuyển đổi trạng thái máy móc.

---

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

• Sinh viên đào tạo chính quy: Sinh viên hệ Cao đẳng liên thông ngành Công nghệ thông tin (chuyên ngành Ứng dụng phần mềm) tại Trường Cao đẳng Xây dựng số 1 và sinh viên các trường Cao đẳng, Đại học kỹ thuật có cùng khung chương trình cơ sở ngành.
• Điều kiện tiên quyết (Prerequisites): Người học cần hoàn thành môn học Tin học cơ sở hoặc Nhập môn lập trình, nắm vững các cấu trúc điều khiển cơ bản (rẽ nhánh if-else, vòng lặp for, while), khái niệm mảng, hàm, và kiến thức toán logic cơ bản.
• Giảng viên chuyên ngành: Sử dụng giáo trình làm tài liệu giảng dạy chuẩn, phân bổ kế hoạch bài giảng theo khung 45 giờ (15 lý thuyết, 28 thực hành, 02 kiểm tra), xây dựng đề cương bài tập lớn và thiết kế ngân hàng đề thi học phần.
• Người tự học và tham khảo: Kỹ thuật viên, lập trình viên chuyển ngành cần củng cố kiến thức nền tảng về tổ chức bộ nhớ, quản lý con trỏ và thuật toán xử lý dữ liệu phục vụ phát triển phần mềm ứng dụng.

---

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?

Giáo trình được biên soạn chuyên biệt cho sinh viên hệ Cao đẳng liên thông ngành Công nghệ thông tin (Ứng dụng phần mềm), đồng thời phù hợp cho sinh viên các khối ngành kỹ thuật phần mềm cần tài liệu cô đọng, thiên về thực hành cấu trúc dữ liệu và giải thuật.

2. Cần chuẩn bị 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ề lập trình cấu trúc bằng ngôn ngữ C hoặc C++, bao gồm: cú pháp khai báo biến, các kiểu dữ liệu cơ sở, cấu trúc điều kiện, vòng lặp, mảng một chiều và kỹ năng viết hàm.

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

Tài liệu chú trọng tính thực hành với tỷ lệ giờ bài tập và thực hành chiếm hơn 62% thời lượng môn học (28/45 giờ). Toàn bộ các cấu trúc dữ liệu (Stack, Queue, Singly/Doubly Linked List, Cây nhị phân, Đồ thị) đều đi kèm mã nguồn cài đặt chi tiết bằng C/C++, có xử lý đầy đủ việc cấp phát và giải phóng bộ nhớ.

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

Người học nên tuân thủ phương pháp tinh chỉnh từng bước: nắm chắc định nghĩa -> tự vẽ sơ đồ khối thuật toán -> gõ và biên dịch lại mã nguồn C++ trên máy tính -> hoàn thành toàn bộ câu hỏi ôn tập và bài tập lập trình quản lý dữ liệu ở mục Hệ thống kiến thức cuối mỗi chương.

5. Giáo trình có cung cấp tài liệu bổ trợ nào không?

Giáo trình tích hợp sẵn hệ thống câu hỏi lý thuyết, các sơ đồ minh họa từng bước chạy của thuật toán, khung mã nguồn mẫu cho từng thao tác dữ liệu và danh mục bài tập thực hành lập trình ứng dụng ở cuối cả 4 chương.

---

Kết luận

Giáo trình Cấu trúc dữ liệu và giải thuật (Trần Thị Mơ chủ biên, CĐXD1, 2022) cung cấp hệ thống kiến thức chuẩn mực về các kiểu cấu trúc dữ liệu tuyến tính (mảng, ngăn xếp, hàng đợi, danh sách liên kết), cấu trúc phi tuyến (cây nhị phân, đồ thị) cùng các thuật toán sắp xếp và tìm kiếm thông dụng.

Lộ trình học tập đề xuất:

1. Giai đoạn 1 (Chương 1): Nắm vững bản chất giải thuật, đánh giá độ phức tạp và phương pháp thiết kế Top-down / tinh chỉnh từng bước.
2. Giai đoạn 2 (Chương 2): Thành thạo kỹ thuật con trỏ và cài đặt các cấu trúc dữ liệu danh sách tuyến tính trên C++.
3. Giai đoạn 3 (Chương 3): Làm chủ cấu trúc phân cấp cây nhị phân, mô hình đồ thị và các thuật toán duyệt DFS/BFS.
4. Giai đoạn 4 (Chương 4): Phân tích, lựa chọn và cài đặt các giải thuật sắp xếp, tìm kiếm tối ưu cho từng bài toán thực tế.

Tài nguyên bổ sung cho người học bao gồm hệ thống bài tập lập trình C++ cuối mỗi chương và đề cương chi tiết môn học MH09 ban hành kèm Quyết định 374ĐT/QĐ-CĐXD1.

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

Chương 1: Giải thuật Chương 2: Danh sách Chương 3: Mô hình cây và đồ thị Chương 4: Các giải thuật sắp xếp và tìm kiếm Mặc dù có nhiều cố gắng, nhưng trong quá trình biên soạn, biên tập và in ấn khó tránh khỏi những thiếu sót. Chúng tôi rất mong nhận được sự đóng góp ý kiến từ phía các thầy cô và bạn đọc để hoàn thiện giáo trình hơn! Xin trân trọng cảm ơn! Hà Nội, ngày……tháng……năm……… Tham gia biên so¿n Trần Thá M¢ - Chủ biên 3 MþC LþC CH¯¡NG 1: GIÀI THUÀT. Cấu trúc dÿ liệu. Các đặc tr°ng của giÁi thuÁt.

Dÿ liệu vào. Dÿ liệu ra. Ngôn ngÿ diễn đ¿t. Ngôn ngÿ thông th°ờng.

Ngôn ngÿ lÁp trình. Ph°¢ng pháp thiÁt kÁ giÁi thuÁt. Phân rã bài toán thành các bài toán nhỏ h¢n. Ph°¢ng pháp tinh chßnh từng b°ớc.

12 CH¯¡NG 2: DANH SÁCH. Danh sách tuyÁn tính. Khái niệm chung. Kiểu hàng đợi.

Danh sách liên kÁt. Danh sách liên kÁt đ¢n (singly linked list). Danh sách liên kÁt vòng (circular linked list). 29 CH¯¡NG 3: MÔ HÌNH CÂY VÀ Đà THà.

Mô hình cây. Cây nhá phân. Biểu diễn đá thá. Phép duyệt đá thá.

39 CH¯¡NG 4: CÁC GIÀI THUÀT SÂP XÀP VÀ TÌM KIÀM. SÃp xÁp kiểu đổi chß trāc tiÁp. SÃp xÁp kiểu vun đßng. Các giÁi thuÁt tìm kiÁm.

Bài toán tìm kiÁm. Tìm kiÁm nhá phân. Cây nhá phân tìm kiÁm. 64 5 Tên môn hác: CÄU TRÚC Dþ LIàU VÀ GIÀI THU¾T Mã môn hác: MH09 Thßi gian thāc hián môn hác: 45 giờ; (Lý thuyÁt: 15 giờ; Thāc hành, thí nghiệm, thÁo luÁn, bài tÁp: 28 giờ; Kiểm tra: 02 giờ) I.

Vß trí, tính chÃt cÿa môn hác: - Vá trí: Môn học Cấu trúc dÿ liệu và giÁi thuÁt là môn học bÃt buác thuác nhóm các môn học c¢ sở trong ch°¢ng trình đào t¿o nghề Công nghệ thông tin. - Tính chất: Môn học có tính ứng dụng cao trong các lĩnh vāc tin học, góp phần nâng cao chất l°ợng đào t¿o nghề và phát triển nguán nhân lāc trong giai đo¿n mới. Mÿc tiêu môn hác: - Về kiÁn thức: Các khái niệm c¢ bÁn về giÁi thuÁt, đánh giá đá phức t¿p của giÁi thuÁt. Các kiểu cấu trúc dÿ liệu thông dụng và mát sß giÁi thuÁt trên các kiểu cấu trúc dÿ liệu đó.

- Về kỹ năng: ThiÁt kÁ đ°ợc mát sß giÁi thuÁt sÃp xÁp, tìm kiÁm. VÁn dụng các kiểu cấu trúc dÿ liệu thông dụng và các giÁi thuÁt để giÁi mát sß bài toán thāc tiễn. - Về năng lāc tā chủ và trách nhiệm: Tích cāc nghiên cứu nhÿng kiÁn thức về cấu trúc dÿ liệu, giÁi thuÁt. Rèn luyện ý thức chấp hành kỷ luÁt lao đáng, phát huy tinh thần chủ đáng nghiên cứu, học hỏi, sáng t¿o trong học tÁp và làm việc.

6 CH¯¡NG 1: GIÀI THU¾T Mÿc tiêu bài hác 1. Cung cấp cho ng°ời học các kiÁn thức c¢ bÁn về c¢ bÁn về giÁi thuÁt: các đặc tr°ng giÁi thuÁt, ngôn ngÿ diễn đ¿t giÁi thuÁt, ph°¢ng pháp thiÁt kÁ giÁi thuÁt, đánh giá đá phức t¿p của giÁi thuÁt trong mát sß bài toán cụ thể. 7 CH¯¡NG 1: GIÀI THU¾T 1. Gi¿i thu¿t Khái niệm giÁi thuÁt hay thuÁt giÁi mà nhiều khi còn đ°ợc gọi là thuÁt toán dùng để chß ph°¢ng pháp hay cách thức (method) để giÁi quyÁt vần đề.

GiÁi thuÁt có thể đ°ợc minh họa b¿ng ngôn ngÿ tā nhiên (natural language), b¿ng s¢ đá (flow chart) hoặc b¿ng mã giÁ (pseudo code). Trong thāc tÁ, giÁi thuÁt th°ờng đ°ợc minh họa hay thể hiện b¿ng mã giÁ tāa trên mát hay mát sß ngôn ngÿ lÁp trình nào đó (th°ờng là ngôn ngÿ mà ng°ời lÁp trình chọn để cài đặt thuÁt toán), chÁng h¿n nh° C, Pascal, ? Khi đã xác đánh đ°ợc cấu trúc dÿ liệu thích hợp, ng°ời lÁp trình s¿ bÃt đầu tiÁn hành xây dāng thuÁt giÁi t°¢ng ứng theo yêu cầu của bài toán đặt ra trên c¢ sở của cấu trúc dÿ liệu đã đ°ợc chọn. Để giÁi quyÁt mát vấn đề có thể có nhiều ph°¢ng pháp, do vÁy sā lāa chọn ph°¢ng pháp phù hợp là mát việc mà ng°ời lÁp trình phÁi cân nhÃc và tính toán. Sā lāa chọn này cũng có thể góp phần đáng kể trong việc giÁm bớt công việc của ng°ời lÁp trình trong phần cài đặt thuÁt toán trên mát ngôn ngÿ cụ thể.

CÁu trúc dÿ liáu Mßi quan hệ giÿa cấu trúc dÿ liệu và GiÁi thuÁt có thể minh họa b¿ng đÁng thức: Cấu trúc dÿ liệu + GiÁi thuÁt = Ch°¢ng trình. Nh° vÁy, khi đã có cấu trúc dÿ liệu tßt, nÃm vÿng giÁi thuÁt thāc hiện thì việc thể hiện ch°¢ng trình b¿ng mát ngôn ngÿ cụ thể chß là vấn đề thời gian. Khi có cấu trúc dÿ liệu mà ch°a tìm ra thuÁt giÁi thì không thể có ch°¢ng trình và ng°ợc l¿i không thể có ThuÁt giÁi khi ch°a có cấu trúc dÿ liệu. Mát ch°¢ng trình máy tính chß có thể đ°ợc hoàn thiện khi có đầy đủ cÁ Cấu trúc dÿ liệu để l°u trÿ dÿ liệu và GiÁi thuÁt xử lý dÿ liệu theo yêu cầu của bài toán đặt ra.

Để đánh giá mát cấu trúc dÿ liệu chúng ta th°ờng dāa vào mát sß tiêu chí sau: - Cấu trúc dÿ liệu phÁi tiÁt kiệm tài nguyên (bá nhớ trong) - Cấu trúc dÿ liệu phÁi phÁn Ánh đúng thāc tÁ của bài toán - Cấu trúc dÿ liệu phÁi dễ dàng trong việc thao tác dÿ liệu. Các đặc tr°ng cÿa giÁi thu¿t - Tính xác định: Mßi b°ớc của thuÁt giÁi cần phÁi đ°ợc mô tÁ mát cách chính xác, chß có mát cách hiểu duy nhất. Bởi vì, nÁu mát b°ớc có thể hiểu theo nhiều cách khác nhau, thì cùng mát dÿ liệu vào, nhÿng ng°ời thāc hiện thuÁt giÁi khác nhau có thể cho ra kÁt quÁ khác nhau. NÁu ta mô tÁ thuÁt giÁi b¿ng ngôn ngÿ tā nhiên, không có gì đÁm bÁo ng°ời đọc hiểu đúng ý của ng°ời viÁt thuÁt giÁi, bởi ngôn ngÿ tā nhiên th°ờng là đa nghĩa.

Để đÁm bÁo đòi hỏi này, thuÁt giÁi cần đ°ợc mô tÁ trong mát ngôn ngÿ lÁp trình, chÁng h¿n mát ngôn ngÿ lÁp trình (Pascal, C. trong các ngôn ngÿ này, các mệnh đề đ°ợc t¿o thành theo các qui tÃc cú pháp nghiêm nghặt và chß có mát ý nghĩa duy nhất. 8 - Tính khả thi: Tất cÁ các phép giÁi có mặt trong các b°ớc của thuÁt giÁi phÁi đủ đ¢n giÁn. Điều đó có nghĩa là các phép giÁi phÁi sao cho, ít nhất về nguyên tÃc có thể thāc hiện đ°ợc bởi con ng°ời trong mát khoÁng thời gian hÿu h¿n.

ChÁng h¿n trong thuÁt giÁi Euclid, ta chß cần thāc hiện các phép chia các sß nguyên, các phép gán và các phép so sánh. - Tính dừng: Với mọi bá dÿ liệu vào thoÁ mãn điều kiện qui đánh, thuÁt giÁi phÁi dừng l¿i sau mát sß hÿu h¿n b°ớc thāc hiện. ChÁng h¿n đßi với thuÁt giÁi Euclid là thuÁt giÁi thoÁ mãn điều kiện này. Bởi vì sß d° r luôn nhỏ h¢n n, nÁu r0 thì giá trá của n ở b°ớc sau là giá trá của r ở b°ớc tr°ớc, ta có n>r=n1>r1=n2>r2.Dãy sß nguyên d°¢ng giÁm dần cần phÁi kÁt thúc ở 0, do đó sau mát sß b°ớc giá trá của r=0 thuÁt giÁi dừng.

Dÿ liáu vào - Input: Mßi thuÁt giÁi cần có mát sß (có thể b¿ng không) dÿ liệu vào. Đó là giá trá cần đ°a vào khi thuÁt giÁi bÃt đầu làm việc. Dÿ liáu ra - Output: Mßi thuÁt giÁi cần có mát hoặc nhiều dÿ liệu ra. Đó là các giá trá có quan hệ xác đánh với giá trá vào và là kÁt quÁ của sā thāc hiện thuÁt giÁi.

Ngôn ngÿ dißn đ¿t 1. Ngôn ngÿ thông thường Trong cách biểu diễn thuÁt giÁi theo ngôn ngÿ tā nhiên, ng°ời ta sử dụng ngôn ngÿ th°ờng ngày để liệt kê các b°ớc của thuÁt giÁi (Các ví dụ về thuÁt giÁi trong mục 1 của ch°¢ng sử dụng ngôn ngÿ tā nhiên). Ph°¢ng pháp biểu diễn này không yêu cầu ng°ời viÁt thuÁt giÁi cũng nh° ng°ời đọc thuÁt giÁi phÁi nÃm các quy tÃc. Tuy vÁy, cách biểu diễn này th°ờng dài dòng, không thể hiện rõ cấu trúc của thuÁt giÁi, đôi lúc gây hiểu lầm hoặc khó hiểu cho ng°ời đọc.

Gần nh° không có mát quy tÃc cß đánh nào trong việc thể hiện thuÁt giÁi b¿ng ngôn ngÿ tā nhiên 1. Lưu đồ L°u đá hay s¢ đá khßi là mát công cụ trāc quan để diễn đ¿t các thuÁt giÁi. Biểu diễn thuÁt giÁi b¿ng l°u đá s¿ giúp ng°ời đọc theo dõi đ°ợc sā phân cấp các tr°ờng hợp và quá trình xử lý của thuÁt giÁi. Ph°¢ng pháp l°u đá th°ờng đ°ợc dùng trong nhÿng thuÁt giÁi có tính rÃc rßi, khó theo dõi đ°ợc quá trình xử lý.

Các nút biểu diễn giải thuật bằng sơ đồ khối: Nút thao tác Nút điều khiển: trong đó ghi điều kiện cần kiểm tra trong quá trình tính toán. 9 Nút khởi đầu, kÁt thúc Cung V¿ l°u đá hoặc s¢ đá khßi, mßi khßi mô tÁ mát b°ớc. Sử dụng mũi tên nßi khßi này với khßi kia để chß trình tā thāc hiện các b°ớc. Để dễ dàng nhÁn biÁt chức năng của từng khßi, mßi khßi đ°ợc thể hiện ở mát d¿ng nh° sau: Ví dụ: Tìm nghiệm thāc của ph°¢ng trình bÁc hai ax2+bx+c=0.

ThuÁt toán gám các b°ớc sau: + NhÁp dÿ liệu a, b, c. + Tính biệt sß  = b2-4ac. + So sánh  với 0. B°ớc tiÁp theo s¿ phụ thuác vào giá trá của .

+ NÁu <0, đáp sß của bài toán là <Vô nghiệm=. + NÁu =0, tính và ghi đáp sß trá của nghiệm kép. + NÁu >0, tính và ghi đáp sß trá của hai nghiệm phân biệt:. L°u đá biểu diễn thuÁt toán này đ°ợc thể hiện nh° sau: 10 1.

Ngôn ngÿ l¿p trình Tuy s¢ đá khßi thể hiện rõ quá trình xử lý và sā phân cấp các tr°ờng hợp của thuÁt toán nh°ng l¿i cáng kềnh. Để mô tÁ mát thuÁt toán nhỏ ta phÁi dùng mát không gian rất lớn. Đôi khi, ta có thể thể hiện thuÁt toán b¿ng ngôn ngÿ lÁp trình nào đó. Mọi ngôn ngÿ lÁp trình đều có nhÿng thao tác c¢ bÁn là xử lý, r¿ nhánh và lặp.

Nh° vÁy, có thể tÁn dụng đ°ợc các khái niệm trong ngôn ngÿ lÁp trình, vừa giúp ng°ời cài đặt dễ dàng hiểu chính xác thuÁt toán. Mát khi đã vay m°ợn cú pháp và khái niệm của ngôn ngÿ lÁp trình thì chÃc chÃn mã giÁ s¿ bá phụ thuác vào ngôn ngÿ lÁp trình đó. Mát đo¿n mã giÁ của thuÁt toán giÁi ph°¢ng trình bÁc hai: if Delta > 0 then begin end else if delta = 0 then xuất kết quả : phương trình có nghiệm kép là -b/(2*a) else {trường hợp delta < 0 } xuất kết quả : phương trình vô nghiệm x1=(-b+sqrt(delta))/(2*a) x2=(-b-sqrt(delta))/(2*a) 11 xuất kết quả : phương trình có hai nghiệm là x1 và x2 1.