在c 中使用指针编写合并排序的问题

我正在尝试用指针编写一个合并排序程序,它接近工作正常,但是存在的问题是在输出中有一些’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  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); } 

首先,只有在忽略错误时,程序才会编译/链接。 为malloc添加#include ,并删除此示例不需要的getch调用。 此外,您的mainfunction是1. 隐含地返回int和2.缺少返回。

您的程序在合并步骤中失败 – 您不会考虑当其中一个arrays在另一个arrays之前耗尽时会发生什么。 当前的程序只是继续读取并抓取leftrightarrays后面的任何东西,通常是零。

你想要的只是在左手或右手都没用完时进行比较,然后只需添加剩下的值,如下所示:

 #include  #include  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; } 

请注意,mergeSort中只有一个malloc调用。

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

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

您应该将其更改为:

 int *merge(int left[], int right[], int n){ int *ordinato, i=0, j=0, k; ordinato = malloc(sizeof(int)*n); while((i