顺序文件的基本概念与查找算法

基本概念

在物理结构中记录排列的先后次序与在逻辑结构中记录排列的先后次序一致的文件称为顺序文件。

记录的排列按关键字值有序的顺序文件称为排序顺序文件，否则，称为一般顺序文件；（该划分是在逻辑上的划分）

在存储介质上采用连续组织方式的顺序文件称为连续顺序文件；采用链接组织方式的顺序文件称为链接顺序文件；（该划分是在物理上的划分）

若排序顺序文件在存储介质上采用连续组织方式，称之为排序连续顺序文件。

连续顺序文件的查找

顺序查找法

基本思想

从文件的第一个记录开始，将用户给出的关键字值与当前被查找记录的关键字值进行比较，若匹配，则查找成功，给出被查到的记录在文件中的位置，查找结束。若所有 n 个记录的关键字值都已比较，不存在与用户要查的关键字值匹配的记录，则查找失败，给出信息 0。

非递归算法 C 语言实现

int SEQSEARCH1(keytype key[], int n, keytype k) {
    int i;
    for(i=1; i<=n; i++) // 位置从 1 开始
        if(key[i]==k) return i;
    return 0;
}

递归算法 C 语言实现

int SEQSEARCH2(keytype key[], int n, keytype k, int i) {
    if(i>n) return 0;
    if(key[i]==k) return i;
    return SEQSEARCH2(key,n,k,i+1);
}
// 该函数调用方式如下：
// int pos = SEQSEARCH2(key,n,k,1); // 从 1 开始

查找效率

平均查找长度 ASL：确定一个记录在文件中的位置所需要进行的关键字值的比较次数的期望值 (平均值)。

对于具有 n 个记录的文件，有

其中，pi 为查找第 i 个记录的概率，ci 为查找第 i 个记录所进行过的关键字的比较次数。

对于具有 n 个记录的顺序文件，若查找概率相等，则有

故算法的时间复杂度为 O(n)。

顺序查找法的优点和缺点

优点：

1. 查找原理和过程简单，易于理解；
2. 对于被查找对象的排列次序没有限制。

缺点：

1. 查找的时间效率低。

排序连续顺序文件的折半查找法（二分查找法）

核心思想

将要查找的关键字值与当前查找范围内位置居中的记录的关键字的值进行比较。 若匹配，则查找成功，给出被查到记录在文件中的位置，查找结束。 若要查找的关键字值小于位置居中的记录的关键字值，则到当前查找范围的前半部分重复上述查找过程，否则，到当前查找范围的后半部分重复上述查找过程，直到查找成功或者失败。 若查找失败，则给出信息 0。

为实现二分查找法，需要几个变量，如下： n ：排序连续顺序文件中记录的个数 low：当前查找范围内第一个记录在文件中的位置。初值 low=1 high：当前查找范围内最后那个记录在文件中的位置。初值 high=n mid：当前查找范围内位置居中的那个记录的位置， mid 初值为：

((low+high)/2 向下取整)

查找失败的标志为 low > high

非递归算法的 C 语言实现

int BINSEARCH1(keytype key[], int n, keytype k) {
    int low=1, high=n, mid;
    while(low<=high){
        mid=(low+high)/2; // 向下取整
        if(key[mid]==k) return mid; // 查找成功
        if(k>key[mid]) low=mid+1; // 准备查找后半部分
        else high=mid-1; // 准备查找前半部分
    }
    return 0; // 查找失败
}

递归算法的 C 语言实现

int BINSEARCH2(keytype key[], int low, int high, keytype k) {
    int mid;
    if(low>high) return 0;
    else{
        mid=(low+high)/2;
        if(key[mid]==k) return mid;
        else if(k<key[mid]) return BINSEARCH2(key,low,mid-1,k);
        else return BINSEARCH2(key,mid+1,high,k);
    }
}

查找效率

若把当前查找范围内居中的记录的位置作为根结点，前半部分与后半部分的记录的位置分别构成根结点的左子树与右子树，则由此得到一棵称为' 判定树'的二叉树，利用它来描述折半查找的过程。如下图：

成功的查找过程正好等于走了一条从根结点到被查找结点的路径，经历的比较次数恰好是被查找结点在二叉树中所处的层次数！

基于此，二分查找的 ASL 计算如下：

二分查找算法的优点和缺点

优点：

1. 查找原理和过程简单，易于理解。
2. 查找的时间效率较高。

缺点：

1. 要求文件的记录按照关键字值有序排列；
2. 对于文件，只适用于排序连续顺序文件。

为了保持文件为排序顺序文件，在文件中插入和删除记录时需要移动大量的其它记录，所以折半查找方法适用于一经建立就很少改动、而又经常需要查找的文件。

Q：在线性表中采用折半查找方法查找数据元素，该线性表应该满足什么条件？ A：1、数据元素按值有序排列；2、必须采用顺序存储结构。

链接顺序文件的查找

链结点构造

链结点构造及文件整体构造如下：

C 语言实现如下：

typedef struct node {
    keytype key;
    rectype rec;
    struct node *link;
} *KeyLink;

非递归查找算法实现如下：

KeyLink SEARCH1(KeyLink F, keytype k) {
    KeyLink p;
    p=F;
    while(p!=NULL){
        if(p->key==k) return p; /* 查找成功 */
        p=p->link;
    }
    return NULL; /* 查找失败 */
}

递归算法实现如下：

KeyLink SEARCH2(KeyLink F, keytype k) {
    if(F!=NULL)
        if(F->key==k ) return F; /* 查找成功 */
        else return SEARCH2(F->link, k );
    return NULL; /* 查找失败 */
}