C语言八大经典算法

大家好，欢迎来到IT知识分享网。

C语言八大经典算法

1. 冒泡排序（Bubble Sort）

– 描述：通过相邻元素比较和交换，将最大元素逐步“冒泡”到数组末尾。

– 代码片段：

“`c

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])

swap(&arr[j], &arr[j+1]);

}

“`

– 示意图：可用箭头表示相邻元素比较和交换的过程。

2. 快速排序（Quick Sort）

– 描述：分治思想，选取基准值将数组分为两部分，递归排序。

– 代码片段：

“`c

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) {

int pi = partition(arr, low, high);

quickSort(arr, low, pi-1);

quickSort(arr, pi+1, high);

}

}

“`

– 示意图：用树状图展示分治过程，标出基准值的位置。

3. 二分查找（Binary Search）

– 描述：在有序数组中通过折半缩小搜索范围。

– 代码片段：

“`c

int binarySearch(int arr[], int l, int r, int x) {

while (l <= r) {

int mid = l + (r – l) / 2;

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

if (arr[mid] < x) l = mid + 1;

else r = mid – 1;

}

return -1;

}

“`

– 示意图：绘制有序数组，标出中间值比较的过程。

4. 递归算法（Recursion）

– 描述：函数调用自身解决问题（如阶乘、斐波那契数列）。

– 代码片段（阶乘）：

“`c

int factorial(int n) {

if (n == 0) return 1;

return n * factorial(n-1);

}

“`

– 示意图：用栈结构展示递归调用过程。

5. 动态规划（Dynamic Programming）

– 描述：通过子问题的最优解推导全局最优解（如背包问题）。

– 代码片段（斐波那契优化）：

“`c

int fib(int 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];

}

“`

– 示意图：表格形式展示子问题的存储和复用。

6. 贪心算法（Greedy Algorithm）

– 描述：每一步选择当前最优解（如找零钱问题）。

– 代码片段（活动选择问题）：

“`c

void activitySelection(int start[], int end[], int n) {

printf(“Selected Activity: 0 “);

int last = 0;

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

if (start[i] >= end[last]) {

printf(“%d “, i);

last = i;

}

}

“`

– 示意图：时间轴标注活动选择顺序。

7. 回溯算法（Backtracking）

– 描述：通过试错探索解空间，失败时回退（如八皇后问题）。

– 代码片段（八皇后问题片段）：

“`c

void solveNQUtil(int board[N][N], int col) {

if (col >= N) return true;

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

if (isSafe(board, i, col)) {

board[i][col] = 1;

if (solveNQUtil(board, col+1)) return true;

board[i][col] = 0; // 回溯

}

}

return false;

}

“`

– 示意图：棋盘上标注皇后的放置和冲突检测。

8. 深度优先搜索（DFS）与广度优先搜索（BFS）

– 描述：图遍历算法，DFS用栈/递归，BFS用队列。

– 代码片段（DFS递归实现）：

“`c

void DFS(int v, int visited[], int graph[][V]) {

visited[v] = 1;

for (int i = 0; i < V; i++)

if (graph[v][i] && !visited[i])

DFS(i, visited, graph);

}

“`

– 示意图：用树或图结构展示遍历顺序。

如何生成图片？

1. 使用绘图工具（如Visio、Draw.io、Lucidchart）根据算法步骤绘制流程图。

2. 代码可视化工具：利用在线工具（如Code2Flow）将代码转换为流程图。

3. 手动绘制：根据上述描述，画出算法的关键步骤和数据结构。

如果需要更具体的某一种算法示意图设计，可以进一步说明需求！