【学习】C语言项目实战：从算法到系统编程

C语言系统学习系列 - 第8篇（完结篇）
通过完整的项目实战，将前面学到的所有知识融会贯通，从算法实现到系统编程，构建真正实用的程序。

前言

经过前面七篇文章的系统学习，您已经掌握了C语言的各个方面：从基础语法到高级特性，从内存管理到文件操作。现在是时候将这些知识整合起来，通过实际项目来巩固和提升编程技能。

项目实战的重要性

理论知识只有通过实践才能真正掌握：

• 算法实现：将经典算法用C语言实现，理解算法的本质
• 数据结构：构建高效的数据结构，解决实际问题
• 系统编程：编写与操作系统交互的程序
• 工程实践：学会项目组织、调试、优化等工程技能

本文项目概览：

• 数据结构库：实现常用数据结构
• 算法集合：经典算法的C语言实现
• 文本处理工具：实用的命令行工具
• 简单操作系统内核：系统编程入门

上一篇：高级特性与现代编程

一、数据结构库项目

（一）通用数据结构库设计

1. 动态数组（Vector）实现

// vector.h - 动态数组头文件
#ifndef VECTOR_H
#define VECTOR_H

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

typedef struct {
    void* data;         // 数据指针
    size_t size;        // 当前元素数量
    size_t capacity;    // 容量
    size_t element_size; // 元素大小
} Vector;

// 基本操作
Vector* vector_create(size_t element_size);
void vector_destroy(Vector* vec);
bool vector_push_back(Vector* vec, const void* element);
bool vector_pop_back(Vector* vec, void* element);
void* vector_get(const Vector* vec, size_t index);
bool vector_set(Vector* vec, size_t index, const void* element);
size_t vector_size(const Vector* vec);
bool vector_empty(const Vector* vec);
void vector_clear(Vector* vec);
bool vector_reserve(Vector* vec, size_t new_capacity);

#endif // VECTOR_H

// vector.c - 动态数组实现
#include "vector.h"
#include <stdlib.h>
#include <string.h>
#include <assert.h>

Vector* vector_create(size_t element_size) {
    if (element_size == 0) return NULL;
    
    Vector* vec = malloc(sizeof(Vector));
    if (vec == NULL) return NULL;
    
    vec->data = NULL;
    vec->size = 0;
    vec->capacity = 0;
    vec->element_size = element_size;
    
    return vec;
}

void vector_destroy(Vector* vec) {
    if (vec != NULL) {
        free(vec->data);
        free(vec);
    }
}

static bool vector_grow(Vector* vec) {
    size_t new_capacity = vec->capacity == 0 ? 4 : vec->capacity * 2;
    return vector_reserve(vec, new_capacity);
}

bool vector_reserve(Vector* vec, size_t new_capacity) {
    if (vec == NULL || new_capacity <= vec->capacity) {
        return false;
    }
    
    void* new_data = realloc(vec->data, new_capacity * vec->element_size);
    if (new_data == NULL) {
        return false;
    }
    
    vec->data = new_data;
    vec->capacity = new_capacity;
    return true;
}

bool vector_push_back(Vector* vec, const void* element) {
    if (vec == NULL || element == NULL) {
        return false;
    }
    
    if (vec->size >= vec->capacity) {
        if (!vector_grow(vec)) {
            return false;
        }
    }
    
    char* data_ptr = (char*)vec->data;
    memcpy(data_ptr + vec->size * vec->element_size, element, vec->element_size);
    vec->size++;
    
    return true;
}

bool vector_pop_back(Vector* vec, void* element) {
    if (vec == NULL || vec->size == 0) {
        return false;
    }
    
    vec->size--;
    if (element != NULL) {
        char* data_ptr = (char*)vec->data;
        memcpy(element, data_ptr + vec->size * vec->element_size, vec->element_size);
    }
    
    return true;
}

void* vector_get(const Vector* vec, size_t index) {
    if (vec == NULL || index >= vec->size) {
        return NULL;
    }
    
    char* data_ptr = (char*)vec->data;
    return data_ptr + index * vec->element_size;
}

bool vector_set(Vector* vec, size_t index, const void* element) {
    if (vec == NULL || element == NULL || index >= vec->size) {
        return false;
    }
    
    char* data_ptr = (char*)vec->data;
    memcpy(data_ptr + index * vec->element_size, element, vec->element_size);
    
    return true;
}

size_t vector_size(const Vector* vec) {
    return vec ? vec->size : 0;
}

bool vector_empty(const Vector* vec) {
    return vec ? vec->size == 0 : true;
}

void vector_clear(Vector* vec) {
    if (vec != NULL) {
        vec->size = 0;
    }
}

2. 链表实现

// linked_list.h - 链表头文件
#ifndef LINKED_LIST_H
#define LINKED_LIST_H

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

typedef struct ListNode {
    void* data;
    struct ListNode* next;
} ListNode;

typedef struct {
    ListNode* head;
    ListNode* tail;
    size_t size;
    size_t element_size;
} LinkedList;

// 基本操作
LinkedList* list_create(size_t element_size);
void list_destroy(LinkedList* list);
bool list_push_front(LinkedList* list, const void* data);
bool list_push_back(LinkedList* list, const void* data);
bool list_pop_front(LinkedList* list, void* data);
bool list_pop_back(LinkedList* list, void* data);
ListNode* list_find(const LinkedList* list, const void* data, 
                   int (*compare)(const void*, const void*));
