常用数据结构实现

数据结构是计算机存储、组织数据的方式。选择合适的数据结构可以显著提高算法的效率。 本章将用C语言实现几种最常用的数据结构：链表、栈、队列和二叉树。 这些结构是学习更复杂算法的基础，也是面试和实际项目中的高频考点。

🔗 链表（Linked List）

链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表在插入和删除操作上比数组更高效，但随机访问较慢。

🔸 单向链表（Singly Linked List）

#include <stdio.h>
#include <stdlib.h>

// 节点结构
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 创建新节点
Node* createNode(int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) return NULL;
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 在头部插入
void insertAtHead(Node **head, int data) {
    Node *newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

// 在尾部插入
void insertAtTail(Node **head, int data) {
    Node *newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node *temp = *head;
    while (temp->next) temp = temp->next;
    temp->next = newNode;
}

// 删除指定值的节点
void deleteNode(Node **head, int key) {
    Node *temp = *head, *prev = NULL;
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;
    prev->next = temp->next;
    free(temp);
}

// 遍历打印
void printList(Node *head) {
    while (head) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

// 释放链表
void freeList(Node *head) {
    Node *tmp;
    while (head) {
        tmp = head;
        head = head->next;
        free(tmp);
    }
}

int main() {
    Node *head = NULL;
    insertAtTail(&head, 10);
    insertAtTail(&head, 20);
    insertAtHead(&head, 5);
    printList(head);   // 5 -> 10 -> 20 -> NULL
    deleteNode(&head, 10);
    printList(head);   // 5 -> 20 -> NULL
    freeList(head);
    return 0;
}

🔸 双向链表（Doubly Linked List）

每个节点包含指向前一个和后一个节点的指针，便于双向遍历和删除。

typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

// 在头部插入
void insertAtHeadD(DNode **head, int data) {
    DNode *newNode = (DNode*)malloc(sizeof(DNode));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = *head;
    if (*head) (*head)->prev = newNode;
    *head = newNode;
}

// 打印正向
void printForward(DNode *head) {
    while (head) {
        printf("%d <-> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

📚 栈（Stack）

栈是一种后进先出（LIFO）的数据结构。可以用数组或链表实现。

🔸 数组实现栈

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct {
    int arr[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

bool isEmpty(Stack *s) {
    return s->top == -1;
}

bool isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

bool push(Stack *s, int val) {
    if (isFull(s)) return false;
    s->arr[++s->top] = val;
    return true;
}

bool pop(Stack *s, int *val) {
    if (isEmpty(s)) return false;
    *val = s->arr[s->top--];
    return true;
}

bool peek(Stack *s, int *val) {
    if (isEmpty(s)) return false;
    *val = s->arr[s->top];
    return true;
}

int main() {
    Stack s;
    initStack(&s);
    push(&s, 10);
    push(&s, 20);
    int val;
    pop(&s, &val);
    printf("弹出: %d\n", val);  // 20
    return 0;
}

🔸 链表实现栈

typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode;

typedef struct {
    StackNode *top;
} LinkedListStack;

void initLLStack(LinkedListStack *s) {
    s->top = NULL;
}

void pushLL(LinkedListStack *s, int val) {
    StackNode *newNode = (StackNode*)malloc(sizeof(StackNode));
    newNode->data = val;
    newNode->next = s->top;
    s->top = newNode;
}

int popLL(LinkedListStack *s) {
    if (s->top == NULL) {
        printf("栈空\n");
        return -1;
    }
    StackNode *temp = s->top;
    int val = temp->data;
    s->top = s->top->next;
    free(temp);
    return val;
}

📬 队列（Queue）

队列是一种先进先出（FIFO）的数据结构。常用实现有循环数组和链表。

🔸 循环队列（数组实现）

#define QUEUE_SIZE 5

typedef struct {
    int arr[QUEUE_SIZE];
    int front;
    int rear;
    int count;  // 元素个数，便于区分满和空
} CircularQueue;

void initQueue(CircularQueue *q) {
    q->front = 0;
    q->rear = 0;
    q->count = 0;
}

bool enqueue(CircularQueue *q, int val) {
    if (q->count == QUEUE_SIZE) return false;
    q->arr[q->rear] = val;
    q->rear = (q->rear + 1) % QUEUE_SIZE;
    q->count++;
    return true;
}

bool dequeue(CircularQueue *q, int *val) {
    if (q->count == 0) return false;
    *val = q->arr[q->front];
    q->front = (q->front + 1) % QUEUE_SIZE;
    q->count--;
    return true;
}

🔸 链式队列

typedef struct QueueNode {
    int data;
    struct QueueNode *next;
} QueueNode;

typedef struct {
    QueueNode *front;
    QueueNode *rear;
} LinkedQueue;

void initLinkedQueue(LinkedQueue *q) {
    q->front = q->rear = NULL;
}

void enqueueL(LinkedQueue *q, int val) {
    QueueNode *newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->data = val;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

int dequeueL(LinkedQueue *q) {
    if (q->front == NULL) return -1;
    QueueNode *temp = q->front;
    int val = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    free(temp);
    return val;
}

🌳 二叉树（Binary Tree）

二叉树每个节点最多有两个子节点。二叉搜索树（BST）是一种特殊的二叉树，左子节点 < 根节点 < 右子节点。

#include <stdio.h>
#include <stdlib.h>

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

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

// 插入节点（构建BST）
TreeNode* insert(TreeNode *root, int data) {
    if (root == NULL) return createTreeNode(data);
    if (data < root->data)
        root->left = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);
    return root;
}

// 查找最小值节点
TreeNode* findMin(TreeNode *root) {
    while (root && root->left) root = root->left;
    return root;
}

// 删除节点
TreeNode* deleteNode(TreeNode *root, int data) {
    if (root == NULL) return NULL;
    if (data < root->data)
        root->left = deleteNode(root->left, data);
    else if (data > root->data)
        root->right = deleteNode(root->right, data);
    else {
        // 找到待删除节点
        if (root->left == NULL) {
            TreeNode *temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode *temp = root->left;
            free(root);
            return temp;
        }
        // 有两个孩子：用右子树的最小值替换
        TreeNode *temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

// 查找节点
TreeNode* search(TreeNode *root, int data) {
    if (root == NULL || root->data == data) return root;
    if (data < root->data)
        return search(root->left, data);
    else
        return search(root->right, data);
}

// 中序遍历（升序）
void inorder(TreeNode *root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

// 释放树
void freeTree(TreeNode *root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

int main() {
    TreeNode *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    printf("中序遍历: ");
    inorder(root);   // 20 30 40 50 60 70 80
    printf("\n");

    root = deleteNode(root, 50);
    printf("删除50后: ");
    inorder(root);
    printf("\n");

    freeTree(root);
    return 0;
}

📊 时间复杂度对比

⚠️ 常见错误与注意事项

• 内存泄漏：在删除节点或清空数据结构时，务必释放所有动态分配的内存。
• 指针悬空：释放节点后，应将指向该节点的指针置为NULL，避免野指针。
• 链表环检测：插入操作不当可能产生环，导致遍历无限循环。
• 栈和队列的边界条件：注意检查空栈/空队列以及满栈/满队列（数组实现）。
• 二叉树的递归深度：极端情况下（如退化为链表）递归可能导致栈溢出，可改用迭代实现。
• 忘记初始化：结构体中的指针成员必须初始化为NULL，否则条件判断会出错。

---

掌握这些基础数据结构的实现，是学习算法和解决复杂编程问题的重要一步。 建议读者动手编码，并尝试扩展这些结构（如循环链表、双向循环链表、平衡二叉树等）。