发布时间 : 星期五 文章数据结构课程设计选题说明[1]更新完毕开始阅读89b9bbd449649b6648d74745
5、选做内容 ：
（1）编写递归形式的算法，求得迷宫中所有可能的通路； （2）以方阵形式输出迷宫及其通路。 18、串基本操作的演示
1、问题描述：（需求分析和背景意义）
如果语言没有把串作为一个预先定义好的基本类型对待，又需要用该语言写一个涉及串操作的软件系统时，用户必须自己实现串类型。试实现串类型，并写一个串的基本操作的演示系统。
2、基本要求：（设计阶段，概要设计和详细设计）
在教科书4.2.2节用堆分配存储表示实现HString串的最小操作子集的基础上，实现串抽象数据类型的其余基本操作， （不使用C语言本身提供的串函数）。 参数合法性检查必须严格。 说明：（在格式中，Φ表示0个、1个或多个空格所组成的串。 〈串标识〉表示一个内部名或一个串文字。前者是一个串的唯一标识，是一种内部形式的（而不是字符形式的）标识符。
后者是两端由单引号括起来的仅可打印字符组成的序列。 串内每两个连续的单引号表示一个单引号符。）
利用上述基本操作函数构造以下系统：它是一个命令解释程序，循环往复地处理用户键入的每一条命令，直至终止程序的命令为止。命令定义如下： 赋值。格式：AΦ〈串标识〉Φ〈回车〉
用〈串标识〉所表示的值建立新串，并显示新串的内部名和串值。如：A′Hi！′ 判相等。 格式：EΦ〈串标识1〉Φ〈串标识2〉Φ〈回车〉 若两串相等，则显示“EQUAL”，否则显示“UNEQUAL”。 联接。 格式：CΦ〈串标识1〉Φ〈串标识2〉Φ〈回车〉 将两串联接产生结果串，它的内部名和串值都显示出来。
（4） 求长度 格式：LΦ〈串标识〉Φ〈回车〉 显示串的长度。 （5） 求子串 格式：SΦ〈串标识〉Φ+〈数1〉Φ+〈数2〉Φ〈回车〉 如果参数合法，则显示子串的内部名和串值。〈数〉不带正负号。 （6）子串定位。 格式：IΦ〈串标识1〉Φ〈串标识2〉Φ〈回车〉 显示第二个串在第一个串中首次出现时的位置。
（7）串替换 格式：RΦ〈串标识1〉Φ〈串标识2〉Φ〈串标识2〉Φ〈回车〉 将第一个串中出现所有出现的第二个串用第三个串替换，显示结果串的内部名和串值，原串不变。
（8）显示格式：PΦ〈回车〉
显示所有在系统中被保持的串的内部名和串值的对照表。
（9）删除格式：DΦ〈内部名〉Φ〈回车〉 删除该内部名对应的的串，即赋值的逆操作。 （10）退出 格式：QΦ〈回车〉 结束程序的运行。
在上述命令中，如果一个自变量是串，则应首先建立它。基本操作函数的结果（即函数值）如果是一个串，则应在尚未分配的区域内新辟空间存放。 3、测试数据： 自定。但要包括以下几组： （1）E″ ″〈回车〉，应显示“EQUAL”。 （2）E′abc′ ′abcd′〈回车〉，应显示“UNEQUAL”。
（3）C″ ″〈回车〉，应显示″。 （4）I′a′ ″〈回车〉，应报告：参数非法。 （5）R′aaa′ ′aa′ ′b′〈回车〉，应显示′ba′ （6） R′aaabc′ ′a′ ′aab′〈回车〉，应显示′aabaabaabbc′。 （7）R′aaaaaaaa′ ′aaaa′ ′ab′〈回车〉，应显示′abab′。 4、实现提示：
（1）演示系统的主结构是一个串表头，可定义为： struct
{ HString StrHead[100]；
int CurNum }StrHeadList；
将各串的头指针依次存于串头数组StrHead中（设串的数目不超过100）。CurNum为系统中现有的串的数目，CurNum+1是可为下一个新串头指针分配的位置。可以取StrHead的元素下标作为所对应串的内部名。
（2）应设置一个命令为分析函数，把命令分析结果通过一下类型的一个变量参数返回： typedef struct
{ int CmdNo；//或char类型，为命令号或命令符
int s[3]； //命令串参数的内部名（最多3个） int num[2]； // 命令的数值参数（最多2个） }ResultType；
此函数还在存储结构中建立命令参数中的〈串〉。可能再设置一个“取下一个命令参数串”的操作是有益的。注意不要把这里的命令与所有机器的操作系统的命令相混。为了处理简单化，可以不对命令的格式作严格的语法检查。 5、选做内容 ：
（1）串头表改用单链表实现。
（2）对命令的格式（即语法）作严格检查，
是系统既能处理正确的命令，也能处理错误的命令。赘言，语义检查（如某内部名对于能够的串已被删除而无定义等）和基本操作参数合法性检查仍留给基本操作去做。 （3） 支持串名。
将串名（可设不超过6个字符）存于串表头中。命令（1）（3）（5）要增加命令参数〈结果串名〉；命令（7）中的〈串标识1〉改为〈串名〉，并用此名作为结果串名，删除原被替串标识，用〈串名〉代替〈串标识〉定义和命令解释中的内部名。每个命令执行完毕时立即自动删除无名串。 19.内部排序算法比较
1、问题描述：（需求分析和背景意义）
在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
2、基本要求：（设计阶段，概要设计和详细设计）
（1）对以下6中常用的内部算法进行比较：起泡排序、直接插入排序、简单选择排序、快速查找排序、希尔排序、堆排序。 （2）待排序表的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加
的比较次数和关键字的移动次数（关键字交换计为3次移动）。 （3）最后要对结果作出简单分析，包括对各数据得出结果波动大小的解释。 3、测试数据： 由随机数产生器产生。 4、实现提示： 主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性，如，正序、逆序和不同程度的乱序。注意采用分块调试的方法。 5、选做内容 ： （1）增加折半插入排序、二路插入排序、归并排序、基数排序等。 （2）对不同的输入表长作实验，观察检查的两个指标相对于表长的变化关系。还可以对稳定性作验证。
20. 算术表达式的求值演示
1、问题描述：（需求分析和背景意义）
表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型的例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。 2、基本要求：（设计阶段，概要设计和详细设计）
以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用教科书表3.1给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书上的例3-1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。 3、测试数据： 教科书例3-1的算术表达式3*（7-2），以及下列表达式 8； 1+2+3+4； 88-1*5；1024/4*8； 1024/（4*8）； （20+2）*（6/2）；3-3-3； 8/（9-9）； 2*（6+2*（3+6*（6+6）））；（（（6+6）*6+3）*2+6）*2；
4、实现提示： （1） 设置运算符栈和运算数栈辅助分析算符优先关系。 （2） 在读入表达式的字符序列的同时，完成运算符和运算数（整数）的识别处理，以及相应的运算。（3）在识别出运算数的同时，要将其字符序列形式转化成整数形式。 （4）在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作的内容。
5、选做内容 ： （ 1）扩充运算符集，如增加乘方、单目减、赋值等运算。 （2）运算量可以是变量。 （3）运算量可以是实数类型。 （4）计算器的功能和仿真界面。 21. 校园导游咨询
1、问题描述：（需求分析和背景意义）
设计一个校园导游程序，为来访的客人提供各种信息查询服务。 2、基本要求：（设计阶段，概要设计和详细设计）
（1）设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度的相关信息。 （2）为来访客人提供图中任意景点的相关信息查询。 （3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短路径。 3、测试数据： 由读者根据实际情况指定。
4、实现提示： 一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。 5、选做内容 ：
（1）求校园的关节点。 （2）提供图中任意景点问路查询，即求任意两个景点之间的所有路径。 （3） 提供校园图中多个景点的最佳访问路线查询，即求途经这个景点的最佳（短）
路径。 （4）校园导游图的景点和道路的修改扩充功能。 （5）扩充道路信息，如道路类别（车道、人行道等）、沿途景色等级，以至可按客人所需分别查询人行路径或车行路径或观景路径等。 （6）扩充每个景点的邻接景点的方向等信息，使得路径查询结果能提供详导向信息。 （7）实现校园导游图的仿真界面。 22. 约瑟夫环的求解及演示
1、问题描述：（需求分析和背景意义）
约瑟夫问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每个人持有一个密码(正整数).一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数.报m的人将出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止.设计一程序求出出列顺序.
2、基本要求：（设计阶段，概要设计和详细设计）
利用单向循环链表存储结构模拟次过程,按照出列的顺序印出个人的编号. 3、测试数据： m的初值为20;n=7,7个人的密码依次为:3,1,7,2,4,8,4,首先m值为6(正确的出列顺序应为6,1,4,7,2,3,5). 4、实现提示： 程序运行后,首先要求用户指定初始报数上限,然后读取个人的密码.可设n≤30.此题所用的循环链表中不需要“头结点”,请注意空表和非空表的界限. 5、选做内容 ： 向上述程序中添加在顺序结构上实现的部分. 23.平衡二叉树操作的演示
1、问题描述：（需求分析和背景意义） 利用平衡二叉树实现一个动态查找表。 2、基本要求：（设计阶段，概要设计和详细设计）
实现动态查找表的三种功能：查找、插入、删除。 3、测试数据：自行设定。 4、实现提示：
（1）初始，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。每次插入或删除一个结点后，应更新平衡二叉树的显示。 （2）平衡二叉树的显示可采用凹入表现形式，也可以采用图形界面画出树行。 （3）、教科书已给出查找和插入算法，本题重点在于对删除算法的设计和实现。假设要删除关键字为x的结点。如果x不在叶子结点上，则用它的左子树中最大值或右子树中的最小值取代x。如此反复取代，直到删除动作传递到某个叶子结点。删除叶子结点时，若需要进行平衡交换，可采用插入的平衡变换的反变换（如，左子树变矮对应右子树长高）。
5、选做内容 ： （1）合并两棵平衡二叉树。 （2）把一棵二叉树分裂为两棵平衡二叉树，使得在一棵树中的所有关键字都小于或等于x，另一棵树中的任一关键字都大于x。 24. 最小生成树问题
1、问题描述：（需求分析和背景意义）
若要在n个城市之间建设通信网络，只需要假设n-1条线路即可。如何以最低的经济代