《数据结构》实验报告查找.pdfVIP

《数据结构》实验班级：学号：姓名：

实验四——查找

一、实验目的

1.掌握顺序表的查找方法，尤其是折半查找方法；

2.掌握二叉排序树的查找算法。

二、实验内容

1.建立一个顺序表，用顺序查找的方法对其实施查找；

2.建立一个有序表，用折半查找的方法对其实施查找；

3.建立一个二叉排序树，根据给定值对其实施查找；

4.对同一组数据，试用三种方法查找某一相同数据，并尝试进行性能分析。

三、实验预习内容

实验一包括的函数有：typedefstruct，创建函数voidcreate(seqlistL)，输出函数void

print(seqlistL)，顺序查找intfind(seqlistL,intnumber)，折半查找inthalffind(seqlistL,intnumber)

主函数main().

实验二包括的函数有：结构体typedefstruct，插入函数voidinsert(bnode*T,bnode*S)，void

insert1(bnode*T)，创建函数voidcreate(bnode*T)，查找函数bnode*search(bnode*T,int

number)，主函数main().

四、上机实验

实验一：

1.实验源程序。

#includeiostream.h

#defineN80

typedefstruct

{

intnumber;//关键字

charname[5];

charsex[2];

intage;

}record;

typedefstruct

{

recordstu[N];

intnum;//记录人数

}seqlist;

//建顺序表

voidcreate(seqlistL)

{

inti;

1

《数据结构》实验班级：学号：姓名：

L.num=0;

请依次输入(输入学号为0认定为终止输入认定为终止输入

学号学号姓名姓名性别性别年龄年龄

cinL.stu[1].number;

for(i=1;L.stu[i].number!=0;)

{

cinL.stu[i].nameL.stu[i].sexL.stu[i].age;

L.num++;

coutendl;

cinL.stu[++i].number;

}

}

//输出学生信息

voidprint(seqlistL)

{

inti;

学生基本信息为学生基本信息为

for(i=1;i=L.num;i++)

endl;

}

//顺序查找

intfind(seqlistL,intnumber)

{

inti;

for(i=L.num;i=0;i--)

if(L.stu[i].number==number)

returni;

}

//折半查找

inthalffind(seqlistL,intnumber)

{

inthigh=L.num,low=1,mid;

for(;low=high;)

{

mid=(high+low)/2;

if(number==L.stu[mid].number)

returnmid;

else

if(numberL.stu[mid].number)

2

《数据结构》实验班级