数据结构课件 第10章 散列.ppt

第十章散列
理解抽象数据类型符号表的概念。
掌握数组实现符号表的方法。
理解开散列和闭散列的概念。
掌握用开散列表实现符号表的方法。
掌握除余法、数乘法、平方取中法、基数转换法和随机数法等散列函数构造方法。
掌握采用线性重新散列技术的闭散列表实现符号表的方法。
11/11/2017
1
福州大学数学与计算机科学学院
10 散列
引言
ADT符号表的概念
以集合为基础,并支持Member、Insert和Delete三种运算的抽象数据类型叫做符号表。
ADT符号表的应用
公司的客户字典
一个地区的固定/移动电话号码字典
软件开发中的数据字典
网上的在线字典
互联网/企业网/局域网网管中的IP地址字典等等
11/11/2017
2
福州大学数学与计算机科学学院
10 散列
实现符号表的简单方法——用固定数组
 
template <class T>
class ADictionary //无序
{public:ADictionary(int size);
~ADictionary( );
int Member(const T& x);
void Insert(const T& x);
void Delete(const T& x);
private:
int arraysize;//数组的规模
int last;//数组中自左至右第一个不放符号表数据的分量下标
T *data;
};
11/11/2017
3
福州大学数学与计算机科学学院
10 散列
实现符号表的简单方法——用固定数组
符号表类Adictionary的定义中未实现的函数
(1和2)构造函数和析构函数
template <class T>
ADictionary<T>::ADictionary(int size): arraysize(size)
{data = new T [arraysize];
last = 0;}
template <class T>
ADictionary<T>::~ADictionary( )
{delete [ ] data;
}
11/11/2017
4
福州大学数学与计算机科学学院
10 散列
实现符号表的简单方法——用固定数组
符号表类Adictionary的定义中未实现的函数
(3)成员关系函数Member 
template <class T>
int ADictionary<T>::Member(const T& x)
{
for (int i = 0; i < last; i++)
if ( data[i] == x ) return 1 ;
return 0;
}
11/11/2017
5
福州大学数学与计算机科学学院
10 散列
实现符号表的简单方法——用固定数组
符号表类Adictionary的定义中未实现的函数
(4) 插入运算Insert
template <class T>
void ADictionary<T>::Insert(const T& x)
{
if(!Member(x)&&last<arraysize)data[last++]=x;
}
11/11/2017
6
福州大学数学与计算机科学学院
10 散列
实现符号表的简单方法——用固定数组
符号表类Adictionary的定义中未实现的函数
(5)删除运算Delete
template <class T>
void ADictionary<T>::Delete(const T& x)
{
if (last > 0){
int i=0;
while (i<last && data[i]!=x) i++;
if (i<last) data[i]=data[--last];
} //技巧
}
11/11/2017
7
福州大学数学与计算机科学学院
10 散列
实现符号表的简单方法——用固定数组
优缺点
优点:
结构简单,实现操作的逻辑简单。
缺点:
所表示的集合的大小受到数组大小的限制。
三个基本操作在最坏情况下都需要O(n)。
通常集合元素并不占满整个数组,空间没有得到充分利用。
11/11/2017
8
福州大学数学与计算机科学学院
10 散列
实现符号表的简单方法——开散列
基本设想
把符号表中的所有元素散列(hashing)即映射到一个桶数组(散列表)的桶中。当有多个不同元素被散列到同一个