Giáo trình Kinh tế: cấu trúc dữ liệu và giải thuật ngành quản trị mạng

Tài liệu chuyên sâu về cấu trúc dữ liệu và giải thuật dành cho sinh viên ngành quản trị mạng với lý thuyết và bài tập thực hành đầy đủ.

• Tác giả: Tổ Bộ Môn Tin Học
• Trường học: Trường Cao đẳng Công nghiệp Hải Phòng
• Chuyên ngành: Cấu trúc dữ liệu và Giải thuật
• Đề tài: Cấu trúc dữ liệu và Giải thuật
• Loại tài liệu: Giáo trình
• Địa điểm: Hải Phòng

Mục lục chi tiết

• LỜI GIỚI THIỆU
• 1. CHƯƠNG 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
• 1.1. Khái niệm cấu trúc dữ liệu và giải thuật, cấu trúc lưu trữ và cấu trúc dữ liệu
• 1.1.1. Khái niệm cấu trúc dữ liệu và giải thuật
• 1.1.2. Cấu trúc dữ liệu và cấu trúc lưu trữ
• 1.1.3. Cấu trúc dữ liệu
• 1.1.4. Các kiểu dữ liệu cơ bản
• 1.1.5. Các kiểu dữ liệu cấu trúc
• 1.1.6. Các kiểu dữ liệu trừu tượng
• 1.1.7. Các tiêu chuẩn đánh giá cấu trúc dữ liệu
• 1.1.8. Các thao tác cơ bản trên một cấu trúc dữ liệu
• 1.2. Giải thuật và đánh giá độ phức tạp của giải thuật
• 1.2.1. Biểu diễn giải thuật
• 1.2.1.1. Bằng ngôn ngữ tự nhiên
• 1.2.1.2. Bằng lưu đồ giải thuật
• 1.2.1.3. Bằng ngôn ngữ diễn đạt giải thuật (mã giả)
• 1.2.2. Một số đặc trưng của giải thuật
• 1.2.3. Đánh giá độ phức tạp của giải thuật
• 1.2.3.1. Độ phức tạp tính toán của giải thuật
• 1.2.3.2. Xác định độ phức tạp tính toán của giải thuật
• 2. CHƯƠNG 2: ĐỆ QUI VÀ GIẢI THUẬT ĐỆ QUI
• 2.1. Khái niệm đệ qui
• 2.2. Giải thuật đệ qui và chương trình đệ qui
• 2.2.1. Giải thuật đệ qui
• 2.2.2. Chương trình con đệ qui
• 2.2.3. Đặc điểm của một chương trình con đệ qui
• 2.3. Thiết kế giải thuật đệ qui
• 2.3.1. Giải thuật đệ qui đơn giản
• 2.3.2. Nguyên tắc thiết kế một giải thuật đệ qui
• 2.3.3. Nguyên tắc thực hiện một hàm đệ qui trong máy tính
• 2.4. Nhận xét giải thuật đệ qui
• 3. CHƯƠNG 3: DANH SÁCH VÀ CÁC PHÉP TOÁN CƠ BẢN TRÊN DANH SÁCH
• 3.1. Khái niệm danh sách tuyến tính
• 3.2. Cài đặt danh sách theo cấu trúc mảng
• 3.3. Danh sách liên kết
• 3.3.1. Sử dụng con trỏ hoặc mối nối để tổ chức danh sách tuyến tính , mà ta gọi là danh sách móc nối (danh sách liên kết), chính là một giải pháp nhằm khắc phục các nhược điểm của cách cài đặt danh sách bằng mảng
• 3.3.2. Cài đặt theo cấu trúc danh sách liên kết đơn
• 3.3.3. Cài đặt theo cấu trúc danh sách liên kết kép
• 3.3.4. Cài đặt theo cấu trúc danh sách liên kết nối vòng
• 3.4. Cài đặt danh sách theo các cấu trúc đặc biệt (ngăn xếp, hàng đợi)
• 3.4.1. Các thao tác cơ bản của Stack
• 3.4.2. Cài đặt Stack bằng mảng
• 3.4.3. Cài đặt Stack bằng danh sách liên kết đơn
• 3.4.4. Ứng dụng của Stack
• 3.4.5. Các thao tác cơ bản của Queue
• 3.4.6. Cài đặt Queue bằng mảng
• 3.4.7. Cài đặt Queue bằng danh sách liên kết đơn
• 3.4.8. Ứng dụng của Queue
• 4. CHƯƠNG 4: CÁC PHƯƠNG PHÁP SẮP XẾP CƠ BẢN
• 4.1. Định nghĩa bài toán sắp xếp
• 4.2. Phương pháp sắp xếp chèn (Insertion sort)
• 4.2.1. Ý tưởng giải thuật Insertion sort
• 4.2.2. Mô tả giải thuật
• 4.2.3. Cài đặt giải thuật
• 4.2.4. Biểu diễn giải thuật
• 4.3. Phương pháp sắp xếp chọn (Selection sort)
• 4.3.1. Ý tưởng giải thuật Selection sort
• 4.3.2. Mô tả giải thuật
• 4.3.3. Cài đặt giải thuật
• 4.3.4. Biểu diễn giải thuật
• 4.4. Phương pháp sắp xếp đổi chỗ (Interchange sort)
• 4.4.1. Ý tưởng của giải thuật Interchange sort
• 4.4.2. Mô tả giải thuật
• 4.4.3. Cài đặt giải thuật
• 4.4.4. Biểu diễn giải thuật
• 4.5. Phương pháp sắp xếp nổi bọt (Bubble sort)
• 4.5.1. Ý tưởng giải thuật Bubble sort
• 4.5.2. Mô tả giải thuật
• 4.5.3. Cài đặt giải thuật
• 4.5.4. Biểu diễn giải thuật
• 4.6. Phương pháp sắp xếp nhanh (Quick sort)
• 4.6.1. Ý tưởng giải thuật Quick sort
• 4.6.2. Mô tả giải thuật
• 4.6.3. Cài đặt giải thuật
• 4.6.4. Biểu diễn giải thuật
• 4.7. Bài toán tìm kiếm
• 4.7.1. Tìm kiếm tuyến tính
• 4.7.1.1. Ý tưởng giải thuật
• 4.7.1.2. Mô tả giải thuật
• 4.7.1.3. Cài đặt giải thuật
• 4.7.1.4. Biểu diễn giải thuật
• 4.7.2. Tìm kiếm nhị phân
• 4.7.2.1. Ý tưởng giải thuật
• 4.7.2.2. Mô tả giải thuật
• 4.7.2.3. Cài đặt giải thuật
• 4.7.2.4. Biểu diễn giải thuật
• 4.8. Khái niệm về cây
• 4.8.1. Khái niệm cây
• 4.8.2. Một số khái niệm của cây
• 4.9. Cây nhị phân
• 4.9.1. Khái niệm cây nhị phân
• 4.9.2. Một số tính chất của cây nhị phân
• 4.9.3. Biểu diễn cây nhị phân
• 4.9.3.1. Lưu trữ cây bằng véc tơ kế tiếp (lưu trữ kế tiếp)
• 4.9.3.2. Lưu trữ cây bằng danh sách liên kết
• 4.9.4. Các phép duyệt cây nhị phân
• 4.9.4.1. Duyệt cây theo thứ tự trước (Preorder traversal)
• 4.9.4.2. Duyệt cây theo thứ tự giữa (Inorder traversal)
• 4.9.4.3. Duyệt cây theo thứ tự sau (Postorder traversal)
• 4.10. Khái niệm về đồ thị
• 4.11. Biểu diễn đồ thị
• 4.11.1. Biểu diễn bằng ma trận kề
• 4.11.2. Biểu diễn đồ thị bằng danh sách kề
• 4.12. Các phép duyệt đồ thị
• 4.12.1. Duyệt theo chiều sâu (Depth First Search)
• 4.12.2. Duyệt theo chiều rộng (Bredth First Search)
• 5. CHƯƠNG 5: BIẾN CON TRỎ VÀ CẤP PHÁT ĐỘNG
• 5.1. Khái niệm biến tĩnh, biến động và biến con trỏ
• 5.2. Khai báo biến con trỏ
• 5.3. Các phép toán trên biến con trỏ
• 5.3.1. Toán tử địa chỉ &
• 5.3.2. Toán tử tham chiếu *
• 5.3.3. Phép chuyển (ép) kiểu
• 5.3.4. Toán tử cộng, trừ con trỏ với một số nguyên và phép tăng giảm
• 5.3.5. Toán tử so sánh
• 5.3.6. Hằng con trỏ
• 5.3.7. Cấp phát vùng nhớ cho biến con trỏ
• 5.4. Mối liên quan giữa con trỏ, hàm, mảng, chuỗi và cấu trúc
• 5.4.1. Biến con trỏ là tham số hình thức của hàm
• 5.4.2. Biến con trỏ là kiểu kết quả hàm trả về
• 5.4.3. Sự tương quan giữa con trỏ và mảng
• 5.4.4. Con trỏ và chuỗi ký tự
• 5.4.5. Con trỏ và kiểu cấu trúc
• 6. CHƯƠNG 6: CÁC CHƯƠNG TRÌNH CÀI ĐẶT MINH HỌA
• 6.1. Chương trình quản lý điểm sinh viên được cài đặt bằng danh sách liên kết đơn
• 6.2. Chương trình chuyển đổi một số hệ 10 sang hệ 2. Sử dụng các thao tác của Stack cài đặt bằng danh sách liên kết đơn để viết chương trình
• 6.3. Chương trình cài đặt các giải thuật sắp xếp và tìm kiếm với danh sách sinh viên được cài đặt bằng mảng
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Khái niệm cơ bản về Cấu trúc dữ liệu và Giải thuật

