数据结构课程设计指导.doc

《数据结构课程设计指导.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计指导.doc（33页珍藏版）》请在三一文库上搜索。

1、数据结构课程设计指导数据结构课程设计指导 一、设计目的一、设计目的 熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。 二、设计要求二、设计要求 在本课程设计过程中要求： （1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务； （2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭 者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的 全部人员皆以零分计入本课程设计成绩。 （3）认真编写课程设计报告。课程设计报告的书写格式及要求见附录 2。 三、设计步骤三、设计步骤 1、 问题分析和任务定义； 2、 数据类型和

2、系统设计； 3、 编码实现和静态检查； 4、 上机调试； 5、总结和整理课程设计报告。 四、考核方式和成绩评定四、考核方式和成绩评定 考核分为两个部分： 程序运行情况：按规定时间到机房运行程序，由老师检查运行情况。学生能对自 己的程序面对教师提问并能熟练地解释清楚。 实验报告：是否按规定书写实验报告的各项内容。 课程设计成绩采用五级分制。 100%=上机检查（50%）+课程设计报告（50%） 五、上交相关内容要求五、上交相关内容要求 上交的成果的内容必须由以下四个部分组成，缺一不可 1 上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个 文件夹中） ； 2 上交程序的说明文

3、件：（保存在.doc 中）在说明文档中应该写明上交程序所在的 目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明； 3 课程设计报告：（保存在 word 文档中，文件名要求 按照“姓名-学号-课程设计 报告“起名，如文件名为“张三-101-课程设计报告“.doc ）按照课程设计的具体要求建立的 功能模块，每个模块要求按照如下几个内容认真完成； 1、需求分析、需求分析 1 程序的功能； 2 输入输出的要求； 3 测试数据。 2、概要设计、概要设计 包括程序设计组成框图，程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的 定义） 。 3、详细设计、详细设计 包括模块功

4、能说明（如函数功能、入口及出口参数说明，函数调用关系描述等） ，每个模块的算 法设计说明（可以是描述算法的流程图） 。 源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清 晰的程序注释。 4、调试分析、调试分析 测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题 是哪些？问题如何解决？） ，算法的改进设想。 5、核心源程序清单和执行结果、核心源程序清单和执行结果 源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清 晰的程序注释。 附录 1 数据结构课程设计的具体内容 本次课程设计完成如下模块（

5、共 36 个模块，抽签决定自己所做题目的序号） 1、一元多项式乘法、一元多项式乘法 1) 问题描述问题描述 已知 A(x)=a0+a1x+a2x2+anxn和 B(x)=b0+b1x+b2x2+bmxm，并且在 A(x)和 B(x)中指数相差很 多，求 A(x)=A(x)*B(x)。 2) 基本要求基本要求 (1)设计存储结构表示一元多项式； (2)设计算法实现一元多项式乘法； (3)分析算法的时间复杂度和空间复杂度。 2、 迷宫问题迷宫问题 1)问题描述问题描述 迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进 迷宫，迷宫中设置很多隔壁，对前进方向形成

6、了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪， 吸引老鼠在迷宫中寻找通路以到达出口。例如，图 2 所示为一个迷宫示意图，其中双边矩形表示迷宫，1 代表有障碍，0 代表无障碍。 2) 基本要求基本要求 (1) 设计数据结构存储迷宫； (2) 设计存储结构保存从入口到出口的通路； (3) 设计算法完成迷宫问题的求解； (4) 分析算法的时间复杂度。 3) 设计思想设计思想 可以采用回溯法实现该问题的求解。回溯法是一种不断试探及时纠正错误的搜索方法。从入口出发， 按某一方向向前探索，若能走通（未走过的） ，即某处可以到达，则到达新点，否则试探下一方向；若所 有的方向均没有通路，则沿原路返回前

7、一点，换下一个方向再继续试探，直到所有可能的通路都搜索到， 0123456789 01111111111 11011101111 21101011111 31010000011 41011101111 51100110001 61011001101 71111111111 入口(1, 1) 出口(6, 8) 图 2 迷宫示意图，其中 1 代表有障碍，0 代表无障碍 前进的方向有八个，分别是上、下、左、右、左上、左下、右上、右下 或找到一条通路，或无路可走又返回到入口点。 在求解过程中，为了保证在任何位置上都能沿原路退回，需要一个后进先出的栈来保存从入口到当前 位置的路径。 可以将迷宫定义成一个

