# C语言核心算法与数据结构：编程基础实践指南

## 算法基础与时间复杂度

算法是解决问题的步骤描述，而数据结构是组织和存储数据的方式。理解算法的时间复杂度和空间复杂度对于编写高效程序至关重要。

```c

// 时间复杂度示例

#include <stdio.h>

#include <time.h>

// O(1) 常数时间复杂度

int get_first_element(int arr[], int size) {

    return arr[0];  // 无论数组多大，操作时间相同

}

// O(n) 线性时间复杂度

int find_element(int arr[], int size, int target) {

    for (int i = 0; i < size; i++) {

        if (arr[i] == target) {

            return i;

        }

    }

    return -1;  // 最坏情况需要遍历整个数组

}

// O(n²) 平方时间复杂度

void bubble_sort(int arr[], int size) {

    for (int i = 0; i < size - 1; i++) {

        for (int j = 0; j < size - i - 1; j++) {

            if (arr[j] > arr[j + 1]) {

                int temp = arr[j];

                arr[j] = arr[j + 1];

                arr[j + 1] = temp;

            }

        }

    }

}

// 性能测试函数

void measure_performance() {

    const int SIZE = 10000;

    int arr[SIZE];

    

    // 初始化数组

    for (int i = 0; i < SIZE; i++) {

        arr[i] = SIZE - i;

    }

    

    clock_t start = clock();

    bubble_sort(arr, SIZE);

    clock_t end = clock();

    

    double time_used = ((double)(end - start)) / CLOCKS_PER_SEC;

    printf("冒泡排序 %d 个元素耗时: %.4f 秒\n", SIZE, time_used);

}

```

## 基础数据结构实现

### 数组与动态数组

```c

// 动态数组实现

#include <stdlib.h>

#include <string.h>

typedef struct {

    int* data;

    size_t size;

    size_t capacity;

} DynamicArray;

DynamicArray* create_dynamic_array(size_t initial_capacity) {

    DynamicArray* arr = (DynamicArray*)malloc(sizeof(DynamicArray));

    if (!arr) return NULL;

    

    arr->data = (int*)malloc(initial_capacity * sizeof(int));

    if (!arr->data) {

        free(arr);

        return NULL;

    }

    

    arr->size = 0;

    arr->capacity = initial_capacity;

    return arr;

}

void dynamic_array_push(DynamicArray* arr, int value) {

    if (arr->size >= arr->capacity) {

        // 扩容

        size_t new_capacity = arr->capacity * 2;

        int* new_data = (int*)realloc(arr->data, new_capacity * sizeof(int));

        if (!new_data) return;

        

        arr->data = new_data;

        arr->capacity = new_capacity;

    }

    

    arr->data[arr->size++] = value;

}

void destroy_dynamic_array(DynamicArray* arr) {

    if (arr) {

        free(arr->data);

        free(arr);

    }

}

// 数组基本操作

void array_operations() {

    // 静态数组

    int static_arr[10];

    

    // 初始化

    for (int i = 0; i < 10; i++) {

        static_arr[i] = i * i;

    }

    

    // 遍历

    for (int i = 0; i < 10; i++) {

        printf("arr[%d] = %d\n", i, static_arr[i]);

    }

    

    // 二维数组

    int matrix[3][3] = {

        {1, 2, 3},

        {4, 5, 6},

        {7, 8, 9}

    };

    

    // 遍历二维数组

    for (int i = 0; i < 3; i++) {

        for (int j = 0; j < 3; j++) {

            printf("%d ", matrix[i][j]);

        }

        printf("\n");

    }

}

```

### 链表数据结构

