首页 1 2 3 4 5 6 7

【数据结构笔记】数据结构基础—查找

1.查找

概念

•设记录表L=(R1 R2……Rn)，其中Ri(l≤i≤n)为记录，对给定的某个值k，在表L中确定key=k的
记录的过程，称为查找。

•若表L中存在一个记录Ri的key=k，记为Ri.key=k，则查找成功，返回该记录在表L中的序号i(或Ri 的地址)，否则(查找失败)返回0(或空地址Null)。

方法

查找方法有顺序查找、折半查找、分块查找、Hash表查找等等。查找算法的优劣将影响到计算机的使用效率，应根据应用场合选择相应的查找算法。

平均查找长度

对查找算法，主要分析其T(n)。查找过程是key的比较过程，时间主要耗费在各记录的key与给定k值的比较上。比较次数越多，算法效率越差（即T(n)量级越高），故用“比较次数”刻画算法的T(n)。一般以“平均查找长度”来衡量T(n)。

平均查找长度ASL（Average Search Length）：对给定k，查找表L中记录比较次数的期望值(或平均值)，即：

Pi为查找Ri的概率。等概率情况下Pi=1/n；Ci为查找Ri时key的比较次数(或查找次数)。

顺序查找算法

对于顺序查找算法，ASL=O(n)，效率是很低的，意味着查找某记录几乎要扫描整个表，当表长n很大时，会令人无法忍受。

折半查找算法

对给定值k，逐步确定待查记录所在区间，每次将搜索空间减少一半(折半)，直到查找成功或失败为止。
设两个游标low、high，分别指向当前待查找表的上界(表头)和下界(表尾)。mid指向中间元素。

分块查找

1.分块

设记录表长为n，将表的n个记录分成b=n/s(向上取整)个块，每块s个记录（最后一块记录数可以少于s个），即：

且表分块有序，即第i（1≤i≤b-1）块所有记录的key小于第i+1块中记录的key，但块内记录可以无序。

2.建立索引

每块对应一索引项：
其中kmax为该块内记录的最大key；link为该块第一记录的序号（或指针）。

例题

总结

        顺序、折半、分块查找和树表的查找中，其ASL的量级在O(n)～O(log2n)之间。
        不论ASL在哪个量级，都与记录长度n有关。随着n的扩大，算法的效率会越来越低。
        ASL与n有关是因为记录在存储器中的存放是随机的，或者说记录的key与记录的存放地址无关，因而查找只能建立在key的“比较”基础上。（如何让查找不建立在比较的基础之上呢？）

2.hash表原理

2.1概念

理想的查找方法是：对给定的k，不经任何比较便能获取所需的记录，其查找的时间复杂度为常数级O(C)。
这就要求在建立记录表的时候，确定记录的key与其存储地址之间的关系f，即使key与记录的存放地址H相对应：

        当要查找key=k的记录时，通过关系f就可得到相应记录的地址而获取记录，从而免去了key的比较过程。
        这个关系f就是所谓的Hash函数（或称散列函数、杂凑函数），记为H(key)。
        它实际上是一个地址映象函数，其自变量为记录的key，函数值为记录的存储地址（或称Hash地址）。

不同的key可能得到同一个Hash地址，即当key1≠key2时，可能有H(key1)=H(key2)，此时称key1和key2为同义词。这种现象称为“冲突”或“碰撞”，因为一个数据单位只可存放一条记录。
一般，选取Hash函数只能做到使冲突尽可能少，却不能完全避免。这就要求在出现冲突之后，寻求适当的方法来解决冲突记录的存放问题。

根据选取的Hash函数H(key)和处理冲突的方法，将一组记录(R1 R2……Rn)映象到记录的存储空间，所得到的记录表称为Hash表，如图：

        选取（或构造）Hash函数的方法很多，原则是尽可能将记录均匀分布，以减少冲突现象的发生。以下介绍几种常用的构造方法。
        直接地址法
        平方取中法
        叠加法
        保留除数法
        随机函数法

2.2保留除数法

又称质数除余法，设Hash表空间长度为m，选取一个不大于m的最大质数p，令： H(key)=key%p。（质数：指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。）

举例

        设记录的key集合k={28，35，63，77，105……}，若选取p=21=3*7（包括质数因子7），有：
           key：28 35 63 77 105 ……
          H(key)=key%21： 7 14 0 14 0 ……
        使得包含质数因子7的key都可能被映象到相同的单元，冲突现象严重。

        若取p=19（质数），同样对上面给定的key集合k，有：
          key：28 35 63 77 105
          H(key)=key%19： 9 16 6 1 10
           H(key)的随机度就好多了。

