数据结构试验

实验四查找和排序应用

1、实验题目：

索引顺序表应用

(1)课题目的：

东北大学信息学院学生信息查询系统。各专业按名称有序，专业内按班级编号有序，班

级内记录无序。

(2)课题任务：

设计索引顺序表的学生信息查询系统。

1)采用顺序表、索引表等存储结构。

2)采用二级顺序表索引。

3)完成表的创建、插入、查询等操作。

4)分析平均查找长度特性。

2、概要设计：

使用顺序表存储学生信息，并按照专业班级挨次排序，并通过输入学号实现检索。先建

立专业索引表，结构体成员为专业中学号的最大值和专业中子顺序表的头指针，对输入的学

号与各块中的最大值进行比较，进而确定专业。再根据所在专业动态生成二级索引表，即班

级索引表，结构体成员为班级中学号的最大值和顺序表的头指针，可查出所在班级。最后在

子顺序表，即各班级的顺序表中进行查找。

平均查找长度为：4+8+x(各班人数的平均值)

3、详细设计：

我设计的部份：我主要设计了构造顺序表和将学生信息按专业班级排序两个部份，将输

入的学生信息存储到顺序表中，而后进行排序。

intmaketablel(structstudentstu[])

(

intml;

intk;

printf("请输入学生信息：专业班级学号姓名输入学号为0结束\n");

scanf("%d%ld%ld%s",&stu[O].m/&stu[O].clas/&stu[O].numberz&stu[O].name);

for(i=0;i<maxsize;)

{i++；

scanf("%d%ld%ld%s",&stu[i].m,&stu[i].clas/&stu[i].numberz&stu[i].name);

if(stu[i].number==O)

break;

)

i-；

k=i;

returnk;

}〃构造顺序表

voidque(structstudentstu[]Jntk)

intj;

structstudenttemp;

for(i=0;i<k;i++)

for(j=i+l;j<k+l;j++)〃循环比较剩余的变量

if(stu川.m>stu[j].m)〃如果前面一个数比后面数大，交换两个数的值

{temp=stu[i];

stu[i]=stu[j];

stu[j]=temp;

)

for(i=0;i<k;i++)

for(j=i+l;j<k+l;j++)〃循环比较剩余的变量

if(stu[i).clas>stu[j].clas)〃如果前面一个数比后面数大，交换两个数的值

{temp=stu[i];

stu[i]=stu[j]；

stu[j]=temp;

)

“/两次冒泡法使学生信息按专业班级排序

4、调试分析：

在调试时浮现过程序浮现死循环和闪退的问题，后来在组长和组员的努力下问题得以解

决。

5、使用说明：

本程序使用二级索引表，以学号作为索引关键字，实现专业一一班级一一个人的三级查

询，提高了查询效率，减少了查询次数。而且专业内班级索引表为动态生成，使用空间并不

会很大，节约了内存。

6、测试结果：

•C:\Users\ffi恺\Desktop迂傻恺忖算机1404王俊恺20143693K幅结构试验\一.一°EI

青辆人学生信息；专业班级学号性哲榆入学号为也酰

恂抖后•访.人注全：

■C:\Users\gHS\Desktop\J4041^1^20143693«UES|2y^\...-°B3I

谓输入学生彳苔息i专业班级学号姓名输，1字号为。靖束

3120140001AA

#22A14RMSAC

B220140008nF

3420143018AI

422s14纯11AN

3520140025AX

»820140065BC

3420149020AZ

0bZH14•4。HR

L520140151CG

122R14R126CB

L820140186Pt

I420140148DF

L120140101BX

212R14W11HR

2120140218HH

2120140220GD

I42Hl4tf263Ji

2220140225GG

2620140288LI

2820140299IH

27IH

3120140303MH

搜狗抖"S■锚入法：二•

■C:\Users\俊恺\Desktop任俊管廿真机1404王俊欣014369瓒幅结构试验\-.-0B9

182014018bFH

1420140148DF

1120140101BX

2120140211HB

212H14加18HH

212014R22a

2420140260

2220140225

2620140288

?A2014融99

2720140290

3120140303

3320148323

312R14A3A9

3220140315

3421914b338

3620140359

3420140340

3520140346

3729143389

3820148399

搜:龙J抖音症物土A

■C:\Users\8HS\Deskiop\Ift1S\lTBfl1404王俊恺2014369玻煽绐利雌、.一

2120140211HB

2120140218HH

212R14W22HGD

2420140268JI

222014B225GG

2628144288L1

28201402991N

2720148290la

J120140303MH

332^140323UH

