C语言的10大基础算法

简介

C语言是一门非常古老并且非常流行的编程语言。C语言强大的功能和丰富的软件库致使它成为了许多程序员和企业的首选开发语言。不仅如此，C语言中还有一些非常重要而基础的算法，这些算法也是程序员必须掌握的一部分。这篇文章将介绍C语言中的10个最基础的算法。

算法介绍

1. 排序算法

排序算法是所有程序员必须掌握的一部分，因为数据处理与排序是编程中不可避免的事情。C语言提供了不少的排序算法，如冒泡排序、选择排序、插入排序等。

以下是一个冒泡排序的C语言代码示例：

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]) 
                swap(&arr[j], &arr[j+1]); 
}

2. 查找算法

查找算法是在一组数据中查找特定值的一种方式。线性查找和二分查找是C语言中最常见的查找算法。

以下是一个二分查找的C语言代码示例：

int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 

        if (arr[mid] == x) 
            return mid; 

        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 

        return binarySearch(arr, mid + 1, r, x); 
    } 

    return -1; 
} 

3. 字符串处理算法

字符串处理算法是在C语言中非常常见的算法，如字符串的拼接、分割、转换等操作。

以下是一个字符串拼接的C语言代码示例：

char *concat(char *s1, char *s2) 
{ 
    char *result = (char *)malloc(strlen(s1) + strlen(s2) + 1); 
    strcpy(result, s1); 
    strcat(result, s2); 
    return result; 
} 

4. 单链表

单链表是C语言中非常常用的数据结构之一，操作简便且易于拓展。

以下是一个单链表的C语言代码示例：

typedef struct node 
{ 
    int data; 
    struct node *next; 
}Node; 

void printList(Node *node) 
{ 
    while (node != NULL) 
    { 
        printf("%d ", node->data); 
        node = node->next; 
    } 
} 

5. 栈与队列

栈与队列是C语言中最受欢迎的数据结构之一。栈与队列的使用场景非常丰富，如表达式转换、进程管理等。

以下是一个栈的C语言代码示例：

#define MAX_SIZE 1000 

typedef struct Stack 
{ 
    int top; 
    int arr[MAX_SIZE]; 
}stack; 

int isEmpty(stack *s) 
{ 
    return s->top == -1; 
} 

void push(stack *s, int data) 
{ 
    s->arr[++s->top] = data; 
} 

int pop(stack *s) 
{ 
    if (!isEmpty(s)) 
        return s->arr[s->top--]; 

    return -1; 
} 

6. 递归算法

递归算法常用于处理复杂的问题，例如排序、求和等操作。

以下是一个阶乘的C语言代码示例：

int factorial(int n) 
{ 
    if (n == 0) 
        return 1; 

    return n * factorial(n-1); 
} 

7. 查找与排序树

二叉树是C语言中一种非常常见的数据结构，不仅可以用于查找操作，还可以用于排序。

以下是一个二叉树的C语言代码示例：

typedef struct node 
{ 
    int key; 
    struct node *left, *right; 
}Node; 

Node *newNode(int item) 
{ 
    Node *temp =  (Node *)malloc(sizeof(Node)); 
    temp->key = item; 
    temp->left = temp->right = NULL; 
    return temp; 
} 

Node* insert(Node* node, int key) 
{ 
    if (node == NULL) 
        return newNode(key); 

    if (key < node->key) 
        node->left  = insert(node->left, key); 
    else if (key > node->key) 
        node->right = insert(node->right, key);    

    return node; 
} 

8. 图

图是C语言中用于解决复杂的问题的一种非常重要的数据结构。

以下是一个图的C语言代码示例：

struct Graph 
{ 
    int V; 
    struct AdjList* array; 
}; 

struct AdjList 
{ 
    struct GraphNode* head; 
}; 

struct GraphNode 
{ 
    int dest; 
    struct GraphNode* next; 
}; 

struct Graph* createGraph(int V) 
{ 
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph)); 
    graph->V = V; 

    graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList)); 

    int i; 
    for (i = 0; i < V; ++i) 
        graph->array[i].head = NULL; 

    return graph; 
} 

9. 动态规划

动态规划算法用于解决复杂的问题，例如组合问题、背包问题等。

以下是一个背包问题的C语言代码示例：

int knapSack(int W, int wt[], int val[], int n) 
{ 
    int i, w; 
    int K[n+1][W+1]; 

    for (i = 0; i <= n; i++) 
    { 
        for (w = 0; w <= W; w++) 
        { 
            if (i==0 || w==0) 
                K[i][w] = 0; 
            else if (wt[i-1] <= w) 
                  K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]); 
            else
                  K[i][w] = K[i-1][w]; 
        } 
    } 

    return K[n][W]; 
} 

10. 数论算法

数论算法用于解决与数字相关的问题，例如素数、最大公约数等。

以下是一个素数判断的C语言代码示例：

bool isPrime(int n) 
{ 
    if (n <= 1) 
        return false; 

    for (int i = 2; i < n; i++) 
        if (n%i == 0) 
            return false; 

    return true; 
} 

结论

C语言是程序员必须掌握的一种编程语言，而在C语言中，掌握基本算法是必不可少的。本文介绍了C语言中最基础的10个算法，并提供了每种算法的示例，希望可以帮助读者更好地理解这些算法并应用到实际开发中。