好库网 好库网首页 | 我的好库
VC开发指南

C语言实现二分法查找

发布者:vchelp
发布日期:2013/5/15 12:27:33   更新日期:2013/5/15 12:27:33
阅读次数:4929
评分:4.80
介绍:二分法查找又称为折半查找,是一种效率较高的查找方式,要求被查找的数据是按照某种顺序排列的有序序列。
正文:

二分法查找又称为折半查找,是一种效率较高的查找方式,要求被查找的数据是按照某种顺序排列的有序序列,在本例中,首先利用qs_struce()对数组进行快速排序,使其成为有序序列,然后通过函数BinarySearch()利用二分查找法查找字符串。

源代码如下:

 

#include <stdio.h>
#include <stdlib.h> 
#include <string.h>
#define NUM 4

struct Data
{
	char name[20];
	char city[20];
	char sex[10];
	char age[10];
	char job[10];
};

struct Data SDatas[NUM]=
{
	"OKBase","Weifang","Male","24","student",
	"Tom","Beijing","Male","31","doctor",
	"Marry","Shanghai","Female","19","techer",
	"Willing","Tianjing","Female","21","worker"
};

void qs_struct(items,left,right);
void quick_struct(items,count);
int BinarySeach(items,name,n);
void print_data(point);

int main(void)
{
	char name[30];
	int i; 
	printf("将原始数据排序\n");
	quick_struct(SDatas,NUM);
	printf("请输入要查找人的名字:\n");
	scanf("%s",name);
	i = BinarySeach(SDatas,name,NUM);
	if(i == -1)
	{
		printf("没有查找到该人信息\n");
		return 0;
	}
	printf("查找结果:\n");
	print_data(&SDatas[i]);
	return 1;
}


void quick_struct(items,count)
struct Data items[];
int count;
{
	qs_struct(items,0,count-1);
}

void qs_struct(items,left,right)
struct Data items[];
int left;
int right;
{
	register int i,j;
	char *x;
	struct Data temp;
	i = left;
	j = right;
	x = items[(left+right/2)].name;
	do
	{
		while((strcmp(items[i].name,x)<0)&&(i<right))
			i++;
		while((strcmp(items[j].name,x)>0)&&(j>left))
			j--;
		if(i<=j)
		{
			temp = items[i];
			items[i] = items[j];
			items[j] = temp;
			i++;
			j--;
		}
	}while(i<=j);
	if(left<j)
		qs_struct(items,left,j);
	if(i<right)
		qs_struct(items,i,right);
}

int BinarySeach(items,name,n)
struct Data items[];
char name[];
int n;
{
	int low,high,mid;
	low = 0;
	high = n-1;
	while(low<=high)
	{
		mid = (low+high)/2;
		if((strcmp(items[mid].name,name)==0))
			return mid;
		else if((strcmp(items[mid].name,name)<0))
			low = mid+1;
		else high = mid-1;
	}
	return -1;
}

void print_data(point)
struct Data *point;
{
	if(point ==NULL)
		return;
	printf("	姓名:%s\n",point->name);
	printf("	城市:%s\n",point->city);
	printf("	性别:%s\n",point->sex);
	printf("	年龄:%s\n",point->age);
	printf("	工作:%s\n",point->job);
}

 

 


评论 [发表评论]
账号 密码 还没帐号呢,现在注册一个?

免责声明:好库网所展示的信息由买卖双方自行提供,其真实性、准确性和合法性由信息发布人负责。好库网不提供任何保证,并不承担任何法律责任。