-1

我有一个大学的任务来编写一个程序，该程序接收一个整数数组及其大小，并返回一个指向原始数组值的排序数组。排序必须使用 mergeSort 算法来完成，我不允许触摸原始数组，只能更改指针数组。

谁能帮我吗？这是我的代码：

void sortedPointerArray (int **arr1[], int size1, int **arr2[], int size2, int **arr3[])
{
    int read1, read2, writeind;

    read1 = read2 = writeind = 0;
    while( (read1<size1) && (read2 < size2))
    {
            if (*(arr1[read1]) < *(arr2[read2]))
            {
                    arr3[writeind] = arr1[read1];
                    writeind++;
                    read1++;
            }
            else
            {
                    arr3[writeind] = arr2[read2];
                    writeind++;
                    read2++;
            }

    }
    while (read1 < size1)
    {
            arr3[writeind] = arr1[read1];
            writeind++;
            read1++;
    }
    while (read2 < size2)
    {
            arr3[writeind] = arr2[read2];
            writeind++;
            read2++;
    }
}

void mergeSort (int **arr, int size)
{
    int temp, i;

    if(size <=1)
            return;
    else
    {
            mergeSort(arr, size/2);
            mergeSort(arr+(size/2), size-(size/2));
            int** temp = (int **)malloc(size*sizeof(int *));
            sortedPointerArray(arr,size/2,arr+(size/2),size-(size/2),temp);
            for (i=0; i<size; i++)
                    (*arr)[i] = (*temp)[i];
            free(temp);
    }
}

由于某些未知原因，我无法编译它并且它不起作用......任何帮助将不胜感激！

4

2 回答 2

0

sortedPointerArray只需要接收 int[]，而不是int**[]. 目前它在合并排序数组时比较指针而不是整数。mergeSort应该更改调用代码指向的数组，因此需要int**（或int*&在 C++ 中）。mergeSort还应该避免释放完全排序的数组。

在不相关的说明中，我认为您的代码可以使用更好的变量名。例如，arr1、arr2 和 arr3 可以分别替换为 in1、in2 和 out。您还可以对数组进行注释，const以减少意外更改输入数组的风险。

于 2013-04-04T21:57:02.983 回答
0 
#include <stdlib.h>
#include <stdio.h>

void mergeSort (int **arr, size_t size);
void sortedPointerArray (int **arr1, size_t size1, int **arr2, size_t size2, int **arr3);

void sortedPointerArray (int **arr1, size_t size1, int **arr2, size_t size2, int **arr3)
{
    size_t read1, read2, writeind;

    for(read1=read2=writeind=0; read1 < size1 && read2 < size2; )
            arr3[writeind++] = (*arr1[read1] < *arr2[read2])
                   ? arr1[read1++]
                   : arr2[read2++]
                   ;

    while (read1 < size1)
            arr3[writeind++] = arr1[read1++];

    while (read2 < size2)
            arr3[writeind++] = arr2[read2++];
}

void mergeSort (int **arr, size_t size)
{
    size_t idx;
    int **temp ;

    if(size < 2) return;

    mergeSort(arr, size/2);
    mergeSort(arr+(size/2), size-(size/2));

    temp = malloc(size*sizeof *temp);
    sortedPointerArray(arr,size/2,arr+(size/2),size-(size/2),temp);
    for (idx=0; idx<size; idx++)
            arr[idx] = temp[idx];
    free(temp);
}


#define COUNTOF(a) (sizeof a/ sizeof a[0])
int array[] = { 3,2,4,5,9,8,7,1,6,0};

int *ptrs[COUNTOF( array)];

int main(void)
{
unsigned idx;

for(idx=0; idx < COUNTOF( array); idx++ ) ptrs[idx] = array+idx;

mergeSort(ptrs, COUNTOF(ptrs) );

for(idx=0; idx < COUNTOF(ptrs); idx++ ) {
        printf("%u: %p %d\n", idx, (void*) ptrs[idx], *ptrs[idx] );
        }
return 0;
}

输出：

0: 0x601064 0
1: 0x60105c 1
2: 0x601044 2
3: 0x601040 3
4: 0x601048 4
5: 0x60104c 5
6: 0x601060 6
7: 0x601058 7
8: 0x601054 8
9: 0x601050 9

评论/更改：

  • 删除了令人困惑（和错误）的额外间接级别
  • 删除了多余的括号
  • 删除了 malloc 不需要的演员表
  • 压缩合并循环以使用dst[aaa++] = src[bbb++];
  • 将所有索引更改为无符号 (size_t) 类型。
  • 之后删除了其他部分if (size <2) return;
  • 添加了一个驱动程序。
  • 去掉大括号并引入三元运算符来挫败老师
于 2013-04-04T22:09:20.180 回答