C/C++程序设计综合实践指导[2021级]
2021级程序设计综合实践指导
一、综合实践要求
综合实践是C语言程序设计、C++到数据结构三门课程的一个综合实践练习，是有别于课程实验的一个独立实践教学环节。综合实践一般在数据结构课程结束后进行，教学时数为2周，其中第1周个人实践(每人选1题)，第2周小组实践(组成2-3人的小组选1题)。具体要求如下：
1、结合实际问题进一步理解和深化课程理论知识，做到理论与实际相结合。
2、能对实际问题进行分析和抽象，并进行算法设计和数据结构设计，具有初步的分析问题和解决问题的能力。
3、了解软件工程的基础理论与方法，初步掌握软件开发过程中的需求分析、系统设计、编码、测试等基本方法和技能。
4、进一步强化编程训练，提高程序设计能力。
5、设计内容要有一定的深度和难度，达到一定工作量，两周代码量不低于1000行。
二、综合实践内容
综合实践的主要工作如下：
1、问题定义与需求分析：根据设计题目的要求，对问题进行分析，确定系统的功能需求和性能需求。
2、数据结构与算法设计：对问题描述中涉及的数据对象定义相应的数据结构，包括逻辑结构、存储定义和主要操作。对主要算法要进行时间和空间复杂度分析。
3、概要设计：采用面向对象方法设计软件结构，定义类及类之间的关系。给出系统的总体解决方案。画出本次设计的功能框图、流程图等。要求系统结构合理、易于实现。
4、详细设计：描述实现过程中所使用的类，数据存储的定义，主要成员函数及其功能等，建议使用UML进行类的描述。
5、编码与测试：用C++编程实现系统，并设计测试用例对系统进行测试，修改程序中的错误，形成格式和风格良好的源程序清单。
6、结果分析：对系统应用效果进行分析，评价系统的先进性、实际应用价值及在在的问题。
7、撰写程序设计综合实践报告。
三、综合实践考核
综合实践考核内容包括个人实践和小组实践两个模块，每个模块又包括实践作品和实践报告两个部分。实践作品包括可正确运行的源程序（刻录成光盘），系统使用说明，主要程序代码（打印附在实践报告内）。 实践报告主要包括系统分析、设计和实现过程，内容如下：
1、问题定义及设计要求；
2、主要实践内容：详细报告中所做的主要工作，包括系统分析、概要设计、数据结构设计、算法设计及模块设计和编程及测试等。
3、总结与体会：写出本次综合实践的主要创新点及存在的问题。
4、参考文献：实践过程中参考的主要书目、文章、或网址，不少于8个。
5、小组实践环节，需要组建2-3人的小组，明确写出小组成员及分工。
综合实践成绩分三部分，实践作品占40％，实践报告占30％，答辩占30％。其中实践作品包括个人实践作品和小组实践作品；实践报告包括个人实践和小组实践两部分，两部分的总结与体会、参考文献统一写在一起。评价因素主要有：
1、知识点覆盖范围及运用能力；
2、数据结构设计与算法设计能力；
3、系统规模（代码行数）；
4、数据存储方式；
5、人机交互（用户体验或评价）
四、时间安排：
第16-17周。第1周个人实践，第2周小组实践。每周具体：
周一：确定选题，查阅文献，确定解决方案。
周二、周三：编写代码实现功能。
周四：修改调试程序，并开始撰写本部分报告。
周五：完成报告，准备本实践部分答辩材料。
第2周周末进行答辩。
源码
https://pan.baidu.com/s/1pq1Nwwo0hlc_J84F93HM4A?pwd=1111
五、第一周个人实践参考题目
1、ATM机存取款管理程序（****）
【问题描述】
模拟银行的自动取款机的使用，实现查询余额、取款、存款、转账、退出系统等功能。不少于10名用户的信息，假设每个用户仅一个账户。
【基本要求】
（1）基于显示器、键盘完成ATM机中基本人机交互。
（2）设计应用程序所需要的类。
（3）将所有交易相关的操作设计成基类，从该基类派生出查询余额、取款、存款、转账等子类。
（4）完成该应用程序的所有功能。
２、个人银行账户管理程序（****）
【问题描述】
某人的活期储蓄账户包括账号，余额，年利率等基本信息，并需要显示账户信息，存款，取款，结算利息等基本操作。
【基本要求】
设计完成以上基本功能的类，并给出相应的测试程序。进一步：
（1）该用户有多个储蓄账户，增加功能能够记录各个账户的总金额，并增加相应的访问函数。
（2）为该用户增加信用账户，注意信用账户与储蓄账户的需求有不同。信用账户的特点是允许透支，每个信用账户也有信用额度，总得透支金额要在这个额度以内。如果向信用账户存钱，不会有利息，但使用信用账户透支则需要支付利息。请重新考虑该程序类的设计与实现。
（3）将用户的账户信息保存至文件中。
３、行文本编辑器（****）
【问题描述】
实现一个英文字符的行文本编辑器，该编辑器根据用户输入的命令可以完成以下功能——
I: input characters.
D: delete a character.
F: move forward a character.
B: move backward a character.
J: jump to the start.
E: jump to the end.
WF: move forward a word.
WB: move backward a word.
Q: quit.
（注：如需使用光标定位，可以直接用一个字符符号表示光标。）
【基本要求】
（1）完善文本形式界面的设计，将编辑的结果存入txt文件。
（2）对txt文件中的单词进行词频统计等。
（3）项目中必须至少实现一个自定义的类，并使用了教材中实现的String，Vector
４、基于EGE的二维小游戏的设计与实现（*****）
【问题描述】
完成二维小游戏如五子棋，飞机大战等的设计与实现。
【基本要求】
（1）角色、地图等游戏对象的数据及功能封装。
（2）完成基本游戏逻辑，设计基本人机交互的设计，具有基本的可玩性。
（3）进一步：地图（场景）的管理。
（4）简单的分值系统，如加入得分规则、生命值等。
难点：类的设计、继承与多态如何应用于角色的设计与实现中。
５、基于EGE的烟花效果的实现（***）
【问题描述】
完成二维小游戏烟花效果的设计与实现。
【基本要求】
（1）形成烟花的粒子（Point）的封装，包括的基本属性有位置，速度，颜色等。
（2）烟花的产生、更新、绘制。
（3）进一步：设计一个粒子系统抽象类，可以在此基础上派生出不同的粒子效果。
难点：类的设计、继承与多态如何应用于不同粒子的设计与实现中。
6、事件驱动模拟（***）
【问题描述】
对复杂问题建立模型进行模拟求解，本设计要求完成排队服务系统的模拟。
【基本要求】
（1）假设有n（n>1）个服务窗口，客户到达的时刻和办理事务的时间是随机的，每个窗口一次接待一个人。
（2）每个客户来了，首先选择空闲的窗口，如果没有，就选择人数最少的窗口排队。
（3）模拟系统的结果需显示在指定的时间内，接待多少客户，总的服务时间等。
难点：模拟过程的实现。
7、图书馆媒体管理程序（****）
【问题描述】
图书馆中的资料很多，如果能分类对其资料流通进行管理，将会带来很多方便，因此需要有一个媒体管理系统。图书馆主要有两类物品资料：图书和光盘。
这两类物品共同具有的属性有：编号、标题、作者等。其中图书类增加出版社、ISBN号、页数等信息；光盘类增加出品者的名字、出品年份和视频时长等信息。
【基本要求】
（1）添加物品：主要完成以上两类物品信息的添加，要求编号唯一。当添加了重复的编号时，则提示数据添加重复并取消添加；当物品库已满，则提示不能再添加新的数据。
（2）查询物品，可按照多种方式来查询物品，分别为：
按标题查询：输入标题，输出所查询的信息，若不存在该记录，则提示“该标题不存在！”；
按类别查询：输入类别，输出所查询的信息，若不存在记录，则提示“该类别没有物品！”；。
（3）显示物品库：输出当前物品库中所有物品信息，每条记录占据一行。
（4）编辑物品：可根据查询结果对相应的记录进行修改，修改时注意编号的唯一性。
（5）删除物品：主要完成图书馆物品信息的删除。如果当前物品库为空，则提示“物品库为空！”，并返回操作；否则，输入要删除的编号，根据编号删除该物品的记录，如果该编号不在物品库中，则提示“该编号不存在”。
8、学生考试成绩管理程序（****）
【问题描述】
设计并实现一个学生考试成绩管理程序。
【基本要求】
（1）设计并实现一个学生类，对学生成绩相关基本信息及相关操作进行封装。学生信息如下：
学生ID， 学生姓名， 4次作业成绩，期中成绩，期末成绩
（2）输入一组学生考试成绩（不少于10名学生的信息），并将所有学生信息存放至链表中。（要求使用第18章链表类模板的实现）
（3）为链表类模板增加排序功能Sort（），按升序排序。然后对学生按总评成绩进行排序。总评成绩计算如下：
4次作业平均成绩20%+期中成绩20%+期末成绩*60%
（4）为链表类模板增加链表逆置功能reverse（）。并按总评成绩由高到低输出学生信息。
难点：链表类模板排序功能的实现。
9、有理数类（复数类）的实现（***）
【问题描述】
定义一个有理数类，将有理数的分子和分母分别存放在两个整型变量中。对有理数的各种操作都可以用重载运算符来实现。
【基本要求】
（1）定义并实现一个有理数类，通过重载运算符+、-、*、/对有理数进行算术运算，通过重载运算符==实现判定两个有理数是否相等。
（2）在应用程序中，创建若干有理数对象，通过带参数的构造函数使得各有理数对象值各不相同，然后分别进行各类运算，输出运算结果，检验其正确性。
（3）复数类的基本要求同上。
10、中缀表达式求值（***）
【问题描述】
表达式由操作数、运算符和界限符组成，操作数可以是常数、变量或常量标识符。运算符分为算术运算符、关系表达符和逻辑运算符。基本界限符包括左右括号和表达式结束符。设计并实现中缀表达式求值.
【基本要求】
（1）基于栈实现带算术运算符表达式的运算，在此基础上实现关系运算和逻辑运算。
（2）项目中的栈必须使用教材18.3.1小节实现的链栈。
难点：如何计算带有括号的表达式。
六、第二周小组实践参考题目
1、学生成绩管理系统（***）
【问题描述】
设计并实现一个能够对学生信息以及其成绩信息进行管理的系统。其中学生信息包括：学号、姓名、年龄、性别；课程成绩信息包括：课程号、课程名、成绩、任课教师。能够根据学生信息和成绩信息对数据进行插入、删除、更新、查询、排序、统计等操作。
【基本要求】
（1）对系统用到的数据要能够从文件中读取；
（2）系统中的排序操作至少要用到快速排序、堆排序和归并排序中的两种排序方法；
（3）系统中查找过程至少用到两种查找方法。
【知识点】
（1）线性表；
（2）排序算法；
（3）查找算法。
2、图书管理系统（***）
【问题描述】
图书管理基本业务活动包括：对一本书进行采编入库、清除库存、借阅和归还等。试设计一个图书管理系统，将上述业务活动借助于计算机系统完成。
【基本要求】
（1）每种书的登记内容至少包括书号、书名、作者、现存量和总库存量等5种。
（2）系统应实现的操作及功能定义如下：
1）采编入库：新购入一种书，经分类和确定书号后登记到图书账目中去。如果这种书在账目中已有，则只将总库存量增加；
2）清除库存：某种书已无保留价值，将它从图书帐目中注销；
3）某种书的现存量大于零，则借出一本，登记借阅者的图书证号和归还期限；
4）归还：注销对借阅者的登记，改变该书的现存量。
【知识点】
（1）线性表；
（2）查找算法；
3哈夫曼编码译码（****）
【问题描述】
设计一种编码，让使用频率高的字符的编码尽可能的短，并且要求一字符的编码不能与另一个字符的编码的前一部分相同。把每个叶子的使用频率作为权，构造哈夫曼树。然后能够通过字符和他的权值来构造哈夫曼编码，并且能够通过编码相反的过程来实现哈夫曼的译码功能。
【基本要求】
（1）能够通过键盘或者纯文本文件读入字符集的大小n，以及n个字符和权值来建立哈夫曼树，并且把建立好的哈夫曼树存入到HuffmanTree.txt中去。
（2）利用已经建立好的哈夫曼树，对文件中的正文进行编码，将结果存入到文件HuffmanCode.txt中。
（3）利用已经建立好的哈夫曼树将HuffmanCode.txt中的哈夫曼编码进行译码，结果存入到HuffmanText.txt中。
（4）能够按照垂直输出二叉树的方式，将存储在HuffmanTree.txt纯文本文件中的哈夫曼树垂直输出。并且在打印哈夫曼编码是，要求字符与编码之间是一一对应的。
【实现提示】
（1）在程序运行时，能够出现一个主选择菜单，用户能够自主选择功能：①建立哈夫曼树；②对哈夫曼树进行编码、译码等功能。
（2）在建立哈夫曼树时，用到文本文件的读取时，需要用到头文件“fstream”来对文本文件进行处理。
【关键技术与知识点】
（1）优先级队列；
（2）哈夫曼树；
（3）啥夫曼编码。
4八皇后问题（***）
【问题描述】
八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。问题描述如下：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
【基本要求】
（1）在8×8格的国际象棋上摆放八个皇后。
（2）任意两个皇后不能处于同一列中。
（3）任意两个皇后不能处于同一行中。
（4）任意两个皇后不能处于对角线中。
（5）程序中包含递归和非递归两种算法。
【实现提示】
最深层的叶子结点才有可能是合法的布局。深度优先遍历这棵“状态树”，寻找这些叶子便是求解过程。
（1）用三个一维数组A、B、C记录棋盘占用情况，称为状态数组，状态数组的初始值为0，表示棋盘上还没有皇后。如果一个皇后占据了某一位置（x0，y0)令A[x0]=B[x0+y0]=C[x0-y0]=1，那么下一个皇后能够占据另一个位置（x1，y1）的前提是A[x1]=B[x1+y1]=C[x1-y1]=0.
（2）作为数组下标，x和y的取值范围是07，因此x+y和x-y的取值范围分别为014和-77，整个取值范围是-714。按照习惯，数组下标从0开始，这就需要加7，使下标范围等价的转换为0~21，数组A、B、C的长度为22.原来的数组元素A[x]、B[x+y]、C[x-y]现在分别等价于A[x+7]、B[x+y+7]、C[x-y-7]。
（3）利用长度为8的一维数组Y记录皇后的位置，如果Y[y]=x(0<=y<8)表示皇后占据了第y行第x列。
（4）求解过程就是深度优先遍历。如果叶子是合法的布局，就输出记录的结果。然后回溯，在回到上一层递归之前，要把状态数组在当前位置上的值恢复为0。
【知识点】
（1）树的遍历；
（2）递归与非递归算法；
（3）栈与队列。
5迷宫求解（***）
【问题描述】
以一个m*n的长方阵表示迷宫，如图1所示，阴影部分表示此路不能，空白部分表示此路可行。规定每次只能走上下左右相邻的一格。设计一个C++程序，求出从入口到出口所有路径。
【基本要求】
（1）迷宫的规格（即行数与列数）、状态设置（即各方格能否通行的状态）、入口和出口的位置，均应由输入随机确定。
（2）求得的路径，应该以从入口到出口的路径上的各个方格的坐标的线性序列输出。当无通路时，应该报告无路径的信息。
（3）扩展内容：求出从入口到出口的最短路径。
【实现提示】
（1）将迷宫转换为图，即把迷宫中的空白看作图的顶点，空白的上下左右邻接关系看作图的无向边。图的顶点存储迷宫空白坐标。这样图1所示的迷宫可以转换成图2所示的图。迷宫求解问题可以转换为图的遍历问题。
（2）存储结构：迷宫可以采用二维数组maze[][]表示。row与col分别表示迷宫的行数与列数。而maze[i][j]表示迷宫中第i行第j列的一个方格，用maze[i][j]=0表示该方格可以通行，用maze[i][j]=1表示该方格不可以通行。可在迷宫的四周加一圈障碍，这样可以保证从任一顶点出发，都可以有4个方向的选择。
（3）可以采用递归算法或非递归算法求出所有路径。非递归算法需要借助栈保存迷宫搜索程中已走过的路径信息，以便在遇到障碍时沿原路返回，在搜索结束后输出栈中保存的最终路径。
（4）求迷宫最短路径可以采用图的广度优先搜索遍历算法，这时需要采用队列作为辅助数据结构。
【知识点】
（1）图的遍历；
（2）单源最短路径；
（3）递归与非递归算法；
（4）栈与队列。
6各种排序算法的性能分析（****）
【问题描述】
排序是一个将记录的无序序列调整成为一个有序序列的过程。排序算法是计算机程序设计中的重要过程，不同的排序算法性能各有不同。在程序中，我们通过随机函数产生规模不同的随机整型数组，然后分别让不同的排序算法来从小到大进行排序。通过排序时间和排序的交换次数上对不同的排序算法进行性能分析。
【基本要求】
（1）每种排序算法在同一规模的数组测试中使用的原始数据是相同的。例如:不同排序算法对一个含有100个元素的无序数组进行排序时，他们的无序序列是相同的。
（2）对用于测试的随机数组规模不少于100个元素，其待测排序数组不少于5组。
（3）对不同的排序算法要求记录排序所需执行时间和移动次数。
（4）对以下排序算法进行性能分析，尽量采用结构化程序设计方法，要求对各个模块的功能及参数作必要的说明。(直接插入排序，折半插入排序，希尔排序，起泡排序，快速排序，直接选择排序，堆排序(加黑的着重要求)，树型选择排序，归并排序以及基数排序)
【实现提示】
（1）通过在程序中插入计数器来实现排序算法中对移动次数的记录。
（2）调用#include
【知识点】
（1）排序算法。
（2）算法性能分析。
7交通咨询系统（最短路径问题） （*****）
【问题描述】
设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径或最低费用或最少时间等问题。对于不同咨询要求，可以输入城市间的路程或所需要时间或所需费用。设计分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。
【基本要求】
（1）对城市信息(城市名、城市间的里程)进行编辑：具备添加、修改、删除功能；
（2）对飞机航班和列车时刻表进行编辑：里程、航班和列车班次的添加、修改、删除；
（3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具，可以不考虑回程；
（4）旅途中的耗费的总时间应包括中转站的等候时间。其中飞机至少二小时，火车至少一小时；
（5）咨询以用户和计算机对话方式进行，要注意人机交互的屏幕界面。由用户选择最优决策原则和交通工具，输入起始站、终点站、出发时间，输出信息：最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间。
【实现提示】
（1）数据存储。城市信息(城市名、代码)、交通信息(城市间的里程、各航班和列车时刻)存储于磁盘文件中。
（2）数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为有向图，图的顶点是城市，边是城市之间所耗费的时间（要包括中转站的等候时间）或旅费。
（3）数据的存储结构。采用邻接表作为数据的存储结构。
（4）求最优决策（最短路径和最小费用）功能模块：用Dijkstra算法求出出发城市到其它各城市的最优值(最短时间或最小的费用)。
（6）主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。
【知识点】
（1）单源最短路径。
（2）一顶点对之间的最短路径。
（3）所有顶点对之间的最短路径。
8重排九宫格（*****）
【问题描述】
将1、2、3、4、5、6、7、8等八个数字随机放在一个3x3的九宫格中，其中有一个格子为空。移动空格可以改变九宫格的状态。移动规则是，每次将与空格（上、下、左、右）相邻的一个数字平移到空格中。假设九宫格的初态和终态分别为图1的（a）和（b）所示，试给出从初态到终态的最少移动步数。
2 8 3
1 4
7 6 5
1 2 3
8 4
7 6 5
【基本要求】
（1）空格只能与空格相邻（上、下、左、右）的一个数字交换位置。
（2）空格不能连续两次与同一个数字交换位置（为了防止循环，规定状态不能返回父结点）。
（3）求出从初状态S0到目标状态Sg的调整过程，即从初态到终态的路径。
（4）扩展内容：在屏幕上显示九宫格的图形形式，并能动态演示移动过程。
【实现提示】
（1）隐式图搜索。九宫格求解是一个典型的状态搜索问题。如果用状态空间的显示表示，则应把其全部状态（共有9！个）存入计算机中，这是一个相当大的数字，不现实。一般采用隐式图搜索法，即从初态开始，逐步地生成问题的状态空间并检查解是否在其中。如图2所示，先从S0开始，产生4状态，如果解不在其中，则分别从这4状态开始产生新的状态。为了防止循环，规定不能返回到父结点。
（2）广度优先搜索算法步骤：
1）将初始状态S0压入队列S中。
2）若队列S为空，则搜索失败，问题无解。
3）取队列S首元素结点N取出放入栈K中并将其以顺序编号n。
4）若目标Sg=N，则搜索成功，问题有解。
5）若N无子结点则返回步骤2.
6）扩展N，将其所有子结点配上指向N的返回指针后，再依次放入队列S中，返回步骤2。
注意：返回指针的值要对应编号。
（3）深度优先搜索法
1）将初始状态S0压入栈S中。
2）若栈S为空，则搜索失败，问题无解。
3）取栈S顶元素结点N放入栈K中并将其以顺序编号n。
4）若目标Sg=N，则搜索成功，问题有解。
5）若N无子结点，则返回步骤2.
6）扩展N，将其所有子结点配上指向N的返回指针后，再依次压入栈S中，返回步骤2。
注意：返回指针要对应编号。
【知识点】
（1）图的遍历；
（2）栈、队列和优先级队列；
（3）状态空间搜索。
9 野人过河（*****）
【问题描述】
有3个野人和3个传教士来到河边渡河，河岸有一条船，每次至多可供2人乘渡，野人和传教士都会划船。在河岸，如果野人人数多于传教士人数，则野人会吃掉传教士。请设计一个程序来描述安全过河过程。
【基本要求】
（1）在河两岸和船上要求野人的人数不大于传教士的人数。
（2）要求输出所有可能的过程。(即不同方法的每个步骤如示例1)
（3）要求对各个模块的功能及参数作必要的说明。
【实现提示】
（1）先设定两个状态数组确定左岸和右岸，再确定状态变量：野人数，传教士数和船。
（2）先从开始岸考虑传教士数>=野人数，河对岸野人数<=传教士数。并且始终保证开过去两人，开回来一人实现有效转换。
（3）可以考虑使用图搜索方法，通过检测结点来实现路径的输出。
输出示例:
第1次：左岸到右岸，传教士过去1人，野人过去1人
第2次：右岸到左岸，传教士过去1人，野人过去0人
第3次：左岸到右岸，传教士过去0人，野人过去2人
第4次：右岸到左岸，传教士过去0人，野人过去1人
第5次：左岸到右岸，传教士过去2人，野人过去0人
第6次：右岸到左岸，传教士过去1人，野人过去1人
第7次：左岸到右岸，传教士过去2人，野人过去0人
第8次：右岸到左岸，传教士过去0人，野人过去1人
第9次：左岸到右岸，传教士过去0人，野人过去2人
第10次：右岸到左岸，传教士过去0人，野人过去1人
第11次：左岸到右岸，传教士过去0人，野人过去2人
【知识点】
（1）图的遍历。
（2）状态空间搜索。
10校园导游系统（****）
【问题描述】
设计一个校园导游系统，为来访的客人提供导游咨询服务，如景点查询、路径查询等。
【基本要求】
（1）设计所在学校的校园平面图，所含景点不少于10个。
（2）为来访客人提供图中任意景点相关信息的查询。
（3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条通路，包括任意两个景点之间的所有路径，任意两个景点之间的最短路径等。
（4）扩展内容：提供景点和道路的扩充及撤销功能。
【实现提示】
（1）用图存储校园平面图中的基本信息。图的顶点表示校园内各景点，存放景点名称、代号、简介等信息；图的边表示景点之间的可达关系；图的边的权植表示两个景点之间的路径长度。
（2）数据的存储结构。采用邻接表作为数据的存储结构。
（3）用迪杰斯特算法（Dijkstra）求出从一个景点到其他所有景点的最短路径，用弗洛伊德算法（Floyd）求所有景点之间的最短路径。
（6）主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。
【知识点】
（1）单源最短路径。
（2）所有顶点对之间的最短路径。
11文本分析（*****）
【问题描述】
编写程序，求出文本中每个单词出现的频次，并比较不同文本的相似度。
【基本要求】
（1）各文本存放在文件中，程序能读取文本文件；
（2）程序能对文本文件进行分词，将分词得到的单词存放到单词表中；
（3）如果一个单词多次出现，要统计单词出现的频率，其频率也要存入到单词表中；
【实现提示】
（1）定义一个结构体StringCount，其中字符串成员str和整数成员num分别记录单词及其出现的次数。
（2）创建单词表，程序扫描到一个单词后要先在单词表中查找该单词是否存在，如果不存在就把该单词存放到单词表中，并将该单词计数设为1；如果该单词存在，就修改单词表中该单词出现的频次，即把该单词计数增1。
（2）为了提高查找速度，建立平衡二叉搜索树，其结点存放单词基本信息（包括单词字符串和单词出现的频次），插入单词结点时要对平衡二叉搜索树进行动态平衡调整。
【知识点】
（1）字符串处理。
（2）平衡二叉搜索树。
12大学教学计划编制（****）
【问题描述】
大学每个专业都要制定教学计划。假设某个专业有40门课程，分8个学期开设。每门课程均在一个学期内完成。课程之间存在先修关系，即一门课程只有其所有先修课程都完成后才能开始。教学计划中至少有5门课程没有先修课程，先修关系路径长度不超过7。同一学期内开设的课程不存在先修关系，即可以并行执行。试设计实现一个教学计划编制程序，把课程分到不同学期，保证所有课程满足先修关系，且能对课程基本信息和上课学期进行查询。
【基本要求】
（1）每门课的信息包括课程基本信息（如课程号、学分等）和课程之间的关系信息（即课程之间的先修关系）。 课程信息存储在文件中。程序从文件中读取课程信息。
（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀，即每个学期课程门数和学分尽量相近；二是把课程尽可能地排在前几个学期中，即课程安排前紧后松。
（3）课程编排结果也要写入文件中。
【实现提示】
（1）课程基本信息和课程之间先修关系信息用图表示，图的顶点存储课程的基本信息，图的边存储课程之间的先修关系。
（2）先采用拓扑排序生成所有课程的之间的先后关系，再根据拓扑排序把课程分解到不同学期。
【知识点】
（1）程序文件读写；
（2）图的邻接表表示法；
（3）图的拓扑排序算法。