⚡

C数据结构Skill c-data-structures

C数据结构技能专注于在C语言中手动管理内存和指针操作，实现和使用基础数据结构如数组、结构体、链表、树和哈希表，适用于嵌入式系统、操作系统和性能关键应用。关键词：C语言，数据结构，内存管理，指针，嵌入式开发，算法，编程基础。

嵌入式软件 0 次安装 2 次浏览 更新于 3/25/2026

name: c-data-structures user-invocable: false description: 当需要使用基础C数据结构，包括数组、结构体、链表、树和哈希表，并实现内存高效实现时使用。 allowed-tools:

  • Read
  • Write
  • Edit
  • Grep
  • Glob
  • Bash

C 数据结构

C语言中的数据结构需要手动内存管理和谨慎的指针操作。理解和实现基础数据结构对于构建高效的C应用程序至关重要。本技能涵盖数组、结构体、链表、树和哈希表。

数组和动态数组

数组提供连续内存存储，具有O(1)的访问时间。动态数组提供灵活性，但代价是偶尔的重新分配。

静态数组

#include <stdio.h>
#include <string.h>

// 使用静态数组
void array_operations(void) {
    int numbers[5] = {1, 2, 3, 4, 5};

    // 数组长度（仅适用于静态数组）
    size_t length = sizeof(numbers) / sizeof(numbers[0]);

    // 遍历数组
    for (size_t i = 0; i < length; i++) {
        printf("%d ", numbers[i]);
    }
    printf("
");

    // 数组作为函数参数（退化为指针）
    int sum = 0;
    for (size_t i = 0; i < length; i++) {
        sum += numbers[i];
    }
    printf("Sum: %d
", sum);
}

动态数组

#include <stdlib.h>
#include <string.h>

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} DynamicArray;

// 初始化动态数组
DynamicArray *array_create(size_t initial_capacity) {
    DynamicArray *arr = malloc(sizeof(DynamicArray));
    if (!arr) return NULL;

    arr->data = malloc(initial_capacity * sizeof(int));
    if (!arr->data) {
        free(arr);
        return NULL;
    }

    arr->size = 0;
    arr->capacity = initial_capacity;
    return arr;
}

// 向数组追加元素
int array_push(DynamicArray *arr, int value) {
    if (arr->size >= arr->capacity) {
        size_t new_capacity = arr->capacity * 2;
        int *new_data = realloc(arr->data, new_capacity * sizeof(int));
        if (!new_data) return -1;

        arr->data = new_data;
        arr->capacity = new_capacity;
    }

    arr->data[arr->size++] = value;
    return 0;
}

// 释放数组内存
void array_free(DynamicArray *arr) {
    if (arr) {
        free(arr->data);
        free(arr);
    }
}

结构体和数据建模

结构体将相关数据组合在一起，实现复杂的数据建模和组织。

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

// 定义结构体
typedef struct {
    char name[50];
    int age;
    float salary;
} Employee;

// 创建和初始化结构体
Employee *employee_create(const char *name, int age, float salary) {
    Employee *emp = malloc(sizeof(Employee));
    if (!emp) return NULL;

    strncpy(emp->name, name, sizeof(emp->name) - 1);
    emp->name[sizeof(emp->name) - 1] = '\0';
    emp->age = age;
    emp->salary = salary;

    return emp;
}

// 结构体嵌套结构体
typedef struct {
    int x;
    int y;
} Point;

typedef struct {
    Point top_left;
    Point bottom_right;
} Rectangle;

// 计算矩形面积
int rectangle_area(const Rectangle *rect) {
    int width = rect->bottom_right.x - rect->top_left.x;
    int height = rect->bottom_right.y - rect->top_left.y;
    return width * height;
}

链表

链表提供动态插入和删除，对于已知位置的操作具有O(1)的时间复杂度。

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

// 单链表节点
typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *head;
    size_t size;
} LinkedList;

// 创建新链表
LinkedList *list_create(void) {
    LinkedList *list = malloc(sizeof(LinkedList));
    if (!list) return NULL;

    list->head = NULL;
    list->size = 0;
    return list;
}

// 在开头插入
int list_prepend(LinkedList *list, int data) {
    Node *node = malloc(sizeof(Node));
    if (!node) return -1;

    node->data = data;
    node->next = list->head;
    list->head = node;
    list->size++;

    return 0;
}

// 在末尾插入
int list_append(LinkedList *list, int data) {
    Node *node = malloc(sizeof(Node));
    if (!node) return -1;

    node->data = data;
    node->next = NULL;

    if (!list->head) {
        list->head = node;
    } else {
        Node *current = list->head;
        while (current->next) {
            current = current->next;
        }
        current->next = node;
    }

    list->size++;
    return 0;
}