8、二维数组，则每个点有 8 个试探方向，如当前点的坐标是(x, y)，与其相邻的 8 个点的坐标都可根据与该点的相邻方位而得到，规定试探顺序为顺时针方向，将这 8 个方向的坐标增量放 在一个结构数组 move8中，在 move 数组中，每个元素由两个域组成：x 表示横坐标增量，y 表示纵坐标 增量。这样会很方便地求出从某点(x，y)按某一方向 v (0v7) 到达新点（i，j）的坐标：i=x+movev. x ； j=y+movev.y。 算法用伪代码描述如下： 1. 栈初始化； 2. 将入口点坐标(x , y)及该点的方向 d（设为-1）入栈； 3. 当栈不空时循环执行下述操作： 3.1 (x

9、 , y , d)容忍值，则在 j 处放置放大器; 2.2 否则 D(i) = maxD(i)，D(j) +d(j) ; 【思考题思考题】本题假设分布网络是一棵二叉树结构，如果是树结构应如何设计算法？ 5、哈夫曼编码、哈夫曼编码 1) 问题描述问题描述 设某编码系统共有 n 个字符，使用频率分别为w1, w2, , wn，设计一个不等长的编码方案，使得该 编码系统的空间效率最好。 2) 基本要求基本要求 (1) 设计数据结构； (2) 设计编码算法； (3) 分析时间复杂度和空间复杂度。 3) 设计思想设计思想 利用 Huffman 编码树求得最佳的编码方案。 根据哈夫曼算法，建立哈夫曼树时，

10、可以将哈夫曼树定义为一个结构型的一维数组 HuffTree，保存哈 夫曼树中各结点的信息，每个结点包括：权值、左孩子、右孩子、双亲，如图 6 所示。由于哈夫曼树中共 有 2n-1 个结点，并且进行 n-1 次合并操作，所以该数组的长度为 2n-1。 构造哈夫曼树的伪代码如下： 1. 数组 huffTree 初始化，所有元素结点的双亲、左右孩子都置为-1； 2. 数组 huffTree 的前 n 个元素的权值置给定权值 wn； 3. 进行 n-1 次合并 3.1 在二叉树集合中选取两个权值最小的根结点，其下标分别为 i1, i2； 3.2 将二叉树 i1、i2 合并为一棵新的二叉树 k； 在哈夫

11、曼树中，设左分支为 0，右分支为 1，从根结点出发，遍历整棵哈夫曼树，求得各个叶子结点 所表示字符的哈夫曼编码。 【思考题思考题】对于采用哈夫曼编码树进行的编码，如何设计解码算法？ 6、TSP 问题问题 1) 问题描述问题描述 所谓 TSP 问题是指旅行家要旅行 n 个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。 该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。 2) 基本要求基本要求 (1) 上网查找 TSP 问题的应用实例； (2) 分析求 TSP 问题的全局最优解的时间复杂度； (3) 设计一个求近似解的算法； (4) 分析算法的时间复杂度。 3

12、) 设计思想设计思想 对于 TSP 问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线， 从中选择最佳的一条。但是用穷举法求解 TSP 问题的时间复杂度为(n!)，当 n 大到一定程度后是不可解 的。 本实验只要求近似解，可以采用贪心法求解：任意选择某个城市作为出发点，然后前往最近的未访问 的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。 为便于查找离某顶点最近的邻接点，可以采用邻接矩阵存储该图。算法用伪代码描述如下： 1. 任意选择某个顶点 v 作为出发点； 2. 执行下述过程，直到所有顶点都被访问： 2.1 v=最后一个被访问的顶点； 2.2

13、 在顶点 v 的邻接点中查找距离顶点 v 最近的未被访问的邻接点 j； 2.2 访问顶点 j； 3. 从最后一个访问的顶点直接回到出发点 v； weight lchild rchild parent 图 6 哈夫曼树的结点结构 【思考题思考题】上网查找 TSP 问题的应用实例，写一篇综述报告。 7、医院选址问题、医院选址问题 1)问题描述问题描述 n 个村庄之间的交通图可以用有向网图来表示，图中边上的权值表示从村庄 i 到村庄 j 的道路长 度。现在要从这 n 个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄 离医院都比较近？ 2) 基本要求基本要求 (1) 建立模

