我正试图编写一个函数,在C中打印trie中的所有单词。我尝试了很多不同的方法,但没有得到任何输出。
这是我的结构:
typedef struct TNode
{
char letter;
struct TNode * children[ALPHABET_SIZE];
int count;
}TNode;
这是我创建trie的方法。它获取一个url,根据网页上的单词创建一个char数组,并根据该数组生成一个trie。
TNode * indexPage(const char* url)
{
char buffer[BUFFER_SIZE]; //Holds the characters from the webpage.
TNode * root; //The root node of the trie.
TNode * hold; //Temporarily holds the node to be added to the trie.
int charsRead; //The number of characters read from the webpage.
int i, j;
charsRead = getText(url, buffer, BUFFER_SIZE);
//Convert all uppercase letters to lowercase in buffer.
for(i = 0; i < charsRead; ++i)
{
if((buffer[i] >= 'A') && (buffer[i] <= 'Z'))
{
//Lowercase characters are 32 greater than uppercase, and
//the 'space' ASCII character equals 32.
buffer[i] += ' ';
}
}
buffer[BUFFER_SIZE - 1] = ' ';
//Initialize the root TNode.
root = (TNode *)malloc(sizeof(TNode));
root->letter = 0;
root->count = 0;
for(i = 0; i < ALPHABET_SIZE; ++i)
{
root->children[i] = NULL;
}
//Create the trie.
hold = root;
for(i = 0; i < charsRead; ++i)
{
if((buffer[i] >= 'a') && (buffer[i] <= 'z'))
{
for(j = 0; j < ALPHABET_SIZE; ++j)
{
if(hold->children[j] == NULL)
{
hold->children[j] = (TNode *)malloc(sizeof(TNode));
hold->children[j]->letter = buffer[i];
hold->children[j]->count = 0;
int x;
for(x = 0; x < ALPHABET_SIZE; ++x)
{
hold->children[j]->children[x] = NULL;
}
hold = hold->children[j];
break;
}
else if(hold->children[j]->letter == buffer[i])
{
hold = hold->children[j];
if((buffer[i + 1] < 'a') || (buffer[i + 1] > 'z'))
{
++(hold->count);
hold = root;
}
}
}
}
return root;
}
我已经确保getText函数正确地填充了缓冲区,并返回了它从网页中读取的字符数。
以下是我尝试的打印方法,但没有成功:
void printTrieContents(TNode * root, char * buffer, int buffIndex)
{
if(root == NULL)
{
return;
}
if(root->count != 0)
{
printf("t%sn", buffer);
}
int i;
for(i = 0; i < ALPHABET_SIZE; ++i)
{
if(root->children[i] != NULL)
{
buffer[buffIndex] = root->children[i]->letter;
printTrieContents(root->children[i], buffer, buffIndex + 1);
}
}
}
我在上面发现的许多页面都是按字母顺序创建的trie,但我必须按单词在页面上的出现顺序打印出来。如果有人能给我一个建议,我将不胜感激。谢谢!
trie只不过是一个按字母顺序高效组织的列表。就像任何按字母顺序排序的列表一样,它对创建的原始顺序一无所知。它是按字母顺序排列的。让我们看一个按字母顺序排列的列表。(如何用trie或任何其他方式表示它是完全不重要的(。
brown
dog
fox
jumps
lazy
over
quick
the
它是从什么文本构建的?谁知道呢。也许是"敏捷的棕色狐狸跳过懒惰的狗"。也许是"狗?狗懒。狐狸?狐狸棕色。跳跃?跳跃快。结束"。也许是无数其他文本中的任何一篇。我们不知道。
我们可以将额外的数据移植到列表中(同样,无论是trie还是其他什么都无关紧要(。数据可以包含一些关于插入顺序的信息。让我们试试:
brown [3]
dog [9]
fox [4]
jumps [5]
lazy [8]
over [6]
quick [2]
the [1,7]
这已经很重要了,但还多吗?重建原文需要什么?看起来我们需要提取数字,将它们与单词配对,将配对放在(例如(一个数组中,并使用数字作为关键字对它们进行排序。列表的字母结构对我们有帮助吗?一点也没有。同一个单词的所有出现都被放在一起了吗?一点也没有。为什么我们把它按字母顺序排列?为了使用按字母顺序排列的列表?好吧,那么,我们已经使用了一个按字母顺序排列的列表,用于滑稽低效和无用的中间存储。如果这就是这次演习的目的,那么我们已经实现了
还有一次,按字母顺序排序的列表是作为trie还是其他任何东西组织都无关紧要。
好的。我更改了代码,使其按字母顺序创建trie。事实上,我现在正在获得输出,但不是网页上的文字。这只是个玩笑。我觉得我现在很接近了,但我仍然不确定我做错了什么。
我将结构更改为:
typedef struct TNode
{
struct TNode * children[ALPHABET_SIZE]; //Children nodes
int count; //Word count
}TNode;
以下是制作trie:的函数
TNode * indexPage(const char* url)
{
char buffer[BUFFER_SIZE];
TNode * root;
TNode * hold;
int charsRead;
int i, j;
charsRead = getText(url, buffer, BUFFER_SIZE);
//printf("%sn",buffer);
//Convert all uppercase letters to lowercase in buffer.
for(i = 0; i < charsRead; ++i)
{
if((buffer[i] >= 'A') && (buffer[i] <= 'Z'))
{
buffer[i] += ' ';
}
}
//Initialize the root TNode.
root = (TNode *)malloc(sizeof(TNode));
root->count = 0;
for(i = 0; i < ALPHABET_SIZE; ++i)
{
root->children[i] = NULL;
}
//Create the trie.
hold = root;
for(i = 0; i < charsRead; ++i)
{
if((buffer[i] >= 'a') && (buffer[i] <= 'z'))
{
if(hold->children[(buffer[i] - 'a')] == NULL)
{
hold->children[(buffer[i] - 'a')] = (TNode *)malloc(sizeof(TNode));
hold->children[(buffer[i] - 'a')]->count = 0;
for(j = 0; j < ALPHABET_SIZE; ++j)
{
hold->children[(buffer[i] - 'a')]->children[j] = NULL;
}
}
if((buffer[i + 1] < 'a') || (buffer[i + 1] > 'z'))
{
++(hold->count);
hold = root;
}
else
{
hold = hold->children[(buffer[i] - 'a')];
}
}
}
//Return the pointer to the trie.
return root;
}
以下是打印trie中所有单词的功能:
void printTrieContents(TNode * root, char * buffer, int buffIndex)
{
int i;
if(root == NULL)
{
return;
}
if(root->count != 0)
{
buffer[buffIndex + 1] = ' ';
printf("t%sn",buffer);
buffIndex = 0;
}
for(i = 0; i < ALPHABET_SIZE; ++i)
{
if(root->children[i] != NULL)
{
buffer[buffIndex] = i + 'a';
printTrieContents(root->children[i], buffer, buffIndex + 1);
}
}
}
如果我使用一个包含pdf的网页(https://www.constitution.org/us_doi.pdf),我得到这样一个混乱的输出:
...
bnr
emy
ozy
yz
zk
zk
ll
nl
...