《数据结构与算法实践》课程教学大纲

数据结构与算法实践

一、课程概况

所属专业：软件工程开课单位：数学计算机科学学院

课程类型：专业实践课程课程代码：07414310

开课学期：4学分：1.5

学时：51核心课程：否

拟使用教材：

徐慧.数据结构与算法实验实践教程[M].清华大学出版社,2012.

国内（外）现有教材：

1.齐悦等著.数据结构、算法与应用[M].清华大学出版社,2015.

2.李文书.数据结构与算法应用实践教程（第2版）[M].北京大学出版社,

2015.

学习参考资料：

1.严蔚敏、吴伟民著.数据结构（C语言版）[M].北京：清华大学出版社,2007.

2.宁正元等著.数据结构习题解析与上机实验指导[M].北京：中国水利水电

出版社,2000.

二、课程描述

数据结构是计算机科学的算法理论基础和软件设计的技术基础，是计算机专

业的核心课程。本课程实验采用实验教学和学生实验相结合方式，使学生掌握数

据结构的基本原理和编程方法达到提高学生分析问题和解决问题的能力的目的。

通过实验环节，学生应学会和掌握本课程的基本和重点知识；理解数据结构的基

本概念和基本原理,深刻理解逻辑结构、物理结构、算法设计之间的关系，掌握

分析问题，建立模型，运用程序进行问题求解的方法。本课程是一门实践性极强的

程序设计课程，旨在培养学生的实际动手能力，加强学生创新思维能力的培养。

三、课程目标

数据结构与算法实践课程将覆盖计算机软件实现中的大部分算法，并具有一

定的深度和广度，使学生对计算机常用算法有一个全盘的了解;通过此课的学习，

学生应该具有针对所给的问题设计和实现高效算法的能力。通过上机实验，将使

学生熟悉、掌握课堂教学中所学的大部分算法。同时，上机实习是对学生在软件

设计方面的综合训练，包括问题分析，总体结构设计，用户界面设计，程序设计

基本技能和技巧等，以培养良好的编程风格和科学作风。通过理论联系实际，以

最终提高学生动手操作的能力以及分析问题的能力。

四、教学要求

本课程由15组设计性实验和2组综合性大实验构成，每次实验课，授课教

师将对学生的相关基础知识进行传授，并对实验的基本要求进行分析讲解，指导

学生做好实验方案设计、实验提交等工作。对学生分组设计实现某个简单系统以

完成综合性作业。

学生应熟悉遵守实验室管理相关规章制度，按时完成各项实验工作。参与实

践课程教学活动不迟到、不早退，无正当理由不请假，上课认真听讲，不做任何

与实践课堂教学无关事宜，不使用手机，积极与授课教师进行实践互动。实验完

成后做好撰写实验报告提交工作，并对最后的综合实验做好系统的演示或者讲解

工作。

五、考核方式及要求

为实现课程教学目标，本门课程考核采用平时成绩、实验考核与综合实验相

结合的方式进行。

平时成绩用于考察学生考勤、参与课程教学的行为表现，占课程总成绩的

30%；

实验考核主要用于检验学生对于实验原理与实验完成情况，占课程总成绩的

40%；

综合实验考核为教师出题和学生自主选题相结合完成某项系统，根据系统功

能、代码完成情况、实验报告撰写情况与答辩结果进行评分，占课程总成绩的

30%o

六、课程内容

实践一：数据结构算法设计基础

（授课时间：第四学期第一周）

教学目标：数据结构的基本概念和术语、抽象数据类型的表示与实现、算法设计

的要求、时间复杂度的概念以及部分算法的时间效率。

主要内容：数据结构与算法绪论、算法的时间效率分析、选择排序、快速排序、

堆排序等排序算法分析比较、汉诺塔递归算法分析比较。

学时：3学时

教学方法：演示法,讲授/现场指导

实验类型：设计型实验、综合性实验

