程序与算法综合设计课程设计指导书

要求：①设计合理的数据结构，编程实现算法；②给定训练数据集，设计合理的文件格式，保存于外存之中；③设计apriori算法，保存关联规则在外存中。

课题22：（85分）程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。

要求：

1) 老鼠形象可辨认，可用键盘操纵老鼠上下左右移动； 2) 迷宫的墙足够结实，老鼠不能穿墙而过；

3) 正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败； 4) 添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙； 5) 找出走出迷宫的所有路径，以及最短路径；

利用序列化功能实现迷宫地图文件的存盘和读出等功能。

课题23：（75分）选择合适的存储结构表示广义表，并能实现下列运算要求： （1）用大写字母表示广义表，用小写字母表示原子，并提供设置广义表的值的功能。 （2）取广义表L的表头和表尾的函数head(L)和tail(L)。 （3）能用这两个函数的复合形式求出广义表中的指定元素。

（4）由广义表的字符串形式到广义表的转换函数Lists Str_ToLists_(S)；例如 Str_ToLists_(“ (a,(a,b),c)”)的值为一个广义表。

（5）由广义表到广义表的字符串形式的转换函数char * Lists_To_Str(L)。 （6）最好能设置多个广义表。

课题24---25提示

简单路径：如果一条路径上的顶点除了起点和终点可以相同外，其它顶点均不相同，则称此路径为一条简单路径；起点和终点相同的简单路径称为回路（或环）。 课题24：（90分）

1）求出无向图中从起点到终点的所有简单路径。其中起点和终点可以由用户自行设

定。

2）求出无向图中从起点到终点的指定长度（如K）的所有简单路径。其中起点和终

点可以由用户自行设定。 课题25：（90分）

1）求出有向图中从起点到终点的所有简单路径。其中起点和终点可以由用户自行设

定。

2）求出有向图中从起点到终点的指定长度（如K）的所有简单路径。其中起点和终

点可以由用户自行设定。

课题26 （95分）《指针式时钟》问题分析,功能分析 （1）正确显示系统时钟；

（2）能准确定位时钟刻度和时分秒针的位置； （3）能随窗口大小的变化而变化。 算法设计及程序设计中技术重点:

在应用程序中，经常有一些任务在后台处理，实现方式有两种：计时器和OnIdle循环处理。计时器是程序中最常用的后台任务机制之一，其时间间隔最低约55毫秒，被广泛用于时钟、磁盘备份程序或需要在某一时刻运行的程序等。

多媒体计时器能编程设定1毫秒或者更小，它是诸如MIDI序列发生器之类的专用型应用程序的理想选择，在Windows API 中有很多查询时钟的函数，利用它们就可以编写出高精度的计时器。

使用计时器只需要了解两个函数：CWnd：：SetTimer（）函数用来设置一个计时器以指定的时间间隔触发，CWnd：：SetTimer（）函数用来使一个正在运行的计时器停止。计时器以两种方式通知应用程序计时器间隔时间已到：发送WM-TIMER消息和调用应用程序定义的回调函数。其中前者相对比较简单，但对于多个计时器则应使用回调函数。计时器消息发送给应用程序时都是低优先级，因此只有当消息对列中没有其他消息时才回处理它们。

计时器消息不能在消息队列中积存，这避免了出现永远无法清空消息队列的状态。尽管如此，Windows应用程序决不应该花费过量的时间来处理消息，除非该处理过程已经委派给辅助线程。如果主线程运行时间过长而没有检查消息队列，则程序的响应能力会受到影响。

程序运行结果图

课题27（90分）、设计某单位职工工资管理系统，功能如下：

对于每位职工存储以下信息：职工编号、基本工资、津贴、岗位津贴、应发数、个人所得税、应扣数、实发数。个人所得税计算方法设为：工资少于2000元的部分为0，2000—3000元部分为5%，3000—4000部分为10%，4000—5000部分为15%，5000元以上部分为20%。

（1）创建存储职工工资信息的存储文件； （2）添加某职工的工资信息； （3）删除某职工的工资信息；

（4）修改某职工的部分工资信息（当月开始增加或减少某些项工资或扣款数变化）； （5）输出指定编号职工的工资信息（查询用）

（6）输出全体职工的工资信息（发工资用）。 课程设计要求：

1．分析问题，给出数学模型，选择数据结构. 2．设计算法，给出算法描述 3．给出源程序清单

4. 编辑、编译、调试源程序 5. 撰写课程设计报告

课题28 （90分）学生成绩管理系统需求与功能分析 学生成绩管理系统的数据结构表如下：

序号 字段名 数据类型 长度 含义 1 class2 char 20 班级 2 num int 学号 3 name char 10 姓名 4 cprog float C程序设计 5 media flaot 多媒体技术 6 eng float 大学英语 7 math float 高等数学 8 sport float 大学体育 9 ave float 平均成绩 10 order int 名次

要求完成学生成绩的录入、统计、查询、修改、删除、输出。

课题29 （95分）散列表的设计与实现 任务：设计散列表实现电话号码查找系统。

要求：（1) 设每个记录有下列数据项：用户名、电话号码、地址；

（2) 从键盘输入各记录，以用户名（汉语拼音形式）为关键字建立散列表； （3) 采用一定的方法解决冲突； （4) 查找并显示给定电话号码的记录； 可以选作内容： （1) 系统功能的完善；

（2) 设计不同的散列函数，比较冲突率；

（3) 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。

课题30 （90分）宿舍管理查询软件

任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：

（1）采用交互工作方式

（2）可以增加、删除、修改信息

（3）建立数据文件 ，数据文件按关键字（姓名、学号、房号）进行排序(选择、快速排序、堆排序等任选一种)

(4) 查询: a.按姓名查询 ;b.按学号查询 ;c按房号查询 (5) 打印任一查询结果（可以连续操作）

课题31 （80分）求解2个字符串的最长公共子串。输入的2个字符串可以从键盘读入，也可以从两个文本文件中读入。

实现提示：可以采用动态规划法和后缀树算法，分析算法的时间复杂和空间复杂度。

课题32（95分）给出一篇英文文章，文件不小于5M的大小。统计其中的每个不同英文单词和总单词的数量。

实现提示：分别用链表和哈希表来实现，注意要给出不同大小文件耗费的时间，对时间性能进行进一步分析。关于英文文章，请自动生成文本文件。也可以从网络上下载几篇英文的文章，然后合并生成。

课题33（90分） 本科生导师制问题

问题描述：在高校的教学改革中，有很多学校实行了本科生导师制。一个班级的学生被分给几个老师，每个老师带领n个学生，如果老师还带研究生，那么研究生也可直接负责本科生。

本科生导师制问题中的数据元素具有如下形式：

⑴ 导师带研究生：（老师,((研究生1,(本科生1, …, 本科生m)), … )) ⑵ 导师不带研究生： (老师,(本科生1, …, 本科生m)) 导师的自然情况只包括姓名、职称； 研究生的自然情况只包括姓名、班级； 本科生的自然情况只包括姓名、班级。 功能要求：要求完成以下功能：

⑴ 插入：将某位本科生或研究生插入到广义表的相应位置； ⑵ 删除：将某本科生或研究生从广义表中删除； ⑶ 查询：查询导师、本科生（研究生）的情况； ⑷ 统计：某导师带了多少个研究生和本科生； ⑸ 输出：将某导师所带学生情况输出。

课题34（80分）

实现二叉树到其对应的Mirror Tree（镜像树）转化。所谓镜像树如下图所示