实验五各种查找操作.doc
文本预览下载声明
实验五、各种查找操作
一、实验目的
1．掌握各种查找（顺序、二分法、查找树、哈希）方法及适用场合，并能在解决实际问题时灵活应用。
2．巩固在散列查找时解决冲突的方法及特点。
二、实验内容(任选两个)
1．线性表查找
2．查找树的实现
3.．哈希表查找的实现
三、实验要求
1．用C++/C完成算法设计和程序设计并上机调试通过。
2．撰写实验报告，提供实验结果和数据。
3．分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。
四、程序实现
写出每个操作的算法（操作过程）
源程序清单
程序1：线性表查找实现和运算
#define MAX 128
main()
{ int i,k,m,n,result;
int a[MAX];
printf(How many nodes in the array \n);
scanf(%d,n);
printf(Please input the value of array element\n);
for(i=0;in;i++)
scanf(%d,a[i]);
printf(The key word?);
scanf(%d,k);
printf(Please Input Your Choice(1-2):);
scanf(%d,m);
switch(m)
{ case 1:
printf(This is ShunXu Search!\n);
result=shx(a,n,k);
if(result=0)
printf(Found No.%d elements of the array\n,result+1);
else
printf(Not found\n);
break;
case 2:
printf(This is ErFen Search!\n);
result=erfen(a,n,k);
if(result=0)
printf(In the No. %d of the array\n,result+1);
else
printf(Not found\n);
break;
default:
printf(1-------------------------ShunXu Search\n);
printf(2-------------------------ErFen Search\n);
return;
}
}
int shx (array, n, k)
/*find the subscript of an elements which value is k in array[n]*/
int array[], n, k;
{ int i;
array[n]=k;/*watch*/
i= 0;
while (array[i]!=k) i++;
if (in) return (i);
else return (-1);
}
int erfen(int array[],int n ,int key)
/*find key in array[] whose length is n,if it is found,then return its address,else return -1*/
{ int l, r,mid;
l=0;
r=n-1;
while (l=r)
{mid=(l+r)/2;
if(key==array[mid])
return mid; /*it is found,return its address*/
else if(keyarray[mid])
r=mid-1;
else l=mid+1;
}
return -1;
}
程序3：哈希表查找的实现和运算
#include stdio.h
#define MAX 10
int H(int key)
{ return(key%MAX);
}
int thread (int key , int m, int addr[] )
/*search the key in the hash table,if it is fo
显示全部