国产一级a片免费看高清,亚洲熟女中文字幕在线视频,黄三级高清在线播放,免费黄色视频在线看

      Trie樹(shù)，又稱(chēng)單詞查找樹(shù)，典型用于統(tǒng)計(jì)和排序大量字符串，查詢(xún)效率比哈希表高。(空間復(fù)雜度高)

它有3個(gè)基本特性：
　　1）根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符。
　　2）從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。
　　3）每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。

Trie的核心思想是空間換時(shí)間。利用字符串的公共前綴來(lái)降低查詢(xún)時(shí)間的開(kāi)銷(xiāo)以達(dá)到提高效率的目的。

Trie樹(shù)的結(jié)構(gòu)體：

Cpp代碼  

1. struct Trie_Node  
2. {  
3.     int id;//數(shù)據(jù)域  
4.     Trie_Node *next[26];//孩子結(jié)點(diǎn)  
5.     Trie_Node()  
6.     {  
7.         id = -1;  
8.         memset(next,0,sizeof(next));  
9.     }  
10. }*root;  

struct Trie_Node{	int id;//數(shù)據(jù)域	Trie_Node *next[26];//孩子結(jié)點(diǎn)	Trie_Node()	{		id = -1;		memset(next,0,sizeof(next));	}}*root;

Trie樹(shù)的更新操作(插入、查詢(xún)某字符串的數(shù)據(jù))

Cpp代碼  

1. int getNum(char *t)  
2. {  
3.     Trie_Node *p = root;  
4.     int i = 0,del;  
5.     while(t[i] != '\0')  
6.     {  
7.         del = t[i] - 'a';  
8.         if(p->next[del] == NULL)  
9.             p->next[del] = new Trie_Node();//動(dòng)態(tài)建樹(shù)，也可以換成靜態(tài)  
10.         p = p->next[del];  
11.         i++;  
12.     }  
13.     if(p->id == -1)  
14.         p->id = num++;  
15.     return p->id;  
16. }  

int getNum(char *t){	Trie_Node *p = root;	int i = 0,del;	while(t[i] != '\0')	{		del = t[i] - 'a';		if(p->next[del] == NULL)			p->next[del] = new Trie_Node();//動(dòng)態(tài)建樹(shù)，也可以換成靜態(tài)		p = p->next[del];		i++;	}	if(p->id == -1)		p->id = num++;	return p->id;}

POJ2513

題目大意：有n根筷子(n=250000)，每根筷子兩頭涂有顏色?，F(xiàn)在問(wèn)能否將所有筷子連起來(lái)，并且每?jī)筛曜拥倪B接點(diǎn)顏色都相同。

分析：題意不難理解，現(xiàn)在做一個(gè)轉(zhuǎn)換：將每種顏色作為一個(gè)結(jié)點(diǎn)，每根筷子兩頭的顏色之間連有一條邊。這樣，就形成了下面的圖：

     這樣問(wèn)題就轉(zhuǎn)化為：要求全部走完且經(jīng)過(guò)每條邊一次且僅一次，即一筆畫(huà)問(wèn)題。 這就成了歐拉路的判斷：

1.判斷該圖是否連通；

2.該圖的每個(gè)點(diǎn)的度要么全為偶數(shù)，要么有且僅有兩個(gè)度為奇數(shù)。

判斷圖是否是連通圖，可以用并查集。計(jì)算每個(gè)點(diǎn)的度，就是統(tǒng)計(jì)單詞出現(xiàn)的次數(shù)。因此聯(lián)想到用Trie樹(shù)統(tǒng)計(jì)單詞出現(xiàn)的次數(shù)，每次將單詞在Trie樹(shù)中查找，若該單詞在trie樹(shù)中第一次出現(xiàn)，則給它一個(gè)標(biāo)號(hào)(相當(dāng)于hash)。

POJ3630(1056)

題目大意：給出n個(gè)電話(huà)號(hào)碼(n=10000)，每個(gè)電話(huà)號(hào)碼長(zhǎng)度不超過(guò)10。要求是否滿(mǎn)足：每個(gè)電話(huà)號(hào)碼不能是其它號(hào)碼的前綴。

分析：在Trie樹(shù)中放置一個(gè)標(biāo)志位，表示從根節(jié)點(diǎn)到該結(jié)點(diǎn)是否是已經(jīng)輸入的號(hào)碼。

Cpp代碼  

1. bool findAndInsert(char *t)  
2. {  
3.     Trie_Node *p = root;  
4.     int i = 0,del;  
5.     while(t[i] != '\0')  
6.     {  
7.         if(p->exist)  
8.             return true;        //別的字符串是當(dāng)前字符串的前綴  
9.         del = t[i] - '0';  
10.         if(p->next[del] == NULL)  
11.         {  
12.             p->next[del] = &node[nodeNum];  
13.             nodeNum++;  
14.         }  
15.         p = p->next[del];  
16.         i++;  
17.     }  
18.     for(i = 0; i < 10; i++)      //當(dāng)前字符串是別的字符串的前綴  
19.     {  
20.         if(p->next[i] != NULL)  
21.             return true;  
22.     }  
23.     p->exist = true;  
24.     return false;  
25. }  

bool findAndInsert(char *t){	Trie_Node *p = root;	int i = 0,del;	while(t[i] != '\0')	{		if(p->exist)			return true;		//別的字符串是當(dāng)前字符串的前綴		del = t[i] - '0';		if(p->next[del] == NULL)		{			p->next[del] = &node[nodeNum];			nodeNum++;		}		p = p->next[del];		i++;	}	for(i = 0; i < 10; i++)		//當(dāng)前字符串是別的字符串的前綴	{		if(p->next[i] != NULL)			return true;	}	p->exist = true;	return false;}

POJ2001

題目大意：現(xiàn)在人們喜歡用縮寫(xiě)，比如carbon可以縮寫(xiě)為carb，但不能縮寫(xiě)為car。因?yàn)橛衏ar這個(gè)準(zhǔn)確的單詞。給你n個(gè)單詞(n=1000)，每個(gè)單詞長(zhǎng)度不超過(guò)20。求出每個(gè)單詞的最短縮寫(xiě)。

分析：在Trie樹(shù)中加入一個(gè)計(jì)數(shù)器num，表示以這個(gè)字符串為前綴的單詞有幾個(gè)。在查詢(xún)時(shí)，根據(jù)傳入的單詞一層層的往下找，找到num=1就說(shuō)明這個(gè)是第一次被使用，停止輸出。

Cpp代碼  

1. #include <iostream>  
2. const int MAX = 1001;  
3. char str[MAX][21];  
4. int nodeNum;  
5.   
6. struct Trie_Node  
7. {  
8.     int num;    //to remember how many words can reach here  
9.     Trie_Node *next[26];  
10.     Trie_Node()  
11.     {  
12.         num = 0;  
13.         memset(next,NULL,sizeof(next));  
14.     }  
15. };  
16. Trie_Node node[MAX*10],head;  
17.   
18. void insert(char *t)  
19. {  
20.     int i=0,del;  
21.     Trie_Node *p = &head;  
22.     while(t[i] != '\0')  
23.     {  
24.         del = t[i] - 'a';  
25.         if(p->next[del] == NULL)  
26.         {  
27.             p->next[del] = &node[nodeNum];  
28.             nodeNum++;  
29.         }  
30.         p->next[del]->num++;  
31.         p = p->next[del];  
32.         i++;  
33.     }  
34. }  
35.   
36. void query(char *t)  
37. {  
38.     int i = 0;  
39.     Trie_Node *p = &head;  
40.     while(t[i] != '\0')  
41.     {  
42.         printf("%c",t[i]);  
43.         p = p->next[t[i]-'a'];  
44.         if(p->num == 1)  
45.             break;  
46.         i++;  
47.     }  
48.     printf("\n");  
49. }  
50.   
51. int main()  
52. {  
53.     int i = 0;  
54.     nodeNum = 1;  
55.     while(scanf("%s",str[i]) != EOF)  
56.     {  
57.         insert(str[i]);  
58.         i++;  
59.     }  
60.     for(int j = 0; j < i; j++)  
61.     {  
62.         printf("%s ",str[j]);  
63.         query(str[j]);  
64.     }  
65.     return 0;  
66. }  

#include <iostream>const int MAX = 1001;char str[MAX][21];int nodeNum;struct Trie_Node{	int num;	//to remember how many words can reach here	Trie_Node *next[26];	Trie_Node()	{		num = 0;		memset(next,NULL,sizeof(next));	}};Trie_Node node[MAX*10],head;void insert(char *t){	int i=0,del;	Trie_Node *p = &head;	while(t[i] != '\0')	{		del = t[i] - 'a';		if(p->next[del] == NULL)		{			p->next[del] = &node[nodeNum];			nodeNum++;		}		p->next[del]->num++;		p = p->next[del];		i++;	}}void query(char *t){	int i = 0;	Trie_Node *p = &head;	while(t[i] != '\0')	{		printf("%c",t[i]);		p = p->next[t[i]-'a'];		if(p->num == 1)			break;		i++;	}	printf("\n");}int main(){	int i = 0;	nodeNum = 1;	while(scanf("%s",str[i]) != EOF)	{		insert(str[i]);		i++;	}	for(int j = 0; j < i; j++)	{		printf("%s ",str[j]);		query(str[j]);	}	return 0;}