```c

// 单链表实现

typedef struct Node {

    int data;

    struct Node* next;

} ListNode;

// 创建新节点

ListNode* create_node(int value) {

    ListNode* node = (ListNode*)malloc(sizeof(ListNode));

    if (node) {

        node->data = value;

        node->next = NULL;

    }

    return node;

}

// 在链表头部插入

ListNode* insert_at_head(ListNode* head, int value) {

    ListNode* new_node = create_node(value);

    if (!new_node) return head;

    

    new_node->next = head;

    return new_node;

}

// 在链表尾部插入

void insert_at_tail(ListNode** head, int value) {

    ListNode* new_node = create_node(value);

    if (!new_node) return;

    

    if (*head == NULL) {

        *head = new_node;

        return;

    }

    

    ListNode* current = *head;

    while (current->next != NULL) {

        current = current->next;

    }

    current->next = new_node;

}

// 查找节点

ListNode* find_node(ListNode* head, int value) {

    ListNode* current = head;

    while (current != NULL) {

        if (current->data == value) {

            return current;

        }

        current = current->next;

    }

    return NULL;

}

// 删除节点

ListNode* delete_node(ListNode* head, int value) {

    if (head == NULL) return NULL;

    

    // 如果删除的是头节点

    if (head->data == value) {

        ListNode* new_head = head->next;

        free(head);

        return new_head;

    }

    

    ListNode* current = head;

    while (current->next != NULL) {

        if (current->next->data == value) {

            ListNode* to_delete = current->next;

            current->next = to_delete->next;

            free(to_delete);

            return head;

        }

        current = current->next;

    }

    return head;

}

// 遍历链表

void traverse_list(ListNode* head) {

    ListNode* current = head;

    while (current != NULL) {

        printf("%d -> ", current->data);

        current = current->next;

    }

    printf("NULL\n");

}

// 反转链表

ListNode* reverse_list(ListNode* head) {

    ListNode* prev = NULL;

    ListNode* current = head;

    ListNode* next = NULL;

    

    while (current != NULL) {

        next = current->next;  // 保存下一个节点

        current->next = prev;   // 反转指针

        prev = current;        // 移动prev

        current = next;        // 移动current

    }

    

    return prev;  // prev成为新的头节点

}

// 检测链表是否有环

int has_cycle(ListNode* head) {

    if (head == NULL || head->next == NULL) {

        return 0;

    }

    

    ListNode* slow = head;

    ListNode* fast = head;

    

    while (fast != NULL && fast->next != NULL) {

        slow = slow->next;          // 每次走一步

        fast = fast->next->next;    // 每次走两步

        

        if (slow == fast) {

            return 1;  // 有环

        }

    }

    

    return 0;  // 无环

}

```

### 栈与队列

```c

// 栈实现（数组版本）

#define MAX_STACK_SIZE 100

typedef struct {

    int data[MAX_STACK_SIZE];

    int top;

} Stack;

void stack_init(Stack* s) {

    s->top = -1;  // 空栈

}

int stack_is_empty(Stack* s) {

    return s->top == -1;

}

int stack_is_full(Stack* s) {

    return s->top == MAX_STACK_SIZE - 1;

}

int stack_push(Stack* s, int value) {

    if (stack_is_full(s)) {

        return 0;  // 栈满

    }

    s->data[++s->top] = value;

    return 1;

}

int stack_pop(Stack* s, int* value) {

    if (stack_is_empty(s)) {

        return 0;  // 栈空

    }

    *value = s->data[s->top--];

    return 1;

}

int stack_peek(Stack* s) {

    if (stack_is_empty(s)) {

        return -1;  // 错误值

    }

    return s->data[s->top];

}

// 栈应用：括号匹配

int is_balanced_parentheses(const char* expression) {

    Stack s;

    stack_init(&s);

    

    for (int i = 0; expression[i] != '\0'; i++) {

        char ch = expression[i];

        

        if (ch == '(' || ch == '[' || ch == '{') {

            stack_push(&s, ch);

        } else if (ch == ')' || ch == ']' || ch == '}') {

            if (stack_is_empty(&s)) {

                return 0;  // 右括号多余

            }

            

            int top_char;

            stack_pop(&s, &top_char);

            

            if ((ch == ')' && top_char != '(') ||

                (ch == ']' && top_char != '[') ||

                (ch == '}' && top_char != '{')) {

                return 0;  // 括号不匹配

            }

        }

    }

    

    return stack_is_empty(&s);  // 栈空表示匹配成功

}

// 队列实现（循环数组）

#define MAX_QUEUE_SIZE 100

typedef struct {

    int data[MAX_QUEUE_SIZE];

    int front;  // 队头

    int rear;   // 队尾

    int size;   // 当前元素数量

} Queue;

void queue_init(Queue* q) {

    q->front = 0;

    q->rear = -1;

    q->size = 0;

}

int queue_is_empty(Queue* q) {

    return q->size == 0;

}

int queue_is_full(Queue* q) {

    return q->size == MAX_QUEUE_SIZE;

}

int queue_enqueue(Queue* q, int value) {

    if (queue_is_full(q)) {

        return 0;

    }

    

    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;

    q->data[q->rear] = value;

    q->size++;

    return 1;

}

int queue_dequeue(Queue* q, int* value) {

    if (queue_is_empty(q)) {

        return 0;

    }

    

    *value = q->data[q->front];

    q->front = (q->front + 1) % MAX_QUEUE_SIZE;

    q->size--;

    return 1;

}

int queue_peek(Queue* q) {

    if (queue_is_empty(q)) {

        return -1;

    }

    return q->data[q->front];

}

```

