|
|
像如果我面试突然问你,我要存很多个手机号码,随时不断的插入和删除新的手机号码,你用什么算法可以很快查找到一个手机号码是否在链表里。——如果应届生无法说出自己定义个算法(正常的),我起码要他知道可以用哈希查找+避免冲突算法+双链表,不然肯定不会录用
4 ~! S4 r7 O5 }4 {) e+ z
8 w; |, S: X) v/ B( z而且数据结构也是有用的,不是什么都可以去调用,比如以前在华为时写的这段代码,就用到了B树——这也是为什么大公司要考数据结构和算法的原因1 V5 i) W$ V3 p4 Q
//BTreeNode加指针域 BTreeNode *next;6 j7 o" f; D9 v$ l+ I. ~3 H7 \
// int leafnodes;
; P& h- j) C0 ]% \, Lwhile(curlayer < layers)
' \( q1 t( M6 B! b! Q6 `3 d7 i{ / D4 ^' S0 E2 J/ [- Q& O, g# M
layernodes = pow(M+1, curlayer); //计算层次为curlayer的结点总数/ j4 F/ d+ B3 O" T/ W( p0 N
pprenode = NULL;
8 U9 B" V- v9 h: m i = 0;
2 n4 w% D! @+ X, s5 S2 H while(i < layernodes)* ]( j6 Q i$ D1 w( e
{
4 j$ m! `' W$ V& z( \/ D- A if(curlayer == layers - 1 )
2 y, T5 d) D+ s- j1 l) x( O { " l, ]" b( x6 W( b4 K$ w0 U
if(leafnodes > m_leafnodes)5 d# I, _3 d1 b! B: b9 L6 K
{
4 P5 `) L2 j2 o' g9 M) B. k5 L cout<<"B+树初始完成,已建立[ "<<leafnodes<<" ]个叶子结点"<<endl;
2 o/ A b% T" e) _6 G break;& u( Y, {$ Z( x: m0 e* s
}! x% ?1 V, r# S" O* A6 d }
else6 a0 A4 ]5 W. a; G
leafnodes++; //计算叶子结点数6 j/ h$ K8 k5 X7 f0 S: f& k
}4 s' s# A# Q8 e
/ k1 r9 T: ]' D/ ^& W. r m_pcurrent=new BtreeNode;
8 `) `" A0 w' r. W4 { if(m_pcurrent != NULL)) a, o) b0 `/ m( q- O+ Q6 I
{
. J2 H; y3 X* J c$ ? if(i == 0) //保存第curlayer+1的第一个结点( i3 O [% E" Q0 X9 Q4 q; \
layerfirst = m_pcurrent;
3 v5 F. _) g/ V# s4 X! y _7 \0 d$ l* m6 B; L8 {4 C
if(pprenode != NULL)
/ |0 c1 e, J' {% n% l pprenode->next=m_pccurent;
t* N$ y6 y8 `% @
+ C3 l+ H. i I$ H' K if(i%(M+1)==1 && i!=1)//父结点的子结点已满时,确定新结点的父结点
+ ^( ^. B5 q! f4 ? {
2 ~4 k8 D" {0 L8 h4 S3 b9 o, ` m_pparent = pprenode->parent->next;
# x7 |9 n1 a7 A4 H/ e; B) l" k }
4 {+ g( B1 q6 {/ g+ d. v m_pparent->child = m_pcurrent;6 D" o, A. h! X9 @
m_pcurrent->parent = m_pparent;
! l$ r3 P5 \( f) O9 \ m_pprenode = m_pcurrent; //保存当前结点
; |& n$ X' Q: y current->next = NULL;3 }5 c5 S1 [ u( o# Y# a x) B
m_pparent->numkeys++;
5 i- h. U2 L4 P3 ? m_pcurrent->numkeys = 0; ! v$ _- R. l) h& N1 ], R- p# Z
1 u$ y1 M- t9 L }//if
& o9 u2 K7 W" k, E( ~( a
A; W0 `: O+ `* }: O else
) ^" Q1 ?, b9 |% K; R return -1;
9 y- l2 q3 I0 x) n }//while" [# t' D* [5 l7 _. k8 z
0 W" r) S& I$ b; H
m_pparent = layerfirst;
3 X" \4 ?" S N& C curlayer++;8 n0 k# P4 i( S$ _1 N
8 }" Z5 J& m: `}//while |
|