14、型，设计存储结构； (2) 设计算法完成问题求解； (3) 分析算法的时间复杂度。 3) 设计思想设计思想 医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。 设图 G=（V，E） ，对任一顶点 k，称 E(k)=maxd(i, k)（iV）为顶点 k 的偏心度。显然，偏心度最 小的顶点即为图 G 的中心点。 如图 7(a)所示是一个带权有向图，其各顶点的偏心度如图(b)所示。 医院选址问题的算法用伪代码描述如下： 1对加权有向图，调用 Floyd 算法，求每对顶点间最短路径长度的矩阵； 2对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度； 3具有最小偏心度的顶点即为所求。 【

15、思考题思考题】图的存储结构和算法的设计需要一定的灵活性和技巧。从医院选址问题的求解过程，你有 什么感想？ 8、简单个人电话号码查询系统简单个人电话号码查询系统 1) 问题描述问题描述 人们在日常生活中经常需要查找某个人或某个单位的电话号码，本实验将实现一个简单的个人电话号 码查询系统，根据用户输入的信息（例如姓名等）进行快速查询。 ab c d e 1 2 5 32 1 4 顶点偏心度 a b 6 b 8 d 5 e 7 (a) (b) 图 7 带权有向图及各顶点的偏心度 2) 基本要求基本要求 (1) 在外存上，用文件保存电话号码信息； (2) 在内存中，设计数据结构存储电话号码信息； (3

16、) 提供查询功能：根据姓名实现快速查询； (4) 提供其他维护功能：例如插入、删除、修改等； (5) 按电话号码进行排序。 3) 设计思想设计思想 由于需要管理的电话号码信息较多，而且要在程序运行结束后仍然保存电话号码信息，所以电话号码 信息采用文件的形式存放到外存中。在系统运行时，需要将电话号码信息从文件调入内存来进行查找等操 作，为了接收文件中的内容，要有一个数据结构与之对应，可以设计如下结构类型的数组来接收数据： const int max=10; struct TeleNumber string name; /姓名 string phoneNumber; /固定电话号码 string

17、mobileNumber; /移动电话号码 string email; /电子邮箱 Telemax; 为了实现对电话号码的快速查询，可以将上述结构数组排序，以便应用折半查找，但是，在数组中实 现插入和删除操作的代价较高。如果记录需频繁进行插入或删除操作，可以考虑采用二叉排序树组织电话 号码信息，则查找和维护都能获得较高的时间性能。更复杂地，需要考虑该二叉排序树是否平衡，如何使 之达到平衡。 9、各种排序算法时间性能的比较、各种排序算法时间性能的比较 1) 问题描述问题描述 对各种排序方法（直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排 序）的时间性能进行比较。 2)

18、基本要求基本要求 (1) 设计并实现上述各种排序算法； (2) 产生正序和逆序的初始排列分别调用上述排序算法，并比较时间性能； (3) 产生随机的初始排列分别调用上述排序算法，并比较时间性能。 3) 设计思想设计思想 上述各种排序方法都是基于比较的内排序，其时间主要消耗在排序过程中进行的记录的比较次数和移 动次数，因此，统计在相同数据状态下不同排序算法的比较次数和移动次数，即可实现比较各种排序算法 的目的。 直接插入排序、起泡排序、直接选择排序在教材中已经实现，请仿照教材中的方法在其他排序算法中 的适当位置插入计数器统计元素的比较次数和移动次数。 【思考题思考题】如果测算每种排序算法所用实际的

19、时间，应如何修改排序算法？ 10、机器调度问题、机器调度问题 1)问题描述问题描述 机器调度是指有 m 台机器需要处理 n 个作业，设作业 i 的处理时间为 ti，则对 n 个作业进行机器分配， 使得： (1) 一台机器在同一时间内只能处理一个作业； (2) 一个作业不能同时在两台机器上处理； (3) 作业 i 一旦运行，则需要 ti个连续时间单位。 设计算法进行合理调度，使得在 m 台机器上处理 n 个作业所需要的处理时间最短。 2) 基本要求基本要求 (1) 建立问题模型，设计数据结构； (2) 设计调度算法，为每个作业分配一台可用机器； (3) 给出分配方案。 3) 设计思想设计思想 假

