第15讲 查找和排序.ppt

第15讲查找和排序
领会和掌握HASH查找原理和方法
掌握HASH查找解决地址冲突的方法:
线性探测再散列和链地址法
掌握线性探测再散列和链地址法的函数编写
领会和掌握排序方法:简单插入、简单选择、基数排序
关键字:就是数据元素中可以标识该数据元素
的数据项,Keyword。
查找:就是根据给定的关键字值,在一组数据
元素中确定一个其关键字值等于给定值
的数据元素的过程。若存在这样的数据
元素,则称查找是成功的;否则称查找
不成功。search
查找表:待查的数据元素集合
什么是查找
衡量一个算法的标准主要有两个:时间和空间
查找算法通常只需要一个或几个辅助空间,因
此主要看查找算法的查找速度(即时间)。
在查找算法中,基本运算是给定值与关键字值
的比较,即算法的主要时间是花费在“比较”上
的。所以评价一个查找算法的好坏主要看比较
次数的多少。
查找算法的评价
折半查找的算法
开始
结束
hig>=low
A[mid]==X
A[mid]>X
(hig+low)/2->mid
mid-1->hig
返回mid
0->mid
mid+1->low
折半查找的算法
查找表的存储结构采用顺序表类
template <class datatype>
class search_list //查找表类的定义
{ private:
datatype *data; //数据元素数组的首地址
int maxsize; //查找表的最大可能长度
int last; //表尾数据元素的下标
public:
search_list() //创建100个元素的线性表的构造函数
{
maxsize=100;
data=new datatype[maxsize];
last=-1; //last为―1表示为空表
}
search_list(int sz) //创建sz个元素的线性表的构造函数
{
if(sz>0) //判定sz是否大于0
maxsize=sz;
else
maxsize=100;
data=new datatype[maxsize];
last=-1; //last为-1表示为空表
}
bool isempty(){ return last==-1?true:false; } //判空表
bool isfull(){ return last==maxsize-1; } //判表满
int length(){ return last+1; } //求表长
bool getdata(int i,datatype &x) //取元素
{
i--;
if (i>=0&&i<=last)
{
x = data[i];
return true;
};
return false;
}
bool get_prior(int i,datatype &x); //取前驱元素
bool (int i,datatype &x); //取后继元素
bool replace(int i,datatype x); //置换元素
bool insert_data(int i,datatype x); //向查找表中插入一个元素
bool delete_data(int i); //从查找表中删除一个元素
void print_list(); //打印查找表中所有元素
bool create_hash1(datatype *pa,int n); //创建线性探测哈希表
bool create_hash2(datatype *pa,int n); //创建二次探测哈希表
bool create_hash3(datatype *pa,int n); //创建链地址法哈希表
int hash_find1(datatype x); //线性探测的哈希查找
int hash_find2(datatype x); //二次探测的哈希查找
int hash_find3(datatype x); //链地址的哈希查找
~search_list(){ delete[]data; } //析构函数
};
哈希查找方法是对关键字进行某种函数公式
运算后直接得到数据元素的存
贮位置(或地址),这种函数
公式称哈希函数
在一块连续的内存空间采用哈希查找方法将
所有数据元素重新组织建立起来的查找表就
称为哈希表
什么是哈希查找
学号
姓名
性别
成绩
03191001
曹屿崢
女
95
03191002
陈娇
女
87
03191003
冯宁宁
女
90
03191004
李晶
女
85
03191