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

《数据结构——查找与排序报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数学与计算机学院实验报告（2011/2012学年第1学期）课程名称数据结构课程代码6014279实验时间2011年12月19日指导单位软件工程系指导教师周立章学生姓名唐九零年级2010级学号312010080611427专业软件工程实验成绩11实验名称查找和排序指导教师周立章实验类型验证实验学时2+8实验时间一、实验目的和要求1．掌握静态表查找存储结构和算法；2．掌握动态表查找存储结构和算法3．掌握折半查找算法和二叉排序树查找算法。4．掌握常用的排序方法及实现；5．深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用实验要求：了解掌握查找算法的基本思想和算法的实现；了解各种方法的排序过程及

2、依据的原则，并掌握各种排序方法的时间复杂度的分析方法。二、实验环境(实验设备)硬件:微型计算机P5软件:WindowsXP+MicrosoftVisualC++6.0三、实验原理及内容实验题目:给出n个学生的考试成绩表，每条信息由姓名和分数组成，试完成下列操作：1.输入n个学生的姓名和成绩，保存于考试成绩表中（可用结构体数组）；2.排序：使用直接插入排序算法对学生的分数按升序排列，结果保存在原考试成绩表中。3.输出：按一行一个学生信息的方式输出n个这生考试成绩表。4.查找：对于经步骤2排序好的考试成绩表，请使用二分查找算法查找分数为x的学生，若存在则输出学生的姓名和分数，否则输出“查无此人”信

3、息。5．根据1中输入的成绩表，实现下列算法：1）建立二叉排序树；2）使用中序遍历算法输出遍历序列；3）在二叉排序树中查找成绩为x的学生，若存在输出该学生信息，否则输出未找到信息。6.将考试成绩表分别使用希尔排序、堆排序对分数进行升序和降序排列并输出。11实验前完成1，3；实验中完成2，4题；实验后完成：5,611实验解答：1.学生考试成绩表的结构体定义structmessage{intkey;stringname;floatscore;message*lchild,*rchild;};2.学生考试成绩表的定义messagem[max+1];3.n个学生录入的算法代码voidstudent::I

4、nput(){stringn;floats;cout<<"请输入学生的信息"<>n;if(n=="0")break;cin>>s;m[i].key=i+1;m[i].name=n;m[i].score=s;length++;if(length>=max){11cout<<"表格已满，不能再输入"<

5、{t=m[i];intj,k;for(j=0;jj;k--){m[k]=m[k-1];}m[k]=t;}}5.n个学生考试成绩表的输出算法voidstudent::Print(){11cout<<"学生成绩表如下："<

6、ats){intt=(low+high)/2;if(low<=high){if(s==m[t].score){cout<<"查找的数据在"<m[t].score){low=t+1;}if(s

7、LL)t=s;elseif(s->scorescore)t->lchild=BinarySortInsert(t->lchild,s);elset->rchild=BinarySortInsert(t->rchild,s);returnt;}voidstudent::BinarySort(){message*s;inti;for(i=0;i