数据结构试验报告-查找、排序的应用

《数据结构试验报告-查找、排序的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、中原工学院《数据结构》实验报告学院：计算机学院专业：计算机科学与技术班级：计科112姓名：康岩岩学号：201100814220指导老师：高艳霞2013-01-0120实验七查找、排序的应用[问题描述]　对学生的基本信息进行管理。[基本要求]设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能：1．总成绩要求自动计算；2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）；3.排序：分别按学生的学号、成绩1、成绩2、总成绩进行

2、排序（要求至少用两种排序算法实现）。[算法设计]首先，由于本次试验要求的是至少实现两个查找算法和两个排序算法，所以这在程序设计时就要考虑至少使用四个单独的表结构来储存数据。当然，每张表中储存的数据对象都是一样的，只是顺序不同。所以在一次输入时，就要同时有四次插入操作。对与数据信息的查找，需要用到二叉平衡树树与哈希表，本次试验只用哈希表对学生姓名进行查找，对于hash表的构造，所使用的方法如下：intHash(char*key){chark=key[0];return(k*k)%MAX_SIZE;}即取关键字的首字母所对应

3、的10进制ASCLL码，然后做平方后Mod数据最大容量。进行学号的查找，所用的是二叉平衡排序树，二叉平衡排序树能尽可能的减少查找过程中数据的较，而由于学号储存形式为字符串，所以比较的20依据就是对每位数进行字典顺序。另外还需要实现排序算法。我使用的折半插入排序法和二叉排序树插入排序。即在数据的插入过程中就进行了排序。[测试数据]查找姓名(哈希查找)查找学号（二叉平衡排序树）：20排序总成绩（二叉排序树插入排序）：排序编程成绩(折半插入排序)20[附录(源代码)];#include"stdafx.h"#include

4、lloc.h>#includeusingnamespacestd;//最大数据容量#defineMAX_SIZE30#defineLH1//左高#defineEH0//等高#defineRH-1//右高typedefstruct{charstu_name[10];intsex;charstu_num[10];//这个值是惟一的intgrade[3];}Student;//学生对象typedefstruct{Studentstu[MAX_SIZE];intcount;}HashTable;//哈希表ty

5、pedefstructBitNode{Studentstu;structBitNode*lchild,*rchild;}*BitTree;//二叉排序树typedefstructBSTNode{Studentstu;intbf;structBSTNode*lchild,*rchild;}*BSTree;//平衡二叉排序树20typedefstructNode{Studentstu[MAX_SIZE];intlength;}SqList;//折半表//hash表的操作intHash(char*key);//计算hash值i

6、ntSearchHash(HashTableH,char*key,int&p,int&c);//查找intInsertHash(HashTable&H,Studentstu);//插入//二叉排序树的操作intSearchBitTree(BitTreeT,intkey,BitTreef,BitTree&p);//查找intInsertBitTree(BitTree&T,Studentstu);//插入intOrderBitTree(BitTreeT);//中序遍历二叉排序树//平衡二叉树的操作boolSearchAVL(

7、BSTreeT,char*key,BSTreef,BSTree&p);//查找voidR_Rotate(BSTree&p);//右旋voidL_Rotate(BSTree&p);//左旋intInsertAVL(BSTree&T,Studentstu,bool&taller);//插入voidLeftBalance(BSTree&T);//左平衡voidRightBalance(BSTree&T);//右平衡//创建总表传入参数为哈希表，二叉排序树，二叉平衡排序树，折半查找表，总量intCreatTable(HashTa

8、ble&H,BitTree&T,BSTree&BT,SqList&L,intcount);//显示学生信息voidshowStuInfo(Studentstu);//比较函数boolEQ(char*k1,char*k2);boolLT(char*k1,char*k2);boolEQ(intn1,intn2);20bo