Cấu trúc dữ liệu và giải thuật là những kiến thức nền tảng trong lĩnh vực công nghệ thông tin và lập trình máy tính. Cấu trúc dữ liệu đề cập đến cách tổ chức, lưu trữ và quản lý dữ liệu trong bộ nhớ máy tính, trong khi giải thuật là tập hợp các bước hoặc quy trình để giải quyết một bài toán cụ thể. Giáo trình này được biên soạn dựa trên chương trình đào tạo Cao đẳng và Trung cấp nghề Quản trị mạng máy tính, gồm 7 chương với nội dung từ cơ bản đến nâng cao. Học viên sẽ nắm vững các kiểu dữ liệu cơ bản, kiểu dữ liệu cấu trúc, và kiểu dữ liệu trừu tượng. Giáo trình cố gắng kết nối các kiến thức giữa các chương và môn học trước đó, giúp sinh viên phát triển kỹ năng lập trình và khả năng chọn cấu trúc dữ liệu phù hợp để xây dựng giải thuật hiệu quả.

1.1. Cấu trúc lưu trữ và Cấu trúc dữ liệu

Cấu trúc lưu trữ là cách bố trí dữ liệu trong bộ nhớ vật lý máy tính, được xác định bởi ngôn ngữ lập trình. Ngược lại, cấu trúc dữ liệu là mô hình logic để tổ chức dữ liệu, độc lập với cách lưu trữ cụ thể. Sự khác biệt giữa hai khái niệm này rất quan trọng để lập trình viên hiểu cách dữ liệu được quản lý ở cả mức độ logic và vật lý.

