数据结构查找算法.doc

《数据结构查找算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、沈阳工程学院学生实验报告实验室名称：信息工程系信息安全实验室实验课程名称：数据结构实验项目名称：查找算法一．实验目的⑴掌握几种典型的查找方法。⑵掌握二叉排序树的建立和查找算法。⑶掌握哈希表的用法。二．实验环境VC++6.0.三．实验内容及要求1.编写程序，使用折半查找算法在输入的n个有序数中进行查找；2.已知一棵二叉排序树如下：①假如删除关键字28，画出新二叉树。②若查找56，需和哪些关键字比较。3.已知散列表的地址区间为0～11，散列函数为H(k)=k%11，采用线性探测法处理冲突，将关键字序列20,30,70,15,8,12,18,63,

2、19依次存储到散列表中，试构造出该散列表，并求出在等概率情况下的平均查找长度。4.设散列函数为H(k)=k%11，采用链地址法处理冲突，将上例中关键字序列依次存储到散列表中，并求出在等概率情况下的平均查找长度。5.若线性表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率∶若找到指定的结点，则将该结点和其前驱结点交换，使得经常被查找的结点尽量位于表的前端。试对线性表的链式存储结构写出实现上述策略的顺序查找算法（查找时必须从表头开始向后扫描）（选做题）四．实验步骤及程序清单1.#include#include

3、b.h>#includeintnum;//元素的个数int*list;//指向线性表的指针inti;voidcreateList(){printf("请输入元素的个数：");fflush(stdin);scanf("%d",&num);list=(int*)malloc(sizeof(int)*num);printf("长度为%d的线性表初始化成功！",num);printf("");system("pause");system("cls");printf("请输入线性表的信息!");for(i=0;i

4、

5、请输入要查找的元素：");fflush(stdin);scanf("%d",&c);low=0;high=num-1;mid=(low+high)/2;while(!taget){if(!taget&&c==list[low]){printf("要查找的元素%d在线性表中的位置是%d",c,low);taget=1;}if(!taget&&c==list[mid]){printf("要查找的元素%d在线性表中的位置是%d",c,mid);taget=1;}if(!taget&&c==list[high]){printf("

6、要查找的元素%d在线性表中的位置是%d",c,high);taget=1;}if(clist[mid]){low=mid+1;mid=(high+low)/2;}if(!taget&&abs(low-high)==1){printf("要查找的元素%d不在此线性表中",c);taget=1;}}}voidmain(){createList();inputAll();search();}2.3.数值19127015183020863地址012

7、34567891011在等概率情况下的平均查找长度=（5+1+1+2+1+1+1+3+4）/9=2.114.地址01234567891011　∧　∧∧　∧∧　　　∧∧↓↓↓↓↓1270173020↓↓158↓63在等概率情况下的平均查找长度=(1+1+2+1+1+2+3+4+1)/9=1.77一．结果分析1.编写程序，使用折半查找算法在输入的n个有序数中进行查找；测试5个数：1,3,5,7,9.运行结果：结果正确。教师评语：