Chương 1: Tổng quan cấu trúc dữ liệu và giải thuật

06/01/2026 CHƯƠNG 1
TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
1. Dữ liệu, thông tin và chương trình 1.1 Dữ liệu
Dữ liệu là các giá trị thô, chưa được xử lý, dùng
để mô tả sự vật, hiện tượng trong thực tế. Dữ liệu thường:
 Dữ liệu chưa mang nhiều ý nghĩa nếu đứng riêng lẻ.
 Dữ liệu là đầu vào cho chương trình. 1.2 Thông tin
Thông tin là dữ liệu đã được xử lý, tổ chức hoặc
diễn giải, có ý nghĩa đối với người sử dụng. 1.3 Chương trình
Một tập hợp các câu lệnh được viết bằng ngôn
ngữ lập trình, dùng để xử lý dữ liệu nhằm tạo ra thông tin mong muốn. 1 06/01/2026 8.5 8.0 9.0 9.2 8.6 Chương Dữ liệu trình XẾP LOẠI HỌC TẬP Điểm trung bình = 8.66 Thông
Sinh viên đạt loại Giỏi tin
Dữ liệu → Chương trình xử lý → Thông tin
2. Cấu trúc dữ liệu là gì
Là cách tổ chức, lưu trữ và quản lý dữ liệu trong
bộ nhớ máy tính để dữ liệu được sử dụng một cách hiệu quả.
Vai trò của CTDL là giúp chương trình:  Chạy nhanh hơn.  Ít tốn bộ nhớ hơn.
 Dễ cài đặt và bảo trì. 2 06/01/2026
CTDL giúp chương trình chạy nhanh hơn.
Yêu cầu: Tìm một dữ liệu sinh viên có MSSV =
2411067 trong danh sách 10.000 sinh viên tại
trong hệ thống quản lý đào tạo của CTUT.
Cách lưu 1: Lưu sinh viên theo dạng không tổ
chức. Ví dụ: sinh viên vào trước thì lưu trước vào danh sách.
Khi thực hiện: Duyệt từ đầu đến cuối danh sách
và so sánh từng sinh viên.
Nguy cơ: Có thể phải so sánh 10.000 lần và
chương trình chậm khi dữ liệu lớn.
Cách lưu 2: Lưu sinh viên theo dạng có tổ chức
ngay từ đầu. Ví dụ: Danh sách được tổ chức theo MSSV tăng dần.
Khi thực hiện: Không cần kiểm tra toàn bộ và số
bước thực hiện có thể giảm nhiều.
Chạy chậm không phải vì máy yếu mà có thể do
dữ liệu được tổ chức chưa tốt. 3 06/01/2026
CTDL giúp ít tốn bộ nhớ hơn.
Yêu cầu: Lưu thông tin các tuyến đường giữa các
giao lộ trong thành phố Cần Thơ.
Cách lưu 1: Hệ thống dùng ma trận 1000 × 1000 = 1.000.000 ô nhớ.
Vấn đề: Chỉ có vài nghìn tuyến đường thực tế.
Nguy cơ: Rất nhiều ô nhớ không dùng đến và lãng phí bộ nhớ.
Cách lưu 2: Dùng danh sách kề (đồ thị). Ví dụ:
{A, B, C} với các cạnh A-B, A-C, B-C.
Vấn đề: Chỉ lưu những tuyến đường thực sự tồn
tại và không lưu các mối quan hệ không có.
Khi thực hiện: Dùng ít bộ nhớ hơn rất nhiều và
Phù hợp với dữ liệu thưa.
CTDL phù hợp → tiết kiệm bộ nhớ 4 06/01/2026
CTDL giúp dễ cài đặt và bảo trì chương trình.
Yêu cầu: Quản lý danh sách công việc: Thêm việc
mới, Xóa việc cũ và Hiển thị danh sách.
Cách lưu 1: Dùng mảng thuần.
Vấn đề: Phải tự quản lý: Chỉ số, dịch chuyển phần
tử và kích thước mảng.
Nguy cơ: Dễ lỗi, code rối và khó bảo trì.
Cách lưu 2: Dùng danh sách liên kết. Cấu trúc gồm nút và con trỏ.
Vấn đề: Mỗi công việc là một node. Chèn/xóa
không cần dịch chuyển dữ liệu.
Khi thực hiện: Ít sửa code cũ và dễ thêm chức năng mới.
CTDL tốt → chương trình rõ ràng → dễ bảo trì 5 06/01/2026
Ví dụ: Mô phỏng hàng chờ tại quầy giao dịch như sau:
 Người đến trước phục vụ trước  Thêm người vào cuối
 Phục vụ người ở đầu
