常用算法程序集(c 语言描述)-C语言-盈思创科技

这份程序集将包含数据结构、排序、查找、图论、数学和字符串处理等多个领域的核心算法，每个算法都会包含：

（图片来源网络，侵删）

算法简介：简要说明算法的用途和思想。
C语言实现：提供清晰、可读的C语言代码。
复杂度分析：分析时间复杂度和空间复杂度。
使用示例：展示如何调用该函数。

数据结构

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

实现：

#include <stdio.h>
#include <stdlib.h>
// 定义链表节点
typedef struct Node {
    int data;
    struct Node* next;
} Node;
// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
// 在链表末尾插入节点
void appendNode(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* last = *head;
    while (last->next != NULL) {
        last = last->next;
    }
    last->next = newNode;
}
// 打印链表
void printList(Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}
// 释放链表内存
void freeList(Node* head) {
    Node* tmp;
    while (head != NULL) {
        tmp = head;
        head = head->next;
        free(tmp);
    }
}
// 使用示例
int main() {
    Node* head = NULL;
    appendNode(&head, 10);
    appendNode(&head, 20);
    appendNode(&head, 30);
    printf("Linked List: ");
    printList(head);
    freeList(head);
    return 0;
}

复杂度分析：

appendNode: 时间复杂度 O(n)，空间复杂度 O(1)。
printList: 时间复杂度 O(n)，空间复杂度 O(1)。

栈

栈是一种特殊的线性表,它只允许在固定的一端进行插入和删除元素操作，遵循后进先出原则。

（图片来源网络，侵删）

实现 (使用数组):

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
    int items[MAX_SIZE];
    int top;
} Stack;
// 初始化栈
void initStack(Stack* s) {
    s->top = -1;
}
// 检查栈是否为空
int isEmpty(Stack* s) {
    return s->top == -1;
}
// 检查栈是否已满
int isFull(Stack* s) {
    return s->top == MAX_SIZE - 1;
}
// 入栈
void push(Stack* s, int value) {
    if (isFull(s)) {
        printf("Stack is full!\n");
        return;
    }
    s->items[++(s->top)] = value;
}
// 出栈
int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return -1; // 返回一个错误值
    }
    return s->items[(s->top)--];
}
// 查看栈顶元素
int peek(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return s->items[s->top];
}
// 使用示例
int main() {
    Stack s;
    initStack(&s);
    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
    printf("Top element: %d\n", peek(&s)); // 输出 30
    printf("Popped element: %d\n", pop(&s)); // 输出 30
    printf("Popped element: %d\n", pop(&s)); // 输出 20
    printf("Top element: %d\n", peek(&s)); // 输出 10
    return 0;
}

复杂度分析：

push, pop, peek: 时间复杂度 O(1)，空间复杂度 O(1)。

队列

队列是一种特殊的线性表,它只允许在一端进行插入操作，而在另一端进行删除操作，遵循先进先出原则。

实现 (使用数组 - 循环队列):

