7.1 查找与表验证

  • 假定有一组关于对象集合的信息。
    • 如果这组信息适于在内存空间中存储,则称为 「表 list」
    • 如果这组信息必须存储在外存中,则称为 「文件 file」
    • 把一组信息中的一个对象称为 「记录 record」
    • 而将每个记录中的信息划分为更小的单元,称为 「域 field」
    • 当对表进行查找时,希望按能识别记录的域来查找记录。这样的域称为 「关键字 key」
  • 记录的结构完全依赖于具体的应用。例如,如果一个表是一个电话号码簿,那么可以定义一个记录 person,它由姓名、地址和电话号码等域组成。如果要找到这个电话簿中的某个电话号码,那么电话号码域就是关键字。而如果要找到某个名字,那么名字域就是关键字。
  • 「顺序查找」 假定有一个表 list 和一个待查关键字 searchnum,要找到表中关键字域与 searchnum 相匹配的记录。如果表 searchnumn 个记录,且 list[i].key 表示记录 i 的关键字值,可以通过依次检查关键字值 list[0].key, list[1].key, ..., list[n-1].key 对其进行查找,直至找到该记录所在位置,或者检查完表中全部记录为止。在查找不成功时,需要进行 n+1 次关键字的比较,从而得到在最坏情况下的计算时间为 O(n)O(n)
  • 「折半查找」 与顺序查找不同,在折半查找中,假定表中的记录是按关键字域有序排列的,即 list[0].key \leq list[1].key \leq \cdots \leq list[n-1].key。正如 1.1 算法 中所讲,折半查找从 searchnumlist[middle].key 的比较开始,其中 middle = (n-1)/2。折半查找在最坏情况下也只需进行 O(logn)O(\log n) 次关键字的比较。
  • 『表验证』 现在需要对两个表 list1list2 是否相同进行验证,或者找出相异的元素。假定表验证算法能识别并报告以下三种类型的不匹配情况:

    1. 关键字为 list1[i].key 的记录出现在第一个表 list1 中,但在第二个表 list2 中,没有与之相同的关键字记录。
    2. 关键字为 list2[j].key 的记录出现在第二个表 list2 中,但在第一个表 list1 中,没有与之相同的关键字记录。
    3. list1[i].key = list2[j].key,但这两个记录至少有另一个域不匹配。

    假定两个表中记录的关键字是随机排列的,两个表的长度分别为 nm。以下函数 verify1 在最坏情况下的渐近计算时间是 O(mn)O(mn),函数 verify2 在验证前,先对输入表进行了排序。该函数在最坏情况下渐近计算时间是 O(tsort(n)+tsort(m)+m+n)O(tsort(n) + tsort(m) + m + n),其中 tsort(n)tsort(n) 是将表中的 n 个记录进行排序所需的时间。本章将会证明,可以把 n 个记录在 O(nlogn)O(n\log n) 时间内进行排序。因此,函数 verify2 在最坏情况下的时间复杂度为 O(max{nlogn,mlogm})O(max\{n \log n, m \log m\})

void verify1(element list1[], element list2[], int n, int m)
{
    int i, j;
    int marked[MAX_SIZE];

    for (i = 0; i < m; i++)
        marked[i] = false;
    for (i = 0; i < n; i++)
    {
        if ((j = seqsearch(list2, m, list1[i].key)) < 0) // seqsearch(int list[], int searchnum, int n) 为顺序查找
            printf("%d is not in list2\n", list1[i].key);
        else
            marked[j] = true;
    }
    for (i = 0; i < m; i++)
        if (!marked[i])
            printf("%d is not in list1\n", list2[i].key);
}
void verify2(element list1[], element list2[], int n, int m)
{
    int i, j;
    sort(list1, n);
    sort(list2, n);
    i = j = 0;
    while (i < n && j < m)
    {
        if (list1[i].key < list2[j].key) {
            printf("%d is not in list2\n", list1[i].key);
            i++;
        }
        else if (list1[i].key == list2[i].key) {
            i++; j++;
        }
        else {
            printf("%d is not in list1\n", list2[j].key);
            j++;
        }
    }
    for (; i < n; i++)
        printf("%d is not in list2\n", list1[i].key);
    for (; j < m; j++)
        printf("%d is not in list1\n", list2[j].key);
}

results matching ""

    No results matching ""