3120140309MQ

322014331，NN

3\20140339RA

362014B35fTft

3420140340RX

352H144246ST

3720140389ZX

3820140399ZZ

请输入今查询学号,

20140218

艘狗抖音检人注金：

C:\Users\俊怡\Desktop\I俊恺\it茸机1404王俊怡201436933箔做曲一

I120148220GD

2420140260J1

222R14R225GC

2620140288L1

282014827?IH

Z72匕14829111A

3120140303nri

)320140323OA

)12014030?NQ

J22614D31SNH

}420148338刖

)62A14A3S9TO

)420140340RX

3520140346ST

3720140389ZX

?R23140399ZZ

清榆人待查询学号，

20140218

专注班级学号姓名

2120148218HH

7、附录：

源程序：

#include<stdio.h>

#definemaxsize100

enummajor{ml=0,m2,m3,m4=3};〃假设有四个专业

inti;

structstudent{

majorm;

intdas;〃班级编号为1・8

longnumber;

char*name;

};〃定义学生个人信息储存结构

structfinder{

longnumber;

structstudent*p;

};〃定义索引表储存结构

structfinderfl;

typedefunionpart{

finderf;

students[maxsize];

}；

partpl;

intmaketablel(structstudentstu[])

(

intml;

intk;

printf(“请输入学生信息：专业班级学号姓名输入学号为。结束\己)；

scanf("%d%ld%ld%s"/&stu[0].m/&stu[0].clas,&stu[0].number,&stu[O].name);

for(i=0;i<maxsize;)

{i++；

scanf("%d%ld%ld%s",&stu[i].mz&stu[i].clas,&stu[i].number,&stu[i].name);

if(stu[i].number==O)

break;

)

i-；

k=i;

returnk;

}〃构造顺序表

voidquefstructstudentstu[],intk)

(

intj;

structstudenttemp;

for(i=0;i<k;i++)

for(j=i+l;j<k+l;j++)〃循环比较剩余的变量

if(stu[i].m>stu[j].m)〃如果前面一个数比后面数大，交换两个数的值

{temp=stu[i];

stu[i]=stu[j];

stu[j]=temp;

)

for(i=0;i<k;i++)

for(j=i+l;j<k+l;j++)〃循环比较剩余的变量

if(stu[i].das>stu[j].clas)〃如果前面一个数比后面数大，交换两个数的值

{temp=stu[i];

stu[i]=stu[j];

stu[j]=temp;

}

}〃两次冒泡法使学生信息按专业班级排序

structstudentmax(structstudentstu[]Jntk)

(

intm=0;

for(i=0;i<k;i++)

{

if(stu[i].number>stu[m].number)

m=i;

)

returnstu[m];

}〃找出每一个块中的最大值

unionpartfindl(structstudentstu[],majormjntk)

(

intj;

i=0;

structstudentsi;

studentstuO[maxsize];

for(j=0;j<k;j++)

(

if(stu[j].m==m)

(

stuO[i]=stu[j];

i++；

)

)

sl=max(stuO,k);

pl.f.number=sl.number;

pl.f.p=stuO;

for(i=0;i<k;i++)

pl.s[i]=stuO[i];

returnpl;

}〃按专业分块

structfinderfind2(structstudentstu[],intk,inta)

(

intj;

structstudentsi;

structstudentstuO[maxsize];

for(j=0;j<k;j++)

(

if(stu[j].clas==a)

(

stuO[i]=stu[j];

i++；

)

else;

)

sl=max(stuO,k);

fl.number=sl.number;

fl.p=stuO;

returnfl;

}〃按班级分块

voidmaketable2(structstudentstu[],structfinderf[]Jntk)

(

majorm=ml;

f[O]=findl(stu,m/k).f;

m=m2;

f[l]=findl(stu,m/k).f;

m=m3;

f[2]=findl(stu,m,k).f;

m=m4;

f[3]=findl(stu/m/k).f;

}〃生成专业索引表

voidmaketable3(unionpartp,structfinderf[],intk)

{

intcl;

for(cl=l,i=0;cl<9;cl++,i++)

f[i]=find2(p.s/k/cl);

}〃生成班级索引表

majorsearchlfintnum,structfinderf[])

(

i=0;

structstudentst;

if(num<f[O].number||num>f[3].number)

{printf(“查无这人！");

)

else

for(;i<4;)

{if(num>=f[i].number&&num<f[i+l].number)

{st=*f[i].p;

returnst.m;

)

elsei++;}

}

voidsearch2(intnum,structfinderf[])

(

i=0;

structstudentst