（图片来源网络，侵删）

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
    int items[MAX_SIZE];
    int front;
    int rear;
} Queue;
// 初始化队列
void initQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}
// 检查队列是否为空
int isEmpty(Queue* q) {
    return q->front == -1;
}
// 入队
void enqueue(Queue* q, int value) {
    if ((q->rear + 1) % MAX_SIZE == q->front) {
        printf("Queue is full!\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->items[q->rear] = value;
}
// 出队
int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
    int item = q->items[q->front];
    if (q->front == q->rear) {
        // 队列中只剩一个元素
        q->front = -1;
        q->rear = -1;
    } else {
        q->front = (q->front + 1) % MAX_SIZE;
    }
    return item;
}
// 使用示例
int main() {
    Queue q;
    initQueue(&q);
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    printf("Dequeued element: %d\n", dequeue(&q)); // 输出 10
    printf("Dequeued element: %d\n", dequeue(&q)); // 输出 20
    enqueue(&q, 40);
    printf("Dequeued element: %d\n", dequeue(&q)); // 输出 30
    printf("Dequeued element: %d\n", dequeue(&q)); // 输出 40
    return 0;
}

复杂度分析：

enqueue, dequeue: 时间复杂度 O(1)，空间复杂度 O(1)。

二叉树

二叉树是每个节点最多有两个子树的树结构,通常子树被称作“左子树”和“右子树”。

实现：

#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;
// 创建新节点
TreeNode* createTreeNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
// 前序遍历 (根 -> 左 -> 右)
void preorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}
// 中序遍历 (左 -> 根 -> 右)
void inorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
}
// 后序遍历 (左 -> 右 -> 根)
void postorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%d ", root->data);
}
// 释放树内存
void freeTree(TreeNode* root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}
// 使用示例
int main() {
    /* 创建如下二叉树:
          1
         / \
        2   3
       / \
      4   5
    */
    TreeNode* root = createTreeNode(1);
    root->left = createTreeNode(2);
    root->right = createTreeNode(3);
    root->left->left = createTreeNode(4);
    root->left->right = createTreeNode(5);
    printf("Preorder Traversal: ");
    preorderTraversal(root); // 输出: 1 2 4 5 3
    printf("\n");
    printf("Inorder Traversal: ");
    inorderTraversal(root); // 输出: 4 2 5 1 3
    printf("\n");
    printf("Postorder Traversal: ");
    postorderTraversal(root); // 输出: 4 5 2 3 1
    printf("\n");
    freeTree(root);
    return 0;
}

复杂度分析：

所有遍历算法的时间复杂度均为 O(n)，n 是树中节点的数量。
空间复杂度取决于树的高度,最坏情况下（树退化为链表）为 O(n)，平均情况下为 O(log n)。

排序算法

冒泡排序

重复地遍历要排序的数列,一次比较两个元素，如果它们的顺序错误就把它们交换过来。

#include <stdio.h>
void bubbleSort(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 printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: ");
    printArray(arr, n);
    bubbleSort(arr, n);
    printf("Sorted array: ");
    printArray(arr, n);
    return 0;
}

复杂度分析：

时间复杂度：O(n²) (最坏、平均情况)，O(n) (最好情况，即数组已有序)。
空间复杂度：O(1)。

快速排序

选择一个基准元素,将数组分为两部分，一部分比基准小，一部分比基准大，然后递归地对这两部分进行排序。

#include <stdio.h>
// 交换两个元素
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}
// 分区函数，返回基准元素的最终位置
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = (low - 1);     // 小于基准的元素的索引
    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于基准
        if (arr[j] <= pivot) {
            i++; // 增加小于基准的元素的索引
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}
// 快速排序主函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi是分区后基准元素的位置
        int pi = partition(arr, low, high);
        // 递归排序分区
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: ");
    printArray(arr, n);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: ");
    printArray(arr, n);
    return 0;
}

复杂度分析：

时间复杂度：O(n log n) (平均、最好情况)，O(n²) (最坏情况，如数组已有序或逆序)。
空间复杂度：O(log n) (递归调用栈的深度)。

归并排序

采用分治法,将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。

#include <stdio.h>
#include <stdlib.h>
// 合并两个已排序的子数组
void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    // 创建临时数组
    int L[n1], R[n2];
    // 复制数据到临时数组
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    // 合并临时数组
    i = 0;
    j = 0;
    k = l;
    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++;
    }
}
// 归并排序主函数
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2; // 防止溢出
        // 递归排序左右两半
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}
void printArray(int A[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    printf("Given array is \n");
    printArray(arr, arr_size);
    mergeSort(arr, 0, arr_size - 1);
    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    return 0;
}

复杂度分析：

时间复杂度：O(n log n) (所有情况)。
空间复杂度：O(n) (需要临时数组)。

查找算法

顺序查找

从数据结构的一端开始,逐个检查每个元素，直到找到所需的元素或检查完所有元素。

#include <stdio.h>
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i; // 返回找到的元素的索引
        }
    }
    return -1; // 未找到，返回-1
}
int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 10;
    int result = linearSearch(arr, n, target);
    if (result == -1) {
        printf("Element not present in array\n");
    } else {
        printf("Element found at index %d\n", result);
    }
    return 0;
}

复杂度分析：

时间复杂度：O(n) (最坏、平均情况)，O(1) (最好情况)。
空间复杂度：O(1)。

二分查找

在有序数组中查找特定元素,每次比较都使搜索范围减半。

#include <stdio.h>
int binarySearch(int arr[], int l, int r, int target) {
    while (l <= r) {
        int mid = l + (r - l) / 2;
        // 检查目标是否在中间
        if (arr[mid] == target) {
            return mid;
        }
        // 如果目标大于中间元素，则在右半部分查找
        if (arr[mid] < target) {
            l = mid + 1;
        }
        // 如果目标小于中间元素，则在左半部分查找
        else {
            r = mid - 1;
        }
    }
    // 未找到目标
    return -1;
}
int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 10;
    int result = binarySearch(arr, 0, n - 1, target);
    if (result == -1) {
        printf("Element not present in array\n");
    } else {
        printf("Element found at index %d\n", result);
    }
    return 0;
}

复杂度分析：

时间复杂度：O(log n) (所有情况)。
空间复杂度：O(1) (迭代版本)，O(log n) (递归版本，调用栈)。

图论算法

图的邻接表表示

这是表示图的一种常用方法,特别适合稀疏图。

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
// 邻接表节点
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;
// 邻接表
typedef struct AdjList {
    AdjListNode* head; // 指向邻接表头节点的指针
} AdjList;
// 图结构
typedef struct Graph {
    int V; // 顶点数
    AdjList* array; // 邻接表数组
} Graph;
// 创建新的邻接表节点
AdjListNode* newAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}
// 创建一个包含 V 个顶点的图
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->array = (AdjList*)malloc(V * sizeof(AdjList));
    for (int i = 0; i < V; ++i) {
        graph->array[i].head = NULL;
    }
    return graph;
}
// 向图中添加一条边
void addEdge(Graph* graph, int src, int dest) {
    // 添加从 src 到 dest 的边
    AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
    // 如果是无向图，添加从 dest 到 src 的边
    // newNode = newAdjListNode(src);
    // newNode->next = graph->array[dest].head;
    // graph->array[dest].head = newNode;
}
// 打印图的邻接表表示
void printGraph(Graph* graph) {
    int v;
    for (v = 0; v < graph->V; ++v) {
        AdjListNode* pCrawl = graph->array[v].head;
        printf("\n Adjacency list of vertex %d\n head ", v);
        while (pCrawl) {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}
int main() {
    int V = 5;
    Graph* graph = createGraph(V);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);
    printGraph(graph);
    // 释放内存的代码省略...
    return 0;
}

深度优先搜索

从起始顶点开始,沿着一条路径尽可能深地访问，直到不能再前进时回溯。

#include <stdio.h>
#include <stdlib.h>
// 假设已经定义了上面的 Graph, AdjListNode, createGraph, addEdge
// 辅助函数：用于DFS的递归实现
void DFSUtil(Graph* graph, int v, int visited[]) {
    // 标记当前节点为已访问并打印
    visited[v] = 1;
    printf("%d ", v);
    // 递归访问所有未访问的邻接节点
    AdjListNode* pCrawl = graph->array[v].head;
    while (pCrawl != NULL) {
        if (!visited[pCrawl->dest]) {
            DFSUtil(graph, pCrawl->dest, visited);
        }
        pCrawl = pCrawl->next;
    }
}
// DFS主函数
void DFS(Graph* graph, int startVertex) {
    // 创建一个visited数组并初始化为false
    int* visited = (int*)malloc(graph->V * sizeof(int));
    for (int i = 0; i < graph->V; i++) {
        visited[i] = 0;
    }
    // 调用递归辅助函数
    printf("DFS starting from vertex %d: ", startVertex);
    DFSUtil(graph, startVertex, visited);
    printf("\n");
    free(visited);
}

广度优先搜索

从起始顶点开始,先访问所有直接相邻的顶点，然后再逐层访问它们的相邻顶点。

#include <stdio.h>
#include <stdlib.h>
// 假设已经定义了上面的 Graph, AdjListNode, createGraph, addEdge
// 并包含队列的实现 (参考上面的队列部分)
void BFS(Graph* graph, int startVertex) {
    int* visited = (int*)malloc(graph->V * sizeof(int));
    for (int i = 0; i < graph->V; i++) {
        visited[i] = 0;
    }
    Queue q; // 使用前面定义的队列
    initQueue(&q);
    visited[startVertex] = 1;
    enqueue(&q, startVertex);
    printf("BFS starting from vertex %d: ", startVertex);
    while (!isEmpty(&q)) {
        int currentVertex = dequeue(&q);
        printf("%d ", currentVertex);
        AdjListNode* pCrawl = graph->array[currentVertex].head;
        while (pCrawl != NULL) {
            if (!visited[pCrawl->dest]) {
                visited[pCrawl->dest] = 1;
                enqueue(&q, pCrawl->dest);
            }
            pCrawl = pCrawl->next;
        }
    }
    printf("\n");
    free(visited);
}

迪杰斯特拉最短路径

用于在加权图中找到从一个源点到所有其他顶点的最短路径。

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
// 假设已经定义了图的邻接表表示
// 找到未访问节点中距离最小的顶点
int minDistance(int dist[], bool sptSet[], int V) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++) {
        if (sptSet[v] == false && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}
// 打印构建的距离数组
void printSolution(int dist[], int V) {
    printf("Vertex \t\t Distance from Source\n");
    for (int i = 0; i < V; i++) {
        printf("%d \t\t %d\n", i, dist[i]);
    }
}
// 迪杰斯特拉算法主函数
void dijkstra(Graph* graph, int src) {
    int V = graph->V;
    int dist[V]; // 存储源点到每个顶点的最短距离
    bool sptSet[V]; // sptSet[i]为true表示顶点i在最短路径树中
    // 初始化所有距离为无穷大，sptSet[]为false
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }
    // 源点到自身的距离为0
    dist[src] = 0;
    // 找到源点到所有其他顶点的最短路径
    for (int count = 0; count < V - 1; count++) {
        // 从未处理的顶点中选择距离最小的顶点
        int u = minDistance(dist, sptSet, V);
        // 标记选定的顶点为已处理
        sptSet[u] = true;
        // 更新u的邻接顶点的距离值
        AdjListNode* pCrawl = graph->array[u].head;
        while (pCrawl != NULL) {
            int v = pCrawl->dest;
            if (!sptSet[v] && dist[u] != INT_MAX && dist[u] + 1 < dist[v]) {
                dist[v] = dist[u] + 1; // 注意：此代码假设边权重为1
            }
            pCrawl = pCrawl->next;
        }
    }
    // 打算计算出的最短距离
    printSolution(dist, V);
}