1.2. Các tiêu chuẩn đánh giá Cấu trúc dữ liệu

Khi chọn cấu trúc dữ liệu, cần xem xét các tiêu chuẩn như hiệu suất truy cập, tốc độ chèn/xóa, không gian bộ nhớ, và độ phức tạp của các phép toán. Mỗi cấu trúc dữ liệu có ưu điểm riêng, ví dụ mảng nhanh chóng truy cập nhưng chèn/xóa chậm, trong khi danh sách liên kết linh hoạt hơn nhưng tốc độ truy cập thấp hơn.

II. Giải thuật và Đánh giá Độ phức tạp

Giải thuật là một chuỗi các bước logic để giải quyết một bài toán cụ thể. Trong lĩnh vực lập trình, việc hiểu và thiết kế giải thuật tối ưu là kỹ năng thiết yếu. Giáo trình cung cấp ba cách biểu diễn giải thuật: sử dụng ngôn ngữ tự nhiên, lưu đồ giải thuật, và ngôn ngữ diễn đạt giải thuật (mã giả). Một giải thuật tốt phải có những đặc trưng như tính xác định, có đầu vào và đầu ra rõ ràng, hữu hạn các bước, và có thể thực hiện được. Độ phức tạp tính toán của giải thuật được đánh giá qua ký hiệu O lớn, giúp lập trình viên so sánh hiệu suất của các giải thuật khác nhau trước khi áp dụng vào thực tế.

2.1. Biểu diễn Giải thuật

Có ba phương pháp chính để biểu diễn giải thuật: thứ nhất là sử dụng ngôn ngữ tự nhiên với lời tả chính xác; thứ hai là dùng lưu đồ giải thuật với các ký hiệu hình học; thứ ba là ngôn ngữ mã giả gần với mã lập trình nhưng dễ hiểu hơn. Mỗi cách biểu diễn có ưu điểm riêng, giúp người học và người phát triển phần mềm dễ dàng giao tiếp và hiểu rõ ý tưởng.

2.2. Xác định Độ phức tạp Tính toán

Độ phức tạp tính toán được xác định bằng cách phân tích số lần thực hiện các phép toán cơ bản trong giải thuật. Ký hiệu O lớn (Big O) được sử dụng để mô tả tốc độ tăng của thời gian thực hiện khi kích thước dữ liệu tăng. Các mức độ phức tạp thường gặp là O(1), O(n), O(n²), O(log n), và O(n log n).

III. Cấu trúc dữ liệu Cơ bản Danh sách Stack và Queue

Danh sách tuyến tính là một trong những cấu trúc dữ liệu cơ bản nhất, được cài đặt bằng hai phương pháp chính: mảng và danh sách liên kết. Cài đặt bằng mảng có ưu điểm truy cập nhanh nhưng hạn chế về kích thước, trong khi danh sách liên kết linh hoạt hơn. Giáo trình cũng giới thiệu hai cấu trúc dữ liệu đặc biệt là Stack (ngăn xếp) và Queue (hàng đợi). Stack hoạt động theo nguyên tắc LIFO (Last In First Out), thích hợp cho các ứng dụng như kiểm tra dấu ngoặc, đảo ngược chuỗi. Queue hoạt động theo nguyên tắc FIFO (First In First Out), được sử dụng trong quản lý tài nguyên, lập lịch công việc. Mỗi cấu trúc có các phép toán cơ bản như thêm, xóa, và truy cập phần tử.

3.1. Danh sách Liên kết và ứng dụng

Danh sách liên kết sử dụng con trỏ hoặc mối nối để kết nối các phần tử, khắc phục nhược điểm của cấu trúc mảng. Có ba loại chính: danh sách liên kết đơn, danh sách liên kết kép, và danh sách liên kết nối vòng. Mỗi loại phù hợp với các tình huống sử dụng khác nhau, từ duyệt tuyến tính đến duyệt hai chiều.

3.2. Stack và Queue trong Lập trình

