7 cấu trúc dữ liệu cơ bản cho các lập trình viên

04-08-2023 14:17

Mục lục

• 1. Khái niệm
• 2.  7 cấu trúc dữ liệu cơ bản cho các lập trình viên

Trong lĩnh vực khoa học máy tính hiện nay, các cấu trúc dữ liệu được ưa chuộng sử dụng trong hầu hết mọi chương trình hay phần mềm đã được phát triển. Ngoài ra chúng cũng là một chủ đề được bàn tán sôi nổi trong các buổi phỏng vấn ở ngành Kỹ thuật phẩn mềm. Trong bài viết này, Hãy cùng Viện Công nghệ Thông tin và Truyền thông ITPlus tìm hiểu về 7 cấu trúc dữ liệu cơ bản cho các lập trình viên nhé!

1. Khái niệm

Về khái niệm, trong lĩnh vực Khoa học máy tính, cấu trúc dữ liệu có hai khái niệm nền tảng là Interface (giao diện) và Implementation (sự triển khai). Chúng được định nghĩa là những cách tổ chức, sắp xếp và lưu trữ dữ liệu trong máy tính nhằm giúp các lập trình viên thực hiện các hoạt động trên dữ liệu được lưu trữ đó một cách dễ dàng hiệu quả hơn. 

2.  7 cấu trúc dữ liệu cơ bản cho các lập trình viên

2.1. Array

Một Array - mảng là một cấu trúc với kích thước cố định có khả năng giữ các item có cùng kiểu dữ liệu. Nó có thể là một mảng các số thực, hay một mảng các số nguyên, một mảng string hay kể cả một mảng của các mảng (mảng 2 chiều). Ngoài ra, mảng được đánh chỉ mục, cho phép ta có thể truy cập ngẫu nhiên vào mảng

2.2. Linked List

Linked list 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. Do đó, ta không thể truy cập ngẫu nhiên mà chỉ có thể truy cập tuần tự vào linked list

Một số lưu ý về linked list:

• Tên của thuộc tính trỏ tới phần tử đầu tiên của linked list là Head

• Phần tử cuối cùng của linked list có tên là tail

• Các phần tử trong linked list được gọi là các node

• Trong trường hợp 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

2.3. Stack

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 sẽ có thể được truy cập đầu tiên) phổ biến và được ưa chuộng trong rất nhiều ngôn ngữ lập trình.

Có hai hoạt động cơ bản có thể được thực hiện trên một stack chính là

Push: Thêm một phần tử vào đỉnh của stack

Pop: Xoá một phần tử khỏi top của stack

2.4. Queue

Queue - hàng đợi là một cấu trúc dạng FIFO (First In First Out - phần tử được đặt ở đầu sẽ có thể được truy cập đầu tiên)

Có hai hoạt động cơ bản sẽ được thực hiện trên một queue:

• Enqueue: Thêm một phần tử vào phí cuối queue

• Dequeue: Xoá một phần tử ở phía đầu Queue

2.5. Tree

Tree - cây là một cấu trúc dữ liệu có phân cấp, khi lưu trữ thì các dữ liệu sẽ được xếp theo thứ bậc cũng như được liên kết chặt chẽ với nhau. Trong cả thập kỷ qua thì có rất nhiều kiểu tree tồn tại và phát triển nhằm đáp ứng yêu cầu các ứng dụng khác nhau, ngoài ra phòng trừ và khắc phục các vấn đề, hạn chế nhất định. Một số ví dụ về Tree như: B-tree, splay tree, Cây tìm kiếm nhị phân,..

2.6. Graph

Một Graph (đồ thị) có thể nói là một tập hợp hữu hạn của các đỉnh (nút) và đường đi giữa các đỉnh này. Hai đỉnh trong đồ thị sẽ được gọi là liền kề nếu chúng được nối với nhau bởi cùng một đường. Kích thước của một đồ thị sẽ được tính bằng số lượng, bậc của đồ thị được tính bằng số lượng đỉnh của nó.

Có hai đồ thị:

• Đồ thị có hướng: từ điểm đầu đến điểm cuối tất cả đường đi của đồ thị đều được đánh dấu

• Đồ thị vô hướng: trên đồ thị này, tất cả đường đi đều không quy định chiều

2.7. Hash Table

Hash table (bảng băm) là một cấu trúc dữ liệu có chức năng là lưu trữ các giá trị, tuy nhiên mỗi giá trị phải có key liên kết. Ngoài ra, hash table còn có khả năng hỗ trợ tìm kiếm nếu ta biết được key của giá trị cần tìm  một cách hiệu quả và nhanh chóng, chính vì vậy mà nó rất hữu dụng trong việc thêm cùng như tìm kiếm dữ liệu.

Ban Truyền thông ITPlus