# 学生成绩管理系统数据结构设计报告

本系统面向高校教务管理中一个典型教学班（50至120人）的成绩管理场景，需支持成绩录入、修改、删除、按学号精确查询、按分数段统计、按总分排名及不及格名单输出等功能。数据来源为各院系教务秘书提交的Excel表格，经预处理后导入系统，成绩字段包含平时成绩（百分制，占30%）与期末成绩（百分制，占70%），总评成绩由加权计算得出，保留一位小数。依据该需求，系统采用线性表作为核心存储结构，辅以哈希索引与二叉排序树索引，兼顾读写性能与代码可读性。

**数据结构选型与存储设计**

学生成绩记录定义为结构体，包含以下字段：学号（char[10]，前两位为入学年份，第三四位为院系代码，后四位为班内序号）、姓名（char[20]）、平时成绩（float）、期末成绩（float）、总评成绩（float）、排名（int）。主存储采用动态数组（顺序表），初始容量为100，按1.5倍因子扩容。顺序表在内存中连续分布，支持O(1)时间复杂度的随机访问，当需要按总分排名或按学号排序时，直接调用快速排序算法对数组下标进行重排，避免频繁移动结构体本身。考虑到每学期成绩数据量不超过10000条，顺序表的内存占用上限约为10000×52字节，即520KB，远低于普通PC机可用内存，故无需引入外部存储或链表结构。

为加快学号精确查询，系统构建哈希表，表长取2003（大于最大记录数的两倍且为质数），除留余数法将学号后四位映射至哈希地址，冲突处理采用链地址法。每个哈希桶存放指向顺序表元素的指针，插入、删除、查找的平均时间复杂度均为O(1)。实际操作中，学号后四位在0至9999范围内非均匀分布，采用除留余数法后各桶负载因子最大不超过8，检索一次命中率约83%，两次内命中率超过96%，性能满足教务人员日常操作需求。

**成绩统计与排名算法**

分数段统计需求将总评成绩划分为六个区间：不及格（小于60）、及格（60至69）、中等（70至79）、良好（80至89）、优秀（90至100）。系统遍历顺序表一次，通过分支判断将记录归入对应计数变量，时间复杂度O(n)。为存储各分数段学生名单，使用五个单向链表分别挂接对应记录指针，便于后续打印不及格名单或导出优秀学生表。

总分排名采用快速排序算法对总评成绩降序排列。为避免重复排序导致数据变动，排序作用于索引数组而非原顺序表。具体实现：定义整型数组idx[n]，初值0至n-1，以总评成绩为关键字进行快速排序，平均时间复杂度O(nlogn)。相同分数段内的学生按学号升序排列，保证排名稳定。排序完成后，依次为顺序表中各记录写入排名值。

**不及格名单与补考管理**

不及格名单的生成通过遍历哈希表各桶中的链表节点，检查总评成绩字段，将低于60分的记录追加至文本文件“fail.txt”，每行含学号、姓名、平时成绩、期末成绩、总评成绩。同时系统维护一个补考状态标志位（char类型，默认值为''N''，补考通过后置为''Y''），该标志位存储于结构体末尾，不影响既有字段的内存对齐。补考成绩单独保存在平行结构体数组中，不覆盖原始成绩，以便教务留档备查。

**查询与修改操作实现**

按学号查询的流程是：对学号后四位做除留余数法得到哈希地址，在对应冲突链中逐节点比对完整学号字符串，若匹配则从顺序表中取出该记录并显示各字段。修改成绩时先锁定记录，校验新成绩在0至100范围内，随后更新平时成绩与期末成绩字段，总评成绩按0.3与0.7的系数重新计算，并同步修改哈希链节点指向的顺序表元素内容，无需重建索引。

删除记录采用标记删除法，在结构体中增加记录有效标志（bool类型），删除操作仅将标志置为false，查询与统计时跳过无效记录，待累计删除量超过总记录数的30%时再执行一次物理压缩，将有效记录前移并重建哈希表。该方法避免了频繁移动元素带来的性能抖动，实测在万级数据量下平均响应时间低于30毫秒。

**性能验证与边界处理**

使用随机生成的5000条模拟数据进行压力测试，其中学号重复率为零，成绩字段随机分布于0至100。系统完成全部导入耗时1.2秒，构建哈希表耗时0.3秒，执行100次随机学号查询的累计耗时0.8秒，平均每次8毫秒。按分数段统计耗时4毫秒，快速排序耗时15毫秒。当输入非法学号（长度不为10或含非数字字符）时，程序返回错误代码并提示用户重新输入，不产生异常退出；成绩字段允许输入一位小数，自动进行四舍五入处理。

该设计在内存占用、时间效率与编码复杂度之间取得平衡。顺序表负责数据存储与批量处理，哈希表负责快速定位，排序索引服务排名需求，链表结构支撑分类统计。各模块间通过结构体指针传递数据，接口清晰，便于后续扩展课程绩点计算、按院系汇总等新功能。