数据结构·查找

查找的基本概念

• 查找
• 查找表
• 静态查找表
  • 适合的方法有顺序查找、折半查找、散列查找等
• 动态查找表
  • 适合的方法有二叉排序树的查找、散列查找等
• 关键字
• 平均查找长度
  • $ASL=\sum_{i=1}^nP_iC_i$

顺序查找和折半查找

顺序查找

• 一般线性表
  • 哨兵
• 有序表

折半查找

• 算法
• 判定树
• ASL

分块查找

• 块间有序
• 块内无序
• $ASL_{min}=\sqrt n+1$

散列表

散列表的基本概念

• 散列函数
• 冲突
• 同义词
• 散列表
• 装填因子

散列函数的构造方法

• 直接定址法（示例）
• 除留余数法（上面示例可以转化为使用除留余数法的版本）
• 数字分析法
• 平方取中法（示例）

处理冲突的方法

• 开放定址法
  • 线性探测法
  • 平方探测法（二次探测法）
  • 双散列法
  • 伪随机序列法
• 拉链法

散列查找及性能分析

C语言使用平方取中法实现散列表的示例

代码如下：

#include <stdio.h>
#define Wdith 8

int transfer(char c) {
	int transfered = c * c;
	transfered = transfered >> 4;
	transfered = transfered % 255;
	return transfered;
}

int get (char c, int *count) {
	int transfered = transfer(c);
	/* printf("transfered: %d\n", transfered); */

	return count[transfered];
}

void inc(char c, int *count) {
	int transfered=transfer(c);
	count[transfered]++;
}

void dec(char c, int *count) {
	int transfered=transfer(c);
	count[transfered]--;
}

int test_char_count();

int main() {
	/* for (char c='a';c<='z';c++) */
	/* 	get(c,NULL); */

	test_char_count();

	return 0;
}

// 统计字符串中各个小写字母出现的次数
int test_char_count(){
	printf("test_char_count...\n");
	char str[]="hello, world!";
	printf("str: %s\n", str);

	int count[256];
	for (int i=0;i<256;i++)
		count[i]=0;

	for (int i=0;str[i]!='\0';i++)
		inc(str[i], count);

	printf("counts:\n");

	for (int i='a';i<='z';i++){
		if (get(i,count)!=0)
			printf("%c: %d\n", i, get(i,count));
	}

	return 0;
}

C语言使用类直接定址法实现散列函数的小测试

代码如下：

#include <stdio.h>
#define MapLength 26

int get(char c, int *count) {
	return count[c-97];
}

void inc(char c, int *count) {
	count[c-97]++;
}

void dec(char c, int *count) {
	count[c-97]--;
}

int test_char_count();

int main(){
	int count[MapLength];
	for (int i=0;i<MapLength;i++)
		count[i]=0;

	int e;
	e = get('a', count);
	printf("get('a') -> %d\n", e);

	inc('a',count);
	e = get('a', count);
	printf("get('a') -> %d\n", e);

	test_char_count();

	return 0;
}

// 统计字符串中各个小写字母出现的次数
int test_char_count(){
	printf("test_char_count...\n");
	char str[]="hello, world!";
	printf("str: %s\n", str);

	int count[MapLength];
	for (int i=0;i<MapLength;i++)
		count[i]=0;

	for (int i=0;str[i]!='\0';i++)
		inc(str[i], count);

	printf("counts:\n");

	for (int i='a';i<='z';i++){
		if (get(i,count)!=0)
			printf("%c: %d\n", i, get(i,count));
	}

	return 0;
}