使用链表计算 C 中未知但巨大的文本文件中的单词
Count words from a text file of unknown but massive size in C using linked list
我会数字。我正在使用包含单词和计数的 struct 的链表。它适用于小文件，但需要我定义最大文本长度。据我所知，文本文件可能超过数 GB。我怎样才能将其更改为不需要 #define MAX_TEXT_LENGTH？我应该使用 malloc() 吗？如果是，我应该将 malloc() 应用到什么地方？最终目标是然后按字母顺序对所有内容进行排序并按频率打印单词，但是在我阅读单词并进行计数后这应该很容易。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_WORD 512
#define MAX_TEXT_LENGTH 10000
typedef struct word
{
char *str; /* Stores the word */
int freq; /* Stores the frequency */
struct word *pNext; /* Pointer to the next word counter in the list */
} Word;
// ===========================================
// FUNCTION PROTOTYPES
//============================================
int getNextWord(FILE *fp, char *buf, int bufsize); /* Given function to get words */
void addWord(char *pWord); /* Adds a word to the list or updates exisiting word */
void show(Word *pWordcounter); /* Outputs a word and its count of occurrences */
Word* createWordCounter(char *word); /* Creates a new WordCounter structure */
// ===========================================
// GLOBAL VARIABLES
//============================================
Word *pStart = NULL; /* Pointer to first word counter in the list */
int totalcount = 0; /* Total amount of words */
int uniquecount = 0; /* Amount of unique words */
// ===========================================
// MAIN
//============================================
int main (int argc, char *argv[]) {
FILE * fp; /* File pointer */
fp = fopen(argv[1],"r"); /* Read text from here */
char buf[MAX_WORD]; /* buf to hold the words */
int size = MAX_TEXT_LENGTH; /* Size */
Word *pCounter = NULL; /* Pointer to Word counter */
/* Read all words from text file */
while (getNextWord(fp, buf, size))
{
/* Add the word to the list */
addWord(buf);
/* Increment the total words counter */
totalcount++;
}
/* Loop through list and figure out the number of unique words */
pCounter = pStart;
while(pCounter != NULL)
{
uniquecount++;
pCounter = pCounter->pNext;
}
/* Print Summary */
printf("\nSUMMARY:\n\n");
printf(" %d words\n", totalcount); /* Print total words */
printf(" %d unique words\n", uniquecount); /* Print unique words */
/* List the words and their counts */
pCounter = pStart;
while(pCounter != NULL)
{
show(pCounter);
pCounter = pCounter->pNext;
}
printf("\n");
/* Free the allocated memory*/
pCounter = pStart;
while(pCounter != NULL)
{
free(pCounter->str);
pStart = pCounter;
pCounter = pCounter->pNext;
free(pStart);
}
/* Close file */
fclose(fp);
return 0;
}
// ===========================================
// FUNCTIONS
//============================================
void show(Word *pWordcounter)
{
printf("\n%-30s %5d", pWordcounter->str,pWordcounter->freq);
}
void addWord(char *word)
{
Word *pCounter = NULL;
Word *pLast = NULL;
if(pStart == NULL)
{
pStart = createWordCounter(word);
return;
}
/* If the word is in the list, increment its count */
pCounter = pStart;
while(pCounter != NULL)
{
if(strcmp(word, pCounter->str) == 0)
{
++pCounter->freq;
return;
}
pLast = pCounter;
pCounter = pCounter->pNext;
}
/* Word is not in the list, add it */
pLast->pNext = createWordCounter(word);
}
Word* createWordCounter(char *word)
{
Word *pCounter = NULL;
pCounter = (Word*)malloc(sizeof(Word));
pCounter->str = (char*)malloc(strlen(word)+1);
strcpy(pCounter->str, word);
pCounter->freq = 1;
pCounter->pNext = NULL;
return pCounter;
}
int getNextWord(FILE *fp, char *buf, int bufsize) {
char *p = buf;
char c;
//skip all non-word characters
do
{
c = fgetc(fp);
if (c == EOF)
return 0;
} while (!isalpha(c));
//read word chars
do
{
if (p - buf < bufsize - 1)
*p++ = tolower(c);
c = fgetc(fp);
} while (isalpha(c));
//finalize word
*p = '[=10=]';
return 1;
}
代码有错误，MAX_TEXT_LENGTH不需要原样。限制应该是确保单个单词不超过 word 缓冲区的长度。在您的程序中将 'buf' 的名称更改为 'nextWordInFileBuffer' 以查看它是否更有意义。
详细说明 John 在他的回答中指出的错误...并对您的整体问题添加一些评论...
> 我知道怎么数字了。我正在使用链表
> 个包含单词和计数的结构。有用
> 在小文件上，但需要我定义最大文本
> 长度。
> 据我所知，文本文件可能超过
> 数 GB。
你的代码看起来很可靠，除了下面的几点我不会改变太多。
我相信您必须对任何特定 "word" 的大小设置上限。
但是文件的整体大小呢？你写的没问题；它只是内存有限。
没错，一个文本文件可以有数 GB（甚至更长）。
但看起来您的代码已经可以有效地处理无限数量的唯一单词。
顺便说一句：我喜欢你的小写；最小化列表大小，找到更多 "common" 个单词。
您的 MAX_WORD 大小已经是 512 个字符。
建议 1：考虑计算您超过 MAX_WORD 尺寸的次数（如果有），并在 运行.
结束时打印出该状态
> 如何将其更改为不需要#define MAX_TEXT_LENGTH？
关于MAX_TEXT_LENGTH，我认为是错误的。约翰在他的回答中也提到了这一点。继续阅读... :-)
> 我应该使用 malloc() 吗？如果是，我应该将 malloc() 应用到什么地方？
我认为不需要更多 malloc()，您已经有了一个很好的自增长链表。
建议2：直接删除MAX_TEXT_LENGTH，完全看不出哪里需要。
事实上，原始代码看起来允许 "buf" 变量上的缓冲区超过 运行s（这将是 "error" 部分）。
更具体地说，"buf" 的容量只有 MAX_WORD，但您的原始代码告诉 getNextWord() 使用 MAX_TEXT_LENGTH，这比 MAX_TEXT_LENGTH 大很多（非常多） MAX_WORD.
考虑将代码修改为如下所示：
/* Read all words from text file */
/* original: */
/* while (getNextWord(fp, buf, size)) */
/* NOTE: remeber size was originally MAX_TEXT_LENGTH (error?). */
/* You could just use MAX_WORD here and delete "size" while you're at it. */
while (getNextWord(fp, buf, MAX_WORD))
{
/* Add the word to the list */
addWord(buf);
/* Increment the total words counter */
totalcount++;
}
> 最终目标是然后按字母顺序对所有内容进行排序并打印
> 有频率的词，但是看了之后应该很容易
> 字数。
r.e。排序，对于 "stretch goal"，请参阅下面的建议 #4。
建议3：为了好玩，你可能还想在最后打印一个你的字长频率图表。
例如：
Freq : Word Length
4851 : 1
205 : 2
104 : 3
...etc...
1 : 406
建议 4：不是通过在末尾添加每个新词来增加列表，如果使用 strcmp( ) 来判断你是否超出了新词的可能加点。这个想法是你可以避免每次添加一个可能位于中间某处的单词时都必须遍历整个列表。不过这种方法更复杂，因为您必须小心处理将某些内容拼接到中间列表以及边缘情况（例如在开始时处理新插入）。
但是，当您到达输入文件的末尾时，列表已经排序，因此可能值得考虑一下这种设计方法。
祝你好运，我觉得你写的代码还不错。
我会数字。我正在使用包含单词和计数的 struct 的链表。它适用于小文件，但需要我定义最大文本长度。据我所知，文本文件可能超过数 GB。我怎样才能将其更改为不需要 #define MAX_TEXT_LENGTH？我应该使用 malloc() 吗？如果是，我应该将 malloc() 应用到什么地方？最终目标是然后按字母顺序对所有内容进行排序并按频率打印单词，但是在我阅读单词并进行计数后这应该很容易。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_WORD 512
#define MAX_TEXT_LENGTH 10000
typedef struct word
{
char *str; /* Stores the word */
int freq; /* Stores the frequency */
struct word *pNext; /* Pointer to the next word counter in the list */
} Word;
// ===========================================
// FUNCTION PROTOTYPES
//============================================
int getNextWord(FILE *fp, char *buf, int bufsize); /* Given function to get words */
void addWord(char *pWord); /* Adds a word to the list or updates exisiting word */
void show(Word *pWordcounter); /* Outputs a word and its count of occurrences */
Word* createWordCounter(char *word); /* Creates a new WordCounter structure */
// ===========================================
// GLOBAL VARIABLES
//============================================
Word *pStart = NULL; /* Pointer to first word counter in the list */
int totalcount = 0; /* Total amount of words */
int uniquecount = 0; /* Amount of unique words */
// ===========================================
// MAIN
//============================================
int main (int argc, char *argv[]) {
FILE * fp; /* File pointer */
fp = fopen(argv[1],"r"); /* Read text from here */
char buf[MAX_WORD]; /* buf to hold the words */
int size = MAX_TEXT_LENGTH; /* Size */
Word *pCounter = NULL; /* Pointer to Word counter */
/* Read all words from text file */
while (getNextWord(fp, buf, size))
{
/* Add the word to the list */
addWord(buf);
/* Increment the total words counter */
totalcount++;
}
/* Loop through list and figure out the number of unique words */
pCounter = pStart;
while(pCounter != NULL)
{
uniquecount++;
pCounter = pCounter->pNext;
}
/* Print Summary */
printf("\nSUMMARY:\n\n");
printf(" %d words\n", totalcount); /* Print total words */
printf(" %d unique words\n", uniquecount); /* Print unique words */
/* List the words and their counts */
pCounter = pStart;
while(pCounter != NULL)
{
show(pCounter);
pCounter = pCounter->pNext;
}
printf("\n");
/* Free the allocated memory*/
pCounter = pStart;
while(pCounter != NULL)
{
free(pCounter->str);
pStart = pCounter;
pCounter = pCounter->pNext;
free(pStart);
}
/* Close file */
fclose(fp);
return 0;
}
// ===========================================
// FUNCTIONS
//============================================
void show(Word *pWordcounter)
{
printf("\n%-30s %5d", pWordcounter->str,pWordcounter->freq);
}
void addWord(char *word)
{
Word *pCounter = NULL;
Word *pLast = NULL;
if(pStart == NULL)
{
pStart = createWordCounter(word);
return;
}
/* If the word is in the list, increment its count */
pCounter = pStart;
while(pCounter != NULL)
{
if(strcmp(word, pCounter->str) == 0)
{
++pCounter->freq;
return;
}
pLast = pCounter;
pCounter = pCounter->pNext;
}
/* Word is not in the list, add it */
pLast->pNext = createWordCounter(word);
}
Word* createWordCounter(char *word)
{
Word *pCounter = NULL;
pCounter = (Word*)malloc(sizeof(Word));
pCounter->str = (char*)malloc(strlen(word)+1);
strcpy(pCounter->str, word);
pCounter->freq = 1;
pCounter->pNext = NULL;
return pCounter;
}
int getNextWord(FILE *fp, char *buf, int bufsize) {
char *p = buf;
char c;
//skip all non-word characters
do
{
c = fgetc(fp);
if (c == EOF)
return 0;
} while (!isalpha(c));
//read word chars
do
{
if (p - buf < bufsize - 1)
*p++ = tolower(c);
c = fgetc(fp);
} while (isalpha(c));
//finalize word
*p = '[=10=]';
return 1;
}
代码有错误，MAX_TEXT_LENGTH不需要原样。限制应该是确保单个单词不超过 word 缓冲区的长度。在您的程序中将 'buf' 的名称更改为 'nextWordInFileBuffer' 以查看它是否更有意义。
详细说明 John 在他的回答中指出的错误...并对您的整体问题添加一些评论...
> 我知道怎么数字了。我正在使用链表
> 个包含单词和计数的结构。有用
> 在小文件上，但需要我定义最大文本
> 长度。
> 据我所知，文本文件可能超过
> 数 GB。
你的代码看起来很可靠，除了下面的几点我不会改变太多。 我相信您必须对任何特定 "word" 的大小设置上限。 但是文件的整体大小呢？你写的没问题；它只是内存有限。
没错，一个文本文件可以有数 GB（甚至更长）。 但看起来您的代码已经可以有效地处理无限数量的唯一单词。
顺便说一句：我喜欢你的小写；最小化列表大小，找到更多 "common" 个单词。
您的 MAX_WORD 大小已经是 512 个字符。 建议 1：考虑计算您超过 MAX_WORD 尺寸的次数（如果有），并在 运行.
结束时打印出该状态
> 如何将其更改为不需要#define MAX_TEXT_LENGTH？
关于MAX_TEXT_LENGTH，我认为是错误的。约翰在他的回答中也提到了这一点。继续阅读... :-)
> 我应该使用 malloc() 吗？如果是，我应该将 malloc() 应用到什么地方？
我认为不需要更多 malloc()，您已经有了一个很好的自增长链表。
建议2：直接删除MAX_TEXT_LENGTH，完全看不出哪里需要。 事实上，原始代码看起来允许 "buf" 变量上的缓冲区超过 运行s（这将是 "error" 部分）。
更具体地说，"buf" 的容量只有 MAX_WORD，但您的原始代码告诉 getNextWord() 使用 MAX_TEXT_LENGTH，这比 MAX_TEXT_LENGTH 大很多（非常多） MAX_WORD.
考虑将代码修改为如下所示：
/* Read all words from text file */
/* original: */
/* while (getNextWord(fp, buf, size)) */
/* NOTE: remeber size was originally MAX_TEXT_LENGTH (error?). */
/* You could just use MAX_WORD here and delete "size" while you're at it. */
while (getNextWord(fp, buf, MAX_WORD))
{
/* Add the word to the list */
addWord(buf);
/* Increment the total words counter */
totalcount++;
}
> 最终目标是然后按字母顺序对所有内容进行排序并打印
> 有频率的词，但是看了之后应该很容易
> 字数。
r.e。排序，对于 "stretch goal"，请参阅下面的建议 #4。
建议3：为了好玩，你可能还想在最后打印一个你的字长频率图表。 例如：
Freq : Word Length
4851 : 1
205 : 2
104 : 3
...etc...
1 : 406
建议 4：不是通过在末尾添加每个新词来增加列表，如果使用 strcmp( ) 来判断你是否超出了新词的可能加点。这个想法是你可以避免每次添加一个可能位于中间某处的单词时都必须遍历整个列表。不过这种方法更复杂，因为您必须小心处理将某些内容拼接到中间列表以及边缘情况（例如在开始时处理新插入）。
但是，当您到达输入文件的末尾时，列表已经排序，因此可能值得考虑一下这种设计方法。
祝你好运，我觉得你写的代码还不错。