顺序查找

àì夳堔傛蜴生んèń 2022-12-06 15:17 165阅读 0赞

## 一 概述 ##

顺序查找又称为线性查找，主要用于在顺序表中的查找。顺序查找通常分为对一般的无序线性表的顺序查找和对按关键字有序的顺序表的顺序查找。

## 二 一般线性表的顺序查找 ##

一般线性表的顺序查找的思想为从线性表的一端开始，逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足给定条件，则查找成功，并返回该元素在线性表中的位置；若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息。

数据结构代码：

typedef struct{        //查找表的数据结构
        
        ElemType *elem;    //元素存储空间基址，建表时按实际长度分配，0号单元留空作为哨兵
        int TableLen;      //表的长度
    }SSTable;
    
    int Search_Seq(SSTable ST,ElemType key) {
        
        ST.elem[0] = key; //哨兵
        for(i=ST.TableLen;ST.elem[i]!=key;--i) { // 从后往前查找
            return i; //若表中不存在关键字为key的元素，将查找到i为0时退出for循环。
        }
    }

将ST.elem\[0\]称为"哨兵"。引入它的目的是使得Search\_Seq内的循环不必判断数组是否会越界，因为满足i==0时，循环一定会跳出。引入哨兵的目的是避免很多不必要的判断语句，从而提高程序效率。

## 三 查找过程分析 ##

一般线性表的顺序查找对于存在n个元素的表，给定值key与表中第i个元素相等，即定位第i个元素时，需进行n-i+1此关键字的比较。

当查找不成功的时候，与表中各关键字的比较次数显然时n+1次，从而顺序查找不成功的平均查找长度即为n+1。

通常，查找表中记录的查找概率并不相等。若能够预先得知每个记录的查找效率，则应该对记录的查找概率进行排序，使得表中记录按查找概率从小到大重新排列。

## 四 有序表的顺序查找 ##

当查找之前就已经知道表时关键字有序的，则查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度。

如果表L为按关键字从小到大排列的顺序表，当从前往后查找时，待查找元素的关键字为key，当查找到第i个元素时，发现第i个元素对应的关键字小于key，但是第i+1个元素对应的关键字大于key，这时候就可返回查找失败的信息，因为第i个元素之后的关键字均大于key，所以表中不存在关键字key的元素。

**注意：**有序表的顺序查找和后面的折半查找的思想是不一样的，且有序表的顺序查找中的线性表可以是链式存储结构。