sequential search.cpp

数据结构中顺序查找的例子

#include<iostream.h>
#include<malloc.h>

#define OK 1
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))

typedef int KeyType;//关键字类型说明为整形

typedef struct
{
	KeyType key;//关键字域
}ElemType;

//静态查找表的顺序存储结构
typedef struct
{
	ElemType *elem;//数据元素存储空间基址，建表时按实际长度分配，0号单元留空
	int length;//表长度
}SSTable;

void Create(SSTable *ST, int n);//构造一个n个数据元素的静态查找表

int Destroy(SSTable *ST)//销毁表ST
{
	free(ST);
	ST=NULL;
	return OK;
}

 void Create(SSTable *ST, int n)
{
	 ST=(SSTable *)malloc(sizeof(ElemType));

}


int Search_Seq(SSTable ST, KeyType key)
//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0
{
	ST.elem[0].key=key;//“哨兵”
	for(int i=ST.length; !EQ(ST.elem[i].key,key); --i)//从后往前找
		return i;//找不到时，返回0
}

int Search_Bin(SSTable ST, KeyType key)
//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0
{
	int low=1;//置区间初值
	int high=ST.length;
	while(low<=high)
	{
		int 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;//在顺序表中找不到关键字为key的元素，则返回0
}