C语言|数据结构

一、顺序表：详细见内存管理

二、链表

// 单链表节点定义（LeetCode标准）
typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 创建新节点
ListNode* createNode(int val) {
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

// 链表反转（高频中的高频）
ListNode* reverseList(ListNode *head) {
    ListNode *pre = NULL, *cur = head, *next = NULL;
    while (cur != NULL) {
        next = cur->next; // 保存下一个节点
        cur->next = pre;  // 反转指针
        pre = cur;        // 移动pre
        cur = next;       // 移动cur
    }
    return pre; // 新头节点
}

// 链表查找指定值节点
ListNode* findNode(ListNode *head, int val) {
    while (head != NULL) {
        if (head->val == val) return head;
        head = head->next;
    }
    return NULL;
}

三、栈

// 栈结构定义
#define MAX_STACK_SIZE 10000 // 适配LeetCode数据范围
typedef struct {
    int data[MAX_STACK_SIZE];
    int top; // 栈顶指针（初始-1）
} Stack;

// 初始化栈
void stackInit(Stack *stack) {
    stack->top = -1;
}

// 判断栈空
int stackIsEmpty(Stack *stack) {
    return stack->top == -1;
}

// 入栈
int stackPush(Stack *stack, int val) {
    if (stack->top >= MAX_STACK_SIZE - 1) return 0; // 栈满
    stack->data[++stack->top] = val;
    return 1;
}

// 出栈
int stackPop(Stack *stack, int *val) {
    if (stackIsEmpty(stack)) return 0;
    *val = stack->data[stack->top--];
    return 1;
}

// 获取栈顶元素
int stackPeek(Stack *stack, int *val) {
    if (stackIsEmpty(stack)) return 0;
    *val = stack->data[stack->top];
    return 1;
}

四、队列

// 循环队列结构定义
#define MAX_QUEUE_SIZE 10000
typedef struct {
    int data[MAX_QUEUE_SIZE];
    int front; // 队头指针
    int rear;  // 队尾指针（指向下一个可插入位置）
} Queue;

// 初始化队列
void queueInit(Queue *queue) {
    queue->front = 0;
    queue->rear = 0;
}

// 判断队列空
int queueIsEmpty(Queue *queue) {
    return queue->front == queue->rear;
}

// 判断队列满
int queueIsFull(Queue *queue) {
    return (queue->rear + 1) % MAX_QUEUE_SIZE == queue->front;
}

// 入队
int queueEnqueue(Queue *queue, int val) {
    if (queueIsFull(queue)) return 0;
    queue->data[queue->rear] = val;
    queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
    return 1;
}

// 出队
int queueDequeue(Queue *queue, int *val) {
    if (queueIsEmpty(queue)) return 0;
    *val = queue->data[queue->front];
    queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
    return 1;
}

五、二叉树

// 二叉树节点定义（LeetCode标准）
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建二叉树节点
TreeNode* createTreeNode(int val) {
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 二叉树前序遍历（递归版，简洁）
void preOrder(TreeNode *root) {
    if (root == NULL) return;
    printf("%d ", root->val); // 访问节点（刷题时替换为业务逻辑）
    preOrder(root->left);
    preOrder(root->right);
}

// 二叉树层序遍历（BFS，高频）
void levelOrder(TreeNode *root) {
    if (root == NULL) return;
    Queue queue;
    queueInit(&queue);
    queueEnqueue(&queue, (int)(long long)root); // 指针转int存储
    while (!queueIsEmpty(&queue)) {
        int val;
        queueDequeue(&queue, &val);
        TreeNode *node = (TreeNode *)(long long)val;
        printf("%d ", node->val); // 访问节点
        if (node->left != NULL) queueEnqueue(&queue, (int)(long long)node->left);
        if (node->right != NULL) queueEnqueue(&queue, (int)(long long)node->right);
    }
}

六、哈希表

// 哈希表节点
typedef struct HashNode {
    int key;
    int val;
    struct HashNode *next;
} HashNode;

// 哈希表结构（链地址法解决冲突）
#define HASH_SIZE 1009 // 质数，减少冲突
typedef struct {
    HashNode *table[HASH_SIZE];
} HashTable;

// 哈希函数
int hashFunc(int key) {
    return abs(key) % HASH_SIZE;
}

// 初始化哈希表
void hashInit(HashTable *ht) {
    for (int i = 0; i < HASH_SIZE; i++) {
        ht->table[i] = NULL;
    }
}

// 插入键值对
void hashInsert(HashTable *ht, int key, int val) {
    int idx = hashFunc(key);
    HashNode *node = (HashNode *)malloc(sizeof(HashNode));
    node->key = key;
    node->val = val;
    node->next = ht->table[idx]; // 头插法
    ht->table[idx] = node;
}

// 查找key对应的val（找不到返回-1）
int hashFind(HashTable *ht, int key) {
    int idx = hashFunc(key);
    HashNode *cur = ht->table[idx];
    while (cur != NULL) {
        if (cur->key == key) return cur->val;
        cur = cur->next;
    }
    return -1;
}

// 释放哈希表内存（刷题可选，避免内存泄漏）
void hashFree(HashTable *ht) {
    for (int i = 0; i < HASH_SIZE; i++) {
        HashNode *cur = ht->table[i];
        while (cur != NULL) {
            HashNode *temp = cur;
            cur = cur->next;
            free(temp);
        }
        ht->table[i] = NULL;
    }
}

七、双向链表

// 双向链表节点定义
typedef struct DListNode {
    int key;          // 存key（LRU需删除尾节点时同步删哈希表）
    int val;          // 存值
    struct DListNode *prev;
    struct DListNode *next;
} DListNode;

// 双向链表结构（带哨兵头/尾，简化边界处理）
typedef struct {
    DListNode *head;  // 哨兵头节点
    DListNode *tail;  // 哨兵尾节点
    int size;         // 链表长度
} DLinkedList;

// 创建双向链表节点
DListNode* createDListNode(int key, int val) {
    DListNode *node = (DListNode*)malloc(sizeof(DListNode));
    node->key = key;
    node->val = val;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

// 初始化双向链表（哨兵头尾相连）
DLinkedList* initDLinkedList() {
    DLinkedList *list = (DLinkedList*)malloc(sizeof(DLinkedList));
    list->head = createDListNode(-1, -1);
    list->tail = createDListNode(-1, -1);
    list->head->next = list->tail;
    list->tail->prev = list->head;
    list->size = 0;
    return list;
}

// 将节点插入到链表头部（LRU访问后移到头部）
void addToHead(DLinkedList *list, DListNode *node) {
    node->prev = list->head;
    node->next = list->head->next;
    list->head->next->prev = node;
    list->head->next = node;
    list->size++;
}

// 删除指定节点（无需遍历找前驱/后继）
void removeNode(DLinkedList *list, DListNode *node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
    list->size--;
}

// 删除并返回尾节点（LRU满时删除尾节点）
DListNode* removeTail(DLinkedList *list) {
    DListNode *tailNode = list->tail->prev;
    removeNode(list, tailNode);
    return tailNode;
}

八、优先级队列

// 优先级队列元素（存值+优先级，这里用值本身作为优先级）
typedef struct {
    int *data;       // 堆数组
    int capacity;    // 容量
    int size;        // 当前元素数
} PriorityQueue;

// 初始化优先级队列（小顶堆，可改比较逻辑为大顶堆）
PriorityQueue* initPriorityQueue(int capacity) {
    PriorityQueue *pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));
    pq->data = (int*)malloc((capacity + 1) * sizeof(int)); // 堆从1开始存储
    pq->capacity = capacity;
    pq->size = 0;
    return pq;
}

// 交换堆中两个元素
void swapPq(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 小顶堆下沉调整（核心）
void heapifyDown(PriorityQueue *pq, int idx) {
    int minIdx = idx;
    int left = 2 * idx;   // 左子节点
    int right = 2 * idx + 1; // 右子节点
    // 找最小的子节点
    if (left <= pq->size && pq->data[left] < pq->data[minIdx]) minIdx = left;
    if (right <= pq->size && pq->data[right] < pq->data[minIdx]) minIdx = right;
    if (minIdx != idx) {
        swapPq(&pq->data[idx], &pq->data[minIdx]);
        heapifyDown(pq, minIdx); // 递归调整
    }
}

// 小顶堆上浮调整
void heapifyUp(PriorityQueue *pq, int idx) {
    while (idx > 1 && pq->data[idx / 2] > pq->data[idx]) {
        swapPq(&pq->data[idx / 2], &pq->data[idx]);
        idx /= 2;
    }
}

// 入队（插入元素）
int pqEnqueue(PriorityQueue *pq, int val) {
    if (pq->size >= pq->capacity) return 0; // 队列满
    pq->size++;
    pq->data[pq->size] = val;
    heapifyUp(pq, pq->size); // 上浮调整
    return 1;
}

// 出队（弹出优先级最高的元素，小顶堆即最小值）
int pqDequeue(PriorityQueue *pq, int *val) {
    if (pq->size == 0) return 0; // 队列空
    *val = pq->data[1];
    pq->data[1] = pq->data[pq->size]; // 最后一个元素移到堆顶
    pq->size--;
    heapifyDown(pq, 1); // 下沉调整
    return 1;
}

// 获取队首元素（不弹出）
int pqPeek(PriorityQueue *pq, int *val) {
    if (pq->size == 0) return 0;
    *val = pq->data[1];
    return 1;
}

九、并查集

// 并查集结构
typedef struct {
    int *parent; // 父节点数组
    int *rank;   // 秩（用于按秩合并，减少树高度）
    int count;   // 连通分量数
} UnionFind;

// 初始化并查集
UnionFind* initUnionFind(int n) {
    UnionFind *uf = (UnionFind*)malloc(sizeof(UnionFind));
    uf->parent = (int*)malloc(n * sizeof(int));
    uf->rank = (int*)malloc(n * sizeof(int));
    uf->count = n; // 初始每个元素自成一个集合
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i; // 父节点指向自己
        uf->rank[i] = 1;   // 初始秩为1
    }
    return uf;
}

// 查找根节点（路径压缩，降低查找复杂度）
int find(UnionFind *uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]); // 路径压缩
    }
    return uf->parent[x];
}

// 合并两个集合（按秩合并，避免树退化成链表）
void unionSet(UnionFind *uf, int x, int y) {
    int rootX = find(uf, x);
    int rootY = find(uf, y);
    if (rootX == rootY) return; // 已在同一集合
    
    // 秩小的树合并到秩大的树下
    if (uf->rank[rootX] < uf->rank[rootY]) {
        uf->parent[rootX] = rootY;
    } else if (uf->rank[rootX] > uf->rank[rootY]) {
        uf->parent[rootY] = rootX;
    } else {
        uf->parent[rootY] = rootX;
        uf->rank[rootX]++; // 秩相同，合并后秩+1
    }
    uf->count--; // 连通分量数减1
}

// 判断两个元素是否连通
int isConnected(UnionFind *uf, int x, int y) {
    return find(uf, x) == find(uf, y);
}

十、邻接表

// 邻接表节点（存储邻接顶点+权重，无权图权重可设为1）
typedef struct AdjNode {
    int vertex;      // 邻接顶点索引
    int weight;      // 边权重
    struct AdjNode *next;
} AdjNode;

// 邻接表头（每个顶点对应一个链表）
typedef struct AdjList {
    AdjNode *head;
} AdjList;

// 图结构（邻接表实现）
typedef struct {
    int numVertices; // 顶点数
    AdjList *array;  // 邻接表数组
    int isDirected;  // 是否有向图（1：有向，0：无向）
} Graph;

