基于二叉排序树的高校分数查询系统

时间：2024-01-22 16:48:18

基于二叉排序树的高校分数查询系统

前述：该学期最后的数据结构的课程设计选题，于是记录在自己博客中，作为自己技术成长的点滴吧。

题目：高校最低录取分数线的查询

编程实现一个开放式的高校本科招生最低分数线的查询系统，供师生及家长等查询，高校自愿放入该校的信息，可能随时有高校加入。

要求实现的查询功能有：

  • 查询等于用户给定分数的高校
  • 查询大于（或小于）用户给定分数的高校
  • 查询最低录取分数线的用户给定的分数段中的高校

  以上就是老师给定题目中要求实现的功能，为了是程序整体更加完整，自己对高校使用部分做了一些功能添加，例如学校信息的增删改查等功能。

题目分析：

  该设计重要功能是查找，查找表为高校最低录取分数信息的集合。根据题意可知，该查找表中的元素个数可能随时增减，所以它是一个动态查找表，可采用树状结构保存。为了提高查询速度，可建立二叉排序树并在二叉排序树中实现查找。

程序的代码结构：

  • 头文件的引入以及结构体的定义 
     1 #include <string.h>
 2 #include <ctype.h>
 3 #include <malloc.h>
 4 #include <stdio.h>
 5 #include <stdlib.h>
 6 
 7 #define TRUE        1
 8 #define FALSE       0
 9 #define OK          1