## 常用算法实现

### 排序算法

```c

// 快速排序

void quick_sort(int arr[], int left, int right) {

    if (left >= right) return;

    

    int pivot = arr[(left + right) / 2];

    int i = left, j = right;

    

    while (i <= j) {

        while (arr[i] < pivot) i++;

        while (arr[j] > pivot) j--;

        

        if (i <= j) {

            int temp = arr[i];

            arr[i] = arr[j];

            arr[j] = temp;

            i++;

            j--;

        }

    }

    

    quick_sort(arr, left, j);

    quick_sort(arr, i, right);

}

// 归并排序

void merge(int arr[], int left, int mid, int right) {

    int i, j, k;

    int n1 = mid - left + 1;

    int n2 = right - mid;

    

    // 创建临时数组

    int* L = (int*)malloc(n1 * sizeof(int));

    int* R = (int*)malloc(n2 * sizeof(int));

    

    // 复制数据到临时数组

    for (i = 0; i < n1; i++)

        L[i] = arr[left + i];

    for (j = 0; j < n2; j++)

        R[j] = arr[mid + 1 + j];

    

    // 合并临时数组

    i = 0; j = 0; k = left;

    while (i < n1 && j < n2) {

        if (L[i] <= R[j]) {

            arr[k] = L[i];

            i++;

        } else {

            arr[k] = R[j];

            j++;

        }

        k++;

    }

    

    // 复制剩余元素

    while (i < n1) {

        arr[k] = L[i];

        i++; k++;

    }

    while (j < n2) {

        arr[k] = R[j];

        j++; k++;

    }

    

    free(L);

    free(R);

}

void merge_sort(int arr[], int left, int right) {

    if (left < right) {

        int mid = left + (right - left) / 2;

        

        merge_sort(arr, left, mid);

        merge_sort(arr, mid + 1, right);

        

        merge(arr, left, mid, right);

    }

}

// 选择排序

void selection_sort(int arr[], int n) {

    for (int i = 0; i < n - 1; i++) {

        int min_index = i;

        for (int j = i + 1; j < n; j++) {

            if (arr[j] < arr[min_index]) {

<"pq.sxyicheng.cn"><"rs.jsnjz.cn"><"vw.csxthr.com">

                min_index = j;

            }

        }

        

        if (min_index != i) {

            int temp = arr[i];

            arr[i] = arr[min_index];

            arr[min_index] = temp;

        }

    }

}

```

### 查找算法

```c

// 二分查找（数组必须已排序）

int binary_search(int arr[], int size, int target) {

    int left = 0, right = size - 1;

    

    while (left <= right) {

        int mid = left + (right - left) / 2;

        

        if (arr[mid] == target) {

            return mid;

        } else if (arr[mid] < target) {

            left = mid + 1;

        } else {

            right = mid - 1;

        }

    }

    

    return -1;  // 未找到

}

// 二分查找递归版本

int binary_search_recursive(int arr[], int left, int right, int target) {

    if (left > right) return -1;

    

    int mid = left + (right - left) / 2;

    

    if (arr[mid] == target) {

        return mid;

    } else if (arr[mid] > target) {

        return binary_search_recursive(arr, left, mid - 1, target);

    } else {

        return binary_search_recursive(arr, mid + 1, right, target);

    }

}

// 哈希表简单实现（线性探测）

#define HASH_TABLE_SIZE 100

typedef struct {

    int key;

    int value;

    int is_occupied;  // 0=空, 1=已占用

} HashEntry;

typedef struct {

    HashEntry entries[HASH_TABLE_SIZE];

} HashTable;

unsigned int hash_function(int key) {

    // 简单哈希函数

    return key % HASH_TABLE_SIZE;

}

void hash_table_init(HashTable* ht) {

    for (int i = 0; i < HASH_TABLE_SIZE; i++) {

        ht->entries[i].is_occupied = 0;

    }

}

int hash_table_insert(HashTable* ht, int key, int value) {

    unsigned int index = hash_function(key);

    unsigned int start_index = index;

    

    do {

        if (!ht->entries[index].is_occupied) {

            ht->entries[index].key = key;

            ht->entries[index].value = value;

            ht->entries[index].is_occupied = 1;

            return 1;  // 成功

        }

        

        if (ht->entries[index].key == key) {

            // 更新已存在的键

            ht->entries[index].value = value;

            return 1;

        }

        

        index = (index + 1) % HASH_TABLE_SIZE;

    } while (index != start_index);

    

    return 0;  // 哈希表已满

}

int hash_table_search(HashTable* ht, int key, int* value) {

    unsigned int index = hash_function(key);

    unsigned int start_index = index;

    

    do {

        if (!ht->entries[index].is_occupied) {

            break;  // 遇到空槽，说明不存在

        }

        

        if (ht->entries[index].key == key) {

            *value = ht->entries[index].value;

            return 1;  // 找到

        }

        

        index = (index + 1) % HASH_TABLE_SIZE;

    } while (index != start_index);

    

    return 0;  // 未找到

}

```

