Cấu trúc dữ liệu và thuật toán | tổng hợp 7 CTDL phổ biến
Xem lại 3 bài viết về CTDL trên website:
- Cấu trúc dữ liệu và thuật toán | Mảng (Array) và Linked List
- Cấu trúc dữ liệu và thuật toán | Ngăn xếp (Stack)
- Cấu trúc dữ liệu và thuật toán | Hàng đợi (Queue)
Cấu trúc dữ liệu là cách tổ chức và lưu trữ dữ liệu trong máy tính để chúng ta có thể thực hiện các hoạt động dựa trên dữ liệu được lưu trữ một cách hiệu quả hơn. Với sinh viên CNTT hay là các bạn đã ra trường đi làm, các lập trình viên lâu năm thì CTDL là hành trang không thể thiếu, và CTDL cũng là các câu hỏi được các nhà tuyển dụng thường xuyên sử dụng để hỏi các ứng viên. Trên website cũng đã có một bài viết tổng hợp các câu hỏi phỏng vấn về CTDL các bạn có thể xem lại TẠI ĐÂY.
7 CTDL phổ biến được đề cập tới trong bài viết bao gồm:
- Mảng (Array)
- Danh sách liên kết ( Linked list)
- Ngăn xếp ( Stack)
- Hàng đợi ( Queue)
- Cây ( Tree)
- Đồ thị ( Graph)
- Bảng băm ( Hash table)
1. Mảng ( Array)
Một mảng ( Array) là một cấu trúc dữ liệu với kích thước cố định, lưu trữ các phần tử cùng kiểu dữ liệu. Nó có thể là một mảng số nguyên, mảng số thực, mảng chuỗi hay một mảng của mảng. Mảng được đánh chỉ mục, được lưu ở các ô nhớ liên tiếp nhau cho phép ta có thể truy cập ngẫu nhiên vào mảng một cách dễ dàng, nhanh chóng.
2. Danh sách liên kết ( Linked List)
Danh sách liên kết là một cấu trúc tuần tự bao gồm một chuỗi các phần tử theo thứ tự tuyến tính được liên kết với nhau. Việc truy cập vào các phần tử trong danh sách liên kết phải là tuần tự, không thể thực hiện truy cập ngẫu nhiên.
- Các phần tử trong danh sách liên kết được gọi là các node
- Mỗi node chứa giá trị và một con trỏ trỏ tới node kế tiếp
- Có một con trỏ head trỏ tới phần tử đầu tiên của danh sách liên kết
3. Ngăn xếp ( Stack)
Là một CTDL hoạt động theo nguyên tắc LIFO ( Last In First Out - phần tử đưa vào sau cùng sẽ được truy cập đầu tiên), CTDL này được thấy thường xuyên trong ngôn ngữ lập trình và ứng dụng của nó đem lại cũng là rất lớn.
Có 2 hoạt động cơ bản được thực hiện trên 1 ngăn xếp đó là:
- Push: Thêm một phần tử vào đỉnh của ngăn xếp
- Pop: Xóa một phần tử khỏi đỉnh của ngăn xếp
Tùy vào nhu cầu mỗi bài toán chúng ta có thể thêm các hàm phù hợp để thuận tiện hơn khi sử dụng ngăn xếp, ví dụ như xem phần tử ở đỉnh mà không xóa, kiểm tra ngăn xếp rỗng,...
4. Hàng đợi ( Queue)
Là một CTDL hoạt động theo nguyên tắc FIFO ( First In First Out - phần tử được đặt ở đầu sẽ được truy cập đầu tiên), có 2 hoạt động cơ bản được thực hiện trên một hàng đợi đó là:
- enqueue: thêm một phần tử vào phía cuối hàng đợi
- dequeue: xóa một phần tử ở phía đầu hàng đợi
Tùy vào nhu cầu mỗi bài toán chúng ta có thể thêm các hàm phù hợp để thuận tiện hơn khi sử dụng hàng đợi tương tự như ngăn xếp. Ngoài ra còn có rất nhiều biến thể của hàng đợi để phù hợp hơn với một số bài toán đặc thù như hàng đợi ưu tiên, hàng đợi 2 đầu,...
5. Cây ( Tree)
Cây là một cấu trúc dữ liệu có phân cấp, trong đó dữ liệu được tổ chức theo thứ bậc và được liên kết với nhau khi lưu trữ. Ứng dụng của cây là rất lớn mà bình thường chúng ta sẽ thấy được ở một số khái niệm như cây đơn vị, cây thư mục,...
Có rất nhiều loại cây đã ra đời để giải quyết các bài toán từ dễ tới khó, khắc phục nhược điểm của cây trước như: cây tìm kiếm nhị phân, B-Tree, Splay Tree, Cây đỏ đen,...
6. Đồ thị ( Graph)
Đồ thị là một tập hợp hữu hạn đỉnh ( nút) và đường đi giữa các đỉnh này. Có nhiều khái niệm liên quan tới đồ thị như bậc của đồ thị, kích thước đồ thị,... 2 đỉnh được gọi là liền kề nếu chúng được nối với nhau bởi 1 đường.
Cây cũng là một loại đồ thị và là đồ thị liên thông, không có chu trình. Nhưng vì cây đặc biệt và ứng dụng lớn vì thế chúng thường được nhắc riêng khi nói về chủ đề đồ thị.
Có 2 loại đồ thị:
- Đồ thị có hướng: tất cả đường đi đều được đánh dấu chiều giữa điểm đầu và điểm cuối
- Đồ thị vô hướng: tất cả đường đi trên nó đều không quy định chiều
7. Bảng băm ( Hash table)
Bảng băm cũng là một loại CTDL khá phổ biến và đặc biệt, nó lưu trữ các giá trị mà mỗi giá trị có một khóa ( key) được liên kết với nó. Bảng băm hỗ trợ tìm kiếm hiệu quả nếu ta biết được khóa của giá trị cần tìm.