注意：上面的Dijkstra代码是针对无权图（或权为1）的，对于有权图，需要在邻接表节点中增加weight字段，并在更新dist[v]时使用dist[u] + pCrawl->weight。

数学算法

最大公约数

计算两个或多个整数的最大公约数。

#include <stdio.h>
// 使用欧几里得算法 (迭代法)
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
// 使用欧几里得算法 (递归法)
int gcd_recursive(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd_recursive(b, a % b);
}
int main() {
    int num1 = 56, num2 = 98;
    printf("The GCD of %d and %d is %d\n", num1, num2, gcd(num1, num2));
    return 0;
}

复杂度分析：

时间复杂度：O(log(min(a, b)))。

最小公倍数

计算两个或多个整数的最小公倍数。

#include <stdio.h>
// 利用GCD计算LCM
int lcm(int a, int b) {
    // 处理a或b为0的情况
    if (a == 0 || b == 0) {
        return 0;
    }
    // LCM(a, b) = |a * b| / GCD(a, b)
    return (a / gcd(a, b)) * b; // 先除后乘可以防止溢出
}
// 假设上面的gcd函数已经定义
int main() {
    int num1 = 12, num2 = 15;
    printf("The LCM of %d and %d is %d\n", num1, num2, lcm(num1, num2));
    return 0;
}

