數據結構第九章 查找part6_第1頁
數據結構第九章 查找part6_第2頁
數據結構第九章 查找part6_第3頁
數據結構第九章 查找part6_第4頁
數據結構第九章 查找part6_第5頁
已閱讀5頁，還剩24頁未讀， 繼續免費閱讀

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

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

2、= NULL)則表明查找不成功，返回“空指針”;3. Trie樹樹 以多重鏈表作存儲結構實現的鍵樹結點結構結點結構:分支結點分支結點葉子結點葉子結點指向記錄的指針0 1 2 3 4 5 24 25 26關鍵字關鍵字指向下層結點的指針每個域對應一個“字母”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葉子結點葉子結點分支結點分支結點指向記錄指向記錄的指針的指針typedef struct TrieNode NodeKind kind; / 結點類型結點類型

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

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論