Giới thiệu Cấu trúc dữ liệu và thuật toán

Thuật toán (Algorithm) là gì?

Theo thuật ngữ lập trình máy tính, thuật toán là một tập hợp các hướng dẫn hay lệnh (statement) được xác định rõ ràng để giải quyết một vấn đề cụ thể. Hay nói cách khác, thuật toán nhận một tập hợp đầu vào (input) và tạo một đầu ra (output) mong muốn. Ví dụ, một thuật toán để cộng hai số sẽ bao gồm các hướng dẫn:

• Nhận hai số đầu vào
• Cộng các số bằng toán tử +
• Hiển thị kết quả (đầu ra)

Một thuật toán tốt sẽ thỏa mãn các yếu tố sau:

• Đầu vào và đầu ra phải được xác định chính xác.
• Mỗi bước trong thuật toán phải rõ ràng và không mơ hồ.
• Thuật toán nên hiệu quả nhất trong số nhiều cách khác nhau để giải quyết một vấn đề.
• Một thuật toán không được bao gồm mã máy tính. Thay vào đó, thuật toán nên được viết theo cách mà nó có thể được sử dụng trong các ngôn ngữ lập trình khác nhau.

Các thuật toán ví dụ

Thuật toán 1: Cộng hai số do người dùng nhập

Bước 1: Bắt đầu
Bước 2: Khai báo các biến num1, num2 và sum
Bước 3: Đọc giá trị num1 và num2
Bước 4: Cộng num1 và num2 và gán kết quả đến sum
 sum ← num1 + num2
Bước 5: Hiển thị sum
Bước 6: Dừng lại

Thuật toán 2: Tìm số lớn nhất trong ba số

Bước 1: Bắt đầu
Bước 2: Khai báo các biến a, b, c
Bước 3: Đọc các biến a, b và c
Bước 4: Nếu a> b
   Nếu a> c
      Hiển thị a là số lớn nhất
   Khác 
      Hiển thị c là số lớn nhất
 Khác
   Nếu b> c
      Hiển thị b là số lớn nhất
   Khác
      Hiển thị c là số lớn nhất
Bước 5: Dừng lại

Cấu trúc dữ liệu (Data structure) là gì?

Trong một bài toán, dữ liệu bao gồm một tập các phần tử cơ sở còn gọi là dữ liệu nguyên tử (atoms). Đó có thể là một số nguyên, một số thực, một kí tự,… Trên cơ sở của các dữ liệu nguyên tử, các cách thức khả dĩ theo đó liên kết chúng lại với nhau, sẽ dẫn đến các cấu trúc dữ liệu (data structures) khác nhau.

Cách biểu diễn một cấu trúc dữ liệu trong bộ nhớ gọi là cấu trúc lưu trữ (storage structure). Có thể có nhiều cấu trúc lưu trữ khác nhau cho một cấu trúc dữ liệu, cũng như có thể có những cấu trúc dữ liệu khác nhau mà được thể hiện trong bộ nhớ bởi cùng một kiểu cấu trúc lưu trữ. Khi đề cập đến cấu trúc lưu trữ, chúng ta cũng cần phân biệt cấu trúc lưu trữ tương ứng bộ nhớ trong – lưu trữ trong, hay ứng với bộ nhớ ngoài – lưu trữ ngoài. Chúng có những đặc điểm riêng kéo theo các cách xử lý cũng khác nhau.

Lưu ý: Các câu từ trên được trích từ cuốn sách kinh điển 
Cấu trúc dữ liệu và giải thuật của tác giả Đỗ Xuân Lôi, 
nhà xuất bản Đại học Quốc gia Hà Nội.

Một cấu trúc dữ liệu được sử dụng để lưu trữ và tổ chức dữ liệu trên máy tính để nó có thể được truy cập và cập nhật một cách hiệu quả.

Tùy thuộc vào yêu cầu và dự án của bạn, điều quan trọng là chọn cấu trúc dữ liệu phù hợp cho dự án của bạn. Ví dụ: nếu bạn muốn lưu trữ dữ liệu tuần tự trong bộ nhớ, thì bạn có thể sử dụng cấu trúc dữ liệu Mảng (Array).

Các loại cấu trúc dữ liệu

Về cơ bản, cấu trúc dữ liệu được chia thành hai loại:

• Cấu trúc dữ liệu tuyến tính (Linear data structure): Trong cấu trúc dữ liệu tuyến tính, các phần tử được sắp xếp tuần tự. Vì các phần tử được sắp xếp theo thứ tự cụ thể nên chúng rất dễ thực hiện. Tuy nhiên, khi độ phức tạp của chương trình tăng lên, cấu trúc dữ liệu tuyến tính có thể không phải là lựa chọn tốt nhất vì sự phức tạp trong hoạt động xử lý. Ví dụ về cấu trúc dữ liệu tuyến tính là Mảng (Array), Ngăn xếp (Stack), Hàng đợi (Queue) và Danh sách liên kết (Linked list). Trong đó cấu trúc Mảng cấu trúc được định nghĩa trước (cấu trúc dữ liệu tiền định – predefined data structure) trong các ngôn ngữ lập trình; các cấu trúc Ngăn xếp, Hàng đợi và Danh sách liên kết sẽ được đề cập chi tiết trong khóa học này.  
• Cấu trúc dữ liệu phi tuyến tính (Non linear data structure): Không giống như cấu trúc dữ liệu tuyến tính, các phần tử trong cấu trúc dữ liệu phi tuyến tính không nằm trong bất kỳ trình tự nào. Thay vào đó, chúng được sắp xếp theo thứ bậc trong đó một phần tử sẽ được kết nối với một hoặc nhiều phần tử. Các ví dụ về cấu trúc này gồm Đồ thị (Graph) và Cây (Tree) sẽ được bàn chi tiết trong khóa học này.

So sánh Cấu trúc dữ liệu tuyến tính  và Cấu trúc dữ liệu phi tuyến tính

Tại sao phải học cấu trúc dữ liệu và thuật toán?

Lập trình là tất cả về cấu trúc dữ liệu và thuật toán. Cấu trúc dữ liệu được sử dụng để lưu giữ dữ liệu trong khi các thuật toán được sử dụng để giải quyết vấn đề bằng cách sử dụng dữ liệu đó.

Cấu trúc dữ liệu và thuật toán đi qua các giải pháp cho các vấn đề tiêu chuẩn một cách chi tiết và cung cấp cho bạn cái nhìn sâu sắc về mức độ hiệu quả của việc sử dụng từng vấn đề trong số chúng. Nó cũng dạy bạn khoa học về đánh giá hiệu quả của một thuật toán. Điều này cho phép bạn chọn tốt nhất trong số các lựa chọn khác nhau.

Phát triển phần mềm liên quan đến việc học các công nghệ mới hàng ngày. Bạn có thể tìm hiểu hầu hết các công nghệ này khi sử dụng chúng trong một trong các dự án của mình. Tuy nhiên, nó không phải là trường hợp với các thuật toán.

Nếu bạn không biết rõ về các thuật toán, bạn sẽ không thể xác định được liệu bạn có thể tối ưu hóa mã bạn đang viết ngay bây giờ hay không. Bạn phải biết trước về chúng và áp dụng chúng ở những nơi có thể và quan trọng.

Bạn có vấn đề gì về bài học này không?