Hệ thống quản lý sử dụng cấu trúc dữ liệu là mảng thường:
 Hành động: Sau nhiều lần lấy người ở đầu sẽ
làm cho bộ nhớ phía trước bị bỏ trống. Để tối
ưu chúng ta phải dời dữ liệu hoặc reset mảng.
 Kết quả: Lãng phí bộ nhớ, xử lý phức tạp. 6 06/01/2026
Hệ thống quản lý sử dụng cấu trúc dữ liệu là Hàng đợi (Queue):
 Hành động: Tự động tăng giảm kích thước.
Tận dụng lại bộ nhớ trống.
 Kết quả: Tiết kiệm bộ nhớ, chương trình gọn và ổn định.
3. Giải thuật (thuật toán) là gì
Một dãy hữu hạn các bước xử lý rõ ràng, dùng
để giải quyết một bài toán cụ thể.
Theo Knuth, giải thuật có các tính chất:  Hữu hạn  Xác định  Hiệu quả
 Có đầu vào và đầu ra. 7 06/01/2026 Tính chất 1: Hữu hạn Sum(n) s ← 0 for i ← 1 to n do s ← s + i return s
Vòng lặp chạy đúng n lần Kết thúc chắc chắn
=> Đây là giải thuật hữu hạn. i ← 1 while i > 0 do print(i) Điều kiện luôn đúng Không có điểm dừng
Không phải giải thuật vì không hữu hạn. 8 06/01/2026 Tính chất 2: Xác định if a > b then max ← a else max ← b Điều kiện rõ ràng
Mỗi bước đều xác định
=> Đây là giải thuật xác định. ChonSoLonTrongDay(A)
Chọn một số lớn trong dãy A Xử lý cho hợp lý
Không rõ ràng trong mô tả Không thể lập trình
Không phải giải thuật vì không xác định
được mục tiêu của thuật toán. 9 06/01/2026 Tính chất 3: Hiệu quả max ← A[0] for i ← 1 to n-1 do if A[i] > max then max ← A[i]
So sánh, gán → thao tác đơn giản
Máy tính thực hiện được
=> Đây là giải thuật hiệu quả.
Tìm nghiệm chính xác của mọi
phương trình bậc cao trong 1 bước. Không khả thi
Không thể thực hiện bằng thao tác cơ bản
Không hiệu quả, đây không phải giải thuật. 10 06/01/2026
Tính chất 4: Có đầu vào, đầu ra Factorial(n) if n = 0 then return 1 else return n * Factorial(n-1) Input: n Output: giá trị giai thừa
=> Đây là giải thuật hợp lệ. for i ← 1 to n do i ← i + 1 Không tạo ra kết quả
Không trả về giá trị gì
=> Không đầy đủ đầu ra, do đó không đúng nghĩa giải thuật. 11 06/01/2026
Cùng một CTDL, giải thuật khác nhau dẫn đến
tốc độ xử lý khác nhau.
Bài toán: Tìm một số trong mảng số nguyên A[ ] gồm n phần tử. for i ← 0 to n-1 do if A[i] = x then return i
Có thể phải kiểm tra n phần tử Chậm khi n lớn while left ≤ right do mid ← (left + right) / 2 if A[mid] = x then return mid else if A[mid] < x then left ← mid + 1 else right ← mid - 1
Mỗi bước bỏ đi một nửa dữ liệu Rất nhanh 12 06/01/2026
Giải thuật là ý tưởng giải quyết bài toán, không
phụ thuộc ngôn ngữ lập trình. max ← A[0]
Mã giả for i ← 1 to n-1 do if A[i] > max then max ← A[i] C Python max = A[0]; max = A[0] for (i = 1; i < n; i++) for i in range(1, n): if (A[i] > max) if A[i] > max: max = A[i]; max = A[i] 3.1 Ngôn ngữ tự nhiên Ưu điểm  Dễ hiểu  Gần gũi Nhược điểm  Dài dòng  Mơ hồ  Không chặt chẽ 13 06/01/2026
Mô tả theo ngôn ngữ tự nhiên:
Giả sử phần tử đầu tiên trong dãy là số lớn nhất.
Bạn hãy lần lượt so sánh số này với các phần tử
còn lại trong dãy. Nếu gặp số nào lớn hơn thì cập
nhật lại số lớn nhất. Khi so sánh xong toàn bộ
dãy, số được giữ lại là số lớn nhất.
Mô tả theo ngôn ngữ tự nhiên:
Chọn một số lớn trong dãy. Bạn hãy xử lý cho hợp lý.
 Chúng ta nên dùng ngôn ngữ tự nhiên khi mô
