算法(一)
發佈於 2019-03-08
本篇开始，我们来看看在工作中比较常用的两大算法之一的查找算法。
概论
查找表(Search Table): 是由同一类型的数据元素构成的集合。 关键字(Key): 是数据元素中某个数据项的值，又称为键值。 若此关键字可以唯一地标识某一记录，则称此关键字为主关键字(Primary Key)。
查找(Searching)就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。
顺序查找表
顺序查找(Sequential Search)又称为线性查找，是最基本的查找技术，他的查找过程是: 从表中第一个(或最后一个)记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录，如果直到最后一个(或第一个)记录，其关键字和给定值都不相等时，则表中没有所查的记录，查找不成功。
class SequentialSearch<T>
{
public static T[] Sequential;
public SequentialSearch(T[] sequential)
{
Sequential = sequential;
}
public Status SequentialSearching(T key, out T record)
{
foreach (var s in Sequential)
{
if (!s.Equals(key)) continue;
record = s;
return Status.Ok;
}
record = default(T);
return Status.Error;
}
}有序查找表
最常用的有序查找就是折半查找。折半查找又称为二分查找(Binary Search)，他的前提是线性表中的记录必须是关键码有序，线性表必须采用顺序存储。折半查找的基本思想是: 在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功，若给定值小于中间记录的关键字，则在中间记录的左半区继续查找，若给定值大于中间记录的关键字，则在中间记录的右半区继续查找，不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。
class BinarySearching
{
public static int[] Binary;
public BinarySearching(int[] binary)
{
Binary = binary;
}
public Status BinarySearch(int key, out int record)
{
var low = 0;
var high = Binary.Length;
while (low <= high)
{
var mid = (low + high) / 2;
if (Binary[mid] < key)
{
low = mid + 1;
}
else if (Binary[mid] > key)
{
high = mid - 1;
}
else
{
record = Binary[mid];
return Status.Ok;
}
}
record = default(int);
return Status.Error;
}
}线性索引查找
数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与他对应的记录相关联的过程。索引技术是组织大型数据库以及磁盘文件的一种重要技术。
索引按照结构可以分为线性索引、树形索引、多级索引。本篇只介绍线性索引。
所谓线性索引就是将索引项集合组织为线性结构，也称索引表。我们介绍三种线性索引:
- 稠密索引
- 分块索引
- 倒排索引
稠密索引
稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项，索引项一定是按照关键码有序的排列。
分块索引
分块有序，是把数据集的记录分成若干块，并且这些块满足:
- 块内无序
- 块间有序
对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引。 分块索引普遍用于数据库表查找等技术中。
倒排索引
用于最基础的搜索技术。本篇略过。
二叉排序树
二叉排序树(Binary Sort Tree)又称为二叉查找树。他或是一棵空树，或者是具有下列性质的二叉树:
- 若他的左子树不空，则左子树上所有结点的值均小于他的根节点的值
- 若他的右子树不空，则右子树上所有结点的值均大于他的根节点的值
- 他的左右子树也分别为二叉排序树
class BinarySortTree
{
public BiTree RootBiTree { get; set; }
//查找
public Status SearchBst(int key, BiTree rootBiTree)
{
var temp = rootBiTree;
if (temp == null)
{
return Status.Error;
}
if (temp.Data == key)
{
return Status.Ok;
}
if (temp.Data > key)
{
temp = temp.LBiTree;
return SearchBst(key, temp);
}
temp = temp.RBiTree;
return SearchBst(key, temp);
}
//插入
public Status InsertBst(int record)
{
var bt = new BiTree
{
Data = record
};
if (RootBiTree == null)
{
RootBiTree = bt;
return Status.Ok;
}
var current = RootBiTree;
while (true)
{
var parent = current;
if (current.Data <= bt.Data)
{
if (current.Data >= bt.Data) return Status.Error;
current = current.RBiTree;
if (current != null) continue;
parent.RBiTree = bt;
break;
}
current = current.LBiTree;
if (current != null) continue;
parent.LBiTree = bt;
break;
}
return Status.Ok;
}
}散列表查找
散列技术是在记录的存储位置和他的关键字之间建立一个确定的对应关系 f，使得每个关键字 key 对应一个存储位置 f(key)。 我们把这种对应关系 f 称为散列函数，又称为哈希函数(Hash)。采用散列技术将记录存储在一块连续的存储空间中，这块存储空间称为散列表或哈希表(Hash Table)。
两个关键字 key1 不等于 key2，但是 f(key1) = f(key2)，这种现象我们称为冲突。
散列函数的构造方法
好的散列函数:
- 计算简单
- 散列地址分布均匀
散列函数构造方法可分为:
- 直接定址法
- 数字分析法
- 平方取中法
- 折叠法
- 除留余数法
- 随机数法
处理散列冲突的方法
- 开放定址法
- 再散列函数法
- 链地址法