C Sorting trouble

How do I sort the occurrence of each word in descending order?

My current code is:

#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];
  NOD开发者_Python百科E *p = NULL;
  int i;

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

You can use any sorting algorithm for sorting you linked list. You can find explanation of sorting algos on wikipedia. Here are some of the most simple sort algorithms

Bubble Sort

Insert Sort

Merge Sort

these Wikipedia pages also contain pseudo code for these algorithms so it should be pretty straight forward translating these algos into C. Your starting point is "P" in main() i.e and you can use these algos to sort either in ascending or descending order.

The question is a bit vague -- do you want to learn something about sorting functions or do you just want the program to work? :-)

In case you just want something that works, you could consider using a dynamically expanding array instead of a linked list. That way you can realloc() when adding new entries, and sort with normal qsort()

As a side effect, you might also see less memory fragmentation compared to using a linked list which could have nice effects on the overall performance - especially if you do fewer and larger re-allocations. The code will also be more compact which could improve readability.

Update: Ah, I can't resist showing what I mean. If you use a dynamically expanding array, the function new_node could be implemented like this:

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

If you like this or not is a matter of personal preference. If this is usable or not really depends on the use case.

I finally managed to solve it thanks everyone for your help!

my code is now:

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