表验证：快速验证（假设表已经排序）

浏览数：14 / 时间：2015年06月08日

表验证：

　　表验证问题实际上就是把一个表的每个关键字作为待查关键字，对另一个表进行重复查找。

　　表验证算法能识别并报告以下两种类型的不匹配情况：

　　(1) 关键字list1[i]的记录出现在第一个表（list1）中，但在第二个表（list2）中，没有与之相同的关键字记录。

　　(2) 关键字list2[i]的记录出现在第二个表（list2）中，但在第一个表（list1）中，没有与之相同的关键字记录。

#include <stdio.h>
#include <stdlib.h>

#define FALSE    0
#define TRUE    1

#define MAX_SIZE    100

int list1[MAX_SIZE + 1] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int    n = 10;
int list2[MAX_SIZE + 1] = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
int    m = 10;

void list_output(int list[], int length)
{
    int i;

    for (i = 0; i < length; i++)
        printf("%4d ", list[i]);
    printf("\n");
}
// 假设表list1、list2已经按照从小到大的循序排列好
void verify2(int list1[], int n, int list2[], int m)
{
    int    i, j;
    i = j = 0;

    while (i < n && j < m) {
        if (list1[i] < list2[j]) {
            printf("%d is not in list2\n", list1[i]);
            i++;
        } else if (list1[i] == list2[j]) {
            i++;
            j++;
        } else {
            printf("%d is no in list1\n", list2[j]);
            j++;
        }
    }

    for (; i < n;i++) {
        printf("%d is not in list2\n", list1[i]);
    }

    for (; j < n; j++) {
        printf("%d is not in list1\n", list2[j]);
    }
}

int main()
{
    list_output(list1, n);
    list_output(list2, m);

    verify2(list1, n, list2, m);

    return 0;
}