sstable.cpp

这是一个实现一种排序法的实验

#include<iostream>
using namespace std;

//关键字类型 
typedef char KeyType;

//数据元素类型 
typedef struct
{
  KeyType key;
}ElemType;

//两个关键字比较的宏定义 
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))

//静态查找表的顺序存储结构 
typedef struct
{
  ElemType *elem;
  int     length;
}SSTable;

//顺序查找
int Search_Seq(SSTable ST,KeyType key)
{
  int i;
  ST.elem[0].key=key;
  for(i=ST.length;!EQ(ST.elem[i].key,key);--i);
  return i;
}

//折半查找 
int Search_Bin(SSTable ST,KeyType key)
{
  int low=1,high=ST.length;
  int mid;
  while(low<=high)
  {
    mid=(low+high)/2;
    if(EQ(key,ST.elem[mid].key))
      return mid;
    else
      if(LT(key,ST.elem[mid].key))
        high=mid-1;
      else
        low=mid+1;
  }
  return 0;
}

int main()
{
  KeyType k[11]="abcdefghij";
  SSTable sst;
  
  //初始化静态查找表 
  sst.elem=(ElemType*)malloc(sizeof(ElemType)*11);
  for(int i=1;i<11;i++)
    sst.elem[i].key=k[i-1];
  sst.length=10;
  
  //调用顺序查找 
  int pos=Search_Seq(sst,'k');
  cout<<"元素在表中的位置是："<<pos;
  cout<<endl<<endl;
  
  //调用折半查找
  pos=Search_Seq(sst,'k');
  cout<<"元素在表中的位置是："<<pos;
  cout<<endl<<endl;

  system("pause");
  return 0;
}