【数据结构课件】查找表.pptVIP

查找表：是一种以集合为逻辑结构，以查找为核 心运算，同时包括其他运算的数据结构。 数字查找树：又称键树，它是一棵度≥ 2的树，树中每 个结点不是包含一个或几个关键字，而是只含有组成关 键字的符号。例如，若关键字是数字，则结点中只包含 一个数位，若关键字是单词，则结点中只包含一个字母。 例如:有如下16个字的关键字的集合{CAI,CAO,Li,LAN,CHA, CHANG,WEN,CHAO,YUN,YANG,LONG,WANG,ZHAO,LIU, WU,CHEN} 可对此集合作如下逐层分割： 首先按其首字符的不同将它们分成5个集合：{CAI,CAO,CHA, CHANG,CHAO,CHEN},{WEN,WANG,WU},{ZHAO},{LI,LAN, LONG,LIU},{YUN,YANG}, 然后对其中4个关键字个数大于1的集合再按其第二个字母的不同 进行分割。若所得子集的关键字个数多于1个，则还需按第三个字 符不同再进行分割。依此类推，直至每个子集中只包含一个关键 字为止。例如对首字符为C的集合进行如下分割{{(CAI),(CAO)},{ {{(CHA),(CHANG),(CHAO),(CHEN)}},显然，如此集合、子集和 元素之间的层次关系可以用一棵树来表示，这棵树便为键树。 North China Electric Power University C A H I O $ $ A $ N O E N G $ $ $ L A I O N $ U N G $ $ W A E U N N $ G $ $ Y A N G $ U N $ Z H A O $ 树中根结点的五棵子树分别表示首字符为C、L、W、Y和Z的五个 关键字子集。从根结点到叶子结点路径上所有结点的字符组成的字 符串表示一个关键字，叶子结点中的特殊符号$表示字符串的结束。 North China Electric Power University 为了查找和插入方便，我们约定键树是有序树，即同一层中兄弟 结点之间依所含符号自左至右有序，并约定结束符$小于任何字符。 通常，键树有两种存储结构： 1)以树的孩子兄弟链表来表示，则树中每个结点包含三个域： Symbol域：存储关键字的一个字符； Son域：存储指向第一棵子树的根的指针； Brother域：存储指向右兄弟结点的指针； 同时，叶子结点的Son域存储指向关键字记录的指针。 此时的二叉树又称为双链树。 双链树的查找过程如下：假设给定值为k(1..n+1),其中k[1]至k[n]表 示待查关键字中n各字符，k[n+1]为结束符$,从双链树的根指针出 发，顺Son指针找到第一棵子树的根结点，以k[1]和此结点的 Symbol域比较，若相等，则顺Son域再比较下一字符，否则沿 Brother域顺序查找，若Symbolk[1]说明查找的关键字不存在，要 进行插入。若查找成功，Search单元中存放已查到的关键字，否则 为Nil. North China Electric Power University North China Electric Power University 下面给出在二叉排序树T中查找结点j,使j↑.key=x，如 果x在T中，则删除x结点，否则,送出B=1，说明此树中 无被删结点的算法： Procedure det(t,j,p:Bitptr;x:KeyType); {j指向被删结点，p指向其双亲，假设树不空} Begin j:=t;B:=1;p:=Nil; while (j Nil) and (B=1) Do Case xj↑.key:[ p:=j;j:=j↑.lchild;] x=j↑.key: B:=0; xj↑.key:[ p:=j;j:=j↑.rchild;] EndCase; North China Electric Power University If B=0 then [ if j↑.lchild=Nil{被删结点无左子树} then s:=j↑.rchild Else if j↑.rchild=nil then s:=j↑.lchild else [ q:=j;s:=q↑.lchild; while s↑.rchild Nil Do [ q:=s;s:=s↑.rchild];s↑.rchild:=j↑.rchild; if