// 创建邻接表节点
AdjNode* createAdjNode(int v, int weight) {
    AdjNode *node = (AdjNode*)malloc(sizeof(AdjNode));
    node->vertex = v;
    node->weight = weight;
    node->next = NULL;
    return node;
}

// 初始化图
Graph* initGraph(int vertices, int isDirected) {
    Graph *graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->isDirected = isDirected;
    graph->array = (AdjList*)malloc(vertices * sizeof(AdjList));
    // 初始化每个顶点的邻接表为空
    for (int i = 0; i < vertices; i++) {
        graph->array[i].head = NULL;
    }
    return graph;
}

// 添加边（无向图需添加双向边）
void addEdge(Graph *graph, int src, int dest, int weight) {
    // 添加src→dest的边
    AdjNode *node = createAdjNode(dest, weight);
    node->next = graph->array[src].head;
    graph->array[src].head = node;
    // 无向图需添加dest→src的边
    if (!graph->isDirected) {
        node = createAdjNode(src, weight);
        node->next = graph->array[dest].head;
        graph->array[dest].head = node;
    }
}

// 图的DFS遍历（递归版）
void dfsGraph(Graph *graph, int v, int *visited) {
    visited[v] = 1; // 标记已访问
    printf("访问顶点：%d ", v); // 刷题时替换为业务逻辑
    
    AdjNode *cur = graph->array[v].head;
    while (cur != NULL) {
        if (!visited[cur->vertex]) {
            dfsGraph(graph, cur->vertex, visited);
        }
        cur = cur->next;
    }
}

十一、单调栈

// 单调栈（基于之前的栈结构，封装单调逻辑）
#define MAX_MONO_STACK_SIZE 10000
typedef struct {
    int data[MAX_MONO_STACK_SIZE];
    int top;
} MonoStack;

// 初始化单调栈
void monoStackInit(MonoStack *stack) {
    stack->top = -1;
}

// 判断栈空
int monoStackIsEmpty(MonoStack *stack) {
    return stack->top == -1;
}

// 入栈（保持栈内元素单调递减，可改逻辑为递增）
int monoStackPush(MonoStack *stack, int val) {
    if (stack->top >= MAX_MONO_STACK_SIZE - 1) return 0;
    // 弹出所有比当前值小的元素（单调递减栈）
    while (!monoStackIsEmpty(stack) && stack->data[stack->top] < val) {
        stack->top--;
    }
    stack->data[++stack->top] = val;
    return 1;
}

// 出栈（仅弹出栈顶，不处理单调逻辑）
int monoStackPop(MonoStack *stack, int *val) {
    if (monoStackIsEmpty(stack)) return 0;
    *val = stack->data[stack->top--];
    return 1;
}

// 示例：找数组中每个元素的下一个更大元素（LeetCode 496题）
int* nextGreaterElement(int nums[], int n, int *resSize) {
    *resSize = n;
    int *res = (int*)malloc(n * sizeof(int));
    MonoStack stack;
    monoStackInit(&stack);
    
    // 倒序遍历
    for (int i = n - 1; i >= 0; i--) {
        // 弹出栈中比当前元素小的
        while (!monoStackIsEmpty(&stack) && stack.data[stack.top] <= nums[i]) {
            stack.top--;
        }
        // 栈空则无更大元素，否则栈顶是答案
        res[i] = monoStackIsEmpty(&stack) ? -1 : stack.data[stack.top];
        // 当前元素入栈
        stack.data[++stack.top] = nums[i];
    }
    return res;
}