数据结构实验五

1、.数据结构实验报告实验题目：实验五、查找排序姓名：学号： 142054301班级： 1420543系名：计算机工程系专业：计算机科学与技术指导老师：实验时间：2016年6月14日实验地点：专业软件实验室【实验概述】1. 实验目的及要求目的：1掌握哈希表的定义，哈希函数的构造方法。2掌握并比较各种排序算法。要求：预习并掌握查找的概念、 静态查找与动态查找、 顺序查找、二分查找、索引查找、二叉排序树的概念、平衡二叉树、哈希查找、直接插入排序、快速排序、冒泡排序、简单选择排序等算法思想。2. 实验原理1、树的逻辑结构特点：树(tree)是n(n 0) 个结点的有限集 T，其中：（1）有且仅有一个特定

2、的结点，称为树的根(root)；（2）当n1时，其余结点可分为 m(m0)个互不相交的有限集 T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。2、树结构中的基本术语，以及树的树形结构表示。.3、二叉树的逻辑结构特点：1、查找和排序是日常数据处理过程中经常要进行的操作和运算。2、查找是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或 ( 记录 ) 。若查找表中存在这样一个记录，则称“查找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”，查找结果：给出“空记录”或“空指针” 。3、静态查找与动态查找的区别。平

3、均查找长度。4、查找算法有：静态查找中常见的查找算法：顺序查找、二分查找、索引查找。动态查找中常见的算法有二叉排序树和平衡二叉树上的查找。平均查找长度为0的哈希查找。5、排序是是将一组“无序”的记录序列调整为“有序”的记录序列。6、排序算法的优劣从空间复杂度、时间复杂度、稳定性三个角度分析。7、常见的排序算法可分为：插入类、交换类、选择类、归并排序、基数排序等。3. 实验环境（使用的软件）VC+6.0.【实验内容】1. 实验算法设计设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、成绩等信息。要求实现以下功能：1、查找：分别给定学生学号、姓名，能够查找到学生的基本信息（要求至少实现改进

4、后的顺序查找算法） ；2、排序：分别按学生的学号、成绩进行排序（要求至少用实现直接插入排序、冒泡排序、简单选择排序算法） 。2. 实验过程（源代码及描述、调试过程及分析）#include#includeusing namespace std;struct studentint num; /学号char name20;/姓名char banji20;/班级int c;/C语言课程成绩int datastruct;/数据结构课程成绩;struct queue.struct student a8;int lenth;class listprivate:queue d;public:int seqse

5、arch(list,char *);int binsearch(list,int,int,int);void insertsort(list);void selectsort(list);void bubblesort(list);list();void display(list);void show(int);list:list()struct student e8=1, 王丽 ,03511,85,76,2, 张秋 ,03511,78,77,.3, 刘丽 ,03511,90,79,4, 王童 ,03511,75,86,5, 赵阳 ,03511,60,71,6, 李艳 ,03511,58,68

6、,7, 钱娜 ,03511,95,89,8, 孙胜 ,03511,45,60,;for(int i=0;i8;i+)d.ai=ei;void list:show(int i)if(i=-1)coutsorry not found!endl;elsecout 学号 班级 c+ 数据结构 n;coutd.ai.num;;coutd.ai.banji;coutd.ai.datastruct;coutd.ai.cendl;.void list:display(list l)cout 学号 班级 c+ 数据结构 n;for(int i=0;i8;i+)coutl.d.ai.nu

7、m;;coutl.d.ai.banji;coutl.d.ai.datastruct;coutl.d.ai.cendl;int list:seqsearch(list l,char name20)/顺序查找for(int i=0;i8;i+)if(strcmp(,name)=0)return i;return -1;void list:insertsort(list l)/直接插入排序.struct student n;for(int i=1;i=0&strcmp(,)0)l.d.aj+1=l.d.aj;j-;

8、l.d.aj+1=n;display(l);void list:selectsort(list l)/简单选择排序for(int i=0;i7;i+)int j=i;for(int k=j;k8;k+).if(l.d.aj.c0;i-)for(int j=0;jl.d.aj+1.datastruct)student d=l.d.aj;l.d.aj=l.d.ai+1;l.d.aj+1=d;.display(l);void main()list l;cout 顺序查找姓名为赵阳的学生n;int i=l.seqsearch(l,赵阳 );l.show(i);coutendl;cout 直接插入排序对姓名进行排序n;cout排序前的结果： n;l.display(l);cout 排序后的结果： n;l. insertsort (l);coutendl;cout 简单选择排序对 c语言成绩进行排序 n;cout排序前的结果： n;l.display(l);cout 排序后的结果： n;l.selectsort(l);.coutendl;cout 冒泡排序对数据结构成绩进行排序n;cout排序前的结果： n;l.display(l);cout 排序后的结果： n;