C並べ替えの問題

Question

各単語の出現を降順で並べ替えるにはどうすればよいですか？

私の現在のコードは次のとおりです。

#include <stdio.h> 
#include <stdlib.h> 
#include <stddef.h> 
#include <ctype.h> 
#include <string.h> 

#define WORDLEN 50 

typedef struct node_struct NODE; 
struct node_struct { 
    char *word;  
    int count; 
    NODE *next; 
}; 

/*compare and adds words to the list*/ 
NODE *new_node(char *word, NODE *head) { 
    NODE *p = head; 
    char *s; 

    if (p == NULL) { 
    p = (NODE*)malloc(sizeof(NODE)); 
    s = (char*)malloc(sizeof(strlen(word) + 1)); 
    strcpy(s, word); 
    p->word = s; 
    p->count = 1; 
    p->next = head; 
    return p; 
    } 
    for (; p->next != NULL && strcmp(p->word, word) != 0; p = p->next); 
    if (strcmp(p->word, word) == 0) { 
    p->count += 1; 
    return head; 
    }else{ 
    p->next = (NODE*)malloc(sizeof(NODE)); 
    p = p->next; 
    s = (char*)malloc(sizeof(strlen(word) + 1)); 
    strcpy(s, word); 
    p->count = 1; 
    p->word = s; 
    p->next = NULL; 
    return head; 
    } 
} 
/*gets words*/ 
char *getword(char *w, int n) 
{ 
    int i = 0; 
    int c; 

    if (n <= 0 || feof(stdin)) 
    return NULL; 
    c = getchar(); 
    while (c != EOF && ! isalpha(c)) { 
    c = getchar(); 
    } 
    if (c == EOF) 
    return NULL; 
    while (isalpha(c)) { 
    if (i < n - 1) { 
     w[i] = toupper(c); 
     i++; 
    } 
    c = getchar(); 
    } 
    w[i] = '\0'; 
    return w; 
} 
/*print*/ 
void print(NODE *p) { 
    for (; p != NULL; p = p->next) { 
    printf("%s %d\n",p->word, p->count); 
    } 
    printf("\n"); 
} 

int main() 
{ 
    char w[WORDLEN]; 
    NODE *p = NULL; 
    int i; 

    while (getword(w, WORDLEN) != NULL) { 
p = new_node(w, p); 
    } 
    print(p); 
    return 0; 
    } 

Answer 1

あなたはリストをリンクソートするための任意のソートアルゴリズムを使用することができます。 algosの並べ替えの説明は、ウィキペディアで見つけることができます。ここでは最も簡単なソートアルゴリズム

Bubble Sort

Insert Sort

Merge Sort

のいくつかのそれはかなりまっすぐ進むCにこれらALGOSを翻訳する必要がありますので、これらのWikipediaのページはまた、これらのアルゴリズムのための擬似コードが含まれてはいますあなたの出発点はmain（）の "P"です。つまり、これらのアルゴを使って昇順または降順のいずれかで並べ替えることができます。

Answer 2

質問は多少曖昧です - 機能を並べ替えることについて勉強したいのですか、あるいは単にプログラムを動作させたいですか？ :-)

あなたが好きなものだけが必要な場合は、リンクリストの代わりに動的に展開する配列を使うことを検討できます。新しいエントリを追加するときにrealloc（）を行い、通常のqsort（）でソートすることができます。

副作用として、パフォーマンス全体特に、より多くの再配分を行う場合は特にそうです。このコードはさらにコンパクトになり、可読性が向上する可能性があります。

更新：ああ、私が意味することを示すことに抵抗することはできません。あなたが動的に拡大し、配列を使用する場合は、関数new_nodeは、このように実装することができますこのかどうかは個人の好みの問題です

NODE * nodes = NULL; 
unsigned node_count = 0; 

void new_node(char word) { 
    unsigned n; 

    for (n = 0; n < node_count && strcmp(nodes[n], word) != 0; n++); 

    if (n < node_count) { 
     nodes[n].count++; 
    } else { 
     nodes = realloc(nodes, sizeof(NODE) * node_count + 1); 
     assert(nodes != NULL); 
     nodes[n].word = strdup(word); 
     assert(nodes[n].word != NULL); 
     nodes[n].count = 1; 
    } 
} 

場合のように。これがである場合は、を使用するかどうかは、実際の使用例に依存しません。

Answer 3

私は結局、あなたの助けをしてくれた皆様に感謝して解決しました！

私のコードは今ある：あなたが動けなくない

