在第0層，所有的關鍵碼根據它們第0位字符, 被劃分到互不相交的27個類中。

因此，root→brch.link[i] 指向一棵子Trie樹，該子Trie樹上所包含的所有關鍵碼都是以第 i 個英文字母開頭。

若某一關鍵碼第 j 位字母在英文字母表中順序為 i ( i = 0, 1, ?, 26 ), 則它在Trie樹的第 j 層分支結點中從第 i 個指針向下找第 j+1 位字母所在結點。當一棵子Trie樹上只有一個關鍵碼時，就由一個元素結點來代替。在這個結點中包含有關鍵碼，以及其它相關的信息，如對應數據對象的存放地址等。

Trie樹的類定義：

const int MaxKeySize = 25; //關鍵碼最大位數

typedef struct { //關鍵碼類型
char ch[MaxKeySize]; //關鍵碼存放數組
int currentSize; //關鍵碼當前位數
} KeyType;

class TrieNode { //Trie樹結點類定義
friend class Trie;
protected:
enum { branch, element } NodeType; //結點類型
union NodeType { //根據結點類型的兩種結構
struct { //分支結點
int num; //本結點關鍵碼個數
TrieNode *link[27]; //指針數組
} brch;
struct { //元素結點
KeyType key; //關鍵碼
recordNode *recptr; //指向數據對象指針
} elem;
}
}

class Trie { //Trie樹的類定義
private:
TrieNode *root, *current;
public:
RecordNode* Search ( const keyType & );
int Insert ( const KeyType & );
int Delete ( const KeyType & );
}

10.3.2 Trie樹的搜索

為了在Trie樹上進行搜索，要求把關鍵碼分解成一些字符元素, 并根據這些字符向下進行分支。

函數 Search 設定 current = NULL, 表示不指示任何一個分支結點, 如果 current 指向一個元素結點 elem，則 current→elem.key 是 current 所指結點中的關鍵碼。

Trie樹的搜索算法：

RecordNode* Trie::Search ( const KeyType & x ) {
k = x.key;
concatenate ( k, ‘b’ );
current = root;
int i = 0; //掃描初始化
while ( current != NULL && current→NodeType != element && i <= x.ch[i] ) {
current = current→brch.link[ord (x.ch[i])];
i = i++;
};
if ( current != NULL && current→NodeType == element && current→elem.key == x )
return current→recptr;
else
return NULL;
}

經驗證，Trie樹的搜索算法在最壞情況下搜索的時間代價是 O(l)。其中, l 是Trie樹的層數(包括分支結點和元素結點在內)。

在用作索引時，Trie樹的所有結點都駐留在磁盤上。搜索時最多做 l 次磁盤存取。

當結點駐留在磁盤上時，不能使用C++的指針 (pointer) 類型, 因為C++不允許指針的輸入 / 輸出。在結點中的 link 指針可改用整型(integer) 實現。

10.3.3 在Trie樹上的插入和刪除

示例：插入關鍵碼bobwhite和bluejay。
a. 插入 x = bobwhite 時，首先搜索Trie樹尋找 bobwhite 所在的結點。
b. 如果找到結點, 并發現該結點的 link[‘o’] = NULL。x不在Trie樹中, 可以在該處插入。插入結果參看圖。
c. 插入 x = bluejay時，用Trie樹搜索算法可找到包含有 bluebird 的元素結點，關鍵碼bluebird 和 bluejay 是兩個不同的值，它們在第5個字母處不匹配。從 Trie樹沿搜索路徑，在第4層分支。插入結果參看圖。

在Trie樹上插入bobwhite和bluejay后的結果 ：

示例：考慮在上圖所示Trie樹中刪除bobwhite。此時，只要將該結點link[‘o’]置為0 (NULL)即可，Trie樹的其它部分不需要改變。

考慮刪除 bluejay。刪除之后在標記為δ3 的子Trie樹中只剩下一個關鍵碼，這表明可以刪去結點δ3 ，同時結點 ρ 向上移動一層。對結點δ2 和δ1 可以做同樣的工作，最后到達結點б。因為以б 為根的子Trie樹中有多個關鍵碼，所以它不能刪去，令該結點link[‘l’] = ρ即可。

為便于Trie樹的刪除, 在每個分支結點中設置了一個 num 數據成員，它記載了結點中子女的數目。

Trie ,又稱 單詞查找樹 ,是一種 樹 形結構，用于保存大量的 字符串 。它的優點是：利用字符串的公共 前綴 來節約存儲空間。

性質

它有3個基本性質：

1. 根節點 不包含 字符 ，除根節點外每一個節點都只包含一個 字符 。
2. 從 根節點 到某一 節點 ， 路徑 上經過的 字符 連接起來，為該 節點 對應的 字符串 。
3. 每個 節點 的所有 子節點 包含的 字符 都不相同。

例子

這是一個Trie結構的例子：

在這個Trie結構中，保存了t、to、te、tea、ten、i、in、inn這8個字符串，僅占用8個 字節 （不包括 指針 占用的空間）

問題：

一、 一個文本文件有多行，每行為一個URL。請編寫代碼，統計出URL中的文件名及出現次數。

　　a) 文件名不包括域名、路徑和URL參數，例如http://www.rs.com/n.op/q/rs?id=1中的文件名是rs。

　　b) 部分URL可能沒有文件名，例如http://www.abc.com/，這類統計為“空文件名”。

