数据结构-查找与排序报告

数学与计算机学院实验报告〔2011/2012学年第1学期〕课程名称数据结构课程代码6014279实验时间2011年12月19日指导单位软件工程系指导教师周立章学生姓名唐九零年级2010级学号专业软件工程实验成绩

实验名称查找和排序指导教师周立章实验类型验证实验学时2+8实验时间实验目的和要求1．掌握静态表查找存储结构和算法；2．掌握动态表查找存储结构和算法3．掌握折半查找算法和二叉排序树查找算法。4．掌握常用的排序方法及实现；5．深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用实验要求：了解掌握查找算法的根本思想和算法的实现；了解各种方法的排序过程及依据的原那么，并掌握各种排序方法的时间复杂度的分析方法。二、实验环境(实验设备)硬件:微型计算机P5软件:WindowsXP+MicrosoftVisualC++6.0三、实验原理及内容实验题目:给出n个学生的考试成绩表，每条信息由姓名和分数组成，试完成以下操作：输入n个学生的姓名和成绩，保存于考试成绩表中〔可用结构体数组〕；排序：使用直接插入排序算法对学生的分数按升序排列，结果保存在原考试成绩表中。输出：按一行一个学生信息的方式输出n个这生考试成绩表。查找：对于经步骤2排序好的考试成绩表，请使用二分查找算法查找分数为x的学生，假设存在那么输出学生的姓名和分数，否那么输出“查无此人”信息。5．根据1中输入的成绩表，实现以下算法：1〕建立二叉排序树；2〕使用中序遍历算法输出遍历序列；3〕在二叉排序树中查找成绩为x的学生，假设存在输出该学生信息，否那么输出未找到信息。6.将考试成绩表分别使用希尔排序、堆排序对分数进行升序和降序排列并输出。实验前完成1，3；实验中完成2，4题；实验后完成：5,6实验解答：1.学生考试成绩表的结构体定义structmessage{ intkey; stringname; floatscore; message*lchild,*rchild;};2.学生考试成绩表的定义messagem[max+1];3.n个学生录入的算法代码voidstudent::Input(){ stringn; floats; cout<<"请输入学生的信息"<<endl; for(inti=0;;i++) { cout<<"请输入学生的星系和成绩："; cin>>n; if(n=="0") break; cin>>s; m[i].key=i+1; m[i].name=n; m[i].score=s; length++; if(length>=max) { cout<<"表格已满，不能再输入"<<endl; break; } }}4．按分数进行直接插入排序算法的代码voidstudent::InsertOrder(messagem[]){ messaget; for(inti=1;i<length;i++) { t=m[i]; intj,k; for(j=0;j<i;j++) { if(t.score<m[j].score) { break; } } for(k=i;k>j;k--) { m[k]=m[k-1]; } m[k]=t; }}5.n个学生考试成绩表的输出算法voidstudent::Print(){ cout<<"学生成绩表如下："<<endl; for(inti=0;i<length;i++) { cout<<"姓名："<<m[i].name<<"成绩："<<m[i].score<<endl; }}6．n个学生按分数进行二分查找算法。intstudent::BinarySearch(intlow,inthigh,floats){ intt=(low+high)/2; if(low<=high) { if(s==m[t].score) { cout<<"查找的数据在"<<t+1<<"位置"<<endl; returnt; } if(s>m[t].score) { low=t+1; } if(s<m[t].score) { high=t-1; } BinarySearch(low,high,s); } else { cout<<"数据查找失败"<<endl; return-1; } return-1;}7．按成绩建立二叉排序树算法message*student::BinarySortInsert(message*t,message*s){ if(t==NULL) t=s; elseif(s->score<t->score) t->lchild=BinarySortInsert(t->lchild,s); else t->rchild=BinarySortInsert(t->rchild,s); returnt;}voidstudent::BinarySort(){ message*s; inti; for(i=0;i<length;i++) { s=newmessage; s->key=m[i].key; s->name=m[i].name; s->score=m[i].score; s->lchild=NULL; s->rchild=NULL;root=BinarySortInsert(root,s); } cout<<"二t叉?树º¡Â遍À¨¦历¤¨²数ºy列¢D：êo"; InterVisit(root); cout<<endl; SearchStudent();}8．按成绩进行二叉排序树查找算法voidstudent::SearchStudent(message*p,floats,int&i){ if(p!=NULL) { SearchStudent(p->lchild,s,i); SearchStudent(p->rchild,s,i); if(p->score==s) { i++; cout<<"查找学生的姓名："<<p->name<<"成绩："<<p->score<<endl; } }}9．你准备用于测试的数据表姓名成绩张山87朱路65唐凤76梅丽67郭阳89刘基10010.写出测试数据在直接插入排序时各趟的结果第一趟：6587766789100；第二趟：6576876789100；第三趟：6567768789100；11.用于测试查找的分数二分查找：〔1〕用于查找成功的分数数据100〔2〕用于查找失败的分数数据10二叉排序树查找：〔1〕用于查找成功的分数数据100〔2〕用于查找失败的分数数据1012.如果将你用于测试的学生分数构建小堆，那么初始小堆是：13.画出你用于测试的学生成绩表建立的二叉排序树四、实验小结1．直接插入排序的平均比拟和平均移动次数分别是什么？平均比拟次数:n平均移动次数:n2.静态和