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

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

一、课程性质与基本要求

数据结构与算法是计算机类专业的一门重要基础课程，是一门理论与工程实践紧密结合的综合性课程，它是研究非数值计算程序设计问题中计算机的操作对象、对象间关系以及常用算法实现原理的课程。

通过课程学习和实验，加深学生对数据结构和算法理论知识的理解，学会如何分析数据结构的特征，为不同的应用场景选择设计合适的逻辑结构、存储结构以及相应的算法。在实验过程中要求学生编写符合软件工程规范的程序，以培养其数据抽象能力和算法设计能力，为后续课程学习和实际工作打下坚实的基础。

二、课程目标

本实验教材主要涉及如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过实验，使学生深刻理解数据的逻辑结构和物理结构的基本概念以及有关算法，提高程序设计与实现能力。

实验目标如下：

目标1：理解数据的物理结构和逻辑结构，具有对抽象数据类型的理解能力。

目标2：掌握常用的数据结构和算法，能根据实际问题构建合适的数据模型，选择或构思合适的算法。

目标3：能根据构思的数据模型和算法编写具有良好风格的实际可运行程序，并对算法的复杂度进行分析。

三、实验环节教学安排

序号

实验项目名称

实验目的

实验内容

学时

1

顺序表的建立及操作

1.掌握线性表的顺序存储结构。

2.掌握顺序表基本操作的算法实现。

3.了解顺序表的应用。

任务1：按表格的方式打印显示序顺序表L中的所有信息。

任务2：写一个函数删除顺序表L中某一元素。

任务3：在有序的顺序表中加入元素后，使表仍然有序。

任务4：将线性表中L的数据保存到一个磁盘文件中。

2

2

链表的建立及操作

1.掌握线性表的链式存储结构的表示和实现方法。

2.掌握链表基本操作的算法实现。

任务1：在单链表L中的第i个学生后面插入一个新学生stu。

任务2：统计单链表L中高等数学大于x并且大学英语大于x的学生人数。

任务3：在任务2的基础上，将单链表L中高等数学成绩和大学英语成绩在min_score到max_score之间的学生组织成一个新的单链表L2。

任务4（选做题）：编程实现在带头结点的双向循环链表中插入和删除元素。

2

3

栈的建立及操作

1．掌握栈的存储结构的表示和实现方法。

2．掌握栈的入栈和出栈等基本操作的算法实现。

任务1：两栈共享空间，设计两栈共享空间的数据结构，然后完成初始化算法、入栈、出栈等算法。

任务2：五子棋游戏中悔棋操作，设计一个悔棋的数据结构并设计相关算法。

任务3（选做题）：象棋游戏中的悔棋操作，设计一个悔棋的数据结构和相关算法。

任务4（选做题）：表达式求值，实现算术表达式的求值问题，假设表达式中只含加、减、乘、除四种运算符。

2

4

队列的建立及操作

1．掌握队列存储结构的表示和实现方法。

2．掌握队列的入队和出队等基本操作的算法实现。

任务1：使用队列打印杨辉三角，写一个函数打印杨辉三角前n行。

任务2：设计一个银行排队叫号系统，能模拟顾客到达取号、银行工作人员准备接待下一位顾客，系统检测队列长度、顾客预计等待时间等。

任务3：写一个模拟程序实现键盘输入循环缓冲区。假设有两个进程同时存在于一个应用程序中，其中一个进程在屏幕上连续显示字符‘A’，与此同时，程序不断检测键盘是否有输入，如果有输入就读入用户输入的字符并保存到缓冲区中。在用户输入时，键入的字符并不立即回显在屏幕上。当用户键入一个逗号“，”时表示第一个进程结束，第二个进程从缓冲区中读取那些已键入的字符并显示在屏幕上。第二个进程结束后，程序又进入第一个进程，重新显示字符“A”，同时用户又可以继续键入字符，直到用户输入一个分号“；”键，才结束第一个进程，同时也结束整个进程。

2

5

二叉树的建立及操作

1．理解二叉树的类型定义与性质。

2.掌握二叉树的二叉链表存储结构的表示和实现方法。

3．掌握二叉树遍历操作的算法实现。

任务1：设计一个函数，根据二叉树的先序遍历序列和中序遍历序列建立二叉树。例如已知先序遍历序列ABCDEFGH和中序遍历序列BDCEAFHG，建立该二叉树。

任务2：实现二叉树中序遍历的非递归操作，设计一个函数，用非递归方法实现对任务1建立的二叉树进行中序遍历。

任务3：给定两棵二叉树，判断两棵二叉树是否相等。

任务4（选做题）：编程求从二叉树根结点到指定结点p之间的路径。

2

6

图的建立及操作

1．掌握图的相关概念。

2．掌握用邻接矩阵和邻接表的方法描述图的存储结构。

3．掌握图的深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站遍历的方法及其实现方法。

4．掌握最小生成树算法。

5.掌握最短路径算法。

任务1：用邻接表作为图的存储结构建立一个无向图。

任务2：在任务1建立的无向图邻接表的基础上，对图进行深度优先遍历和广度优先遍历，输出遍历序列，并分析算法的时间