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

《数据结构》实验 班级： 学号： 姓名： 实验四 ——查找

一、实验目的

1. 掌握顺序表的查找方法，尤其是折半查找方法； 2. 掌握二叉排序树的查找算法。

二、 实验内容

1.

2. 3. 4. 建立一个顺序表，用顺序查找的方法对其实施查找； 建立一个有序表，用折半查找的方法对其实施查找； 建立一个二叉排序树，根据给定值对其实施查找；

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

三、实验预习内容

实验一包括的函数有：typedef struct ，创建函数void create(seqlist & L)，输出函数void print(seqlist L)，顺序查找int find(seqlist L,int number)，折半查找int halffind(seqlist L,int number) 主函数main().

实验二包括的函数有：结构体typedef struct， 插入函数void insert(bnode * & T,bnode * S)，void insert1(bnode * & T)，创建函数void create(bnode * & T)，查找函数bnode * search(bnode * T,int number)，主函数main().

四、上机实验 实验一：

1. 实验源程序。 #include #define N 80 typedef struct { int number; //关键字 char name[5]; char sex[2]; int age; }record;

typedef struct { record stu[N]; int num;//记录人数 }seqlist;

//建顺序表

void create(seqlist & L) { int i;

1

《数据结构》实验 班级： 学号： 姓名： L.num=0; cout<<\请依次输入(输入学号为0认定为终止输入):\ cout<<\学号\姓名\性别\年龄\ cin>>L.stu[1].number; for(i=1;L.stu[i].number!=0;) { cin>>L.stu[i].name>>L.stu[i].sex>>L.stu[i].age; L.num++; cout<>L.stu[++i].number; } }

//输出学生信息 void print(seqlist L) { int i; cout<<\学生基本信息为:\ for(i=1;i<=L.num;i++) cout<<\endl; }

//顺序查找

int find(seqlist L,int number) { int i; for(i=L.num;i>=0;i--) if(L.stu[i].number==number) return i; }

//折半查找

int halffind(seqlist L,int number) { int high=L.num,low=1,mid; for(;low<=high;) { mid=(high+low)/2; if(number==L.stu[mid].number) return mid; else if(number

2

《数据结构》实验 班级： 学号： 姓名： high=mid-1; else low=mid+1; } return 0; }

void main() { int i,number; seqlist L; create(L); print(L); cout<<\折半查找:\ cout<<\输入学生学号:\ cin>>number;

if((i=halffind(L,number))!=0) cout<<\endl; else cout<<\失败!\ cout<<\顺序查找:\ cout<<\输入学生学号:\ cin>>number;

if((i=find(L,number))!=0) cout<<\endl; else cout<<\失败!\}

实验二：

#include typedef struct { int number; //关键字 char name[5]; char sex[2]; int age; }record;

3

《数据结构》实验 班级： 学号： 姓名： typedef struct node { record inf; struct node *lchild,*rchild; }bnode;

void insert(bnode * & T,bnode * S) { if(!T) T=S; else if(S->inf.numberinf.number) insert(T->lchild,S); else insert(T->rchild,S); }

void insert1(bnode * & T) { int flag=1; int number; bnode * u; char ctinue; for(;flag==1;) { cout<<\依次输入(学号为0默认为结束输入):\ cout<<\学号\姓名\性别\年龄\ cin>>number; while(number) { u=new bnode; u->inf.number=number; cin>>u->inf.name>>u->inf.sex>>u->inf.age; u->lchild=u->rchild=NULL; insert(T,u); cin>>number; } cout<<\继续插入(Y/N):\ cin>>ctinue; if(ctinue=='y'||ctinue=='y') flag=1; else flag=0; } }

void create(bnode * & T)

4