时间戳

首页 > 解决方案 > 如何从文本中插入单词并通过 bst 跟踪词频？

c - 如何从文本中插入单词并通过 bst 跟踪词频？

问题描述

我的作业是一个字典结构，其中包含一棵树来存储单词。在 main.c 中，我创建了一个名为 stopwords 的字典，它从文件中读取单词并将单词插入到字典中。在 dict.c 中，我需要实现一个可以从 main 更新和显示字典的数据结构。

Q1。我的插入功能是否可以更新 main.c 中的停用词？ Q2。我应该如何打印字典中的每个单词和频率？看来我不能使用递归作为传入 Dict 类型。谢谢

dict.c

typedef struct _DictNode *Link;
typedef struct _DictNode *Tree;
typedef struct _DictRep *Dict;

typedef struct _WFreq {
   char  *word;  
   int    freq;  
} WFreq;

typedef struct  _DictNode {
   WFreq  data;
   Link   left;
   Link   right;
   //int   height;
} DictNode;

struct _DictRep { //pointer to the root node 
   Link tree;
};

// create new empty Dictionary
Dict newDict() 
{
   Dict new = malloc(sizeof(*new));
   //if (new == NULL) err (EX_OSERR, "couldn't allocate Dict");
   new->tree = NULL;
   return new;
}

// insert new word into Dictionary
// return 0 when word is found already and 1 when not found
//WFreq *DictInsert(Dict d, char *w)
int DictInsert(Dict d, char *w)
{
   int direction;
   Link temp = malloc(sizeof(DictNode));
   temp->left = NULL;
   temp->right = NULL;
   temp->data.word = w;
   temp->data.freq = 1;

   if (d->tree == NULL){
      d->tree = temp;
   } else {
      Link prev = NULL;
      Link this = d->tree;
      
      //find the node that should point to this node
      while (this != NULL){
         prev = this;
         if((direction = strcmp(this->data.word, temp->data.word)) == 0){
            //word already exists 
            this->data.freq++;
            free(temp);
            return 0;
         } else {
            if (direction < 0)
               this = this->right;
            else 
               this = this->left;
         }
      }
      //update the prev node 
      if (direction < 0)
         prev->right = temp;
      else
         prev->left = temp;
   }
   return 1;
}

// print a dictionary
void showDict(Dict d)
{
   //recursive?
   printf("%s %d\n",d->tree->data.word, d->tree->data.freq);
   return;
}

主程序

FILE *in = fopen("stopwords", "r");
   Dict stopwords = newDict();
   char *stop_word = malloc(MAXWORD);
   while(fscanf(in, "%s", stop_word)!=EOF){
      //reading in characters 
      DictInsert(stopwords, stop_word);
   }
   showDict(stopwords);
   fclose(in);
   free(stop_word);

标签： cbinary-search-tree

解决方案

Q1。我的插入功能是否可以更新 main.c 中的停用词？

win 参数DictInsert()指向stop_word在“main.c”中分配的缓冲区，但该缓冲区被“停用词”文件中的每个单词重用。因此，DictInsert()需要将字复制到一个新的缓冲区。

如果非标准strdup()功能可用，您可以使用它：

temp->data.word = strdup(w);

如果strdup()不可用，您可以这样做：

temp->data.word = malloc(strlen(w) + 1);
strcpy(temp->data.word, w);

如果找到重复的单词，则temp->data.word在释放之前释放temp：

free(temp->data.word);
free(temp);

Q2。我应该如何打印字典中的每个单词和频率？看来我不能使用递归作为传入 Dict 类型。

您可以定义一个Link递归打印的函数：

void showDictHelper(Link tree)
{
    if (tree == NULL)
        return;
    showDictHelper(tree->left);
    printf("%s %d\n",tree->data.word, tree->data.freq);
    showDictHelper(tree->right);
}

然后从以下位置调用它showDict()：

void showDict(Dict d)
{
    showDictHelper(d->tree);
}

推荐阅读