六色网站,胶州网站优化,给个免费资源,wordpress cpanel查找 1. 基本概念2. 顺序表查找2.1 顺序查找2.2 顺序查找优化-哨兵 3. 有序表查找3.1 折半查找#xff08;二分查找#xff09; 4. 分块查找#xff08;索引顺序查找#xff09;5. Hash表#xff08;散列表#xff09;5.1 散列函数的设计5.2 代码实现5.2.1 初始化Hash表5… 查找 1. 基本概念2. 顺序表查找2.1 顺序查找2.2 顺序查找优化-哨兵 3. 有序表查找3.1 折半查找二分查找 4. 分块查找索引顺序查找5. Hash表散列表5.1 散列函数的设计5.2 代码实现5.2.1 初始化Hash表5.2.2 插入数据元素操作5.2.3 删除数据元素 5.2.4 完整实现 1. 基本概念
查找表由相同数据类型的数据元素构成的集合。 关键字数据元素中某个数据项它可以标识一个数据元素是唯一的。 查找Searching就是根据给定的某个值在查找表中找到一个关键字等于给定 值的数据元素。 静态查找表查找表中的数据元素不会发生变化 动态查找表查找表中的数据元素会发生变化插入、修改和删除 查找长度在查找运算中需要对比关键字的次数 平均查找长度ASL所查找过程中进行关键字比较次数的平均值用于衡量查找算法的效率包括成功和失败两种情况。
2. 顺序表查找
2.1 顺序查找
顺序查找线性查找用于在静态的线性表顺序表或链表中进行查找 算法的思想是从线性表的某一端开始把表中的元素和关键字逐个比较线性表的遍历
// 查找表arry中关键字key是否存在返回数组下标
int Search_Seql(int *array,int len,int key)
{for(int i 0;ilen;i){if(array[i]key){return i;}}return -1; // 查找失败
}2.2 顺序查找优化-哨兵
每次循环查找都需要对下标i是否越界进行判断可以把数组的首个元素设置为哨兵(需要数组把下标为0的位置预留给哨兵)从数组末尾开始遍历可以省略每次比较下标是否越界。
int Search_Seql_2(int* array,int len,int key)
{// 设置哨兵array[0]key; int i 0;for(i len-1;array[i]!key;i--); // 空语句return i; // 如果找到直接返回如果没找到则会下标为0此时返回0表示未找到
}3. 有序表查找
3.1 折半查找二分查找
折半查找二分查找只适用于有序升序或降序通常升序的顺序表不能是链表 算法思想在有序表中取中间作为比较对象如果查找目标大于中间记录的关键字那么在右半区继续查找如果查找目标小于中间记录的关键字则在左半区进行查找。不断重复上述过程直到找到查找成功或者查找完毕无法找到为止。
迭代方法实现
// 迭代实现
int Binary_Search1(int* array, int len, int key)
{int low 0, high len - 1;int mid (low high) / 2;while (low high){if (array[mid] key) // 找到{return mid;}else if (key array[mid]) //key小在左半区{high mid - 1;}else // key大在右半区{low mid 1;}mid (low high) / 2;}return -1; // 查找失败
}
递归实现
// 递归实现
int Binary_Search2(int* array, int key, int low, int high)
{if (lowhigh) // 查找失败{return -1;}int mid (low high) / 2;if(key array[mid]) // 找到{return mid;}// key小else if (key array[mid]){//向左递归return Binary_Search2(array, key, low, mid- 1);}//key 大else {// 向右递归return Binary_Search2(array, key, mid 1, high);}
}4. 分块查找索引顺序查找
分块查找索引顺序查找是顺序查找的一种改进方法。在此查找法中除表本身外还需要建立一个索引表。索引表中存放了每个分块的最大关键字和分块的起始地址。 分块有序
块内无序即每一块内的记录不要求有序块间有序即第一块第二块第三块…之间要求有顺序。
查找过程
先查找索引表确定待查找元素所属的分块顺序或折半查找在分块内使用顺序查找
5. Hash表散列表
散列Hash表这种数据结构的特点是数据元素关键字和它在表中的存储的地址直接相关。关键字与存储地址之间的对应关系的函数称为哈希函数。 哈希函数Address Hash(Key)
Hash是一种以常数平均时间执行插入、删除和查找的技术但是不支持元素排序和查找最小大值的操作Hash函数是一种映射关系很灵活任何关键字通过它的计算返回的值都落在表长允许的范围之内即可对于不同的关键字可能得到相同的Hash地址这种现象称为冲突Hash地址相同的关键字称为同义词。处理冲突的办法由四种链地址法、开放定址法、再散列法和建立公共溢出区。Hash表的装填因子表中记录数/表长越大关键字冲突的可能性越大同义词越多查找效率可能更低。 对于长度固定的散列表来说当数据分布的越均匀查找效率越高。
5.1 散列函数的设计
除留余数法Hash(key)key%p 如果散列表的表长为mp为小于等于m的最大质数在一般情况下对质数取余会让冲突更少数据元素在散列表中分布的更均匀。直接定址法Hash(key)a*keyb 这种方法的计算最简单不会产生冲突适合关键字的分布比较连续的情况如果关键字分布不连续空位较多会造成存储空间浪费。
散列函数的设计没有固定的方法需要结合实际情况考虑的因素有
清楚关键字分布情况散列表的大小合理太大浪费空间太小则产生太多的同义词散列表中的数据分布要均匀不要形成堆积散列函数代码要精简
5.2 代码实现
5.2.1 初始化Hash表
Hash表由存储链表头结点的数组数据元素单链表构成并且每个数据元素对应有关键字’key’和数值’value’因此需要构建三个结构体并对他们初始化
// Hash表中数据元素结构体
struct Element
{int key; // 关键字int value; // 数据元素可以是任意数据类型
};// 数据元素单链表
struct Node
{Element elem; // 数据元素Node* next; // next指针
};// Hash表
struct HashTable
{Node* head;// 数据元素存储地址动态分配数组int table_size;// 表的大小int count; // 数据元素个数
};// 初始化Hash表
HashTable* InitHashTable(int table_size)
{HashTable* ht new(HashTable);ht-table_size table_size; // 表长ht-count 0; // 数据元素个数// 分配和初始化数据元素单链表的头结点ht-head new Node[ht-table_size]; // 产生大小为table_size的数组用于存放头结点// 初始化单链表头结点for (int i 0; i ht-table_size; i){ht-head[i].next nullptr;ht-head[i].elem.key 0;ht-head[i].elem.value 0;}return ht;
}5.2.2 插入数据元素操作
Hash表根据数据元素的key生成一个Hash地址找到Hash地址对应的头结点后插入到头结点对应的单链表中这里使用的是头插法。实际开发中可以对value按照一定顺序插入
// Hash函数,产生Hash地址
unsigned int Hash(HashTable* hs, int key)
{return key % hs-table_size; // 除留余法对表长取余
}// 查找关键字为key的数据元素存在则返回结点地址
Node* Lookup(HashTable* hs, int key)
{int pos Hash(hs, key); // 找到Hash地址Node* pp hs-head[pos].next;// 从头结点下一个结点开始遍历这个单链表while (pp ! nullptr pp-elem.key ! key){pp pp-next;}return pp;
}// 向Hash表中插入数据元素
bool Insert(HashTable* hh, Element* ee)
{// 查找关键字是否存在存在则插入失败Node* pp Lookup(hh,ee-key);if (pp ! nullptr){return false;}// 不存在创建新的结点Node* qq new Node; qq-elem *ee;qq-next nullptr;// 插入新数据元素int pos Hash(hh, ee-key); // 获取Hash地址// 头插法Node head_node hh-head[pos]; // 找到头结点qq-next head_node.next;hh-head[pos].next qq;// 表中元素个数hh-count;return true;
}5.2.3 删除数据元素
从Hash表中删除数据元素也是根据它的key值生成一个Hash地址然后找到头结点遍历整个头结点对应的单链表找到key值对应结点的前一个结点删除最后key值对应的结点。
// 删除Hash表中的一个数据根据key删除数据
bool Delete(HashTable* hs, unsigned int key)
{// 根据key产生Hash地址int pos Hash(hs, key);Node* node_ptr hs-head[pos]; // 找到头结点所在位置while (node_ptr-next ! nullptr node_ptr-next-elem.key ! key) // 遍历单链表找到key前的结点{node_ptr node_ptr-next;}if (node_ptr-next nullptr) // 查找失败{return false;}// 删除链表结点Node* delete_node node_ptr-next;node_ptr-next delete_node-next;delete delete_node;hs-count--;return 0;
}
5.2.4 完整实现
#include iostream
using namespace std;// Hash表中数据元素结构体
struct Element
{int key; // 关键字int value; // 数据元素可以是任意数据类型
};// 数据元素单链表
struct Node
{Element elem; // 数据元素Node* next; // next指针
};// Hash表
struct HashTable
{Node* head;// 数据元素存储地址动态分配数组int table_size;// 表的大小int count; // 数据元素个数
};// 初始化Hash表
HashTable* InitHashTable(int table_size)
{HashTable* ht new(HashTable);ht-table_size table_size; // 表长ht-count 0; // 数据元素个数// 分配和初始化数据元素单链表的头结点ht-head new Node[ht-table_size]; // 产生大小为table_size的数组用于存放头结点// 初始化单链表头结点for (int i 0; i ht-table_size; i){ht-head[i].next nullptr;ht-head[i].elem.key 0;ht-head[i].elem.value 0;}return ht;
}// Hash函数,产生Hash地址
unsigned int Hash(HashTable* hs, int key)
{return key % hs-table_size; // 除留余法对表长取余
}// 查找关键字为key的数据元素存在则返回结点地址
Node* Lookup(HashTable* hs, int key)
{int pos Hash(hs, key); // 找到Hash地址Node* pp hs-head[pos].next;// 从头结点下一个结点开始遍历这个单链表while (pp ! nullptr pp-elem.key ! key){pp pp-next;}return pp;
}// 向Hash表中插入数据元素
bool Insert(HashTable* hh, Element* ee)
{// 查找关键字是否存在存在则插入失败Node* pp Lookup(hh,ee-key);if (pp ! nullptr){return false;}// 不存在创建新的结点Node* qq new Node; qq-elem *ee;qq-next nullptr;// 插入新数据元素int pos Hash(hh, ee-key); // 获取Hash地址// 头插法Node head_node hh-head[pos]; // 找到头结点qq-next head_node.next;hh-head[pos].next qq;// 表中元素个数hh-count;return true;
}// 打印Hash表
void PrintHash(HashTable* hs)
{for (int i 0; i hs-table_size; i){Node* pp hs-head[i].next;// 招待第一个结点while (pp){cout [ pp-elem.key - pp-elem.value ] ;pp pp-next;}cout ^\n;}
}// 删除Hash表中的一个数据根据key删除数据
bool Delete(HashTable* hs, unsigned int key)
{// 根据key产生Hash地址int pos Hash(hs, key);Node* node_ptr hs-head[pos]; // 找到头结点所在位置while (node_ptr-next ! nullptr node_ptr-next-elem.key ! key) // 遍历单链表找到key前的结点{node_ptr node_ptr-next;}if (node_ptr-next nullptr) // 查找失败{return false;}// 删除链表结点Node* delete_node node_ptr-next;node_ptr-next delete_node-next;delete delete_node;hs-count--;return 0;
}// 销毁Hash表
void DestoryHash(HashTable* hs)
{if (hs nullptr){return;}// 遍历Hash表释放全部单链表for (int i 0; i hs-table_size; i){// 访问每个头结点的下一个结点Node* tmp_Ptr hs-head[i].next;while (tmp_Ptr){Node* next_Ptr tmp_Ptr-next;delete tmp_Ptr;// 访问下一个结点tmp_Ptr next_Ptr;}}hs-count 0;hs-table_size 0;// 释放头结点数组delete [] hs-head;// 删除Hash表delete hs;
}
int main(void)
{HashTable* hs InitHashTable(10);// 数据元素Element ee;// 插入数据元素ee.key 10; ee.value 110; Insert(hs, ee);ee.key 11; ee.value 111; Insert(hs, ee);ee.key 12; ee.value 112; Insert(hs, ee);ee.key 13; ee.value 113; Insert(hs, ee);ee.key 14; ee.value 114; Insert(hs, ee);ee.key 15; ee.value 115; Insert(hs, ee);ee.key 16; ee.value 116; Insert(hs, ee);ee.key 17; ee.value 117; Insert(hs, ee);ee.key 18; ee.value 118; Insert(hs, ee);ee.key 19; ee.value 119; Insert(hs, ee);ee.key 20; ee.value 120; Insert(hs, ee);ee.key 21; ee.value 121; Insert(hs, ee);PrintHash(hs);if (Lookup(hs, 21) nullptr){cout 查找key21失败 endl;}else{cout key21,value Lookup(hs, 21)-elem.value endl;}Delete(hs, 21);PrintHash(hs);if (Lookup(hs, 21) nullptr){cout 查找key21失败 endl;}else{cout key21,value Lookup(hs, 21)-elem.value endl;}DestoryHash(hs);return 0;
}
