01/10/2018, 15:24
"index=key[i] -'a'" trong phần insert từ khóa vào Trie của đoạn code dưới có ý nghĩa gì?
Cho e hỏi trong phần insert từ khóa vào trong cây của đoạn code dưới thì sao index=key[i] -‘a’.
// C++ implementation of search and insert
// operations on Trie
#include <bits/stdc++.h>
using namespace std;
const int ALPHABET_SIZE = 26;
// trie node
struct TrieNode
{
struct TrieNode *children[ALPHABET_SIZE];
// isEndOfWord is true if the node represents
// end of a word
bool isEndOfWord;
};
// Returns new trie node (initialized to NULLs)
struct TrieNode *getNode(void)
{
struct TrieNode *pNode = new TrieNode;
pNode->isEndOfWord = false;
for (int i = 0; i < ALPHABET_SIZE; i++)
pNode->children[i] = NULL;
return pNode;
}
// If not present, inserts key into trie
// If the key is prefix of trie node, just
// marks leaf node
void insert(struct TrieNode *root, string key)
{
struct TrieNode *pCrawl = root;
for (int i = 0; i < key.length(); i++)
{
int index = key[i] - 'a';
if (!pCrawl->children[index])
pCrawl->children[index] = getNode();
pCrawl = pCrawl->children[index];
}
// mark last node as leaf
pCrawl->isEndOfWord = true;
}
Bài liên quan
index=key[i] -'a'là để chuyển ký tự về số nguyên. Do children đánh số từ 0 tới 25, mà ký tự thì đi từ ‘a’ tới ‘z’, nên phải chuyển ‘a’ về 0, ‘b’ về 1, …, ‘z’ về 25. Có nhiều cách chuyển, cách dễ hiểu nhất là lấy ký tự đó trừ đi ‘a’, vì trong C++ ký tự là 1 số nguyên 8-bit, nên có thể lấy ký tự trừ ký tự. ‘a’ - ‘a’ ra 0, ‘b’ - ‘a’ ra 1, v.v…bạn cho mk hỏi luôn là chỗ khai báo này ở đoạn đâu đấy nghĩ là gì đc ko?
struct TrieNode *children[ALPHABET_SIZE];
bạn học cây nhị phân rồi chắc biết 1 node của cây nhị phân có 2 children là left và right, còn ở đây cây này có tới tận 26 children, vì ký tự tiếng Anh có 26 ký tự. children[0] là aChild, children[1] là bChild, …, children[25] là zChild. Vì liệt kê ra khổ dâm quá nên người ta xài mảng cho khỏe. Nếu bạn thích bạn khai báo node cây nhị phân là
Node* children[2]cũng đượckhi khởi tạo 1 node của cây nhị phân bạn nhớ có dòng gán
left = NULLvàright = NULL, ở đây cũng tương tự với dòngchildren[i] = NULL;ok. tks bạn nhiều…