Stack và Queue là hai cấu trúc dữ liệu quan trọng được cài đặt từ danh sách liên kết hoặc mảng. Stack dùng cho các bài toán liên quan đến kiểm tra cấu trúc, đảo ngược, tính toán biểu thức. Queue được áp dụng trong bài toán BFS, quản lý bộ đệm, và lập lịch công việc trong hệ điều hành.

IV. Các Phương pháp Sắp xếp và Tìm kiếm

Sắp xếp và tìm kiếm là những bài toán cơ bản và quan trọng trong khoa học máy tính. Giáo trình giới thiệu năm phương pháp sắp xếp phổ biến: Insertion Sort (sắp xếp chèn) có độ phức tạp O(n²), thích hợp với dữ liệu nhỏ; Selection Sort (sắp xếp chọn) cũng O(n²); Bubble Sort (sắp xếp nổi bọt) dễ hiểu nhưng chậm; Interchange Sort (sắp xếp đổi chỗ) là cải tiến của Bubble Sort; và Quick Sort (sắp xếp nhanh) với trung bình O(n log n), hiệu quả hơn với dữ liệu lớn. Đối với tìm kiếm, giáo trình cung cấp hai phương pháp: tìm kiếm tuyến tính O(n) áp dụng cho dữ liệu chưa sắp xếp, và tìm kiếm nhị phân O(log n) cho dữ liệu đã sắp xếp. Việc chọn giải thuật phù hợp phụ thuộc vào kích thước dữ liệu, tính chất dữ liệu, và yêu cầu hiệu suất.

4.1. So sánh các Phương pháp Sắp xếp

Mỗi phương pháp sắp xếp có ưu và nhược điểm khác nhau. Insertion Sort tốt cho dữ liệu nhỏ; Bubble Sort dễ cài đặt nhưng kém hiệu quả; Quick Sort là lựa chọn tốt cho dữ liệu lớn với độ phức tạp trung bình O(n log n). Việc hiểu độ phức tạp của từng phương pháp giúp lập trình viên chọn giải pháp tối ưu.

4.2. Chiến lược Tìm kiếm Hiệu quả

Tìm kiếm tuyến tính là phương pháp cơ bản, kiểm tra tuần tự từng phần tử. Tìm kiếm nhị phân yêu cầu dữ liệu được sắp xếp nhưng nhanh hơn nhiều lần. Lựa chọn giải thuật tìm kiếm phù hợp tùy thuộc vào trạng thái dữ liệu và tần suất tìm kiếm.

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: MH 12) là tài liệu học tập lưu hành nội bộ do Tổ Bộ môn Tin học thuộc Trường Cao đẳng Công nghiệp Hải Phòng biên soạn, với sự tham gia đóng góp ý kiến từ Khoa Công nghệ thông tin - Trường Cao đẳng nghề Công nghệ Việt - Hàn Bắc Giang. Trong chương trình đào tạo trình độ Cao đẳng và Trung cấp nghề Quản trị mạng máy tính, môn học được xếp vào khối kiến thức kỹ thuật cơ sở, được giảng dạy cho sinh viên năm thứ hai sau khi đã hoàn thành các học phần Tin học và Lập trình căn bản. Tổng thời lượng thực hiện môn học là 77 giờ, bao gồm 22 giờ lý thuyết, 49 giờ thực hành/thảo luận/bài tập và 6 giờ kiểm tra đánh giá.

Mục tiêu học tập của giáo trình tập trung vào ba phương diện:

• Kiến thức: Trang bị bản chất mối quan hệ giữa cấu trúc dữ liệu và giải thuật trong quy trình xây dựng phần mềm, dựa trên nguyên lý kinh điển "Algorithms + Data Structures = Programs" của nhà khoa học máy tính Niklaus Wirth (1975). Giúp người học trình bày được cấu trúc, cách khai báo và các thao tác cơ bản trên các cấu trúc dữ liệu (mảng, danh sách liên kết, ngăn xếp, hàng đợi, cây, đồ thị).
• Kỹ năng: Xây dựng cấu trúc dữ liệu thích hợp cho các bài toán ứng dụng cụ thể (tạo lập, hiển thị, tính toán, sắp xếp, tìm kiếm); cài đặt hoàn chỉnh các giải thuật bằng ngôn ngữ lập trình C hoặc Pascal.
• Năng lực tự chủ và trách nhiệm: Rèn luyện ý thức học tập, tính cẩn trọng trong lập trình và năng lực chủ động nghiên cứu tài liệu kỹ thuật.

Cấu trúc giáo trình gồm 7 chương lý thuyết - thực hành, đi kèm chuyên đề bổ trợ về biến con trỏ, cấp phát động và hệ thống chương trình ứng dụng hoàn chỉnh. Phương pháp tiếp cận đi từ khái niệm lý thuyết, phân tích thuật toán, minh họa qua mã giả và lưu đồ, đến việc cài đặt trực tiếp bằng mã nguồn ngôn ngữ C.

---

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 7 chương trọng tâm theo tiến trình logic từ cơ bản đến nâng cao:

[Chương 1: Phân tích và thiết kế giải thuật]
                       ↓
[Chương 2: Đệ quy và giải thuật đệ quy]
                       ↓
