数据结构课程设计题

ss“数据结构”课程设计题目1、城市链表[问题描述]将若干城市的信息，存入一个带头结点的单链表。结点中的城市信息包括：城市名，城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。[基本要求]（1）给定一个城市名，返回其位置坐标；（2）给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。[测试数据]由学生依据软件工程的测试技术自己确定。注意测试边界数据。2、约瑟夫生死者游戏[问题描述]约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。[基本要求]利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。[测试数据]m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。[实现提示]程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n≤30。[选作内容]向上述程序中添加在顺序结构上实现的部分。3、括号匹配的检验[问题描述]假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（（）[]）或[（[][]）]等为正确格式，[（]）或（（（]均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列：ss[([][])]12345678当计算机接受了第1个括号以后，他期待着与其匹配的第8个括号的出现，然而等来的却是第2个括号，此时第1个括号“[”只能暂时靠边，而迫切等待与第2个括号相匹配的第7个括号“）”的出现，类似的，因只等来了第3个括号“[”，此时，其期待的紧迫程度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号的期待紧迫程度高于第2个括号，而第2个括号的期待紧迫程度高于第1个括号；在接受了第4个括号之后，第3个括号的期待得到了满足，消解之后，第2个括号的期待匹配就成了最急迫的任务了，……，依次类推。可见这个处理过程正好和栈的特点相吻合。[基本要求]读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”。[测试数据]输入（[]（）），结果“匹配”输入[（）]，结果“此串括号匹配不合法”[实现提示]设置一个栈，每读入一个括号，若是左括号，则作为一个新的更急迫的期待压入栈中；若是右括号，并且与当前栈顶的左括号相匹配，则将当前栈顶的左括号退出，继续读下一个括号，如果读入的右括号与当前栈顶的左括号不匹配，则属于不合法的情况。在初始和结束时，栈应该是空的。[选作内容]考虑增加大括号的情况。4、停车场管理[问题描述]设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。[测试数据]设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车ss牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。[基本要求]以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。[实现提示]需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。[选作内容]（1）两个栈共享空间，思考应开辟数组的空间是多少？（2）汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。（3）汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。（4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。5、简单行编辑程序。[问题描述]文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。被编辑的文本文件可能很大，全部读入编辑程序的数据空间（内存）的做法既不经济，也不总能实现。一种解决方法是逐段地编辑。任何时刻只把待编辑文件的一段放在内存，称为活区。试按照这种方法实现一个简单的行编辑程序。设文件每行不超过320个字符，很少超过80字符。[基本要求]实现以下4条基本编辑命令：（1）行插入。格式：i行号回车文本回车将文本插入活区中第行号行之后（2）行删除。格式：d行号1[□行号2]回车ss删除活区中第行号1行（到第行号2行）。两种格式的例子是：“d10↙”和“d10□14↙”（3）活区切换。格式：n回车将活区写入输出文件，并从输入文件中读入下一段，作为新的活区。（4）活区显示。格式：p回车逐页地（每页20行）显示活区内容，每显示一页之后请用户决定是否继续显示以后各页（如果存在）。印出的每一行要前置以行号和一个空格符，行号固定占4位，增量为1。各条命令中的行号均须在活区中各行行号范围之内，只有插入命令的行号可以等于活区第一行行号减1，表示插入当前屏幕中第一行之前，否则命令参数非法。[测试数据]由学生依据软件工程的测试技术自己确定。注意测试边界数据，如首行、尾行。[实现提示]（1）设活区的大小用行数activemaxlen（可设为100）来描述。考虑到文本文件行长通常为正态分布，且峰值在60到70之间，用320×activemaxlen大小的字符数组实现存储将造成大量浪费。可以以标准行块为单位为各行分配存储，每个标准行块含81个字符。这些行块可以组成一个数组，也可以利用动态链表连接起来。一行文字可能占多个行块。行尾可用一个特殊的ASCII字符（如(012)8）标识。此外，还应记住活区起始行号。行插入将引起随后各行行号的顺序下推。（2）初始化过程包括：请用户提供输入文件名（空串表示无输入文件）和输出文件名，两者不能相同。然后尽可能多地从输入文件中读入各行，但不超过activemaxlen-x。x的值可以自定，例如20。（3）在执行行插入命令的过程中，每接收到一行时到要检查活区大小是否已达activemaxlen。如果是，则为了在插入这一行之后仍保持活区大小不超过activemaxlen，应将插入点之前的活区部分中第一行输出到输出文件中；若插入点为第一行之前，则只得将新插入的这一行输出。（4）若输入文件尚未读完，活区切换命令可将原活区中最后几行留在活区顶部，以保持阅读连续性；否则，它意味着结束编辑或开始编辑另一个文件。（5）可令前三条命令执行后自动调用活区显示。[选作内容]（1）对于命令格式非法等一切错误作严格检查和适当处理。（2）加入更复杂的编辑操作，如对某行进行串替换；在活区内进行模式匹配等，格式可以为S行号@串1@串2回车和m串回车。6、校园导游程序[问题描述]ss用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。[基本要求]（1）查询各景点的相关信息；（2）查询图中任意两个景点间的最短路径。（3）查询图中任意两个景点间的所有路径。（4）增加、删除、更新有关景点和道路的信息。[选作内容]（1）求多个景点的最佳（最短）游览路径。（2）区分机动车道和人行道。（3）实现导游图的仿真界面。7、员工管理系统[问题描述]每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。系统能够完成员工信息的查询、更新、插入、删除、排序等功能。[基本要求]（1）排序：按不同关键字，对所有员工的信息进行排序。（2）查询：按特定条件查找员工。（3）更新：按编号对某个员工的某项信息进行修改。（4）插入：加入新员工的信息。（5）删除：按编号删除已离职的员工的信息。[选作内容]实现图形用户界面。8、算术表达式求值[问题描述]一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。[基本要求]（1）从键盘读入一个合法的算术表达式，输出正确的结果。ss（2）显示输入序列和栈的变化过程。[选作内容]扩充运算符集合。引入变量操作数。操作数类型扩充到实数。9、二叉树及应用（1）二叉树的建立与遍历[问题描述]建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。[基本要求]从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。[测试数据]ABCффDEфGффFффф（其中ф表示空格字符）则输出结果为先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA[选作内容]采用非递归算法实现二叉树遍历。（2）打印二叉树结构[问题描述]按凹入表形式横向打印二叉树结构，即二叉树的根在屏幕的最左边，二叉树的左子树在屏幕的下边，二叉树的右子树在屏幕的上边。例如：ss[测试数据]由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空二叉树。[实现提示]（1）利用RDL遍历方法；（2）利用结点的深度控制横向位置。*2、打印树结构[问题描述]按凹入表形式打印树形结构。例如：[测试数据]由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空树。[实现提示]（1）利用树的先根遍历方法；（2）利用结点的深度控制横向位置。ss10、哈夫曼编码-译码[问题描述]打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，对每一个字符进行编码，编码完成后再对其编码进行译码。利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。[基本要求]一个完整的系统应具有以下功能：（1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree