C语言算法详细介绍和相关题目讲解。

晚霞的不甘

发布于 2025-12-23 10:15:49

1200

一、算法基础概念

1.1 什么是算法

算法是解决特定问题的一系列清晰指令，具有以下特性：

· 有穷性：执行有限步骤后必然终止 · 确定性：每个步骤都有明确含义 · 可行性：每个操作都可以通过已实现的基本运算执行 · 输入：有零个或多个输入 · 输出：有一个或多个输出

1.2 算法复杂度分析

// 时间复杂度示例
void example_algorithm(int n) {
    // O(1) - 常数时间复杂度
    int a = 1;
    
    // O(n) - 线性时间复杂度
    for(int i = 0; i < n; i++) {
        printf("%d ", i);
    }
    
    // O(n²) - 平方时间复杂度
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            printf("(%d,%d) ", i, j);
        }
    }
}

二、基础算法详解

2.1 排序算法

冒泡排序

void bubble_sort(int arr[], int n) {
    for(int i = 0; i < n - 1; i++) {
        for(int j = 0; j < n - i - 1; j++) {
            if(arr[j] > arr[j + 1]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

快速排序

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);
}

2.2 查找算法

二分查找

int binary_search(int arr[], int n, int target) {
    int left = 0, right = n - 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; // 未找到
}

三、经典算法题目讲解

3.1 两数之和

题目：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

解法：

#include <stdio.h>

void two_sum(int nums[], int n, int target) {
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            if(nums[i] + nums[j] == target) {
                printf("找到两数: %d + %d = %d\n", nums[i], nums[j], target);
                return;
            }
        }
    }
    printf("未找到符合条件的两个数\n");
}

// 优化版本（假设数组已排序）
void two_sum_optimized(int nums[], int n, int target) {
    int left = 0, right = n - 1;
    
    while(left < right) {
        int sum = nums[left] + nums[right];
        if(sum == target) {
            printf("找到两数: %d + %d = %d\n", nums[left], nums[right], target);
            return;
        } else if(sum < target) {
            left++;
        } else {
            right--;
        }
    }
    printf("未找到符合条件的两个数\n");
}

3.2 斐波那契数列

题目：计算第n个斐波那契数

解法：

// 递归解法（时间复杂度高）
int fibonacci_recursive(int n) {
    if(n <= 1) return n;
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}

// 动态规划解法（高效）
int fibonacci_dp(int n) {
    if(n <= 1) return n;
    
    int dp[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    
    for(int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

// 空间优化版本
int fibonacci_optimized(int n) {
    if(n <= 1) return n;
    
    int prev1 = 0, prev2 = 1;
    int current;
    
    for(int i = 2; i <= n; i++) {
        current = prev1 + prev2;
        prev1 = prev2;
        prev2 = current;
    }
    
    return current;
}

3.3 最大子数组和

题目：找出一个整数数组中具有最大和的连续子数组

解法（Kadane算法）：

#include <stdio.h>
#include <limits.h>

int max_subarray_sum(int nums[], int n) {
    int max_sum = INT_MIN;
    int current_sum = 0;
    
    for(int i = 0; i < n; i++) {
        current_sum += nums[i];
        
        if(current_sum > max_sum) {
            max_sum = current_sum;
        }
        
        if(current_sum < 0) {
            current_sum = 0;
        }
    }
    
    return max_sum;
}

// 扩展：返回子数组的起止位置
void max_subarray_with_indices(int nums[], int n) {
    int max_sum = INT_MIN;
    int current_sum = 0;
    int start = 0, end = 0, temp_start = 0;
    
    for(int i = 0; i < n; i++) {
        current_sum += nums[i];
        
        if(current_sum > max_sum) {
            max_sum = current_sum;
            start = temp_start;
            end = i;
        }
        
        if(current_sum < 0) {
            current_sum = 0;
            temp_start = i + 1;
        }
    }
    
    printf("最大子数组和: %d\n", max_sum);
    printf("子数组范围: [%d, %d]\n", start, end);
}

3.4 链表反转

题目：反转一个单链表

解法：

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

// 链表节点定义
struct ListNode {
    int val;
    struct ListNode *next;
};

// 迭代法反转链表
struct ListNode* reverse_list(struct ListNode* head) {
    struct ListNode *prev = NULL;
    struct ListNode *current = head;
    struct ListNode *next = NULL;
    
    while(current != NULL) {
        next = current->next;  // 保存下一个节点
        current->next = prev;  // 反转指针
        prev = current;        // 移动prev
        current = next;        // 移动current
    }
    
    return prev;  // 新的头节点
}

// 递归法反转链表
struct ListNode* reverse_list_recursive(struct ListNode* head) {
    if(head == NULL || head->next == NULL) {
        return head;
    }
    
    struct ListNode* new_head = reverse_list_recursive(head->next);
    head->next->next = head;
    head->next = NULL;
    
    return new_head;
}

四、算法实践建议

4.1 学习路径

1. 基础阶段：掌握基本数据结构（数组、链表、栈、队列） 2. 进阶阶段：学习排序、查找、递归、动态规划 3. 高级阶段：图算法、字符串算法、高级数据结构

4.2 练习方法

· 每天坚持刷1-2道算法题 · 理解算法思想，不只是记忆代码 · 分析时间复杂度和空间复杂度 · 尝试多种解法并进行比较

4.3 常用技巧

// 双指针技巧示例
void two_pointers_example(int arr[], int n) {
    int left = 0, right = n - 1;
    
    while(left < right) {
        // 根据条件移动指针
        if(/* 某种条件 */) {
            left++;
        } else {
            right--;
        }
    }
}

// 滑动窗口技巧示例
void sliding_window_example(int arr[], int n, int k) {
    int window_sum = 0;
    
    // 计算第一个窗口的和
    for(int i = 0; i < k; i++) {
        window_sum += arr[i];
    }
    
    // 滑动窗口
    for(int i = k; i < n; i++) {
        window_sum = window_sum - arr[i - k] + arr[i];
        // 处理当前窗口
    }
}

五、总结

C语言算法学习需要理论与实践相结合。通过不断练习经典题目，深入理解算法思想，并能够根据具体问题选择合适的算法策略。记住，算法的核心是思想，代码只是思想的表达形式。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-11-10，如有侵权请联系 [email protected] 删除

int