[Khái quát] Cấu trúc dữ liệu

TỔNG QUAN CẤU TRÚC DỮ LIỆU

Cấu trúc dữ liệu là một thành phần không thể thiếu trong môn học. Nó áp dụng cho rất nhiều, hầu như là toàn bộ bài toán dù lớn hay nhỏ. Thế cấu trúc dữ liệu là gì?

Trích Wikipedia EN: “Trong ngành khoa học máy tính, cấu trúc dữ liệu là cách tổ chức, quản lý và lưu trữ dữ liệu theo một định dạng nào đó mà ta có thể truy cập và chỉnh sửa một cách hiệu quả. Nói đúng hơn, cấu trúc dữ liệu là một tập các dữ liệu, mối quan hệ giữa chúng, và các hàm hoặc toán tử có thể áp dụng lên chúng.”

Theo Wiki, ta có thể hiểu nôm na rằng đó là một cách tổ chức (bao gồm bố trí, quản lý, lưu trữ,…) để ta có thể dễ dàng thao tác trên dữ liệu (truy cập; chỉnh sửa – thêm, xóa, sắp xếp;…). Dùng một Arrays để lưu trữ danh sách điểm số, tên của các thành viên trong một lớp học, cũng có thể xem như là một cách cấu trúc dữ liệu, vì Arrays này có sự bố trí các dữ liệu cùng loại liền kề nhau, khi duyệt từng ô dữ liệu để thao tác sẽ khá là dễ dàng.

Một cách định nghĩa tương tự của geeksforgeek ngắn gọn: “Cấu trúc dữ liệu là một cách tổ chức dữ liệu trên máy tính cụ thể sao cho chúng có thể được sử dụng một cách hiệu quả”. Khi đã hiểu khái niệm rồi thì định nghĩa tổng quát này sẽ giúp bạn dễ nhớ hơn.

Dưới đây mình sẽ đưa ra một vài cấu trúc dữ liệu tiêu biểu, để cho các bạn hình dung rõ hơn về nó.

Arrays

Hình 1: Lưu trữ chuỗi số dùng cấu trúc dữ liệu Arrays

Ở hình 1, chúng ta dùng Arrays để lưu trữ chuỗi số 1, 6, 5, 8, 10. Chú ý các địa chỉ cách nhau 1 đơn vị, nghĩa là các số được lưu trữ liền kề nhau. Tập các ô nhớ liền kề nhau tạo thành một vùng nhớ. Một vùng nhớ có các giá trị liên quan với nhau sẽ dễ dàng hơn trong việc xử lí. Giả dụ như khi bạn muốn tìm kiếm số 5 trong chuỗi số 1, 6, 5, 8, 10. Giả sử có rất nhiều chuỗi khác cũng lưu trữ trong bộ nhớ, nhưng ta chỉ muốn tìm số 5 trong chuỗi trên mà thôi. Chính nhờ việc sắp xếp liền kề nhau, máy tính sẽ biết khu vực 201-205 là khu vực của chuỗi 1, 6, 5, 8, 10, và chỉ cần tiếp cận khu vực đó duyệt từng phần tử là được.

LinkedList

Hình 2: Lưu trữ chuỗi số dùng cấu trúc dữ liệu LinkedList

Đây là một dạng lưu trữ liên kết, không phụ thuộc vào vị trí giữa các phần tử. Một phần tử ngoài lưu trữ dữ liệu, còn lưu trữ con trỏ dẫn đến dữ liệu tiếp theo. Hình 2 là một LinkedList lưu trữ một chuỗi số 1, 5, 6, 10, 8. Chắc hẳn bạn đang có một thắc mắc, việc lưu trữ một chuỗi số phức tạp hơn cả Arrays, nhưng tại sao nó vẫn được sử dụng. Chúng ta hãy xét đến nhược điểm của Arrays và ưu điểm của LinkedList để tìm ra lí do.

Arrays có kích thước cố định. Chúng ta sẽ thử cho một ví dụ để hiểu vì sao kích thước của Arrays là cố định.

