考研 期末 数据结构实验大纲.docVIP

实验大纲 实验目的：掌握线性表的顺序存储结构和链式存储结构。 实验内容：编写计算两个多项式相乘P x Q x R x 的函数 实验要求：独立编写程序并上机完成，输出正确结果。 实验二：迷宫求解 实验目的：掌握栈和队列两种数据类型及其存储结构。 实验内容：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 实验要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一座标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2）,…。 实验三：Huffman树及Huffman编码的算法实现 实验目的：掌握哈夫曼树。 实验内容：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。 实验要求： 编写完整的系统，要求具有以下功能： 1、?I:初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存入文件hfmTree中。 2、?E:编码 Encoding 。利用以建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 3、?D：译码 Decoding 。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 4、?P:印代码文件（Print 。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 5、?T:印哈夫曼树 Tree?printing 。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。 实验四：校园导游咨询 实验目的：掌握图的存储方法和最短路经算法。 实验内容：设计一个校园导游程序，为来访客人 实验要求： 1、设计所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 2、为来访客人提供图中任意景点相关信息的查询。 3、为来访客人提供图中任意景点的纹路查询，即查询任意两个景点之间的一条最短的简单路径。 实验一 必做,?基本实验，4学时 实验题目：多项式乘法问题 设计一个一元稀疏多项式简单计算器。实验内容与要求?一元稀疏多项式简单计算器的基本功能是：???（1 输入并建立多项式；???（2）输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,...,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列。???（3）多项式a与多项式b相乘，建立多项式。 实验用测试数据和相关结果分析：（由学生填写） 实验总结：（由学生填写） 实验二 必做,?设计性实验，4学时 实验题目：迷宫的求解 实验内容与要求 迷宫只有两个门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到出口的路径。【知识要点】 迷宫问题是栈应用的一个典型例子。求解过程可采用回溯法。回溯法是一种不断试探且及时纠正错误的有哪些信誉好的足球投注网站方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向?;?若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的下标及从该点前进的方向，栈中保存的就是一条迷宫的通路。 为了确保程序能够终止，调整时，必须保证曾被放弃过的填数序列不被再次试验，即要求按某种有序模型生成填数序列。给解的候选者设定一个被检验的顺序，按这个顺序逐一生成候选者并检验。【实现提示】 对于迷宫问题，用回溯法的难点就在如何为解空间排序，以确保曾被放弃过的填数序列不被再