20、设有七个作业，所需时间分别为2, 14, 4, 16, 6, 5, 3，有三台机器，编号分别为 m1、m2和 m3。这七 个作业在三台机器上进行调度的情形如图 9 所示，阴影区代表作业的运行区间。作业 4 在 0 到 16 时间被 调度到机器 1 上运行，在这 16 个时间单位中，机器 1 完成了对作业 4 的处理；作业 2 在 0 到 14 时间被调 度到机器 2 上处理，之后机器 2 在 14 到 17 时间处理作业 7；在机器 3 上，作业 5 在 06 时间完成，作业 6 在 611 时间完成，作业 3 在 1115 时间完成，作业 1 在 1517 时间完成。注意到作业 i 只能在一

21、台 机器上从 si时刻到 si +ti时间完成且任何机器在同一时刻仅能处理一个作业，因此最短调度长度为 17。 在上述处理中，采用了最长时间优先（LPT）的简单调度策略。在 LPT 算法中，作业按其所需时间的 递减顺序排列，在分配一个作业时，将其分配给最先变为空闲的机器。 m1 m2 m3 时间 分配 作业作业 5作业作业 6 作业作业 3 作业作业 1 作业作业 2 作业作业 7 作业作业 4 17 16 图 9 三台机器的调度示例 654 下面设计完成下面设计完成 LPT 算法的存储结构。算法的存储结构。 为每个机器设计数据类型： struct MachineNode int ID; /机

22、器号 int avail; /机器可用时刻 ; 为每个作业设计数据类型： struct JobNode int ID; /作业号 int time; /处理时间 ; LPT 算法用伪代码描述如下： 1. 如果作业数 n机器数 m，则 1.1 将作业 i 分配到机器 i 上； 1.2 最短调度长度等于 n 个作业中处理时间最大值； 2. 否则，重复执行以下操作，直到 n 个作业都被分配： 2.1 将 n 个作业按处理时间建成一个大根堆 H1； 2.2 将 m 个机器按可用时刻建立一个小根堆 H2； 2.3 将堆 H1 的堆顶作业分配给堆 H2 的堆顶机器； 2.4 将 H2 的堆顶机器加上 H1

23、 的堆顶作业的处理时间重新插入 h2 中； 2.5 将堆 H1 的堆顶元素删除； 3. 堆 H2 的堆顶元素就是最短调度时间； 11、 运动会分数统计运动会分数统计 1)问题描述问题描述 参加运动会有 n 个学校，学校编号为 1n。比赛分成 m 个男子项目，和 w 个女子项目。项目编号 为男子 1m，女子 m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为： 7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。 （m 将插入活区中第行之后 （2）行删除。格式：d 删除活区中第行（到第行）。两种格式的例子是：“d10”和“d1014” （3）活

24、区切换。格式：n 将活区写入输出文件，并从输入文件中读入下一段，作为新的活区。 （4）活区显示。格式：p 逐页地（每页 20 行）显示活区内容，每显示一页之后请用户决定是否继续显示以后各页（如果存在） 。印出的每一行要前置以行号和一个空格符，行号固定占 4 位，增量为 1。 各条命令中的行号均须在活区中各行行号范围之内，只有插入命令的行号可以等于活区第一行行号减 1，表示插入当前屏幕中第一行之前，否则命令参数非法。 3)3)测试数据测试数据 由学生依据软件工程的测试技术自己确定。注意测试边界数据，如首行、尾行。 4)4)实现提示实现提示 （1） 设活区的大小用行数 activemaxlen（可

25、设为 100）来描述。考虑到文本文件行长通常为正态分 布，且峰值在 60 到 70 之间，用 320activemaxlen 大小的字符数组实现存储将造成大量浪费。可以以标 准行块为单位为各行分配存储，每个标准行块含 81 个字符。这些行块可以组成一个数组，也可以利用动 态链表连接起来。一行文字可能占多个行块。行尾可用一个特殊的 ASCII 字符（如(012)8）标识。此外， 还应记住活区起始行号。行插入将引起随后各行行号的顺序下推。 （2） 初始化过程包括：请用户提供输入文件名（空串表示无输入文件）和输出文件名，两者不能相 同。然后尽可能多地从输入文件中读入各行，但不超过 activemax