tả ý tưởng ban đầu, giải thích cho người không
chuyên và thuyết trình, trao đổi ý tưởng.
 Chúng ta không nên dùng ngôn ngữ tự nhiên
cho việc thiết kế giải thuật chính xác hoặc chuẩn bị lập trình. 14 06/01/2026 3.2 Lưu đồ
Lưu đồ là biểu diễn đồ họa của giải thuật.
Các bước được vẽ bằng các hình chuẩn, nối với nhau bằng mũi tên. Các ký hiệu:
 Hình oval: Bắt đầu / Kết thúc
 Hình chữ nhật: Xử lý  Hình thoi: Điều kiện
 Hình bình hành: Nhập / Xuất dữ liệu Bắt đầu i = 0 Sai i < 100 Khởi động máy Đúng Kết thúc i = i+1 15 06/01/2026 3.3 Mã giả
Mã giả là cách mô tả giải thuật gần với ngôn
ngữ lập trình nhưng không phụ thuộc cú pháp của ngôn ngữ nào.
Đây là cách biểu diễn được sử dụng nhiều nhất trong môn học.
4. Độ phức tạp thuật toán
Độ phức tạp thuật toán: là mức tài nguyên mà
giải thuật cần để thực hiện, thường xét trên 2 tiêu
chí: Thời gian và Bộ nhớ.
Đối với môn học này, chủ yếu chúng ta xét độ phức tạp thời gian.
Độ phức tạp thời gian được đo bằng: Số phép
toán và Số bước thực hiện. Nó phụ thuộc vào kích
thước dữ liệu đầu vào và không đo bằng thời gian
chạy thực tế hoặc tốc độ xử lý của máy tính. 16 06/01/2026
Ký hiệu độ phức tạp thuật toán là Big-O, trong đó:
 Mô tả mức tăng của thời gian chạy
 Khi kích thước dữ liệu tăng lớn
Một số độ phức tạp thường gặp: STT Ký hiệu Ý nghĩa 1 O(1) Hằng số 2 O(n) Tuyến tính 3 O(n²) Bậc hai 4 O(log n) Logarit
Ví dụ 1: Tìm giá trị X trong mảng A gồm n phần
tử. Độ phức tạp của thuật toán sau là gì? O(log n) 17 06/01/2026
Ví dụ 2: Tìm giá trị lớn nhất mảng A gồm n
phần tử. Độ phức tạp của thuật toán sau là gì? O(n)
Ví dụ 3: Đếm số cặp phần tử trong mảng A. Độ
phức tạp của thuật toán sau là gì? O(n2) 18 06/01/2026 Bài tập 1: Bài tập 2: Bài tập 3:
Bài tập 4: Cho n = 1.000.000
Vì sao cần nghiên cứu và học CTDL và GT? Vì:
 Giảm độ phức tạp chương trình.
 Tối ưu bộ nhớ và thời gian.
 Là nền tảng của các môn học và lĩnh vực khác. Data 1 CTDL và GT Chương trình Data 2 Data … 19