算法竞赛之查找算法(持续补充...)

#include <iostream>
using namespace std;
#define Maxsize 100
int SqSearch(int r[],int n,int x) { //顺序查找
  for(int i=0; i<n; i++) //要判断i是否超过范围n
    if(r[i]==x) //r[i]和x比较
      return i;//返回下标
  return -1;
}
int SqSearch2(int r2[],int n,int x) { //顺序查找优化算法
  int i;
  r2[0]=x;//待查找元素放入r[0]，作为监视哨
  for(i=n; r2[i]!=x; i--); //不需要判断i是否超过范围
  return i;
}
int main() {
  int i,n,x,r[Maxsize],r2[Maxsize+1];
  cout<<"请输入元素个数n为："<<endl;
  cin>>n;
  cout<<"请依次n个元素："<<endl;
  for(int i=0; i<n; i++) {
    cin>>r[i];
    r2[i+1]=r[i];//r2[]数组0空间未用，做监视哨
  }
  cout<<endl;
  cout<<"请输入要查找的元素：";
  cin>>x;
  //i=SqSearch(r,n,x);
//    if(i==-1)
//      cout<<"该数列中没有要查找的元素"<<endl;
//    else
//      cout<<"要查找的元素在第"<<i+1<<"位"<<endl;
  i=SqSearch2(r2,n,x);
  if(i==0)
    cout<<"该数列中没有要查找的元素"<<endl;
  else
    cout<<"要查找的元素在第"<<i<<"位"<<endl;
  return 0;
}

#include<iostream>
#include<cstdlib> //排序sort函数需要该头文件
#include<algorithm>
using namespace std;
const int M=100;
int x,n,i;
int s[M];
int BinarySearch(int s[],int n,int x) { //二分查找非递归算法
  int low=0,high=n-1;  //low指向有序数组的第一个元素，high指向有序数组的最后一个元素
  while(low<=high) {
    int middle=(low+high)/2;  //middle为查找范围的中间值
    if(x==s[middle])  //x等于查找范围的中间值，算法结束
      return middle;
    else if(x>s[middle]) //x大于查找范围的中间元素，则从左半部分查找
      low=middle+1;
    else            //x小于查找范围的中间元素，则从右半部分查找
      high=middle-1;
  }
  return -1;
}
int recursionBS (int s[],int x,int low,int high) { //二分查找递归算法
  //low指向数组的第一个元素，high指向数组的最后一个元素
  if(low>high)              //递归结束条件
    return -1;
  int middle=(low+high)/2;  //计算middle值(查找范围的中间值)
  if(x==s[middle])          //x等于s[middle]，查找成功，算法结束
    return middle;
  else if(x<s[middle])      //x小于s[middle]，则从前半部分查找
    return recursionBS (s,x,low,middle-1);
  else               //x大于s[middle]，则从后半部分查找
    return recursionBS (s,x,middle+1,high);
}
int main() {
  cout<<"该数列中的元素个数n为：";
  cin>>n;
  cout<<"请依次输入数列中的元素：";
  for(i=0; i<n; i++)
    cin>>s[i];
  sort(s,s+n); //二分查找的序列必须是有序的，如果无序需要先排序
  cout<<"排序后的数组为：";
  for(i=0; i<n; i++) {
    cout<<s[i]<<" ";
  }
  cout<<endl;
  cout<<"请输入要查找的元素：";
  cin>>x;
  //i=BinarySearch(s,n,x);
  i=recursionBS(s,x,0,n-1);
  if(i==-1)
    cout<<"该数列中没有要查找的元素"<<endl;
  else
    cout<<"要查找的元素在第"<<i+1<<"位"<<endl;//位序和下标差1
  return 0;
}

