C语言八大经典算法_c语言八大经典算法代码

### **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. **手动绘制**：根据上述描述，画出算法的关键步骤和数据结构。

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