数据结构与算法 实验教学大纲

数据结构与算法实验教学大纲一课程性质与基本要求数据结构与算法是计算机类专业的一门重要基础课程，是一门理论与工程实践紧密结合的综合性课程，它是研究非数值计算程序设计问题中计算机的操作对象、对象间关系以及常用算法实现原理的课程通过课程学习和实验，加深学生对数据结构和算法理论知识的理解，学会如何分析数据结构的特征，为不同的应用场景选择设计合适的逻辑结构、存储结构以及相应的算法在实验过程中要求学生编写符合软件工程规范的程序，以培养其数据抽象能力和算法设计能力，为后续课程学习和实际工作打下坚实的基础二课程目标本实验教材主要涉及如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价通过实验，使学生深刻理解数据的逻辑结构和物理结构的基本概念以及有关算法，提高程序设计与实现能力实验目标如下目标1:理解数据的物理结构和逻辑结构，具有对抽象数据类型的理解能力目标2掌握常用的数据结构和算法，能根据实际问题构建合适的数据模型，选择或构思合适的算法目标3能根据构思的数据模型和算法编写具有良好风格的实际可运行程序，并对算法的复杂度进行分析三实验环节教学安排序号实验目的实验内容学时实验项目名称任务1方安表格的方式打印显不序顺序表L中的所

1.掌握线性表的顺序存有信息储结构任务2写一个函数删除顺序表L中某一元素顺序表的建立

2.掌握顺序表基本操作2任务3:在有序的顺序表中加入元素后，使表仍然有及操作的算法实现序

13.了解顺序表的应用任务4:将线性表中L的数据保存到一个磁盘文件中

1.掌握线性表的链式存任务1在单链表L中的第i个学生后面插入一个新储结构的表示和实现方学生stu法任务2:统计单链表L中高等数学大于x并且大学英链表的建立及

2.掌握链表基本操作的语大于x的学生人数2操作算法实现任务3在任务2的基础上，将单链表L中高等数2学成绩和大学英语成绩在min_score到max_score之间的学生组织成一个新的单链表L2任务4（选做题）编程实现在带头结点的双向循环链表中插入和删除元素

1.掌握栈的存储结构任务1:两栈共享空间，设计两栈共享空间的数据结的表示和实现方法构，然后完成初始化算法、入栈、出栈等算法任

2.掌握栈的入栈和出务2五子棋游戏中悔棋操作，设计一个悔棋的数栈等基本操作的算法实据结构并设计相关算法栈的建立及操2现任务3（选做题）象棋游戏中的悔棋操作，设计一作3个悔棋的数据结构和相关算法任务4（选做题）表达式求值，实现算术表达式的求值问题，假设表达式中只含加、减、乘、除四种运算符

1.掌握队列存储结构任务1:使用队列打印杨辉三角，写一个函数打印杨的表示和实现方法辉三角前n行

2.掌握队列的入队和任务2设计一个银行排队叫号系统，能模拟顾客到出队等基本操作的算法达取号、银行工作人员准备接待下一位顾客，系统实现检测队列长度、顾客预计等待时间等任务3写一个模拟程序实现键盘输入循环缓冲区假设后两个进程同时存在于一个应用程序中，其中一个进程在屏幕上连续显示字符A,与此同时，程队列的建立及序不断检测键盘是否有输入，如果有输入就读入用2操作户输入的字符并保存到缓冲区中在用户输入时，4键入的字符并不立即回显在屏幕上当用户键入一个逗号”时表示第一个进程结束，第二个进程从缓冲区中读取那些已键入的字符并显示在屏幕上第二个进程结束后，程序又进入第一个进程，重新显示字符“A”，同时用户又可以继续键入字符，直到用户输入一个分号“键，才结束第一个进程，同时也结束整个进程

1.理解二叉树的类型任务1:设计一个函数，根据二叉树的先序遍历序列定义与性质和中序遍历序列建立二叉树例如已知先序遍历序

2.掌握二叉树的二叉列ABCDEFGH和中序遍历序列BDCEAFHG,建立该二链表存储结构的表示和叉树二叉树的建立实现方法任务2实现二叉树中序遍历的非递归操作，设计一2及操作

3.掌握二叉树遍历操个函数，用非递归方法实现对任务1建立的二叉树5进行中序遍历作的算法实现任务3:给定两棵二叉树，判断两棵二叉树是否相等任务4选做题编程求从二叉树根结点到指定结点P之间的路径

1.掌握图的相关概念任务1:用邻接表作为图的存储结构建立一个无向

