基于strtok的文本文件单词排序与词频统计C语言问题

分析文本文件，对单词进行分词后按字母顺序排序并统计词频。
示例：

输入：The house is on the ground on earth.
输出：
earth - 1
ground - 1
house - 1
is - 1
on - 2
the - 2

已完成工作 #

已实现C语言中文本文件打开、按行读取、使用strtok分词、将分词转为小写的功能，对应代码如下：

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

void lower_string(char s[]);

int main()
{
    FILE *file;
    //char path[100];
    char ch[100];
    int characters;

    /* Input path of files to merge to third file
    printf("Enter source file path: ");
    scanf("%s", path);
    file = fopen(path, "r");*/
    file = fopen("test.txt", "r"); //testing w.o repeated input


    /* Check if file opened successfully */
    if (file == NULL)
    {
        printf("\nUnable to open file.\n");
        printf("Please check if file exists and you have read privilege.\n");

        exit(EXIT_FAILURE);
    }

    const char delim[] = " ,.;!?[\n]";
    char *token;
    int tokenNum;


    while (fgets(ch, sizeof(ch), file) != NULL)
    {
        lower_string(ch);
        token = strtok(ch, delim);

        while (token != NULL)
        {
            printf("Token:%s\n", token);
            token = strtok(NULL, delim);
            tokenNum++;
        }
    }


    printf("%d\n", tokenNum);  //total words testing
    /* Close files to release resources */
    fclose(file);

    return 0;
}
void lower_string(char s[])
{
    int c = 0;
    while (s[c] != '\0')
    {
        if (s[c] >= 'A' && s[c] <= 'Z')
        {
            s[c] = s[c] + 32;
        }
        c++;
    }
}

遇到的问题 #

卡在单词分组与排序环节，尝试过整数类型的有序链表实现，但不知如何结合strtok适配字符串场景，链表代码如下：

#include <stdio.h>
#include <stdlib.h>
//These structures are declared globally so they are available to all functions
//in the program.
typedef struct list_node_s
{               //defines structure of one node
    int key;            //key value - here an integer
    int count;          //frequency key value encountered in input
    struct list_node_s *restp;  //pointer to the next node in list = NULL if EOL

} list_node_t;

typedef struct              //defines head of list structure
{
    list_node_t *headp;     //pointer to first node in list, NULL if list is empty
    int size;               //current number of nodes in the list
} ordered_list_t;

//Prototypes
list_node_t * insert_in_order (list_node_t * old_listp, int new_key);
void insert (ordered_list_t * listp, int key);
int delete (ordered_list_t * listp, int target);
list_node_t * delete_ordered_node (list_node_t * listp, int target,int *is_deleted);

void print_list (ordered_list_t * listp);

#define SEND -999       //end of input sentinal
int main (void)
{
    int next_key;
    ordered_list_t my_list = {NULL, 0};

    printf("\n\nProgram to build, display and manipulate (delete) an Ordered Linked List \n");
    printf("\nAdapted from code in \"Problem Solving and Programming in C\" by J.R. Hanly and E.B. Koffman\n\n");
    printf ("enter integer keys - end list with %d\n", SEND);

/* build list by in-order insertions*/
    for (scanf ("%d", &next_key);
    next_key != SEND;
    scanf ("%d", &next_key))
    {
        insert (&my_list, next_key);
    }

/* Display completed list */
    printf ("\nOrdered list as built:\n");
    print_list(&my_list);

/* Process requested deletions */
    printf("enter key value for node to be removed from list or %d to end > ", SEND);

    for (scanf ("%d", &next_key);
    next_key != SEND;
    scanf ("%d", &next_key))
    {
        if (delete (&my_list, next_key))
        {
            printf ("%d deleted.\n  New list:\n", next_key);
            print_list (&my_list);
        }
        else
        {
            printf ("No deletion.  %d not found\n", next_key);
        }

    printf ("enter key value for node to be removed from list or %d to end > ", SEND);
    }
    return (0);
}

/* prints contents of a linked list Display the elements in the list pointed to by the pointer list.*/
void print_list (ordered_list_t * listp)
{
    list_node_t * tmp;
    for (tmp = listp->headp; tmp != NULL; tmp = tmp->restp)
    printf ("key = %d;  count = %d\n", tmp->key, tmp->count);
    printf ("\n\n");
}

//Inserts a new node containing new_key into an existing list and returns a pointer to the first node of the new list
list_node_t * insert_in_order (list_node_t * old_listp, int new_key)
{
    list_node_t * new_listp;
    if (old_listp == NULL)                  //check for end of list (EOL)
    {
        new_listp = (list_node_t *) malloc (sizeof (list_node_t));
        new_listp->key = new_key;
        new_listp->count = 1;
        new_listp->restp = NULL;
    }
    else if (old_listp->key == new_key)     //check for matching key, increment count
    {
        old_listp->count++;
        new_listp = old_listp;
    }
    else if (old_listp->key > new_key)      //Next node key value > new key, so insert new node at current location
    {
        new_listp = (list_node_t *) malloc (sizeof (list_node_t));
        new_listp->key = new_key;
        new_listp->count = 1;
        new_listp->restp = old_listp;
    }
    else
    {
        new_listp = old_listp;
        new_listp->restp = insert_in_order (old_listp->restp, new_key);
    }
return (new_listp);
}
//inserts a node into an ordered list_node_t
void insert (ordered_list_t * listp, int key)
{
++(listp->size);
listp->headp = insert_in_order (listp->headp, key);
}
//deletes the first node containing the target key from an ordered list; returns 1
//if target found & deleted, 0 otherwise (means target not in list)
int delete (ordered_list_t * listp, int target)
{
    int is_deleted;
    listp->headp = delete_ordered_node (listp->headp, target, &is_deleted);
    if (is_deleted)
     --(listp->size);       //reduce current node count (size); keep size of list current
    return (is_deleted);
}

