1

我把这个当作家庭作业。使用合并排序，我正在尝试对整数数组进行排序，新的指针数组将以正确的顺序保存指向每个整数的指针，因此如果 arr = {7,2,5,9,4} 比指针数组将是 {ptr to 2, ptr to 4, ptr to 5, ptr to 7, ptr to 9}

所以，起初我需要编写如下函数：

int** pointerSort(int* arr, int size);

我这样做了：

int** pointerSort(int* arr, int size) {
int **res1, **res2, **res;
if (size <= 1) {
    if (size == 0)
        return NULL;

    res = (int **)malloc(sizeof(int) * size);
    *res = arr;

    return res;
}

res1 = pointerSort(arr, size/2);
res2 = pointerSort(arr + size/2, size - size/2);

res = (int **)malloc(sizeof(int **) * size);
merge(res1,size/2,res2, size - size/2,res);

return res;
}


void merge (int **arr1, int size1, int **arr2, int size2, int **res) {

int i1,i2, resI;
i1 = i2 = resI = 0;

while (i1 < size1 && i2 < size2) {
    if (**(arr1 + i1) <= **(arr2 + i2)){
        *(res + resI++) = *(arr1 + i1++);
    }
    else {
        *(res + resI++) = *(arr2 + i2++);
    }
}
while (i1 < size1) {
    *(res + resI++) = *(arr1 + i1++);
}

while (i2 < size2) {
    *(res + resI++) = *(arr2 + i2++);
}
}

但之后我需要将其更改为

void pointerSort2(int* arr, int size, int*** pointers);

这就是我卡住的地方。这是我到目前为止所得到的，它似乎不起作用

void pointerSort2(int* arr, int size, int*** pointers) {
    if (size <= 1) {
        if (size == 0)
            return;

        pointers = (int ***)malloc(size * sizeof(int ***));
        *pointers = &arr;

        return;
    }
    pointerSort2(arr, size/2,pointers);
    pointerSort2(arr + size/2, size - size/2,pointers);

    int ***res = (int ***)malloc(sizeof(int ***) * size);
    merge2(pointers,size/2,pointers, size - size/2,res);

    pointers = res;
}

void merge2 (int ***arr1, int size1, int ***arr2, int size2, int ***res) {
    int i1,i2, resI;
    i1 = i2 = resI = 0;
    int val;
    int val2;
    int b;
    while (i1 < size1 && i2 < size2) {
            int val = ***(arr1 + i1);
    int val2 = ***(arr2 + i2);
    int b = ***(arr1 + i1) <= ***(arr2 + i2);
        if (b) {
            *(res + resI++) = *(arr1 + i1++);
        }
        else {
            *(res + resI++) = *(arr2 + i2++);
        }
    }
    while (i1 < size1) {
        *(res + resI++) = *(arr1 + i1++);
    }

    while (i2 < size2) {
        *(res + resI++) = *(arr2 + i2++);
    }
}

非常感谢

4

1 回答 1

1

首先，关于第一个功能，我有 2 条评论pointerSort()

1）替换res的分配

res = (int **)malloc(sizeof(int) * size);
res = (int **)malloc(sizeof(int**) * size);

只有

res = (int **)malloc(sizeof(int *) * size);

2）在合并之后添加，free否则你会得到内存泄漏res1res2

res = (int **)malloc(sizeof(int **) * size);
merge(res1,size/2,res2, size - size/2,res);
free(res1);
free(res2);

关于您的功能pointerSort2和merge2：这两个功能都有很多代码错误。在新代码修复后在这里。

注意：玩多级指针有些复杂。使用时要小心

void pointerSort2(int* arr, int size, int*** pointers) {
    int **tmp;
    int **pointers1, **pointers2;
    if (size <= 1) {
        if (size == 0)
            return;

        tmp = (int **)malloc(size * sizeof(int **));
        *tmp = arr;
        *pointers = tmp;
        return;
    }
    pointerSort2(arr, size/2,&pointers1);
    pointerSort2(arr + size/2, size - size/2,&pointers2);


    merge2(pointers1,size/2,pointers2, size - size/2,&tmp);
    free(pointers1);
    free(pointers2);    
    *pointers = tmp;
}

void merge2 (int **arr1, int size1, int **arr2, int size2, int ***res) {
    int i1,i2, resI;
    i1 = i2 = resI = 0;
    int val;
    int val2;
    int b;
    int **tmp = (int **)malloc((size1+size2) * sizeof(int **));
    *res = tmp;
    while (i1 < size1 && i2 < size2) {
            int val = **(arr1 + i1);
    int val2 = **(arr2 + i2);
    int b = **(arr1 + i1) <= **(arr2 + i2);
        if (b) {
            *(tmp + resI++) = *(arr1 + i1++);
        }
        else {
            *(tmp + resI++) = *(arr2 + i2++);
        }
    }
    while (i1 < size1) {
        *(tmp + resI++) = *(arr1 + i1++);
    }

    while (i2 < size2) {
        *(tmp + resI++) = *(arr2 + i2++);
    }
}

pointerSort2的调用main应该是

int arr[5] = {2, 5, 3, 7, 6}
int **res;
pointerSort2(arr, 5, &res);
于 2013-04-01T09:19:13.950 回答