数据结构查找算法.doc

精品文档，仅供学习与交流，如有侵权请联系网站删除
【精品文档】第 1 页
沈 阳 工 程 学 院
学 生 实 验 报 告
实验室名称：信息工程系信息安全实验室
实验课程名称：数据结构
实验项目名称：查找算法
实验目的
⑴掌握几种典型的查找方法。
⑵掌握二叉排序树的建立和查找算法。
⑶掌握哈希表的用法。
实验环境
VC++.
实验内容及要求
，使用折半查找算法在输入的n个有序数中进行查找；
：
①假如删除关键字28，画出新二叉树。
②若查找56，需和哪些关键字比较。
～11，散列函数为H(k)=k % 11，采用线性探测法处理冲突，将关键字序列20,30,70,15,8,12,18,63,19依次存储到散列表中，试构造出该散列表，并求出在等概率情况下的平均查找长度。
(k)=k % 11，采用链地址法处理冲突，将上例中关键字序列依次存储到散列表中，并求出在等概率情况下的平均查找长度。
，则可用如下策略提高顺序查找的效率∶若找到指定的结点，则将该结点和其前驱结点交换，使得经常被查找的结点尽量位于表的前端。试对线性表的链式存储结构写出实现上述策略的顺序查找算法（查找时必须从表头开始向后扫描）（选做题）
实验步骤及程序清单
1. #include <>
#include <>
#include <>
int num;//元素的个数
int * list;//指向线性表的指针
int i;
void createList()
{
printf("\n请输入元素的个数：");
fflush(stdin);
scanf("%d",&num);
精品文档，仅供学习与交流，如有侵权请联系网站删除
【精品文档】第 2 页
list=(int *)malloc(sizeof(int)*num);
printf("\n长度为%d的线性表初始化成功！\n",num);
printf("\n");
system("pause");
system("cls");
printf("\n请输入线性表的信息!\n");
for(i=0;i<num;i++)
{
printf("\n请输入第%d个元素的值：",i+1);
fflush(stdin);
scanf("%d",&list[i]);
}
printf("\n线性表创建成功!\n");
}
void inputAll()
{
printf("\n当前线性表的元素个数为%d\n",num);
for(i=0;i<num;i++)
{
printf("\n第%d个元素的值为%d：",i,list[i]);
}
}
void search()
{
int low,mid,high;
int c