Lập trình C/C++

Liệt kê các cấu trúc dữ liệu phổ biến trong C++ (Full)

Posted on by Đỗ Thành
17
Th2
View: 81

Trong C++, có nhiều cấu trúc dữ liệu khác nhau được sử dụng để lưu trữ và tổ chức dữ liệu một cách hiệu quả. Dưới đây là danh sách đầy đủ các cấu trúc dữ liệu phổ biến trong C++:

1. Cấu trúc dữ liệu cơ bản (Primitive Data Structures)

Đây là những kiểu dữ liệu cơ bản được hỗ trợ trực tiếp bởi ngôn ngữ C++:

  • int : Lưu trữ số nguyên.
  • float : Lưu trữ số thực với độ chính xác đơn (single precision).
  • double : Lưu trữ số thực với độ chính xác kép (double precision).
  • char : Lưu trữ ký tự đơn lẻ.
  • bool : Lưu trữ giá trị logic true hoặc false.
  • wchar_t : Ký tự rộng, thường dùng cho Unicode.
  • short : Số nguyên ngắn.
  • long : Số nguyên dài.
  • long long : Số nguyên rất dài.
  • unsigned int , unsigned short , unsigned long , unsigned long long : Các kiểu số nguyên không dấu.

2. Cấu trúc dữ liệu dẫn xuất (Derived Data Structures)

Đây là các cấu trúc dữ liệu được tạo ra từ các kiểu dữ liệu cơ bản bằng cách sử dụng mảng, con trỏ, hoặc các kỹ thuật khác.

a. Mảng (Array)

  • Mảng một chiều : Ví dụ: int arr[5];
  • Mảng đa chiều : Ví dụ: int matrix[3][3];

b. Con trỏ (Pointer)

  • Con trỏ là biến lưu trữ địa chỉ của một biến khác. Ví dụ: int* ptr;

c. Tham chiếu (Reference)

  • Tham chiếu là một bí danh của một biến đã tồn tại. Ví dụ: int& ref = x;

3. Cấu trúc dữ liệu do người dùng định nghĩa (User-defined Data Structures)

a. Cấu trúc (struct)

  • Cấu trúc cho phép bạn nhóm nhiều loại dữ liệu khác nhau thành một đơn vị duy nhất.
struct Student {
    int id;
    string name;
    float gpa;
};

b. Liên hiệp (union)

  • Liên hiệp cho phép lưu trữ nhiều loại dữ liệu khác nhau trong cùng một vùng nhớ, nhưng chỉ một thành viên có thể được sử dụng tại một thời điểm.
union Data {
    int i;
    float f;
    char str[20];
};

c. Lớp (class)

  • Lớp là một kiểu dữ liệu trừu tượng, cho phép bạn định nghĩa các thuộc tính và phương thức.
class Car {
    public:
        string brand;
        void drive() {
            cout << "Driving " << brand << endl;
        }
};

d. Liệt kê (enum)

  • Liệt kê là một tập hợp các hằng số nguyên được đặt tên.
enum Color { RED, GREEN, BLUE };

4. Cấu trúc dữ liệu động (Dynamic Data Structures)

a. Danh sách liên kết (Linked List)

  • Danh sách liên kết là một chuỗi các nút, mỗi nút chứa dữ liệu và một con trỏ đến nút tiếp theo.
struct Node {
    int data;
    Node* next;
};

b. Ngăn xếp (Stack)

  • Ngăn xếp hoạt động theo nguyên tắc LIFO (Last In First Out). Bạn có thể sử dụng STL std::stack hoặc tự triển khai.
#include <stack>
std::stack<int> s;

c. Hàng đợi (Queue)

  • Hàng đợi hoạt động theo nguyên tắc FIFO (First In First Out). Bạn có thể sử dụng STL std::queue hoặc tự triển khai.

d. Hàng đợi ưu tiên (Priority Queue)

  • Hàng đợi ưu tiên là một loại hàng đợi trong đó phần tử có độ ưu tiên cao nhất được xử lý trước.
e. Cây (Tree)
Cây là một cấu trúc dữ liệu phân cấp, thường được sử dụng để biểu diễn các mối quan hệ cha-con.

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
};

f. Đồ thị (Graph)

  • Đồ thị là một tập hợp các đỉnh và cạnh, thường được sử dụng để biểu diễn mạng lưới.
vector<vector<int>> graph;

b. List

  • List là một danh sách liên kết đôi, cho phép chèn và xóa phần tử ở bất kỳ vị trí nào.
#include <deque>
std::deque<int> dq;

d. Set

  • Set là một tập hợp các phần tử duy nhất, được sắp xếp theo thứ tự tăng dần.
#include <set>
std::set<int> s;

e. Multiset

  • Multiset tương tự như set, nhưng cho phép lưu trữ các phần tử trùng lặp.
#include <set>
std::multiset<int> ms;

f. Map

  • Map là một cấu trúc dữ liệu lưu trữ các cặp key-value, trong đó các key là duy nhất.
#include <map>
std::map<string, int> m;

g. Multimap

  • Multimap tương tự như map, nhưng cho phép lưu trữ các key trùng lặp.
#include <map>
std::multimap<string, int> mm;

h. Unordered Set/Map

  • Unordered Set và Unordered Map là các phiên bản không được sắp xếp của Set và Map, sử dụng bảng băm để lưu trữ dữ liệu.
#include <unordered_set>
std::unordered_set<int> us;

#include <unordered_map>
std::unordered_map<string, int> um;

5. Cấu trúc dữ liệu đặc biệt

a. Heap

  • Heap là một cấu trúc dữ liệu cây nhị phân hoàn chỉnh, thường được sử dụng để triển khai hàng đợi ưu tiên.
#include <algorithm>
std::make_heap(v.begin(), v.end());

b. Hash Table

  • Hash table là một cấu trúc dữ liệu sử dụng hàm băm để lưu trữ và truy xuất dữ liệu nhanh chóng.
#include <unordered_map>
std::unordered_map<int, string> hashTable;

c. Trie

  • Trie là một cấu trúc dữ liệu dạng cây, thường được sử dụng để lưu trữ và tìm kiếm chuỗi.
struct TrieNode {
    bool isEndOfWord;
    TrieNode* children[26];
};

Tổng kết

Trong C++, có rất nhiều cấu trúc dữ liệu khác nhau, từ cơ bản đến phức tạp, giúp lập trình viên lựa chọn phù hợp với từng bài toán cụ thể. Việc hiểu rõ và sử dụng đúng cấu trúc dữ liệu sẽ giúp tối ưu hóa hiệu suất và tài nguyên của chương trình.

Đỗ Thành