数据结构折半排序查找.doc
折半查询一、 实验目的1，掌握排序算法及基本思想及实现的技术；能够根据实际问题特点的要求选择合理的排序方法，理解排序在数据处理中的重要性；2. 学会比较各种排序方法的稳定性分析以及在最好 、最坏和平均情况的时间性能分析。3. 掌握顺序查找和折半查找两种查找的算法及实现技术；了解它们各自的优缺点。4. 熟悉各种查找方法的适用范围和条件；掌握顺序查找、折半查找的基本思想及效率分析。二、 实验环境1. 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows2. 软件：DOS或Windows操作系统+Turbo C;三、 实验要求1. 本次实验较为简单，每个同学独立按时完成，通过实验掌握记录的概念，为以后数据库技术打好基础。2. 如果输入数据较为繁琐，可减低每个班的人数。3. 输入输出数据要有提示，方便用户操作。四、 实验内容1. 现在某个学院有20名同学分属于2个班级（Class1和Class2，每个班有10名同学，每个同学记录包括：班级、学号、姓名、性别、电话号码等信息）。2. 以学号为主关键字，以班级为次关键字，建立一个顺序表，表中的每个数据元素是一个记录，其中的某个域用来存储关键字的值，按关键字的值进行顺序查找。为分析排序方法的稳定性，关键字可用次关键字。#include "stdio.h"#include "malloc.h"#include "string.h"typedef struct 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_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(low<=high)mid=(low+high)/2;if(l->elemmid.num>num)high=mid-1;else j=mid;low=mid+1;i=j;for(j=mid;j>=i;j-)if(j=-1|num>l->elemj.num)break;else if(num=l->elemj.num&&c>l->elemj.cla)break;return(+j);void move_hc(sqlist_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");for(i=0;i<l->sum;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",&num,&c);while(num!=-1|c!=-1)low=0;high=l->length-1;while(low<=high)mid=(low+high)/2;if(l->elemmid.num<num)low=mid+1;else if(l->elemmid.num>num)high=mid-1;else if(l->elemmid.cla<c)mid+;else if(l->elemmid.cla>c)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;i<l->sum;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("作者:黄晨");