[Chương 3: Mảng, danh sách & Kiểu dữ liệu trừu tượng (Stack, Queue)]
                       ↓
[Chương 4: Cấu trúc dữ liệu kiểu cây (Tree & Binary Tree)]
                       ↓
[Chương 5: Cấu trúc dữ liệu đồ thị (Graph - DFS, BFS)]
                       ↓
[Chương 6: Các phương pháp sắp xếp (Sorting)]
                       ↓
[Chương 7: Các phương pháp tìm kiếm (Searching & BST)]

• Chương 1: Phân tích và thiết kế giải thuật: Trình bày định nghĩa cấu trúc dữ liệu, giải thuật, cấu trúc lưu trữ (bộ nhớ trong và bộ nhớ ngoài); phân loại kiểu dữ liệu cơ bản, kiểu dữ liệu cấu trúc (array, record, file) và kiểu dữ liệu trừu tượng. Giới thiệu các đặc trưng của giải thuật (tính đơn nghĩa, tính dừng, tính đúng đắn, tính phổ dụng, tính hiệu quả), cách biểu diễn giải thuật (ngôn ngữ tự nhiên, lưu đồ khối, mã giả) và phương pháp xác định độ phức tạp tính toán thông qua ký hiệu $O(g(n))$ cùng các quy tắc tính toán (quy tắc tổng, quy tắc nhân, phép toán tích cực).
• Chương 2: Đệ quy và giải thuật đệ quy: Định nghĩa tính đệ quy, phân tích cấu trúc của chương trình con đệ quy gồm lời gọi chính nó, việc thu nhỏ kích thước bài toán và điều kiện dừng (trường hợp suy biến). Trình bày cơ chế lưu vết trong máy tính (tham số, biến cục bộ, địa chỉ quay lui), phân tích ưu - nhược điểm của đệ quy, kỹ thuật khử đệ quy bằng phương pháp lặp. Minh họa qua các bài toán: tính giai thừa $n!$, thuật toán Euclid tìm ước số chung lớn nhất, dãy số Fibonacci, đảo ngược số nguyên và bài toán Tháp Hà Nội.
• Chương 3: Mảng, danh sách và các kiểu dữ liệu trừu tượng: Trình bày danh sách tuyến tính; cài đặt danh sách bằng mảng tĩnh (lưu trữ kế tiếp) với các thao tác khởi tạo, kiểm tra rỗng/đầy, tìm kiếm, chèn, xóa, sắp xếp. Phân tích cấu trúc danh sách liên kết (móc nối) nhằm khắc phục nhược điểm của mảng, bao gồm danh sách liên kết đơn, danh sách liên kết kép, danh sách nối vòng. Trình bày cấu trúc và thao tác của hai dạng danh sách đặc biệt: Ngăn xếp (Stack - LIFO) và Hàng đợi (Queue - FIFO) cài đặt bằng mảng và bằng danh sách liên kết đơn.
• Chương 4: Cấu trúc dữ liệu kiểu cây: Khái niệm cây tổng quát và cây nhị phân, các tính chất của cây nhị phân; biểu diễn cây bằng mảng kế tiếp và bằng danh sách liên kết; các phép duyệt cây nhị phân: duyệt theo thứ tự trước (Preorder Traversal), duyệt theo thứ tự giữa (Inorder Traversal) và duyệt theo thứ tự sau (Postorder Traversal).
• Chương 5: Đồ thị: Định nghĩa đồ thị vô hướng, đồ thị có trọng số; phương pháp biểu diễn đồ thị bằng ma trận kề và danh sách kề; các giải thuật duyệt đồ thị: duyệt theo chiều sâu (Depth First Search - DFS) và duyệt theo chiều rộng (Breadth First Search - BFS).
• Chương 6: Sắp xếp: Định nghĩa bài toán sắp xếp nội; nguyên lý hoạt động, mô tả thuật toán và cài đặt mã nguồn C cho các giải thuật sắp xếp cơ bản: Sắp xếp chèn (Insertion sort), Sắp xếp chọn (Selection sort), Sắp xếp đổi chỗ (Interchange sort), Sắp xếp nổi bọt (Bubble sort) và giải thuật Sắp xếp nhanh (Quick sort).
• Chương 7: Tìm kiếm: Bài toán tìm kiếm dữ liệu; phân tích cơ chế, mô tả và cài đặt giải thuật Tìm kiếm tuyến tính (Linear search), Tìm kiếm nhị phân (Binary search) và cấu trúc Cây nhị phân tìm kiếm (Binary Search Tree - BST).

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

• Lý thuyết nền tảng (Fundamental theories): Lý thuyết về độ phức tạp thuật toán và đánh giá hiệu năng hệ thống qua thời gian thực hiện $T(n)$ trong các trường hợp tốt nhất, xấu nhất và trung bình; lý thuyết về đệ quy và nguyên lý ngăn xếp hệ thống khi thực thi hàm.
• Nguyên lý cốt lõi (Core principles): Tiêu chuẩn đánh giá một cấu trúc dữ liệu (phản ánh đúng thực tế, phù hợp với các thao tác, tiết kiệm tài nguyên CPU và bộ nhớ); nguyên lý con trỏ, tham chiếu (&), giải tham chiếu (*), cấp phát và giải phóng bộ nhớ động trong C.
• Mô hình cấu trúc dữ liệu chuẩn (Essential frameworks): Toàn bộ các cấu trúc dữ liệu tuyến tính (List, Stack, Queue) và phi tuyến (Tree, Graph), cùng các mô hình trừu tượng hóa kiểu dữ liệu thông qua cấu trúc bản ghi (struct) và cấu trúc tự trỏ (self-referential structure).

