数据结构实验五

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

2、仅有一个特定的结点，称为树的根(root)；（2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集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<iostream>#include<string>using namespace std;struct studentint num; /学号char name20; /姓名char banji20; /班级int c; /C语言课程成绩int datastruct; /数据结构课程成绩;struct queuestruct student a8;int lenth;class li

5、stprivate:queue d;public:int seqsearch(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

6、,77,3,"刘丽","03511",90,79,4,"王童","03511",75,86,5,"赵阳","03511",60,71,6,"李艳","03511",58,68,7,"钱娜","03511",95,89,8,"孙胜","03511",45,60,;for(int i=0;i<8;i+)d.ai=ei;void list:show(int

7、i)if(i=-1)cout<<"sorry not found!"<<endl;elsecout<<"学号"<<"班级"<<"c+"<<"数据结构n"cout<<""<<d.ai.num<<" " cout<<<<" "cout<<d.ai.banji<<&quo

8、t; "cout<<d.ai.datastruct<<" "cout<<d.ai.c<<endl;void list:display(list l)cout<<"学号"<<"班级"<<"c+"<<"数据结构n"for(int i=0;i<8;i+)cout<<""<<l.d.ai.num<<" " cout&l

9、t;<<<" "cout<<l.d.ai.banji<<" "cout<<l.d.ai.datastruct<<" "cout<<l.d.ai.c<<endl;int list:seqsearch(list l,char name20)/顺序查找for(int i=0;i<8;i+)if(strcmp(,name)=0)return i;return -1;void list:insertsort

10、(list l)/直接插入排序struct student n;for(int i=1;i<8;i+)n=l.d.ai;int j=i-1;while(j>=0&&strcmp(,)<0)l.d.aj+1=l.d.aj;j-;l.d.aj+1=n;display(l);void list:selectsort(list l)/简单选择排序for(int i=0;i<7;i+)int j=i;for(int k=j;k<8;k+)if(l.d.aj.c<l.d.ak+1.c)j=k+1;if(j!=i)stud

11、ent s=l.d.ai;l.d.ai=l.d.aj;l.d.aj=s;display(l);void list:bubblesort(list l)/冒泡排序for(int i=7;i>0;i-) for(int j=0;j<i;j+)if(l.d.aj.datastruct>l.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,&

12、quot;赵阳");l.show(i);cout<<endl;cout<<"直接插入排序对姓名进行排序n" cout<<"排序前的结果：n"l.display(l);cout<<"排序后的结果：n"l. insertsort (l);cout<<endl;cout<<"简单选择排序对c语言成绩进行排序n" cout<<"排序前的结果：n"l.display(l);cout<<"排序后的结果：n"l.selectsort(l);cout<<endl;cout<<"冒泡排序对数据结构成绩进行排序n" cout<<"排序前的结果：n