数据结构课程设计-学生成绩查询系统.doc

数据结构课程设计报告学 号姓 名班 级计-143班指导教师安徽工业大学计算机学院2016年6月目 录课题一 学生成绩查询系统2一、问题描述2二、设计思路2三、数据结构定义2四、系统功能模块介绍3五、程序清单3六、运行及调试分析9七、课程设计总结11课题二 马的遍历 12一、问题描述12二、设计要求12三、分析与实现12四、数据结构定义12五、系统功能模块分析13六、程序清单13七、运行及调试分析17八、课程设计总结18课题一 学生成绩查询系统一、问题描述编写程序完成学生成绩记录的查询。学生基本情况学 号姓 名成绩99070101李 军98.599070102王颜霞8699070103孙 涛5699070104单晓宏9699070105张华8399070106李小明7299070107陈小婷98 若按学号进行顺序查找，例如：输入99070103，则输出 56 。 按学号排序后对学号进行折半查找。 随机输入以学号为关键字的学生信息并构建二叉排序树，对学号进行二叉排序树查找。二、设计思路1创建学生信息结构体；2. 初始化线性表，存入学生信息；3. 通过顺序查找实现根据学号进行顺序查找需要得到的学生的信息；4. 按学号对学生信息进行排序，通过折半查找从排序后的学号中找到要找的学生信息；5. 初始化二叉树，以学号为关键字构建二叉树，通过中序遍历二叉树，对学号进行二叉排序树查找，得到相应学生的成绩信息。三、数据结构定义1.宏定义 #define size 100 /*最大学生数*/2.students Init()初始化构造一个空线性表，void input(students student,long num1,char name1,float grade1)函数输入学生信息；3. int shunxu(students student,long num00)函数按学号顺序查找得到相应学生姓名和成绩；4. void paixu(students student)函数按学号进行排序，int midsearch(students student,long num0)函数对学号进行折半查找；5. bintree Init_tree()函数初始化二叉树，void Insertbintree(bintree *t,long k,char name,float grade)函数进行排序二叉树插入，void search(bintree t)函数进行中序遍历二叉树，bintree bintreesearch(bintree t,long k)函数对二叉排序树查找。四、系统功能模块介绍开始输入指令1-4输入学生信息（学号、姓名、成绩）按学号进行顺序查找按学号排序后，对学号进行折半查找构建二叉排序树， 对学号进行二叉树查找是否继续？结束 1 2 3 4 是（1） 否（0）五、程序清单#include #include #include #define size 100typedef struct node long num; /*学号*/char name10; /*学生姓名*/float grade; /*成绩*/message;typedef struct node2 message numbersize;int length;*students;typedef struct node3 long key;char name10;float grade; struct node3 *lchild; struct node3 *rchild;*bintree;/*线性表初始化*/students Init() students student; student=(students)malloc(sizeof(node2); student-length=-1; return student;/*插入学生信息*/void input(students student,long num1,char name1,float grade1) student-length+; student-numberstudent-length.num=num1; strcpy(,name1); student-numberstudent-length.grade=grade1;/*顺序查找*/int shunxu(students student,long num00) students s; int i; s=student; for(i=0;ilength;i+) if(s-numberi.num=num00) printf(此名为%s的成绩是:%.2fn,,s-numberi.grade); return 1; return 0;/*按学号排序*/void paixu(students student) int i,j;long t;for(j=0;jlength;j+)for(i=0;ilength-j-1;i+) if(student-numberi.numstudent-numberi+1.num)t=student-numberi.num;student-numberi.num=student-numberi+1.num;student-numberi+1.num=t;/*折半查找*/int midsearch(students student,long num0) int low=0; int high; int mid;high=student-length;while(lownumbermid.num=num0) return (mid);else if(student-numbermid.numnum0) high=mid-1;else low=mid+1;return (-1);/*初始化二叉树*/bintree Init_tree()bintree t;t=NULL;return t;/*排序二叉树插入*/void Insertbintree(bintree *t,long k,char name,float grade) bintree p;if(*t=NULL) p=(bintree)malloc(sizeof(node3);p-key=k;strcpy(p-name,name);p-grade=grade;p-lchild=p-rchild=NULL;*t=p;else if(kkey) Insertbintree(&(*t)-lchild,k,name,grade);else Insertbintree(&(*t)-rchild,k,name,grade);/*中序遍历树*/void search(bintree t) if(t) search(t-lchild); printf(%ldn,t-key); search(t-rchild);/*对二叉排序树查找*/bintree bintreesearch(bintree t,long k)bintree p;p=t;if(p=NULL) return NULL;if(p-key=k) return p;if(p-keyk)bintreesearch(p-lchild,k);elsebintreesearch(p-rchild,k);void main() int i,n=7,s,p; long num0,o; char name010; float grade0=0; bintree b,b1; students student; student=Init(); b=Init_tree(); do printf( *n); printf( * *n); printf( * 学生成绩查询系统 *n); printf( * 1.添加学生基本情况 *n); printf( * 2.按学号进行顺序查找 *n); printf( * 3.排序后折半查找 *n); printf( * 4.建立二叉排序树并查找 *n); printf( * *n); printf( *n); printf(请输入相应序号:); scanf(%d,&s); switch(s) case 1: printf(请输入7位学生的学号姓名成绩（例如：001 李军 100）n); for(i=0;inumberi.num); break; case 4: for(i=0;ilength+1;i+) Insertbintree(&b,student-numberi.num,,student-numberi.grade); if(i=student-length+1) printf(插入完成！n); search(b); printf(请输入需要查询的学号：); scanf(%ld,&o); b1=bintreesearch(b,o); printf(学号为%d的%s学生的成绩为：%.2fn,b1-key,b1-name,b1-grade); break; default: printf(输入了无效字符！n);break; printf(n是否继续？（1继续，0结束）：); scanf(%d,&p); system(cls); while(p); printf(程序结束！n);六、运行及调试分析1.选择指令1，输入表格中的学生信息2.选择1继续执行其他功能，选择指令2按学号进行顺序查找3.指令3进行折半查找4.指令4实现二叉树的建立，查找所要找的学号对应的学生信息5.选择0结束程序七、课程设计总结我会选择这个课题是因为这个课题和之前c语言课程设计做的学生信息管理系统类似，觉得做起来会相对容易。但是，当我开始做的时候却不知道从哪开始，只好在图书馆查资料。在这个实验中，我对于二叉树的排序掌握不够，因此，在后面的复习中，我需要在这上面多花点时间。课题二 马的遍历一、 问题描述在中国象棋棋盘上，对任一位置上放置的一个马，均能选择一个合适的路线，使得该棋子能按象棋的规则不重复地走过棋盘上的每一位置。 二、 设计要求1依次输出所走过的各位置的坐标。2最好能画出棋盘的图形形式，并在其上动态地标注行走过程。三、分析与实现马踏棋盘问题，是指将马随机放在中国象棋的9*10棋盘的某个方格中，马按走棋规则（马走日字）进行移动。要求每个方格只进入一次，走遍棋盘上全部90个方格。由用户自行指定一个马的初始位置，求出马的行走路线，并按照求出的行走路线的顺序，将数字1、2、90依次填入9*10的方阵并输出。从用户给出的初始位置开始判断，按照顺时针顺序，每次产生一个新的结点，并验证此路点的可用性，需要考虑的是当前路点是否超出棋盘范围和此路点是否走过。如果新路点可用，则入栈，并执行下一步，重复进行如上步骤，每次按照已走路点的位置生成新路点。如果一个路点的可扩展路点数为0，进行回溯，直到找到一个马能踏遍棋盘的行走路径并输出。四、 数据结构定义1.本课题使用的数据结构是栈，利用顺序栈来实现。2.所用到的函数有：void Init()棋盘初始化函数void PushStack(HorsePoint positon)入栈函数HorsePoint PopStack()出栈函数HorsePoint GetInitPoint()用于输入horse的起始坐标HorsePoint GetNewPoint(HorsePoint *parent) 是产生新结点函数void CalcPoint(HorsePoint hh) 是计算路径的函数void PrintChess()用于输出以9*10矩阵的形式输出运行结果 五、 系统功能模块介绍开始输入坐标(x,y)是否能踏遍棋盘？按顺序输出马踏过的点输出：此时不能踏遍棋盘上所有的点结束 是 否六、 程序清单#includestdio.h#define MAX1 8 /*横格数最大值*/#define MAX2 8 /*纵格数最大值*/#define MAXLEN 64 /*棋盘总格数*/#define INVALIDDIR -1 /*8步可走的方向*/#define MAXDIR 8 /*下一步可走的方向*/typedef structint x; /*表示横坐标*/int y; /*表示纵坐标*/int d; /*表示移动方向*/HorsePoint; HorsePoint ChessPathMAXLEN; /*模拟路径栈*/int count; /*入栈结点个数*/int ChessBoardMAX1MAX2; /*模拟棋盘数组*/void Init() /*棋盘初始化函数*/int i,j;for(i=0;iMAX1;i+)for(j=0;jMAX2;j+)ChessBoardij=0; /*棋盘格均初始化为0，表示没走过*/ for(i=0;i=MAX1|positon.y=MAX2|positon.x0|positon.yd=parent-d+; /*上一结点能走的方向*/for(i=parent-d;ix+tryxi; /*试探新结点的可走方向*/newpoint.y=parent-y+tryyi;if(newpoint.x=0&newpoint.y=0&ChessBoardnewpoint.xnewpoint.y=0)parent-d=i; /*上一结点可走的方向*/ChessBoardnewpoint.xnewpoint.y=1; /*标记已走过*/return newpoint;parent-d=INVALIDDIR;return newpoint;void CalcPoint(HorsePoint hh) /*计算路径的函数*/HorsePoint npositon;HorsePoint *ppositon;Init(); /*调用初始化函数*/ppositon=&hh;PushStack(*ppositon);while(!(count=0|count=MAXLEN) /*当路径栈不空或不满时*/ppositon=&ChessPathcount-1; /*指针指向栈*/npositon=GetNewPoint(ppositon); /*产生新结点*/if(ppositon-d!=INVALIDDIR) /*可以往下走*/ChessPathcount-1.d=ppositon-d;PushStack(npositon);elsePopStack();void PrintChess() /*以8*8矩阵的形式输出运行结果*/int i,j;int stateMAX1MAX2; /*stateij为棋盘上(i,j)点被踏过的次序*/int step=0; /*行走步数初始化*/HorsePoint positon;if(c