数据结构实验指导书(2016)(9)

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验11”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．现在某个学院有20名同学分属于2个班级（Class1 和Class2，每个班有10名同学，每个同学记录包括：班级、学号、姓名、性别、电话号码等信息）。

3．以学号为主关键字，以班级为次关键字，建立一个顺序表，表中的每个数据元素是一个记录，其中的某个域用来存储关键字的值，按关键字的值进行顺序查找。为分析排序方法的稳定性，关键字可用次关键字。

4．完成如下函数（其中查找函数用顺序查询和折半查询两种方式实现），注意折半查询只适合有序的顺序表：

3．思考两种查找的效率分析和适用场合。 #include \#include \#include \

typedef struct {int cla; int num;

char name[20]; char sex;

long phonenum; }student;

typedef struct {student *elem; int length; int sum; }ST;

ST *initlist() {ST *l;

l=(ST*)malloc(sizeof(ST));

第38页 /共58页

if(!l)printf(\没有创建ST!\\n\

l->length=0;l->sum=3;

l->elem=(student*)malloc(3*sizeof(student)); if(!l->elem)printf(\没有创建elem!\\n\return(l); }

int place(ST *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->elem[mid].num>num)high=mid-1; else {j=mid;low=mid+1;}} i=j;

for(j=mid;j>=i;j--)

{if(j==-1||num>l->elem[j].num)break;

else if(num==l->elem[j].num&&c>l->elem[j].cla)break;} return(++j);}

void move(ST *l,int j) {int i;

for(i=l->length-1;i>=j;i--)

{l->elem[i+1].cla=l->elem[i].cla;

strcpy(l->elem[i+1].name,l->elem[i].name); l->elem[i+1].num=l->elem[i].num; l->elem[i+1].sex=l->elem[i].sex;

l->elem[i+1].phonenum=l->elem[i].phonenum;}}

void createlist(ST *l) {int i,j,c,num;

char nam[20],s;long p;

printf(\输入学生信息(class name num sex phonenum):\\n\for(i=0;isum;i++) {flushall();

scanf(\j=!(l->length)?0:place(l,c,num); move(l,j);

l->elem[j].cla=c;

strcpy(l->elem[j].name,nam); l->elem[j].num=num; l->elem[j].sex=s;

l->elem[j].phonenum=p;

第39页 /共58页

l->length++;}}

void searchban(ST *l) {int low,high,mid,num,c;

printf(\输入查找人的学号和班级号:\scanf(\if(num!=-1||c!=-1)

{low=0;high=l->length-1; while(low<=high) {mid=(low+high)/2;

if(l->elem[mid].numelem[mid].num>num)high=mid-1; else {if(l->elem[mid].claelem[mid].cla>c)mid--; break;}}

printf(\e,l->elem[mid].num,l->elem[mid].sex,l->elem[mid].phonenum); } }

void searchshun(ST *l) {int num,c,i;

printf(\输入查找人的学号和班级号:\scanf(\for(i=0;i<=l->length;i++)

if(l->elem[i].num==num)break; if(i!=l->length)

printf(\em[i].num,l->elem[i].sex,l->elem[i].phonenum); else

printf(\无此人！\ }

void printlist(ST *l) {int i,j=0;

printf(\当前表中信息如下:class/name/num/sex/phonenum\\n\for(i=0;isum;i++)

{printf(\elem[i].num,l->elem[i].sex,l->elem[i].phonenum); if(++j==3){j=0;printf(\printf(\

第40页 /共58页

void main() {ST *l; ST *l2;

printf(\

l=initlist();createlist(l);printlist(l); printf(\用折半查询实现class1\\n\searchban(l); printf(\l2=initlist(); createlist(l2); printlist(l2);

printf(\用顺序查询实现class2\\n\searchshun(l2); }

实验十二有序表查找算法的实现

实验预备知识：

1．理解记录、关键字和查找的相关概念。 2．熟练掌握有序表的存储结构。

一、实验目的

1．掌握排序算法及基本思想及实现的技术；能够根据实际问题特点的要求选择合理的排序方法；理解排序在数据处理中的重要性；

2．学会比较各种排序方法的稳定性分析以及在最好、最坏和平均情况的时间性能分析。 3．掌握顺序查找和折半查找两种查找的算法及实现技术；了解它们各自的优缺点。 4．熟悉各种查找方法的适用范围和条件；掌握顺序查找、折半查找的基本思想及效率分析。

二、实验环境

⒈ 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉ 软件：DOS或Windows操作系统+Turbo C；

三、实验要求

1．本次实验较为简单，每个同学独立按时完成，通过实验掌握记录的概念，为以后数据库技术打好基础。

2．如果输入数据较为繁琐，可减低每个班的人数。 3．输入输出数据要有提示，方便用户操作。

第41页 /共58页

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验11”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．现在某个学院有20名同学分属于2个班级（Class1 和Class2，每个班有10名同学，每个同学记录包括：班级、学号、姓名、性别、电话号码等信息）。

3．以学号为主关键字，以班级为次关键字，建立一个顺序表，表中的每个数据元素是一个记录，其中的某个域用来存储关键字的值，按关键字的值进行顺序查找。为分析排序方法的稳定性，关键字可用次关键字。

4．完成如下函数（其中查找函数用顺序查询和折半查询两种方式实现），注意折半查询只适合有序的顺序表：

3．思考两种查找的效率分析和适用场合。 #include \#include \#include \

typedef struct {int cla; int num;

char name[20]; char sex;

long phonenum; }student;

typedef struct {student *elem; int length; int sum; }ST;

ST *initlist() {ST *l;

l=(ST*)malloc(sizeof(ST));

第42页 /共58页