C++ 数据结构学习笔记

常用数据结构

数组(Array)

数组是一种线性数据结构，它由同一数据类型的元素组成，这些元素通过一个相同的变量名访问。在C++中，数组的声明方式如下：

cppCopy Code
数据类型 数组名[数组长度];

例如，以下代码声明了一个整型数组：

cppCopy Code
int arr[5];

链表(Linked List)

链表是一种线性数据结构，其中每个节点包含数据和指向下一个节点的指针。链表分为单向链表和双向链表两种形式。在C++中，实现链表通常需要自定义节点类，下面是单向链表的实现示例：

cppCopy Code
class Node {
public:
    int data;
    Node *next;
    Node(int d) {data = d; next = NULL;}
};

栈(Stack)

栈是一种后进先出(LIFO)的数据结构，它只允许在顶部插入和删除元素。在C++中，使用STL容器stack可以轻松实现栈：

cppCopy Code
#include <stack>

using namespace std;

stack<int> s;
s.push(1); // 元素1入栈
int top = s.top(); // 获取栈顶元素
s.pop(); // 删除栈顶元素

队列(Queue)

队列是一种先进先出(FIFO)的数据结构，它只允许在队尾插入元素，在队头删除元素。在C++中，使用STL容器queue可以轻松实现队列：

cppCopy Code
#include <queue>

using namespace std;

queue<int> q;
q.push(1); // 元素1入队
int front = q.front(); // 获取队头元素
q.pop(); // 删除队头元素

哈希表(Hash Table)

哈希表是一种通过将键映射到确定位置来快速查找值的数据结构。哈希表的实现需要考虑哈希函数的设计和冲突解决策略。C++中STL容器unordered_map可以轻松实现哈希表：

cppCopy Code
#include <unordered_map>

using namespace std;

unordered_map<string, int> mp;
mp["one"] = 1; // 插入键值对
int val = mp["one"]; // 获取值

实例

以下是一个使用链表实现栈的实例：

cppCopy Code
class Node {
public:
    int data;
    Node *next;
    Node(int d) {data = d; next = NULL;}
};

class Stack {
private:
    Node *top;
public:
    Stack() {top = NULL;}
    void push(int val) {
        Node *new_node = new Node(val);
        if(top == NULL) {
            top = new_node;
        }
        else {
            new_node->next = top;
            top = new_node;
        }
    }
    int pop() {
        if(top == NULL) {
            cout << "Stack is empty" << endl;
            return -1;
        }
        else {
            int val = top->data;
            top = top->next;
            return val;
        }
    }
};

int main() {
    Stack s;
    s.push(1);
    s.push(2);
    s.push(3);
    cout << s.pop() << endl; // 输出3
    cout << s.pop() << endl; // 输出2
    cout << s.pop() << endl; // 输出1
    cout << s.pop() << endl; // 输出"Stack is empty"并返回-1
    return 0;
}