数据结构-查找（顺序查找，加监视稍，折半查找（代码实现），分块查找散链表（哈希表）查找（无代码））

日期： 2019-11-22 分类：跨站数据测试 300次阅读

查找算法

数据结构-查找（顺序查找，加监视稍，折半查找（代码实现），分块查找，散链表查找（无代码））
一，顺序查找1
按照线性顺序，一个一个的比较，找到返回其位置，找不到返回值0

int Seq_Search1(SeqList p,DataType a)
{
	int i=1;
	while(i<=p.length&&p.data[i]!=a)
	{
		i++;
	}
	if(i>p.length)
		return 0;
	else 
		return i;
}

二，顺序查找2（加监视稍）

int Seq_Search2(SeqList p,DataType a)
{
	int i;
	p.data[0]=a;//监视稍
	i=p.length;
	while(p.data[i]!=a)
	{
		i--;
	}
	return i;
}

比较次数少，效率更高！！！

顺序表上的顺序查找性能分析

对于n个元素的查找表，若查找的是第i个记录时，需进行n-i+1次关键字比较，即ci=n-i+1。设查找每个元素的概率相等。
查找成功时，顺序查找的平均查找长度为：
在这里插入图片描述

查找不成功时，表中每个关键字都要比较一次，直到监视哨，因此关键字的比较次数总是n+1次

在这里插入图片描述

二，折半查找
折半查找的思想为：在有序表中，取中间元素作为比较对象，
若给定值与中间元素的关键字相等，则查找成功；若给定值小
于中间元素的关键字，则在中间元素的左半区继续查找；若给
定值大于中间元素的关键字，则在中间元素的右半区继续查找。
不断重复上述查找过程，直到查找成功，或所查找的区域无数
据元素，查找失败。

例如: key=64 的查找过程如下：
在这里插入图片描述

伪代码
key≠data[mid],key>p.data[mid]
∴low=mid+1
mid=(low+high)/2

a≠data[mid],key<data[mid]
∴high=mid-1
mid=(low+high)/2

a=data[mid] 此时就找到了key（关键字）
返回 mid 下标值

int Binary_Search(SeqList p,DataType a)
{
    int mid,low=1,high=p.length;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(a==p.data[mid])
		{return mid;}
		else if(a<p.data[mid])
		{high=mid-1;}
		else
			low=mid+1;
		return 0;
	}
}