《数据结构查找实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构查找实验报告.docx（4页珍藏版）》请在三一文库上搜索。
1、数据结构课程实验报告学生姓名学号班级指导老师实验名称查找实验成绩实验报告实 验实验目的：折半查找概 述实验要求：（1）建立现有学生信息表，平均成绩已有序。（2）输入插入学生的记录信息。（3）用折半查找找到插入位置，并插入记录。实验基本原理：首先，将表中间位置记录的关键字与查找关键字比较，如果两者相 等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置 记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。 重复以上步骤，直到找到满足条件的结果为止，若找不到，则返回失败。实 验实验设计思路、步骤和方法等：（1 ）用结构数组存储成绩信息表。（2）对记录中的平
2、均成绩进行折半查找并插入。内 容实验过程（实验中涉及的记录、数据、分析）： 程序代码如下：/*折半查找*/#i nclude <stdio.h>#defi ne N 10/*定义学生信息类型*/typedef structchar name10; /*姓名 */float avg; /*平均成绩 */Stude nt;int BinSort(Student *a,int n,Student x); void Display(Student *a,int n); /*/*按平均成绩进行折半排序*/显示学生信息表*/void mai n()1Student aN="Zhao&
3、quot;,95,"Qian",90,"Sun",86,"Li",75,x;int n=4;/*学生人数，即表长*/printf("初始%d位学生的信息表如下：n",n);Display(a, n);prin tf("nn");prin tf("请输入学生姓名：");sea nf("%s",x .n ame);prin tf("请输入平均成绩：");scan f("%f", &x.avg );n=Bin So
4、rt(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=amid.avg)i=mid+1; /* break;else if(x.avg>
5、amid.avg) high=mid-1; /*elselow=mid+1; /* if(low>high) i=low; /*/* 在下标i前插入*/for(j=n-1; j>=i; j-)aj+1=aj;ai=x;n+; return n;/*显示学生信息表*/void Display(Student *a,int n) 查找成功，记录插入位置i*/取前半查找区间*/取后半查找区间*/查找失败，记录插入位置i*/int i;实验结果:4re s htiao iar uniiao ieri unfor(i=0; i<n; i+)prin tf("n%-10s %-6.1f',ai. name,ai.avg);位学生的信息袤妇下;95.090.08G.075-0f半排序后5位半生的信息表如下:95.090.0叽08&.075.ahey to rantinue实 验 小 结实验的心得体会：折半查找适用于顺序存储的有序表，可提高查找速度。实验思考：如果插入的学生平均成绩在原表中有相同值时，本实验中采用其后面插入。如测试中输 入Wang 86，该记录则插入到 Sun 86的后面。指 导 教 师 评 语指导教师日期