参 考 书

《数据结构》，严蔚敏、吴伟民，清华大学出版社2007， 2013年4月第39次印刷， ISBN：978-7-302-14751-0

《数据结构（c语言版）》，赵坚 姜梅等，中国水利水电出版社2005, 2006月8月第二次印刷，ISBN：7-5084-3052-2

参考网站

能力目标

通过本课程的学习，使得学生从数据逻辑结构、存储结构和基本运算算法设计三个层面掌握基本的数据组织和数据处理方法，能够从问题出发设计面向数据结构的求解算法，并能够对算法进行时间复杂度与空间复杂度分析；具备较高水准的采用数据结构方法求解实际问题的能力。

综合素质目标

在数据结构课程思政教学中，从大学生求知需求出发，遵循学生成长规律，立足人才培养目标和学科优势，进行系统设计，在教学目标的制定过程中注重“价值引导”，深度拓展教学内容，培养学生对工作学习效率的理解，引导学生规章意识，纪律意识、大局意识，合作精神，认识严谨工作作风的重要性，启发学生勤于思考，勇于探索专业未知领域。

√

√

√

√

√

√

英文

简介

Data structure is a professional basic course, which is the basis of learning other software development and design courses. The main contents include: linear table, stack and queue, string, array and generalized table, tree, graph, search algorithm and sorting algorithm. Through the study of this course, students can master the basic data organization and data processing methods from the three levels of data logical structure, storage structure and basic operation algorithm design, be able to design the solution algorithm for data structure from the problem, and analyze the time complexity and spatial complexity of the algorithm. It lays the foundation for the follow-up courses such as operating system.

1

绪论

6

数据结构的研究内容；基本概念和术语；抽象数据类型的表示与实现；算法和算法分析；复习c语言相关内容

2

线性表

14

线性表的定义和特点；线性表的类型定义；线性表的顺序表示和实现；线性表的链式表示和实现；顺序表和链表的比较；线性表的应用等

3

栈和队列

14

栈和队列的定义和特点；栈的表示和操作的实现；栈与递归；队列的表示和操作的实现；栈和队列的应用等

4

串 、数组和广义表

12

串的表示和实现，包括顺序存储和链式存储表示；古典的模式匹配算法；数组的存储方法；特殊矩阵和稀疏矩阵的压缩存储，稀疏矩阵的转置运算；广义表的逻辑结构和存储结构等

5

树和二叉树

8

二叉树的定义和术语，二叉树的性质，特殊的二叉树；二叉树的存储结构，顺序存储和二叉链表；二叉树的前序、中序、后序、层次遍历方法；线索化二叉树；树和森林的定义，树的存储，树、森林与二叉树的转换；树的应用，哈夫曼树及哈夫曼编码

6

图

6

图的定义和术语；图的两种存储结构：邻接矩阵和邻接表表示法；图的两种遍历策略：深度优先搜索和广度优先搜索；构造最小生成树的两种算法：普里姆算法和克鲁斯卡尔算法；求最短路径问题的算法，迪杰斯特拉算法等

7

查找（自学）

6

查找的基本概念，平均查找长度；基于线性表的查找：顺序查找、折半查找；基于树表的查找：二叉排序树、平衡二叉树；散列表：散列表的基本概念，散列函数的构造方法、处理冲突的方法、散列表的查找与分析

8

排序（自学）

6

排序的基本概念，包括正序，逆序，稳定性，排序方法的分类；插入排序：直接插入排序、折半插入排序和希尔排序；交换排序：冒泡排序和快速排序；选择排序：简单选择排序和堆排序；归并排序：2-路归并排序；基数排序：多关键字的排序和链数基数排序；排序算法分析：各种排序算法的比较和移动次数，时间复杂度和空间复杂度的分析等

培养学生对工作学习效率的理解，并讨论提高学习效率的方法

在绪论中，介绍数据结构的各种概念、术语，及算法的时空效率分析，融入同学在日常生活和学习中要多注意考虑效率问题，并探讨如何提高学习效率。

培养学生的国家荣誉、民族自豪感

讲解线性表的特征，线性表数据在计算机中的不同存储方法和数据操作算法，通过举例中国古近代算法，融入民族自豪感

引导学生规章意识，纪律意识

讲解队列的特性原理，以银行和食堂排队举例，融入秩序的重要性和对提高效率的帮助

引导学生在完成任务时要有大局意识，合作精神。

通过举例树形的组织机构管理实现和哈夫曼编码实现，融入大局意识，合作精神

帮助学生认识严谨工作作风的重要性，启发学生勤于思考，勇于探索专业未知领域

通过讲解最小生成树，最短路径求解和关键路径的求解，融入要勤于思考，逻辑思维要严谨

课堂考勤和纪律

作业

期中考试

期末考试

知识和能力目标

20

50

70

综合素质目标

10

20

30

85-100

（A）

75-84

（B）

62-74

（C）

60-61

（D）

0-59

（E）

目标

15%

55%

15%

5%

10%

课程负责人/专业负责人审核意见

签名： 年 月 日

论证专家意见

签名： 年 月 日

系审核意见

签名： 年 月 日

学院审核意见

签名（盖章）： 年 月 日