bool list_remove(LinkedList* list, const void* data,
                int (*compare)(const void*, const void*));
size_t list_size(const LinkedList* list);
bool list_empty(const LinkedList* list);
void list_clear(LinkedList* list);

// 迭代器
typedef struct {
    ListNode* current;
} ListIterator;

ListIterator list_begin(const LinkedList* list);
bool list_iterator_valid(const ListIterator* iter);
void list_iterator_next(ListIterator* iter);
void* list_iterator_data(const ListIterator* iter);

#endif // LINKED_LIST_H

// linked_list.c - 链表实现
#include "linked_list.h"
#include <stdlib.h>
#include <string.h>

static ListNode* create_node(size_t element_size, const void* data) {
    ListNode* node = malloc(sizeof(ListNode));
    if (node == NULL) return NULL;
    
    node->data = malloc(element_size);
    if (node->data == NULL) {
        free(node);
        return NULL;
    }
    
    memcpy(node->data, data, element_size);
    node->next = NULL;
    
    return node;
}

static void destroy_node(ListNode* node) {
    if (node != NULL) {
        free(node->data);
        free(node);
    }
}

LinkedList* list_create(size_t element_size) {
    if (element_size == 0) return NULL;
    
    LinkedList* list = malloc(sizeof(LinkedList));
    if (list == NULL) return NULL;
    
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
    list->element_size = element_size;
    
    return list;
}

void list_destroy(LinkedList* list) {
    if (list != NULL) {
        list_clear(list);
        free(list);
    }
}

bool list_push_front(LinkedList* list, const void* data) {
    if (list == NULL || data == NULL) return false;
    
    ListNode* new_node = create_node(list->element_size, data);
    if (new_node == NULL) return false;
    
    new_node->next = list->head;
    list->head = new_node;
    
    if (list->tail == NULL) {
        list->tail = new_node;
    }
    
    list->size++;
    return true;
}

bool list_push_back(LinkedList* list, const void* data) {
    if (list == NULL || data == NULL) return false;
    
    ListNode* new_node = create_node(list->element_size, data);
    if (new_node == NULL) return false;
    
    if (list->tail == NULL) {
        list->head = list->tail = new_node;
    } else {
        list->tail->next = new_node;
        list->tail = new_node;
    }
    
    list->size++;
    return true;
}

bool list_pop_front(LinkedList* list, void* data) {
    if (list == NULL || list->head == NULL) return false;
    
    ListNode* to_remove = list->head;
    
    if (data != NULL) {
        memcpy(data, to_remove->data, list->element_size);
    }
    
    list->head = list->head->next;
    if (list->head == NULL) {
        list->tail = NULL;
    }
    
    destroy_node(to_remove);
    list->size--;
    
    return true;
}

void list_clear(LinkedList* list) {
    if (list == NULL) return;
    
    ListNode* current = list->head;
    while (current != NULL) {
        ListNode* next = current->next;
        destroy_node(current);
        current = next;
    }
    
    list->head = list->tail = NULL;
    list->size = 0;
}

size_t list_size(const LinkedList* list) {
    return list ? list->size : 0;
}

bool list_empty(const LinkedList* list) {
    return list ? list->size == 0 : true;
}

// 迭代器实现
ListIterator list_begin(const LinkedList* list) {
    ListIterator iter = {list ? list->head : NULL};
    return iter;
}

bool list_iterator_valid(const ListIterator* iter) {
    return iter && iter->current != NULL;
}

void list_iterator_next(ListIterator* iter) {
    if (iter && iter->current) {
        iter->current = iter->current->next;
    }
}

void* list_iterator_data(const ListIterator* iter) {
    return (iter && iter->current) ? iter->current->data : NULL;
}

3. 哈希表实现

// hash_table.h - 哈希表头文件
#ifndef HASH_TABLE_H
#define HASH_TABLE_H

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

typedef struct HashEntry {
    void* key;
    void* value;
    struct HashEntry* next;
} HashEntry;

typedef struct {
    HashEntry** buckets;
    size_t bucket_count;
    size_t size;
    size_t key_size;
    size_t value_size;
    size_t (*hash_func)(const void* key, size_t key_size);
    int (*compare_func)(const void* key1, const void* key2, size_t key_size);
} HashTable;

// 基本操作
HashTable* hash_table_create(size_t key_size, size_t value_size,
                            size_t (*hash_func)(const void*, size_t),
                            int (*compare_func)(const void*, const void*, size_t));
void hash_table_destroy(HashTable* table);
bool hash_table_insert(HashTable* table, const void* key, const void* value);
bool hash_table_get(const HashTable* table, const void* key, void* value);
bool hash_table_remove(HashTable* table, const void* key);
bool hash_table_contains(const HashTable* table, const void* key);
size_t hash_table_size(const HashTable* table);
bool hash_table_empty(const HashTable* table);

// 默认哈希函数
size_t hash_string(const void* key, size_t key_size);
size_t hash_int(const void* key, size_t key_size);

// 默认比较函数
int compare_string(const void* key1, const void* key2, size_t key_size);
int compare_int(const void* key1, const void* key2, size_t key_size);

#endif // HASH_TABLE_H

// hash_table.c - 哈希表实现
#include "hash_table.h"
#include <stdlib.h>
#include <string.h>

