Cấu trúc dữ liệu là gì? Chúng ta hiểu đơn giản 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. Hầu hết mọi phần mềm, chương trình đều sử dụng cấu trúc dữ liêu. Dưới đây mình sẽ giới thiệu 1 số cấu trúc dữ liệu thường gặp khi chúng ta làm việc:
Arrays
ARRAY – mảng là một cấu trúc có kích thước cố định, có thể trữ item có cùng kiểu dữ liệu (một mảng số nguyên, số thực, string hay thậm chí một mảng của các mảng). Mảng được dánh chỉ mục, cho phép truy cập ngẫu nhiên vào mảng.
Phần tử: Mỗi mục được lưu giữ trong một mảng được gọi là một phần tử.
Chỉ mục (Index): Mỗi vị trí của một phần tử trong một mảng có một chỉ mục số được sử dụng để nhận diện phần tử.
Linked Lists
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 item theo thứ tự tuyến tính được liên kết với nhau và khôn thể thực hiện truy cập ngẫu nhiên.
- Các phẩn tử trong linked list được gọi là node
- Mỗi node chứa một key và một con trỏ trỏ tới node kế tiếp của nó, được gọi là next
- Thuộc tính tên là head, trỏ tới phần tử đầu tiên của linked list
- Phần tử cuối của linked list có tên là tail
Stacks
STACK – ngăn xếp là một cấu trúc dạng LIFO (Last In First Out – phẩn tử được đưa vào sau cùng, có thể được truy cập đầu tiên) được thấy thường xuyên trong nhiều ngô ngữ lập trình. Có thể thực hiện 2 hoạt động cơ bản trên một stack:
- Push: thêm một phần tử vào đỉnh của stack
- Pop: Xóa một phần tử khỏi top của stack
- Peek: Trả về phần tử ở đỉnh của stack mà không xoá nó đi ( hàm bổ sung )
- isEmpty: Kiểm tra một stack có rỗng không ( hàm bổ sung )
- isFull: Kiểm tra một stack có đang đầy không ( hàm bổ sung )
Ứng dụng để: Sử dụng cho tính toán giá trị biểu thức, Sử dụng cho cài đặt lời gọi hàm trong lập trình đệ quy.
Queue
QUEUE – hàng đợi là cấu trúc dạng 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 1 queue:
- Enqueue: thêm một phẩn tử vào phía cuối queue
- Dequeue: xóa một phần tử ở phía đầu queue
Tree
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à liên kết với nhau khi lưu trữ. Có nhiều kiểu tree đã được phát triển để phù hợp với các ứng dụng khác nhau hoặc khắc phục những hạn chế nhất định, có thể kể đến như: cây tìm kiếm nhị phân, B-tree, Treap, Red-Black Tree, Splay Tree…
Graph
GRAPH – đồ thị là một tập hợp hữu hạn các đỉnh và đường đi giữa các đỉnh này. Kích thước của một đồ thị được tính bằng số lượng, bậc của đồ thị được tính bằng số đỉnh của nó. 2 đỉnh được gọi là liền kề nếu chúng được nối với nhau bằng cùng 1 đường. Có 2 loại đồ thị:
- Đồ thị có hướng: Tất cả đường đi trên nó đề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.
Hash table
HASH TABLE – bản băm là cấu trúc dữ liệu lưu trữ các giá trị mà mỗi giá trị có một key được liên kết với nó. Hash Table hỗ trợ tìm kiếm hiệu quả nếu ta biết được key của giá trị cần tìm.
Do đó, nó hiệu quả trong việc thêm, tìm kiếm dữ liệu bất kể kích thước dữ liệu như thế nào. Hash Table sử dụng Array – mảng như là một kho lưu giữ trung gian và sử dụng kỹ thuật Hash để tạo key tại nơi giá trị được chèn vào.
Ứng dụng:
- Sử dụng để cài đặt việc đánh index trong database.
- Sử dụng để cài đặt các mảng liên kết.
- Sử dụng để cài đặt kiểu cấu trúc dữ liệu Set.
Hash function (h) là một hàm đặc biệt sử dụng để giải quyết vấn đề của cách tiếp cận đánh địa chỉ trực tiếp. Với cách truy cập trực tiếp, khi đó một giá trị với key k sẽ được lưu trữ trong slot k. Sử dụng hàm băm, ta sẽ tính toán index của slot mà value được lưu trữ. Giá trị được tính toán bằng hàm băm của một key được gọi là hash value, cho biết index của slot mà giá trị được ánh xạ tới.
h(k) = k % m
- h: hàm băm
- k: key của hash value cần xác định
- m: size của hash table
Trên đây là bài viết ngắn gọn mình tổng hợp giới thiệu về các cấu trúc dữ liệu thường gặp trong quá trình làm việc. Hi vọng bài viết sẽ có thể mang lại cho bạn một chút kiến thức bổ ích.
Cảm ơn các bạn đã ghé thăm. Chúc các bạn thành công!