/*
Hash函数 ---二次探测,线性探测法. 
*/ 
#include<iostream>
#include<string.h>
using namespace std;
const int m = 15;//哈希表的表长 
const int NULLKEY = 0;//单元为空的标记
int HT[m],HC[m];//HT:存放hash表  HC:统计查找次数
int H(int key){//哈希函数 
  return key%13;
} 
int Linedetect(int HT[],int H0,int key,int &cnt){
  int Hi;
  for(int i = 1; i<m;i++){
    cnt++;//计数
    Hi = (H0+i)%m; //按照线性探测法计算下一个Hash地址 Hi
    if(HT[Hi]==NULLKEY){
      return Hi;//若单元Hi为空,则所查元素不存在 
    } else if(HT[Hi]==key){//若单元Hi中的元素关键字为key,说明该元素已经被存过,则也返回改地址.. 
      return Hi;
    } 
  }
  return -1;//如果没找到则返回-1 
} 
int Seconddetect(int HT[],int H0,int key,int &cnt){
  int Hi;
  for(int i = 1; i <= m / 2; i++){
    int i1 = i*i;
    int i2 = -i1;
    cnt++;
    Hi = (H0+i1)%m;//按照二次探测法计算下一个哈希地址 Hi
    if(HT[Hi]==NULLKEY){//若单元Hi为空,或者里面已经存放了要插入 的元素则返回改地址. 
      return Hi;
    } else if(HT[Hi]==key){
      return Hi;
    } 
    cnt++;
    Hi = (H0+i2)%m;//按照二次探测 计算下一个哈希地址Hi
     if(Hi<0){
      Hi+=m;
     }
     if(HT[Hi]==NULLKEY){//
      return Hi;
     }else if(HT[Hi]==key){
      return Hi;
     } 
  }
  return -1;
} 
int SearchHash(int HT[],int key){//查找
  //在哈希表HT中查找关键字为key的元素，若查找成功，返回哈希表的单元标号，否则返回-1
  int H0 = H(key);根据哈希函数H（key）计算哈希地址  没有冲突的话就是用Hash函数,否则就得启用线性探测或者..来处理冲突,然后再存储. 
  int Hi,cnt = 1;
  if(HT[H0]==NULLKEY){//若单元H0为空，则所查元素不存在
    return -1;
  } else if(HT[H0]==key){//若单元H0中元素的关键字为key，则查找成功
    cout<<"查找成功,比较次数:"<<cnt<<endl; 
  }else{
    Hi = Linedetect(HT,H0,key,cnt);
    if(HT[Hi]==key){
      cout<<"查找成功,比较次数:"<<cnt<<endl;
      return Hi; 
    }else{
      return -1;//如果单元Hi为空,则所查元素不存在. 
    }
  }
}
bool InsertHash(int HT[],int key){
  int H0 = H(key);// 计算哈希地址
  int Hi = -1,cnt = 1;
  if(HT[H0]==NULLKEY){
    HC[H0]=1;
    HT[H0] = key;//若单元H0为空,放入
    return 1;
  } else{
    // Hi = Seconddetect(HT,H0,key,cnt);//二次探测 
    Hi = Linedetect(HT,H0,key,cnt);// cnt以引用的形式传入
    if(Hi!=-1 && HT[Hi]==NULLKEY){
      HC[Hi] = cnt;
      HT[Hi] = key;//若单元Hi为空,放入
      return 1; 
    } 
  }
  return 0;
} 
void print(int HT[]){
  for(int i = 0;i<m;i++){
    cout<<HT[i]<<"\t";  
  }
  cout<<endl;
} 
int main()
{
  int x;
  memset(HT,0,sizeof(HT));
  memset(HC,0,sizeof(HC));
  cout<<"HT的初始状态:"<<endl;
  print(HT);
  cout<<"输入12个关键字,存入到哈希表中:"<<endl;
  for(int i = 0; i<12;i++){
    cin>>x;
    if(!InsertHash(HT,x)){
      cout<<"创建哈希表失败!"<<endl;
      return 0; 
    }
  } 
  cout<<"输出哈希表:"<<endl;
  print(HT);
  print(HC);
  cout<<"输入要查找的关键字:"<<endl;
  cin>>x;
  int result = SearchHash(HT,x);
  if(result!=-1){
    cout<<"在第"<<result+1<<"位置找到"<<endl; 
  } else{
    cout<<"未找到"<<endl; 
  } 
  return 0;
}
//14 36 42 38 40 15 19 12 51 65 34 25