数据结构查找实验报告.docx

数据结构课程实验报告 学生姓名 学 号 班 级 指导老师 实验名称 查找 实验成绩 实验报告 实 验 实验目的：折半查找 概 述 实验要求：（1）建立现有学生信息表，平均成绩已有序。 （2） 输入插入学生的记录信息。 （3） 用折半查找找到插入位置，并插入记录。 实验基本原理：首先，将表中间位置记录的关键字与查找关键字比较，如果两者相 等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置 记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。 重复以上步骤，直到找到满足条件的结果为止，若找不到，则返回失败。 实 验 实验设计思路、步骤和方法等： （1 ）用结构数组存储成绩信息表。 （2）对记录中的平均成绩进行折半查找并插入。 内 容 实验过程（实验中涉及的记录、数据、分析）： 程序代码如下： /*折半查找*/ #i nclude stdio.h #defi ne N 10 /*定义学生信息类型*/ typedef struct{ char name[10]; /* 姓名 */ float avg; /* 平均成绩 */ }Stude nt; int BinSort(Student *a,int n,Student x); void Display(Student *a,int n); /* /* 按平均成绩进行折半排序 */ 显示学生信息表*/ void mai n() 1 Student a[N]={{Zhao,95},{Qian,90},{Sun,86},{Li,75}},x; int n=4; /* 学生人数，即表长*/ printf( 初始%d位学生的信息表如下：\n,n); Display(a, n); prin tf(\n\n); prin tf( 请输入学生姓名：); sea nf(%s,x .n ame); prin tf( 请输入平均成绩：); scan f(%f, x.avg ); n=Bin Sort(a ,n, x); printf(\n 折半排序后%d位学生的信息表如下：\n,n); Display(a, n); prin tf(\n ”); } /*按平均成绩进行折半查找并插入新记录，使表仍按平均成绩降序排列 */ int BinSort(Student *a,int n,Student x) { int low,high,mid; int i,j; /* 折半查找*/ low=0; high=n-1; while(low=high) { mid=(low+high)/2; if(x.avg==a[mid].avg) { i=mid+1; /* break; } else if(x.avga[mid].avg) high=mid-1; /* else low=mid+1; /* } if(lowhigh) i=low; /* /* 在下标i前插入*/ for(j=n-1; j=i; j--) a[j+1]=a[j]; a[i]=x; n++; return n; } /*显示学生信息表*/ void Display(Student *a,int n) { 查找成功，记录插入位置 i*/ 取前半查找区间*/ 取后半查找区间*/ 查找失败，记录插入位置 i*/ int i; 实验结果: 4 re s h tiao iar un iiao ieri un for(i=0; in; i++) prin tf(\n%-10s %-6.1f,a[i]. name,a[i].avg); } 位学生的信息袤妇下; 95.0 90.0 8G.0 75-0 f半排序后5位半生的信息表如下: 95.0 90.0 叽0 8.0 75.a hey to rantinue 实 验 小 结 实验的心得体会： 折半查找适用于顺序存储的有序表，可提高查找速度。 实验思考： 如果插入的学生平均成绩在原表中有相同值时，本实验中采用其后面插入。如测试中输 入Wang 86，该记录则插入到 Sun 86的后面。 指 导 教 师 评 语 指导教师 日期