实践二：顺序表及其应用

（授课时间：第四学期第二周）

教学目标：理解线性表的顺序表示和实现，顺序表的存储结构，掌握顺序表的基

本操作；利用顺序表实现有关问题的求解。

主要内容：线性表的类型定义、顺序表示和实现、顺序表的基本操作；设计算法

实现约瑟夫问题、并编程实现有序表的合并问题。

学时：3学时

教学方法：演示法/讲授/现场指导

实验类型：设计型实验、综合性实验

实践三：链表及其应用

（授课时间：第四学期第三周）

教学目标：掌握单链表的表示和实现，单链表的存储结构，掌握单链表的基本操

作；利用链表实现有关问题的求解；理解并掌握双链表、循环单链表、

循环双链表的基本操作，编程实现相关问题的求解。

主要内容：单链表、双链表、循环单链表、循环双链表的类型定义及基本操作；

设计算法实现多项式的求和、和求导问题，实现集合并、交、差运算

问题。

学时：3学时

教学方法：演示法/讲授/现场指导

实验类型：设计型实验、综合性实验

实践四：栈及其应用

（授课时间：第四学期第四周）

教学目标：理解栈的概念和基本要素，掌握顺序栈和链栈的存储与基本运算的算

法，利用栈实现相关问题的求解。

主要内容：顺序栈和链栈的存储结构与基本操作；利用栈实现数制转换；设计算

法解决表达式求值问题、掌握设计回溯算法的基本技巧并结合栈用于

8皇后问题的求解；编程实现、设计算法求解迷宫问题、顺序栈的公

用问题。

学时：3学时

教学方法：演示法/讲授/现场指导

实验类型：设计型实验、综合性实验

实践五：队列及其应用

（授课时间：第四学期第五周）

教学目标：理解队列的概念和基本要素，掌握顺序环形队列和链式队列的存储与

基本运算的算法，利用队列实现相关问题的求解。

主要内容：顺序环形队列和链式队列的存储结构与基本操作；利用链式队列编写

程序模拟病人到医院看病，排队看医生的情况；以栈模拟停车场，以

队列模拟车场外的候车场，编程实现停车场的模拟；设计链表表示轮

渡，队列存储到达渡口的车，设计算法实现轮渡的模拟。

学时：3学时

教学方法：演示法，讲授/现场指导

实验类型：设计型实验、综合性实验

实践六：串及其应用

（授课时间：第四学期第六周）

教学目标：理解串的概念和基本要素，掌握顺序串、链串的基本操作；掌握串的

模式匹配的各种算法，利用串实现相关问题的求解。

主要内容：顺序串和链串的存储结构与基本操作；Brute_Force算法、Boyer_Moore

算法、kmp算法实现串的模式匹配；设计算法进行病毒感染检测，编

程实现最长连续相同字符、字符串加密、计数的模式匹配。

学时：3学时

教学方法：演示法/讲授/现场指导

实验类型：设计型实验、综合性实验

实践七：数组、广义表及其应用

（授课时间：第四学期第七周）

教学目标：理解数组、广义表的概念和基本要素，掌握数组、广义表的存储结构

和基本运算；实现矩阵的压缩存储，广义表的递归算法；利用数组和

广义表实现相关问题的求解。

主要内容：数组的定义、顺序表示和基本运算的实现、矩阵的压缩存储；广义表

的定义、存储结构和基本运算、递归算法求广义表深度；设计算法实

现存储格式转换问题、矩阵求解魔方问题、两个对称矩阵之和与乘积

问题。

学时：3学时。

教学方法：演示法/讲授/现场指导

实验类型：设计型实验、综合性实验

实践八：树及其应用

（授课时间：第四学期第八周）

教学目标：理解树、二叉树的定义和基本术语；掌握二叉树的存储结构和基本运

算、二叉树的各种遍历算法；利用二叉树实现相关问题的求解。

