首页 > 试题广场 >

试编写算法，在根结点指针为t的m-阶B树上查找关键字k,返回

[问答题]

试编写算法，在根结点指针为t的m-阶B树上查找关键字k,返回记录(pt,i,tag).若查找成功，则特征位tag=1,等于k的关键字即为指针pt所指结点中的第i个关键字；若查找不成功，则特征位tag=0，等于k的关键字应插入到指针pt所指结点中第i个和第i+1个关键字之间。简化B-树存储结构如下所示：

type  mblink=↑mbnodembnode=record
  keynum:integer;
  parent:mblink;
  key:array[1..m]  of  keytp  {关键字}  ptr:array [0..m]  of  mblink
end;
result=record
   pt:mblink;
   i:integer;
   tag:(0..1)
    end;

（注：所用语言C, PASCAL等都可使用编制算法。若算法不用类PASCAL描述，要给出相应语言的结构描述。题目中给出的结构说明可供参考，也可自行给出）

Letitia

解析：

FUNC Srch_Mtree（t:mblink；k：keytp）：result；
   //在根结点指针为t的m阶B-树上查找关键字k，返回记录（pt，i，tag）。若查找成功，//置tag=1，等于k的关键字即pt所指结点中第i个关键字；若查找失败，关键字k应插入//pt所指结点的第i和第i+1个关键字之间。   p:=t；q:=null；found:=false；i:=0；//p指向待查结点，q指向p的双亲结点   WHILE（p<>NIL）AND NOT found DO     [n:=p↑.keynum；i:=search（p,k）；//在p↑.key[1..n]中查找      IF（i>0）AND（p↑.key[i]=k）THEN found：=true      ELSE[q:=p；p:=p↑.ptr[i]；]     ]
   IF found THEN return  （p,i,1）//查找成功ELSE return  （q，i，0）//查找失败，返回插入位置

[ 算法讨论] 插入时，若所在结点关键字keynum<m-1，则插入后结束；若插入前keynum=m-1，则要产生结点的分裂，分裂可能持续到根结点，使树的高度增加1，这里不再细述。

发表于 2017-05-16 02:24:10 回复(0)