|
|
像如果我面试突然问你,我要存很多个手机号码,随时不断的插入和删除新的手机号码,你用什么算法可以很快查找到一个手机号码是否在链表里。——如果应届生无法说出自己定义个算法(正常的),我起码要他知道可以用哈希查找+避免冲突算法+双链表,不然肯定不会录用
6 W2 S* i5 W: J2 s. C: N2 }3 f3 I- v1 _. A0 l# Y- k6 X
而且数据结构也是有用的,不是什么都可以去调用,比如以前在华为时写的这段代码,就用到了B树——这也是为什么大公司要考数据结构和算法的原因
4 y8 B. g7 M& K+ i/ ^//BTreeNode加指针域 BTreeNode *next;
( f7 _+ e% `- |$ l b6 A7 l% M// int leafnodes;
% c8 P/ m, n8 d( N' g3 Y3 @/ G7 Jwhile(curlayer < layers)
9 H, O4 @" ^& C) F( Q" P) M# l{ 7 g3 s5 W2 u9 \2 P6 [6 A" r
layernodes = pow(M+1, curlayer); //计算层次为curlayer的结点总数
* z5 i$ u" y. G pprenode = NULL;
1 o0 D3 s# m! P _ n i = 0;* V' x2 f8 A: [ J
while(i < layernodes)
# q7 i2 X- T4 @# a S3 M: ? { - K% K, W S1 ~' Y9 r
if(curlayer == layers - 1 )
2 w9 _/ Q9 t8 k J {
0 _' K5 K* h, n" k% J$ z# w0 J if(leafnodes > m_leafnodes): Q9 |8 I! y D @& \0 J
{; i' H2 @* W0 r
cout<<"B+树初始完成,已建立[ "<<leafnodes<<" ]个叶子结点"<<endl;
2 R- g h% H0 \3 L ] break;
; ]$ k2 A+ X% Q3 ?$ L( A- p }6 u9 m; H6 S W% \
else, A i7 I. ], G$ h: }1 `
leafnodes++; //计算叶子结点数
& k3 _: z7 Q- d7 v* s0 j( n }! g, _- H8 d2 H9 C
+ y" |0 c" i. @- V! z0 d' [
m_pcurrent=new BtreeNode;* U& s8 C0 v& _! s( V
if(m_pcurrent != NULL)
! T( e+ K) N# c5 K% f, l% X3 ? { * X, _4 N' z: Y' n Z5 g5 m
if(i == 0) //保存第curlayer+1的第一个结点$ j4 v. }+ u0 d6 H+ }* e
layerfirst = m_pcurrent;
: V7 v& c% g3 O, x" V5 u( X
5 C I7 c* b, z$ v8 @3 c$ \ if(pprenode != NULL)
* M: M* I9 P D: } pprenode->next=m_pccurent;* B4 K1 ?9 ^( J
X5 x4 H. p# c" F if(i%(M+1)==1 && i!=1)//父结点的子结点已满时,确定新结点的父结点
4 ^$ z0 P! P0 I {
% ^/ X' a" h, j p$ q/ I0 T m_pparent = pprenode->parent->next;+ z7 p3 g- a+ Q9 D0 ?' S
}
* j6 d+ M) E. p( m1 m8 {6 H: E1 N m_pparent->child = m_pcurrent;
( ]6 D8 d; b: H$ F& q( K2 M& J m_pcurrent->parent = m_pparent;( G1 x& a7 _; |$ i
m_pprenode = m_pcurrent; //保存当前结点/ D, g2 J' @4 n! R: W* o' E8 a
current->next = NULL;$ S( q$ Q; H5 `1 Z% P9 V+ b
m_pparent->numkeys++;
3 l3 Y9 V% a; @ L- |, N m_pcurrent->numkeys = 0;
$ D4 j! {1 W, q" `) |6 \
. `" c+ ~9 a( e; I# n4 @2 B6 j+ H }//if9 K* v. q9 B3 W2 w* E5 `/ x+ G
* n# f# n0 x2 v9 o' a7 C
else, i# x0 f+ e+ q# N0 @% e
return -1;
- @* A `8 a7 ^. O+ [( c }//while3 v4 t4 M' ?, R/ J' x2 b w+ D
& v' b! W. U1 L# l+ |; X
m_pparent = layerfirst;* f* D$ o/ l; c" d
curlayer++; G) Z) D8 ^ U' ]& B+ K, P- q
# M" H5 C& j1 ?; W' T6 g+ V# j9 e3 U}//while |
|