#define DEFAULT_BUCKET_COUNT 16
#define LOAD_FACTOR_THRESHOLD 0.75

static HashEntry* create_entry(size_t key_size, size_t value_size,
                              const void* key, const void* value) {
    HashEntry* entry = malloc(sizeof(HashEntry));
    if (entry == NULL) return NULL;
    
    entry->key = malloc(key_size);
    entry->value = malloc(value_size);
    
    if (entry->key == NULL || entry->value == NULL) {
        free(entry->key);
        free(entry->value);
        free(entry);
        return NULL;
    }
    
    memcpy(entry->key, key, key_size);
    memcpy(entry->value, value, value_size);
    entry->next = NULL;
    
    return entry;
}

static void destroy_entry(HashEntry* entry) {
    if (entry != NULL) {
        free(entry->key);
        free(entry->value);
        free(entry);
    }
}

HashTable* hash_table_create(size_t key_size, size_t value_size,
                            size_t (*hash_func)(const void*, size_t),
                            int (*compare_func)(const void*, const void*, size_t)) {
    if (key_size == 0 || value_size == 0 || hash_func == NULL || compare_func == NULL) {
        return NULL;
    }
    
    HashTable* table = malloc(sizeof(HashTable));
    if (table == NULL) return NULL;
    
    table->buckets = calloc(DEFAULT_BUCKET_COUNT, sizeof(HashEntry*));
    if (table->buckets == NULL) {
        free(table);
        return NULL;
    }
    
    table->bucket_count = DEFAULT_BUCKET_COUNT;
    table->size = 0;
    table->key_size = key_size;
    table->value_size = value_size;
    table->hash_func = hash_func;
    table->compare_func = compare_func;
    
    return table;
}

void hash_table_destroy(HashTable* table) {
    if (table == NULL) return;
    
    for (size_t i = 0; i < table->bucket_count; i++) {
        HashEntry* entry = table->buckets[i];
        while (entry != NULL) {
            HashEntry* next = entry->next;
            destroy_entry(entry);
            entry = next;
        }
    }
    
    free(table->buckets);
    free(table);
}

bool hash_table_insert(HashTable* table, const void* key, const void* value) {
    if (table == NULL || key == NULL || value == NULL) return false;
    
    size_t hash = table->hash_func(key, table->key_size);
    size_t index = hash % table->bucket_count;
    
    // 检查是否已存在
    HashEntry* entry = table->buckets[index];
    while (entry != NULL) {
        if (table->compare_func(entry->key, key, table->key_size) == 0) {
            // 更新现有值
            memcpy(entry->value, value, table->value_size);
            return true;
        }
        entry = entry->next;
    }
    
    // 创建新条目
    HashEntry* new_entry = create_entry(table->key_size, table->value_size, key, value);
    if (new_entry == NULL) return false;
    
    new_entry->next = table->buckets[index];
    table->buckets[index] = new_entry;
    table->size++;
    
    return true;
}

bool hash_table_get(const HashTable* table, const void* key, void* value) {
    if (table == NULL || key == NULL) return false;
    
    size_t hash = table->hash_func(key, table->key_size);
    size_t index = hash % table->bucket_count;
    
    HashEntry* entry = table->buckets[index];
    while (entry != NULL) {
        if (table->compare_func(entry->key, key, table->key_size) == 0) {
            if (value != NULL) {
                memcpy(value, entry->value, table->value_size);
            }
            return true;
        }
        entry = entry->next;
    }
    
    return false;
}

size_t hash_table_size(const HashTable* table) {
    return table ? table->size : 0;
}

bool hash_table_empty(const HashTable* table) {
    return table ? table->size == 0 : true;
}

// 默认哈希函数实现
size_t hash_string(const void* key, size_t key_size) {
    const char* str = (const char*)key;
    size_t hash = 5381;
    
    for (size_t i = 0; i < key_size && str[i] != '\0'; i++) {
        hash = ((hash << 5) + hash) + str[i];
    }
    
    return hash;
}

size_t hash_int(const void* key, size_t key_size) {
    (void)key_size;  // 未使用参数
    int value = *(const int*)key;
    return (size_t)value;
}

// 默认比较函数实现
int compare_string(const void* key1, const void* key2, size_t key_size) {
    return strncmp((const char*)key1, (const char*)key2, key_size);
}

int compare_int(const void* key1, const void* key2, size_t key_size) {
    (void)key_size;  // 未使用参数
    int a = *(const int*)key1;
    int b = *(const int*)key2;
    return (a > b) - (a < b);
}

（二）数据结构测试程序

// test_data_structures.c - 数据结构测试
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <time.h>
#include "vector.h"
#include "linked_list.h"
#include "hash_table.h"

void test_vector(void) {
    printf("=== 测试动态数组 ===\n");
    
    Vector* vec = vector_create(sizeof(int));
    assert(vec != NULL);
    assert(vector_empty(vec));
    
    // 添加元素
    for (int i = 0; i < 10; i++) {
        assert(vector_push_back(vec, &i));
    }
    
    assert(vector_size(vec) == 10);
    assert(!vector_empty(vec));
    
    // 访问元素
    for (size_t i = 0; i < vector_size(vec); i++) {
        int* value = (int*)vector_get(vec, i);
        assert(value != NULL);
        assert(*value == (int)i);
    }
    
    // 修改元素
    int new_value = 99;
    assert(vector_set(vec, 5, &new_value));
    int* modified = (int*)vector_get(vec, 5);
    assert(*modified == 99);
    
    // 删除元素
    int popped;
    assert(vector_pop_back(vec, &popped));
    assert(popped == 9);
    assert(vector_size(vec) == 9);
    
    printf("动态数组测试通过\n");
    vector_destroy(vec);
}