2.3处理冲突的方法

选取随机度好的Hash函数可使冲突减少，一般来讲不能完全避免冲突。设Hash表地址空间为0～m-l（表长为m）：

冲突是指：表中某地址j∈[0，m-1]中己存放有记录，而另一个记录的H(key)值也为j。

处理冲突的方法一般为：在地址j的前面或后面找一个空闲单元存放冲突的记录，或将相冲突的诸记录拉成链表。
在处理冲突的过程中，可能发生一连串的冲突现象，即可能得到一个地址序列H1、H2……Hn，Hi∈[0，m-l]。H1是冲突时选取的下一地址，而H1中可能己有记录，又设法得到下一地址H2……直到某个Hn不发生冲突为止。这种现象称为“聚积”，它严重影响了Hash表的查找效率。

冲突现象的发生有时并不完全是由于Hash函数的随机性不好引起的，聚积的发生也会加重冲突。

还有一个因素是表的装填因子α，α=n/m，其中m为表长，n为表中记录个数。一般α在0.7～0.8之间，使表保持一定的空闲余量，以减少冲突和聚积现象。

2.3.1开放地址法

当发生冲突时，在H(key)的前后找一个空闲单元来存放冲突的记录，即在H(key)的基础上获取下一地址：
Hi = ( H(key) + di ) % m
其中m为表长，%运算是保证Hi落在[0，m-l]区间；di为地址增量。di的取法有多种：
（1）di=1，2，3，……(m-1)——称为线性探查法；
（2）di=1^2，-1^2，2^2，-2^2，……——称为二次探查法。

举例

设记录的key集合k={23，34，14，38，46，16，68，15，07，31，26}，记录数n=11。
令装填因子α=0.75，取表长m= n/α =15（向上取整）。
用“保留余数法”选取Hash函数（p=13）：
H(key) = key % 13

68对13取余等于3，和16重复了，故带入公式3+1对15取余等于4，故68放到4的位置，其他同理

2.3.2链地址法

发生冲突时，将各冲突记录链在一起，即同义词的记录存于同一链表。

设H(key)取值范围（值域）为[0,m-1]，建立头指针向量HP[m]，HP[i]（0≤i≤m-l）初值为空。

设H(key)=key%13，k={ 23，34，14，38，46，16，68，15，07，31，26 }

链地址法解决冲突的优点：无聚积现象；删除表中记录容易实现。

3.hash表的实现

#define N 15
typedef int datatype;

typedef struct node {  // 键值对儿，这里和python的字典有点不一样
	datatype key;		// 值
	datatype value; // 是H(key)，即key所对应的位置
	struct node * next;
}listnode, *linklist;

typedef struct {
	listnode data[N];
}hash;

创建

hash * hash_create() {
	hash * HT;  // 整个hash表

	if ((HT = (hash *)malloc(sizeof(hash))) == NULL) {
		printf("malloc failed\n");
		return NULL;
	}

	memset(HT, 0, sizeof(hash)); // 这样写效率更高，使得诸如data[11].key、data[11].value都为0

	return HT;
}

插入

int hash_insert(hash *HT, datatype key) {
	linklist p, q;

	if (HT == NULL) {
		printf("HT is NULL\n");
		return -1;
	}

	if ((p = (linklist)malloc(sizeof(listnode))) == NULL) { // 创建新节点
		printf("malloc failed\n");
		return -1;
	}
  // 初始化新节点中的值
	p->key = key;
	p->value = key % N;
	p->next = NULL;

	q = &(HT->data[key % N]); // HT->data[key % N]是一个节点，此时q指向hash表中key待插入的位置

// 如果q->next为1，表明key的待插入位置（即H(key)）已经插入过节点了
// 由于插入是顺序插入，所以要比较新插入的节点的key和已有的节点的key哪个大，大的放后面
	while (q->next && q->next->key < p->key ) {
		q = q->next;
	}

	p->next = q->next;
	q->next = p;

	return 0;

}

查找

// 先找hash表中对应的位置，再看这个位置有没有重复的
linklist  hash_search(hash *HT, datatype key) {
	linklist p;

	if (HT == NULL) {
		printf("HT is NULL\n");
		return NULL;
	}

	p = &(HT->data[key % N]);

	while (p->next && p->next->key != key) {
		p = p->next;
	}

	if (p->next == NULL) {
		return NULL;
	} else {
		printf("found\n");
		return p->next;
	}
}

当先锋百科网