《数据结构与算法》课程实验内容与要求一、 课程简介本课程着重讲述①线性结构、树型结构、图等典型数据结构的逻辑特点、存储结构及其相应的基本算法。
②各种查找算法③典型内部排序算法。
二、 实验的作用、地位和目的数据结构是一门技术基础课，通过实验深刻理解各种逻辑结构、存储结构的特性，培养为实际问题分析其数据对象、基本操作，选择逻辑结构、存储结构灵活应用基本算法，设计出具有专业水准的应用程序的能力。
三、 实验方式与要求①首先要求学生在课下完成问题分析、算法设计，基本完成程序设计。
②实验时，每位学生使用一台微机，独立调试，完成程序。
③程序调试好后，由指导教师检测运行结果，并要求学生回答相关的问题。
教师评出检查成绩。
④学生记录程序的输入数据，运行结果及源程序。
⑤在一周内完成实验报告。
四、 考核方式与实验报告要求实验成绩由指导教师根据学生的实验完成情况、源程序质量、回答问题情况、实验报告质量、实验纪律等方面给分。
学生在实验后的一周内提交实验报告。
实验报告按照附件中实验报告模版书写。
实验报告中应包括如下内容：实验内容按任课教师下达的实验任务填写（具体实验题目和要求）；实验过程与实验结果应包括如下主要内容：数据结构定义算法设计思路简介算法描述：可以用自然语言、伪代码或流程图等方式算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等算法时间复杂度分析源程序清单与实验结果或其它说明可打印，并装订在实验报告之后。
实验报告雷同者，本次实验成绩为0分或雷同实验报告平分得分五、 实验的软硬件环境硬件环境：PⅡ以上微型计算机软件环境：Windows98/2000, VC++6.0或turbo C六、 实验内容安排实验一线性表应用实验时间：2017年3月9日1-2节（地点：7-219），3月10日5-6节（地点：7-215）实验目的： 理解线性表的逻辑特点；掌握顺序表、链表存储结构，以及线性表的基本操作，如插入、删除、查找，以及线性表合并等操作在顺序存储结构和链式存储结构上的实现算法，并能够在实际问题背景下的灵活运用线性表来解决问题，实现相应算法。
每位同学可从下面题目中选择至少2题实现：其中第一题为必做题1．一元稀疏多项式简单的计算器1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器2）要求: （1）采用单链表存储结构一元稀疏多项式（2）输入并建立多项式（3）输出多项式（4）实现多项式加、减运算3）分析算法时间复杂度2. 约瑟夫环问题1）问题描述：有编号为1, 2…n 的n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。
开始给定一个正整数m，从第一个人按顺时针方向自1开始报数，报到m者出列，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一人开始重新自1开始报数。
如此下去，直到所有人都出列。
试设计算法，输出出列者的序列。
2）要求: 采用顺序和链式两种存储结构实现3）分析算法时间复杂度3．单链表基本操作练习1）问题描述：在主程序中提供下列菜单：1…建立链表2…连接链表3…输出链表0…结束2）实验要求：算法中包含下列过程，分别完成相应的功能：CreateLinklist(): 从键盘输入数据，创建单链表ContLinklist()：将前面建立的两个单链表首尾相连OutputLinklist()：输出显示单链表3）分析算法时间复杂度4．单链表基本操作练习1）问题描述：已知单链表L（带头节点）是一个递增有序表，试编写算法，删除表中值大于min且小于max的节点（若表中有这样的节点），同时释放被删节点的空间。
2）实验要求：min和max是两个给定参数。
3）分析算法时间复杂度实验报告格式及要求：按附件中实验报告模版书写。
（具体要求见四）实验二栈与队列应用实验时间：2017年3月20日3-4节（地点：7-219），3月23日1-2节（地点：7-220）实验目的：1、理解栈和队列的逻辑特点；掌握栈和队列基本操作的实现，并能灵活运用栈或队列特性，综合运用程序设计、算法分析等知识解决实际问题。
2、实验设置较高要求：理解组成递归算法的基本条件，理解递归算法与相应的非递归算法的区别，理解栈和队列的应用与作用。
具体实验题目：（任课教师根据实验大纲自己指定）每位同学从下面题目中至少选择2题实现：其中1,2题中至少选择1题，3-5题中至少选择1题 1．十进制数与N进制数据的转换1）问题描述：将从键盘输入的十进制数转换为N（如二进制、八进制、十六进制）进制数据。
2）要求: 利用顺序栈实现数制转换问题2．表达式语法判读：1）问题描述：假设表达式中允许包含3种括号：圆括号、方括号和大括号，编写一个算法判断表达式中的括号是否正确配对。
2）要求：输出信息提示表达式中括号是否匹配，属于哪类不匹配（如左括号多？右括号多）。
3. 算术表达式求值算法1）问题描述：从键盘输入一个算术表达式并输出它的结果2）要求：算术表达式可包含加、减、乘、除、十进制整数和小括号，利用栈实现4. 停车场管理问题1）问题描述：设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。
车辆按到达停车场的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。
如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车走开，则排在便道上的第一辆车就进入停车场。
停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。
每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。
如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。
编写程序模拟该停车场的管理。
2）要求：要求程序输出每辆车到达后的停车位置（停车场或便道上），以及某辆车离开停车场时应缴纳的费用和他在停车场内停留的时间3）实现提示：以栈模拟停车场，以队列模拟便道，按照从终端读入的车辆“到达”“离开”信息模拟停车场管理5、迷宫问题：1）问题描述：设计算法完成迷宫问题求解，输出迷宫中所有路径的求解。
2）要求：使用递归算法和非递归两种方法实现实验报告格式及要求：按附件中实验报告模版书写。
（具体要求见四）实验三二叉树操作实验时间：2017年4月20日1-2节（地点：7-220），4月21日5-6节（地点：7-220）实验目的：理解二叉树的逻辑特点和二叉树的性质；掌握二叉树的二叉链表存储结构，掌握二叉树的创建算法、遍历算法的递归与非递归实现。
具体实验题目：（任课教师根据实验大纲自己指定）第1题为必做题，第2题为选做题目：1.每位同学按下述要求实现相应算法：以二叉链表为存储结构，实现二叉树的创建、遍历算法1）问题描述：在主程序中提供下列菜单：1…建立树2…前序遍历树3…中序(非递归)遍历树4…后序遍历树0…结束2）实验要求：①定义下列过程：CreateTree(): 按从键盘输入的前序序列，创建树PreOrderTree()：前序遍历树（递归）InOrderTree()：中序(非递归)遍历树LaOrderTree(): 后序遍历树（递归）②每位同学在实验过程中要单步运行程序，跟踪二叉树的创建过程与前序遍历的递归过程。
2. 树的转换：我们都知道用“孩子兄弟”表示法可以将一棵一般的树转换为二叉树。
请设计算法将一棵树用这种方法转换为二叉树，并输出转换前和转换后树的前序遍历序列。
实验报告格式及要求：按附件中实验报告模版书写。
（具体要求见四）实验四图的深度优先与广度优先遍历实验时间：2017年5月11日，1-2节（地点：7-215），5月12日5-6节（地点：7-216）实验目的：理解图的逻辑特点；掌握理解图的两种主要存储结构（邻接矩阵和邻接表），掌握图的构造、深度优先遍历、广度优先遍历算法。
具体实验题目：（任课教师根据实验大纲自己指定）第1题为必做题，第2题为选做题目：1. 每位同学按下述要求实现相应算法： 根据从键盘输入的数据创建图（图的存储结构可采用邻接矩阵或邻接表），并对图进行深度优先搜索和广度优先搜索1）问题描述：在主程序中提供下列菜单：1…图的建立2…深度优先遍历图3…广度优先遍历图0…结束2）实验要求：图的存储可采用邻接表或邻接矩阵；定义下列过程：CreateGraph(): 按从键盘的数据建立图DFSGrahp()：深度优先遍历图BFSGrahp()：广度优先遍历图2. 拓扑排序：给出一个图的结构，输出其拓扑排序序列（顶点序列用空格隔开），要求在同等条件下，编号小的顶点在前。
实验报告格式及要求：按附件中实验报告模版书写。
（具体要求见四）实验五查找算法应用实验时间：2016年6月1日1-2节（地点：7-215），6月2日5-6节（地点：7-216）实验目的：理解二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现；掌握散列存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散列表的查找、建立。
散列表等查找算法解决实际问题。
具体实验题目：（任课教师根据实验大纲自己指定）每位同学可从下面题目中选择1-2题实现：1．哈希表查找1）问题描述：针对某个集体的“人名”构造哈希表，解决按“人名”进行查找的索引结构。
2）实验要求：要求表的平均查找长度不超过R（R可以从键盘输入确定），完成相应的建表和查表程序。
2．构造二叉排序树，并进行中序遍历1）问题描述：从键盘读入一串整数构造一棵二叉排序树，并对得到的二叉排序述进行中序遍历，得到有序序列。
2）实验要求：该二叉排序树以二叉链表存储3. 拼写检查1）问题描述：现在有一些英语单词需要做拼写检查，你的工具是一本词典。
需要检查的单词，有的是词典中的单词，有的与词典中的单词相似，你的任务是发现这两种情况。
单词A与单词B相似的情况有三种：①删除单词A的一个字母后得到单词B；②用任意一个字母替换单词A的一个字母后得到单词B；③在单词A的任意位置增加一个字母后得到单词B。
2）实验要求：发现词典中与给定单词相同或相似的单词。
实验报告格式及要求：按附件中实验报告模版书写。
（具体要求见四）。