数据结构试验报告查找排序的应用.docx
《数据结构试验报告查找排序的应用.docx》由会员分享，可在线阅读，更多相关《数据结构试验报告查找排序的应用.docx（21页珍藏版）》请在冰点文库上搜索。
数据结构试验报告查找排序的应用
中原工学院
《数据结构》
实验报告
学院：
计算机学院
专业：
计算机科学与技术
班级：
计科112
姓名：
康岩岩
学号：
201100814220
指导老师：
高艳霞
2013-01-01
实验七查找、排序的应用
[问题描述]
对学生的基本信息进行管理。
[基本要求]
设计一个学生信息管理系统，学生对象至少要包含：
学号、姓名、性别、成绩1、成绩2、总成绩等信息。
要求实现以下功能：
1．总成绩要求自动计算；
2．查询：
分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）；
3.排序：
分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。
[算法设计]
首先，由于本次试验要求的是至少实现两个查找算法和两个排序算法，所以这在程序设计时就要考虑至少使用四个单独的表结构来储存数据。
当然，每张表中储存的数据对象都是一样的，只是顺序不同。
所以在一次输入时，就要同时有四次插入操作。
对与数据信息的查找，需要用到二叉平衡树树与哈希表，本次试验只用哈希表对学生姓名进行查找，对于hash表的构造，所使用的方法如下：
intHash（char*key）{
chark=key[0];
return（k*k）%MAX_SIZE;
}
即取关键字的首字母所对应的10进制ASCLL码，然后做平方后Mod数据最大容量。
进行学号的查找，所用的是二叉平衡排序树，二叉平衡排序树能尽可能的减少查找过程中数据的较，而由于学号储存形式为字符串，所以比较的依据就是对每位数进行字典顺序。
另外还需要实现排序算法。
我使用的折半插入排序法和二叉排序树插入排序。
即在数据的插入过程中就进行了排序。
[测试数据]
查找姓名（哈希查找）
查找学号（二叉平衡排序树）：
排序总成绩（二叉排序树插入排序）：
排序编程成绩（折半插入排序）
[附录（源代码）];
#include"stdafx.h"
#include
#include
usingnamespacestd;
//最大数据容量
#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;//平衡二叉排序树
typedefstructNode{
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）;
boolLT（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;iStudent*stu=（Student*）malloc（sizeof（Student））;
cout<<"输入第"<cout<<"姓名:
";
cin>>stu->stu_name;
cout<<"学号:
";
cin>>stu->stu_num;
cout<<"性别:
";
cin>>stu->sex;
cout<<"编程成绩:
";
cin>>stu->grade[0];
cout<<"英语成绩:
";
cin>>stu->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;//指向左孩子的右子树根
switch（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;
lc->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;
return1;
}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;
taller=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;
if（!
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;
return0;
}elseif（EQ（key,T->stu.grade[2]））{
p=T;
return1;
}elseif（LT（key,T->stu.grade[2]））{
returnSearchBitTree（T->lchild,key,T,p）;
}else{
returnSearchBitTree（T->rchild,key,T,p）;
}
}
intOrderBitTree（BitTreeT）{
if（T）{
if（OrderBitTree（T->lchild））{
if（T->stu.stu_num!
=NULL）{
showStuInfo（T->stu）;
if（OrderBitTree（T->rchild））{
return1;
}
}
}
return0;
}else{
return1;
}
}
/*
//创建表
intCreatStuHashtable（HashTable&H,intcount）{
H.count=0;
for（inti=0;iStudent*stu=（Student*）malloc（sizeof（Student*））;
cout<<"输入第"<cout<<"姓名:
";
cin>>stu->stu_num;
cout<<"学号:
";
cin>>stu->stu_name;
cout<<"性别:
";
cin>>stu->sex;
cout<<"编程成绩:
";
cin>>stu->grade[0];
cout<<"英语成绩:
";
cin>>stu->grade[1];
stu->grade[2]=stu->grade[0]+stu->grade[1];
InsertHash（H,*stu）;
}
return1;
}
*/
//判断两字符串是否相等，没有用算法，生配的
boolEQ（char*k1,char*k2）{
if（strcmp（k1,k2）==0）{
returntrue;
}
returnfalse;
}
boolLT（char*k1,char*k2）{
if（strcmp（k1,k2）<0）{
returntrue;
}
returnfalse;
}
boolEQ（intn1,intn2）{
if（n1==n2）{
returntrue;
}
returnfalse;
}
boolLT（intn1,intn2）{
if（n1returntrue;
}
returnfalse;
}
//计算关键字所对应的值
intHash（char*key）{
chark=key[0];
return（k*k）%MAX_SIZE;
}
intSearchHash（HashTableH,char*key,int&index,int&c）{
index=Hash（key）;
while（!
H.stu[index].stu_name&&!
EQ（key,H.stu[index].stu_name））{
index++;
c++;
}
//此时若查找成功
if（EQ（key,H.stu[index].stu_name））{
return1;
}
return0;
}
//插入操作
intInsertHash（HashTable&H,Studentstu）{
intindex=0;
intc=0;
if（SearchHash（H,stu.stu_name,index,c））{
return-1;
}elseif（cH.stu[index]=stu;
H.count++;
return1;
}else{
cout<<"错误!
!
需要从简哈希表!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
"<system（"pause"）;
exit（0）;
return0;
}
}
//打印学生信息
voidshowStuInfo（Studentstu）{
cout<<"姓名:
"<cout<<"学号:
"<cout<<"性别:
"<cout<<"编程成绩:
"<cout<<"英语成绩:
"<cout<<"总成绩:
"<cout<<"---------------------------\n";
}
int_tmain（intargc,_TCHAR*argv[]）
{
SqListlist;
list.length=0;
//hash表
HashTablehash;
hash.count=0;
//二叉排序树
BitTreetree=NULL;
//平衡二叉排序树
BSTreebstree=NULL;
intcount;
cout<<"请输入总人数:
";
cin>>count;
CreatTable（hash,tree,bstree,list,count）;
system（"cls"）;
while
（1）{
//查找功能
cout<<"1,查找姓名（哈希查找）"<cout<<"2,查找学号（二叉平衡树查找）"<//排序功能
cout<<"3,排序总成绩（二叉排序树插入排序）"<cout<<"4,排序编程成绩（折半插入排序）"<cout<<"5,退出:
"<<"\n\n";
intselect;
cout<<"选择操作:
";
cin>>select;
system（"cls"）;
if（select==1）{
charname[10];
cout<<"输入姓名:
";
cin>>name;
intindex=0,t=0;
Studentstu;
//intSearchHash（HashTableH,char*key,int&p,int&c）;//查找
SearchHash（hash,name,index,t）;
stu=hash.stu[index];
if（stu.stu_num!
=NULL）{
showStuInfo（stu）;
}else{
cout<<"没有找到学生信息!
"<}
}elseif（select==2）{
charnum[10];
cout<<"输入学号:
";
cin>>num;
Studentstu;
BSTreef=NULL,p=NULL;
if（SearchAVL（bstree,num,f,p））{
stu=p->stu;
showStuInfo（stu）;
}else{
cout<<"没有找到学生信息!
"<}
}elseif（select==3）{
OrderBitTree（tree）;
}elseif（select==4）{
Studentstu;
for（inti=0;istu=list.stu[i+1];
showStuInfo（stu）;
}
}else{
break;
}
cout<<"\n====================================\n"<}
free（tree）;
free（bstree）;
return0;
}
升级会员 