## 字符串处理算法

```c

// KMP字符串匹配算法

void compute_lps(const char* pattern, int pattern_len, int* lps) {

    int length = 0;  // 最长前缀后缀长度

    lps[0] = 0;      // 第一个字符的lps总是0

    

    int i = 1;

    while (i < pattern_len) {

        if (pattern[i] == pattern[length]) {

            length++;

            lps[i] = length;

            i++;

        } else {

            if (length != 0) {

                length = lps[length - 1];

            } else {

                lps[i] = 0;

                i++;

            }

        }

    }

}

int kmp_search(const char* text, const char* pattern) {

    int text_len = strlen(text);

    int pattern_len = strlen(pattern);

    

    if (pattern_len == 0) return 0;

    

    int* lps = (int*)malloc(pattern_len * sizeof(int));

    compute_lps(pattern, pattern_len, lps);

    

    int i = 0;  // text索引

    int j = 0;  // pattern索引

    

    while (i < text_len) {

        if (pattern[j] == text[i]) {

            i++;

            j++;

        }

        

        if (j == pattern_len) {

            free(lps);

            return i - j;  // 找到匹配

        } else if (i < text_len && pattern[j] != text[i]) {

            if (j != 0) {

                j = lps[j - 1];

            } else {

                i++;

            }

        }

    }

    

    free(lps);

    return -1;  // 未找到

}

// 字符串反转

void reverse_string(char* str) {

    if (!str) return;

    

    int len = strlen(str);

    for (int i = 0; i < len / 2; i++) {

        char temp = str[i];

        str[i] = str[len - i - 1];

        str[len - i - 1] = temp;

    }

}

// 判断字符串是否为回文

int is_palindrome(const char* str) {

    int len = strlen(str);

    for (int i = 0; i < len / 2; i++) {

        if (str[i] != str[len - i - 1]) {

            return 0;

        }

    }

    return 1;

}

```

## 树结构基础

```c

// 二叉树节点

typedef struct TreeNode {

    int data;

    struct TreeNode* left;

    struct TreeNode* right;

} TreeNode;

// 创建二叉树节点

TreeNode* create_tree_node(int value) {

    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));

    if (node) {

        node->data = value;

        node->left = NULL;

        node->right = NULL;

    }

    return node;

}

// 二叉树遍历

void preorder_traversal(TreeNode* root) {

    if (root == NULL) return;

    

    printf("%d ", root->data);      // 访问根节点

    preorder_traversal(root->left);  // 遍历左子树

    preorder_traversal(root->right); // 遍历右子树

}

void inorder_traversal(TreeNode* root) {

    if (root == NULL) return;

    

    inorder_traversal(root->left);   // 遍历左子树

    printf("%d ", root->data);       // 访问根节点

    inorder_traversal(root->right);  // 遍历右子树

}

void postorder_traversal(TreeNode* root) {

    if (root == NULL) return;

    

    postorder_traversal(root->left);   // 遍历左子树

    postorder_traversal(root->right);  // 遍历右子树

    printf("%d ", root->data);         // 访问根节点

}

// 二叉查找树插入

TreeNode* bst_insert(TreeNode* root, int value) {

    if (root == NULL) {

        return create_tree_node(value);

    }

    

    if (value < root->data) {

        root->left = bst_insert(root->left, value);

    } else if (value > root->data) {

        root->right = bst_insert(root->right, value);

    }

    

    return root;

}

// 二叉查找树查找

TreeNode* bst_search(TreeNode* root, int value) {

    if (root == NULL || root->data == value) {

        return root;

    }

    

    if (value < root->data) {

        return bst_search(root->left, value);

    } else {

        return bst_search(root->right, value);

    }

}

// 计算二叉树高度

int tree_height(TreeNode* root) {

    if (root == NULL) return 0;

    

    int left_height = tree_height(root->left);

    int right_height = tree_height(root->right);

    

    return (left_height > right_height ? left_height : right_height) + 1;

}

```

