標準MergeSort算法

我目前正在使用一個漂亮的標準合併排序文件，但我遇到了一些問題。我對數據結構相當陌生，所以不能完全理解發生了什麼。任何提示都會很好。謝謝。標準MergeSort算法

下面是代碼

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

typedef struct CELL *LIST; 
struct CELL { 
    int element; 
    LIST next; 
} 

LIST merge(LIST list1, LIST list2); 
LIST split(LIST list); 
LIST MergeSort(LIST list); 
LIST MakeList(); 
void PrintList(LIST list); 

int main() 
{ 
    LIST list; 

    list = MakeList(); 
    PrintList(MergeSort(list)); 
} 

LIST MakeList() 
{ 
    int x; 
    LIST pNewCell; 
    if(scanf("%d", &x) == EOF) return NULL; 
    else { 
     pNewCell = (LIST) malloc(sizeof(struct CELL)); 
     pNewCell->next = MakeList(); 
     pNewCell->element = x; 
     return pNewCell; 
    } 
} 

void PrintList(LIST list) 
{ 
    while(list != NULL) { 
     printf("%d\n", list->element); 
     list = list->next; 
    } 
} 

LIST MergeSort(LIST list) 
{ 
    LIST SecondList; 

    if (list == NULL) return NULL; 
    else if (list->next == NULL) return list; 
    else { 
     SecondList = split(list); 
     return merge(MergeSort(list), MergeSort(SecondList)); 
    } 
} 

LIST merge(LIST list1, LIST list2) 
{ 
    if (list1 == NULL) return list2; 
    else if(list2 == NULL) return list1; 
    else if(list1->element <= list2->element){ 
     list1->next = merge(list1->next, list2); 
     return list1; 
    } 
    else { 
     list2->next = merge(list1, list2->next); 
     return list2; 
    } 
} 

LIST split(LIST list) 
{ 
    LIST pSecondCell; 

    if (list == NULL) return NULL; 
    else if (list->next == NULL) return NULL; 
    else { 
     pSecondCell = list->next; 
     list->next = pSecondCell->next; 
     pSecondCell->next = split(pSecondCell->next); 
     return pSecondCell; 
    } 
}

而且，我得到的（多平臺）是

prog.c:10:6: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘merge’ 
LIST merge(LIST list1, LIST list2); 
     ^~~~~ 
prog.c: In function ‘MergeSort’: 
prog.c:53:16: warning: implicit declaration of function ‘merge’ [-Wimplicit-function-declaration] 
     return merge(MergeSort(list), MergeSort(SecondList)); 
       ^~~~~ 
prog.c:53:16: warning: return makes pointer from integer without a cast [-Wint-conversion] 
     return merge(MergeSort(list), MergeSort(SecondList)); 
       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
prog.c: At top level: 
prog.c:57:6: error: conflicting types for ‘merge’ 
LIST merge(LIST list1, LIST list2) 
     ^~~~~ 
prog.c:53:16: note: previous implicit declaration of ‘merge’ was here 
     return merge(MergeSort(list), MergeSort(SecondList)); 
       ^~~~~

來源

2017-03-16 Evan

遞歸合併將佔用O（n）堆棧空間，而不是學習問題，但對於大型列表來說會是個問題。如果感興趣，你可以考慮實現一個[自下而上的列表合併排序 - 維基例子]（http://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists），它使用相同的merge（）函數，但是使用一個指向節點的指針數組，用於存儲臨時列表而不是分割它們。它比分割列表快，但將列表移動到數組，對數組進行排序，以及從已排序數組創建新列表的速度更快。 – rcgldr

這是錯誤的錯誤：

typedef struct CELL *LIST; 
struct CELL { 
    int element; 
    LIST next; 
}

試試這個：

typedef struct CELL { 
    int element; 
    struct CELL *next; 
} CELL, *LIST;

請注意next必須是一個指針，而不是另一個CELL結構。

您的第一條錯誤消息只是指出您在聲明struct CELL後錯過了分號。（這也是爲什麼merge()的聲明被忽略的原因。）

來源

2017-03-16 22:00:09

哦！我錯過了分號。聽起來很正確。謝謝您的幫助！ – Evan

標準MergeSort算法

回答

相關問題