26、len-x。x 的值可以自定，例如 20。 （3） 在执行行插入命令的过程中，每接收到一行时到要检查活区大小是否已达 activemaxlen。如果 是，则为了在插入这一行之后仍保持活区大小不超过 activemaxlen，应将插入点之前的活区部分中第一行 输出到输出文件中；若插入点为第一行之前，则只得将新插入的这一行输出。 （4） 若输入文件尚未读完，活区切换命令可将原活区中最后几行留在活区顶部，以保持阅读连续性； 否则，它意味着结束编辑或开始编辑另一个文件。 （5） 可令前三条命令执行后自动调用活区显示。 5)5)选作内容选作内容 （1） 对于命令格式非法等一切错误作严格检查和适当处理。

27、（2） 加入更复杂的编辑操作，如对某行进行串替换；在活区内进行模式匹配等，格式可以为 S 和 m。 16、哈希表设计、哈希表设计 1)1)问题描述问题描述 针对某个集体中人名设计一个哈希表，使得平均查找长度不超过 R，并完成相应的建表和查表程序。 2)2)基本要求基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有 30 个，取平均查找长度的上限为 2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。 3)3)测试数据测试数据 取读者周围较熟悉的 30 个人名。 4)4)选作内容选作内容 （1） 从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈

28、希函数，比较他们 的地址冲突率（可以用更大的名字集合作实验）。 （2） 研究这 30 个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。 （3） 在哈希函数确定的前提下尝试各种不同处理冲突的方法，考察平均查找长度的变化和造好的哈 希表中关键字的聚集性。 17、统计成绩、统计成绩 1)1)问题描述问题描述 给出 n 个学生的 m 门考试的成绩表，每个学生的信息由学号、姓名以及各科成绩组成。对学生的考试 成绩进行有关统计，并打印统计表。 2)2)基本要求基本要求 （1） 按总数高低次序，打印出名次表，分数相同的为同一名次； （2） 按名次打印出每个学生的学号、姓名、总分以及

29、各科成绩。 3)3)测试数据测试数据 由学生依据软件工程的测试技术自己确定。注意测试边界数据。 4)4)选作内容选作内容 对各科成绩设置不同的权值。 18、校园导游程序、校园导游程序 1)1)问题描述问题描述 用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介 等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问 题。 2)2)基本要求基本要求 （1） 查询各景点的相关信息； （2） 查询图中任意两个景点间的最短路径。 （3） 查询图中任意两个景点间的所有路径。 （4） 增加、删除、更新有关景点和道路的信息。 3)3

30、)选作内容选作内容 （1） 求多个景点的最佳（最短）游览路径。 （2） 区分机动车道和人行道。 （3） 实现导游图的仿真界面。 19、员工管理系统、员工管理系统 1 1）问题描述）问题描述 每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。系统能够完成员 工信息的查询、更新、插入、删除、排序等功能。 2 2）基本要求）基本要求 （1） 排序：按不同关键字，对所有员工的信息进行排序。 （2） 查询：按特定条件查找员工。 （3） 更新：按编号对某个员工的某项信息进行修改。 （4） 插入：加入新员工的信息。 （5） 删除：按编号删除已离职的员工的信息。 20、 排序二叉树的遍

31、历（排序二叉树的遍历（ 用递归或非递归的方法都可以）用递归或非递归的方法都可以） 1)1)问题描述问题描述 输入树的各个结点，建立排序二叉树，对建立的排序二叉树进行层次、先序、中序和后序遍历并统计 该二叉树中叶子结点的数目。 2)2)基本要求基本要求 (1)用菜单实现 (2)能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列和叶子结点的数目。 21、个人帐簿管理系统设计、个人帐簿管理系统设计 1)问题描述问题描述 个人帐簿管理系统记录某人每月的全部收入及各项开支情况，包括食品消费，房租，子女教育费用， 水电费，医疗费，储蓄等。进入系统后可以输入和修改某月的收支情况，可以对每月的开支从小到

