一、实验目的

1.掌握查找表的结构。

2.掌握顺序查找、折半查找、二叉排序树查找和哈希查找。

二、实验环境

Windows 10、Visual C++ 6.0

三、实验任务

1.编写程序实现顺序查找和折半查找。

(1)顺序查找

#include <stdio.h>
#include <stdlib.h>

#define LIST_SIZE 20 

typedef char KeyType;
typedef int OtherType;

typedef struct
{
	KeyType key;
	OtherType other_data;
}RecordType;

typedef struct
{
	RecordType  r[LIST_SIZE+1];  /* r[0]为工作单元 */
	int length;
}RecordList;

void createlist(RecordList *l)
{
	int i;
	int len;
	KeyType ch;
	printf("请输入线性表的长度:");
	scanf("%d",&len);
	l->length = len;
	for(i=1; i<=len; i++)
	{
		printf("请输入线性表的第%d个元素:",i);
		fflush(stdin);
		scanf("%c",&ch);
		l->r[i].key = ch;
	}
}

int SeqSearch(RecordList  l,  KeyType  k)
/*在顺序表l中顺序查找其关键字等于k的元素，若找到，则函数值为该元素在表中的位置，否则为0*/
{
	int i;
	l.r[0].key=k; 
	i=l.length;
	while (l.r[i].key!=k)  i--;
	return(i);
}

int SeqSearch2(RecordList l,  KeyType k)
/*不用"监视哨"法，在顺序表中查找关键字等于k的元素*/
{
	int i;
	i=l.length;
	while (i>=1&&l.r[i].key!=k)  i--;
	if (i>=1) 
		return(i);
	else
		return (0);
}


int main()
{
	RecordList l;
	int locate1,locate2;
	KeyType k;
	createlist(&l);
	printf("请输入要查找的元素:");
	fflush(stdin);
	scanf("%c",&k);
	locate1 = SeqSearch(l,k);
	if(locate1 == 0)
		printf("未找到!\n");
	else
		printf("该元素在表中的位置为%d\n",locate1);
	locate2 = SeqSearch2(l,k);
	if(locate2 == 0)
		printf("未找到!\n");
	else
		printf("该元素在表中的位置为%d\n",locate2);
	return 0;
}

(2)折半查找

#include <stdio.h>
#include <stdlib.h>

#define LIST_SIZE 20 

typedef char KeyType;
typedef int OtherType;

typedef struct
{
	KeyType key;
	OtherType other_data;
}RecordType;

typedef struct
{
	RecordType  r[LIST_SIZE+1];  /* r[0]为工作单元 */
	int length;
}RecordList;

void createlist(RecordList *l)
{
	int i;
	int len;
	KeyType ch;
	printf("请输入线性表的长度:");
	scanf("%d",&len);
	l->length = len;
	for(i=1; i<=len; i++)
	{
		printf("请输入线性表的第%d个元素:",i);
		fflush(stdin);
		scanf("%c",&ch);
		l->r[i].key = ch;
	}
}

int BinSrch(RecordList  l,  KeyType  k)
/*在有序表l中折半查找其关键字等于k的元素，若找到，则函数值为该元素在表中的
位置*/
{
	int low,high,mid;
	low=1;  
	high=l.length;/*置区间初值*/
	while( low <= high)
	{
		mid=(low+high) / 2;
		if  (k==l.r[mid]. key)  
			return (mid);/*找到待查元素*/
		else  
			if (k<l.r[mid]. key) 
				high=mid-1;/*未找到，则继续在前半区间进行查找*/
			else  
				low=mid+1;/*继续在后半区间进行查找*/
	}
	return (0);
}



void main()
{
	RecordList l;
	int locate;
	KeyType k;
	createlist(&l);
	printf("请输入要查找的元素:");
	fflush(stdin);
	scanf("%c",&k);
	locate = BinSrch(l,k);
	if(locate == 0)
		printf("未找到!\n");
	else
		printf("该元素在表中的位置为%d\n",locate);
	
}

2.编写程序实现二叉排序树查找。四

#include <stdio.h>
#include <stdlib.h>

#define ENDKEY 0

typedef int KeyType;

typedef struct  node
{
	KeyType  key ; /*关键字的值*/
	struct node  *lchild,*rchild;/*左右指针*/
}BSTNode, *BSTree;

