当前位置：首页 > article >正文

考研真题数据结构

article 2024/11/14 14:45:32

【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
```

可以看到，奇数已经移动到了偶数的前面。