// 移除第一个出现的值
int list_remove(LinkedList *list, int data) {
    if (!list->head) return -1;

    // 移除头节点
    if (list->head->data == data) {
        Node *temp = list->head;
        list->head = list->head->next;
        free(temp);
        list->size--;
        return 0;
    }

    // 移除其他节点
    Node *current = list->head;
    while (current->next) {
        if (current->next->data == data) {
            Node *temp = current->next;
            current->next = current->next->next;
            free(temp);
            list->size--;
            return 0;
        }
        current = current->next;
    }

    return -1;  // 未找到
}

// 释放整个链表
void list_free(LinkedList *list) {
    if (!list) return;

    Node *current = list->head;
    while (current) {
        Node *next = current->next;
        free(current);
        current = next;
    }

    free(list);
}

双向链表

双向链表允许双向遍历，具有前向和后向指针。

#include <stdlib.h>

// 双向链表节点
typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

typedef struct {
    DNode *head;
    DNode *tail;
    size_t size;
} DoublyLinkedList;

// 创建新双向链表
DoublyLinkedList *dlist_create(void) {
    DoublyLinkedList *list = malloc(sizeof(DoublyLinkedList));
    if (!list) return NULL;

    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
    return list;
}

// 在末尾插入（使用尾指针为O(1)）
int dlist_append(DoublyLinkedList *list, int data) {
    DNode *node = malloc(sizeof(DNode));
    if (!node) return -1;

    node->data = data;
    node->next = NULL;
    node->prev = list->tail;

    if (list->tail) {
        list->tail->next = node;
    } else {
        list->head = node;
    }

    list->tail = node;
    list->size++;
    return 0;
}

// 从末尾移除（使用尾指针为O(1)）
int dlist_pop(DoublyLinkedList *list, int *data) {
    if (!list->tail) return -1;

    *data = list->tail->data;
    DNode *node = list->tail;

    if (list->tail->prev) {
        list->tail = list->tail->prev;
        list->tail->next = NULL;
    } else {
        list->head = NULL;
        list->tail = NULL;
    }

    free(node);
    list->size--;
    return 0;
}

二叉树

二叉树以层次结构组织数据，实现高效的搜索、插入和遍历操作。

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

// 二叉树节点
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建新树节点
TreeNode *tree_node_create(int data) {
    TreeNode *node = malloc(sizeof(TreeNode));
    if (!node) return NULL;

    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 插入到二叉搜索树
TreeNode *bst_insert(TreeNode *root, int data) {
    if (!root) {
        return tree_node_create(data);
    }

    if (data < root->data) {
        root->left = bst_insert(root->left, data);
    } else if (data > root->data) {
        root->right = bst_insert(root->right, data);
    }

    return root;
}

// 在二叉搜索树中搜索
TreeNode *bst_search(TreeNode *root, int data) {
    if (!root || root->data == data) {
        return root;
    }

    if (data < root->data) {
        return bst_search(root->left, data);
    }

    return bst_search(root->right, data);
}

// 中序遍历（对于BST为排序顺序）
void tree_inorder(TreeNode *root) {
    if (!root) return;

    tree_inorder(root->left);
    printf("%d ", root->data);
    tree_inorder(root->right);
}

// 释放整个树
void tree_free(TreeNode *root) {
    if (!root) return;

    tree_free(root->left);
    tree_free(root->right);
    free(root);
}

哈希表

哈希表使用哈希函数和冲突解决提供O(1)平均情况的插入、删除和查找。

#include <stdlib.h>
#include <string.h>

#define HASH_TABLE_SIZE 100

// 哈希表条目
typedef struct Entry {
    char *key;
    int value;
    struct Entry *next;  // 用于冲突链
} Entry;

// 哈希表
typedef struct {
    Entry *buckets[HASH_TABLE_SIZE];
    size_t size;
} HashTable;

// 哈希函数（djb2）
unsigned long hash(const char *str) {
    unsigned long hash = 5381;
    int c;

    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c;
    }

    return hash % HASH_TABLE_SIZE;
}

// 创建哈希表
HashTable *hashtable_create(void) {
    HashTable *table = malloc(sizeof(HashTable));
    if (!table) return NULL;

    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        table->buckets[i] = NULL;
    }
    table->size = 0;

    return table;
}

