《数据结构综合实验》由会员分享，可在线阅读，更多相关《数据结构综合实验（15页珍藏版）》请在金锄头文库上搜索。
1、数据结构综合实验具体课程设计报告要求如下：一需求分析：在该部分中根据设计题目的要求，充分地分析和理解问题， 叙述系统的功能要求，明确问题要求做什么？以及限制条件是什么？1. 1问题描述1. 2基本要求(1) 输入的形式和输入值的范围；(2) 输出的形式；(3) 程序所能达到的功能；二概要设计说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。1、数据结构2、程序模块3、各模块之间的调用关系以及算法设计三详细设计实现概要设计中定义的所有数据类型，对每个操作写出 c语言算法;对主程序和其他模块也都需要写出c语言算法；写出出函数和过程的调用关系 四测试与分析测
2、试数据，输出测试的结果，这里的测试数据应该完整和严格。并对结果进行分析。五总结总结可以包括：课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对数据结构课程的认识等内容。六附录：源程序清单。参考题目(可以选其他题目)：一、括号匹配的检验【问题描述】 假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即()或()等为正确表达式，()或(均为不正确的格式。检验括号是否匹配的方法可 用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列：()12345678当计算机接受了第一个括号以后，他期待着与其匹配的第8个括
3、号的出现，然而等来的却是第二个括号，此时第一个括号”“只能暂时靠边，而迫切等待与第二个括号相匹配的第7个括号的出现，类似的，因只等来了第三个括号“,此时，其期待的紧迫程度较第二个括号更紧迫，则第二个括号只能靠边，让位于第三个括号，显然第三个括号的期待紧迫程度高于第2个，而第二个括号的期待紧迫程度高于第一个括号；在接受了第4个括号之后，第三个括号的群殴带得到了满足，消解之后，第二个括号的期待匹配就成了最紧迫的任务 了，依次类推。 可见这个处理过程正好和栈的特点相吻合。【基本要求】 读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”。【测试数据】 输入()，结果“匹配”输入(),结
4、果“此串括号匹配不合法”【测试提示】设置一个栈，每读入一个括号，若是左括号，则作为一个新的更紧迫的期待压入栈中；若是右括号，并且与当前栈顶的左括号相匹配，则将当前栈顶的左括号退出，继续读下一个括号，如果读入的右括号与当前栈顶的左括号不匹配，则属于不合法的情况； 在初始和结束时，栈应该是空的。、表达式合法性检查【问题描述】 假设表达式中允许初显的运算符有 +、-、*、 /、%共五种，不允许省略运 算符，且都是双目运算符，要求设计算法检查输入的表达式是否符合书写规范。【基本要求】 如果通过合法检查，则进入下一个环节一一求值；如果不合法，则应像编译 器一样，根据不同的错误种类给出相应的提示。三、停车
5、场管理【问题描述】设停车场是一个可停放 n辆汽车的狭长通道，且只有一个大门可供汽车进出。 汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列(大门在最南端，最先到达的第一辆车停放在车场的最北端)，若车场内已停满 n辆汽车，则后来的汽车只能在门外的 便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在他之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。【测试数据】 设 n=2,输入数据为： A 1，5)， A 2，
6、10)，( D ,1,15) ,( A ,3, 20), ( A ,4,25) ,( A ,5,30),( D ,2,35),( D ,4,40),( E ,0,0).每一组输入数据包括三 个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，A 表示到达；D 表示离去；E 表示输入结束。【基本要求】以栈模拟停车场，以队列模拟车场外的便道。按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌 照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达， 则输出汽车在停车场内或便道上的停车位置；若是车
7、离去，则输出汽车在停车场内停留的时间和应缴纳的费(在便道上停留的时间不收费)。栈以顺序结构实现，队列以链表实现。【实现提示】需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车， 包括两个数据项：汽车的牌照号码和进入停车场的时刻。四、实现一个简单的行编辑程序。问题描述文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作和统计字符个数、统计单词个数等静态操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。可以在全屏幕上进行这些操作的编辑程序叫做全屏幕编 辑工具。
8、被编辑的文本文件可能很大，全部读入编辑程序的数据空间(内存)的做法既不 经济，也不总能实现。一种解决方法是逐段地编辑。任何时刻只把待编辑文件的一段放在内 存，称为活区。试按照这种方法实现一个简单的行编辑程序。设文件每行不超过 320个字符，很少超过80字符。基本要求方向一、以单文档界面为基础，设计实现一个全屏幕编辑程序(类似记事本，但和记事本功能有所不同），并在该程序中实现主要的文本编辑的基本命令，命令可以放在菜单项中。方向二、以命令形式的界面为基础，设计实现一个行编辑工具，主要实现以下四条基本行 编辑命令：（1）行插入。格式：i行号 回车 文本 回车 将 文本 插入活区中第行号行之后（2）行
9、删除。格式：d行号1 行号2回车 删除活区中第 行号1行（到第 行号 2行）。两种格式的例子是：“d10/”和“ d10口 14/”（3 ）活区切换。格式：*回车 将活区写入输出文件，并从输入文件中读入下一段，作为新的活区。（4）活区显示。格式：P回车 逐页的（每页 20行）显示活区内容，没显示一页后请用 户决定是否继续显示以后各页（如果存在）。印出的每一行要前置以行号和一个空格符，行号固定占4位，增量为1. 各条命令中的行号均须在活区中各行行号范围之内，只有茶如 命令的行号可以等于活区第一行行号减1,表示插入当前屏幕中第一行之前，否则命令参数非法。测试数据由学生依据软件工程的测试技术自己确定
10、。注意测试边界数据，如首行、尾行。实现提示（1）设活区的大小用行数 activemaxlen （可设为100）来描述。考虑到文本文件行长通常 为正态分布，且峰值在60到70之间，用320*activemaxlen大小的字符数组实现存储将造成 大量浪费。可以以标准行块为单位为各行分配存储，每个标准行块含81个字符。这些行块可以组成一个数组，也可以利用动态链表连接起来。一行文字可能占多个块。行尾可用一个特殊的ASCII字符标识。此外，还应该记住活区起始行号。行插入将引起随后各行行号的 顺序下推。（2）初始化过程包括：请用户提供输入文件名（空格表示无文件输入）和输出文件名，两 者不能相同。然后尽可能
11、多的从输入文件中读入各行，但不超过activemaxlen-x。x的值可用自定。（3）在执行插入命令的过程中，每接收到一行时倒要检查活区大大小是否已达 activemaxlen。如果是，则为了在插入这一行之后仍保持活区大小不超过activemaxlen，应将插入点之前的活区部分中第一行输出到输出文件中，若插入点为第一行之前，则只得将新插入的这一行输出。（4）若输入文件尚未读完，活区切换命令可将原活区中最后几行留在活区顶部，以保持阅读连续性；否则，它意味着结束编辑或开始编辑另一个文件。（5）可令前三条命令执行后自动调用活区显示。五、迷宫求解【问题描述】可以输入一个人任意大小的迷宫数据，用非递归的
12、方法求出一条走出迷宫的路径，并将路径输出。【基本要求】 在上交资料中请写明： 存储结构、基本算法（可以使用程序流程图）、源程序、 测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法或者递归和非递归的转 换方法等。六、 八皇后问题【问题描述】八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8*8格的国际象棋上摆放 8个皇后，使其不能互相攻击，即任意两个皇后不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出了92种结果。【基
13、本要求】对于八皇后问题的实现，如果结合动态的图形演示，则可以使算法的描述更形象、生动。要求编写程序试图求出八皇后的所有解（全部的92组解）。七、哈希表设计问题描述针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R,并完成相应的建表和查表程序。基本要求假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为 2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处 理冲突。测试数据取读者周围较熟悉的 30个人名。F面是古文鉴赏，不需要的朋友可以下载后编辑删除！谢谢！九歌湘君屈原朗诵：路英君不行兮夷犹，蹇谁留兮中洲。美要眇兮宜修，沛吾乘兮桂舟。令沅湘兮无
14、波，使江水兮安流。望夫君兮未来，吹参差兮谁思。驾飞龙兮北征，邅吾道兮洞庭。薜荔柏兮蕙绸，荪桡兮兰旌。望涔阳兮极浦，横大江兮扬灵。扬灵兮未极，女婵媛兮为余太息。横流涕兮潺湲，隐思君兮陫侧。桂棹兮兰枻，斫冰兮积雪。采薜荔兮水中，搴芙蓉兮木末。 心不同兮媒劳，恩不甚兮轻绝。石濑兮浅浅，飞龙兮翩翩。交不忠兮怨长，期不信兮告余以不闲。朝骋骛兮江皋，夕弭节兮北渚。她含着笑，切着冰屑悉索的萝卜,她含着笑，用手掏着猪吃的麦糟， 她含着笑，扇着炖肉的炉子的火， 她含着笑，背了团箕到广场上去晒好那些大豆和小麦，大堰河，为了生活， 在她流尽了她的乳液之后， 她就用抱过我的两臂，劳动了。大堰河，深爱着她的乳儿；在年节里，为了他，忙着切那冬米的糖，为了他，常悄悄地走到村边的她的家里去，为了他，走到她的身边叫一声妈，大堰河，把他画的大红大绿的关云长 贴在灶边的墙上，大堰河，会对她的邻居夸口赞美她的乳儿; 大堰河曾做了一个不能对人说的梦： 在梦里，她吃着她的乳儿的婚酒， 坐在辉煌的结彩的堂上，而她的娇美的媳妇亲切的叫她“婆婆” 大堰河，深爱她的乳儿！大堰河，在她的梦没有做醒的时候已死了。 她死时，乳儿不在她的旁侧，她死时，平时打骂她的丈夫也为她流泪， 五个儿子，个个哭得很悲，她死时，轻轻地呼着她的乳儿的名字， 大堰河，已死了，她死时，乳儿不在她的旁侧。大堰河，含泪的去了！同着四
