|
|
像如果我面试突然问你,我要存很多个手机号码,随时不断的插入和删除新的手机号码,你用什么算法可以很快查找到一个手机号码是否在链表里。——如果应届生无法说出自己定义个算法(正常的),我起码要他知道可以用哈希查找+避免冲突算法+双链表,不然肯定不会录用
0 B. \! G" P; o3 {& d
& h, [2 T) Z, }- y: h8 X2 W而且数据结构也是有用的,不是什么都可以去调用,比如以前在华为时写的这段代码,就用到了B树——这也是为什么大公司要考数据结构和算法的原因/ r2 b* a* a5 j8 H' a" q" t
//BTreeNode加指针域 BTreeNode *next;* |- i5 ]3 Y& [8 z
// int leafnodes;
3 ^2 A+ i. `& b& Nwhile(curlayer < layers); |9 l) R( q4 R# w. K3 c
{ % z _8 [/ R0 ~2 d* [7 ^& z% A0 X
layernodes = pow(M+1, curlayer); //计算层次为curlayer的结点总数
/ N6 T3 H8 p# z pprenode = NULL;6 X2 Y, ~) A0 F# B2 Z3 z
i = 0; J- y) ?6 J/ g' U/ v
while(i < layernodes)/ b! w5 F5 |+ R, F5 k8 ^0 `, j# u& H
{ # f* t* J5 l8 b# l2 u/ d3 G
if(curlayer == layers - 1 )) i; M) e! W, E8 W" Q* a( `
{ $ |: Z3 ^/ i% m7 ]9 g( n
if(leafnodes > m_leafnodes) [& n4 m' c1 z2 v! @
{
& T( t. V% b9 @% l( | cout<<"B+树初始完成,已建立[ "<<leafnodes<<" ]个叶子结点"<<endl;
; {2 c+ @7 |( s% D2 J! W) d; Q- m break;
4 `) S: Z5 i A2 u$ R }
~1 x5 C5 P* Y& t* T else/ E; t0 \, U- B0 C2 G$ u
leafnodes++; //计算叶子结点数
4 i$ ^2 H& J9 ]; x3 S0 m1 p+ m1 p }: }# s# f3 P/ n" D( q9 @: J
$ Q; i; M+ c4 V; h" g' z9 o2 x
m_pcurrent=new BtreeNode;
5 r7 s0 m, h* D& ] if(m_pcurrent != NULL)6 @6 |( d6 a' `& z. L6 X& d4 Z" b
{
5 i5 Z% d2 |+ B. J- N if(i == 0) //保存第curlayer+1的第一个结点* L( v- B; V9 H! v9 H7 o# L
layerfirst = m_pcurrent;0 t7 F/ H- i& w" O
& h$ L! Y; ]& N% R/ B3 V
if(pprenode != NULL)
$ x4 J- a5 j( O7 q4 F0 ]1 a pprenode->next=m_pccurent;
; ]0 h6 a: \7 P, B 8 b1 a: @4 F5 `- v+ F: B, X
if(i%(M+1)==1 && i!=1)//父结点的子结点已满时,确定新结点的父结点: G% g d) t+ I. X
{
$ m' A/ A% n/ \: g( n m_pparent = pprenode->parent->next;" Y+ b8 T* c, M: x+ y g( j
}' ?& R) u- M$ V9 J/ C
m_pparent->child = m_pcurrent;
O6 {+ e+ W( m: n$ F& B m_pcurrent->parent = m_pparent;
+ C8 l( P4 J; C. r) O/ l m_pprenode = m_pcurrent; //保存当前结点9 v) g/ J% [4 B' p8 o. v
current->next = NULL;
* Y/ {3 d5 v7 T m_pparent->numkeys++;
" X! \, @5 B- V. V0 Y m_pcurrent->numkeys = 0; & A; Q, [, J& ]
( W$ J8 V0 n! f5 J$ [
}//if0 `- B0 H$ _/ R
8 x5 o# I5 d4 E. r: R) \% S else, }) A, Z% x: k& t
return -1;$ `: ]% F3 n, M1 W
}//while1 S+ b/ r5 u ]! A1 s" Z
2 J% b. K1 q, n9 A" v6 X* {' H% r
m_pparent = layerfirst;# }, s1 Z0 J+ A- |/ }' i: ]% Y+ {
curlayer++;1 Q& `8 z+ t1 L& k
O9 Z( d* k# r! ^) t m& U' d/ J6 C* c' \
}//while |
|