Kỹ năng phát triển

• Kỹ năng kỹ thuật (Technical skills): Kỹ năng vẽ lưu đồ giải thuật; viết mã giả; khai báo cấu trúc dữ liệu phức hợp; thao tác trực tiếp với con trỏ; cài đặt thuật toán bằng ngôn ngữ C chuẩn.
• Kỹ năng phân tích (Analytical skills): Phân tích và lựa chọn cấu trúc dữ liệu tối ưu cho từng bài toán; xác định độ phức tạp tính toán $O(1), O(n), O(n^2), O(n\log_2 n)$; so sánh hiệu năng giữa giải thuật đệ quy và giải thuật lặp.
• Năng lực ứng dụng thực tiễn (Practical competencies): Xây dựng các chương trình xử lý dữ liệu hoàn chỉnh, bao gồm quản lý hồ sơ sinh viên, chuyển đổi hệ đếm (cơ số 10 sang cơ số 2) bằng Stack, và triển khai các thuật toán sắp xếp/tìm kiếm trên tập dữ liệu thực tế.

---

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

Giáo trình được thiết kế theo định hướng tích hợp lý thuyết với thực hành, trong đó thời lượng thực hành, thảo luận và bài tập chiếm 63,6% tổng quỹ thời gian môn học (49/77 giờ).

Phân bổ thời lượng	Số giờ	Tỷ lệ (%)
Lý thuyết	22	28,6%
Thực hành / Bài tập / Thảo luận	49	63,6%
Kiểm tra	6	7,8%
Tổng cộng	77	100%

• Tiếp cận sư phạm (Pedagogical approach): Mỗi chủ đề được trình bày tuần tự qua 4 bước: (1) Nêu định nghĩa và ý nghĩa thực tế; (2) Mô tả giải thuật qua ngôn ngữ tự nhiên và lưu đồ khối; (3) Cung cấp mã giả/mã nguồn cài đặt bằng C; (4) Phân tích đánh giá độ phức tạp và nêu ví dụ áp dụng.
• Bài tập và Case studies: Hệ thống bài tập cuối chương được chia theo các cấp độ dễ, vừa và ứng dụng tổng hợp:
  • Bài tập phân tích: Đánh giá độ phức tạp các đoạn mã lặp lồng nhau, chuyển đổi hàm đệ quy sang hàm lặp (như bài toán Fibonacci, đảo chuỗi).
  • Case study quản lý thực tế: Xây dựng ứng dụng quản lý hồ sơ nhân viên/sinh viên sử dụng struct gồm các trường mã, họ tên, ngày sinh (Date), điểm thành phần (LaptrinhCB, KientrucMT, MangMT) và tính điểm trung bình (DiemTB).
• Hình thức kiểm tra, đánh giá (Assessment methods): Khung đánh giá được phân định cụ thể trong tiến trình 77 giờ:
  • Bài kiểm tra số 1 (1 giờ): Đánh giá kiến thức Chương 1, 2 và Chương 3 (Mảng, danh sách tuyến tính, Stack, Queue).
  • Bài kiểm tra số 2 (1 giờ): Đánh giá kiến thức Chương 4 (Cấu trúc cây và duyệt cây nhị phân).
  • Bài kiểm tra số 3 (2 giờ): Đánh giá kỹ năng cài đặt các thuật toán sắp xếp thuộc Chương 6.
  • Kiểm tra hết môn (2 giờ): Đánh giá tổng hợp toàn bộ kiến thức và kỹ năng thực hành môn học.
• Hướng dẫn tự học (Self-study guidelines): Giáo trình phân chia rõ ràng các nội dung giảng viên giảng dạy trực tiếp trên lớp và các phần sinh viên tự đọc (như chi tiết cài đặt danh sách liên kết kép, danh sách nối vòng, một số biến thể duyệt cây). Cuối mỗi chương đều có hệ thống câu hỏi lý thuyết để người học tự củng cố kiến thức.

---

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

