数据结构课程设计.doc

Project1简单编译器表达式处理的模拟（一） 语法检查1） 括号匹配的检验【问题描述】假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（() ）或( )等为正确表达式， ( )或( ( ( 均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列： ( ) 1 2 3 4 5 6 7 8当计算机接受了第一个括号以后，他期待着与其匹配的第8个括号的出现，然而等来的却是第二个括号，此时第一个括号” “ 只能暂时靠边，而迫切等待与第二个括号相匹配的第7个括号的出现，类似的，因只等来了第三个括号“,此时，其期待的紧迫程度较第二个括号更紧迫，则第二个括号只能靠边，让位于第三个括号，显然第三个括号的期待紧迫程度高于第2个，而第二个括号的期待紧迫程度高于第一个括号； 在接受了第4个括号之后，第三个括号的群殴带得到了满足，消解之后，第二个括号的期待匹配就成了最紧迫的任务了，.,依次类推。 可见这个处理过程正好和栈的特点相吻合。【基本要求】读入圆括号和方括号的任意序列，输出“匹配” 或 “此串括号匹配不合法”。【测试数据】输入（ （ ） ），结果“匹配”输入 ( ) ,结果“此串括号匹配不合法”【测试提示】 设置一个栈，每读入一个括号，若是左括号，则作为一个新的更紧迫的期待压入栈中；若是右括号，并且与当前栈顶的左括号相匹配，则将当前栈顶的左括号退出，继续读下一个括号，如果读入的右括号与当前栈顶的左括号不匹配，则属于不合法的情况；在初始和结束时，栈应该是空的。【选作内容】考虑增加大括号的情况2） 表达式合法性检查【问题描述】假设表达式中允许初显的运算符有+ 、-、*、 /、%共五种，不允许省略运算符，且都是双目运算符，要求设计算法检查输入的表达式是否符合书写规范。【基本要求】 如果通过合法检查，则进入下一个环节求值； 如果不合法，则应像编译器一样，根据不同的错误种类给出相应的提示。（二） 表达式求值 【问题描述】 如果输入的表达式通过语法检查，设计算法模拟完成对表达式求值的过程。【实现提示】 利用栈完成后表达式求值过程，可以有不同的方法。如：使用符号表；使用后缀表达式；使用二叉树等。 Project2.停车场管理【问题描述】设停车场是一个可停放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).每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，A表示到达；D表示离去；E表示输入结束。【基本要求】以栈模拟停车场，以队列模拟车场外的便道。按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去，则输出汽车在停车场内停留的时间和应缴纳的费（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。【实现提示】需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包括两个数据项：汽车的牌照号码和进入停车场的时刻。【选作内容】 两个栈共享空间，思考应开辟数组的空间是多少？ 汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如一辆客车和1.5辆小汽车的占地面积相同，一辆十轮卡车占地面积相当于3辆小汽车的占地面积。 汽车可以直接从便道开走，此时排在它前面的汽车要先开走让道，然后再依次排到队尾。 停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。Project 3. 文学研究助手和简单编辑程序的实现本项目的目的是熟悉串类型的实现方法和文本模式匹配方法，熟悉一般文字处理软件的设计方法，较复杂问题的分解求精方法，进一步强化这样一个观念：程序是数据结构结合定义在其上的操作，此外还希望起到训练合作能力和熟悉文件操作的目的。（一）文学研究助手问题描述文学研究人员统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。基本要求英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。测试数据以你的源程序模拟英文小说，程序语言保留字集作为待统计的词汇集。实现提示设小说的词汇一律不跨行。这样，每读入一行，就统计这个词在这行中出现的次数。出现位置在所在行的行号可以用链表存储。若某行中出现了不止一次，不必存多个相同的行号。如果读者希望达到选作部分（1）和（2）所提出的要求，则首先啊、把KMP算法改写成如下的等价形式，再将它推广到多个模式的情形。选作内容（1） 模式匹配要基于KMP算法。（2） 整个统计过程只对小说文字扫描一遍以提高效率。（3） 假设小说中的每个单词或者从行首开始，或者前置一个空格符。利用单词匹配特点另写一个高效的统计程序，与KMP算法统计程序进行效率比较。（4） 推广到更一般的模式集匹配问题，并设待查模式串可以跨行（提示：定义操作getchar（）（二）简单编辑程序问题描述 文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作和统计字符个数、统计单词个数等静态操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。可以在全屏幕上进行这些操作的编辑程序叫做全屏幕编辑工具。被编辑的文本文件可能很大，全部读入编辑程序的数据空间（内存）的做法既不经济，也不总能实现。一种解决方法是逐段地编辑。任何时刻只把待编辑文件的一段放在内存，称为活区。试按照这种方法实现一个简单的行编辑程序。设文件每行不超过320个字符，很少超过80字符。基本要求方向一、以单文档界面为基础，设计实现一个全屏幕编辑程序（类似记事本，但和记事本功能有所不同），并在该程序中实现主要的文本编辑的基本命令，命令可以放在菜单项中。方向二、以命令形式的界面为基础，设计实现一个行编辑工具，主要实现以下四条基本行编辑命令：（1） 行插入。格式：i 将插入活区中第行之后（2） 行删除。格式：d1删除活区中第行（到第行）。两种格式的例子是：“d10”和“d1014”（3）活区切换。格式：n将活区写入输出文件，并从输入文件中读入下一段，作为新的活区。（4）活区显示。格式：P逐页的（每页20行）显示活区内容，没显示一页后请用户决定是否继续显示以后各页（如果存在）。印出的每一行要前置以行号和一个空格符，行号固定占4位，增量为1. 各条命令中的行号均须在活区中各行行号范围之内，只有茶如命令的行号可以等于活区第一行行号减1，表示插入当前屏幕中第一行之前，否则命令参数非法。测试数据 由学生依据软件工程的测试技术自己确定。注意测试边界数据，如首行、尾行。实现提示（1） 设活区的大小用行数activemaxlen（可设为100）来描述。考虑到文本文件行长通常为正态分布，且峰值在60到70之间，用320*activemaxlen大小的字符数组实现存储将造成大量浪费。可以以标准行块为单位为各行分配存储，每个标准行块含81个字符。这些行块可以组成一个数组，也可以利用动态链表连接起来。一行文字可能占多个块。行尾可用一个特殊的ASCII字符标识。此外，还应该记住活区起始行号。行插入将引起随后各行行号的顺序下推。（2） 初始化过程包括：请用户提供输入文件名（空格表示无文件输入）和输出文件名，两者不能相同。然后尽可能多的从输入文件中读入各行，但不超过activemaxlen-x。x 的值可用自定。（3） 在执行插入命令的过程中，每接收到一行时倒要检查活区大大小是否已达activemaxlen。如果是，则为了在插入这一行之后仍保持活区大小不超过activemaxlen，应将插入点之前的活区部分中第一行输出到输出文件中，若插入点为第一行之前，则只得将新插入的这一行输出。（4） 若输入文件尚未读完，活区切换命令可将原活区中最后几行留在活区顶部，以保持阅读连续性；否则，它意味着结束编辑或开始编辑另一个文件。（5） 可令前三条命令执行后自动调用活区显示。选作内容（1） 对于命令格式非法等一切错误作严格检查和适当处理。（2） 加入更复杂的编辑操作，如对某行进行串替换；在活区内进行模式匹配等，格式可以为S和m。project 4.递归与回溯（一）迷宫求解【问题描述】可以输入一个人任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出。【基本要求】在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法或者递归和非递归的转换方法等。（二）八皇后问题【问题描述】八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8*8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出了92种结果。【基本要求】对于八皇后问题的实现，如果结合动态的图形演示，则可以使算法的描述更形象、生动。要求编写程序试图求出八皇后的所有解（全部的92组解）。 Project5.图论应用（一） 图遍历的演示问题描述 很多涉及图上操作的运算都是以图的遍历操作作为基础的。试写一个程序，演示无向图的遍历操作。基本要求 以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。测试数据 由学生依据软件工程的测试技术自己确定。注意测试边界数据，如单个结点。实现提示 设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则他们的编号分别为1，2，3，n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。选作内容 （1） 借助于栈类型（自己定义和实现）将深度优先遍历用非递归算法实现。（2） 以邻接多重表为存储结构建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。（3） 实现有向图的遍历操作。（二） 交通图最短路径问题描述 自定义一个交通图（如：校园、小镇、某城市），并给出各地点之间的距离，求从某地出发到达目的地的最短路径。基本要求 输入出发地和目的地名称，输出找到的最短路径。实现提示 原始数据最好采用文件存储，以节省输入；将地名和顶点的编号信息存储到一个表中，可以实现输入的实际数据到程序中处理的抽象数据之间的转换。测试数据 自定。 Project6.检索算法模拟（一）动态查找表问题描述 从键盘读入一组数据，建立二叉排序树并对其进行查找、遍历、格式化打印等有关操作。基本要求 建立二叉排序树并对其进行查找，包括成功和不成功两种情况，并给出查找长度；为提高检索效率，要求在检索过程中进行平衡化处理。测试数据 由学生依据软件工程的测试技术自己确定。注意测试边界数据。选作内容 实现二叉排序树的插入、删除操作。（二）哈希表设计问题描述 针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。测试数据 取读者周围较熟悉的30个人名。选作内容 （1）从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较他们的地址冲突率（可以用更大的名字集合做实验）。 （2）研究30个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。 （3）在哈希函数确定的前提下尝试各种不同处理冲突的方法，考察平均查找长度的变化和造好的哈希表中的关键字的聚集性。Project 7.数据压缩传输过程模拟【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对传输数据预先编码，在接收端将传来的数据进行译码。对于双工信道，每端都要有一个完整的编译码系统，试为这样的通信端编码写一个哈夫曼编译码系统。【基本功能】一个完整的系统应具有以下功能：初始化：输入一串字符（正文），计算不同字符（包括空格）的数目以及每种字符出现的频率（出现次数），根据权值建立哈夫曼树，输出每一个字符的哈夫曼编码。编码：利用求出的哈夫曼编码，对该正文（字符串）进行编码，并输出。译码：对于得到的一串编码，利用已求得的哈夫曼编码进行译码，将译出的正文输出。输出哈夫曼树形态，以树的形式输出哈夫曼树【运行流程】【测试数据】A. 初始化1. 输入正文“there are three students“2. 统计字符出现的次数并输出字符 a d e h n r s t u 空格次数 1 1 6 2 1 3 2 4 1 33. 根据字符出现的次数求出哈夫曼编码并输出字符 a d e h n r s t u 空格编码 0000 0001 01 1110 0010 100 1111 110 0011 1014. 以树的形式输出哈夫曼树B. 编码：发送方利用得到的哈夫曼编码对正文进行编码，输出密文11011100110001101000010001101110111010001011011111110001100010100101101111C. 译码：接收方利用哈夫曼对密文进行译码，输出译后的字符串应为：there are three studentsojectProject8 城市公交线路