32、大进行 排序，可以根据输入的月份查询每月的收支情况。 2) 基本要求基本要求 （1（初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数； （2（完成最低要求：建立一个文件，包括某人 5 个月的收支情况，能对文件中的信息进行扩充（追加） ，修改和删除； （3（进一步要求：完成对每月的开支排序，以及完成系统查询功能。有兴趣的同学可以自己扩充系统 功能。 22、学分管理程序、学分管理程序 1) 问题描述问题描述 请设计一个学生的学分管理程序。 假设每位学生必须完成基础课 50 学分、专业课 50 学分、选修课 24 学分、人文类课程 8 学分、实验 性课程 20 学分才能够毕业。因此在管理

33、学分时，要考虑每个学分所属于的课程类别。学分信息应该包括 学号、姓名、课程类别、学分等。 2) 基本要求基本要求 该程序应该具有下列功能： (1) 通过键盘输入某位学生的学分； (2) 给定学号，显示某位学生的学分完成情况； (3) 给定某个班级的班号，显示该班所有学生学分完成情况； (4) 给定某位学生的学号，修改该学生的学分信息； (5) 按照某类课程的学分高低进行排序； (6) 提供一些统计各类信息的功能。 23、销售管理系统、销售管理系统 1)问题描述问题描述 某公司有四个销售员（编号：1-4） ，负责销售五种产品（编号：1-5） 。每个销售员都将当天出售的每 种产品各写一张便条交上来

34、。每张便条包含内容： 1）销售员的代号 2）产品的代号 3）这种产品的当天的销售额 每位销售员每天可能上缴 0-5 张便条。假设，收集到了上个月的所有便条，编写一个处理系统，读 取上个月的销售情况（自己设定） ，进行如下处理。 2) 基本要求基本要求 1）计算上个月每个人每种产品的销售额。 2）按销售额对销售员进行排序，输出排序结果（销售员代号） 3）统计每种产品的总销售额，对这些产品按从高到底的顺序，输出排序结果（需输出产品的代号和 销售额） 24、宿舍管理软件、宿舍管理软件 1)问题描述问题描述 设某宿舍有:101,102,201,202 四个房间,每个房间有 4 个床位,学生信息包括学号

35、、姓名、房间号，为 学生宿舍管理人员编写一个宿舍管理软件。 2) 基本要求基本要求 该程序应该具有下列功能： (1) 学生的入住处理； (2) 学生退房处理； (3) 输出学生入住信息(按房间号和床号有序)； (4) 修改入住信息； (5) 学生调换宿舍或床位处理； (6) 按给定学号、姓名、房号查询； (7) 查询房间使用情况。 25、排序系统设计、排序系统设计 1)问题描述问题描述 设编号为 1，2，3，n 的 n(n0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开 始时任选一个正整数做为报数上限 m，从第一个人开始顺时针方向自 1 起顺序报数，报到 m 是停止报数， 报 m 的

36、人出列，将他的密码作为新的 m 值，从他的下一个人开始重新从 1 报数。如此下去，直到所有人 全部出列为止。令 n 最大值取 30。要求设计一个程序模拟此过程，求出出列编号序列。 2) 基本要求基本要求 （1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数； （2）完成最低要求：建立一个文件，包括某 5 个人的情况。 26、库存管理系统、库存管理系统 1)问题描述问题描述 试设计一库存管理系统，产品信息包括产品编号、名称、价格、数量等（产品编号不重复） 。 2) 基本要求基本要求 该系统应具有以下功能： 1、产品信息录入功能(产品信息用文件保存)输入 2、产品信息浏览功能 输出

37、3、产品入库 4、产品出库 5、查询和排序功能： 1）按价格从大到小排序 2）按名称查询 6、产品信息删除、修改功能。 27、学生作业完成情况管理程序、学生作业完成情况管理程序 1)问题描述问题描述 请设计一个学生作业完成情况管理程序。 假设某门课程一学期要留 10 次作业，每次老师要进行批改，给出分数后还要进行登记。学期期末要 根据每次作业的成绩计算出最终的平时成绩（满分 100） 。作业登记信息应该包含：学号、姓名、10 次作 业的完成情况。 2) 基本要求基本要求 该程序应该具有下列功能： (1) 通过键盘输入某位学生某次作业的分数； (2) 给定学号，显示某位学生作业完成情况； (3)

