0

我昨天写了下面的插入排序（我3天前开始学习C）。出于某种原因，排序不会修改数组AT ALL。

#include <stdio.h>
int *insert(int arr[], int index, int item);
int *isort(int arr[]);
int main() {
    int a[17] = {1, 2, 9, 5, 3, 2, 1, 6, 5, 9, 0, 1, 3, 4, 2, 3, 4};
    int *b = isort(a);
    for (int i = 0; i < 17; i += 1) {
        printf("%d ", b[i]);
    }
    return 0;
}
int *insert(int arr[], int index, int item) {
    --index;
    while (index >= 0 && item < arr[index]) {
        arr[index + 1] = arr[index];
        --index;
    }
    arr[index + 1] = item;
    return arr;
}
int *isort(int arr[]) {
    for (int i = 1; i < sizeof(arr) - 1; i++) {
        arr = insert(arr, i, arr[i]);
    }
    return arr;
}

我想它可能是我的编译器，因为我正在运行一个非 unix 机器上的编译器：lcc-win，但我不确定。我在这里缺少一些基本的东西吗？

4

2 回答 2

3 
int *isort(int arr[]) {
    for (int i = 1; i < sizeof(arr) - 1; i++) {
        arr = insert(arr, i, arr[i]);
    }
    return arr;
}

在这个函数sizeof(arr)中实际上返回的是指针的大小而不是数组的大小。

在 C 中，一个特殊规则说数组参数实际上被调整为相应指针类型的参数。

那是：

int *isort(int arr[]) { /* ... */ }

相当于：

int *isort(int *arr) { /* ... */ }

要解决此问题，请在函数中添加一个采用数组大小​​的新参数：

int *isort(int arr[], size_t size) { /* ... */ }
于 2012-08-14T20:49:36.697 回答
1

如前所述，第一个问题是 isort 函数在指针上使用 sizeof 运算符。乍一看，C 处理数组的方式有点奇怪。数组的名称是指向其第一个元素的指针。因此，当您像这样调用 isort 时：

int *b = isort(a);

您只是将指向数组的指针推入堆栈。在isot的定义中，

int *isort(int arr[])

将 arr 声明为指向 int 的指针，就像

int *isort(int *arr)

C 在这方面更加令人困惑：如果您说过：

int *isort(int arr[17])

arr 变量仍然只是一个指向 int 的指针……这里的“17”被丢弃了！即使使用这种语法，sizeof(arr) 仍然是指向 int 的指针的大小。

在 32 位系统 (ILP32) 上，sizeof(arr) 将始终为 4，无论数组有多大。

因此，需要将数组的大小传递给 isort。一个很好的通用方法是定义这样的宏：

#define NITEMS(arr) (sizeof(arr)/sizeof(arr[0]))

这将计算任何类型数组中的元素数。

您的下一个问题更多的是一种风格，而不是实际的错误：

arr = insert(arr, i, arr[i]);

这将调用插入函数并引用“arr”。通过该引用修改数组，然后返回指向该数组的指针。它总是和你一开始发送的指针相同，所以这个赋值实际上什么也没做，没有害处。就像我说的，风格问题，而不是代码错误。

最后一个问题是您的 isort 函数会短暂停止（在您纠正 sizeof 问题之后），因为您从 1 变为 sizeof-1。这是一个固定版本：

#include <stdio.h>
#define NITEMS(arr) (sizeof(arr)/sizeof(arr[0]))

int *insert(int arr[], int index, int item);
int *isort(int arr[], size_t nitems);
int main() {
    int a[17] = {1, 2, 9, 5, 3, 2, 1, 6, 5, 9, 0, 1, 3, 4, 2, 3, 4};
    int *b = isort(a, NITEMS(a));
    for (int i = 0; i < NITEMS(a); i += 1) {
        printf("%d ", b[i]);
    }
    printf("\n");
    return 0;
}

int *insert(int arr[], int index, int item) {
    --index;
    while (index >= 0 && item < arr[index]) {
        arr[index + 1] = arr[index];
        --index;
    }
    arr[index + 1] = item;
    return arr;
}

int *isort(int arr[], size_t nitems) {
    for (int i = 1; i < nitems; i++) {
        insert(arr, i, arr[i]);
    }
    return arr;
}
于 2012-08-14T23:15:52.997 回答