void test_linked_list(void) {
    printf("\n=== 测试链表 ===\n");
    
    LinkedList* list = list_create(sizeof(int));
    assert(list != NULL);
    assert(list_empty(list));
    
    // 添加元素
    for (int i = 0; i < 5; i++) {
        assert(list_push_back(list, &i));
    }
    
    for (int i = 5; i < 10; i++) {
        assert(list_push_front(list, &i));
    }
    
    assert(list_size(list) == 10);
    
    // 使用迭代器遍历
    printf("链表内容: ");
    ListIterator iter = list_begin(list);
    while (list_iterator_valid(&iter)) {
        int* value = (int*)list_iterator_data(&iter);
        printf("%d ", *value);
        list_iterator_next(&iter);
    }
    printf("\n");
    
    // 删除元素
    int front_value, back_value;
    assert(list_pop_front(list, &front_value));
    assert(list_pop_back(list, &back_value));
    
    printf("删除的元素: 前=%d, 后=%d\n", front_value, back_value);
    assert(list_size(list) == 8);
    
    printf("链表测试通过\n");
    list_destroy(list);
}

void test_hash_table(void) {
    printf("\n=== 测试哈希表 ===\n");
    
    HashTable* table = hash_table_create(sizeof(char*), sizeof(int),
                                        hash_string, compare_string);
    assert(table != NULL);
    assert(hash_table_empty(table));
    
    // 插入键值对
    const char* keys[] = {"apple", "banana", "cherry", "date", "elderberry"};
    int values[] = {1, 2, 3, 4, 5};
    
    for (int i = 0; i < 5; i++) {
        assert(hash_table_insert(table, &keys[i], &values[i]));
    }
    
    assert(hash_table_size(table) == 5);
    
    // 查找值
    for (int i = 0; i < 5; i++) {
        int retrieved_value;
        assert(hash_table_get(table, &keys[i], &retrieved_value));
        assert(retrieved_value == values[i]);
        printf("键 '%s' -> 值 %d\n", keys[i], retrieved_value);
    }
    
    // 测试不存在的键
    const char* nonexistent = "grape";
    assert(!hash_table_contains(table, &nonexistent));
    
    printf("哈希表测试通过\n");
    hash_table_destroy(table);
}

void performance_test(void) {
    printf("\n=== 性能测试 ===\n");
    
    const int test_size = 100000;
    clock_t start, end;
    
    // Vector性能测试
    start = clock();
    Vector* vec = vector_create(sizeof(int));
    for (int i = 0; i < test_size; i++) {
        vector_push_back(vec, &i);
    }
    end = clock();
    
    double vector_time = ((double)(end - start)) / CLOCKS_PER_SEC;
    printf("Vector插入%d个元素耗时: %.4f秒\n", test_size, vector_time);
    vector_destroy(vec);
    
    // LinkedList性能测试
    start = clock();
    LinkedList* list = list_create(sizeof(int));
    for (int i = 0; i < test_size; i++) {
        list_push_back(list, &i);
    }
    end = clock();
    
    double list_time = ((double)(end - start)) / CLOCKS_PER_SEC;
    printf("LinkedList插入%d个元素耗时: %.4f秒\n", test_size, list_time);
    list_destroy(list);
    
    printf("Vector比LinkedList快 %.2f倍\n", list_time / vector_time);
}

int main(void) {
    printf("数据结构库测试程序\n");
    printf("==================\n");
    
    test_vector();
    test_linked_list();
    test_hash_table();
    performance_test();
    
    printf("\n所有测试通过！\n");
    return 0;
}

二、算法实现项目

（一）排序算法集合

1. 经典排序算法实现

// sorting.h - 排序算法头文件
#ifndef SORTING_H
#define SORTING_H

#include <stddef.h>

// 排序算法函数指针类型
typedef void (*sort_func_t)(void* array, size_t count, size_t element_size,
                           int (*compare)(const void*, const void*));

// 排序算法
void bubble_sort(void* array, size_t count, size_t element_size,
                int (*compare)(const void*, const void*));
void selection_sort(void* array, size_t count, size_t element_size,
                   int (*compare)(const void*, const void*));
void insertion_sort(void* array, size_t count, size_t element_size,
                   int (*compare)(const void*, const void*));
void merge_sort(void* array, size_t count, size_t element_size,
               int (*compare)(const void*, const void*));
void quick_sort(void* array, size_t count, size_t element_size,
               int (*compare)(const void*, const void*));
void heap_sort(void* array, size_t count, size_t element_size,
              int (*compare)(const void*, const void*));

// 搜索算法
int linear_search(const void* array, size_t count, size_t element_size,
                 const void* key, int (*compare)(const void*, const void*));
int binary_search(const void* array, size_t count, size_t element_size,
                 const void* key, int (*compare)(const void*, const void*));

// 工具函数
void swap_elements(void* a, void* b, size_t element_size);
int compare_int(const void* a, const void* b);
int compare_double(const void* a, const void* b);
int compare_string(const void* a, const void* b);

// 性能测试
void benchmark_sorting_algorithms(void);

