--------------------------------------------------------------------------------
標題: B-tree查找函數
作者: 葉飛虎
日期: 2011.04.19
--------------------------------------------------------------------------------
在 B-tree 中搜索鍵值，結點內可以使用二分查找，若要查找指定范圍內數據與查找鍵值
相比相對要復雜一點。
現給出查找指定范圍內第一項和最后一項數據的示例代碼：
1 // B-tree 的項
2 typedef struct
3 {
4 long Key; // 鍵值
5 void* Link; // 子結點或數據
6 } TBTItem, *PBTItem;
7
8 // B-tree 的結點
9 typedef struct
10 {
11 Byte Count; // 項數[1..維數]
12 bool IsLeaf; // 是否為葉子結點
13 TBTItem Items[100]; // 項列表(假設 B-tree 維度為 100)
14 } TBTNode, *PBTNode;
15
16 // 查找范圍內的第一項并返回序號(注: AFrom < ATo)
17 TBTNode* FindFirstItem(TBTNode* ARoot, long AFrom, long ATo,
18 bool AIsInc, long& AIndex)
19 {
20 // 初始化
21 bool boolRet = false;
22 TBTNode* pNode = ARoot;
23 TBTNode* pNext = NULL;
24 long intNext = 0;
25 long intBegin, intEnd, intMid, intKey;
26
27 // 循環查找層
28 while (pNode != NULL)
29 {
30 // 初始化(注: pNode->Count >= 1)
31 intEnd = pNode->Count - 1;
32 intBegin = 0;
33
34 // 結點內二分查找
35 while (intBegin <= intEnd)
36 {
37 intMid = (intBegin + intEnd) >> 1;
38 intKey = pNode->Items[intMid].Key;
39 if (intKey < AFrom)
40 intBegin = intMid + 1;
41 else
42 {
43 intEnd = intMid - 1;
44 if (intKey == AFrom)
45 {
46 intBegin = intMid;
47 break;
48 }
49 }
50 }
51
52 // 判斷是否為葉結點
53 AIndex = intBegin;
54 if (pNode->IsLeaf)
55 {
56 if (intKey != AFrom)
57 {
58 if (AIndex != pNode->Count)
59 {
60 boolRet = (pNode->Items[AIndex].Key <= ATo);
61 break;
62 }
63 }
64 else if (AIsInc)
65 {
66 boolRet = true;
67 break;
68 }
69 else if (AIndex < pNode->Count - 1)
70 {
71 AIndex++;
72 boolRet = (pNode->Items[AIndex].Key <= ATo);
73 break;
74 }
75
76 // 下一結點項
77 if (pNext == NULL)
78 break;
79 else
80 {
81 pNode = (TBTNode*)pNext->Item[intNext].Link;
82 pNext = NULL;
83 }
84 }
85 else
86 {
87 // 校正索引
88 if (AIndex == pNode->Count)
89 AIndex = pNode->Count - 1;
90 else if (intKey == AFrom)
91 {
92 if (AIndex < pNode->Count - 1)
93 {
94 intNext = AIndex + 1;
95 pNext = (pNode->Items[intNext].Key <= To) ? pNode : NULL;
96 }
97 }
98 else if (AIndex == 0)
99 pNext = NULL;
100 else
101 {
102 intNext = AIndex--;
103 pNext = (pNode->Items[intNext].Key <= To) ? pNode : NULL;
104 }
105
106 // 子結點
107 pNode = (TBTNode*)pNode->Item[AIndex].Link;
108 }
109 }
110
111 // 返回結果
112 return boolRet ? pNode : NULL;
113 }
114
115 // 查找范圍內的最后一項并返回序號(注: AFrom < ATo)
116 TBTNode* FindLastItem(TBTNode* ARoot, long AFrom, long ATo,
117 bool AIsInc, long& AIndex)
118 {
119 // 初始化
120 bool boolRet = false;
121 TBTNode* pNode = ARoot;
122 long intBegin, intEnd, intMid, intKey;
123
124 // 循環查找層
125 while (pNode != NULL)
126 {
127 // 初始化(注: pNode->Count >= 1)
128 intEnd = pNode->Count - 1;
129 intBegin = 0;
130
131 // 結點內二分查找
132 while (intBegin <= intEnd)
133 {
134 intMid = (intBegin + intEnd) >> 1;
135 intKey = pNode->Items[intMid].Key;
136 if (intKey < ATo)
137 intBegin = intMid + 1;
138 else
139 {
140 intEnd = intMid - 1;
141 if (intKey == ATo)
142 {
143 intBegin = intMid;
144 break;
145 }
146 }
147 }
148
149 // 判斷是否為葉結點
150 AIndex = intBegin;
151 if (pNode->IsLeaf)
152 {
153 if ((intKey == ATo) && AIsInc)
154 boolRet = true;
155 else if (AIndex > 0)
156 {
157 AIndex--;
158 boolRet = (pNode->Items[AIndex].Key >= AFrom);
159 }
160
161 break;
162 }
163 else
164 {
165 // 校正索引
166 if ((intKey == ATo) && AIsInc)
167 ;
168 else if (AIndex > 0)
169 AIndex--;
170 else
171 break;
172
173 // 子結點
174 pNode = (TBTNode*)pNode->Item[AIndex].Link;
175 }
176 }
177
178 // 返回結果
179 return boolRet ? pNode : NULL;
180 }
181
posted on 2011-05-22 12:00
Kyee Ye 閱讀(337)
評論(0) 編輯 收藏 引用 所屬分類:
技巧雜集