0

我正在尝试编写一个带有指针的合并排序程序，它几乎可以正常工作，但问题是在输出中有一些“0”而不是排序数组的一些数字。

为了测试代码，您必须编写一个 txt 文件prova.txt，其中包含数组，行数为一个。例如：

prova.txt：

4
7
2
9
1
45
87

运行代码时，我期望输出

0: 1 
1: 2
2: 4 
3: 7 
4: 9 
5: 45 
6: 87

但我明白了

0: 1 
1: 0 
2: 0 
3: 0 
4: 0 
5: 0 
6: 2

此外，你有什么建议可以给我改进我的代码吗？

    #include <stdio.h>

int *merge(int left[], int right[], int n){
      int *ordinato, i=0, j=0;
      ordinato = malloc(sizeof(int)*n);
      while(i+j < n){
          if(left[i] < right[j]){
              *(ordinato+i+j) = left[i];
              i++;
          }else{
              *(ordinato+i+j) = right[j];
              j++;
          }
      }
      return ordinato;      
}

int *mergeSort(int *daOrd, int n){
      int k = 0, *left, *right, *ordinato;
      ordinato = malloc(sizeof(int)*n);
      left = malloc(sizeof(int)*(n/2));
      right = malloc(sizeof(int)*(n-(n/2)));
      if (n<2){
         ordinato = daOrd;     
      }else{
         for(k=0; k<n/2; k++)
             *(left + k) = *(daOrd + k);
         for(k=n/2; k<n; k++)
             *(right + k -(n/2)) = *(daOrd + k);

         left = mergeSort(left, n/2);
         right = mergeSort(right, n-(n/2));
         ordinato = merge(left, right, n);
      }      
      return ordinato;
}

main(){
     FILE *input;
     input = fopen("prova.txt", "r");
     if(!input) printf("Errore");

     int tot = 100000;//is the maximum n

     int *array;
     array = malloc(sizeof(int)*tot);
     int indice = 0;
     while(fscanf(input,"%d", (array + indice)) != EOF) indice++;

     int *ord = mergeSort(array, indice);

     int k;
     for(k=0; k<indice; k++) printf("%d: %d \n",k,  *(ord+k));


     getch();
     fclose(input);     
}
4

2 回答 2

1

关于优化所用内存的建议：
1. 如果您想在每一步都分配内存（尽管这不是必需的），请确保在不再需要临时缓冲区时释放所有使用的内存。
2. 无需每一步都创建缓冲区。您可以在开始时分配一个缓冲区，并在算法的每一步都使用该数组中的指针。

问题在于合并功能。当您到达其中一个数组（右或左）的末尾时，您指向的是未分配的内存。在那里，它发现值 0 总是小于剩下的数组中的值。因此，当您的一个缓冲区完全复制到结果中时，您必须停止合并，然后复制另一个缓冲区的剩余内容。

你应该把它改成这样：

int *merge(int left[], int right[], int n){
  int *ordinato, i=0, j=0, k;
  ordinato = malloc(sizeof(int)*n);
  while((i<n/2) && (j<n-n/2)){
      if(left[i] < right[j]){
          *(ordinato+i+j) = left[i];
          i++;
      }else{
          *(ordinato+i+j) = right[j];
          j++;
      }
  }
  while(i!=n/2){
       *(ordinato+i+j) = left[i];
       i++; 
  }
  while(j!=n-n/2){
       *(ordinato+i+j) = right[j];
       j++; 
  }
  return ordinato;      
}
于 2013-07-07T15:59:20.890 回答
1

首先，您的程序仅在您忽略错误时编译/链接。添加#include <stdlib.h>formalloc并删除getch调用，因为此示例不需要它。此外，您的main函数是 1.隐式返回 int 和 2. 缺少该返回。

您的程序在合并步骤中失败 - 您没有考虑当其中一个数组先于另一个用完时会发生什么。当前的程序只是继续阅读并抓取leftorright数组后面的任何内容，这通常是零。

您想要的是仅在左右都没有耗尽时进行比较，然后只需添加剩余的值，如下所示：

#include <stdlib.h>
#include <stdio.h>

void merge(const int* left, const int* right, int* res, int n) {
    int i=0, j=0;
    while ((i < n/2) && (j < n - (n/2))) {
        if (left[i] < right[j]) {
            res[i+j] = left[i];
            i++;
        } else {
            res[i+j] = right[j];
            j++;
        }
    }
    while (i < n/2) {
        res[i+j] = left[i];
        i++;
    }
    while (j < n-(n/2)) {
        res[i+j] = right[j];
        j++;
    }

    return res;
}

void _mergeSort(int* values, int* aside, int n) {
    if (n < 2) {
        return;
    }
    _mergeSort(values, aside, n/2);
    _mergeSort(values+n/2, aside+n/2, n-(n/2));
    merge(values, values + n/2, aside, n);
    memcpy(values, aside, n * sizeof(int));
}

void mergeSort(int* values, int n) {
    int* aside = malloc(sizeof(int) * n);
    _mergeSort(values, aside, n);
    free(aside);
}

int main() {
    FILE *input;
    input = fopen("prova.txt", "r");
    if (!input) {
        fprintf(stderr, "Could not open file");
        return 1;
    }

    int maximum_n = 100000;
    int *array = malloc(sizeof(int)*maximum_n);
    int count;
    for (count = 0;count < maximum_n;count++) {
        if (fscanf(input, "%d", (array + count)) == EOF) {
            break;
        }
    }
    mergeSort(array, count);

    for(int k=0; k < count; k++) {
        printf("%d: %d \n", k, array[k]);
    }
    return 0;
}

请注意，mallocmergeSort 现在只有一个调用。

于 2013-07-07T16:36:18.160 回答