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

中原工学院《数据结构》实验报告学院：计算机学院专业：计算机科学与技术班级：计科112姓名：康岩岩学号：201100814220指导老师：高艳霞2013-01-012实验七查找、排序的应用[问题描述]对学生的基本信息进行管理。[基本要求]设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能：1．总成绩要求自动计算；2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）；3.排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。[算法设计]首先，由于本次试验要求的是至少实现两个查找算法和两个排序算法，所以这在程序设计时就要考虑至少使用四个单独的表结构来储存数据。当然，每张表中储存的数据对象都是一样的，只是顺序不同。所以在一次输入时，就要同时有四次插入操作。对与数据信息的查找，需要用到二叉平衡树树与哈希表，本次试验只用哈希表对学生姓名进行查找，对于hash表的构造，所使用的方法如下：intHash(char*key){chark=key[0];return(k*k)%MAX_SIZE;}即取关键字的首字母所对应的10进制ASCLL码，然后做平方后Mod数据最大容量。进行学号的查找，所用的是二叉平衡排序树，二叉平衡排序树能尽可能的减少查找过程中数据的较，而由于学号储存形式为字符串，所以比较的3依据就是对每位数进行字典顺序。另外还需要实现排序算法。我使用的折半插入排序法和二叉排序树插入排序。即在数据的插入过程中就进行了排序。[测试数据]查找姓名(哈希查找)查找学号（二叉平衡排序树）：4排序总成绩（二叉排序树插入排序）：排序编程成绩(折半插入排序)5[附录(源代码)];#includestdafx.h#includemalloc.h#includeiostreamusingnamespacestd;//最大数据容量#defineMAX_SIZE30#defineLH1//左高#defineEH0//等高#defineRH-1//右高typedefstruct{charstu_name[10];intsex;charstu_num[10];//这个值是惟一的intgrade[3];}Student;//学生对象typedefstruct{Studentstu[MAX_SIZE];intcount;}HashTable;//哈希表typedefstructBitNode{Studentstu;structBitNode*lchild,*rchild;}*BitTree;//二叉排序树typedefstructBSTNode{Studentstu;intbf;structBSTNode*lchild,*rchild;}*BSTree;//平衡二叉排序树6typedefstructNode{Studentstu[MAX_SIZE];intlength;}SqList;//折半表//hash表的操作intHash(char*key);//计算hash值intSearchHash(HashTableH,char*key,int&p,int&c);//查找intInsertHash(HashTable&H,Studentstu);//插入//二叉排序树的操作intSearchBitTree(BitTreeT,intkey,BitTreef,BitTree&p);//查找intInsertBitTree(BitTree&T,Studentstu);//插入intOrderBitTree(BitTreeT);//中序遍历二叉排序树//平衡二叉树的操作boolSearchAVL(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(HashTable&H,BitTree&T,BSTree&BT,SqList&L,intcount);//显示学生信息voidshowStuInfo(Studentstu);//比较函数boolEQ(char*k1,char*k2);boolLT(char*k1,char*k2);boolEQ(intn1,intn2);7boolLT(intn1,intn2);//折半插入排序voidBInsertSort(SqList&L){for(inti=2;i=L.length;i++){L.stu[0]=L.stu[i];//暂存到零元intlow=1;inthigh=i-1;while(low=high){intm=(low+high)/2;//此处折半//如果插入点在底区if(LT(L.stu[0].grade[0],L.stu[m].grade[0])){high=m-1;}else{//如果插入点在高区区low=m+1;}}for(intj=i-1;j=high+1;--j){//对插入点以后的数据进行右移L.stu[j+1]=L.stu[j];}L.stu[high+1]=L.stu[0];//插入}}//创建总表intCreatTable(HashTable&H,BitTree&T,BSTree&BT,SqList&L,intcount){for(inti=0;icount;i++){Student*stu=(Student*)malloc(sizeof(Student));cout输入第i+1个学生的信息endl;cout姓名:;cinstu-stu_name;cout学号:;cinstu-stu_num;8cout性别:;cinstu-sex;cout编程成绩:;cinstu-grade[0];cout英语成绩:;cinstu-grade[1];stu-grade[2]=stu-grade[0]+stu-grade[1];//计算总成绩InsertHash(H,*stu);//加入哈希表InsertBitTree(T,*stu);//加入二叉排序树boolflag=false;InsertAVL(BT,*stu,flag);//加入二叉平衡排序树L.stu[i+1]=*stu;//加入折半排序表L.length++;BInsertSort(L);//插入后进行排序}return1;}//左平衡操作voidLeftBalance(BSTree&T){BSTNode*lc=T-lchild;//lc指向左子树BSTNode*rd;switch(lc-bf){caseLH:T-bf=lc-bf=EH;//新节点插入T的左孩子的左子树，右旋R_Rotate(T);break;caseRH://新节点插入T的左孩子的右子树，右旋rd=lc-lchild;//指向左孩子的右子树根9switch(rd-bf){//修改平衡因子caseLH:T-bf=RH;lc-bf=EH;break;caseEH:T-bf=lc-bf=EH;break;caseRH:T-bf=EH;lc-bf=LH;break;}rd-bf=EH;L_Rotate(T-lchild);//对T左子树做左平衡处理R_Rotate(T);//右旋break;}}voidRightBalance(BSTree&T){BSTNode*lc=T-rchild;BSTNode*rd;switch(lc-bf){caseLH:rd=lc-lchild;switch(rd-bf){caseLH:T-bf=EH;lc-bf=LH;break;caseEH:T-bf=lc-bf=EH;break;caseRH:T-bf=RH;10lc-bf=EH;break;}rd-bf=EH;R_Rotate(T-rchild);L_Rotate(T);break;caseRH:T-bf=lc-bf=EH;L_Rotate(T);break;}}//右旋voidR_Rotate(BSTree&p){BSTNode*lc;lc=p-lchild;p-lchild=lc-rchild;lc-lchild=p;p=lc;}//左旋voidL_Rotate(BSTree&p){BSTNode*rc;rc=p-rchild;p-rchild=rc-lchild;rc-lchild=p;p=rc;}//查找平衡二叉树boolSearchAVL(BSTreeT,char*key,BSTreef,BSTree&p){if(!T){p=f;return0;}elseif(EQ(key,T-stu.stu_num)){p=T;11return1;}elseif(LT(key,T-stu.stu_num)){returnSearchAVL(T-lchild,key,T,p);}else{returnSearchAVL(T-rchild,key,T,p);}}//插入到平衡二叉树intInsertAVL(BSTree&T,Studentstu,bool&taller){if(!T){T=(BSTree)malloc(sizeof(BSTNode));T-stu=stu;T-lchild=T-rchild=NULL;T-bf=EH;taller=true;}else{if(EQ(stu.stu_num,T-stu.stu_num)){taller=false;return0;}if(LT(stu.stu_num,T-stu.stu_num)){if(!InsertAVL(T-lchild,stu,taller)){return0;}if(taller){switch(T-bf){caseLH:LeftBalance(T);taller=false;break;caseEH:T-bf=LH;taller=true;break;caseRH:T-bf=EH;12taller=false;break;}}}else{if(!InsertAVL(T-rchild,stu,taller)){return0;}if(taller){switch(T-bf){caseLH:T-bf=EH;taller=false;break;caseEH:T-bf=RH;taller=true;break;caseRH:RightBalance(T);taller=false;break;}}}}return1;}//插入二叉排序树节点intInsertBitTree(BitTree&T,Studentstu){BitTreep=NULL,f=NULL;BitNode*s;if(!SearchBitTree(T,stu.grade[2],f,p)){s=(BitTree)malloc(sizeof(BitNode));s-stu=stu;s-lchild=s-rchild=NULL;13if(!p){T=s;}elseif(LT(stu.grade[2],p-stu.grade[2])){p-lchild=s;}else{p-rchild=s;}returntrue;}else{returnfalse;}}//查找二叉排序树intSearchBitTree(BitTreeT,intkey,BitTreef,BitTree&p){if(!T){p=f;re