## 综合应用示例

```c

// 简单的学生成绩管理系统

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef struct {

    int id;

    char name[50];

    float score;

} Student;

typedef struct Node {

    Student data;

    struct Node* next;

} StudentNode;

// 创建成绩管理系统

StudentNode* create_student_system() {

    return NULL;  // 空链表

}

// 添加学生

StudentNode* add_student(StudentNode* head, Student student) {

    StudentNode* new_node = (StudentNode*)malloc(sizeof(StudentNode));

    if (!new_node) return head;

    

    new_node->data = student;

    new_node->next = head;

    return new_node;

}

// 按学号查找

StudentNode* find_student_by_id(StudentNode* head, int id) {

    StudentNode* current = head;

    while (current != NULL) {

        if (current->data.id == id) {

            return current;

        }

        current = current->next;

    }

    return NULL;

}

// 删除学生

StudentNode* delete_student(StudentNode* head, int id) {

    if (head == NULL) return NULL;

    

    if (head->data.id == id) {

        StudentNode* new_head = head->next;

        free(head);

        return new_head;

    }

    

    StudentNode* current = head;

    while (current->next != NULL) {

        if (current->next->data.id == id) {

            StudentNode* to_delete = current->next;

            current->next = to_delete->next;

            free(to_delete);

            return head;

        }

        current = current->next;

    }

    return head;

}

// 统计平均分

float calculate_average_score(StudentNode* head) {

    if (head == NULL) return 0.0;

    

    float total = 0.0;

    int count = 0;

    StudentNode* current = head;

    

    while (current != NULL) {

        total += current->data.score;

        count++;

        current = current->next;

    }

    

    return total / count;

}

// 按成绩排序（降序）

StudentNode* sort_students_by_score(StudentNode* head) {

    if (head == NULL || head->next == NULL) return head;

<"xy.zhaiLimao.com"><"za.yunruiwater.cn"><"ca.sxyicheng.cn">

    

    // 将链表转为数组以便排序

    int count = 0;

    StudentNode* current = head;

    while (current != NULL) {

        count++;

        current = current->next;

    }

    

    Student* students = (Student*)malloc(count * sizeof(Student));

    current = head;

    for (int i = 0; i < count; i++) {

        students[i] = current->data;

        current = current->next;

    }

    

    // 使用选择排序

    for (int i = 0; i < count - 1; i++) {

        int max_index = i;

        for (int j = i + 1; j < count; j++) {

            if (students[j].score > students[max_index].score) {

                max_index = j;

            }

        }

        

        if (max_index != i) {

            Student temp = students[i];

            students[i] = students[max_index];

            students[max_index] = temp;

        }

    }

    

    // 重建链表

    StudentNode* new_head = NULL;

    for (int i = 0; i < count; i++) {

        new_head = add_student(new_head, students[i]);

    }

    

    free(students);

    return new_head;

}

// 打印所有学生

void print_students(StudentNode* head) {

    printf("学号\t姓名\t成绩\n");

    printf("--------------------\n");

    

    StudentNode* current = head;

    while (current != NULL) {

        printf("%d\t%s\t%.2f\n", 

               current->data.id, 

               current->data.name, 

               current->data.score);

        current = current->next;

    }

}

int main() {

    StudentNode* system = create_student_system();

    

    // 添加测试数据

    Student s1 = {1001, "张三", 85.5};

    Student s2 = {1002, "李四", 92.0};

    Student s3 = {1003, "王五", 78.5};

    

    system = add_student(system, s1);

    system = add_student(system, s2);

    system = add_student(system, s3);

    

    printf("所有学生信息:\n");

    print_students(system);

    

    printf("\n平均成绩: %.2f\n", calculate_average_score(system));

    

    printf("\n按成绩排序后:\n");

    system = sort_students_by_score(system);

    print_students(system);

    

    // 清理内存（在实际应用中需要实现）

    // ...

    

    return 0;

}

```

C语言算法与数据结构是编程能力的基石。通过理解和掌握这些基础概念与实现，开发者能够编写出高效、可靠的程序。从简单的数组和链表到复杂的排序算法和树结构，这些知识构成了解决实际问题的重要工具集。通过不断实践和应用，可以将这些基础知识转化为解决复杂问题的实际能力。