38、 给定某个班级的班号，显示该班所有学生的作业完成情况； (4) 给定某位学生的学号，修改该学生的作业完成信息； (5) 给定某位学生的学号，删除该学生的信息； (6) 按学生的最终平时成绩进行排序； (7) 输出平均分数。 28、学生籍贯管理系统、学生籍贯管理系统 1)问题描述问题描述 编制一个学生籍贯信息记录簿，每个学生信息包括：学号、姓名、籍贯、通信地址。 2) 基本要求基本要求 该程序应该具有下列功能： （1）输入学生信息并以磁盘文件保存； （2）读取磁盘文件并显示输出所有学生的籍贯信息； （3）按学号或姓名查询其籍贯； （4）按籍贯查询并输出该籍贯的所有学生； （5）能添加、删除和修改

39、学生的籍贯信息； （6）显示输出天津籍和非天津籍学生的信息并可分别存盘； （7） 按学号进行排序。 29、机票管理系统、机票管理系统 1)问题描述问题描述 一机场每天有 n 个航班，每个班次都有一班次号（1、2、3n） ，固定的起飞时间，固定的路线（起 始站、终点站） ，大致的飞行车时间，固定的额定载客量。如 班次 起飞时间 起点站 终点站 飞行时间 额定载量 已定票人数 1 8:00 天津 广汉 2 145 130 2 6:30 天津 成都 0.5 140 140 3 7:00 天津 成都 0.5 140 120 4 10:00 天津 成都 0.5 140 120 试设计一个机票管理系统，对

40、机场的售票情况进行管理。 2) 基本要求基本要求 功能要求： （1）录入班次信息(信息用文件保存),可不定时地增加班次数据； （2）浏览班次信息,可显示出所有班次当前状况(如果当前系统时间超过了某班次的起飞时间,则显示“此 班已发出”的提示信息)。 （3）查询路线：可按班次号查询 ,可按终点站查询； （4）售票和退票功能 A：当查询出已定票人数小于额定载量且当前系统时间小于起飞时间时才能售票，自动更新已售票人数 B：退票时，输入退票的班次，当本航班飞机未发出时才能退票，自动更新已售票人数。 30、学生成绩系统、学生成绩系统 1)问题描述问题描述 使用下面的数据，设计一个简单的成绩管理系统，实现

41、出最基本的功能。 学生基本信息文件(A.TXT)及其内容：A.TXT 文件不需要编程录入数据，可用文本编辑工具直接生成 学号 姓名 性别 宿舍号码 电话号码 01 张成成 男 501 87732111 02 李成华 女 101 87723112 03 王成凤 女 101 87723112 04 张明明 男 502 87734333 . 学生成绩基本信息文件(B.TXT)及其内容： 学号 课程编号 课程名称 学分 平时成绩 实验成绩 卷面成绩 综合成绩 实得学分 01 A01 大学物理 3 66 78 82 02 B03 高等数学 4 78 -1 90 01 B03 高等数学 4 45 -1 8

42、8 02 C01 VF 3 65 76 66 . . 2) 基本要求基本要求 功能要求及说明： (1) 数据录入功能: 对 B.TXT 进行数据录入,只录入每个学生的学号、课程编号、课程名称、学分、 平时成绩、实验成绩、卷面成绩共 7 个数据. 综合成绩、学分由程序根据条件自动运算。 综合成绩的计算:如果本课程的实验成绩为-1，则表示无实验，综合成绩=平时成绩*30%+卷面成绩*70%; 如果实验成绩不为-1,表示本课程有实验,综合成绩=平时成绩*15%+实验成绩*.15%+卷面成绩*70% . 实得学分的计算: 采用等级学分制. 综合成绩在 90-100 之间 ,应得学分=学分*100% 综

43、合成绩在 70-90 之间 ,应得学分=学分*80% 综合成绩在 60-70 之间 ,应得学分=学分*65% 综合成绩在 60 以下 ,应得学分=学分*0% （2）删除功能：当在 A.TXT 中删除一个学生时，自动地在 B.TXT 中删除此人所有信息。 （3）排序功能：能实现选择按综合成绩或实得学分升序或降序排序并显示数据。 （4）查询功能：分为学生基本情况查询和成绩查询两种 A：学生基本情况查询： A1-输入一个学号或姓名（可实现选择） ，查出此生的基本信息并显示输出。 A2-输入一个宿舍号码，可查询出本室所有的学生的基本信息并显示输出。 B：成绩查询： B1：输入一个学号时，查询出此生的所

