《李士鹏组实验报告》由会员分享，可在线阅读，更多相关《李士鹏组实验报告（21页珍藏版）》请在金锄头文库上搜索。
1、 安阳师范学院 数据结构课外实践 数据结构课外实践报告 项 目 名 称: 学生数据结构成绩管理系统 所 在 班 级: 2012级软件工程（java1）班 小 组 成 员：李士鹏 谷亚宁 李明浩 黄智 指 导 教 师：刘运通 起 止 时 间：第17周 项目基本信息项目名称学生数据结构成绩管理系统项目简介(1)学生信息及成绩的录入要求包括的学生信息有：学号、姓名、性别、出生日期、数据结构、线性代数、概率统计成绩（至少录入10名以上学生）所录入的学生按学号散列存储（散列函数为：学号%5 取整，如 1002%5 =2），采用拉链法解决冲突。 (2)学生成绩的查询要求根据提供的学号完成学生成绩的查询（必
2、须采用哈希查找） (3)学生成绩的分段统计和排序输出统计出各分数段学生人数（60分以下，6070，7180，.)小组成员李士鹏 谷亚宁 李明浩 黄智任务分工李士鹏：数据录入和查询谷亚宁：数据的统计和排序李明浩：界面规划和整理黄智 ：函数调用的调试课外实践评定成绩记录指导教师意见系统完成情况：优 良 中 差报告完成情况：优 良 中 差答辩评定成绩团队整体成绩：成员成绩李士鹏谷亚宁李明浩黄智综 合 成 绩一.实验目的 通过学习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、编码集成以及调试分析，熟练掌握数据结构的选择、设计、实现、以及操作方法，为进一步的开发应用打好基础。二.
3、问题描述实现功能：学生相关信息的输入、输出、查找、读入、显示、保存、排序、退出。三.需求分析 该程序所做的工作是对学生的成绩的管理，为师生进行学生成绩的记录、查询提供方便。此程序规定： 1.在成绩录入是，姓名为10个字母以内的字符串；各科成绩为整形；学号长整型，性别和出生日期为字符型； 2.程序的输出信息主要为：输出学生的各科成绩及排序统计学生相关成绩数据；3. 程序的功能主要包括：学生本人信息的录入、修改、查找、学生本人及成绩的输出和统计；首先运行程序，包括4个选项，0.保存并退出系统. 1.按学号录入学生信息 2.按学号查询学生成绩 3.分段统计与排序输出。4.然后可以根据不同的需要选择不
4、同的选项进行操作四.概要设计4.1系统用到的数据有：int dataST;/数据结构int gailv;/概率统计int xiandai;/线性代数 long number; /学号char name10; /姓名 char sex10; /性别char date20; /出生日期 score s; /成绩4.2用到的主要函数：(1)int hash(int key); /用除留余数法构造哈希函数(2)int Build_Hash(Hash *H,stu st);/输入一组关键字,建立Hash表,用链地址法处理冲突(3)int Search(Hash *H,int key);/成绩查询(4)v
5、oid HeapAdjust (HeapType &H , int s, int m);/筛选(5)void HeapSort(HeapType &H);/ 堆排序。(6)void Segment(HeapType h);/统计各个分数段的人数(7)int Sort(Hash *H);/使用堆排序对各科成绩按从高到低排列输出(8)void create(Hash *H);/录入学生信息(9)void Find(Hash *H);/查询学生信息(10)void tongji(Hash *H);/分段统计及排序(11)void savedata(student *&p);(12)student *
6、getdata();(13)void main();/主函数内部可以实现多函数调用4.3本实验从整体上分为四大模块：（1）创建并录入学生相关信息 ；（2）按学号查询学生成绩信息；（3）分段统计成绩与排序输出 ；（4）退出管理系统 ；五重要函数原理解析1.哈希函数（1）定义：Hash，一般翻译做散列，也有直接音译为哈希的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的
7、消息压缩到某一固定长度的消息摘要的函数。（2）本次实验中的所用到的哈希表概念及其作用哈希表中元素是由哈希函数确定的。将数据元素的关键字K作为自变量，通过一定的函数关系（称为哈希函数），计算出的值，即为该元素的存储地址。表示为： Addr = H（key）为此在建立一个哈希表之前需要解决两个主要问题：构造一个合适的哈希函数均匀性 H（key）的值均匀分布在哈希表中；简单以提高地址计算的速度冲突的处理冲突：在哈希表中，不同的关键字值对应到同一个存储位置的现象。即关键字K1K2，但H（K1）= H（K2）。均匀的哈希函数可以减少冲突，但不能避免冲突。发生冲突后，必须解决；也即必须寻找下一个可用地址。
8、解决冲突的方法：1链接法（拉链法）；开放定址法。以及哈希表的构造方法直接定址法例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。数字分析法有学生的生日数据如下：年.月.日75.10.0375.11.2376.03.02经分析，第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。平方取中法取关键字平方后的中间几位为哈希地址。折叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。例如：每一种西文图书都有一个国际标准图书编号，它是一个1
9、0位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，可采用此法构造一个四位数的哈希函数。*除留余数法取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。H(key)=key MOD p (p=m)随机数法选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key），其中random为随机函数。通常用于关键字长度不等时采用此法。*若已知哈希函数及冲突处理方法，哈希表的建立步骤如下：Step1.取出一个数据元素的关键字key，计算其在哈希表中的存储地址D=H(key）。若存储地址为D的存储空间还没有被占用，则将该数据元素存入；
10、否则发生冲突，执行Step2。Step2.根据规定的冲突处理方法，计算关键字为key的数据元素之下一个存储地址。若该存储地址的存储空间没有被占用，则存入；否则继续执行Step2，直到找出一个存储空间没有被占用的存储地址为止。*冲突无论哈希函数设计有多么精细，都会产生冲突现象，也就是2个关键字处理函数的结果映射在了同一位置上，因此，有一些方法可以避免冲突。拉链法拉出一个动态链表代替静态顺序存储结构，可以避免哈希函数的冲突，不过缺点就是链表的设计过于麻烦，增加了编程复杂度。此法可以完全避免哈希函数的冲突。多哈希法设计二种甚至多种哈希函数，可以避免冲突，但是冲突几率还是有的，函数设计的越好或越多都可
11、以将几率降到最低（除非人品太差，否则几乎不可能冲突）。开放地址法开放地址法有一个公式：Hi=(H(key)+di) MOD m i=1,2,.,k(k=m-1）其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,.m-1，称线性探测再散列。如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为1,-1,4,-4,9,-9,16,-16,.k*k,-k*k(knumber);if(Hi=NULL)Hi=st; /作为链表的第一个结点 else for(p=Hi;p-next;p=p-next); if(p-number=st-number) prin
12、tf( 已存在该学号的学生，添加学生信息出错!n); return 0; p-next=st; /插入链表尾部. return 1;2.堆排序*1： 堆的定义：n个元素的序列k1,k2,kn当且仅当满足下列关系时，称之为堆。 ki = k2i ki = k2i+1堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。*2： 利用堆及其运算，可以很容易地实现选择排序的思想。堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间，弥补了锦标赛排序的缺点。堆排序分为两个步骤： 第一步，根据初始输入数据，利用堆的调整算法 形成初始堆（最大堆或最小堆）； 第二步，通过一系列的对象交换和重新调整堆进行排序。对堆自堆顶至叶子的调整过程称为“筛选”。*3筛选（调整堆）算法： void HeapAdjust (SqList &H, int s, int m) / 已知H.rs.m中记录的关键字除H.rs.key之外均满足堆的定义, 本函数依据关键字的大小对H.rs进行调整, 使H.rs.m成为一 个大顶堆(最
