本文共 2607 字，大约阅读时间需要 8 分钟。

1、查找的定义

根据某个给定关键字K，从集合R中找出关键字与K相同的记录。查找分为动态查找和静态查找：动态查找，集合中内容是动态变化的；静态查找，集合中内容是固定不变的。本文主要来介绍最基本的静态查找的方法：顺序查找和二分查找。

2、具体的实现

2.1 基本数据结构

/* 定义查找相关数据结构 */#define TABLE_LENGTH	10typedef int ElementType;typedef struct _StaticTable{	ElementType Element[TABLE_LENGTH + 1];	int Length;}StaticTable;

2.2 顺序查找

/**	顺序查找   *		输入参数: Tbl 要查找的顺序表，K 要查找的元素  *		返回值: 要查找元素的下标，0失败  */int SequentialSearch (StaticTable *Tbl, ElementType K){	int i = 0;	Tbl->Element[0] = K;	for (i = Tbl->Length; Tbl->Element[i] != K; i--);	return i;}

2.3 二分查找

/**	二分查找(数据元素按照由小到大排列)  *		输入参数: Tbl 要查找的表，K 要查找的元素  *		返回值: 查找到的元素的下标；0失败，没有找到  */int BinarySearch ( StaticTable * Tbl, ElementType K){	int left, right, mid;	left = 1;	right = Tbl->Length;	while (left <= right)	{		mid = (left + right)/2;		if (Tbl->Element[mid] > K) right = mid - 1;		else if (Tbl->Element[mid] < K) left = mid + 1;		else return mid;	}	return 0;}

2.4 完整示例代码

#include 
   
    /* 定义查找相关数据结构 */#define TABLE_LENGTH	10typedef int ElementType;typedef struct _StaticTable{	ElementType Element[TABLE_LENGTH + 1];	int Length;}StaticTable;/**	顺序查找   *		输入参数: Tbl 要查找的顺序表，K 要查找的元素  *		返回值: 要查找元素的下标，0失败  */int SequentialSearch (StaticTable *Tbl, ElementType K){	int i = 0;	Tbl->Element[0] = K;	for (i = Tbl->Length; Tbl->Element[i] != K; i--);	return i;}/**	二分查找(数据元素按照由小到大排列)  *		输入参数: Tbl 要查找的表，K 要查找的元素  *		返回值: 查找到的元素的下标；0失败，没有找到  */int BinarySearch ( StaticTable * Tbl, ElementType K){	int left, right, mid;	left = 1;	right = Tbl->Length;	while (left <= right)	{		mid = (left + right)/2;		if (Tbl->Element[mid] > K) right = mid - 1;		else if (Tbl->Element[mid] < K) left = mid + 1;		else return mid;	}	return 0;}/* 程序入口 */int main(){	int i = 0;	int ret;	ElementType element;	StaticTable tbl;	/* 给表格赋值 */	tbl.Length = TABLE_LENGTH;	printf("Input 10 numbers : ");	for (i = 1; i <= tbl.Length; i++)	{		scanf("%d", &tbl.Element[i]);	}	printf("***************************SequentialSearch******************************\n");	/* 输入要查找的元素 */	printf("Input the value that need searching : ");	scanf("%d", &element);		/* 查找相应元素 */	ret = SequentialSearch(&tbl, element);	if (ret == 0)	{		printf("Searching is failed!\n");	}	else 	{		printf("The searching index is %d, value is %d\n", ret, tbl.Element[ret]);	}	printf("***************************BinarySearch******************************\n");	/* 输入要查找的元素 */	printf("Input the value that need searching : ");	scanf("%d", &element);	/* 通过二分法查找指定元素 */	ret = BinarySearch(&tbl, element);	if (ret == 0)	{		printf("Searching is failed!\n");	}	else 	{		printf("The searching index is %d, value is %d\n", ret, tbl.Element[ret]);	}		return 0;	}
   

转载地址：http://elgoi.baihongyu.com/