C语言中collection是什么？如何实现？

C语言标准库中并没有直接提供名为 Collection 或类似 List、Set、Map 这样的通用集合数据结构。

这与其他现代语言（如 Java、C#、Python）形成了鲜明对比，在C语言中，你需要自己动手实现这些数据结构,或者使用第三方库。

C语言提供了一些基础的数据结构，我们可以利用它们来构建功能强大的集合，这些基础结构就是集合的“基石”。

C语言中集合的基石

C语言中,我们主要使用以下三种结构来构建集合：

1. 数组
2. 结构体
3. 动态内存分配

数组 - 固定大小的集合

数组是C语言中最基础、最原始的“集合”，它是一块连续的内存空间,用于存储相同类型的元素。

特点：

• 大小固定：数组在创建时大小就确定了,不能动态改变。
• 内存连续：所有元素在内存中是连续存放的，这使得随机访问（通过索引）非常快（时间复杂度 O(1)）。
• 插入/删除慢：在数组中间插入或删除一个元素，需要移动大量元素，效率较低（时间复杂度 O(n)）。

示例：一个简单的整数数组

#include <stdio.h>
int main() {
    // 一个包含5个整数的数组
    int numbers[5] = {10, 20, 30, 40, 50};
    // 访问元素
    printf("第一个元素: %d\n", numbers[0]); // 输出 10
    // 遍历数组
    for (int i = 0; i < 5; i++) {
        printf("%d ", numbers[i]);
    }
    printf("\n");
    return 0;
}

局限性： 因为大小固定,数组不适合元素数量不确定或频繁增删的场景。

动态数组 - 可变大小的集合

为了克服数组大小固定的缺点，我们可以使用动态内存分配（malloc, calloc, realloc, free）来创建一个“动态数组”，它本质上是一个指向内存块的指针，当空间不够时，我们可以重新分配一块更大的内存,并将旧数据复制过去。

特点：

• 大小可变：可以根据需要动态调整大小。
• 底层是数组：仍然保持了数组内存连续的优点,随机访问快。
• 扩容有成本：每次扩容都需要重新分配内存和数据拷贝,这是一个相对耗时的操作。

示例：一个简单的动态数组实现

