使用指針編寫合併排序的問題c

Question

我試圖用指針編寫合併排序程序，它接近於工作良好，但存在的問題是在輸出中存在一些「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 

此外，有沒有什麼建議你可以給我改進我的代碼？
1.如果你想在每一步分配內存（雖然這不是必要的），請確保您免費使用的所有內存時臨時緩存不再：

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

Answer 1

首先，當你忽略錯誤程序只編譯/鏈接。爲malloc添加#include <stdlib.h>，並刪除getch調用，因爲此示例不需要它。此外，您的main函數是1. 隱含返回int和2.缺少返回。

您的程序在合併步驟中失敗 - 您不會考慮當其中一個陣列耗盡時發生的情況。目前的計劃只是繼續閱讀並抓住left或right陣列後面的任何內容，這通常是零。

你需要的是隻有在既不向左或向右耗盡進行比較，然後只需添加剩餘的值，就像這樣：

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

需要注意的是，只有一個malloc內歸併通話了。

Answer 2

關於所使用的內存優化

諮詢需要。
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;  
}