數(shù)據(jù)結(jié)構(gòu)第九章 查找part6

1、 在查找不成功之后，需進(jìn)行插入。顯然，關(guān)鍵字插入插入的位置位置必定在最下最下層的非葉結(jié)點(diǎn)層的非葉結(jié)點(diǎn)，有下列幾種情況：3插入插入1) 插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)nsymbol 其中: p 指向雙鏈樹中某個(gè)結(jié)點(diǎn)， 0 i K.num-1初始狀態(tài): p=T-first; i = 0;若 ( p & p-symbol = K.chi & ifirst; i+;若 ( p & p-symbol != K.chi )則繼續(xù)在鍵樹的同一層上進(jìn)行查找 p=p-next;若 ( p & p-symbol=K.chi & i=K.num-1)則 查找成功，返回指向相應(yīng)記錄

2、的指針 p-infoptr 若 ( p = NULL)則表明查找不成功，返回“空指針”;3. Trie樹樹 以多重鏈表作存儲結(jié)構(gòu)實(shí)現(xiàn)的鍵樹結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):分支結(jié)點(diǎn)分支結(jié)點(diǎn)葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)指向記錄的指針0 1 2 3 4 5 24 25 26關(guān)鍵字關(guān)鍵字指向下層結(jié)點(diǎn)的指針每個(gè)域?qū)?yīng)一個(gè)“字母”0 1(A) 3 4 5(E) 9(I) 268(H)4(D) 19(S) 22(V) 0 18(R) 7(G) 190 5(E)THADHAS HAVE HEHERHEREHIGHHIS葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)分支結(jié)點(diǎn)分支結(jié)點(diǎn)指向記錄指向記錄的指針的指針typedef struct TrieNode NodeK

3、ind kind; / 結(jié)點(diǎn)類型結(jié)點(diǎn)類型 union struct KeyType K; Record *infoptr lf; / 葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)(關(guān)鍵字和指向記錄的指針關(guān)鍵字和指向記錄的指針) struct TrieNode *ptr27; int num bh; / 分支結(jié)點(diǎn)分支結(jié)點(diǎn)(27個(gè)指向下一層結(jié)點(diǎn)的指針個(gè)指向下一層結(jié)點(diǎn)的指針) TrieNode, *TrieTree; / 鍵樹類型鍵樹類型結(jié)點(diǎn)結(jié)構(gòu)的結(jié)點(diǎn)結(jié)構(gòu)的 C 語言描述語言描述:在在 Trie 樹中查找記錄的過程樹中查找記錄的過程:假設(shè)假設(shè): T 為指向 Trie 樹根結(jié)點(diǎn)的指針， K.ch0.K.num-1 為待查關(guān)鍵字(給定值)。則則查找過程中的基本操作為： 搜索和對應(yīng)字母相應(yīng)的指針?biāo)阉骱蛯?yīng)字母相應(yīng)的指針: 若若 p 不空，且 p 所指為分支結(jié)點(diǎn)， 則則 p = p-bh.Ptrord(K.Chi) ; ( 其中: 0 i K.num-1 )初始狀態(tài)初始狀態(tài): p=T; i = 0;若若 ( p & p-kind = BRANCH & ibh.ptrord(K.chi); i+;其中，ord 為求字符在字母表中序號的函數(shù)若若 ( p & p-kind=LEAF & p-lf.K=K)則則 查找成功查找成功，返回返回指向相應(yīng)記錄的指針 ptr 反之，反之，