#include <stdio.h> 
#include <stdlib.h> 
#include <stddef.h> 
#include <ctype.h> 
#include <string.h> 

#define WORDLEN 50 

typedef struct node_struct NODE; 
struct node_struct { 
    char *word;  
    int count; 
    NODE *next; 
}; 

void new_node(char *word, NODE **head); 
void print(NODE *p); 
void mergesort_node(NODE **head); 
void split_list(NODE *source, NODE **p, NODE **q); 
NODE *merge_sorted_lists(NODE *source1, NODE *source2); 
char *getword(char *word); 

int main(int argc, char *argv[]) 
{ 
    char w[WORDLEN]; 
    NODE *p = NULL; 

    while (getword(w)) { 
    new_node(w, &p); 
    } 
    mergesort_node(&p); 
    print(p); 
    return 0; 
    } 

//adds words to the list 
void new_node(char *word, NODE **head) { 
    NODE *p = *head; 
    char *s; 

    if (p == NULL) { 
    p = (NODE*)malloc(sizeof(NODE)); 
    s = (char*)malloc(sizeof(strlen(word) + 1)); 
    strcpy(s, word); 
    p->word = s; 
    p->count = 1; 
    p->next = NULL; 
    *head = p; 
    }else{ 
    for (; p->next != NULL && strcmp(p->word, word) != 0; p = p->next); 
    if (strcmp(p->word, word) == 0) { 
    p->count += 1; 
    }else{ 
    p->next = (NODE*)malloc(sizeof(NODE)); 
    p = p->next; 
    s = (char*)malloc(sizeof(strlen(word) + 1)); 
    strcpy(s, word); 
    p->count = 1; 
    p->word = s; 
    p->next = NULL; 
    } 
    } 
} 
//gets words 
char *getword(char *w) 
{ 
    int i = 0; 
    int c; 

    if (WORDLEN <= 0 || feof(stdin)){ 
    return NULL;} 
    c = getchar(); 
    while (c != EOF && ! isalpha(c)) { 
    c = getchar(); 
    } 
    if (c == EOF) 
    return NULL; 
    while (isalpha(c)) { 
    if (i < WORDLEN - 1) { 
     w[i] = toupper(c); 
     i++; 
    } 
    c = getchar(); 
    } 
    w[i] = '\0'; 
    return w; 
} 
//print 
void print(NODE *p) { 
    for (; p != NULL; p = p->next) { 
    printf("%s %d\n",p->word, p->count); 
    } 
    printf("\n"); 
} 

//mergesort 

void mergesort_node(NODE **head) { 
    NODE *p, *q, *newhead; 
    newhead = *head; 

    if (newhead == NULL || newhead->next == NULL) { 
    return; 
    } 
    split_list(newhead, &p, &q); 
    mergesort_node(&p); 
    mergesort_node(&q); 
    *head = merge_sorted_lists(p, q); 
} 

//Splits list in middle, using fast/slow method 
void split_list(NODE *source, NODE **p, NODE **q) { 
    NODE *f, *s; 
    s = source; 
    f = source->next; 

    while (f != NULL) { 
    f = f->next; 
    if (f != NULL) { 
     s = s->next; 
     f = f->next; 
    } 
    } 
    *p = source; 
    *q = s->next; 
    s->next = NULL; 
} 

//Merges two individually sorted lists into one sorted list. 
NODE *merge_sorted_lists(NODE *source1, NODE *source2) { 
    NODE *p, *q, *e, *newhead; 
    p = source1; 
    q = source2; 
    e = newhead = NULL; 

    while (p != NULL && q != NULL) { 
    if (p->count >= q->count) {  //Compares the top items from the lists, 
     if (e == NULL) {    //and puts the largest as next in the new list. 
    e = p; 
    newhead = e; 
     }else{ 
    e->next = p; 
    e = e->next; 
     } 
     p = p->next; 
    }else if (p->count < q->count) { 
     if (e == NULL) { 
    e = q; 
    newhead = e; 
     }else{ 
    e->next = q; 
    e = e->next; 
     } 
     q = q->next; 
    } 
    } 
    if (p == NULL) {  //If one list ends, the rest of the other is added to the new list. 
    if (e == NULL) { 
     e = q; 
     newhead = e; 
    }else{ 
     e->next = q; 
    } 
    }else if (q == NULL) { 
    if (e == NULL) { 
     e = p; 
     newhead = e; 
    }else{ 
     e->next = p; 
    } 
    } 
    return newhead; 
}