節省空間的線索

我想用C來實現節省空間的線索這是我的結構：節省空間的線索

struct node { 
char val; //character stored in node 
int key; //key value if this character is an end of word 
struct node* children[256]; 
};

當我添加一個節點，它的指數是字符的無符號的字符轉換。例如，如果我想添加「c」，那麼

children[(unsigned char)'c']

是指向新添加的節點的指針。然而，這個實現需要我聲明一個256個元素的節點*數組。我想要做的是：

struct node** children;

，然後添加一個節點，只爲節點的malloc空間，並有

children[(unsigned char)'c']

指向新節點時。問題是，如果我先不給malloc malloc空間，那麼我顯然不能引用任何索引，否則這是一個很大的錯誤。

所以我的問題是：我如何實現一個trie，使它只存儲非空指針給它的子節點？

來源

2011-06-22 joe smallz

爲什麼不檢查'children'是否爲NULL？ – Drakosha

你有沒有考慮**定向非循環詞圖**？見http://en.wikipedia.org/wiki/Directed_acyclic_word_graph –

您可以嘗試使用de la Briandais trie，其中每個節點只有一個子指針，並且每個節點還有一個指向「兄弟」的指針，以便所有兄弟都有效地存儲爲鏈表而不是直接指向由父母。

來源

2011-06-22 15:21:56 Kevin

雖然這不會破壞遍歷時間嗎？ – kyun

@kyun是的，但正如其他答覆者指出的那樣，你不能既節省空間又節省時間。如果速度是一個問題，[ter trieary]（http://drdobbs.com/database/184410528）可能是一個不錯的選擇（每個節點有3個指針：一個指向「較小」的兄弟，一個指向「更大」兄弟姐妹，和一個孩子） – Kevin

不錯，我看到如何可以更快 – kyun

你不能真正擁有它並且既節省空間又在子節點中進行O（1）查找。

當你只爲這實際上添加的條目分配空間，而不是空指針，你可以不再做

children[(unsigned char)'c']

，你可以直接不再索引數組。

一種替代方法是簡單地通過兒童進行線性搜索。並存儲了多少項的附加計數children陣列已即

children[(unsigned char)'c'] = ...;

有可能成爲

for(i = 0; i < len; i++) { 
    if(children[i] == 'c') 
    break; 
} 
if(i == len) { 
    //...reallocate and add space for one item in children 
} 
children[i] = ...;

如果你的樹在一個級別有很多非空條目的結束，你可能按排序順序插入孩子並進行二分法搜索。或者您可以將兒童添加爲鏈接列表而不是數組。

來源

2011-06-22 15:25:22 Lyke

如果你只是想做一個英文關鍵字搜索，我認爲你可以最大限度地減少你的孩子的大小，從256到26 - 足以涵蓋26個字母a-z。

此外，您可以使用鏈表來保持兒童數量更小，這樣我們可以進行更有效的迭代。

我還沒有經過圖書館，但我認爲trie implementation將有所幫助。

來源

2012-05-28 11:56:39 fatjazz

通過將每個節點的子節點作爲節點的散列表，您既可以節省空間又可以保持不變的查找時間。特別是當涉及Unicode字符時，字典中的字符集不限於52 +一些，這比精確性更需要。通過這種方式，您可以同時保持使用樹狀結構的好處並節省時間和空間。

我還必須補充說，如果你使用的字符集接近無界，那麼有可能有鏈接的節點列表可能會很好。如果你喜歡難以控制的噩夢，你可以選擇一種混合方法，其中前幾個級別將他們的子女留在哈希表中，而較低級別上有他們的鏈表。對於一個真正的錯誤農場，選擇一個動態的錯誤農場，在每個鏈表通過一個閾值時，將其轉換爲一個哈希表。您可以輕鬆分攤成本。

可能性是無止境的！

來源

2013-01-15 22:58:58 bariscaglar

節省空間的線索

回答

相關問題