#endif // SORTING_H

// sorting.c - 排序算法实现
#include "sorting.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <time.h>

void swap_elements(void* a, void* b, size_t element_size) {
    if (a == b) return;
    
    char* temp = malloc(element_size);
    if (temp == NULL) return;
    
    memcpy(temp, a, element_size);
    memcpy(a, b, element_size);
    memcpy(b, temp, element_size);
    
    free(temp);
}

// 冒泡排序
void bubble_sort(void* array, size_t count, size_t element_size,
                int (*compare)(const void*, const void*)) {
    if (array == NULL || count <= 1 || compare == NULL) return;
    
    char* arr = (char*)array;
    
    for (size_t i = 0; i < count - 1; i++) {
        bool swapped = false;
        for (size_t j = 0; j < count - 1 - i; j++) {
            void* elem1 = arr + j * element_size;
            void* elem2 = arr + (j + 1) * element_size;
            
            if (compare(elem1, elem2) > 0) {
                swap_elements(elem1, elem2, element_size);
                swapped = true;
            }
        }
        if (!swapped) break;  // 优化：如果没有交换，数组已排序
    }
}

// 选择排序
void selection_sort(void* array, size_t count, size_t element_size,
                   int (*compare)(const void*, const void*)) {
    if (array == NULL || count <= 1 || compare == NULL) return;
    
    char* arr = (char*)array;
    
    for (size_t i = 0; i < count - 1; i++) {
        size_t min_idx = i;
        
        for (size_t j = i + 1; j < count; j++) {
            void* elem_j = arr + j * element_size;
            void* elem_min = arr + min_idx * element_size;
            
            if (compare(elem_j, elem_min) < 0) {
                min_idx = j;
            }
        }
        
        if (min_idx != i) {
            void* elem_i = arr + i * element_size;
            void* elem_min = arr + min_idx * element_size;
            swap_elements(elem_i, elem_min, element_size);
        }
    }
}

// 插入排序
void insertion_sort(void* array, size_t count, size_t element_size,
                   int (*compare)(const void*, const void*)) {
    if (array == NULL || count <= 1 || compare == NULL) return;
    
    char* arr = (char*)array;
    char* temp = malloc(element_size);
    if (temp == NULL) return;
    
    for (size_t i = 1; i < count; i++) {
        memcpy(temp, arr + i * element_size, element_size);
        
        size_t j = i;
        while (j > 0 && compare(arr + (j - 1) * element_size, temp) > 0) {
            memcpy(arr + j * element_size, arr + (j - 1) * element_size, element_size);
            j--;
        }
        
        memcpy(arr + j * element_size, temp, element_size);
    }
    
    free(temp);
}

// 归并排序辅助函数
static void merge(void* array, size_t left, size_t mid, size_t right,
                 size_t element_size, int (*compare)(const void*, const void*)) {
    char* arr = (char*)array;
    size_t left_size = mid - left + 1;
    size_t right_size = right - mid;
    
    char* left_array = malloc(left_size * element_size);
    char* right_array = malloc(right_size * element_size);
    
    if (left_array == NULL || right_array == NULL) {
        free(left_array);
        free(right_array);
        return;
    }
    
    memcpy(left_array, arr + left * element_size, left_size * element_size);
    memcpy(right_array, arr + (mid + 1) * element_size, right_size * element_size);
    
    size_t i = 0, j = 0, k = left;
    
    while (i < left_size && j < right_size) {
        void* left_elem = left_array + i * element_size;
        void* right_elem = right_array + j * element_size;
        
        if (compare(left_elem, right_elem) <= 0) {
            memcpy(arr + k * element_size, left_elem, element_size);
            i++;
        } else {
            memcpy(arr + k * element_size, right_elem, element_size);
            j++;
        }
        k++;
    }
    
    while (i < left_size) {
        memcpy(arr + k * element_size, left_array + i * element_size, element_size);
        i++;
        k++;
    }
    
    while (j < right_size) {
        memcpy(arr + k * element_size, right_array + j * element_size, element_size);
        j++;
        k++;
    }
    
    free(left_array);
    free(right_array);
}

static void merge_sort_recursive(void* array, size_t left, size_t right,
                                size_t element_size, int (*compare)(const void*, const void*)) {
    if (left < right) {
        size_t mid = left + (right - left) / 2;
        
        merge_sort_recursive(array, left, mid, element_size, compare);
        merge_sort_recursive(array, mid + 1, right, element_size, compare);
        merge(array, left, mid, right, element_size, compare);
    }
}

// 归并排序
void merge_sort(void* array, size_t count, size_t element_size,
               int (*compare)(const void*, const void*)) {
    if (array == NULL || count <= 1 || compare == NULL) return;
    
    merge_sort_recursive(array, 0, count - 1, element_size, compare);
}

// 比较函数实现
int compare_int(const void* a, const void* b) {
    int ia = *(const int*)a;
    int ib = *(const int*)b;
    return (ia > ib) - (ia < ib);
}

int compare_double(const void* a, const void* b) {
    double da = *(const double*)a;
    double db = *(const double*)b;
    return (da > db) - (da < db);
}

int compare_string(const void* a, const void* b) {
    return strcmp(*(const char**)a, *(const char**)b);
}

