查找实验（C语言）

1.实验目的

（1）掌握静态查找表算法（重点掌握折半查找）；

（2）掌握动态查找表——二叉排序树查找算法；

2.实验要求

算法1：采用顺序存储结构创建静态查找表，对查找表进行顺序查找和改进的顺序查找，并对其查找效率进行比较；

算法2：采用顺序存储结构创建静态查找表——有序表，对有序表进行二分查找；

3.代码实现 

 
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
 
#define MAXSIZE 100
#define MAX_NODE 100
//定义
typedef int keytype;
typedef struct
{
	keytype key;
	int info;
}ElemType;
 
//定义
typedef struct
{
	ElemType elem[MAXSIZE];
	int length;
}Sstable;
 
//定义
typedef struct node
{
	int data;
	struct node *LChild;
	struct node *RChild;
}BST;
 
//创建BST（二叉树）
void CreateBST( BST *T, int arr[], int n ) 
{
	BST *s, *p, *q; 
	int i; 
	T->data = arr[0]; 
	T->LChild = NULL; 
	T->RChild = NULL; 
	for( i = 1; i < n; i++ ) 
	{
		s = (BST *)malloc( sizeof(BST) ); 
		s->data   = arr[i];
		s->LChild = NULL;
		s->RChild = NULL;
		p = T;
		while( p != NULL )
		{
			if( s->data == p->data )
			{
				printf( "%d existed.\n", s->data );
				q = NULL;
				break; 
			}
			q = p;
			if( s->data < p->data )
			{
				p = p->LChild;
			}
			else if( s->data > p->data )
			{
				p = p->RChild;			
			}
		} 
		if( q != NULL && s->data < q->data )
		{
			q->LChild = s;
		}
		else if( q != NULL && s->data > q->data )
		{
			q->RChild = s;
		}	
	}
}//CreateBST
 
//查找二叉树
int SearchBST( BST *T, int key )
{
	int flag = 0; //查找成功标志，初始化为失败 
	BST *p = T; 
	while( p != NULL )
	{
		if ( p->data == key )
		{
			flag = 1;
			break;
		}
		else if( key < p->data )
		{
			p = p->LChild;
		}
		else
		{
			p = p->RChild;
		}
	}
	return( flag );
}//SearchBST
 
//创建一个顺序表
void Create(Sstable &ST, int n)
{
	int i;
	printf("请输入顺序表元素（用空格隔开）：\n");
	for(i = 1;i <= n;i++)
	{
		scanf("%d", &ST.elem[i].key);
	}
}
 
//静态查找表算法
int Search_Seq(Sstable ST, keytype key)
{
	int i = ST.length;
	ST.elem[0].key = key;
	while(i >= 0)
	{
		if(key == ST.elem[i].key)
		{
			return i;
		}
		i--;
	}
}
 
//折半查找
int Search_Bin(Sstable ST,keytype key)
{
	int low, high, mid;
	low = 1;
	high = ST.length;
	while(low <= high)
	{
		mid = (low + high)/2;
		if(key == ST.elem[mid].key) 
		{
			return mid;
		}
		else if(key < ST.elem[mid].key) 
		{
			high=mid-1;
		}
		else 
		{
			low=mid+1;
		}
	}
	return 0;
}
 
//主函数
int main()
{
	Sstable ST;
	keytype key;
	int i;
	printf("***欢迎使用查找系统***\n");
	printf("请选择你要进行的操作：\n");
	printf("1.静态查找表算法\n");
	printf("2.折半查找\n");
	printf("3.二叉树查找\n");
	printf("请选择：");
	scanf("%d", &i);
	switch (i) {
		case 1: {//静态查找表算法
			printf("新建顺序表\n请输入长度：");
			scanf("%d",&ST.length);
			Create(ST,ST.length);
			printf("请输入想要查找的元素：\n");
			scanf("%d", &key);
			i = Search_Seq(ST, key);
			if(i)
			{
				printf("元素位置在：%d\n", i);
			}
			else
			{
				printf("元素不存在！\n");
			}
			break;
		}
		case 2: {//折半查找
			printf("新建有序顺序表\n请输入长度：");
			scanf("%d",&ST.length);
			Create(ST,ST.length);
			printf("请输入想要查找的元素：\n");
			scanf("%d", &key);
			i=Search_Bin(ST,key);
			if(i) 
			{
				printf("元素位置在：%d\n",i);
			}
			else  
			{
				printf("元素不存在！\n");
			}	
			break;
		}
		case 3:{
			int arr[] = { 18, 3, 7, 20, 14, 19, 27, 2 };
			BST *T = ( BST * )malloc( sizeof( BST ) );
			CreateBST( T, arr, 8 );
	
			int flag, key;
			key = 10;
			flag = SearchBST( T, key );
			if( flag == 0 )
			{
				printf( "failure : %d is not on the BST\n", key );
			}
			else
			{
				printf( "success : %d is on the BST\n", key );
			}
	
			key = 19;
			flag = SearchBST( T, key );
			if( flag == 0 )
			{
				printf( "failure : %d is not on the BST\n", key );
			}
			else
			{
				printf( "success : %d is on the BST\n", key );
			}
			return 0;
			break;
		}
		case 0: {
			printf("期待下次使用!\n");
			break;
		}
	}
	return 0;
}

4.运行结果