|
|
像如果我面试突然问你，我要存很多个手机号码，随时不断的插入和删除新的手机号码，你用什么算法可以很快查找到一个手机号码是否在链表里。——如果应届生无法说出自己定义个算法（正常的），我起码要他知道可以用哈希查找+避免冲突算法+双链表，不然肯定不会录用
! E, R1 p) g- _! o* v
, o4 m% M, V. v6 C+ o7 u4 Y9 I而且数据结构也是有用的，不是什么都可以去调用，比如以前在华为时写的这段代码，就用到了B树——这也是为什么大公司要考数据结构和算法的原因
) r7 R$ G5 T! O- ~( [+ \. w! s. l4 o//BTreeNode加指针域 BTreeNode *next;, D- H3 L: {- ?! z
// int leafnodes;! g. t& n" ]! T* y" ~" r# D9 t
while(curlayer < layers)
5 l% D4 N Q4 n7 M: o) k{
* u1 |! {$ K: m' Y layernodes = pow(M+1, curlayer); //计算层次为curlayer的结点总数
, ] q7 k4 a7 J pprenode = NULL;
$ ?0 L+ H, U' b0 {4 M& f i = 0;' C$ S& p& ?. o, A# b, }0 _4 _
while(i < layernodes)
# K* z( ~& s- z2 q2 A {
/ ~+ _( I) p% W( I if(curlayer == layers - 1 )
+ K% C3 g5 c' H2 z# H' O {
- t! U6 g: S3 m- `* a6 e if(leafnodes > m_leafnodes)
* g: n' X* i, [) y {" R7 R+ P1 I4 I1 y
cout<<"B+树初始完成,已建立[ "<<leafnodes<<" ]个叶子结点"<<endl;- P, w0 f; _6 x6 A
break;
7 z3 R3 L) v, c7 a) \( p& D2 ~ }. ^4 h7 ]4 r" V
else
/ x- x, U/ n/ T. T# l leafnodes++; //计算叶子结点数' C% p/ P6 f( v$ }
} ?" \2 s/ }- x3 C
( h- b7 s5 l& N! j" I) V- I m_pcurrent=new BtreeNode;5 e0 O- q6 C1 i6 J3 q( j0 |
if(m_pcurrent != NULL)8 n' D4 ~: _& J5 p# c) G
{
! O2 G* D! l' E; B if(i == 0) //保存第curlayer+1的第一个结点
( E$ g* R p5 f& x2 c1 c) r) b layerfirst = m_pcurrent;
' z4 _: _1 V9 c4 H
( @! p) W* Z2 _" V if(pprenode != NULL)0 F, I; A8 ]" X! B
pprenode->next=m_pccurent;8 u+ c _" Z! D) `- D6 [3 R
4 e) C5 I6 m2 z" k9 a5 Y& V if(i%(M+1)==1 && i!=1)//父结点的子结点已满时,确定新结点的父结点
( H) y- {& ]2 l+ J8 H; B {+ @3 g# J& x+ O* J9 c
m_pparent = pprenode->parent->next;+ N4 t6 y+ Q& p0 s9 n" M
}/ J( \1 w- f( }& U' b! `, b
m_pparent->child = m_pcurrent;
/ Z% f" s. D# l0 G2 P' S8 h m_pcurrent->parent = m_pparent;
" }( b1 C# H- f m_pprenode = m_pcurrent; //保存当前结点3 x3 W! `, T* {# q- ~2 [
current->next = NULL;$ Z* ]% i" a' V$ ~
m_pparent->numkeys++;
% _: s" n- H+ M: d1 C: ?6 p m_pcurrent->numkeys = 0;
* |+ _- O! ]6 l4 S9 u6 F8 q% t$ H
3 E8 X! y8 J2 K! l, ~5 k3 _ }//if4 n1 M; n! X; X; i Y* w6 i4 ^2 V
$ m% q2 f$ P# K- }5 b/ T& p3 h { else
0 H8 ^( E+ E O% ?% d; ^" d# }. g return -1;
) x* `3 M. o) j }//while
+ _- d: j! M% y$ A/ K6 j
6 A2 G, n+ e) Y q) ^+ e1 S m_pparent = layerfirst;( B4 o9 u% @, f. {
curlayer++;5 }- ]. l- [& p+ ?$ p/ `
( ^6 ^0 X( G; K6 G}//while |
|
IP卡
狗仔卡
发表于 2009-6-5 10:29
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
发表于 2009-6-7 18:00
发表于 2009-6-7 19:03