44、有课程情况，格式如下： 学 号：xx 姓 名：xxxxx 课程编号：xxx 课程名称：xxxxx 综合成绩：xxxx 实得学分: xx 课程编号：xxx 课程名称：xxxxx 综合成绩：xxxx 实得学分: xx 课程编号：xxx 课程名称：xxxxx 综合成绩：xxxx 实得学分: xx 共修：xx 科，实得总学分为: xxx 31、单项选择题标准化考试系统、单项选择题标准化考试系统 1)问题描述问题描述 设计一单项选择题标准化考试系统，实现考试的标准化管理。 2) 基本要求基本要求 功能要求： （1）用文件保存试题库。 （每个试题包括题干、4 个备选答案、标准答案） （2）试题录入：可随时

45、增加试题到试题库中 （3）试题抽取：每次从试题库中可以随机抽出 N 道题（N 由键盘输入） （4）答题：用户可实现输入自己的答案 （5）自动判卷：系统可根据用户答案与标准答案的对比实现判卷并给出成绩。 注意：在 C 语言中产生随机数的方法：使用随机数函数 在使用随机数函数 random()之前，应包含文件 #include 然后使用下述函数初始化： randomize();/* init the random number generator */ 以后就可以直接使用 random()函数来产生需要的数据： 如果需要产生 10 以内的数，使用 random(10)就可以了；产生 100 以内的

46、数，使用 random(100)就可以 了。 在 C+中，产生随机数： #include #include 然后 srand(time(0); /以当前时间当做随机种子 rand(); /产生一个位于 0-32767 之间的随机数 32、通信录管理系统、通信录管理系统 1)问题描述问题描述 设计出模拟手机通信录管理系统，实现对手机中的通信录进行管理。 2) 基本要求基本要求 功能要求： （1）查看功能：选择此功能时，列出下列三类选择。 A 工作类 B 家庭类 C 朋友类 ，当选中某类时，显示出此类所有数据中的姓名和电话号码） （2）增加功能：能录入新数据（一个结点包括：姓名、电话号码、分类（可

47、选项有：A 工作类 B 家庭类 C 朋友类） 、家庭住址） 。例如 杨春 13589664454 商务类 南开区 当录入了重复的姓名和电话号码时，则提示数据录入重复并取消录入；当通信录中超过 10 条信息时， 存储空间已满，不能再录入新数据；录入的新数据能按递增的顺序自动进行条目编号。 （3）修改功能：选中某个人的姓名时，可对此人的相应数据进行修改 （4） 删除功能：选中某个人的姓名时，可对此人的相应数据进行删除，并自动调整后续条目的编号。 33、成绩管理系统、成绩管理系统 1)问题描述问题描述 现有学生成绩信息，内容如下 姓名 学号 语文 数学 英语 张明明 01 67 78 82 李成友

48、02 78 91 88 张辉灿 03 68 82 56 王露 04 56 45 77 陈东明 05 67 38 47 . 请编写一系统，实现学生信息管理。 2) 基本要求基本要求 功能要求： （1）信息维护： 要求：学生信息数据要以文件的形式保存，能实现学生信息数据的维护。此模块包括子模块有：增加 学生信息、删除学生信息、修改学生信息 （2）信息查询： 要求：查询时可实现按姓名查询、按学号查询 （3）成绩统计： 要求：A 输入任意的一个课程名（如数学）和一个分数段（如 60-70） ，统计出在此分数段的学生情 况。 排序：能对用户指定的任意课程名，按成绩升序或降序排列学生数据并显示排序结果（使用表格的形 式显示排序后的输出结果） （使用多种方法排序者，加分） 34、图书管理系统、图书管理系统 1)问题描述问题描述 设计一个系统，对图书信息进行管理，信息描述：有关该系统基本信息的描述，如：图书名称、图书编 号、单价、作者、存在状态、借书人姓名、性别、学号等。 2) 基本要求基本要求 基本功能： 1、新