数据结构第4次实验报告.doc

中国矿业大学计算机学院实验报告课程名称 数据结构 实验名称 搜索 班级 计科11-3 姓名 冯剑飞 学号 08113405 仪器组号_21-22机房_ 实验日期 2012年12月28号 实验报告要求：1.实验目的 2.实验内容 3.实验步骤 4.运行结果 5.流程图 6.实验体会 一、实验目的 1 熟练掌握顺序搜索、折半搜索和索引搜索等基本搜索算法，熟悉这些算法适合在何种存储结构下实现2 熟练掌握二叉排序树的特性、建立方法以及动态搜索算法3 熟练掌握散列表的特点及构造方法二、实验要求1 实验之前认真准备，编写好源程序。2 实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。3 不断积累程序的调试方法。3、 实验步骤1、 阅读教材相关章节，了解程序架构。2、 根据伪代码编写实现可执行程序。3、 调试程序，提高程序健壮性。4、 输入多组数据，测试程序，寻找漏洞。5、 在关键部位写下注释，提高程序可读性。4、 实验内容 基本题1、实现基于有序顺序表的折半搜索。#include using namespace std;struct nodeListint number;char name15;int CETgrade;int main ()int search(nodeList nodeList, int n, int v);nodeList nodeList10= 0,zhangwei,545,1,zengxiaoxian,456,2,guangu,525,3,lvziqiao,421,4,zhangfei,343,5,liubei,555,6,caocao,546,7,lvbu,400,8,sunquan,567,9,zhugeliang,654;cout-编号-姓名-成绩-endl;for(int i=0;i10;i+)cout nodeListi.number nodeL nodeListi.CETgradeendl;cout请输入要查找的编号（0到9）v; int find=search(nodeList,10,v);cout该编号学生的情况为nodeListfind.number nodeL nodeListfind.CETgradeendl;return 0;int search(nodeList nodeList, int n, int v) int left, right, middle; left = 0, right = n - 1; while (left v) right = middle - 1; else if (nodeListmiddle.number v) left = middle + 1; else return middle; return -1;2、设单链表的结点是按关键字的值从小到大排列的，试写出对此表的搜索程序并调试。#include using namespace std;struct keySearchlong keynumber;char name15; char sex15; char country15;int main ()keySearch keysearch10= 1001,张飞,男,蜀国,1002,张小贤,男,中国,1003,关谷神奇,男,日本,1004,吕子乔,男,中国,1005,杨贵妃,女,唐朝,1006,刘备,男,蜀国,1007,曹操,男,魏国,1008,吕布,男,汉朝,1009,孙权,男,东吴,1010,诸葛亮,男,蜀国;cout你想了解谁的信息？:v;if(v1010)cout列表中没有你要找的人endl;elsefor(int i=1001;i1011;i+)if(i=v)cout此人的信息是：endl;coutkeysearchi-1001.keynumber keysearchi-1001.sex keysearchi-1001.countryendl;else continue;return 0;加强题 1、 若输入 12000个不同的整数，其值介于0和19999之间，用散列法将这些数进行存储，散列函数为H(n)=n/2，请设计实现程序并调试。2、 五、实验体会这此实验使用的是查找方面的内容，程序中使用了折半查找，折半查找比较难使用正确，就第一个程序