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

 PAGE \* MERGEFORMAT 20 中原工学院 《数据结构》 实验报告 学 院： 计算机学院 专 业：计算机科学与技术 班 级： 计科112 姓 名： 康岩岩 学 号： 201100814220 指导老师： 高艳霞 2013-01-01 实验七 查找、排序的应用 [问题描述] 　对学生的基本信息进行管理。 [基本要求] 设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能： 1．总成绩要求自动计算； 2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）； 3.排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。 [算法设计] 首先，由于本次试验要求的是至少实现两个查找算法和两个排序算法，所以这在程序设计时就??考虑至少使用四个单独的表结构来储存数据。当然，每张表中储存的数据对象都是一样的，只是顺序不同。所以在一次输入时，就要同时有四次插入操作。 对与数据信息的查找，需要用到二叉平衡树树与哈希表，本次试验只用哈希表对学生姓名进行查找，对于hash表的构造，所使用的方法如下： int Hash(char*key){ char k=key[0]; return (k*k)%MAX_SIZE; } 即取关键字的首字母所对应的10进制ASCLL码，然后做平方后Mod数据最大容量。 进行学号的查找，所用的是二叉平衡排序树，二叉平衡排序树能尽可能的减少查找过程中数据的较，而由于学号储存形式为字符串，所以比较的依据就是对每位数进行字典顺序。 另外还需要实现排序算法。我使用的折半插入排序法和二叉排序树插入排序。即在数据的插入过程中就进行了排序。 [测试数据] 查找姓名(哈希查找) 查找学号（二叉平衡排序树）： 排序总成绩（二叉排序树插入排序）： 排序编程成绩(折半插入排序) [附录(源代码)]; #include stdafx.h #include malloc.h #include iostream using namespace std; //最大数据容量 #define MAX_SIZE 30 #define LH 1 //左高 #define EH 0 //等高 #define RH -1 //右高 typedef struct{ char stu_name[10]; int sex; char stu_num[10]; //这个值是惟一的 int grade[3]; }Student; //学生对象 typedef struct{ Student stu[MAX_SIZE]; int count; }HashTable;//哈希表 typedef struct BitNode{ Student stu; struct BitNode *lchild,*rchild; }*BitTree;//二叉排序树 typedef struct BSTNode{ Student stu; int bf; struct BSTNode *lchild,*rchild; }*BSTree;//平衡二叉排序树 typedef struct Node{ Student stu[MAX_SIZE]; int length; }SqList;//折半表 //hash表的操作 int Hash(char*key); //计算hash值 int SearchHash(HashTable H,char*key,intp,intc);//查找 int InsertHash(HashTableH,Student stu);//插入 //二叉排序树的操作 int SearchBitTree(BitTree T,int key,BitTree f,BitTree p);//查找 int InsertBitTree(BitTree T,Student stu);//插入 int OrderBitTree(BitTree T);//中序遍历二叉排序树 //平衡二叉树的操作 bool SearchAVL(BSTree T,char*key,BSTree f,BSTreep);//查找 void R_Rotate(BSTree p);//右旋 void L_Rotate(BSTree p);//左旋 int InsertAVL(BSTreeT,Student stu,bool taller);//插入 void LeftBalance(BSTreeT); //左平