数据结构与C语言综合训练实习
42 数组操作 43 打印日历表 44 学生证管理程序 45 图书登记管理程序 （4）平均成绩可按个人或科目进行； （5）查找可按最高个人平均分进行，或按指定科目的最高分进行； （6）每个学生的信息包括：序号、学号、性别、成绩1、成绩2、成绩3、成绩4； （7）基本功能为：建立文件、增加学生记录、新建学生信息文件、删除/修改学生记录。 设计菜单处理程序，对一维数组进行不同的操作。 （1）操作项目包括求数组最大值、最小值、求和、求平均值、排序、 二分查找、有序插入； （2）设计并利用字符菜单进行操作项目的选择，程序一次运行可根据选择完成一项或多项操作；通过菜单“退出”来结束程序的运行； （3）数组的输入、输出可支持命令行输入文件名、界面输入文件名从数据文件中输入和输出；也支持界面录入。 打印指定年份的公历表和农历表。 （1）输入年份为1990～2050内任一年； （2）可以选择输出公历表或农历表； （3）农历表包括二十四节气。 该程序应该具有下列功能： (1) 通过键盘输入某位学生的学生证信息。学生证包含的信息请参看自己的学生证； (2) 给定学号，显示某位学生的学生证信息； (3) 给定某个班级的班号，显示该班所有学生的学生证信息； (4) 给定某位学生的学号，修改该学生的学生证信息； (5) 给定某位学生的学号，删除该学生的学生证信息； (6) 提供一些统计各类信息的功能。 该程序应该具有下列功能： (1) 通过键盘输入某本图书的信息； (2) 给定图书编号，显示该本图书的信息； (3) 给定作者姓名，显示所有该作者编写的图书信息； (4) 给定出版社，显示该出版社的所有图书信息； 6
数据结构与C语言综合训练实习
46 学生学分管理程序 47 作业完成情况管理程序 48 旅店POS机管理系统 49 学生通讯录管理系统 (5) 给定图书编号，删除该本图书的信息； (6) 提供一些统计各类信息的功能。 假设每位学生必须完成基础课50学分、专业课50学分、选修课24学分、人文类课程8学分、实验性课程20学分才能够毕业。因此在管理学分时，要考虑每个学分所属于的课程类别。 该程序应该具有下列功能： (1) 通过键盘输入某位学生的学分； (2) 给定学号，显示某位学生的学分完成情况； (3) 给定某个班级的班号，显示该班所有学生学分完成情况； (4) 给定某位学生的学号，修改该学生的学分信息； (5) 按照某类课程的学分高低进行排序； (6) 提供一些统计各类信息的功能。 假设某门课程一学期要留10次作业，每次老师要进行批改，给出分数后还要进行登记。学期期末要根据每次作业的成绩计算出最终的平时成绩（满分100）。 该程序应该具有下列功能： (1) 通过键盘输入某位学生某次作业的分数； (2) 给定学号，显示某位学生作业完成情况； (3) 给定某个班级的班号，显示该班所有学生的作业完成情况； (4) 给定某位学生的学号，修改该学生的作业完成信息； (5) 给定某位学生的学号，删除该学生的信息； (6) 提供一些统计各类信息的功能。 旅店收款POS机管理系统的简单实现。 （1）前台管理：包括空房分等级显示、入住登记、退房结算、洗衣房管理、娱乐项目管理； （2）后台管理包括客房预定分析、营业额统计、日报表、月报表、年报表）； （3）设计数据结构文件来实现数据库管理，包括数据录入、查询、删除、修改、更新。 用链表方式来实现学生通讯录管理系统。 （1）通过定义一个包含学生通讯录（主要包括：学号、姓名、系别、专业、籍贯、家庭住址、 7
数据结构与C语言综合训练实习
50 超长正整数的乘法 51 个人电话号码查询系统 52 数字文本压缩 53 订票系统 联系电话等）的结构体类型，实现增加学生通讯录的内容、删除某个学生通讯录、输出全部学生通讯录内容、根据用户需求查找某个或某些学生的通讯录内容（如：按系别、专业、学号、姓名等内容进行查找）。 （2）能够实现以上给定的各项功能，具有方便简洁的操作界面，具有一定的容错性。 设计一个算法来完成两个超长正整数的乘法。 算法提示： 首先要设计一种数据结构来表示一个超长的正整数，然后才能够设计算法。 问题描述：实现简单的个人电话号码查询系统，根据用户输入的信息（如姓名，身份证号，电话号码、邮件地址等）进行快速查询。 基本要求： (1) 插入：实现将用户的信息插入到系统中；(2) 删除：删除某个用户的信息；(3) 修改：修改某个用户的信息；(4) 查询：根据姓名、身份证号等查询用户信息（包括简单条件查询，组合条件查询、模糊查询等）；(5) 排序：对于用户信息进行排序，提高查询速度；(6) 输出：输出用户信息。 提示： (1) 在内存中，设计数据结构存储电话号码的信息；在外存中，利用文件的形式来保存电话号码信息，系统运行时，将电话号码信息从文件调入内存来进行插入、查找等操作。 (2) 如果数据的插入删除频繁，可以考虑采取二叉排序树组织电话号码信息（也可采用较复杂的平衡二叉树），可以提高查找和维护的时间性能。 (3) 选择不同的排序和查找算法，尽可能提高查找和维护性能。 问题描述：利用哈夫曼编码，实现数字文本的压缩和解压缩。基本要求：对于给定的数字文本，可以根据其频度进行哈夫曼编码，并能输出对应的哈夫曼树和哈夫曼编码；实现哈夫曼解码。提高要求：(1)能够分析文件，统计文件中出现的字符，统计字符出现的概率，再对文件进行编码，实现文件的压缩和解压缩。(2)能够对于文件的压缩比例进行统计。 基本要求： (1)录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定） (2)查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班 8
数据结构与C语言综合训练实习
54 学籍管理系统 55 数字游戏的设计 票价，票价折扣，确定航班是否满仓）； (3)可以输入起飞抵达城市，查询飞机航班情况； (4)订票：（订票情况可以存在一个数据文件中，结构自己设定），可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号； (5)修改航班信息：当航班信息改变可以修改航班数据文件。 问题描述：建立学籍管理系统，实现对于学生信息的添加和维护管理。 基本要求：完成学籍登记表中的下面功能（登记表中包括学号、姓名、性别、出生日期、政治面貌、联系方式、家庭住址等信息）。 ⑴ 插入：将某学生的基本信息插入到登记表中； ⑵ 删除：将满足条件的基本信息删除； ⑶ 修改：对基本信息的数据项进行修改； ⑷ 查询：查找满足条件的学生； ⑸ 输出：将登记表中的全部（或满足条件）基本信息输出。 提高要求： ⑴ 可以添加课程信息（如开课学期、上课时间、上课地点等信息），学生选课信息，实现学生的选课功能； ⑵ 增加学生成绩信息，可以对学生的成绩进行插入、删除、修改等操作； ⑶ 实现查找某学生的选课记录，课程成绩等； ⑷ 利用二叉排序树、平衡树、排序算法等数据结构知识提高排序和查找速度。 提示： ⑴ 学生登记表一般建立后，比较少更改，因此，可以采用顺序表方式建立； ⑵ 学生选课、成绩等信息，一般更改比较频繁，则可以采取链表建立； ⑶ 可以将学生的信息存储到文件中；系统运行时，将信息从文件调入到内存中运行。 （1）一个四位数，各位上的数字不重复,从1到9。 （2）按以下提示猜出这个四位数。 9
数据结构与C语言综合训练实习
56 稀疏矩阵的压缩与还原 57 文章编辑 （3）每次猜测输入的数据给出类似的提示*A*B。 （4）其中A前的*代表你本次猜对了多少个数字。 （5）其中B前的*代表你本次猜对的数字并且位置正确的个数。 一个矩阵含有非零元素比较少，而零元素相对较多，这样的矩阵称为稀疏矩阵，对稀疏矩阵的存储我们不用完全用二维数组来存储，可以用一个三元组，即任意一个稀疏矩阵可以 用一个只有三列的二维数组来存放， 要求把给定的稀疏矩阵用为三元组表示；同时把三元组转换为稀疏矩阵形式。 输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符。 要求： （1）分别统计出其中英文字母数和空格数及整篇文章总字数； （2）统计某一字符串在文章中出现的次数，并输出该次数； （3）删除某一子串，并将后面的字符前移。 存储结构使用线性表，分别用几个子函数实现相应的功能； 输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。 输出形式： (1) 分行输出用户输入的各行字符； (2) 分4行输出\全部字母数\、\数字个数\、\空格个数\、\文章总字数\(3) 输出删除某一字符串后的文章； 建立有向无环图，并输出拓扑的序列。 实现随机探测再散列哈希表的创建与查找 58 59 拓扑排序 随机探测再散列哈希表 60 公园的导游图 给出一张某公园的导游图，游客通过终端询问可知： 从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不 重复地游览各景点，最后回到出口（出口就在入口旁边）。 分步实施： 10