[数据结构与算法] 静态查找C语言实现

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 静态查找C语言实现 -> 正文阅读

[数据结构与算法]静态查找C语言实现

#include "stdio.h"    
#include "stdlib.h"   

#include "math.h"  
#include "time.h"

#define maxlen 100
int F[100];


int sequential_Search(int* a, int n, int key)//从头部开始查找
{
	int i;
	for (i = 1;i <= n;i++)
	{
		if (a[i] == key)
		{
			return i;
		}
	}
	return 0;
}

int sequential_Search2(int* a, int n, int key)//从尾部开始查找
{
	int i;
	i = n;
	a[0] = key;
	while (a[i] != key)
	{
		i--;
	}
	return i;
}

int binary_search(int* a, int n, int key) //折中查找
{
	int mid, low, high;
	low = 1;
	high = n;
	while (low<=high)
	{
		mid = (low + high) / 2;
		if (a[mid] > key)
		{
			high = mid-1;
		}
		else if (a[mid] < key)
		{
			low = mid+1;
		}
		else
		{
			return mid;
		}
	}
	return 0;
}

int interpolation_Search(int* a, int n, int key) //插值查找，适合均匀变化的数组
{
	int low, high, mid;
	low = 1;	/* 定义最低下标为记录首位 */
	high = n;	/* 定义最高下标为记录末位 */
	while (low <= high)
	{
		mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]); /* 插值 */
		if (key < a[mid])		/* 若查找值比插值小 */
			high = mid - 1;		/* 最高下标调整到插值下标小一位 */
		else if (key > a[mid])/* 若查找值比插值大 */
			low = mid + 1;		/* 最低下标调整到插值下标大一位 */
		else
			return mid;		/* 若相等则说明mid即为查找到的位置 */
	}
	return 0;
}

int fibonacci_Search(int* a, int n, int key)
{
	int low, high, mid;
	low = 0;
	high = n;
	int k=0;
	int i;
	while (n>=F[k]-1)
	{
		k++;
	}
	for (i = n+1;i < F[k] - 1;i++)
	{
		a[i] = a[n];
	}
	while (low<=high)
	{
		mid = low + F[k - 1] - 1;
		if (a[mid] < key)
		{
			low = mid + 1;
			k = k - 2;
		}
		else if (a[mid] > key)
		{
			high = mid - 1;
			k--;
		}
		else
		{
			if (mid <= n)
			{
				return mid;
			}
			else
			{
				return n;
			}
		}
	}
	return 0;
}

int main()
{
	int a[maxlen + 1], i, result;
	int arr[maxlen] = { 0,1,16,24,35,47,59,62,73,88,99 };

	for (i = 1;i <= maxlen;i++)
	{
		a[i] = i;
	}
	a[0] = maxlen;

	F[0] = 0;
	F[1] = 1;
	for (int i = 2;i < 100;i++)
	{
		F[i] = F[i - 1] + F[i - 2];
	}

	result = sequential_Search(a, maxlen,35);
	printf("顺序查找:%d \n", result);
	result = sequential_Search(a, maxlen, 35);
	printf("顺序查找2:%d \n", result);
	 
	result = Binary_Search(arr, 10, 62);
	printf("折中查找:%d \n", result);


	result = interpolation_Search(arr, 10, 62);
	printf("插值查找:%d \n", result);

	result = fibonacci_Search(arr, 10, 62);
	printf("斐波那契查找:%d \n", result);
}