⚡

C语言数据结构Skill c-data-structures

这个技能专注于在C语言中实现各种基础与高级数据结构，如数组、链表、树和哈希表，并进行手动内存管理。适用于系统编程、嵌入式开发、性能优化和算法实现，关键词包括C语言、数据结构、内存管理、数组、链表、树、哈希表、系统编程、嵌入式开发。

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

名称: c-data-structures 用户可调用: false 描述: 在C语言中实现数据结构时使用，包括数组、链表、树和哈希表，并手动管理内存。 允许工具:

  • Bash
  • 读取
  • 写入
  • 编辑

C语言数据结构

掌握在C语言中实现基础和高级数据结构，包括适当的内存管理，如数组、链表、树、哈希表等。

数组和指针

静态数组

#include <stdio.h>

void print_array(int arr[], size_t size) {
    for (size_t i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("
");
}

int main(void) {
    int numbers[5] = {10, 20, 30, 40, 50};

    printf("数组大小: %zu 字节
", sizeof(numbers));
    printf("元素大小: %zu 字节
", sizeof(numbers[0]));
    printf("元素数量: %zu
", sizeof(numbers) / sizeof(numbers[0]));

    print_array(numbers, 5);

    // 数组索引是指针算术
    printf("numbers[2] = %d
", numbers[2]);
    printf("*(numbers + 2) = %d
", *(numbers + 2));

    return 0;
}

动态数组

#include <stdio.h>
#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;
}

int array_get(DynamicArray *arr, size_t index) {
    if (index >= arr->size) {
        fprintf(stderr, "索引越界
");
        return -1;
    }
    return arr->data[index];
}

void array_free(DynamicArray *arr) {
    if (arr) {
        free(arr->data);
        free(arr);
    }
}

int main(void) {
    DynamicArray *arr = array_create(2);

    array_push(arr, 10);
    array_push(arr, 20);
    array_push(arr, 30);  // 将触发调整大小

    for (size_t i = 0; i < arr->size; i++) {
        printf("%d ", array_get(arr, i));
    }
    printf("
");

    array_free(arr);
    return 0;
}

结构体和联合体

结构体

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

typedef struct {
    char name[50];
    int age;
    float gpa;
} Student;

typedef struct {
    int x;
    int y;
} Point;

// 带有灵活数组成员的结构体
typedef struct {
    size_t length;
    char data[];  // 灵活数组成员
} String;

String *string_create(const char *str) {
    size_t len = strlen(str);
    String *s = malloc(sizeof(String) + len + 1);
    if (!s) return NULL;

    s->length = len;
    strcpy(s->data, str);
    return s;
}

void demonstrate_structs(void) {
    Student s1 = {"Alice", 20, 3.8};
    Student s2;

    // 复制结构体
    s2 = s1;
    s2.age = 21;

    printf("s1: %s, 年龄 %d
", s1.name, s1.age);
    printf("s2: %s, 年龄 %d
", s2.name, s2.age);

    // 结构体指针
    Student *sp = &s1;
    printf("通过指针的名称: %s
", sp->name);

    // 灵活数组成员
    String *str = string_create("Hello, World!");
    printf("字符串: %s (长度: %zu)
", str->data, str->length);
    free(str);
}

联合体

#include <stdio.h>
#include <stdint.h>

typedef union {
    uint32_t word;
    uint16_t halfwords[2];
    uint8_t bytes[4];
} Word;

typedef enum {
    TYPE_INT,
    TYPE_FLOAT,
    TYPE_STRING
} ValueType;

typedef struct {
    ValueType type;
    union {
        int i;
        float f;
        char *s;
    } value;
} Value;

void print_value(Value *v) {
    switch (v->type) {
        case TYPE_INT:
            printf("int: %d
", v->value.i);
            break;
        case TYPE_FLOAT:
            printf("float: %f
", v->value.f);
            break;
        case TYPE_STRING:
            printf("string: %s
", v->value.s);
            break;
    }
}

int main(void) {
    Word w = {.word = 0x12345678};
    printf("Word: 0x%08x
", w.word);
    printf("Byte 0: 0x%02x
", w.bytes[0]);
    printf("Byte 1: 0x%02x
", w.bytes[1]);

    Value v1 = {TYPE_INT, {.i = 42}};
    Value v2 = {TYPE_FLOAT, {.f = 3.14}};
    Value v3 = {TYPE_STRING, {.s = "Hello"}};

    print_value(&v1);
    print_value(&v2);
    print_value(&v3);

    return 0;
}

链表

单链表

#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_push_front(LinkedList *list, int data) {
    Node *new_node = malloc(sizeof(Node));
    if (!new_node) return -1;

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

    return 0;
}

int list_push_back(LinkedList *list, int data) {
    Node *new_node = malloc(sizeof(Node));
    if (!new_node) return -1;

    new_node->data = data;
    new_node->next = NULL;

    if (!list->head) {
        list->head = new_node;
    } else {
        Node *current = list->head;
        while (current->next) {
            current = current->next;
        }
        current->next = new_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 && current->next->data != data) {
        current = current->next;
    }

    if (current->next) {
        Node *temp = current->next;
        current->next = current->next->next;
        free(temp);
        list->size--;
        return 0;
    }

    return -1;
}

void list_print(LinkedList *list) {
    Node *current = list->head;
    while (current) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL
");
}

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 <stdio.h>
#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;
}

int dlist_push_back(DoublyLinkedList *list, int data) {
    DNode *new_node = malloc(sizeof(DNode));
    if (!new_node) return -1;

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

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

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

int dlist_push_front(DoublyLinkedList *list, int data) {
    DNode *new_node = malloc(sizeof(DNode));
    if (!new_node) return -1;

    new_node->data = data;
    new_node->prev = NULL;
    new_node->next = list->head;

    if (!list->head) {
        list->tail = new_node;
    } else {
        list->head->prev = new_node;
    }

    list->head = new_node;
    list->size++;
    return 0;
}

void dlist_print_forward(DoublyLinkedList *list) {
    DNode *current = list->head;
    while (current) {
        printf("%d <-> ", current->data);
        current = current->next;
    }
    printf("NULL
");
}

void dlist_print_backward(DoublyLinkedList *list) {
    DNode *current = list->tail;
    while (current) {
        printf("%d <-> ", current->data);
        current = current->prev;
    }
    printf("NULL
");
}

void dlist_free(DoublyLinkedList *list) {
    if (!list) return;

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

栈和队列

栈（基于数组）

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

typedef struct {
    int *data;
    size_t capacity;
    int top;
} Stack;

Stack *stack_create(size_t capacity) {
    Stack *stack = malloc(sizeof(Stack));
    if (!stack) return NULL;

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

    stack->capacity = capacity;
    stack->top = -1;
    return stack;
}

bool stack_is_empty(Stack *stack) {
    return stack->top == -1;
}

bool stack_is_full(Stack *stack) {
    return stack->top == (int)(stack->capacity - 1);
}

int stack_push(Stack *stack, int value) {
    if (stack_is_full(stack)) {
        return -1;
    }

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

int stack_pop(Stack *stack, int *value) {
    if (stack_is_empty(stack)) {
        return -1;
    }

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

int stack_peek(Stack *stack, int *value) {
    if (stack_is_empty(stack)) {
        return -1;
    }

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

void stack_free(Stack *stack) {
    if (stack) {
        free(stack->data);
        free(stack);
    }
}

队列（循环缓冲区）

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

typedef struct {
    int *data;
    size_t capacity;
    size_t front;
    size_t rear;
    size_t size;
} Queue;

Queue *queue_create(size_t capacity) {
    Queue *queue = malloc(sizeof(Queue));
    if (!queue) return NULL;

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

    queue->capacity = capacity;
    queue->front = 0;
    queue->rear = 0;
    queue->size = 0;
    return queue;
}

bool queue_is_empty(Queue *queue) {
    return queue->size == 0;
}

bool queue_is_full(Queue *queue) {
    return queue->size == queue->capacity;
}

int queue_enqueue(Queue *queue, int value) {
    if (queue_is_full(queue)) {
        return -1;
    }

    queue->data[queue->rear] = value;
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->size++;
    return 0;
}

int queue_dequeue(Queue *queue, int *value) {
    if (queue_is_empty(queue)) {
        return -1;
    }

    *value = queue->data[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size--;
    return 0;
}

void queue_free(Queue *queue) {
    if (queue) {
        free(queue->data);
        free(queue);
    }
}

二叉树

二叉搜索树

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

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

typedef struct {
    TreeNode *root;
    size_t size;
} BST;

BST *bst_create(void) {
    BST *tree = malloc(sizeof(BST));
    if (!tree) return NULL;

    tree->root = NULL;
    tree->size = 0;
    return tree;
}

TreeNode *create_node(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_helper(TreeNode *node, int data) {
    if (!node) {
        return create_node(data);
    }

    if (data < node->data) {
        node->left = bst_insert_helper(node->left, data);
    } else if (data > node->data) {
        node->right = bst_insert_helper(node->right, data);
    }

    return node;
}

int bst_insert(BST *tree, int data) {
    tree->root = bst_insert_helper(tree->root, data);
    if (tree->root) {
        tree->size++;
        return 0;
    }
    return -1;
}

TreeNode *bst_search_helper(TreeNode *node, int data) {
    if (!node || node->data == data) {
        return node;
    }

    if (data < node->data) {
        return bst_search_helper(node->left, data);
    }
    return bst_search_helper(node->right, data);
}

bool bst_search(BST *tree, int data) {
    return bst_search_helper(tree->root, data) != NULL;
}

TreeNode *find_min(TreeNode *node) {
    while (node->left) {
        node = node->left;
    }
    return node;
}

TreeNode *bst_delete_helper(TreeNode *node, int data) {
    if (!node) return NULL;

    if (data < node->data) {
        node->left = bst_delete_helper(node->left, data);
    } else if (data > node->data) {
        node->right = bst_delete_helper(node->right, data);
    } else {
        // 找到要删除的节点
        if (!node->left) {
            TreeNode *temp = node->right;
            free(node);
            return temp;
        } else if (!node->right) {
            TreeNode *temp = node->left;
            free(node);
            return temp;
        }

        // 节点有两个子节点
        TreeNode *temp = find_min(node->right);
        node->data = temp->data;
        node->right = bst_delete_helper(node->right, temp->data);
    }

    return node;
}

void inorder_traversal(TreeNode *node) {
    if (node) {
        inorder_traversal(node->left);
        printf("%d ", node->data);
        inorder_traversal(node->right);
    }
}

void preorder_traversal(TreeNode *node) {
    if (node) {
        printf("%d ", node->data);
        preorder_traversal(node->left);
        preorder_traversal(node->right);
    }
}

void postorder_traversal(TreeNode *node) {
    if (node) {
        postorder_traversal(node->left);
        postorder_traversal(node->right);
        printf("%d ", node->data);
    }
}

void bst_free_helper(TreeNode *node) {
    if (node) {
        bst_free_helper(node->left);
        bst_free_helper(node->right);
        free(node);
    }
}

void bst_free(BST *tree) {
    if (tree) {
        bst_free_helper(tree->root);
        free(tree);
    }
}

哈希表

简单哈希表

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

typedef struct HashNode {
    char *key;
    int value;
    struct HashNode *next;
} HashNode;

typedef struct {
    HashNode **buckets;
    size_t capacity;
    size_t size;
} HashTable;

unsigned long hash(const char *str, size_t capacity) {
    unsigned long hash = 5381;
    int c;

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

    return hash % capacity;
}

HashTable *hashtable_create(size_t capacity) {
    HashTable *table = malloc(sizeof(HashTable));
    if (!table) return NULL;

    table->buckets = calloc(capacity, sizeof(HashNode *));
    if (!table->buckets) {
        free(table);
        return NULL;
    }

    table->capacity = capacity;
    table->size = 0;
    return table;
}

int hashtable_insert(HashTable *table, const char *key, int value) {
    unsigned long index = hash(key, table->capacity);

    // 检查键是否存在
    HashNode *current = table->buckets[index];
    while (current) {
        if (strcmp(current->key, key) == 0) {
            current->value = value;
            return 0;
        }
        current = current->next;
    }

    // 创建新节点
    HashNode *new_node = malloc(sizeof(HashNode));
    if (!new_node) return -1;

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

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

    return 0;
}

bool hashtable_get(HashTable *table, const char *key, int *value) {
    unsigned long index = hash(key, table->capacity);

    HashNode *current = table->buckets[index];
    while (current) {
        if (strcmp(current->key, key) == 0) {
            *value = current->value;
            return true;
        }
        current = current->next;
    }

    return false;
}

bool hashtable_remove(HashTable *table, const char *key) {
    unsigned long index = hash(key, table->capacity);

    HashNode *current = table->buckets[index];
    HashNode *prev = NULL;

    while (current) {
        if (strcmp(current->key, key) == 0) {
            if (prev) {
                prev->next = current->next;
            } else {
                table->buckets[index] = current->next;
            }

            free(current->key);
            free(current);
            table->size--;
            return true;
        }

        prev = current;
        current = current->next;
    }

    return false;
}

void hashtable_free(HashTable *table) {
    if (!table) return;

    for (size_t i = 0; i < table->capacity; i++) {
        HashNode *current = table->buckets[i];
        while (current) {
            HashNode *next = current->next;
            free(current->key);
            free(current);
            current = next;
        }
    }

    free(table->buckets);
    free(table);
}

内存管理

自定义分配器

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

typedef struct Block {
    size_t size;
    bool is_free;
    struct Block *next;
} Block;

typedef struct {
    void *memory;
    size_t total_size;
    Block *free_list;
} Allocator;

Allocator *allocator_create(size_t size) {
    Allocator *alloc = malloc(sizeof(Allocator));
    if (!alloc) return NULL;

    alloc->memory = malloc(size);
    if (!alloc->memory) {
        free(alloc);
        return NULL;
    }

    alloc->total_size = size;

    // 初始化空闲列表为一个大的块
    alloc->free_list = (Block *)alloc->memory;
    alloc->free_list->size = size - sizeof(Block);
    alloc->free_list->is_free = true;
    alloc->free_list->next = NULL;

    return alloc;
}

void *allocator_alloc(Allocator *alloc, size_t size) {
    Block *current = alloc->free_list;
    Block *prev = NULL;

    // 寻找第一个合适的块
    while (current) {
        if (current->is_free && current->size >= size) {
            // 如果有足够空间，分割块
            if (current->size >= size + sizeof(Block) + 1) {
                Block *new_block = (Block *)((char *)current + sizeof(Block) + size);
                new_block->size = current->size - size - sizeof(Block);
                new_block->is_free = true;
                new_block->next = current->next;

                current->size = size;
                current->next = new_block;
            }

            current->is_free = false;
            return (char *)current + sizeof(Block);
        }

        prev = current;
        current = current->next;
    }

    return NULL;
}

void allocator_free(Allocator *alloc, void *ptr) {
    if (!ptr) return;

    Block *block = (Block *)((char *)ptr - sizeof(Block));
    block->is_free = true;

    // 如果下一个块空闲，合并
    if (block->next && block->next->is_free) {
        block->size += sizeof(Block) + block->next->size;
        block->next = block->next->next;
    }

    // 如果前一个块空闲，合并
    Block *current = alloc->free_list;
    while (current && current->next != block) {
        current = current->next;
    }

    if (current && current->is_free) {
        current->size += sizeof(Block) + block->size;
        current->next = block->next;
    }
}

void allocator_destroy(Allocator *alloc) {
    if (alloc) {
        free(alloc->memory);
        free(alloc);
    }
}

最佳实践

  1. 始终初始化指针：将指针初始化为NULL，以避免访问未初始化的内存。在解引用前检查NULL。

  2. 释放所有分配的内存：每个malloc/calloc/realloc必须有相应的free。仔细跟踪分配以防止内存泄漏。

  3. 检查分配成功：在使用分配的内存之前，始终检查malloc/calloc/realloc是否返回NULL。

  4. 避免悬空指针：释放内存后将指针设置为NULL。永远不要在使用指针后释放它指向的内存。

  5. 使用大小参数：向函数传递大小参数，而不是硬编码数组大小，以提高可重用性和安全性。

  6. 实现一致的清理：为所有数据结构提供free/destroy函数，以相反的顺序执行完整的清理。

  7. 验证输入参数：在对数据结构执行操作之前，检查NULL指针和无效索引。

  8. 使用typedef提高清晰度：对结构体使用typedef以提高代码可读性并减少冗长。

  9. 考虑缓存局部性：安排结构体成员和访问模式以最大化CPU缓存效率，特别是对于性能关键的代码。

  10. 文档化所有权：清楚地文档化哪些函数拥有分配的内存，哪些负责释放它。

常见陷阱

  1. 内存泄漏：忘记释放分配的内存或丢失对分配内存的最后一个引用会导致内存泄漏。

  2. 缓冲区溢出：写入超出分配的数组边界会破坏内存并导致未定义行为或安全漏洞。

  3. 使用后释放：在内存被释放后访问它会导致未定义行为和潜在崩溃。

  4. 双重释放：两次释放相同的内存会破坏堆并导致崩溃。释放后始终将指针设置为NULL。

  5. 未初始化的指针：在初始化前使用指针会导致访问随机内存地址。

  6. 浅拷贝问题：复制带有指针的结构体会创建对相同内存的多个引用，导致双重释放或意外修改。

  7. 差一错误：不正确的循环边界或数组索引会导致缓冲区溢出或遗漏元素。

  8. 整数溢出：在计算分配大小时不检查溢出可能导致分配不足。

  9. 混合sizeof操作数类型：使用sizeof与指针而不是指向的类型（sizeof(ptr) vs sizeof(*ptr)）分配错误的大小。

  10. 低效的重新分配：为每个元素重新分配而不是加倍容量会导致性能差（O(n²)而不是摊销O(1)）。

何时使用此技能

在需要时使用C数据结构：

  • 为特定性能要求实现自定义数据结构
  • 在内存受限的嵌入式系统上工作
  • 构建需要细粒度内存控制的系统级软件
  • 创建内存布局重要的高性能应用程序
  • 开发内核模块或设备驱动程序
  • 为学习目的理解低级内存管理
  • 将教科书算法移植到生产代码
  • 构建基础库和框架
  • 在资源受限环境中优化内存使用
  • 实现自定义分配器或内存池

此技能对于系统程序员、嵌入式开发人员、性能工程师以及任何在资源受限或性能关键环境中使用C的人员都是必需的。

资源

书籍

  • 《C程序设计语言》 by Kernighan and Ritchie
  • 《数据结构使用C》 by Reema Thareja
  • 《C语言算法》 by Robert Sedgewick
  • 《理解和使用C指针》 by Richard Reese

在线资源

工具

  • Valgrind: 内存错误检测和分析
  • AddressSanitizer: 快速内存错误检测器
  • GDB: 带有内存检查的GNU调试器
  • cppcheck: C/C++静态分析工具
  • Electric Fence: 用于检测内存分配错误的库