// 插入或更新键值对
int hashtable_set(HashTable *table, const char *key, int value) {
    unsigned long index = hash(key);
    Entry *entry = table->buckets[index];

    // 检查键是否存在
    while (entry) {
        if (strcmp(entry->key, key) == 0) {
            entry->value = value;
            return 0;
        }
        entry = entry->next;
    }

    // 创建新条目
    Entry *new_entry = malloc(sizeof(Entry));
    if (!new_entry) return -1;

    new_entry->key = strdup(key);
    if (!new_entry->key) {
        free(new_entry);
        return -1;
    }

    new_entry->value = value;
    new_entry->next = table->buckets[index];
    table->buckets[index] = new_entry;
    table->size++;

    return 0;
}

// 通过键获取值
int hashtable_get(HashTable *table, const char *key, int *value) {
    unsigned long index = hash(key);
    Entry *entry = table->buckets[index];

    while (entry) {
        if (strcmp(entry->key, key) == 0) {
            *value = entry->value;
            return 0;
        }
        entry = entry->next;
    }

    return -1;  // 未找到
}

// 释放哈希表
void hashtable_free(HashTable *table) {
    if (!table) return;

    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        Entry *entry = table->buckets[i];
        while (entry) {
            Entry *next = entry->next;
            free(entry->key);
            free(entry);
            entry = next;
        }
    }

    free(table);
}

栈和队列

栈（LIFO）和队列（FIFO）是基础的抽象数据类型，具有许多应用。

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

// 使用动态数组的栈
typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} Stack;

// 创建栈
Stack *stack_create(size_t initial_capacity) {
    Stack *stack = malloc(sizeof(Stack));
    if (!stack) return NULL;

    stack->data = malloc(initial_capacity * sizeof(int));
    if (!stack->data) {
        free(stack);
        return NULL;
    }

    stack->size = 0;
    stack->capacity = initial_capacity;
    return stack;
}

// 压栈
int stack_push(Stack *stack, int value) {
    if (stack->size >= stack->capacity) {
        size_t new_capacity = stack->capacity * 2;
        int *new_data = realloc(stack->data,
                                new_capacity * sizeof(int));
        if (!new_data) return -1;

        stack->data = new_data;
        stack->capacity = new_capacity;
    }

    stack->data[stack->size++] = value;
    return 0;
}

// 出栈
int stack_pop(Stack *stack, int *value) {
    if (stack->size == 0) return -1;

    *value = stack->data[--stack->size];
    return 0;
}

// 查看栈顶
int stack_peek(Stack *stack, int *value) {
    if (stack->size == 0) return -1;

    *value = stack->data[stack->size - 1];
    return 0;
}

// 检查栈是否为空
bool stack_is_empty(Stack *stack) {
    return stack->size == 0;
}

// 释放栈
void stack_free(Stack *stack) {
    if (stack) {
        free(stack->data);
        free(stack);
    }
}

最佳实践

  1. 始终将指针初始化为NULL，以防止访问未初始化的内存
  2. 在使用分配的内存之前检查malloc/calloc/realloc的返回值
  3. 以分配顺序的反序释放所有分配的内存
  4. 使用sizeof(变量)而不是sizeof(类型)以提高可维护性
  5. 跟踪数据结构大小以避免缓冲区溢出
  6. 当函数不应修改数据时使用const指针
  7. 显式初始化所有结构体成员以避免未定义行为
  8. 为数据结构操作记录时间和空间复杂度
  9. 使用typedef为结构体和指针创建更清晰的类型名称
  10. 为所有自定义数据结构实现销毁/释放函数

常见陷阱

  1. 忘记释放内存，导致长期运行程序中的内存泄漏
  2. 访问已释放的内存（释放后使用），导致未定义行为
  3. 多次释放同一内存（双重释放），导致堆损坏
  4. malloc后未检查NULL，导致段错误
  5. 使用未初始化的指针，访问随机内存位置
  6. 由于未跟踪数组边界导致的缓冲区溢出
  7. 返回指向局部变量的指针，这些变量会超出作用域
  8. 插入/删除操作后未更新大小计数器
  9. 链式结构中的循环引用没有适当清理
  10. 需要深拷贝时使用浅拷贝，共享可变状态

何时使用C数据结构

使用C数据结构当需要：

  • 对内存布局和访问模式的最大控制
  • 没有垃圾收集的最小内存开销
  • 实时系统的可预测性能特性
  • 与硬件或低级系统接口的集成
  • 构建其他语言使用的基础库
  • 理解高级抽象的内部工作原理
  • 用于学习算法和复杂性分析的教育目的
  • 资源有限的嵌入式系统需要效率
  • 性能关键代码，每个字节都很重要
  • 需要维护或扩展的遗留代码库

资源