С сортировка неприятностей

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

Вы можете использовать любой алгоритм сортировки для связанного списка.Вы можете найти объяснение сортировки алгоритмов в Википедии.Вот некоторые из самых простых алгоритмов сортировки

Bubble Sort

Вставить сортировку

Объединить сортировку

эти страницы Википедии также содержат псевдокод для этих алгоритмов, так что перевод этих алгоритмов в C должен быть довольно простым. Ваша отправная точка - "P" в main (), т.е. вы можете использовать эти алгоритмы для сортировкив порядке возрастания или убывания.

Answer 2

Мне наконец удалось решить эту проблему, спасибо всем за помощь!

мой код теперь:

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

Answer 3

Вопрос немного неясен - вы хотите узнать что-то о функциях сортировки или вы просто хотите, чтобы программа работала?: -)

Если вам просто нужно что-то, что работает, вы можете рассмотреть возможность использования динамически расширяемого массива вместо связанного списка.Таким образом, вы можете использовать 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;
    }
}

Если вам нравится , это вопрос личного предпочтения или нет.Если это годен к употреблению или нет, зависит от варианта использования.