主要内容：二叉树的存储结构和基本操作；先序遍历、中序遍历、后序遍历算法

的分析比较；设计算法实现二叉树中从根结点到叶子结点的路径、叶

子结点个数的计算、由遍历构造二叉树、二叉树任一结点的特征计算。

学时：3学时。

教学方法：演示法/讲授/现场指导

实验类型：设计型实验、综合性实验

实践九：树及其应用

（授课时间：第四学期第九周）

教学目标：掌握线索二叉树的算法、树与森林、赫夫曼树及其应用、回溯法与树

的遍历；解决一些相关的综合问题。

主要内容：实现中序线索化二叉树的算法、树和森林的遍历算法、利用赫夫曼算

法构造赫夫曼树；设计算法实现电文的编码和译码、家族关系查询系

统。

学时：3学时。

教学方法：演示法/讲授/现场指导

实验类型：设计型实验、综合性实验

实践十：图及其应用

（授课时间：第四学期第十周）

教学目标：掌握图的定义和基本术语、图的存储结构和基本操作、图的遍历；利

用图解决一些相关问题。

主要内容：图的存储结构：数组表示法、邻接表、十字链表、邻接多重表存储图

的分析比较、邻接矩阵和邻接表的转化；深度优先遍历、广度优先遍

历算法的实现与比较；有向图的路径问题。

学时：3学时。

教学方法：演示法/讲授/现场指导

实验类型：设计型实验、综合性实验

实践十一：图及其应用

（授课时间：第四学期第十一周）

教学目标：掌握图的连通性问题、有向无环图及其应用、最短路径的算法。

主要内容：克鲁斯卡尔算法、普利姆算法的实现；编程实现拓扑排序的序列、求

关键路径、关键活动的算法；设计算法求从某个源点到其余各顶点的

最短路径和每一对顶点之间的最短路径。

学时：3学时。

教学方法：演示法/讲授/现场指导

实验类型：设计型实验、综合性实验

实践十二：图及其应用

（授课时间：第四学期第十二周）

教学目标：利用图解决一些综合性问题。

主要内容：假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一

些区域中的重要站点，弧代表已有的公交路线，弧上的权表示该路线

上的票价（或者所需时间），设计一个交通指南系统，指导前来咨询

者以最低的票价或最少的时间从区域中的某一站点到达另一站点。

学时：3学时。

教学方法：演示法/讲授/现场指导

实验类型：设计型实验、综合性实验

实践十三：查找及其应用

（授课时间：第四学期第十三周）

教学目标：掌握静态查找表、二叉排序树、哈希表及其应用，并利用查找解决一

些相关问题。

主要内容：顺序表、有序表的查找算法，二叉排序树查找算法的验证，设计哈希

表的创建、查找、元素插入等算法并验证，顺序查找与折半查找的性

能比较、线性散列与链式散列的性能比较。

学时：3学时。

教学方法：演示法/讲授/现场指导

实验类型：设计型实验、综合性实验

实践十四：排序及其应用

（授课时间：第四学期第十四周）

教学目标：掌握各种内部排序的特点和算法。

主要内容：直接实现插入排序、冒泡排序、选择排序、快速排序、希尔排序、堆

排序等6种内部排序算法，比较各算法的比较次数和移动次数。

学时：3学时。

教学方法：演示法/讲授/现场指导

实验类型：设计型实验、综合性实验

实践十五：排序及其应用

（授课时间：第四学期第十五周）

教学目标：利用排序解决一些相关问题。

主要内容：修改冒泡排序算法以实现双向冒泡排序；用单链表作为待排序数据的

存储结构，在其上实现直接插入排序算法；

学时：3学时。

教学方法：演示法/讲授/现场指导

实验类型：设计型实验、综合性实验

实践十六：综合实验

（授课时间：第四学期第十六周）

教学目标：设计算法实现有关数据结构的综合问题

主要内容：设计算法、编程实现通讯录管