素数判断

判断一个数是否为素数（质数）。

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
// 判断一个数是否为素数
bool isPrime(int n) {
    // 小于等于1的数不是素数
    if (n <= 1) {
        return false;
    }
    // 2是唯一的偶素数
    if (n == 2) {
        return true;
    }
    // 排除所有偶数
    if (n % 2 == 0) {
        return false;
    }
    // 只需检查奇数因子，直到sqrt(n)
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}
int main() {
    int num = 29;
    if (isPrime(num)) {
        printf("%d is a prime number.\n", num);
    } else {
        printf("%d is not a prime number.\n", num);
    }
    return 0;
}

复杂度分析：

时间复杂度：O(√n)。

斐波那契数列

一个经典的数列,其中每个数字是前两个数字的和。

#include <stdio.h>
// 递归实现 (效率低，不推荐用于大n)
int fibonacci_recursive(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}
// 迭代实现 (效率高)
int fibonacci_iterative(int n) {
    if (n <= 1) {
        return n;
    }
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}
int main() {
    int n = 10;
    printf("Fibonacci number at position %d (recursive) is %d\n", n, fibonacci_recursive(n));
    printf("Fibonacci number at position %d (iterative) is %d\n", n, fibonacci_iterative(n));
    return 0;
}

复杂度分析：

递归：时间复杂度 O(2ⁿ)，空间复杂度 O(n)。
迭代：时间复杂度 O(n)，空间复杂度 O(1)。

字符串算法

字符串反转

将一个字符串中的字符顺序颠倒。

#include <stdio.h>
#include <string.h>
// 反转字符串 (原地修改)
void reverseString(char str[]) {
    int length = strlen(str);
    for (int i = 0; i < length / 2; i++) {
        char temp = str[i];
        str[i] = str[length - i - 1];
        str[length - i - 1] = temp;
    }
}
int main() {
    char str[] = "hello world";
    printf("Original string: %s\n", str);
    reverseString(str);
    printf("Reversed string: %s\n", str);
    return 0;
}

复杂度分析：

时间复杂度：O(n)，n 是字符串的长度。
空间复杂度：O(1)。

字符串连接

将两个字符串拼接成一个。

#include <stdio.h>
#include <string.h>
// 连接两个字符串 (strcat的标准库实现)
void myStrcat(char dest[], const char src[]) {
    int i, j;
    // 找到dest字符串的末尾
    for (i = 0; dest[i] != '\0'; i++);
    // 将src的内容复制到dest的末尾
    for (j = 0; src[j] != '\0'; j++) {
        dest[i + j] = src[j];
    }
    // 添加字符串结束符
    dest[i + j] = '\0';
}
int main() {
    char str1[100] = "Hello, "; // 确保dest有足够的空间
    char str2[] = "world!";
    myStrcat(str1, str2);
    printf("Concatenated string: %s\n", str1);
    return 0;
}

复杂度分析：

时间复杂度：O(n + m)，n 和 m 分别是两个字符串

常用算法程序集(c 语言描述)

目录

数据结构

链表

栈

队列

二叉树

排序算法

冒泡排序

快速排序

归并排序

查找算法

顺序查找

二分查找

图论算法

图的邻接表表示

深度优先搜索

广度优先搜索

迪杰斯特拉最短路径

数学算法

最大公约数

最小公倍数

素数判断

斐波那契数列

字符串算法

字符串反转

字符串连接

相关文章

目录[+]