數據結構試驗

實驗四查找和排序應用

1、實驗題目：

索引順序表應用

(1)課題目的：

東北大學信息學院學生信息查詢系統(tǒng)。各專業(yè)按名稱有序，專業(yè)內按班級編號有序，班

級內記錄無序。

(2)課題任務：

設計索引順序表的學生信息查詢系統(tǒng)。

1)采用順序表、索引表等存儲結構。

2)采用二級順序表索引。

3)完成表的創(chuàng)建、插入、查詢等操作。

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

2、概要設計：

使用順序表存儲學生信息，并按照專業(yè)班級挨次排序，并通過輸入學號實現檢索。先建

立專業(yè)索引表，結構體成員為專業(yè)中學號的最大值和專業(yè)中子順序表的頭指針，對輸入的學

號與各塊中的最大值進行比較，進而確定專業(yè)。再根據所在專業(yè)動態(tài)生成二級索引表，即班

級索引表，結構體成員為班級中學號的最大值和順序表的頭指針，可查出所在班級。最后在

子順序表，即各班級的順序表中進行查找。

平均查找長度為：4+8+x(各班人數的平均值)

3、詳細設計：

我設計的部份：我主要設計了構造順序表和將學生信息按專業(yè)班級排序兩個部份，將輸

入的學生信息存儲到順序表中，而后進行排序。

intmaketablel(structstudentstu[])

(

intml;

intk;

printf("請輸入學生信息：專業(yè)班級學號姓名輸入學號為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++)〃循環(huán)比較剩余的變量

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++)〃循環(huán)比較剩余的變量

if(stu[i).clas>stu[j].clas)〃如果前面一個數比后面數大，交換兩個數的值

{temp=stu[i];

stu[i]=stu[j]；

stu[j]=temp;

)

“/兩次冒泡法使學生信息按專業(yè)班級排序

4、調試分析：

在調試時浮現過程序浮現死循環(huán)和閃退的問題，后來在組長和組員的努力下問題得以解

決。

5、使用說明：

本程序使用二級索引表，以學號作為索引關鍵字，實現專業(yè)一一班級一一個人的三級查

詢，提高了查詢效率，減少了查詢次數。而且專業(yè)內班級索引表為動態(tài)生成，使用空間并不

會很大，節(jié)約了內存。

6、測試結果：

?C:\Users\ffi愷\Desktop迂傻愷忖算機1404王俊愷20143693K幅結構試驗\一.一°EI

青輛人學生信息；專業(yè)班級學號性哲榆入學號為也酰

恂抖后?訪.人注全：

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

謂輸入學生彳苔息i專業(yè)班級學號姓名輸，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};〃假設有四個專業(yè)

inti;

structstudent{

majorm;

intdas;〃班級編號為1?8

longnumber;

char*name;

};〃定義學生個人信息儲存結構

structfinder{

longnumber;

structstudent*p;

};〃定義索引表儲存結構

structfinderfl;

typedefunionpart{

finderf;

students[maxsize];

}；

partpl;

intmaketablel(structstudentstu[])

(

intml;

intk;

printf(“請輸入學生信息：專業(yè)班級學號姓名輸入學號為。結束\己)；

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++)〃循環(huán)比較剩余的變量

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++)〃循環(huán)比較剩余的變量

if(stu[i].das>stu[j].clas)〃如果前面一個數比后面數大，交換兩個數的值

{temp=stu[i];

stu[i]=stu[j];

stu[j]=temp;

}

}〃兩次冒泡法使學生信息按專業(yè)班級排序

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;

}〃按專業(yè)分塊

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;

}〃生成專業(yè)索引表

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