Chúng ta có một dòng code

int[] Arrays = new int[3];

i[0]=2;

i[1]=4;

i[2]=6;

int x = 18;

Như thế, trong ô nhớ máy tính sẽ biểu thị như sau

Hình 3: Ví dụ về cấu trúc dữ liệu

Vùng nhớ có địa chỉ từ 201-203 là vùng nhớ của Arrays, và ô nhớ 204 là của bộ nhớ x. Giả sử chúng ta tồn tại dòng lệnh add() trong Arrays với chức năng thêm phần tử vào cuối Arrays, ta thêm một dòng lệnh như sau.

arrays.add(8);

Với cương vị là một người tạo ra ngôn ngữ Java, bạn làm thế nào để Arrays nằm trong một vùng nhớ, và x vẫn giữ nguyên vị trí cũ? Nếu bạn đẩy x vào ô nhớ 205 và thay ô nhớ 204 thành số 8, điều này sẽ rất nguy hiểm vì việc thay đổi vị trí ô nhớ có thể dẫn đến nhiều sự sai lệch trong tính toán, ví dụ như ô nhớ 205 đã có giá trị nào đó và bạn đè giá trị 18 lên ô nhớ ấy (tất nhiên bạn có thể xử lí bằng cách nào đó nữa nhưng như thế sẽ tốn rất nhiều thời gian và nó sẽ phức tạp thêm). Hoặc một cách giải quyết như bài toán nối 2 chuỗi mà String trong Java đã làm, đó là dành ra một vùng nhớ mới và lưu trữ các giá trị. Có vẻ vì sự phiền phức đó mà Java đã không làm, mà thay vào đó là sự ra đời của LinkedList. Nếu ta muốn thêm số 8 vào trong chuỗi đã cho, ta chỉ cần lưu số 8 vào một ô nhớ x bất kì, và cho ô nhớ 203 một pointer trỏ đến ô nhớ x đó là xong.

Tóm lại, các thao tác làm thay đổi kích thước trên Arrays là không thể, đó là điểm yếu lớn nhất của Arrays khiến cho LinkedList ra đời. Tuy độ phức tạp sẽ cao hơn một tí nhưng sẽ giải quyết được bài toán kích thước. Phụ thuộc vào ưu nhược điểm của từng loại cấu trúc dựa trên bài toán cụ thể mà ta sẽ chọn loại nào phù hợp.

Graph

Như đã giới thiệu ở bài trước, graph là một đồ thị dùng để mô hình lại dữ liệu có liên kết với nhau, phục vụ cho việc học tập, nghiên cứu. Trong cấu trúc dữ liệu, graph cũng được xem như một loại cấu trúc thể hiện rõ quan hệ giữa các dữ liệu theo dạng non-linear (phi tuyến tính). Quan hệ tuyến tính giữa các dữ liệu được xem là quan hệ theo một đường có thứ tự nhất định. Các cấu trúc dữ liệu Arrays và LinkedList là những dạng tuyến tính, còn ở graph có một sự đa dạng hơn, không chỉ sắp xếp theo một đường thẳng có thứ tự, mà mỗi phần tử còn có thể liên kết tới nhiều phần tử khác, hoặc chính nó. Sự đa dạng của nó giúp giải quyết được nhiều bài toán thực tế, bởi vốn dĩ mối liên kết giữa các đối tượng ngoài thực tế đâu chỉ là một đường thẳng đâu, nhỉ!

Tổng kết lại bài, chúng ta đã tìm hiểu về cấu trúc dữ liệu và các dạng cơ bản của nó. Mình cũng muốn giải thích tổng quan từng bài một trong môn Cấu trúc dữ liệu nhưng có vẻ sẽ khá là dài, nên mình xin kết thúc tại đây. Cảm ơn các bạn đã theo dõi!

Nội dung bài viết thuộc về Lê Công Diễn.

Người viết: Lê Công Diễn

Mang đi nhớ ghi nguồn