2023年数据结构实验报告查找最高分与次高分.pdf

核据秸相与程序强制实险实验报告课程名称数据结构与程序设计实验课程编号090 6 5 50实验项目名称查找最高分与次高分学号年级姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静实验室名称地点21B276哈尔滨工程大学 实验报告六实验课名称:数据结构与程序设计实验实验名称:查找最高分与次高分班级：学号：姓名：时 间:2 0 23.05.05一、问题描述有5 1 2人参与玩某游戏，从 尸5 1 2给每个人分派一个编号，每个人的游戏得分 在0999之间,现要用不同方法查找出游戏参与者的最高分和次高分。规定：a.自行产生51 2个的随机整数作为所有游戏参与者的得分。b.输出所有游戏参与者(用编号表达)及其得分。c.用顺序查找方法查找出其中取得最高分和次高分者及其分数，并输出。d.锦标赛法查找出其中取得最高分和次高分者及其分数，并输出。e.通过无序序列建堆和堆调整得到取得最高分者和次高分者及其分数，并输出。f.比较不同方法的查找效率和各自的特点。二、数据结构设计1,使用结构体People存储序号和得分，表达个体t y ped e f stru c t i nt num；int score;Pe o p 1 e;2,设立M I N表 达Pe。pie数据类型的最小值，用于竞标赛查找#def i ne I N_MAX(int)(u n s i g n ed)(in t)0)1)#de f i ne IN_MIN(-|N _ M A X-l)cons t P e ople MIN=5 1 3,I N_MIN);3.使用结构体Pe o p 1 e s作为顺序表,存储每个个体t y pe d e f s tructPeopl e base；int leng t h;P e o pies;三、算法设计1 .顺序查找int search(Pe o pies*p)P e ople big g e r=p-b as e 1；P e op I e big g est=p-base 1 ;int n;f or(n=1 ；n b asen.s c o re bi g gest.s c or e)big g er=b i g ge s t;b i gg e st=pba s e n;e 1 se i f(p-ba s en.s c ore b igge r.score)b i gger=p-b ase n;if(p-b a s e n.num!=b igge s t.num&p-b a s e n.sco r e=big g es t.score)p r intf(第d人和第d人的分数同样大 n”，p-basen.num,b igge s t.num);)P r intf(第 1 人的的分数最大:%dn,big g est.num,b ig g es t.sco r e);P r i n t f(*第=n)/x为叶子节点p-base 冈=MIN;return；e 1 se i f(r=n)/x有左子树，无右子树p-basex=p-b a s e L 1 ；r e t u rn；)if(p-base I,n um=p-b a s e x.n u m)Ad j us t(p,I,n);e 1 seAdjust(p,r,n)；)p-basex=max(p-basel,p-b a s e r)；)(b).初始树并依次查找最大值与最大值vo i d Game S or t(Peoples*a,i n t n)i nt i,Ie n；P eo p les*b;b=(Peoples*)ma 1 1 o c(siz e of(P eopl e s);len=1;w h ile(len n)len bas e=(People*)malloc(si z e o f(P e o p 1 e)*len);b-l e ngth=1 e n;fo r(i=len/2；i b asei=(i-1 en/2 b a se i-len/2)：(M I N)；)for(i=len/2-1 ;i=l；i)/在双亲存放左右最大值b-basei=ma x(bbas e 2*i,b-bas e 2*i+1 1);for(i=1；iba s e i=b-bas e 1;A d j u s t(b,1,len);)p r in t f(第%d 人的的分数最大:%dn,a-basel.num,a-b a sel.score);p r i n tf(第(1 人的的分数次大：%d n,a b as e 2.n um,a-base2.s core)；f r ee(b)；3.通过无序序列建堆和堆调整得到取得最高分者和次高分者及其分数(a).筛 选:除 P bas e s外均满足堆定义，调整pb a ses,将 p-b a ses,m建立为大顶堆i n t He a pA d j ust(P e ople s*p,i n t s,int m)P eople rc=p-bases;in t j;for(j=2*s;j=m;j*=2)i f(jbasej.s c o r e basej+1 .s c o r e)+j;j 指向较大的孩子节点)i f(!(r c.sc o re base j .scor e)b r eak；)p-base s =p-b as e j；s=j;p-b ases=r c;re t urn 0;)(b).对 p base1.512建堆，进行堆调整取得最高分和次高分者,并输出i n t HeapSort(People s*p)int i;for(i=(p-le n gt h)/2；i0；一 i)从最后一个非叶子节点开始，建立大顶堆H e apA d j u s t(p,i,p 1 ength);)for(i=p-l e ngth;i510;-i)只将最大和次大的得分互换到末尾s wap(p-bas e 1,p-ba s e i);He a pAdj u s t(p,1,i-1);pri n tf(第d 人的的分数最大:%d n,p-b ase512.n um,p-base 5 12.score);p r i nt f(第%d 人的的分数次大:%dn,p-bas e 511.num,p-b a se 511.sco r e)；return 0;）四、运营测试与分析L 开始运营后，自 行 产 生 5 1 2 个的随机整数作为所有游戏参与者的得分，并输出所有游戏参与者（用编号表达）及其得分。7228422116969085441日否否否否否否否否否否否否得否皆否否否否否否否正数皴数数数数数数数数数数数数数数数数数数数数数数匕二ts二14.二二14.二Is二二.rv二&-1s二LJIIs二tsI-ISI-二L-A,11Is二14.二L-JLFIIH二&-人人人人人人人人人人人人人人人人人人人人人人人人ITTTJlTytTTtxlTTT第第第第第第第第第第第第第第第第第第第第第第第第一7 17114295716644145288?1851524550115117977121日得否否否否否否否否否否否否否否否否否否否否得否正数数数数数数数数数数数数数数数数数数数数皴第第第第第第第第第第第第第第第第第第第第第第第第4、V.ZX4、V4、vLh、V4、V4、vr*4、V4VA、V4、V4、vLh、V4、V、V卜、vLhV卜、.Vts二LJ二g二-JD1-L-L3II乙，二L-L-141.1lsk、vhV卜、：vLh、.卜、卜,vMh、，v、.4lvlh、vMh、,卜，vlh、.V卜、v卜、卜、，VIs二s二L-Is二h.二L-Is二h.11s二6V二th.二ts二L-Is二141.1141.1Is二h.二s二J，二h.1Ys二人人人人人人人人人人人人人人人人人人人人人人4680246888999944414444第第第第第第第第第第第第第第第第第第816546011395842176163493947186171827r=_否否否否否否否否否否否否否否否否否否否否否7E一数数数数数数数数数数数数一数数数数jTT-0，/*FT-TT-f*TT-JTT-JTT*d-fEI-n-TT-/*TT-TT-JTTl&Q-XA.ATT777944AAAx5.O9Q44一第第第第第第第第第第第第第第第第第第第士3.输出顺序查找，锦标赛查找，堆排序查找的结果大大亵数数 契4A序4424顿第第-h v h v勺一/n r一赛1/4/一听、4 4*4 2O R第8 59 99 90裳8 59 99 9 最大：998244人的的分数茯大：995五、实验收获与思考通过本次实验，巩固了关于查找算法的知识，同时在编程过程中发现了自己的局限性，碰到了很多语法错误及逻辑错误，通过不断的调试解决问题，使我对编程有了更加进一步的体会和结识。顺序查找，锦标赛查找，堆查找的效率及特点：假如有n个待查找元素，顺序查找每次查找均需进行n-1次比较，但不需额外存储空间。锦标赛排序构成的树是满的完全二叉树,深度为log2+l,除第一次选择具有最大关键码的记录需要进行n-1次比较外，重构树选择具有次小、再次小关键码记录所需的比较次数均为0 但这种选择方法虽然减少了许多查找时间，但是使用了较多的附加存储。堆查找的运营时间重要花费在初始和调整堆时进行的反复筛选上，堆查找仅需记录一个大小供互换的辅助存储空间，每个记录仅占有一个存储空间。六、源代码#include#include#incl u d e#def i n e max(x,y)(x.sco r e)(y.score)?(x)：(y)#d e f ine IN_MAX(i n t)(un s i gned)(i n t)0)1)#de f i n e IN_M I N(-|N_MAX-1)t ypedef s t ructi nt num;i nt s c ore;Peo p Ie;typedef str u ctP e o p 1 e*base;i nt 1 eng t h;P e oples;c onst P eopl e MIN=51 3,I N_MIN；Pe o p 1 e#def i n e s wap(x,y)=x；x=y；y=;i nt ini t _all_pe o p 1 e(Peo p ie s *p)i n t n;srand(unsi g ned)t i m e(N U LL);设立每个人的成绩为随机值for(n=l;nb a s e n.n u m=n;p-ba s en.s c ore=r and()%l 0 0 0；)p-length=512;r e tu r n 0;)i n t c opy_ peop 1 e(P e opl e s*p 1 ,People s*p2)int n;f o r (n=l；nba s en.n um=pl-b a s en.num；p 2-base n.s c or e=pl-b a s e n.s c ore;)p 2-length=p 1 -le n g th;r e tu r n 0；)i n t d i s pl a y(Peo p 1 es*p)i n t n；for(n=1;n b as e n.num,p-b as e n.sc ore);if(n%2=0)pr i ntf(nn)；)r e turn 0；)顺序查找int sea rch(Peo p les*p)P eo p 1 e b i gg e r=p-basel;Peo p Ie biggest=p-b a sel;i n t n;fo r(n=1；nb a s en.s co r e bigges t.s c ore)b i gger=bigge s t;b ig g e s t=p-base n；el s e if(p-basen.s c o re b i g ge r.scor e)b i g ger=p-basen;)i f(p-b a sen.n u m !=b i g g e s t.num&p-b a sen.score=bi gges t.sco r e)printf(第 d人和第d人的分数同样大 n,p-b a sen.num,bi gg e st.n um);print f(第%d 人的的分数最大:%d n,b i g gest.num,bi g ge s t.score)；pr i n t f(第 d 人的的分数次大:d n M,big g er.num,bigge r.s c o r e);return 0;)/锦标赛排序-输出后调整i n t Adj u st(Pe o p 1 e s*p,int x,in t n)i n t I=x*2;左子树int r=I+1;右子树i f(l=n)x为叶子节点p-basex=MIN;return 0；els e i f(r=n)/x有左子树，无右子树p-b a se x =p-b a s e I；r et u r n 0；)if(p-basel.num =p-basex.num)Adj u st(p,1 ,n);e 1 s eAdjust(p,r,n);p-b a sex=m a x(p-basel,p-b a s e r)；retu r n 0;)j n t Gam e Sort(P eoples*a,i nt n)int i,len;Peop 1 e s b;len=1 ;w h i le(1 e n n)len=1;/len 为偶数)len=2*len；/p r i n tf(H len:%dn,l e n);b.b ase=(People*)mall o c(sizeof(Pe o pl e)*1 e n);b.length=1 en;f or(i=len/2;ilen;i+)/初始b.b ase i =(i-le n/2base i-len/2)：(MIN)；for(i=len/2-l;i=l;i 一)/在双亲存放左右最大值b.base i=max(b.b a s e2*i,b.b ase2*i+1);)f or(i=l;ibasei=b.b asel;A d jus t(&b,1,1 e n);)printf(第 1 人的的分数最大:%d n,a-b asel.num,a-b a s e l.s c o r e)；p r in t f(第 d 人的的分数次大：d n”，a-base2.n umz a-base 2.score);return 0;)/*堆排序-筛选*只有p-bas e s 不符合规定，将 p b a s e s,m建立为大顶堆*/int He a pAd j ust(Peo p i e s *p,i n t s,i n t m)Pe o pl e rc=p-b a ses；in t j；for(j=2*s;j=m;j*=2)i f(jbase j.scor e bas e j+1.s c o r e)+j；/J 指向较大的孩子节点)i f(!(r c.scor e basej.score)break;)p-ba s e L s =p-base j;s=j；)p-base s=rc;r etu r n 0;/*对 p-base1.5 1 2 进行堆排序,只将最大和次大互换到末尾*/int H e apSor t(Pe o pl e s*p)int i；for(i=(p-lengt h)/2；i 0;i)从最后一个非叶子节点开始，建立大顶堆H e ap Ad j ust(p,i,p-length);)f o r(i=p-len g th;i510；-i)只将最大和次大的得分互换到末尾swa p(p-b a s el,p-b asei);H eapA dj u s t(p,1,i-1);)pr i ntf(第 d 人的的分数最大：%dn,p-base51 2.n um,p-bas e 512.score);pri n tf(第d 人的的分数次大:%d n，p-b a se 5 1 1.n um,p-base 5 11.sco re);r e tu r n 0;)i n t main()Peoples p 1;p 1 .base=(Peopl e*)malloc(siz e o f(Peo p le)*5 1 3);Pe o p 1 es p2;p2.base=(People*)ma 1 loc(s i z eof(P e o p le)*5 1 3);Peopl e s p 3；p3.base=(P e ople*)mall o c(s ize o f(P eop 1 e)*513);i n it_all_ p eopl e(&p 1)；co p y_people(&p 1 ,&p 2)；co p y_ p e op 1 e(&pl,&p 3);d i sp 1 ay(&p 1);pr i n t f(“n 顺序查找:n )；sear c h(&p 1 )；prin t f(n 锦标赛查找:n )；Game S o r t(&p2,513);p r i ntf(n 堆排序查找:n );Heap S o rt(&p 3)；fr e e(p 1 .b ase)；f ree(p 2.base);f re e(p3.b ase);re t urn 0;教师评分:教师签字: