【2017年山西大学考研真题】已知线性表按顺序存储，且每个元素都是不相同的整数型元素。
（1）设计把所有奇数移动到所有偶数前面的算法。
（2）根据给出算法的设计思想，根据设计思想，给出描述算法
（1）算法设计思想：
1. 使用两个指针 `start` 和 `end` 分别指向线性表的第一个元素和最后一个元素。
2. 不断移动 `start` 指针，直到找到一个偶数。
3. 不断移动 `end` 指针，直到找到一个奇数。
4. 如果 `start` 指针小于等于 `end` 指针，则将 `start` 指针指向的偶数和 `end` 指针指向的奇数进行交换。
5. 重复步骤 2 ~ 4，直到 `start` 指针大于等于 `end` 指针。
（2）根据上述设计思想，可以用 C 语言编写以下算法：
```c
#include <stdio.h>
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void moveOddBeforeEven(int* arr, int n) {
if (arr == NULL || n <= 1) {
return;
}
int* start = arr; // start 指针指向数组的第一个元素
int* end = arr + n - 1; // end 指针指向数组的最后一个元素
while (start < end) {
while (*start % 2 != 0) { // 找到一个偶数
start++;
}
while (*end % 2 == 0) { // 找到一个奇数
end--;
}
if (start < end) {
swap(start, end); // 交换偶数和奇数
}
}
}
int main() {
int arr[] = {2, 1, 3, 8, 5, 6, 7, 4};
int n = sizeof(arr) / sizeof(arr[0]);
printf("移动前的数组：");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
moveOddBeforeEven(arr, n);
printf("移动后的数组：");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
在上述代码中，首先定义了一个辅助函数 `swap`，用于交换两个整数的值。然后定义了主函数 `moveOddBeforeEven`，根据设计思想实现了将奇数移动到偶数前面的算法。最后，在 `main` 函数中，通过调用 `moveOddBeforeEven` 函数，将奇数移动到偶数前面，并打印移动前和移动后的数组。输出结果为：
```
移动前的数组：2 1 3 8 5 6 7 4
移动后的数组：1 3 5 7 2 8 6 4
```
可以看到，奇数已经移动到了偶数的前面。