#include <stdio.h>
#include <stdlib.h>
// 定义一个动态数组结构体
typedef struct {
    int *data;      // 指向存储数据的数组
    size_t size;    // 当前元素个数
    size_t capacity; // 当前分配的总容量
} DynamicArray;
// 初始化动态数组
void initDynamicArray(DynamicArray *arr, size_t initialCapacity) {
    arr->data = (int *)malloc(initialCapacity * sizeof(int));
    if (arr->data == NULL) {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    arr->size = 0;
    arr->capacity = initialCapacity;
}
// 向动态数组添加元素
void pushBack(DynamicArray *arr, int value) {
    // 检查是否需要扩容
    if (arr->size >= arr->capacity) {
        arr->capacity *= 2; // 容量翻倍
        arr->data = (int *)realloc(arr->data, arr->capacity * sizeof(int));
        if (arr->data == NULL) {
            fprintf(stderr, "内存重新分配失败\n");
            exit(EXIT_FAILURE);
        }
    }
    arr->data[arr->size++] = value; // 添加元素并增加size
}
// 释放动态数组内存
void freeDynamicArray(DynamicArray *arr) {
    free(arr->data);
    arr->data = NULL;
    arr->size = arr->capacity = 0;
}
int main() {
    DynamicArray myArray;
    initDynamicArray(&myArray, 2); // 初始容量为2
    pushBack(&myArray, 10);
    pushBack(&myArray, 20);
    pushBack(&myArray, 30); // 添加第三个元素时会触发扩容
    printf("动态数组内容: ");
    for (size_t i = 0; i < myArray.size; i++) {
        printf("%d ", myArray.data[i]);
    }
    printf("\n");
    printf("当前大小: %zu, 当前容量: %zu\n", myArray.size, myArray.capacity);
    freeDynamicArray(&myArray);
    return 0;
}

这个 DynamicArray 就是一个非常典型的集合实现，类似于 C++ 的 std::vector 或 Java 的 ArrayList。

链表 - 高效增删的集合

链表是另一种基础数据结构，它通过“节点”来存储数据,每个节点包含数据和指向下一个节点的指针。

特点：

• 大小动态：不需要预先分配固定大小的内存,增删节点非常方便。
• 内存非连续：节点在内存中可以任意分布,通过指针连接。
• 随机访问慢：要访问第 i 个元素，必须从头节点开始遍历，直到找到该节点（时间复杂度 O(n)）。
• 插入/删除快：只要找到目标位置，插入或删除节点只需要修改几个指针即可（时间复杂度 O(1)，前提是已定位到节点）。

示例：一个简单的单向链表实现

#include <stdio.h>
#include <stdlib.h>
// 定义链表节点
typedef struct Node {
    int data;
    struct Node *next;
} Node;
// 在链表头部插入节点
Node* insertAtHead(Node *head, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = value;
    newNode->next = head;
    return newNode; // 新节点成为新的头节点
}
// 打印链表
void printList(Node *head) {
    Node *current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}
// 释放链表内存
void freeList(Node *head) {
    Node *current = head;
    while (current != NULL) {
        Node *temp = current;
        current = current->next;
        free(temp);
    }
}
int main() {
    Node *head = NULL; // 空链表
    head = insertAtHead(head, 30);
    head = insertAtHead(head, 20);
    head = insertAtHead(head, 10);
    printf("链表内容: ");
    printList(head);
    freeList(head);
    return 0;
}

这个链表就是一种集合,它高效地处理了元素的动态增删。

结构体与哈希表 - 键值对集合

当我们需要一个类似“字典”或“映射”（Map）的集合，即通过一个键来快速查找一个值时，哈希表是最佳选择，哈希表的核心就是结构体和指针的结合。

原理：

1. 定义一个结构体 HashMap，它包含一个指向“桶”（Bucket）数组的指针。
2. 每个“桶”本身也是一个结构体或链表,用于处理哈希冲突。
3. 通过一个哈希函数将键转换成一个数组索引,然后存储或查找对应的值。

示例：一个非常简化的哈希表思路

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 键值对
typedef struct {
    char *key;
    int value;
} KeyValuePair;
// 哈希表桶（这里用链表解决冲突）
typedef struct Bucket {
    KeyValuePair *pair;
    struct Bucket *next;
} Bucket;
// 哈希表
typedef struct {
    Bucket **buckets; // 桶数组
    int size;         // 桶的数量
} HashMap;
// 哈希函数 (简单示例，实际应更复杂)
unsigned int hash(const char *key, int size) {
    unsigned long hash = 5381;
    int c;
    while ((c = *key++)) {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    }
    return hash % size;
}
// ... (省略了 put, get, free 等函数的实现，这通常是一个比较复杂的工程)
int main() {
    // 一个哈希表的实现远比这复杂，这里只展示其结构思想
    // HashMap *myMap = createHashMap(10);
    // put(myMap, "apple", 100);
    // int price = get(myMap, "apple"); // price 应该是 100
    // freeHashMap(myMap);
    printf("哈希表示例：实际实现是一个完整的工程，\n");
    return 0;
}

这个思路展示了如何用C语言的结构体和指针构建一个复杂的集合。

总结与对比

在C语言中，“集合”不是一个内置的概念，而是一个设计和实现的问题，你需要根据你的具体需求（是需要快速查找？还是频繁增删？）来选择合适的基础数据结构（数组、结构体、指针）并组合实现。

• 如果你需要快速随机访问，并且元素数量变化不频繁，数组是好的选择。
• 如果你需要频繁在尾部增删元素，动态数组是最佳选择。
• 如果你需要频繁在任何位置增删元素，并且不关心随机访问速度，链表更合适。
• 如果你需要通过键快速查找值，那么你需要自己实现一个哈希表。

对于大型项目，直接从零实现这些数据结构既耗时又容易出错,开发者通常会使用成熟的第三方库，

• GLib: 提供了非常完整的GObject系统，包括 GArray, GList, GHashTable 等丰富的数据结构。
• apr (Apache Portable Runtime): Apache项目提供的跨平台库,也包含了很多数据结构实现。
• 其他轻量级库: 如 uthash (一个单文件哈希表库), stlport (C++ STL在C上的移植) 等。