哈希表

HashTable.cpp

概念

哈希函数：H(key): K -> D , key ∈ K

构造方法

  • 直接定址法
  • 除留余数法
  • 数字分析法
  • 折叠法

  • 平方取中法

    冲突处理方法

  • 链地址法：key 相同的用单链表链接

  • 开放定址法

    • 线性探测法：key 相同 -> 放到 key 的下一个位置，Hi = (H(key) + i) % m
    • 二次探测法：key 相同 -> 放到 Di = 1^2, -1^2, ..., ±（k)^2,(k<=m/2）
    • 随机探测法：H = (H(key) + 伪随机数) % m

      线性探测的哈希表数据结构

      线性探测的哈希表数据结构和图片
      1. typedef char KeyType;
      2. typedef struct {
      3. KeyType key;
      4. }RcdType;
      5. typedef struct {
      6. RcdType *rcd;
      7. int size;
      8. int count;
      9. bool *tag;
      10. }HashTable;
      哈希表 - 图1

      递归

      概念

      函数直接或间接地调用自身

      递归与分治

  • 分治法

    • 问题的分解
    • 问题规模的分解
  • 折半查找（递归）
  • 归并排序（递归）

  • 快速排序（递归）

    递归与迭代

  • 迭代：反复利用变量旧值推出新值

  • 折半查找（迭代）
  • 归并排序（迭代）

    广义表

    头尾链表存储表示
    广义表的头尾链表存储表示和图片
    1. // 广义表的头尾链表存储表示
    2. typedef enum {ATOM, LIST} ElemTag;
    3. // ATOM==0：原子，LIST==1：子表
    4. typedef struct GLNode {
    5.   ElemTag tag;
    6.   // 公共部分，用于区分原子结点和表结点
    7.   union {
    8.       // 原子结点和表结点的联合部分
    9.       AtomType atom;
    10.       // atom 是原子结点的值域，AtomType 由用户定义
    11.       struct {
    12.           struct GLNode *hp, *tp;
    13.       } ptr;
    14.       // ptr 是表结点的指针域，prt.hp 和 ptr.tp 分别指向表头和表尾
    15.   } a;
    16. } *GList, GLNode;
    哈希表 - 图2
    扩展线性链表存储表示
    扩展线性链表存储表示和图片
    1. // 广义表的扩展线性链表存储表示
    2. typedef enum {ATOM, LIST} ElemTag;
    3. // ATOM==0：原子，LIST==1：子表
    4. typedef struct GLNode1 {
    5.   ElemTag tag;
    6.   // 公共部分，用于区分原子结点和表结点
    7.   union {
    8.       // 原子结点和表结点的联合部分
    9.       AtomType atom; // 原子结点的值域
    10.       struct GLNode1 *hp; // 表结点的表头指针
    11.   } a;
    12.   struct GLNode1 *tp;
    13.   // 相当于线性链表的 next，指向下一个元素结点
    14. } *GList1, GLNode1;
    哈希表 - 图3