2.掌握用邻接矩阵和图邻接表的方法描述图的任务2在任务1建立的无向图邻接表的基础上，对存储结构图进行深度优先遍历和广度优先遍历，输出遍历序

3.掌握图的深度优先列，并分析算法的时间复杂度搜索和广度优先搜索遍任务3选做题用邻接矩阵作为图的存储结构建历的方法及其实现方立一个连通网，并构造该网的最小生成树图的建立及操62法任务4选做题校园导航系统用无向图表示你作

4.掌握最小生成树算所在学校的校园景点平面图，图中顶点表示主要景法点，存放景点的编号、名称、简介等信息，图中的

5.掌握最短路径算法边表示景点间的道路，存放路径长度等信息要求实现如下功能1查询各景点的相关信息2查询图中任意两个景点间的最短路径3查询图中任意两个景点间的所有路径

1.理解基于不同查找结任务1:二分查找非递归算法，用二分查找的非递构的查找技术归算法实现范例

22.掌握顺序查找算法任务2二叉排序树，编程实现如下功能

3.掌握二分查找算法1按照输入的n个关键字序列顺序建立二叉排序

4.掌握索引查找算法树，二叉排序树采用二叉链表的存储结构2先输入待查找记录的关键字值key,然后在二叉排序树上查找该记录，如果在二叉排序树中存在该记录，则显示“找到”的信息，否则显示“找不到”的信息3输入待插入记录的关键字值key,然后在二叉7查找2排序树上查找该记录，如果查找失败，则在二叉排序树中插入该记录对应的结点，并输出插入操作后的二叉排序树以某种遍历序列表示4输入待删除记录的关键字值key,然后在二叉排序树上查找该记录，如果查找成功，则在二叉排序树中删除该记录对应的结点，并输出删除操作后的二叉排序树以某种遍历序列表示假设二叉排序树中元素的关键字值类型为int任务3分块查o找选做，编程实现如下功能1建立索引查找表2利用索引查找确定给定记录在索引查找表中的块号和在块中的位置

1.掌握常用的排序方任务1建立顺序表，输入n个学生的姓名和成绩,法，并掌握用高级语言将该顺序表作为待排序序列，利用直接选择排序对实现排序算法的方法待排序序列按成绩从高到低进行排序，并输出排序

2.理解排序的定义和各后的结果，并分析算法的时间和空间复杂度任务种排序方法的特点，并2建立顺序表,输入n个学生的姓名和成绩,将该顺能加以灵活应用序表作为待排序序列，利用希尔排序对待排序序列排序

3.了解各种方法的排按成绩从高到低进行排序，并输出排序后的结果，82序过程及其时间复杂度并分析算法的时间和空间复杂度的分析方法任务3:建立顺序表,输入n个学生的姓名和成绩,将该顺序表作为待排序序列，利用2路归并排序对待排序序列按成绩从高到低进行排序，并输出排序后的结果，并分析算法的时间和空间复杂度

1.理解贪心算法中贪心任务1:用贪心策略求解最优装载问题选择性质有n个集装箱

1、

2、…、n需要装上轮船，集装箱i

2.对于给定的问题，识的重量明,轮船装载重量限制为C,每个集装箱的重别是否适合用贪心算法量小于cW|WC，无体积限制，问如何装使得轮船求解上的集装箱个数最多

3.理解贪心算法的局限任务2用贪心策略解决最小延迟调度问题性，在某些时候贪心算给定等待服务的客户集合A={1,2,…，n},各客户法只能提供近似解的服务时间t,tn,其中客户i的2服务时间为t.如〉0,各客户的期望完成时刻D=d贪心算法bd,…，d„,其中客户i期望的服务完成时刻为292刻一个调度fA-N,f⑴为客户i的开始时刻如果对客户i的服务在《之前结束，那么客户i的服务没有延迟，如果在出之后结束，那么这个服务就被延迟了，延迟的时间等于该服务的实际完成时刻fi+ti减去预期结束时刻d一个调度fio的最大延迟是所有客户延迟时长的最大值max{fi+t］小}要求找出一个调度使得最大延迟达到最小

1.理解回溯法的基本原任务1利用回溯算法求解0T背包问题给定n种理物品和一个背包第i种物品重量为Wi,其价值为回溯法

2.掌握如何定义问题的Vi,其中i=l,2,3,•••,n背包的容量为c问2o状态空间树以及如何在如何选择放入背包的物品，使得放入背包的物品的10树中进行深度优总价值最大。