数据结构知识点梳理第5章

第七章 查找

相关概念：
（1）关键码：数据元素中某个数据项的值具有唯一标识一个数据元素（或记录），这种唯一位移的关键码被称作主关键码；若关键码不具备这种唯一性，则可称其为次关键码。
（2）动态索引表与静态索引表：在进行查找操作时若涉及对索引表的修改，则该索引表可视为动态索引表；反之则被视为静态索引表。
（3）平均查找长度：为了确定特定关键码在索引表中的位置所需进行的关键字比较次数的期望值被称为该算法在成功查找情况下的平均查找长度。
对于包含n个记录的索引表而言：
ASL = \sum_{i=1}^{n} P_i C_i
其中P_i代表找到第i个记录的概率且满足\sum_{i=1}^{n} P_i = 1；
C_i表示找到与给定值相等的关键码所对应的第i个记录时所需的比较次数。
可以用平均查找长度这一指标来评估算法性能

7.2.1 线性搜索
线性搜索的过程是从第一个元素开始逐步比较每个元素。如果找到目标元素则表示成功；未能找到目标元素则表示失败。
在本节讨论中，默认采用线性表（即数组）作为数据存储的基础结构。

    typedef struct
    {
    	KeyType key;	//关键字域
    	InfoType OtherInfo;	//其他域
    }ElemType;

顺序表的定