各种基本算法实现小结(六)—— 查找算法

长平狐 发布于 2013/01/06 11:23
阅读 126
收藏 2

各种基本算法实现小结(六)—— 查找算法

(均已测试通过)

===================================================================

 

1、简单查找

在一组无序数列中,查找特定某个数值,并返回其位置pos

测试环境:VC 6.0 (C)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 101
void input(int num[])
{
	int i;
	
	srand((unsigned)time(NULL));
	for(i=1; i<MAX; i++)
		num[i]=rand()%100;
}
void output(int num[])
{
	int i;
	
	for(i=1; i<MAX; i++)
	{
		printf("%5d", num[i]);
		if(0==i%10)
			printf("/n");
	}
}
int find(int num[], int x)
{
	int i;
	for(i=1; i<MAX; i++)
		if(x == num[i])
			return i;
	return 0;
}
void main()
{
	int x, pos, num[MAX];
	input(num);
	
	printf("num...: /n");
	output(num);
	
	printf("Enter find num: ");
	scanf("%d", &x);
	pos=find(num, x);
	if(pos)
		printf("OK! %d is found in pos: %d/n", x, pos);
	else
		printf("Sorry! %d is not found... in num/n", x);
}

运行结果:

 

==========================================================

2、 折半查找

在有序数列中,逐步缩小查找范围,直至找到或找不到记录为止

本算法首先随机生成100个无序数列,然后利用快速排序算法排序成有序数列,然后再用折半查找算法

说明:本算法中的排序算法,可用上一篇排序算法中的任一种算法实现,如选择排序、冒泡排序、快速排序等

 

测试环境:VC 6.0 (C)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 101
void input(int num[])
{
	int i;
	
	srand((unsigned)time(NULL));
	for(i=1; i<MAX; i++)
		num[i]=rand()%100;
}
void output(int num[])
{
	int i;
	
	for(i=1; i<MAX; i++)
	{
		printf("%5d", num[i]);
		if(0==i%10)
			printf("/n");
	}
}
void sort(int num[], int low, int high) /* quick sort */
{
	int l, h;
	
	if(low<high)
	{
		l=low;
		h=high;
		num[0]=num[l]; /* save pivot */
		
		while(l<h)
		{
			while(l<h && num[h]>=num[0]) h--;
				num[l]=num[h];
			while(l<h && num[l]<=num[0]) l++;
				num[h]=num[l];
		}
		num[l]=num[0]; /* insert pivot */
		
		sort(num, low, l-1);
		sort(num, l+1, high);
	}
}
int find(int num[], int x, int low, int high)
{
	int mid;
	
	while(low<=high)
	{
		mid=(low+high)/2; /* find is OK */
		
		if(x==num[mid])
			return mid;
		else if(x<num[mid])
			high=mid-1;
		else
			low=mid+1;
	}
	return 0;
}
void main()
{
	int x, pos, num[MAX];
	input(num);
	
	printf("sort before... /n");
	output(num);
	sort(num, 1, MAX-1);
	printf("sort after... /n");
	output(num);
	
	printf("Enter find num: ");
	scanf("%d", &x);
	pos=find(num, x, 1, MAX-1);
	if(pos)
		printf("OK! %d is found in pos: %d/n", x, pos);
	else
		printf("Sorry! %d is not found... in num/n", x);
}

运行结果:

  

==========================================================

 

 

参考推荐:

学习算法之路

各种基本算法实现小结(一)—— 链 表

各种基本算法实现小结(二)—— 堆 栈

各种基本算法实现小结(三)—— 树与二叉树

各种基本算法实现小结(四)—— 图及其遍历

各种基本算法实现小结(五)—— 排序算法

各种基本算法实现小结(六)—— 查找算法

各种基本算法实现小结(七)—— 常用算法



原文链接:http://blog.csdn.net/sunboy_2050/article/details/5645835
加载中
返回顶部
顶部