　　c) 出現在不同URL中的相同文件名視為同一文件名，例如http://www.ceshi.com/hi.php和ftp://ftp.cdef.com/hi.php為同一文件名

　　文件內容示例如下：

　　http://www.test.com/abc/de/fg.php?id=1&url=http://www.test.com/index.html

　　http://www.ceshi.com/hi.jsp

　　ftp://ftp.ceshi.com/hi.jsp

　　http://www.hello.com/cw/hi.jsp?k=8

　　http://www.hi.com/jk/l.html?id=1&s=a.html

　　http://www.rs.com/n.op/q/rs?id=1

　　http://www.abc.com/

二、 一個簡單的論壇系統，以數據庫儲存如下數據：

　　用戶名，email，主頁，電話，聯系地址，發帖標題，發帖內容，回復標題，回復內容。

　　每天論壇訪問量300萬左右，更新帖子10萬左右。

　　請給出數據庫表結構設計，并結合范式簡要說明設計思路。

三、 現有兩個文件，

　　a)數據文件A，格式為：關鍵詞、IP地址、時間，記錄條數為1000萬左右，該文件是無序排列的。

　　b)數據文件B是關鍵詞ID到關鍵詞的對應表文件，格式為：ID、關鍵詞，記錄條數在100萬左右，也是無序排列的。該對應表中的記錄是一一對應的，不存在ID或者關鍵詞重復的情況。

　　要求將數據文件A對應的關鍵詞替換為B中的ID，生成新的數據文件C，數據文件C的格式為：關鍵詞ID、IP地址、時間。

　　請設計一個程序，實現上述功能，并分析時間復雜度和空間復雜度。運行程序所使用的服務器的內存為1G，硬盤足夠大。(至少要給出關鍵算法和設計思路)

    
      第一題
    
  

    
      　　簡評
    
  

    　　百度的主要業務是搜索，搜索的基本原理如下
  

    
      
        　　1．
      
    
    編寫爬蟲程序到互聯網上抓取網頁海量的網頁。
  

    
      
        　　2．
      
    
    將抓取來的網頁通過抽取，以一定的格式保存在能快速檢索的文件系統中。
  

    
      
        　　3．
      
    
    把用戶輸入的字符串進行拆分成關鍵字去文件系統中查詢并返回結果。
  

    　　由以上
    
      3
    
    點可見，字符串的分析，抽取在搜索引擎中的地位是何等重要。
  

    　　因此，百度的筆試面試題中，出現這樣的題就變得理所當然了。
    
      

      
    
  

　　以下是該題的 java 實現，代碼如下：

importjava.net. * ;
importjava.io. * ;
importjava.util. * ;

/**/ /* *
*@authortzy
*在j2sdk1.4.2下測試通過
*/
public class FileNameStat
... {
private StringsrcPath; // 要統計的文件路徑
private MapstatMap; // 用于統計的map

public FileNameStat(StringsrcPath)
... {
this .srcPath = srcPath;
statMap = new TreeMap();
}

/**/ /* 獲得要統計的URL的文件名 */
public StringgetFileName(StringurlString)
... {
URLurl = null ;
StringfilePath = null ;
StringfileName = null ;
try
... {
url = new URL(urlString);
filePath = url.getPath();
int index = 0 ;
if ((index = filePath.lastIndexOf( " / " )) !=- 1 )
... {
fileName = filePath.substring(index + 1 );
}
else
... {
fileName = "" ;
}
}
catch (MalformedURLExceptione)
... {
}
return fileName;
}

/**/ /* 統計指定文件名的個數 */
public void stat(Stringfilename)
... {
Integercount = null ;
if (statMap. get (filename) != null )
... {
count = (Integer)statMap. get (filename);
count = new Integer(count.intValue() + 1 );
}
else
... {
count = new Integer( 1 );
}
statMap.put(filename,count);
}

/**/ /* 統計的主方法 */
public void start()throwsFileNotFoundException,IOException
... {
BufferedReaderbfin = new BufferedReader( new FileReader( this .srcPath));
Stringtemp = null ;
while ((temp = bfin.readLine()) != null )
... {
stat(getFileName(temp));
}
}

/**/ /* 輸出統計結果 */
public void result()
... {
Iteratorit = statMap.entrySet().iterator();
while (it.hasNext())
... {
Map.Entryentry = (Map.Entry)(it.next());
System. out .println((entry.getKey().equals( "" ) ? " 空文件名 " :entry.getKey()) + " 的個數是 " + entry.getValue());
}
}

public static void main(String[]args)throwsException
... {
FileNameStatfns = new FileNameStat( " src.txt " ); // 指定成待統計文件
fns.start();
fns.result();
}
}

      　　這道題也與百度的業務有關，百度現在除了搜索外，還有貼吧，知道，博客等重要產品。
    

      　　同時也在積極的探索社區化，包括前不久宣布進軍電子商務領域，搜索之外的這些產品，
      

      
其主要功能的實現主要是對數據庫的操作。
    

      　　因此，想進入百度，也需要對數據庫有一定的認識。
    

      
        

        
      
      
        
          實現思路及數據庫設計
        
        ：
      
    

      
其他字段略，根據需要添加
    

      　　如何對海量數據進行快速檢索，這是搜索引擎的必需考慮的問題。這又涉及到數據結構和算法。
    

      　　因此，要想進入百度，就必須熟悉一些基本的算法和數據結構。　
    

Trie Tree and some DS&Athm sample