Standard-MergeSort-Algorithmus

Question

Ich arbeite derzeit mit einer ziemlich Standard-Merge-Sort-Datei, habe aber einige Probleme. Ich bin ziemlich neu in Datenstrukturen, verstehe also nicht wirklich, was vor sich geht. Irgendwelche Tipps wären auch nett. Vielen Dank. Hier

ist der Code

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

Und die Fehler, die ich (auf mehreren Plattformen) erhalten sind

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)); 
       ^~~~~ 

Answer 1

Das ist falsch:

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

dies stattdessen versuchen:

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

Beachten Sie, dass next ein Zeiger sein muss, nicht ein weiterer CELL struct.

Die erste Ihrer Fehlermeldungen zeigt nur, dass Sie das Semikolon nach Ihrer Deklaration von struct CELL verpasst haben. (Dies ist auch der Grund, warum die Deklaration von merge() ignoriert wird.)