10 #define ERROR       0
11 
12 typedef int Status;
13 
14 typedef struct node{
15     struct node *lchild;
16     struct node *rchild;
17     int grade;
18     char university[36];
19 }BiTreeNode, *BiTree;
20 
21 typedef struct element{
22     int grade;
23     char university[30];
24 }Information;

     

  • 创建节点 
    1 Status CreateBiTree(BiTree &T){
2     T=(BiTree)malloc(sizeof(BiTreeNode));
3     T->lchild = NULL;
4     T->rchild = NULL;
5     return OK; 
6 }

     

  • 高校信息的插入 
     1 Status InsertData(BiTree &T,Information mess){
 2     BiTree NT;
 3     if(T==NULL){
 4         CreateBiTree(T);
 5         T->grade=mess.grade;
 6         strcpy(T->university,mess.university);
 7     }else{
 8         if(mess.grade<T->grade){
 9             if(T->lchild==NULL){
10                 CreateBiTree(NT);
11                 T->lchild=NT;
12                 NT->grade=mess.grade;
13                 strcpy(NT->university,mess.university);
14             }else
15                 InsertData(T->lchild,mess);
16         }else{
17             if(T->rchild==NULL){
18                 CreateBiTree(NT);
19                 T->rchild=NT;
20                 NT->grade=mess.grade;
21                 strcpy(NT->university,mess.university);
22             }else
23                 InsertData(T->rchild,mess);
24         }
25     }
26     return OK;
27 }

     

  • 查找相应的学校，存在返回结构体指针T，否则返回NULL，其中FT为查找到节点T的父母节点，lr用来表明为其左右子树（0为左子树，1为右子树） 
     1 BiTree FindUniversity(BiTree T,BiTree &FT,Information mess,int &lr){
 2     BiTree BT=NULL;
 3     if(T->lchild){
 4         if(FindUniversity(T->lchild,FT,mess,lr))
 5             BT=FindUniversity(T->lchild,FT,mess,lr);
 6         if(strcmp(T->lchild->university,mess.university)==0){
 7             FT=T;
 8             lr=0;
 9         }
10     }
11     if(strcmp(T->university,mess.university)==0){
12         return T;
13     }
14     if(T->rchild){
15         if(FindUniversity(T->rchild,FT,mess,lr))
16             BT=FindUniversity(T->rchild,FT,mess,lr);
17         if(strcmp(T->rchild->university,mess.university)==0){
18             FT=T;
19             lr=1;
20         }
21     } 
22     return BT;
23 }

     

  • 删除学校  
     1 Status DeleteData(BiTree &T,Information mess){
 2     BiTree NT=NULL,FT=NULL,GT=NULL,LT=NULL;
 3     int lr=3;
 4     if(NT=FindUniversity(T,FT,mess,lr)){
 5         if(NT->lchild==NULL&&NT->rchild==NULL){
 6             free(NT);
 7             if(lr==0)
 8                 FT->lchild=NULL;
 9             else if(lr==1)
10                 FT->rchild=NULL;
11             else
12                 T=NULL;
13         }else if(NT->lchild==NULL){
14             if(lr==0)
15                 FT->lchild=NT->rchild;
16             else if(lr==1)
17                 FT->rchild=NT->rchild;
18             else
19                 T=NT->rchild;
20             free(NT);
21         }else if(NT->rchild==NULL){
22             if(lr==0)
23                 FT->lchild=NT->lchild;
24             else if(lr==1)
25                 FT->rchild=NT->lchild;
26             else
27                 T=NT->lchild;
28             free(NT);
29         }else{
30             LT=NT;
31             GT=NT->rchild;
32             while(GT->lchild){
33                 LT=GT;
34                 GT=GT->lchild;
35             }
36             if(GT->rchild&&LT==NT){
37                 LT->rchild=GT->rchild;
38                 NT->grade=GT->grade;
39                 strcpy(NT->university,GT->university);
40                 free(GT);
41             }else if(GT->rchild){
42                 LT->lchild=GT->rchild;
43                 NT->grade=GT->grade;
44                 strcpy(NT->university,GT->university);
45                 free(GT);
46             }else{
47                 NT->grade=GT->grade;
48                 strcpy(NT->university,GT->university);
49                 LT->lchild=NULL;
50                 free(GT);
51             }
52         }
53     }
54     return OK;
55 }

     

  • 查询学生需要的信息，根据stat数值完成相应操作  
     1 Status DisplayNeed(BiTree T,int stat,int score,int score_max){
 2     if(T->lchild)
 3         DisplayNeed(T->lchild,stat,score,score_max);
 4     switch(stat){
 5         case 1:{
 6             if(T->grade==score){
 7                 printf("学校：%30s\t分数线：%5d\n",T->university,T->grade);
 8             }
 9             break;
10         }
11         case 2:{
12             if(T->grade>score){
13                 printf("学校：%30s\t分数线：%5d\n",T->university,T->grade);
14             }
15             break;
16         }
17         case 3:{
18             if(T->grade<score){
19                 printf("学校：%30s\t分数线：%5d\n",T->university,T->grade);
20             }
21             break;
22         }
23         case 4:{
24             if(T->grade>=score&&T->grade<=score_max){
25                 printf("学校：%30s\t分数线：%5d\n",T->university,T->grade);
26             }
27             break;
28         }
29     }
30     if(T->rchild)
31         DisplayNeed(T->rchild,stat,score,score_max);
32     return OK;
33 }

     

  • 中序遍历整个二叉顺序树 
    1 Status InOrderTraverse(BiTree T){
2     if(T->lchild)
3         InOrderTraverse(T->lchild);
4     printf("学校：%30s\t分数线：%5d\n",T->university,T->grade);
5     if(T->rchild)
6         InOrderTraverse(T->rchild);
7     return OK;
8 }

     

  • 主函数 
      1 int main(){
  2     BiTree T,BT,FT;
  3     int Ch_one,Ch_two,score,score_min,score_max,lr,num;
  4     Information message,backmessage; 
  5     char universityName[16];
  6     T=NULL;
  7     BT=NULL;
  8     FT=NULL;
  9     lr=3;
 10     Ch_one=1;
 11     Ch_two=1;
 12     printf("高校分数查询系统 V1.0");
 13 
 14     while(Ch_one){
 15         printf("\n\n请输入相应序号进行操作！(输入0退出本系统，回车键表示确定)\n"); 
 16         printf("  1 学生使用\n  2 高校使用\n  请输入：");
 17         scanf("%d",&Ch_one);
 18         Ch_two=1;
 19         if(Ch_one==1){ 
 20             while(Ch_two){
 21                 if(T){
 22                     printf("    1 查询等于给定分数的高校\n    2 查询大于给定分数的高校\n    3 查询小于给定分数的高校\n");
 23                     printf("    4 查询最低录取分数线的给定的分数段中的高校\n    0 返回主菜单\n    请输入：");
 24                     num=0;
 25                     score_max=0;
 26                     scanf("%d",&Ch_two);
 27                 }else{
 28                     printf("\n院校数据不存在，请先对院校数据进行添加！\n");
 29                     Ch_two=0;
 30                 }
 31                     
 32                 switch(Ch_two){
 33                     case 0: break;
 34                     case 1:{
 35                         printf("    请输入给定的分数：");
 36                         scanf("%d",&score);
 37                         NumberGet(T,Ch_two,score,score_max,num);
 38                         if(num){
 39                             printf("\n共查询到高校%d个\n",num);
 40                             printf("--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--\n");
 41                             DisplayNeed(T,Ch_two,score,score_max);
 42                             printf("--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--\n\n");
 43                         }else
 44                             printf("\n未查询到结果！\n\n");
 45                         break;
 46                     }
 47                     case 2:{
 48                         printf("    请输入给定的分数：");
 49                         scanf("%d",&score);
 50                         NumberGet(T,Ch_two,score,score_max,num);
 51                         if(num){
 52                             printf("\n共查询到高校%d个\n",num);
 53                             printf("--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--\n");
 54                             DisplayNeed(T,Ch_two,score,score_max);
 55                             printf("--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--\n\n");
 56                         }else
 57                             printf("\n未查询到结果！\n\n");
 58                         
 59                         break;
 60                     }
 61                     case 3:{
 62                         printf("    请输入给定的分数：");
 63                         scanf("%d",&score);
 64                         NumberGet(T,Ch_two,score,score_max,num);
 65                         if(num){
 66                             printf("\n共查询到高校%d个\n",num);
 67                             printf("--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--\n");
 68                             DisplayNeed(T,Ch_two,score,score_max);
 69                             printf("--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--\n\n");
 70                         }else
 71                             printf("\n未查询到结果！\n\n");
 72                         break;
 73                     }
 74                     case 4:{
 75                         printf("    请输入给定的分数段的最小值："); 
 76                         scanf("%d",&score_min);
 77                         printf("    请输入给定的分数段的最大值："); 
 78                         scanf("%d",&score_max);
 79                         NumberGet(T,Ch_two,score_min,score_max,num);
 80                         if(num){
 81                             printf("\n共查询到高校%d个\n",num);
 82                             printf("--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--\n");
 83                             DisplayNeed(T,Ch_two,score_min,score_max);
 84                             printf("--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--\n\n");
 85                         }else
 86                             printf("\n未查询到结果！\n\n");
 87                         break;
 88                     }
 89                     default:
 90                         printf("输入错误！\n"); 
 91                 }
 92             } 
 93         }
 94         if(Ch_one==2){
 95             while(Ch_two){
 96                 printf("    1 高校信息加入\n    2 高校分数修改\n    3 高校名称修改\n");
 97                 printf("    4 高校申请退出\n    5 高校信息展示\n    0 返回主菜单\n    请输入：");
 98                 scanf("%d",&Ch_two);
 99                 switch(Ch_two){
100                     case 0: break;
101                     case 1:{
102                         printf("    请输入学校名称：");
103                         scanf("%s",universityName);
104                         strcpy(message.university,universityName);
105                         printf("    请输入最低分数线：");
106                         scanf("%d",&message.grade);
107                         if(T&&FindUniversity(T,FT,message,lr)){
108                             DeleteData(T,message);
109                             InsertData(T,message);
110                             printf("\n该高校已存在！已将新数据作为数据源进行修改\n\n");
111                         } 
112                         else{
113                             InsertData(T,message);
114                             printf("\n信息添加成功！\n\n");
115                         }
116                         break;
117                     }
118                     case 2:{
119                         printf("    请输入学校名称：");
120                         scanf("%s",universityName);
121                         strcpy(message.university,universityName);
122                         printf("    请输入修改后的最低分数线：");
123                         scanf("%d",&message.grade);
124                         if(T&&FindUniversity(T,FT,message,lr)){
125                             DeleteData(T,message);
126                             InsertData(T,message);
127                             printf("\n分数线修改成功！\n\n");
128                         }else{
129                             InsertData(T,message);
130                             printf("\n之前该学校不存在，现已将数据插入数据库！\n\n");
131                         }
132                             
133                         break;
134                     }
135                     case 3:{
136                         printf("    请输入原学校名称：");
137                         scanf("%s",universityName);
138                         strcpy(message.university,universityName);
139                         printf("    请输入修改后的学校名称：");
140                         scanf("%s",universityName);
141                         strcpy(backmessage.university,universityName);
142                         if(T&&FindUniversity(T,FT,message,lr)&&!FindUniversity(T,FT,backmessage,lr)){
143                             BT=FindUniversity(T,FT,message,lr);
144                             strcpy(BT->university,universityName);
145                             printf("\n学校名称修改成功！\n\n"); 
146                         }else
147                             printf("\n该学校不存在或已包含更名后的学校！\n\n"); 
148                         break;
149                     }
150                     case 4:{
151                         printf("    请输入申请退出的学校名称：");
152                         scanf("%s",universityName);
153                         strcpy(message.university,universityName);
154                         if(T&&FindUniversity(T,FT,message,lr)){
155                             DeleteData(T,message);
156                             printf("\n该校已退出分数查询系统！\n\n"); 
157                         }else
158                             printf("\n该学校不存在！\n\n"); 
159                         
160                         break;
161                     }
162                     case 5:{
163                         if(T){
164                             printf("\n--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--\n");
165                             InOrderTraverse(T);
166                             printf("--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--\n\n");
167                         }else
168                             printf("\n数据为空！\n\n");
169                         
170                         break;
171                     } 
172                     default:
173                         printf("\n输入错误！\n\n");
174                 }
175             }
176         }
177     }
178     return 0;
179 }

     

程序的运行结果：

高校使用：

  • 学校信息添加
  • 学校名称修改
  • 学校分数线修改
  • 学校申请退

该部分的所有数据均随时产生，与实际高校录取线并无直接关系，仅仅用来程序演示。

 

学生使用：

  • 根据特定分数查询相应学校
  • 查询大于给定分数的高效
  • 查询小于给定分数的高效
  • 查询给定分数段中的高校

当且仅当院校数据存在时才可进行数据查询。

 

总结

 本次程序整体的数据结构基于二叉排序树建立，以分数为判断依据，来决定该高校在改二叉顺序数中的存储位置，这就要求我们对该结构的熟练结构，以便于实现数据的增删查改，其中相对于重要的是数据的删除，删除一个节点时出现的情况多种多样，相对于较难以处理的就是该节点有左右子树均存在时，这时需要查找一个相对与接近删除节点的信息用来替代此节点。用转移的思想，把复杂的节点转化为相对简单的节点来进行处理。通过这次课程设计，认识到，数据结构的重要性，我们应该认真学习数据结构，体会其中的思想和逻辑处理。

相关文章