chap009DS-H.ppt讲义.ppt

3. Trie树检索树 — 以多重链表作存储结构实现的键树 结点结构: 分支结点 叶子结点 指向记录 的指针 0 1 2 3 4 5 … … 24 25 26 关键字 指向下层结点的指针 每个域对应一个“字母” 0 1(A) 3 4 5(E) 9(I) … … 26 8(H) 4(D) 19(S) 22(V) 0 18(R) 7(G) 19 0 5(E) T HAD HAS HAVE HE HER HERE HIGH HIS ? ? ? ? ? ? ? ? ? 叶子结点 分支结点 指向记录 的指针 typedef struct TrieNode { NodeKind kind; // 结点类型 union { struct { KeyType K; Record *infoptr } lf; // 叶子结点(关键字和指向记录的指针) struct { TrieNode *ptr[27]; int num } bh; // 分支结点(27个指向下一层结点的指针) } } TrieNode, *TrieTree; // 键树类型 结点结构的 C 语言描述: 在 Trie 树中查找记录的过程: 假设: T 为指向 Trie 树根结点的指针， K.ch[0..K.num-1] 为待查关键字(给定值)。 则查找过程中的基本操作为： 有哪些信誉好的足球投注网站和对应字母相应的指针: 若 p 不空，且 p 所指为分支结点， 则 p = p-bh.Ptr[ord(K.Ch[i])] ; ( 其中: 0 ≤ i ≤ K.num-1 ) 初始状态: p=T; i = 0; 若 ( p p-kind == BRANCH iK.num) 则继续有哪些信誉好的足球投注网站下一层的结点 p=p-bh.ptr[ord(K.ch[i])]; i++; 其中，ord 为求字符在字母表中序号的函数 若 ( p p-kind==LEAF p-lf.K==K) 则 查找成功，返回指向相应记录的指针 p-lf.infoptr 反之，即 ( !p || p-kind==LEAF p-lf.K!=K ) 则表明查找不成功，返回“空指针”; 一、哈希表是什么？ 二、哈希函数的构造方法 三、处理冲突的方法 四、哈希表的查找 五、哈希表的删除操作 六、对静态查找表，．．． 9.3 哈 希 表 以上两节讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系， 一、哈希表是什么？ 查找的过程为给定值依次和关键字集合中各个关键字进行比较， 查找的效率取决于和给定值进行比较的关键字个数。 用这类方法表示的查找表，其平均查找长度都不为零。 不同的表示方法，其差别仅在于： 关键字和给定值进行比较的顺序不同。 在 m 阶(最多有m棵子树)的B-树上，每个非终端结点可能含有： n 个关键字 Ki（1≤ i≤n） nm n 个指向记录的指针 Di（1≤i≤n） n+1 个指向子树的指针 Ai（0≤i≤n） 多叉树的特性 typedef struct BTNode { int keynum; // 结点中关键字个数，结点大小 struct BTNode *parent; // 指向双亲结点的指针 KeyType key[m+1]; // 关键字（0号单元不用） struct BTNode *ptr[m+1]; // 子树指针向量 Record *recptr[m+1]; // 记录指针向量 } BTNode, *BTree; // B树结点和B树的类型 B-树结构的C语言描述如下: 非叶结点中的多个关键字均自小至大有序排列，即：K1 K2 … Kn ； 指针Ai-1 所指子树上所有关键字均小于Ki ； 指针Ai 所指子树上所有关键字均大于Ki ； 查找树的特性 平衡树的特性 树中所有叶子结点均不带信息，且在树中的同一层次上； 根结点或为叶子结点，根结点或至少含有两棵子树； 其余所有非叶结点均至少含有?m/2?棵子树