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

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

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

3、序树能尽可能的减少查找过程中数据的较，而由于学号储存形式为字符串，所以比较的依据就是对每位数进行字典顺序。另外还需要实现排序算法。我使用的折半插入排序法和二叉排序树插入排序。即在数据的插入过程中就进行了排序。 测试数据查找姓名(哈希查找)查找学号（二叉平衡排序树）：排序总成绩（二叉排序树插入排序）：排序编程成绩(折半插入排序)附录(源代码);#include stdafx.h#include #include using namespace std;/最大数据容量#define MAX_SIZE 30#define LH 1 /左高#define EH 0 /等高#define RH -1 /

4、右高typedef struct char stu_name10; int sex; char stu_num10; /这个值是惟一的 int grade3;Student; /学生对象typedef struct Student stuMAX_SIZE; int count;HashTable;/哈希表typedef struct BitNode Student stu; struct BitNode *lchild,*rchild;*BitTree;/二叉排序树typedef struct BSTNode Student stu; int bf; struct BSTNode *lchil

5、d,*rchild;*BSTree;/平衡二叉排序树typedef struct Node Student stuMAX_SIZE; int length;SqList;/折半表/hash表的操作int Hash(char*key); /计算hash值int SearchHash(HashTable H,char*key,int&p,int&c);/查找int InsertHash(HashTable&H,Student stu);/插入/二叉排序树的操作int SearchBitTree(BitTree T,int key,BitTree f,BitTree &p);/查找int Inser

