攻克数据结构和算法——第五天：查找

一，查找的基本概念

一是数据如何组织——查找表,
二是在查找表上如何查找——查找方法

1，查找表是由同类型的数据元素(或记录)构成的集合。
 

2，对查找表基本操作

●1)查询某个数据元素是否在查找表中;
●2)检索某个数据元素的各种属性;
●3)在查找表中插入一个数据元素; 
●4)从查找表中删去某个数据元素。

3，查找表分类

●静态查找表
仅作查询和检索操作的查找表。

●动态查找表
"查询”结果"不在查找表中”→数据元素插入到查找表中; ;
"查询”结果为"在查找表中”的数据元素→删除。

查找过程中，往往是依据数据元素的某个数据项进行查找，这个数据项通常是数据的关键字。
关键字:是数据元素中某个数据项的值，用以标识一个数据元素。

若关键字能标识唯一的一个数据元素,
则称为主关键字。
若关键字能标识若干个数据元素,
则称为次关键字。
 

4，平均查找长度ASL

给定值与关键字比较次数的期望值

5，常见的查找算法：

1）顺序查找
2）二分查找
3）索引查找
4）哈希查找
 

二，顺序查找

顺序查找基本思想
●从表中指定位置(一般为最后一一个，第0个位置设为岗哨)的记录开始，沿某个方向将记录的关键字与给定值相比较,若某个记录的关键字和给定值相等，则查找成功; 

●反之，若找完整个顺序表，都没有与给定关键字值相等的记录，则此顺序表中没有满足查找条件的记录，查找失败。

●空间复杂度: O(1)
●时间复杂度:
查找算法的基本运算是给定值与顺序表中记录关键字值的
比较。

最好情况: O(1)
最坏情况: O(n)
平均情况: O(n)

 代码实现：

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时，循环一定会跳出。引入哨兵的目的是避免很多不必要的判断语句，从而提高程序效率。

三，折半查找

1，有序表:如果顺序表中的记录按关键字值有序，即: R[i].key≤R[i+ 1].key (或R[i].key≥R[i+ 1].key)，
i=1,2...n-1，则称顺序表为有序表。
1 3 7 10 12 124
有序表

1 3 7 13 12 124
无序表
 

将待查关键字与有序表中间位置的记录进行比较，若相等，查找成功，若小于，则只可能在有序表的前半部分，若大于则只可能在有序表的后半部分，因此，经过一次比较，就将查找范围缩小一半,这样一直进行下去直到找到所需记录或记录不在查找表中。
 

2，代码实现：

int BinarySearch(DataType SL[], KeyType key, int n){
/*在长度为n的有序表SL中折半查找其关键字等于key的记录*/
/*查找成功返回其在有序表中的位置，查找失败否返回0*/
    int low=1;
    int high=n;
    while(low< =high){
        mid=(loW+ high)/2;
        if(key == SL[mid].key) {return mid;}
        else if( key> SL[mid].key) low=mid+ 1;
            else high=mid-1;
    }
    return 0;
}

3，折半查找特点

折半查找的查找效率高;
平均查找性能和最坏性能相当接近; 
折半查找要求查找表为有序表;
并且，折半查找只适用于顺序存储结构。

4，性能分析：

以深度为h的满二叉树为例， 即: n=2^h-1 并且查找概率相等，则

 当n> 50时，可得近似结果
ASL≈log2(n+1)-1

四，索引查找

在现代社会，数据充斥着我们的生活，正因为大量的数据才能有现在如此现代化的社会，但是大量的数据也给人们带来了很大的困扰。并且有的数据是很杂乱的，会导致查找困难。

所以我们想到了一种方法，就是建立索引。

索引说白了就是一个关键字，一个能帮助你更方便查找的关键字，可以是很多东西，一个字母，一个字符串，一个数字等等。

1，索引使用方法
●先分析数据规律，建立索引
●再根据索引|进行快速定位
●在定位的地方进行细致搜索

先分块，块间有序，就可以快速定位到块。

2，索引表的构建
1) 分块:

第Rk块中所有关键字< Rk+1块中所有关键字，(k=1, 2, ..L-1）

2)建立索引项:

关键字项:记载该块中最大关键字值;
指针项:记载该块第一 个记录在表中位置。

3)所有索引项组成索引表。

3，索引表的查找

分两步，第一步是索引表的查找，第二步是查找表的查找。

Data.Structures.and.Algorithms

pdf 0星 超过10%的资源 17.02MB

下载

索引表是有序的。

4，例子：

5，索引表的顺序查找算法思想描述
首先根据待查找关键字在索弓|表当中定位块。定位的方法是:只要
key>索引块i的最大关键值，则i++, 定位下一个索引项;直到定位到
索引块，或者把索弓|项都定位完也没有比key关键字大的索引项。
如果定位到块，则在块内部进行顺序查找。

6，代码实现：

int IndexSequelSearch(IndexType |s[], DataType s[], int m, KeyType key){
/*索引表为Is[0]-Is[m-1]，顺序表为s */
    i=0;
    while(i ls [i ].key) i++; /*块间查找*/
        if(i= =m)return -1; /*查找失败*/
        else{
            /*在块内顺序查找*/
            j=ls[ i ].Link;
            while(Key!=s[j].key &&j1 ].Link)j++;
            if(key = = s[j].key)return j; /*查找成功*/
            else return -1; /*查找失败*/
    }
}

typedef struct IndexType
{   
    KeyType key;
    int Link;
} IndexType;

7，性能分析：

ASL=ASL(索引表)+ASL (块内)
 

五，哈希查找

数据结构 查找

rar 5星 超过95%的资源 196KB

下载