【数据结构】数据结构与算法基础课程笔记第七章查找

分类	作用
主关键字	唯一地标识一条记录（只对应一个数据元素）
次关键字	可用于识别若干记录（用次关键字找具体的数据项）

3、如何显示查找的结果？

若查找成功，则结果给出整个记录的信息，或给出记录在查找表中的位置；

若查找失败，则结果给出 “空记录” 或 “空指针” 。

4、查找的目的是什么？

在不在：查询某个特定的元素是否在表中
有没有：检索某个特定元素的各种属性
打基础：作为之后将要进行的插入或删除操作的基础

5、查找表怎么分类？

类型	功能
静态查找表	仅作查询操作
动态查找表	做插入和删除操作

6、如何评价查找算法的优劣性？

我们评价查找算法的优劣性的根据，是算法中关键字的比较次数，也就是平均查找长度（ASL，Average Search Length）。

平均查找长度就是关键字比较次数的期望值（查找第i个记录的概率乘以找到它所需的比较次数，再求和）：

7、在学习查找算法的过程中，我们要研究的是什么？

查找的方法取决于查找表的结构，我们在对算法进行优化之前，就要先研究查找表的存储结构，在集合中的数据元素之间人为地加上某种确定的约束关系，提高查找的效率。

总之，我们要研究的就是查找表的各种组织方法及其查找过程的实施。

作者离期末考只剩两周啦！正在紧张备考中，所以接下来就只是记录一下知识的自用笔记，没有过多的讲解，等到暑假再做一下优化~

二、线性表的查找

1. 顺序查找

1.1 顺序表的类型定义

typedef struct{
	KeyType key;//关键字域 
}ElemType;

typedef struct{
	ElemType *R;//表的基地址 
	int length;//表长 
}SSTable;//Sequential Search Table
SSTable ST;//定义顺序表ST

1.2 顺序查找应用范围

顺序表或线性链表表示的静态查找表
表内元素之间无序

1.3 顺序查找算法

初始版

int Search_Seq(SSTable ST,KeyType key){
	for(int i=ST.length;i>=1;i--)
		if(ST.R[i].key==key) return i;
	return 0;
}//若查找成功，则返回其位置信息，否则返回0

进阶版（设置监视哨兵，减少比较次数）

int Search_Seq(SSTable ST,KeyType key){
	ST.R[0].key=key;
	for(i=ST.length;ST.R[i].key!=key;i--)
		return i;
}//若查找成功，则i不为0，返回当前i的值

改进前后的顺序查找算法，时间复杂度都为O(n)。

1.4 提高查找效率的方法

1.5 查找算法的优缺点

优点：算法简单，逻辑次序无要求，且不同存储结构均适用。

缺点：ASL太长，时间效率太低。

2. 折半查找

又称二分查找，每次将待查记录所在区间缩小一半。

2.1 折半查找算法

int Search_Bin(SSTable ST,KeyType key){
	int low =1,high=ST.length;//设置区间两端 
	while(low<=high){
		mid=(low+high)/2;
		if(ST.R[mid].key==key) return mid;//找到待查元素 
		else if(key<ST.R[mid].key) high=mid-1;//继续在前半区间进行查找 
		else low=mid+1;//继续在后半区间进行查找 
	}
	return 0;//顺序表中不存在待查元素 
}