数据结构之查找
查找的方法大致有两大种：线性和非线性
其中线性查找（静态查找）有：顺序查找和有序查找
非线性查找（动态查找）包括：搜索二叉树（改进：平衡二叉树，红黑树），B树（2-3树，2-3-4树，B树，B+树），散列表
一、线性查找
(1) 顺序查找：
顺序查找其实就是相当于数组查找或链表查找，for或while解决
数组查找：
int search1(vector<int>array,int target){ for(int i=0;i<array.size();++i){ if(array[i]==target) return i; } return -1;//-1表示查找失败 } //优化：可以增加一维空间，添加一个哨兵---其实我觉得没什么必要 int search2(vector<int>array,int target){ array.insert(array.begin(),target); int i=array.size()-1; while(array[i]!=target) --i; return i-1;//返回-1表示查找失败 }链表查找
ListNode* search3(ListNode *head,int target){ while(head){ if(head->val==target){ return head; } } return nullptr;//表示没找到节点 }(2) 有序查找
有序查找其实最常用到的就是二分查找。有序查找主要二分查找为基础，加上一些改进后的查找方法。二分查找
由于队列有序，因此可以不断的从中间左右两边去查找，一半一半的找。
关键点是：while(left<right)还是while(left<=right),mid=left+(right-left)>>1;//如果是查几个数之和为target，则是while(left<right) //如果只是查一个数，那么就是while(left<=right) int search1(vector<int>array,int target){ int left=0,right=array.size()-1; while(left<=right){ int mid=left+(right-left)>>1; if(array[mid]==target) return mid; else if(array[mid]<target) left=mid+1; else right=mid-1; } return -1;//表示没找到 }插值查找
对二分查找的mid进行修改，改为：mid=left+(right-left)*(target-array[left])/(array[right]-array[left]);
其适用于关键字分布比较均匀的查找表。斐波那契查找
因为斐波纳契数列越往后的数，相邻两个的比值越接近黄金分割比例，因此，我们可以利用这一特点，对查找数列进行黄金分段。即对长度为len，F[n-1]<len<=F[n]的查找列分段为：左边长度F[n-1],右边长度F[n-2]。为得到斐波纳契数列中数的大小，需要对原数组长度进行延展。因而，最后返回查找结果时，也得判断是否超了原数组大小，如是，咋返回最后一个位置。int search2(vector<int>array,int target){ //首先，需要得到一个斐波纳契数列,最后一个元素就是所要的长度 const int len=array.size(); vector<int>F;F.push_back(0);F.push_back(1); for(int i=0;len>F.back();++i){ F.push_back(F[i]+F[i+1]); } int k=F.size()-1; //重建新的数组 vector<int>new_array(array); for(int i=0;i<(F[k]-len);++i){ new_array.push_back(array.back()); } //查找 int left=0,right=F[k]-1; while(left<=right){ int mid=left+F[k-1]-1; if(new_array[mid]>target){ right=mid-1; --k; } else if(new_array[mid]<target){ left=mid+1; k-=2; } else return mid<=len-1 ? mid:len-1; } }二、非线性查找
搜索二叉树、平衡二叉树在之前的关于树的总结这篇文章中已经详细讲诉，这里就不赘述了。
(1) B树
谈一下，另一种用来查找的特殊的树，多路查找树，也叫B树，其实就是改造原来树的节点的结构，
A.让每一个树节点可以包含多个元素，
B.且不像二叉树，B树一个节点可以有多个孩子。
C.另外，B树必须是很平衡的树，即叶节点必须都在最后一层，且每个节点要么无子节点，要么就必须是含>=2个节点。
D.B树的节点可以混搭，如果其中最大的节点是k节点(含k-1个元素，连k个子节点)，则称该树为k阶B树。
常见的有：2树，2-3树，2-3-4树，这都属于特殊的B树
(2) B+树
B+树其实就是进一步改变B树的节点结构，让每个节点的末尾多一个记录父节点的数据，这样，查找的时候，只要找到范围，就可以直接顺序读取所有数据了，不用像中序遍历那样，来回跑。
如图：
这样有助于查找一个范围内数据，比如我要[4，9]的数据，只要查到3节点介于3，5间的节点，然后直接向右遍历就可以得到这个范围的数据了。
(3) 散列表(哈希表)
掌握哈希表的关键是，明白如何找到哈希函数，以及如何解决哈希冲突，以及装填因子的概念
A. 找到哈希函数：
直接定址法：f(key)=a*key+b(a,b为常数)，不会出现哈希冲突，适合查找表小且连续，不常用
平方取中法：f(key)=key^2的中间数字，适合不知道关键字分布，而位数又不是很大的情况
折叠法：将key分段累加，取加法结果的后几位
除留余数法：f(key)=key%p(p<=查找表长)，为减少哈希冲突，经验是：p取小于等于表长(最好接近表长)的最小质数或不包含小于20质因子的合数。
随机数法：f(key)=random(key)
B. 解决哈希冲突：
开放定法：f(key)=(f(key)+d)%m，其中d的不同取法对应不同的探测方法：
如果d=1，则是线性探测法，容易发生堆积（原来不是冲突的位置，因为线性探测，导致的冲突）
如果d=1^2,-1^2,2^2,-2^2,...，则是二次探测法
如果d=random(),则是随机探测法
再散列函数法：f(key)=RH(key),不断的更换散列函数，让关键字不聚集
链地址法：将映射到同一位置的key对应的val，结成链表，位置存放链表的头指针
公共溢出区法：把冲突的key统一放到一个公共溢出区。
C. 装填因子：
alpha=填入表中的记录个数、散列表的长度//代码实现哈希表 const int maxSize = 100; //定义hash表 template <class T> class hashTable { private: int size=0; T *nums=new T[maxSize](); int hashfun(T key) { int pos = int(key) % maxSize; int d = 1; while (nums[pos]) { int di = d & 0x1 ? d*d : -d*d; pos = (pos + di) % maxSize; ++d; } return pos; } public: bool count(T key) { int pos= int(key) % maxSize; int d = 1; while (nums[pos] != key) { int di = d & 0x1 ? d*d : -d*d; pos = (pos + di) % maxSize; ++d; if (!pos) return 0; } return 1; } void insert(T key) { int pos = hashfun(key); nums[pos] =key; ++size; } bool empty() { if (!size) return 0; return 1; } int getsize() { return size; } void clear() { size = 0; delete[]nums; } }; int main() { hashTable<char>tt; string str = "iloveyoubdhahbwjd dawdklam22312"; for (int i = 0; i < str.size(); ++i) { tt.insert(str[i]); } cout << tt.count('0') << endl; }
查看6道真题和解析