/* deletes node containing target key from a list whose head is listp; returns a pointer
   to the modified list (incase it is the first node, pointed to by listp), frees
   the memory used by tyhe deleted node and sets a flag to indicate success (1) or
   failure (0; usually means no such node found).
*/

list_node_t * delete_ordered_node (list_node_t * listp, int target, int *is_deleted)
{
    list_node_t *to_freep, *ansp;

    // if list empty, nothing to do; return NULL
    printf ("check for empty list; target: %d \n", target);
    if (listp == NULL)
    {
        *is_deleted = 0;
        ansp = NULL;
    }

    //if first node is to be deleted, do it; relink rest of list to list header struct
    else if (listp->key == target)
    {
        printf ("at first node; target: %d \n", target);
        *is_deleted = 1;
        to_freep = listp;       //keeps track of node memory location to be freed
        ansp = listp->restp;
        free (to_freep);        //release the memory of the deleted node for reuse
    }

    //if target exists, it is further down the list (recursive step), make recursive call
    //to move down the list looking for the target value
    else
    {
        printf ("chase down list to find: %d \n", target);
        ansp = listp;
        ansp->restp = delete_ordered_node (listp->restp, target, is_deleted);
    }
    return (ansp);
}

BST代码疑问 #

新增二叉搜索树（BST）节点代码如下，但存在三个疑问：

#define WLENGTH 100
//Base Node info
struct node 
{
    char word[WLENGTH];
    int key;
    int freq;
    struct node *left, *right;
};

//Function to create a new node
struct node *newNode(char wordn, int item, int freqn) 
{
    struct node *temp = (struct node *) malloc(sizeof(struct node));
    temp->word = wordn;
    temp->key = item;
    temp->freq = freqn;
    temp->left = temp->right = NULL;
    return temp;
}

//Function to place nodes in order 
void inorder(struct node *root) 
{
    if (root != NULL) 
    {
        inorder(root->left);
        printf("%d ", root->key);
        inorder(root->right);
    }
}

/*Function to insert a new node with given key*/
struct node* insert(struct node* node, int key) 
{
    /* If the tree is empty, return a new node */
    if (node == NULL)
        return newNode(key);

    /* Otherwise, recur down the tree */
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);

    /* return the (unchanged) node pointer */
    return node;
}

1. 是否需要追踪key（假设对提取特定单词有用）；
2. 如何添加树的字母排序逻辑，求参考资料；
3. 如何将每个单词传入该树中。

问题解答 #

1. 是否需要追踪key？

不需要额外的key字段。你的需求是按单词字母排序并统计词频，单词本身就是天然的“键”，直接用word字段做比较和索引即可。额外的key只会增加冗余，除非你有后续扩展需求（比如给单词分配唯一ID），否则完全可以删掉这个字段。

2. 添加字母排序逻辑

C语言中用strcmp函数比较字符串的字典序，返回值规则：

• 返回值 < 0：第一个字符串字典序靠前
• 返回值 = 0：两个字符串相等
• 返回值 > 0：第一个字符串字典序靠后

修改BST代码，把基于整数key的比较替换为基于word的strcmp比较：

#include <string.h> // 需包含strcmp、strncpy头文件

#define WLENGTH 100
// 简化节点结构，移除冗余key字段
struct node 
{
    char word[WLENGTH];
    int freq;
    struct node *left, *right;
};

// 创建新节点，仅传入单词
struct node *newNode(const char *word) 
{
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    strncpy(temp->word, word, WLENGTH - 1);
    temp->word[WLENGTH - 1] = '\0'; // 确保字符串终止
    temp->freq = 1;
    temp->left = temp->right = NULL;
    return temp;
}

// 按字典序插入节点
struct node* insert(struct node* node, const char *word) 
{
    if (node == NULL)
        return newNode(word);

    int cmp = strcmp(word, node->word);
    if (cmp < 0)
        node->left = insert(node->left, word);
    else if (cmp > 0)
        node->right = insert(node->right, word);
    else
        node->freq++; // 单词已存在，词频+1

    return node;
}

// 中序遍历输出有序结果（字母升序）
void inorder(struct node *root) 
{
    if (root != NULL) 
    {
        inorder(root->left);
        printf("%s - %d\n", root->word, root->freq);
        inorder(root->right);
    }
}

BST的中序遍历天然会输出有序结果，这里正好是按字母升序排列的单词和词频，符合需求。

3. 将每个单词传入树中

在已有的分词代码基础上，定义BST根节点指针，每次获取到token（单词）时调用insert函数插入：

// 在main函数开头添加
struct node *root = NULL;

// 修改分词循环
while (token != NULL)
{
    root = insert(root, token); // 插入当前单词到BST
    token = strtok(NULL, delim);
    tokenNum++;
}

// 文件读取完成后输出结果
printf("\n词频统计结果：\n");
inorder(root);

注意你的lower_string函数已将所有单词转为小写，保证了统计的一致性，无需额外处理大小写。

内容的提问来源于stack exchange，提问作者NM215