集合和静态查找表

• Back to Course Home

集合的定义

• 集合中的数据元素除了属于同一集合之外，没有任何逻辑关系。
• 在集合中，每个数据元素有一个区别于其他元素的 唯一标识，通常称为 键值或关键字值。

#ifndef SET_H
#define SET_H

#include <bits/stdc++.h>
using namespace std;

template <class KEY, class OTHER>
struct SET {
    KEY key;
    OTHER other;
    SET(const KEY &k, const OTHER &o) : key(k), other(o) {}
    SET() {}
    bool operator != (const SET<KEY, OTHER> &x) const {
        return key != x.key;
    }
    bool operator == (const SET<KEY, OTHER> &x) const {
        return key == x.key;
    }
    ostream &operator << (ostream &os) const {
        os << key;
        return os;
    }
};

#endif

查找的基本概念

• 用于查找的集合称之为查找表
• 查找表分类：
  • 静态查找表：数据元素固定
  • 动态查找表
• 根据查找的数据元素存放位置：
  • 内部查找
  • 外部查找：记录

静态查找表

无序表的查找

• 查找表中的元素无序
• 顺序查找
  • 时间复杂度：\(O(N)\)

有序表的查找

• 顺序查找：\(O(N)\)
• 二分查找：\(O(\log N)\)

• 插值查找：

  • 根据下面的公式估算位置
  \[ next = low + [\frac{(x - A[low])}{A[high] - A[low]} \times (high - low - 1)] \]

• 分块查找/顺序索引查找

  • 分块：块间必须是有序的
  • 索引表：对查找表分块后建立，每个索引项包含一个块内的最大元素值和该索引块的起始地址
  • 先查找索引表，确定在哪一块，再在块中查找元素

#include "8-1-set.h"
#include <bits/stdc++.h>
using namespace std;

template <class KEY, class OTHER>
int seqSearch(SET<KEY, OTHER>* data, int size, const KEY& x) {
    data[0].key = x;
    for (int i = size; data[i].key != x; i--);
    return i;
}

template <class KEY, class OTHER>
int binSearch(SET<KEY, OTHER>* data, int size, const KEY& x) {
    int left = 1, right = size, mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (data[mid].key == x) {
            return mid;
        }
        if (data[mid].key < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return 0;
}