数据结构试验

实验四查找和排序应用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].number,&stu[O].name);for(i=0;i<maxsize;){i++；scanf("%d%ld%ld%s",&stu[i].m/&stu[i].clas/&stu[i].number,&stu[i].name);if(stu[i].number==O)break;)i-；k=i;returnk;}〃构造顺序表voidque(structstudentstu[],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].clas>stu[j].clas)〃如果前面一个数比后面数大，交换两个数的值{temp=stu[i];stu[i]=stu[j];stu[j]=temp;}}//两次冒泡法使学生信息按专业班级排序4、调试分析：在调试时浮现过程序浮现死循环和闪退的问题，后来在组长和组员的努力下问题得以解决。5、使用说明：本程序使用二级索引表，以学号作为索引关键字，实现专业一一班级一一个人的三级查询，提高了查询效率，减少了查询次数。而且专业内班级索引表为动态生成，使用空间并不会很大，节约了内存。6、测试结果：■C:\Users\傻恺\Desktop\I俊怡、计算机1404王俊恺20143593数幅结构雌'…-青狗入学生信息：专业班级学号姓名输A学号为也吉束X■匚\血0俊信5，1(5\1俊恺\计算见1404王俊恺20143693蚊据给用雌\”・-c182U14418bFH1420149148DF1120140101BX,,1201402X1HB120140218HN912R14A22R0Im420140260220140225962014028811R2014腼99|La7201402983120140303332014a323312014船0932201403153420140J38362814035934201403403520140346n7281443893820140399口讣J折音箍人;/一■C:\Use「s\傻恺\Desk〔op\I俊恺、计算机1404王俊信20143693数据结构试虻-2120140211HB2120149218HH212H14«22RGD2420140260JI2220140225GGI629144288L12820149299IH2720140290I。3120140303MHJ32914匕323OR312014B309MQ222014初1，NH3420140339PA362014035?TA3420149340RX352H14初46ST3720140389ZX3820140399ZZ请输入今查询学号:20140218■C:\Users\发恺\Desktop\I俊憎'计茸机1404王俊恺20143693数据后构试孰.・・一2120148220GP2420148260J1222W14R225GC2620148288L12820148299IH272匕14嫉2丫。1A3120148383rm332014032333120140309HQJ220140315NP3420140338Rfi?62C140招9TQ3\20140340m3520140346SI3720148389ZX1R2W14A399ZZ看柿人待查询学号.20140218专业班级学号姓名2120148218HH7、附录：源程序：ttinclude<stdio.h>#definemaxsize100enummajor{ml=0,m2,m3,m4=3};〃假设有四个专业inti;structstudent{majorm;intclas;〃班级编号为1・8longnumber;char*name;};〃定义学生个人信息储存结构structfinder{longnumber;structstudent*p;};〃定义索引表储存结构structfinderfl;typedefunionpart{finderf;students[maxsize];}；partpl;intmaketablel(structstudentstu[])(intml;intk;printf(“请输入学生信息：专业班级学号姓名输入学号为0结束\n“)；scanf("%d%ld%ld%s"/&stu[O].m,&stu[O].clas,&stu[O].number/&stu[O].name);for(i=0;i<maxsize;){i++；scanf("%d%ld%ld%s",&stu[i].m/&stu[i].clas/&stu[i].number/&stu[i].name);if(stu[i].number==O)break;)i--；k=i;returnk;}〃构造顺序表voidque(structstudentstu[],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].clas>stu[j].clas)〃如果前面一个数比后面数大，交换两个数的值{temp=stu[i];stu[i]=stu[j];stu[j]=temp;)}〃两次冒泡法使学生信息按专业班级排序structstudentmax(structstudentstu[],intk)(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[],intkJnta)(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[],intk)(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=lJ=0;cl<9;cl++J++)f[i]=find2(p.s,k,cl);}〃生成班级索引表majorsearchl(intnum,structfinderf[])(i=0;structstudentst;if(num<f[0].number||num>f[3].number){printf("查无这人!”)；}elsefor(;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;if(num<f[O].number)|num>f[7].number)printf("查无这人!")；else{for(;i<8;){if(num>=f[i].number&&num<f[i+l].number){st=*f[i].p;switch(st.m){case(ml):pnntf("ml");break;case(m2):printf("m2");break;case(m3):printf("m3");break;case(m4):pnntf("m4");break;}printf("%ld%ld%s"/st.clas/st.number,);}elsei++;}})intmain()(structstude