2011-07-12 20:50:21Morris
a181. 逆逆向思考
a181. 逆逆向思考
內容 ：
Trie，又稱單詞查找樹或鍵樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用於統計和排序大量的字元串（但不僅限於字元串），
所以經常被搜索引擎系統用於文本詞頻統計。它的優點是：最大限度地減少無謂的字元串比較，查詢效率比哈希表高。
以上資料引用自維基百科
現在想請你模擬出一個簡單的 Trie
這是一個 Trie 結構的例子： 
在這個 Trie 結構中，保存了 A、to、tea、ted、ten、i、in、inn 這 8 個字元串，僅佔用 8 個位元組（不包括指針佔用的空間）。
怕有人因為瀏覽器問題, 排版亂掉
範例輸出 :
輸入說明
：
有多筆測試資料,
第一行有一個數字 N, 代表有 N 個字串
每個字串長度不超過 100,0000 個字元長度
所涵蓋的字元為 ASCII 33 ~ 127 (可顯示字元, 除了空白 32 外)
× 不給 N 的範圍, 是希望你用 linked list 做（用內建 or 動態陣列, 也是OK）
× 不用擔心記憶體的問題(用鏈結做的話)
× 記得用free();
輸出說明
：
對於每一組測資
將整個 Trie 輸出
按照 ASCII 由小排到大
詳情請參考範例輸出
範例輸入 ：
8
A
to
tea
ted
ten
i
in
inn
10
/
/7
/?
/7g
G
(
({
(n
/?J
/)
範例輸出 ：
[ ][A]
[i][n][n]
[t][e][a]
[d]
[n]
[o]
[ ][(][n]
[{]
[/][)]
[7][g]
[?][J]
[G]
提示
：
ZeroJudge 的 主機, 果真是進步了, 原本遞迴深度 10 萬就會 stack overflow
每想到現在出到 20 萬, 仍然不會 overflow
所以現在出到遞迴深度 100 萬, 你家的主機, 也差不多 10 萬, 就準備吃 RE 了
那你要怎麼寫呢 ?
出處
：
/**********************************************************************************/
/* Problem: a181 "逆逆向思考" from Trie */
/* Language: C */
/* Result: AC (1780ms, 25368KB) on ZeroJudge */
/* Author: morris1028 at 2011-07-11 19:15:03 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
typedef struct TrieNode {
char c;
struct TrieNode *kid, *peer;
}TrieNode;
typedef struct Trie {
struct TrieNode *root;
}Trie;
typedef struct Stack {
struct Stack *prev;
struct TrieNode *now, *curr;
int dv;
char work;
}Stack;
void Trieinit(Trie*);
void InsTrie(Trie*, char s[]);
void TriePrint(TrieNode*, int);
void Trieinit(Trie *tree) {
tree->root = (TrieNode*)malloc(sizeof(TrieNode));
tree->root->c = ' ';
tree->root->kid = tree->root->peer = NULL;
}
void TriePrint(TrieNode *now, int dv) {
Stack *stack, *temp;
stack = (Stack*)malloc(sizeof(Stack));
stack->prev = NULL, stack->now = now, stack->dv = dv, stack->work = 0;
int a;
char flag = 0, flag2;
while(stack != NULL) {
if(stack->work == 0) {
if(flag == 1) {
for(a = 0, flag = 0; a < stack->dv; a++)
printf(" ");
}
stack->curr = stack->now->kid, stack->work = 1;
printf("[%c]", stack->now->c);
}
flag2 = 0;
while(stack->curr != NULL) {
temp = (Stack*)malloc(sizeof(Stack));
temp->now = stack->curr, temp->prev = stack, temp->dv = stack->dv+1;
temp->work = 0;
stack->curr = stack->curr->peer;
stack = temp, flag2 = 1;
break;
}
if(flag2) continue;
if(stack->now->kid == NULL) flag = 1, puts("");
temp = stack->prev, free(stack->now), free(stack), stack = temp;
}
}
void InsTrie(Trie *tree, char s[]) {
TrieNode *curr = tree->root, *prev = NULL, *temp, *p;
int a;
for(a = 0; s[a]; a++) {
p = curr, curr = p->kid, prev = NULL;
while(curr != NULL && curr->c < s[a]) {
prev = curr, curr = curr->peer;
}
if(curr == NULL) {
temp = (TrieNode*)malloc(sizeof(TrieNode));
temp->c = s[a], temp->kid = temp->peer = NULL;
if(prev == NULL) p->kid = temp;
else prev->peer = temp;
curr = temp;
}
else {
if(curr->c == s[a]) {continue;}
temp = (TrieNode*)malloc(sizeof(TrieNode));
temp->c = s[a], temp->kid = NULL;
if(curr == p->kid) p->kid = temp, temp->peer = curr;
else prev->peer = temp, temp->peer = curr;
curr = temp;
}
}
}
main() {
int N;
char s[1000001];
while(scanf("%d", &N) == 1) {
Trie Tree;
Trieinit(&Tree);
getchar();
while(N--)
gets(s), InsTrie(&Tree, s);
TriePrint(Tree.root, 0);
}
return 0;
}