• Tính liên kết trong chương trình đào tạo: Giáo trình liên kết trực tiếp các kiến thức lập trình cơ sở với các bài toán chuyên ngành Quản trị mạng máy tính (như cấu trúc hàng đợi xử lý gói tin, biểu diễn cấu trúc liên kết mạng qua đồ thị, quản lý bảng chuyển tiếp).
• Cung cấp mã nguồn cài đặt chi tiết: Khác với các tài liệu thuần túy lý thuyết toán học, giáo trình cung cấp đầy đủ các đoạn mã cài đặt bằng ngôn ngữ C có chú thích chi tiết, minh họa rõ ràng cơ chế quản lý bộ đệm bàn phím (fflush(stdin)), nhập xuất chuỗi ký tự (gets(), strcpy()), thao tác trỏ bản ghi và phân bổ bộ nhớ.
• Biểu diễn giải thuật đa dạng: Thuật toán được diễn giải đồng thời bằng ba công cụ: văn bản tự nhiên, lưu đồ khối trực quan (sử dụng các khối chức năng xử lý, vào/ra dữ liệu, rẽ nhánh điều kiện) và mã giả tựa C/Pascal, giúp người học dễ dàng chuyển đổi giải thuật sang bất kỳ ngôn ngữ lập trình nào.
• Tích hợp các chương trình ứng dụng mẫu hoàn chỉnh: Giáo trình dành riêng các mục thực hành chuyên sâu (trang 156-176) cung cấp mã nguồn hoàn chỉnh có cấu trúc menu tương tác cho 3 bài toán:
  1. Chương trình quản lý điểm sinh viên cài đặt bằng danh sách liên kết đơn (bao gồm đầy đủ các hàm: khởi tạo, chèn, xóa, tìm kiếm theo tên, sắp xếp theo họ tên và sắp xếp theo điểm trung bình).
  2. Chương trình chuyển đổi số nguyên hệ thập phân (hệ 10) sang hệ nhị phân (hệ 2) sử dụng ngăn xếp (Stack) cài đặt bằng danh sách liên kết đơn.
  3. Chương trình cài đặt các giải thuật sắp xếp và tìm kiếm trên danh sách sinh viên lưu trữ bằng mảng.

---

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

• Sinh viên: Giáo trình phục vụ trực tiếp cho sinh viên năm thứ hai thuộc hệ Cao đẳng và Trung cấp nghề Quản trị mạng máy tính tại Trường Cao đẳng Công nghiệp Hải Phòng, cũng như sinh viên các ngành Công nghệ thông tin, Kỹ thuật phần mềm tại các trường cao đẳng kỹ thuật.
• Điều kiện tiên quyết (Prerequisites): Người học cần hoàn thành các học phần Tin học đại cương và Lập trình căn bản (nắm vững cú pháp cơ bản của ngôn ngữ C hoặc Pascal, các kiểu dữ liệu nguyên thủy, câu lệnh điều kiện if-else, vòng lặp for, while, mảng một chiều và kỹ thuật viết hàm).
• Giảng viên: Tài liệu cung cấp đề cương chi tiết 77 giờ, phân chia tỷ lệ lý thuyết, thực hành và các mốc kiểm tra định kỳ, làm căn cứ chuẩn để xây dựng giáo án, bài giảng và đề thi đánh giá năng lực người học.
• Tự học và tham khảo: Phù hợp làm tài liệu tra cứu cho kỹ thuật viên, lập trình viên muốn củng cố nền tảng về tổ chức dữ liệu, thao tác con trỏ và thuật toán xử lý dữ liệu cơ bản.

---

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

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

Giáo trình được biên soạn phục vụ sinh viên năm thứ hai trình độ Cao đẳng và Trung cấp nghề Quản trị mạng máy tính, đồng thời phù hợp cho người học khối ngành kỹ thuật công nghệ thông tin cần tài liệu học tập thực hành về cấu trúc dữ liệu và giải thuật.

2. Cần kiến thức nền nào trước khi học giáo trình này?

Người học cần có kiến thức cơ bản về tin học và đã học qua một ngôn ngữ lập trình (ưu tiên C hoặc Pascal), nắm được các cấu trúc điều khiển cơ bản (rẽ nhánh, vòng lặp), kỹ thuật xây dựng hàm và thao tác với mảng một chiề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 lý thuyết khác là gì?

Giáo trình tập trung vào tính thực hành với tỷ trọng 49/77 giờ dành cho thực hành/thảo luận/bài tập, cung cấp mã nguồn C đầy đủ có menu điều khiển cho các bài toán quản lý cụ thể, và kết hợp minh họa thuật toán qua cả lưu đồ khối lẫn mã giả.

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

Người học nên đọc kỹ phần phân tích nguyên lý và theo dõi vết hoạt động của thuật toán qua lưu đồ khối; sau đó tự viết lại mã nguồn trên máy tính dựa trên mã giả, thực thi và kiểm tra các trường hợp biên; cuối cùng hoàn thành toàn bộ bài tập và câu hỏi ôn tập ở cuối mỗi chương.

5. Giáo trình có cung cấp mã nguồn mẫu và tài liệu tham khảo không?

Có. Giáo trình tích hợp sẵn 3 chương trình nguồn hoàn chỉnh ở các trang 156–176 (chương trình quản lý điểm sinh viên, đổi hệ cơ số bằng Stack, sắp xếp/tìm kiếm bằng mảng) và danh mục tài liệu tham khảo chuyên ngành tại trang 177.

---

Kết luận

Giáo trình Cấu trúc dữ liệu và giải thuật của Trường Cao đẳng Công nghiệp Hải Phòng là tài liệu giảng dạy và học tập mang tính chuẩn hóa, tập trung cung cấp nền tảng vững chắc về cách thức tổ chức dữ liệu và phương pháp thiết kế giải thuật cơ bản trong khoa học máy tính.

