一、课程简介

数据结构课程在计算机应用中具有举足轻重的作用，是计算机专业的技术基础课，主要讲述算法设计和数据结构的基础原理和技术，主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。主要有三个方面：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。由于本课程是计算机程序设计理论基础，所以也是非计算机理工类专业的重要选修课程。

使学生理解并部分掌握算法分析、算法设计和为计算机加工处理的数据设计逻辑结构、存储结构的基本方法和理论。本课程的学习过程也是算法设计的技巧和能力的训练过程，使学生初步获得编写结构、正确易读、符合软件工程规范的理论、技巧和能力。

本课程于第五学期开设，为选修课。总学时数为36学时，2.0学分。

二、课程目标

（一）基本理论知识

学生通过本课程的学习应对算法、算法运行时间分析方法、基本数据结构方法有全面系统的了解。主要理论内容包括：

1．掌握线性表定义、两种存储结构及在不同的存储结构下基本算法的实现。

2．掌握栈、队列的定义、特点、两种存储结构及基本运算的实现；了解栈、队列的应用。

3．了解串的定义、存储方式及串的基本运算。

4．理解数组的结构特点和存储方式；了解矩阵的压缩存储。

5．理解二叉树的定义、性质及其存储方法、遍历算法。

6．理解树的定义、术语。

7．理解图的基本概念及术语、存储结构、遍历方法。

8．了解查找算法。

9．了解排序算法的基本思想。

（二）基本技能

通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计和技巧有所了解。

（三）基本素质

培养有理想、有道德、有文化、有纪律的四有新人；培养学生具有严谨的、实事求是的科学作风。培养学生独力观察、思考问题、分析问题、解决问题和科学思维的能力。

三、学时分配

四、理论教学目标与内容

第一单元 数据结构的概念

目标

1.了解数据结构和抽象数据类型的概念。

2.掌握算法的定义和算法分析的方法。

内容

详细了解：（1）数据结构的基本概念和术语；（2）抽象数据类型的表示与实现；

（3）算法和算法分析：算法设计的要求，算法效率的度量，算法的存储空间需求。

第二单元 线性表

目标

熟悉：（1）线性表的逻辑结构；（2）掌握线性表的顺序存储及运算实现；（3）掌握线性表的链式存储和实现。

内容

1.详细了解：（1）线性表的类型和定义；（2）线性表的顺序表示和实现；（3）线性链表。

2.一般介绍：（1）循环链表；（2）双向链表。

第三单元 栈和队列

目标

熟悉：（1）栈基本概念及栈的应用；（2）掌握队列基本概念及队列的应用。

内容

1. 详细了解：（1）抽象数据类型栈的定义；（2）抽象数据类型队列的定义；（3）栈的表示和实现；（4）栈的应用举例。

2. 一般介绍：（1）链队列――队列的链式表示和实现；（2）循环队列――队列的顺序表示和实现。

第四单元 串

目标

1.掌握串及其基本运算，串的表示与实现。

2.了解串的模式匹配算法，串的应用。

内容

1. 详细了解：（1）串类型的定义；（2）串的表示和实现；（3）定义顺序存储表示；

2. 一般介绍：（1）堆分配存储表示；（2）串的块链存储表示；（3）串操作应用举例。

第五单元 数组和广义表

目标

1.掌握数组的定义，数组的顺序表示与实现。

2.了解：（1）数组的压缩存储；（2）了解广义表的定义。

内容

1．详细了解：（1）数组的定义；（2）数组的顺序表示和实现；（3）矩阵的压缩存储；（4）特殊矩阵；（5）稀疏矩阵。

2．一般介绍：（1）广义表的定义；（2）广义表的存储结构。

第六单元  树和二叉树

目标

1.掌握树的定义与基本术语，二叉树，二叉树的遍历。

2.了解线索二叉树，树与森林。

内容  

1．详细了解：（1）树的基本定义；（2）二叉树的定义、性质、存储结构、遍历二叉树和线索二叉树；（3）树的存储结构。

2．一般介绍：（1）森林与二叉树的转换；（2）树和森林的遍历。

第七单元 图

目标

1.掌握图的基本概念、存储表示。

2.了解图的遍历和连通性。

内容

1．详细了解：（1）图的定义和术语；（2）图的存储结构：数组表示法、邻接表、十字链表、邻接多重表。

2．一般介绍：（1）图的遍历：深度优先搜索、广度优先搜索；（2）图的连通性问题。

第八单元 查找

目标

了解静态查找法、动态查找法和哈希表查找法的定义。

内容

一般介绍：（1）．静态查找表：顺序表、有序表、索引顺序的查找；（2）动态查找：二叉排序树和和平衡二叉树；（3）哈希查找法。

第九单元 排序

目标

了解排序的基本概念、方法。

内容

一般介绍：（1）内部排序法简介：插入排序，交换排序，选择排序；（2）外部排序简介：外部信息的存取、外部排序的方法。

五、 措施和评价

（一）措施

本课程采用教师讲授、学生自学相结合的教学方式，形成教师和学生双向互动、教学相长的最佳教学模式。注意充分发挥学生的自主性，进行课堂专题讨论。在教师的指导下，学生有计划地、系统地进行自学。学生必须认真地、系统地阅读教师指定的教材、教学参考书，虽然没有实验条件，要求学生利用其他方式多加练习。

（二）评价

1.授课质量评价按“教师教学质量评价表”，由督导组、同行、学生和教研室予以评定。

2.学生成绩评价依据教学大纲和理论课考试权值分配进行期末理论考试。本课程考试用百分制计算，成绩达到60分以上者为合格；注重考察学生的综合能力和素质，根据做作业、上课提问、课堂讨论等情况和期末考试相结合，综合确定。具体考试及计分方法如下：

能力和素质（40%）：根据作业、考勤、上课提问、课堂讨论等情况而定，主要是实验技能。

期末考试（60%）：开卷笔试；以教师讲授的内容为主要考试内容范围，辅之以教材和主要参考书中的内容。

【注】

1.本课程的先修课程：

《C语言程序设计》

2.本课程使用教材：

《数据结构（C语言版）》，严蔚敏,吴伟民编著 清华大学出版社

3.主要参考书：

（1）《数据结构习题集》 严蔚敏、吴伟民编著 清华大学出版社

（2）《数据结构(C语言篇)习题与解析》 李春葆编著 清华大学出版社

（3）《数据结构(用面向对象方法与C++描述)》 殷人昆，陶永雷编著 清华大学出版社。

编写 李明彩

审校 杨 楠