|
|
像如果我面试突然问你,我要存很多个手机号码,随时不断的插入和删除新的手机号码,你用什么算法可以很快查找到一个手机号码是否在链表里。——如果应届生无法说出自己定义个算法(正常的),我起码要他知道可以用哈希查找+避免冲突算法+双链表,不然肯定不会录用 M+ s. M* f( [! k+ H
0 T5 t% o* Q0 \5 l2 D而且数据结构也是有用的,不是什么都可以去调用,比如以前在华为时写的这段代码,就用到了B树——这也是为什么大公司要考数据结构和算法的原因' c. f1 U7 ]' I
//BTreeNode加指针域 BTreeNode *next;
' d3 `* J* _8 `. g; j# S// int leafnodes;6 U( K* l+ R; S9 A8 n2 [
while(curlayer < layers)
! n: P7 T; W/ ?{
2 s4 Y+ M" `8 W1 J/ ^0 _1 e. {6 p7 R layernodes = pow(M+1, curlayer); //计算层次为curlayer的结点总数: E' }: e0 f1 G* X# j0 _
pprenode = NULL;
8 P9 M P8 p% Y3 h9 y7 f6 C i = 0;& k# f; N+ E/ _1 R
while(i < layernodes)
8 p: ^) i. l6 m' M: m { & X% j4 e9 R6 N, L1 ]
if(curlayer == layers - 1 )# F: G; L. T( Q6 @
{ 1 p) i7 J* J d
if(leafnodes > m_leafnodes)
- T3 h9 l ^9 A. y+ g1 d { t" x( e8 f! U0 I* d) I" n2 I
cout<<"B+树初始完成,已建立[ "<<leafnodes<<" ]个叶子结点"<<endl;7 E, @9 f# l9 v- ~% r4 s
break;! I# e0 p9 y3 A, l2 H9 y
}, W: g3 W+ S7 g) |7 W
else% D' d6 a( \4 [) K- D. e
leafnodes++; //计算叶子结点数
9 N* r+ h8 F5 W) \ }7 n2 i0 Z" J6 j
/ R0 a ]" [2 Z! i) b# ~
m_pcurrent=new BtreeNode;3 D$ I1 ]: u$ [( @' r" C: ^$ S) P
if(m_pcurrent != NULL)
3 ^6 V% R, F2 \2 @- D" Y. E" t8 Z {
8 U4 J- Q' r) v. C. J if(i == 0) //保存第curlayer+1的第一个结点! y a6 V5 R7 k" C. r& U2 ]% o4 |
layerfirst = m_pcurrent;
8 A: C( M0 q0 h% F, o 4 y( h+ }7 y$ C. N. L* x
if(pprenode != NULL)8 k; T8 e) |; }( h! G0 |
pprenode->next=m_pccurent;: z8 g8 N7 P. d9 w- I" E# S S
4 T4 N# h" Q( o+ Q8 w& g/ R4 V" E
if(i%(M+1)==1 && i!=1)//父结点的子结点已满时,确定新结点的父结点) ~# {# x* M( u& P
{8 |, q2 |1 d. Q% Y& h- I+ n
m_pparent = pprenode->parent->next;
6 W! F" H0 c% G' x/ }# } }4 |% l0 z) S+ z$ C! g1 Z8 I
m_pparent->child = m_pcurrent;0 ^% y8 x' ~; [& b- W, [/ [9 X
m_pcurrent->parent = m_pparent;
0 Q# G1 C$ K5 q, u- e m_pprenode = m_pcurrent; //保存当前结点
, b( ?0 M, J6 S, V: ^) F current->next = NULL;( R8 A5 v$ ^9 o; O- N9 P7 o! r( [! W
m_pparent->numkeys++;% V) K- { U( `
m_pcurrent->numkeys = 0; ! \' ?) u, I+ j9 @1 H# S
% E" n0 n* N, z& B) v" d5 X }//if5 y" X T- `. O+ m3 i5 W9 S
+ ~7 f2 x% |# \+ }" W9 } else5 D/ I# R# m5 V. w9 S* S1 A
return -1;
/ d, a7 Z6 w }3 l5 r2 c }//while8 s) K( R$ }6 P) B& X
; O; Z. ?- h1 g
m_pparent = layerfirst;
8 M. d k) ~, F3 _7 _3 `3 S curlayer++;
6 W5 ?# G3 z* B: r
5 F" f: G- Y2 G* Q- M( v7 y0 W( Q}//while |
|