Đối với anh em lập trình viên, cấu trúc dữ liệu và giải thuật luôn là một kiến thức tuy cơ bản nhưng lại khá khó khăn để học, tìm hiểu và thành thạo. Tuy nhiên hầu như ai cũng hiểu được tầm quan trọng của nó trong việc xây dựng một chương trình, tối ưu hóa source code dự án. Bài viết hôm nay chúng ta cùng nhau tìm hiểu về môn học thú vị này để hiểu được tầm quan trọng của nó với lập trình nhé.
Cấu trúc dữ liệu là gì?
Cấu trúc dữ liệu (Data Structures) là cách thức lưu trữ, tổ chức dữ liệu trong chương trình, hệ thống có mục đích để giúp việc sử dụng, thao tác với dữ liệu đó hiệu quả nhất.
Một cấu trúc dữ liệu được định nghĩa sẽ đi kèm với các thao tác, hoạt động trên loại cấu trúc đó. Thông thường sẽ bao gồm các thao tác:
- Tìm kiếm: tìm và trả về một hoặc nhiều phần tử có giá trị thỏa mãn theo các tiêu chí tìm kiếm
- Sắp xếp: thực hiện sắp xếp các phần tử dựa trên giá trị theo thứ tự tăng/ giảm
- Chèn: thêm một phần tử vào cấu trúc
- Cập nhật: chỉnh sửa giá trị một phần tử trong cấu trúc
- Xóa: loại bỏ phần tử trong cấu trúc
Một số cấu trúc dữ liệu cơ bản
- Arrays – Mảng: cấu trúc với kích thước cố định, được đánh chỉ mục giúp truy cập vào từng phần tử.
- Linked List – Danh sách liên kết: cấu trúc tuần tự chứa chuỗi các items theo một thứ tự tuyến tính được liên kết với nhau.
- Hash Table – Bảng băm: cấu trúc lưu trữ các giá trị được ánh xạ với một key sinh ra nhờ hàm băm.
- Stack – Ngăn xếp: cấu trúc dạng LIFO (Last In First Out – phần tử ở cuối cùng được truy cập đầu tiên)
- Queue – Hàng đợi: cấu trúc dạng FIFO (First In First Out – phần tử ở đầu được truy cập đầu tiên)
- Tree – Cây: cấu trúc dữ liệu phân cấp, tổ chức theo thứ bậc và được liên kết với nhau giống như một cây với các cành và lá.
- Graph – Đồ thị: tập hợp hữu hạn các đỉnh (nút) và cạnh (đường đi giữa các đỉnh).
Giải thuật là gì?
Giải thuật hay thuật toán (Algorithms) là một tập hợp hữu hạn có trình tự các hướng dẫn để thực hiện giải quyết một vấn đề cụ thể.
Một giải thuật cần có đầu vào (input) và đầu ra (output) xác định trước; từng bước thực hiện rõ ràng (clear instructions). Giải thuật không phụ thuộc vào ngôn ngữ lập trình (language independent) mà có thể được triển khai trong nhiều ngôn ngữ lập trình khác nhau. Một giải thuật cần đảm bảo tính khả thi (workable) và phải kết thúc sau một hữu hạn các bước (finiteness).
Một số loại giải thuật phổ biến:
- Search engine algorithm: Giải thuật tìm kiếm
- Encryption algorithm: Giải thuật mã hóa
- Greedy algorithm: Giải thuật tham lam
- Recursive algorithm: Giải thuật đệ quy
- Backtracking algorithm: Giải thuật quay lui
- Divide-and-conquer algorithm: Giải thuật chia để trị
- Dynamic programming algorithm: Giải thuật quy hoạch động
- Brute-force algorithm: Giải thuật vét cạn
- Sorting algorithm: Giải thuật sắp xếp
- Hashing algorithm: Giải thuật băm
- Randomized algorithm: Giải thuật ngẫu nhiên
Một số khái niệm trong giải thuật
Lưu đồ giải thuật
Lưu đồ giải thuật hay sơ đồ khối (Flow Chart) là một công cụ giúp biểu diễn thuật toán bằng hình vẽ. Nó mô tả việc nhập, xuất dữ liệu cùng luồng xử lý thông qua các ký hiệu hình học. Sơ đồ khối giúp chúng ta dễ dàng hình dung các bước của thuật toán được triển khai, tăng tính logic của giải thuật. Với một lập trình viên, việc đọc được lưu đồ giải thuật sẽ giúp bạn triển khai viết code theo ngôn ngữ lập trình của mình một cách dễ dàng hơn.
Mã giả
Mã giả (Pseudocode) là một bản mô tả giải thuật lập trình ngắn gọn sử dụng những quy ước có cấu trúc, thường được bỏ đi những chi tiết không cần thiết (ví dụ như khai báo biến, chương trình con,…) giúp giải thuật dễ hiểu hơn. Mục đích của mã giả cũng là giúp người đọc dễ dàng hơn trong việc hiểu giải thuật, và có thể làm mẫu để triển khai trong các ngôn ngữ lập trình khác nhau.
Độ phức tạp của giải thuật
Độ phức tạp (algorithm complexity) của giải thuật là một ước lượng tương đối về số phép tính mà giải thuật cần thực hiện đối với bộ dữ liệu đầu vào có kích thước n. Nó có ý nghĩa giúp đánh giá hiệu quả của một thuật toán, thường được ký hiệu là O(A), trong đó:
- O(1): thể hiện rằng giải thuật có độ phức tạp hằng số khi thời gian chạy không phụ thuộc kích thước dữ liệu đầu vào
- O(A): thể hiện rằng giải thuật sẽ cần tối đa A câu lệnh O(1) được thực thi để giải quyết bài toán
Một số độ phức tạp giải thuật thường gặp: O(n), O(log n), O(log n2),…
Tầm quan trọng của CTDL>
Cấu trúc dữ liệu và giải thuật luôn có sự song hành với nhau trong việc giải quyết một bài toán. Nhà khoa học máy tính Niklaus Emil Wirth (cha đẻ của ngôn ngữ lập trình Pascal) từng xuất bản cuốn sách với cái tên “Algorithms + Data Structures = Programs” hay có nghĩa là Giải thuật + Cấu trúc dữ liệu = Chương trình; để nói lên tầm quan trọng của CTDL>.
Để viết được một chương trình hay giải một bài toán trong lập trình, chúng ta luôn phải kết hợp 2 yếu tố, đó là lựa chọn một cấu trúc dữ liệu phù hợp cho việc lưu trữ các biến, các giá trị; sau đó tìm ra phương hướng kết hợp mọi thứ với nhau bằng giải thuật. Một cấu trúc dữ liệu tốt sẽ giúp chúng ta quản lý dữ liệu một cách hiệu quả, chính xác hơn; một thuật toán tốt sẽ giúp xử lý dữ liệu nhanh chóng, rõ ràng hơn. Kết hợp 2 điều này sẽ giúp chúng ta tạo ra một chương trình chạy đúng, chạy nhanh và phù hợp với các ràng buộc về phần cứng khác.
Hiện nay, bộ môn CTDL> luôn xuất hiện trong hầu hết các chương trình giảng dạy chuyên ngành lập trình, công nghệ thông tin ở các trường đại học; và ngay từ các lớp trung học chúng ta cũng đã có môn học liên quan. Điều này cũng nói lên việc cần thiết phải nắm vững các cấu trúc dữ liệu cơ bản cùng các giải thuật phổ biến để có thể áp dụng vào source code chương trình mà bạn viết.
Kết bài
Bất cứ chương trình được viết bằng ngôn ngữ lập trình nào đều cần có cấu trúc dữ liệu và áp dụng các giải thuật của riêng nó. Nắm được kiến thức về CTDL> giúp bạn tự tin hơn trong các buổi phỏng vấn, lấy điểm từ nhà tuyển dụng. Hy vọng bài viết hữu ích dành cho bạn và hẹn gặp lại trong các bài viết tiếp theo của mình.
Tác giả: Phạm Minh Khoa
Xem thêm:
- Tìm hiểu cấu trúc dữ liệu ArrayMap trong Android
- Seminar môn Cấu trúc dữ liệu và giải thuật
- 8 cấu trúc dữ liệu siêu cơ bản mà Dev nào cũng nên biết
Xem thêm việc làm IT hấp dẫn trên TopDev