6、tBitTree(BitTree &T,Student stu);/插入int OrderBitTree(BitTree T);/中序遍历二叉排序树/平衡二叉树的操作bool SearchAVL(BSTree T,char*key,BSTree f,BSTree&p);/查找void R_Rotate(BSTree &p);/右旋void L_Rotate(BSTree &p);/左旋int InsertAVL(BSTree&T,Student stu,bool &taller);/插入void LeftBalance(BSTree&T); /左平衡void RightBalance(BSTr

7、ee&T);/右平衡/创建总表 传入参数为 哈希表，二叉排序树，二叉平衡排序树，折半查找表，总量 int CreatTable(HashTable&H,BitTree&T,BSTree&BT,SqList&L,int count);/显示学生信息void showStuInfo(Student stu);/比较函数bool EQ(char*k1,char*k2);bool LT(char*k1,char*k2);bool EQ(int n1,int n2);bool LT(int n1,int n2);/折半插入排序void BInsertSort(SqList&L) for(int i=2;

8、i=L.length;i+) L.stu0=L.stui; /暂存到零元 int low=1; int high=i-1; while(low=high+1;-j)/对插入点以后的数据进行右移 L.stuj+1=L.stuj; L.stuhigh+1=L.stu0;/插入 /创建总表int CreatTable(HashTable&H,BitTree&T,BSTree&BT,SqList&L,int count) for(int i=0;icount;i+) Student*stu=(Student*)malloc(sizeof(Student); cout输入第i+1个学生的信息endl;

9、coutstu-stu_name; coutstu-stu_num; coutstu-sex; coutstu-grade0; coutstu-grade1; stu-grade2=stu-grade0+stu-grade1; /计算总成绩 InsertHash(H,*stu);/加入哈希表 InsertBitTree(T,*stu);/加入二叉排序树 bool flag=false; InsertAVL(BT,*stu,flag);/加入二叉平衡排序树 L.stui+1=*stu;/加入折半排序表 L.length+; BInsertSort(L); /插入后进行排序 return 1;/左

10、平衡操作void LeftBalance(BSTree&T) BSTNode* lc=T-lchild; /lc指向左子树 BSTNode* rd; switch(lc-bf) case LH: T-bf=lc-bf=EH; /新节点插入T的左孩子的左子树，右旋 R_Rotate(T); break; case RH: /新节点插入T的左孩子的右子树，右旋 rd=lc-lchild; /指向左孩子的右子树根 switch(rd-bf) /修改平衡因子 case LH: T-bf=RH; lc-bf=EH; break; case EH: T-bf=lc-bf=EH; break; case R

11、H: T-bf=EH; lc-bf=LH; break; rd-bf=EH; L_Rotate(T-lchild); /对T左子树做左平衡处理 R_Rotate(T); /右旋 break; void RightBalance(BSTree&T) BSTNode* lc=T-rchild; BSTNode* rd; switch(lc-bf) case LH: rd=lc-lchild; switch(rd-bf) case LH: T-bf=EH; lc-bf=LH; break; case EH: T-bf=lc-bf=EH; break; case RH: T-bf=RH; lc-bf=

12、EH; break; rd-bf=EH; R_Rotate(T-rchild); L_Rotate(T); break; case RH: T-bf=lc-bf=EH; L_Rotate(T); break; /右旋void R_Rotate(BSTree &p) BSTNode*lc; lc=p-lchild; p-lchild=lc-rchild; lc-lchild=p; p=lc;/左旋void L_Rotate(BSTree &p) BSTNode*rc; rc=p-rchild; p-rchild=rc-lchild; rc-lchild=p; p=rc;/查找平衡二叉树bool

13、SearchAVL(BSTree T,char*key,BSTree f,BSTree&p) if(!T) p=f; return 0; else if(EQ(key,T-stu.stu_num) p=T; return 1; else if(LT(key,T-stu.stu_num) return SearchAVL(T-lchild,key,T,p); else return SearchAVL(T-rchild,key,T,p); /插入到平衡二叉树int InsertAVL(BSTree&T,Student stu,bool &taller) if(!T) T=(BSTree)mall

14、oc(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; return 0; if(LT(stu.stu_num,T-stu.stu_num) if(!InsertAVL(T-lchild,stu,taller) return 0; if(taller) switch(T-bf) case LH: LeftBalance(T); taller=false; break; case EH: T-bf

15、=LH; taller=true; break; case RH: T-bf=EH; taller=false; break; else if(!InsertAVL(T-rchild,stu,taller)return 0; if(taller) switch(T-bf) case LH: T-bf=EH; taller=false; break; case EH: T-bf=RH; taller=true; break; case RH: RightBalance(T); taller=false; break; return 1;/插入二叉排序树节点int InsertBitTree(Bi

16、tTree &T,Student stu) BitTree p=NULL,f=NULL; BitNode*s; if(!SearchBitTree(T,stu.grade2,f,p) s=(BitTree)malloc(sizeof(BitNode); s-stu=stu; s-lchild=s-rchild=NULL; if(!p) T=s; else if(LT(stu.grade2,p-stu.grade2) p-lchild=s; else p-rchild=s; return true; else return false; /查找二叉排序树int SearchBitTree(Bit

17、Tree T,int key,BitTree f,BitTree &p) if(!T) p=f; return 0; else if(EQ(key,T-stu.grade2) p=T; return 1; else if(LT(key,T-stu.grade2) return SearchBitTree(T-lchild,key,T,p); else return SearchBitTree(T-rchild,key,T,p); int OrderBitTree(BitTree T) if(T) if(OrderBitTree(T-lchild) if(T-stu.stu_num!=NULL)

18、 showStuInfo(T-stu); if(OrderBitTree(T-rchild) return 1; return 0; else return 1; /*/创建表int CreatStuHashtable(HashTable&H,int count)H.count=0;for(int i=0;icount;i+)Student*stu=(Student*)malloc(sizeof(Student*);cout输入第i+1个学生的信息endl;coutstu-stu_num;coutstu-stu_name;coutstu-sex;coutstu-grade0;coutstu-g

19、rade1;stu-grade2=stu-grade0+stu-grade1;InsertHash(H,*stu);return 1;*/判断两字符串是否相等，没有用算法，生配的bool EQ(char*k1,char*k2) if(strcmp(k1,k2)=0) return true; return false;bool LT(char*k1,char*k2) if(strcmp(k1,k2)0) return true; return false;bool EQ(int n1,int n2) if(n1=n2) return true; return false;bool LT(int

20、 n1,int n2) if(n1n2) return true; return false;/计算关键字所对应的值int Hash(char*key) char k=key0; return (k*k)%MAX_SIZE;int SearchHash(HashTable H,char*key,int&index,int&c) index=Hash(key); while(!H.stuindex.stu_name&!EQ(key,H.stuindex.stu_name) index+; c+; /此时若查找成功 if(EQ(key,H.stuindex.stu_name) return 1;

21、return 0;/插入操作int InsertHash(HashTable&H,Student stu) int index=0; int c=0; if(SearchHash(H,stu.stu_name,index,c) return -1; else if(cMAX_SIZE) H.stuindex=stu; H.count+; return 1; else cout错误!需要从简哈希表!endl; system(pause); exit(0); return 0; /打印学生信息void showStuInfo(Student stu) cout姓名:stu.stu_nameendl

22、; cout学号:stu.stu_numendl; cout性别:stu.sexendl; cout编程成绩:stu.grade0endl; cout英语成绩:stu.grade1endl; cout总成绩:stu.grade2endl; cout-n;int _tmain(int argc, _TCHAR* argv) SqList list; list.length=0; /hash表 HashTable hash; hash.count=0; /二叉排序树 BitTree tree=NULL; /平衡二叉排序树 BSTree bstree=NULL; int count; coutcou

23、nt; CreatTable(hash,tree,bstree,list,count); system(cls); while(1) /查找功能 cout1,查找姓名(哈希查找)endl; cout2,查找学号(二叉平衡树查找)endl; /排序功能 cout3,排序总成绩(二叉排序树插入排序)endl; cout4,排序编程成绩(折半插入排序)endl; cout5,退出:nn; int select; coutselect; system(cls); if(select=1) char name10; coutname; int index=0,t=0; Student stu; /int

24、 SearchHash(HashTable H,char*key,int&p,int&c);/查找 SearchHash(hash,name,index,t); stu=hash.stuindex; if(stu.stu_num!=NULL) showStuInfo(stu); else cout没有找到学生信息!endl; else if(select=2) char num10; coutnum; Student stu; BSTree f=NULL,p=NULL; if(SearchAVL(bstree,num,f,p) stu=p-stu; showStuInfo(stu); else cout没有找到学生信息!endl; else if(select=3) OrderBitTree(tree); else if(select=4) Student stu; for(int i=0;ilist.length;i+) stu=list.stui+1; showStuInfo(stu); else break; coutn=nendl; free(tree); free(bstree); return 0;