// 线性搜索
int linear_search(const void* array, size_t count, size_t element_size,
                 const void* key, int (*compare)(const void*, const void*)) {
    if (array == NULL || key == NULL || compare == NULL) return -1;
    
    const char* arr = (const char*)array;
    
    for (size_t i = 0; i < count; i++) {
        if (compare(arr + i * element_size, key) == 0) {
            return (int)i;
        }
    }
    
    return -1;
}

// 二分搜索
int binary_search(const void* array, size_t count, size_t element_size,
                 const void* key, int (*compare)(const void*, const void*)) {
    if (array == NULL || key == NULL || compare == NULL) return -1;
    
    const char* arr = (const char*)array;
    int left = 0;
    int right = (int)count - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        const void* mid_elem = arr + mid * element_size;
        
        int cmp = compare(mid_elem, key);
        if (cmp == 0) {
            return mid;
        } else if (cmp < 0) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

2. 算法性能测试

// algorithm_benchmark.c - 算法性能测试
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <assert.h>
#include "sorting.h"

typedef struct {
    const char* name;
    sort_func_t function;
} SortAlgorithm;

// 生成测试数据
int* generate_random_array(size_t count, int max_value) {
    int* array = malloc(count * sizeof(int));
    if (array == NULL) return NULL;
    
    for (size_t i = 0; i < count; i++) {
        array[i] = rand() % max_value;
    }
    
    return array;
}

int* generate_sorted_array(size_t count) {
    int* array = malloc(count * sizeof(int));
    if (array == NULL) return NULL;
    
    for (size_t i = 0; i < count; i++) {
        array[i] = (int)i;
    }
    
    return array;
}

int* generate_reverse_sorted_array(size_t count) {
    int* array = malloc(count * sizeof(int));
    if (array == NULL) return NULL;
    
    for (size_t i = 0; i < count; i++) {
        array[i] = (int)(count - 1 - i);
    }
    
    return array;
}

// 验证数组是否已排序
bool is_sorted(const int* array, size_t count) {
    for (size_t i = 1; i < count; i++) {
        if (array[i] < array[i - 1]) {
            return false;
        }
    }
    return true;
}

// 测试单个排序算法
double test_sort_algorithm(sort_func_t sort_func, int* array, size_t count) {
    clock_t start = clock();
    sort_func(array, count, sizeof(int), compare_int);
    clock_t end = clock();
    
    return ((double)(end - start)) / CLOCKS_PER_SEC;
}

void benchmark_sorting_algorithms(void) {
    printf("=== 排序算法性能测试 ===\n");
    
    SortAlgorithm algorithms[] = {
        {"冒泡排序", bubble_sort},
        {"选择排序", selection_sort},
        {"插入排序", insertion_sort},
        {"归并排序", merge_sort},
        {"快速排序", quick_sort},
        {"堆排序", heap_sort}
    };
    
    size_t algorithm_count = sizeof(algorithms) / sizeof(algorithms[0]);
    size_t test_sizes[] = {1000, 5000, 10000};
    size_t size_count = sizeof(test_sizes) / sizeof(test_sizes[0]);
    
    srand((unsigned int)time(NULL));
    
    for (size_t s = 0; s < size_count; s++) {
        size_t test_size = test_sizes[s];
        printf("\n测试数据大小: %zu\n", test_size);
        printf("%-12s %-12s %-12s %-12s\n", "算法", "随机数据", "已排序", "逆序");
        printf("--------------------------------------------------------\n");
        
        for (size_t a = 0; a < algorithm_count; a++) {
            // 跳过大数据量的慢速算法
            if (test_size > 5000 && (a == 0 || a == 1)) {
                printf("%-12s %-12s %-12s %-12s\n", 
                       algorithms[a].name, "跳过", "跳过", "跳过");
                continue;
            }
            
            double times[3];
            
            // 测试随机数据
            int* random_array = generate_random_array(test_size, 10000);
            times[0] = test_sort_algorithm(algorithms[a].function, random_array, test_size);
            assert(is_sorted(random_array, test_size));
            free(random_array);
            
            // 测试已排序数据
            int* sorted_array = generate_sorted_array(test_size);
            times[1] = test_sort_algorithm(algorithms[a].function, sorted_array, test_size);
            assert(is_sorted(sorted_array, test_size));
            free(sorted_array);
            
            // 测试逆序数据
            int* reverse_array = generate_reverse_sorted_array(test_size);
            times[2] = test_sort_algorithm(algorithms[a].function, reverse_array, test_size);
            assert(is_sorted(reverse_array, test_size));
            free(reverse_array);
            
            printf("%-12s %-12.4f %-12.4f %-12.4f\n", 
                   algorithms[a].name, times[0], times[1], times[2]);
        }
    }
}

void test_search_algorithms(void) {
    printf("\n=== 搜索算法测试 ===\n");
    
    const size_t test_size = 100000;
    int* array = generate_sorted_array(test_size);
    
    // 测试线性搜索
    clock_t start = clock();
    int linear_result = linear_search(array, test_size, sizeof(int), 
                                     &(int){50000}, compare_int);
    clock_t end = clock();
    double linear_time = ((double)(end - start)) / CLOCKS_PER_SEC;
    
    // 测试二分搜索
    start = clock();
    int binary_result = binary_search(array, test_size, sizeof(int), 
                                     &(int){50000}, compare_int);
    end = clock();
    double binary_time = ((double)(end - start)) / CLOCKS_PER_SEC;
    
    printf("搜索目标: 50000\n");
    printf("线性搜索: 找到位置 %d, 耗时 %.6f 秒\n", linear_result, linear_time);
    printf("二分搜索: 找到位置 %d, 耗时 %.6f 秒\n", binary_result, binary_time);
    printf("二分搜索比线性搜索快 %.0f 倍\n", linear_time / binary_time);
    
    free(array);
}

int main(void) {
    printf("算法性能测试程序\n");
    printf("================\n");
    
    benchmark_sorting_algorithms();
    test_search_algorithms();
    
    printf("\n测试完成！\n");
    return 0;
}

三、文本处理工具项目

（一）命令行文本分析器

// text_analyzer.c - 文本分析工具
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>

#define MAX_WORD_LENGTH 100
#define MAX_WORDS 50000

typedef struct {
    char word[MAX_WORD_LENGTH];
    int frequency;
} WordFreq;

typedef struct {
    char* content;
    size_t length;
    int char_count;
    int word_count;
    int line_count;
    int sentence_count;
    WordFreq* words;
    int unique_words;
} TextStats;

// 读取文件内容
char* read_file(const char* filename, size_t* size) {
    FILE* file = fopen(filename, "r");
    if (file == NULL) {
        fprintf(stderr, "错误: 无法打开文件 '%s'\n", filename);
        return NULL;
    }
    
    fseek(file, 0, SEEK_END);
    long file_size = ftell(file);
    fseek(file, 0, SEEK_SET);
    
    if (file_size < 0) {
        fprintf(stderr, "错误: 无法获取文件大小\n");
        fclose(file);
        return NULL;
    }
    
    char* content = malloc(file_size + 1);
    if (content == NULL) {
        fprintf(stderr, "错误: 内存分配失败\n");
        fclose(file);
        return NULL;
    }
    
    size_t bytes_read = fread(content, 1, file_size, file);
    content[bytes_read] = '\0';
    
    fclose(file);
    *size = bytes_read;
    return content;
}

// 标准化单词（转小写，去除标点）
void normalize_word(char* word) {
    int write_pos = 0;
    for (int i = 0; word[i] != '\0'; i++) {
        if (isalnum(word[i])) {
            word[write_pos++] = tolower(word[i]);
        }
    }
    word[write_pos] = '\0';
}

// 添加或更新词频
void add_word(TextStats* stats, const char* word) {
    if (strlen(word) == 0) return;
    
    // 查找是否已存在
    for (int i = 0; i < stats->unique_words; i++) {
        if (strcmp(stats->words[i].word, word) == 0) {
            stats->words[i].frequency++;
            return;
        }
    }
    
    // 添加新单词
    if (stats->unique_words < MAX_WORDS) {
        strncpy(stats->words[stats->unique_words].word, word, MAX_WORD_LENGTH - 1);
        stats->words[stats->unique_words].word[MAX_WORD_LENGTH - 1] = '\0';
        stats->words[stats->unique_words].frequency = 1;
        stats->unique_words++;
    }
}

// 分析文本
TextStats* analyze_text(const char* content, size_t length) {
    TextStats* stats = malloc(sizeof(TextStats));
    if (stats == NULL) return NULL;
    
    stats->content = malloc(length + 1);
    if (stats->content == NULL) {
        free(stats);
        return NULL;
    }
    
    stats->words = malloc(MAX_WORDS * sizeof(WordFreq));
    if (stats->words == NULL) {
        free(stats->content);
        free(stats);
        return NULL;
    }
    
    strcpy(stats->content, content);
    stats->length = length;
    stats->char_count = 0;
    stats->word_count = 0;
    stats->line_count = 0;
    stats->sentence_count = 0;
    stats->unique_words = 0;
    
    char current_word[MAX_WORD_LENGTH] = {0};
    int word_pos = 0;
    bool in_word = false;
    
    for (size_t i = 0; i <= length; i++) {
        char c = (i < length) ? content[i] : '\0';
        
        // 字符计数
        if (i < length && !isspace(c)) {
            stats->char_count++;
        }
        
        // 行计数
        if (c == '\n') {
            stats->line_count++;
        }
        
        // 句子计数
        if (c == '.' || c == '!' || c == '?') {
            stats->sentence_count++;
        }
        
        // 单词处理
        if (isalnum(c) && word_pos < MAX_WORD_LENGTH - 1) {
            current_word[word_pos++] = c;
            in_word = true;
        } else {
            if (in_word) {
                current_word[word_pos] = '\0';
                normalize_word(current_word);
                
                if (strlen(current_word) > 0) {
                    add_word(stats, current_word);
                    stats->word_count++;
                }
                
                word_pos = 0;
                in_word = false;
            }
        }
    }
    
    // 如果文本不以换行符结尾，行数加1
    if (length > 0 && content[length - 1] != '\n') {
        stats->line_count++;
    }
    
    return stats;
}

// 词频排序比较函数
int compare_word_freq(const void* a, const void* b) {
    const WordFreq* wa = (const WordFreq*)a;
    const WordFreq* wb = (const WordFreq*)b;
    
    if (wa->frequency != wb->frequency) {
        return wb->frequency - wa->frequency;  // 降序
    }
    
    return strcmp(wa->word, wb->word);  // 字母顺序
}

// 打印统计结果
void print_statistics(const TextStats* stats, bool show_words, int top_words) {
    printf("=== 文本统计结果 ===\n");
    printf("字符数: %d\n", stats->char_count);
    printf("单词数: %d\n", stats->word_count);
    printf("行数: %d\n", stats->line_count);
    printf("句子数: %d\n", stats->sentence_count);
    printf("唯一单词数: %d\n", stats->unique_words);
    
    if (stats->word_count > 0) {
        printf("平均单词长度: %.2f\n", 
               (double)stats->char_count / stats->word_count);
    }
    
    if (show_words && stats->unique_words > 0) {
        // 复制并排序词频数据
        WordFreq* sorted_words = malloc(stats->unique_words * sizeof(WordFreq));
        if (sorted_words != NULL) {
            memcpy(sorted_words, stats->words, stats->unique_words * sizeof(WordFreq));
            qsort(sorted_words, stats->unique_words, sizeof(WordFreq), compare_word_freq);
            
            printf("\n=== 词频统计 (前%d个) ===\n", top_words);
            int display_count = (stats->unique_words < top_words) ? 
                               stats->unique_words : top_words;
            
            for (int i = 0; i < display_count; i++) {
                printf("%3d. %-20s %d次\n", 
                       i + 1, sorted_words[i].word, sorted_words[i].frequency);
            }
            
            free(sorted_words);
        }
    }
}

// 释放统计数据
void free_text_stats(TextStats* stats) {
    if (stats != NULL) {
        free(stats->content);
        free(stats->words);
        free(stats);
    }
}

// 显示帮助信息
void show_help(const char* program_name) {
    printf("用法: %s [选项] <文件名>\n", program_name);
    printf("选项:\n");
    printf("  -w, --words     显示词频统计\n");
    printf("  -t, --top N     显示前N个高频词 (默认: 20)\n");
    printf("  -h, --help      显示此帮助信息\n");
    printf("\n");
    printf("示例:\n");
    printf("  %s document.txt\n", program_name);
    printf("  %s -w -t 10 document.txt\n", program_name);
}

int main(int argc, char* argv[]) {
    if (argc < 2) {
        show_help(argv[0]);
        return 1;
    }
    
    bool show_words = false;
    int top_words = 20;
    const char* filename = NULL;
    
    // 解析命令行参数
    for (int i = 1; i < argc; i++) {
        if (strcmp(argv[i], "-h") == 0 || strcmp(argv[i], "--help") == 0) {
            show_help(argv[0]);
            return 0;
        } else if (strcmp(argv[i], "-w") == 0 || strcmp(argv[i], "--words") == 0) {
            show_words = true;
        } else if (strcmp(argv[i], "-t") == 0 || strcmp(argv[i], "--top") == 0) {
            if (i + 1 < argc) {
                top_words = atoi(argv[++i]);
                if (top_words <= 0) top_words = 20;
            }
        } else if (argv[i][0] != '-') {
            filename = argv[i];
        }
    }
    
    if (filename == NULL) {
        fprintf(stderr, "错误: 请指定要分析的文件\n");
        show_help(argv[0]);
        return 1;
    }
    
    // 读取和分析文件
    size_t file_size;
    char* content = read_file(filename, &file_size);
    if (content == NULL) {
        return 1;
    }
    
    printf("正在分析文件: %s\n", filename);
    printf("文件大小: %zu 字节\n\n", file_size);
    
    TextStats* stats = analyze_text(content, file_size);
    if (stats == NULL) {
        fprintf(stderr, "错误: 文本分析失败\n");
        free(content);
        return 1;
    }
    
    print_statistics(stats, show_words, top_words);
    
    // 清理资源
    free(content);
    free_text_stats(stats);
    
    return 0;
}

四、总结与展望

（一）系列回顾

通过这八篇文章的系统学习，我们完成了从C语言入门到项目实战的完整旅程：

基础篇（第1-3篇）：

• 掌握了C语言的基本语法和数据类型
• 学会了函数设计和模块化编程
• 深入理解了数组和字符串处理

核心篇（第4-6篇）：

• 掌握了指针和内存管理的核心技术
• 学会了复杂数据类型的组织和使用
• 掌握了文件操作和数据持久化

高级篇（第7-8篇）：

• 探索了C语言的高级特性和现代编程技巧
• 通过项目实战整合了所有知识点

（二）继续学习的方向

系统编程：

• 操作系统原理和系统调用
• 网络编程和并发编程
• 嵌入式系统开发

性能优化：

• 算法和数据结构优化
• 内存管理优化
• 编译器优化技术

工程实践：

• 大型项目的组织和管理
• 代码质量和测试
• 跨平台开发

（三）实践建议

1. 多写代码：理论知识需要通过大量实践来巩固
2. 阅读源码：学习优秀开源项目的代码
3. 参与项目：加入开源项目或自己发起项目
4. 持续学习：关注C语言标准的发展和新技术

恭喜您完成了C语言系统学习系列！
现在您已经具备了扎实的C语言基础，可以开始更高级的编程挑战了。记住，编程是一门实践的艺术，只有不断练习才能真正掌握。

---

参考资料：

• 《算法导论》- Thomas H. Cormen等
• 《UNIX环境高级编程》- W. Richard Stevens
• 《深入理解计算机系统》- Randal E. Bryant
• 《操作系统概念》- Abraham Silberschatz等
• 《C语言接口与实现》- David R. Hanson
• Linux内核源码：https://github.com/torvalds/linux
• GNU C库源码：https://www.gnu.org/software/libc/