Lộ trình học tập được thiết kế xuyên suốt: bắt đầu từ kỹ năng phân tích độ phức tạp thuật toán và kỹ thuật đệ quy, tiến tới làm chủ các cấu trúc dữ liệu tuyến tính (Mảng, Danh sách liên kết, Stack, Queue), cấu trúc phi tuyến (Cây, Đồ thị), và thuần thục các giải thuật sắp xếp, tìm kiếm kinh điển. Tài liệu giúp người học hình thành tư duy lập trình cấu trúc và kỹ năng tối ưu hóa mã nguồn, tạo tiền đề tiếp thu các học phần chuyên sâu trong lĩnh vực mạng máy tính và phát triển phần mềm.

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

CHƯƠNG 1 PHÂN TÍCH VÀ THIẾT KẾ GIẢI THUẬT Muc tiêu: Trình bày được khái niệm vê câu truc dư liêu, giải thuật, mối quan hệ giữa cấu trúc dữ liệu và giải thuật. Đánh giá được độ phức tạp của giải thuật. Trình bày được các kiểu dữ liệu cơ bản, các kiểu dữ liệu cấu trúc và kiểu dữ liệu trừu tượng. Khái niệm cấu trúc dữ liệu và giải thuật, cấu trúc lưu trữ và cấu trúc dữ liệu.

Khái niệm cấu trúc dữ liệu và giải thuật Algorithms + Data Structures = Programs " Giai thuật + Cấu trúc dữ liệu = Chương trình " Đo la nhan đê cuốn sách đươc xuât ban năm 1975, bơi nha khoa hoc may tinh Thuy sy Niklaus Wirth Emil, cuôn sach đa đươc công nhân rông rai va vân con hưu dung đên ngay nay. Năm vưng câu truc dư liêu va giai thuât la cơ sơ giup sinh viên có khả năng đi sâu thêm vào các môn học chuyên ngành. Giải thuật(Algorithms): Đó là một dãy các câu lệnh (statements) chặt chẽ và rõ ràng xác định một trình tự các thao tác trên một số các đối tượng nào đó, sao cho sau một số hữu hạn bước thực hiện ta đạt đươc kết quả mong muốn. Dữ liệu (Data): Là đối tượng của giải thuật để khi tác động bởi các thao tác của giải thuật ta nhận được kết quả mong muốn.

Giải thuật chỉ phản ánh các phép xử lí, còn đối tượng để xử lí trên MTĐT, chính là dữ liệu (data) chúng biểu diễn các thông tin cần thiết cho bài toán: Các dữ kiện đưa vào, các kết quả trung gian va kêt qua đâu ra cua bai toan.1: Chương trinh tìm ươc chung lớn nhất của 2 số nguyên dương a và b. Dư kiên đưa vao (input): a, b nguyên dương Phep xư ly (Process) : Dưa theo thuât toan Euclid, thuât toan nôi tiêng nhât co tư thơi cô đai. Bươc 1: Tim r, la phân dư cua phep chia a cho b. Thi: Gan gia tri cua b cho E (E←b) va dưng lai Nêu ngươc lai (r ≠ 0).

Thi: Gan gia tri b cho a ( a←b). Gan gia tri r cho b (b←r) va quay lai bươc 1. 11 Kêt qua ra (Output): E, Ươc chung lơn nhât cua a va b. Cấu trúc dữ liệu (Data Structures): Cách sắp xếp, tổ chức dữ liệu, tạo quan hệ nội tại giữa các phần tử dữ liệu, tạo thuận lợi cho các phép xử lý và nâng cao hiệu quả của chúng.

Bản thân các phần tử của dữ liệu có mối quan hệ với nhau, ngoài ra nếu lại biết “tổ chức” theo các cấu trúc thích hợp thì việc thực hiện các phép xử lí trên các dữ liệu càng thuận lợi hơn, đạt hiệu quả cao hơn.2: Viêt chương trinh thưc hiên công viêc sau: Nhâp vao tư ban phim n sô nguyên bât ky Tinh tông cac sô vưa nhâp va đưa kêt qua ra man hinh Dư kiên đưa vao (input): so, tong la 2 biên sô nguyên và n là số lượng số nguyên. Phep xư ly (Process) : Thưc hiên n lân công viêc sau: - Nhâp gia tri cho biên so - Công gia tri biên so vao biên tong Kêt qua ra (Output): tong, tông n sô nguyên vưa nhâp Vơi 2 yêu câu (a, b) cua bai toan, ta chi cân môt biên so đê lưu gia tri tưng sô nguyên nhâp vao va công gôp dân gia tri ngay vao môt biên tong.3: Viêt chương trinh thưc hiên công viêc sau: Nhâp vao tư ban phim n sô nguyên bât ky. Tinh tông cac sô vưa nhâp va đưa kêt qua ra man hinh. Săp xêp day sô theo chiều tăng dần va đưa day đa săp xêp ra man hinh.

Dư kiên đưa vao (input): tong la biên sô nguyên. M la môt biên mang kiểu phân tư là kiêu sô nguyên. n là số lượng số nguyên.