《数据结构折半排序查找.doc》由会员分享，可在线阅读，更多相关《数据结构折半排序查找.doc（4页珍藏版）》请在三一办公上搜索。
1、折半查询一、 实验目的1，掌握排序算法及基本思想及实现的技术；能够根据实际问题特点的要求选择合理的排序方法，理解排序在数据处理中的重要性；2. 学会比较各种排序方法的稳定性分析以及在最好 、最坏和平均情况的时间性能分析。3. 掌握顺序查找和折半查找两种查找的算法及实现技术；了解它们各自的优缺点。4. 熟悉各种查找方法的适用范围和条件；掌握顺序查找、折半查找的基本思想及效率分析。二、 实验环境1. 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows2. 软件：DOS或Windows操作系统+Turbo C;三、 实验要求1. 本次实验较为简单，每个同学独立按时完成，通过实验掌握记录
2、的概念，为以后数据库技术打好基础。2. 如果输入数据较为繁琐，可减低每个班的人数。3. 输入输出数据要有提示，方便用户操作。四、 实验内容1. 现在某个学院有20名同学分属于2个班级（Class1和Class2，每个班有10名同学，每个同学记录包括：班级、学号、姓名、性别、电话号码等信息）。2. 以学号为主关键字，以班级为次关键字，建立一个顺序表，表中的每个数据元素是一个记录，其中的某个域用来存储关键字的值，按关键字的值进行顺序查找。为分析排序方法的稳定性，关键字可用次关键字。#include stdio.h#include malloc.h#include string.htypedef s
3、truct int cla;int num;char name7;char sex;long phnum;stu_hc;typedef structstu_hc *elem;int length;int sum;sqlist_hc;sqlist_hc *initlist_hc()sqlist_hc *l;int n;l=(sqlist_hc*)malloc(sizeof(sqlist_hc);if(!l)printf(出错!n);printf(输入学生人数:);scanf(%d,&n);l-length=0;l-sum=n;l-elem=(stu_hc*)malloc(n*sizeof(stu
4、_hc);if(!l-elem)printf(出错!n);return(l);int place_hc(sqlist_hc *l,int c,int num)int low,high,mid,j=-1,i;low=0;high=l-length-1;while(lowelemmid.numnum)high=mid-1;else j=mid;low=mid+1;i=j;for(j=mid;j=i;j-)if(j=-1|numl-elemj.num)break;else if(num=l-elemj.num&cl-elemj.cla)break;return(+j);void move_hc(sq
5、list_hc *l,int j)int i;for(i=l-length-1;i=j;i-)l-elemi+1.cla=l-elemi.cla;strcpy(l-elemi+1.name,l-elemi.name);l-elemi+1.num=l-elemi.num;l-elemi+1.sex=l-elemi.sex;l-elemi+1.phnum=l-elemi.phnum;void createlist_hc(sqlist_hc *l)int i,j,c,num;char nam7,s;long p;printf(输入学生信息(class name num sex phonenum):n
6、);for(i=0;isum;i+)flushall();scanf(%d %s %d %c %ld,&c,nam,&num,&s,&p);j=!(l-length)?0:place_hc(l,c,num);move_hc(l,j);l-elemj.cla=c;strcpy(l-elemj.name,nam);l-elemj.num=num;l-elemj.sex=s;l-elemj.phnum=p;l-length+;void seekstu_hc(sqlist_hc *l)int low,high,mid,num,c;printf(输入查找人的学号和班级号:);scanf(%d %d,&n
7、um,&c);while(num!=-1|c!=-1)low=0;high=l-length-1;while(lowelemmid.numelemmid.numnum)high=mid-1;else if(l-elemmid.claelemmid.clac)mid-;break;printf(%d,%s,%d,%c,%ldn,l-elemmid.cla,l-elemmid.name,l-elemmid.num,l-elemmid.sex,l-elemmid.phnum);printf(输入查找人的学号和班级号:);scanf(%d %d,&num,&c);void printlist_hc(sqlist_hc*l)int i,j=0;printf(当前表中信息如下:class/name/num/sex/phonenumn);for(i=0;isum;i+)printf(%d/%s/%d/%c/%ld ,l-elemi.cla,l-elemi.name,l-elemi.num,l-elemi.sex,l-elemi.phnum);if(+j=3)j=0;printf(n);printf(n);main()sqlist_hc *l;l=initlist_hc();createlist_hc(l);printlist_hc(l);seekstu_hc(l);printf(作者:黄晨);
