静态查找表：无序，有序，顺序查找，二分查找，STL

63 阅读 0 评论 42 点赞

我是靠谱客的博主自信鱼，最近开发中收集的这篇文章主要介绍静态查找表：无序，有序，顺序查找，二分查找，STL，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

《数据结构思想与实现第二版》第八章代码摘录

集合元素的类型

template <class KEY,class OTHER>
struct SET{
KEY key;
OTHER other;
};

以下的数组都是从1开始存储，0号当成哨兵或者不用

无序表的顺序查找

template<class KEY,class OTHER>
int seqSearch_disorder(SET<KEY,OTHER>data[],int size,const KEY &x){
data[0].key=x;int i=0;
for(i=size;data[i].key!=x;i--);
return i;
}

有序表

1.顺序查找

无序表确定不存在，要遍历整个数组，有序表只要发现不满足条件就行。
假设data[0]-[size]从小到大，只要x<data[i].key就终止循环

template <class KEY,class OTHER>
int seqSearch_order(SET<KEY,OTHER>data[],int size,const KEY &x){
data[0].key=x;int i=0;
for(i=size;data[i].key>x;i--);
if (data[i].key==x) return i;
else return 0;
}

2.二分查找

0号不用

int binarySearch(SET<KEY,OTHER>data[],int size,const KEY &x){
int low=0,mid=0,high=size;
while (low<=high) {
mid=(low+high)/2;
if (x==data[mid].key) return mid;
else if(x<data[mid].key) high=mid-1;
else low=mid+1;
}
return 0;
}

STL中的静态查找表

#include<vector>
#include<iostream>
#include <algorithm>
int main() {
int a[]={2,33,67,88,99,100};//必须是有序表！！
vector<int>v;
vector<int>::iterator itr;
for (int i=0; i<6; i++) {
v.push_back(a[i]);在v的最后一个向量后插入一个元素，其值为a[i];
}
if (binary_search(v.begin(), v.end(), 33)) cout<<"33存在"<<endl;//binary_search返回bool类型
else cout<<"33不存在"<<endl;
itr=find(v.begin(), v.end(), 3);
cout<<itr-v.begin()<<endl;//返回下标
cout<<*itr<<endl;//会返回要查找的元素值（如果找到）
return 0;
}