void InsertBST(BSTree *bst, KeyType key)
/*若在二叉排序树中不存在关键字等于key的元素，插入该元素*/
{ 
	BSTree s;
	if (*bst == NULL)/*递归结束条件*/
	{
		s=(BSTree)malloc(sizeof(BSTNode));/*申请新的结点s*/
		s-> key=key;
		s->lchild=NULL; 
		s->rchild=NULL;
		*bst=s;
	}
	else 
		if (key < (*bst)->key)
			InsertBST(&((*bst)->lchild), key);/*将s插入左子树*/
		else 
			if (key > (*bst)->key)
				InsertBST(&((*bst)->rchild), key); /*将s插入右子树*/
}




void  CreateBST(BSTree  *bst)
/*从键盘输入元素的值，创建相应的二叉排序树*/
{ 
	KeyType key;
	*bst=NULL;
	scanf("%d", &key);
	while (key!=ENDKEY)   /*ENDKEY为自定义常量*/
	{
		InsertBST(bst, key);
		scanf("%d", &key);
	}
}

void  PreOrder(BSTree root) 
/*先序遍历二叉树, root为指向二叉树根结点的指针*/
{
	if (root!=NULL)
	{
		printf("%d  ",root->key);  /*输出结点*/
		PreOrder(root->lchild);  /*先序遍历左子树*/
		PreOrder(root->rchild);  /*先序遍历右子树*/
	}
}


BSTree  SearchBST(BSTree bst, KeyType key)
/*在根指针bst所指二叉排序树bst上，查找关键字等于key的结点，若查找成功，返回指向该元素结点指针，否则返回空指针*/
{ 
	BSTree q;
	q=bst;
	while(q)
	{
		if (q->key == key) 
			return q;  /*查找成功*/
		if (q->key > key)  
			q=q->lchild;  /*在左子树中查找*/
		else  
			q=q->rchild;  /*在右子树中查找*/
	}
	return NULL; /*查找失败*/
}/*SearchBST*/

BSTNode  * DelBST(BSTree t, KeyType  k) /*在二叉排序树t中删去关键字为k的结点*/
{
	BSTNode  *p, *f,*s ,*q;
	p=t; 
	f=NULL;
	while(p)  /*查找关键字为k的待删结点p*/
	{ 
		if(p->key==k )  break;  /*找到则跳出循环*/
		f=p;   /*f指向p结点的双亲结点*/
		if(p->key>k)  
			p=p->lchild;
		else 
			p=p->rchild;
	} 
	if(p==NULL)  return t;  /*若找不到，返回原来的二叉排序树*/
	if(p->lchild==NULL)  /*p无左子树*/
	{ 
		if(f==NULL) 
			t=p->rchild;  /*p是原二叉排序树的根*/
		else 
			if(f->lchild==p)  /*p是f的左孩子*/
				f->lchild=p->rchild ;  /*将p的右子树链到f的左链上*/
			else  /*p是f的右孩子*/
				f->rchild=p->rchild ;  /*将p的右子树链到f的右链上*/
			free(p);  /*释放被删除的结点p*/
	}
	else  /*p有左子树*/
	{ 
		q=p; 
		s=p->lchild;
		while(s->rchild)  /*在p的左子树中查找最右下结点*/
		{
			q=s; 
			s=s->rchild;
		}
		if(q==p) 
			q->lchild=s->lchild ;  /*将s的左子树链到q上*/
		else 
			q->rchild=s->lchild;
		p->key=s->key;  /*将s的值赋给p*/
		free(s);
	}
	return t;
}  /*DelBST*/


int main()
{
	BSTree T;
	int k;
	BSTree result;
	printf("建立二叉排序树，请输入序列:\n");
    CreateBST(&T);
	printf("先序遍历输出序列为:");
	PreOrder(T);
	printf("\n请输入要查找的元素:");
	fflush(stdin);
	scanf("%d",&k);
	result = SearchBST(T,k);
	if (result != NULL)
		printf("要查找的元素为%d\n",result->key);
	else
		printf("未找到!\n");
	result = DelBST(T,k);
	PreOrder(result);
	return 0;
}

 四、实验结果与分析

1.

分析：静态查找表用顺序存储结构表示时，顺序查找的查找过程为：从表中的最后一个数据元素开始，逐个同记录的关键字做比较，如果匹配成功，则查找成功；反之，如果直到表中第一个关键字查找完也没有成功匹配，则查找失败。

折半查找在每次查找时都排除了一半数据，所以它的效率是非常高的。但是，折半查找只适合数组，不适合链表。链表中也可以用折半查找，但是不仅不会提高效率，反而还会降低效率。

2.

分析：使用二叉排序树实现动态查找操作的过程，实际上就是从二叉排序树的根结点到查找元素结点的过程，所以时间复杂度同被查找元素所在的树的深度（层次数）有关。