C - 带单词和频率的排序链表

Question

我在完成编程类(class)的代码时遇到一些问题(我是 C 的绝对初学者)。目的是从标准输入(runfile < input.c)读取单词，计算它们的频率，并按字母顺序对列表进行排序(首先是大写单词)，示例输出:

Image Sample output

我在 Stack 上找到了一些代码，我对其进行了修改，到目前为止它会生成包含单词及其频率的输出。但是，我不知道如何按照上面的示例对列表进行排序。我们的老师建议，如果找到一个新单词，应该立即将其插入排序到链接列表中，他给了我们以下代码示例(摘自 this program ):

void addSorted(link *n, int x) {
  if (*n == NULL || x < (*n)->data) {
    *n = cons(x, *n);
  } else {
    addSorted(&((*n)->next), x);
  }
}

据我了解，“link *n”应该是指向下一个节点的指针，“data”在这种情况下保存整数，“cons”应该是此代码中用于构造新节点的函数或链接，不确定“int x”，我猜它是当前用于比较的整数。正如我所说，我在将最后一点调整到我的代码中时遇到了麻烦。我尝试调整我的 addWord() 函数，但它对我不起作用。下面是我迄今为止的工作代码:

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

//=============== STRUCTURE ==================
typedef struct word {
    char *mywords;              // list node with word pointer 
    int freq;                   // Frequency count
    struct word *pNext;         // Pointer to next node in linked list 
    } Word;

//======= INITIATION OF FUNCTIONS ===========
int readWord(char *temp_word, int temp_size);   // Given function to get words
void addWord(char *pWord);                      // Adds a word to the list or updates exisiting word
void printmywords(Word *pListNodes);            // Output list of words and frequencies
Word* construct(char *word);                    // Constructs list nodes

//============GLOBAL VARIABLES================
Word *pFirst = NULL;                  // Pointer to first node in linked list

//================ MAIN ======================    
int main () {

    char temp_word[32]; // temporary buffer to hold words
    int size = 10000;

    Word *pNode = NULL; // pointer to word counter

    while (readWord(temp_word, size)) { // Read all words from standard input

        addWord(temp_word); // Add word to list
    }

    // List the words and their counts
    pNode = pFirst;
    while(pNode != NULL)
    {
        printmywords(pNode);
        pNode = pNode->pNext;
    }
    printf("\n");

    // Free the allocated  memory
    pNode = pFirst;
    while(pNode != NULL)
    {
        free(pNode->mywords);        
        pFirst = pNode;           
        pNode = pNode->pNext;  
        free(pFirst);                  
    }
     return 0;
}

//================ FUNCTIONS =================

void printmywords(Word *pListNodes)
{
    printf("\n%-20s   %5d", pListNodes->mywords,pListNodes->freq); // output word and frequency
}

void addWord(char *word)
{
  Word *pNode = NULL;
  Word *pLast = NULL;

  if(pFirst == NULL)
  {
    pFirst = construct(word);
    return;
  }

  // Update frequency, if word in list
  pNode = pFirst;
  while(pNode != NULL)
  {
    if(strcmp(word, pNode->mywords) == 0)
    {
      ++pNode->freq;
      return;
    }
    pLast = pNode;            
    pNode = pNode->pNext;  
  }

  // Add new word, if not in list
  pLast->pNext = construct(word);
}

Word* construct(char *word)
{
  Word *pNode = NULL;
  pNode = (Word*)malloc(sizeof(Word));
  pNode->mywords = (char*)malloc(strlen(word)+1);
  strcpy(pNode->mywords, word);
  pNode->freq = 1;
  pNode->pNext = NULL;
  return pNode;
}

int readWord(char *temp_word, int temp_size) {
    char *p = temp_word;
    char c;

    // skip all non-word characters
    do {
        c = getchar();
        if (c == EOF) 
            return 0;
        } while (!isalpha(c));

    // read word chars
    do {
        if (p - temp_word < temp_size - 1)
        *p++ = c;
        c = getchar();
        } while (isalpha(c));

        // finalize word
        *p = '\0';
        return 1;
        }

感谢任何帮助。

Answer 1

好的，试试这两个函数:

Word *cons(char *word, Word *next) {
  Word *result = construct(word);
  if (result) {
    result->pNext = next;
  }
  else {
    printf("Out of memory in cons\n");
    exit(1);
  }
  return result;
}

void addSorted(Word **nodeRef, char *word) {
  Word *node = *nodeRef;

  /* strcmp will do a binary comparison, which suits your purpose
     because you want capitalized words before lower-case; the order
     of the arguments is important - <0 means the first argument should
     come before the second argument. */

  if ((node == NULL) || (strcmp(word, node->mywords) < 0)) {
    *nodeRef = cons(word, node);
  }
  else if (strcmp(word, node->mywords) == 0) {
    ++node->freq;
  }
  else {
    /* there's not really any point to using recursion on a linked
       list, except for the fact that it's really easy to use recursion
       on a linked list. On a vary large list, iteration would most likely
       be faster; however, professors really like to show how clever they
       are, so you're better off using it anyway. */

    addSorted(&node->pNext, word);
  }
}

其他几点:

char temp_word[32]; // temporary buffer to hold words
int size = 10000;

您有一个 31 个字符的缓冲区，但您告诉您的 readWord 函数它是 10K 个字符？

此外，不要转换 malloc() 的返回值。