--------------------------------------------------------------------------------
标题: 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 阅读(326)
评论(0) 编辑 收藏 引用 所属分类:
技巧杂集