1、中文名称：数据结构

总学时72学时，其中讲授54学时，实验18学时

考试（期终考试成绩中卷面成绩占70%，实践环节成绩占30%）

《数据结构》是计算机学科的一门专业基础课。通过该课程的学习使学生掌握数据结构的基本概念、基本原理和基本方法；掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析；能够运用数据结构基本原理和方法进行问题的分析与求解。

计算机科学与技术专业（物联网工程方向）

七、课程教学要求和学时分配

1、数据结构的课程体系

掌握数据结构、存储结构和数据类型的基本概念及相关术语；理解算法要素的确切含义；掌握算法设计的基本要求以及分析算法的时间与空间复杂度的方法。

重点是数据与数据元素，抽象数据类型表示法，类C语言语法，渐近时间复杂度的意义、作用以及计算方法。难点是数据元素间的四种结构关系，抽象数据类型表示法，渐近时间复杂度的意义。

（四）建议学时 2学时

2、线性表的顺序表示和实现

3、线性表的链式表示和实现

掌握线性表的逻辑结构特性；掌握线性表的顺序存储结构和链式存储结构的描述方法及其结构特点；熟练掌握线性表在顺序存储结构和链式存储结构的结构上进行相关的查找、插入、删除等操作的算法，并且能够从时间和空间复杂度的角度综合比较两种存储结构的不同特点。

重点是线性表的定义，线性表的顺序表示和实现方法，线性链表的单链表表示及实现方法。定位结点、删除结点、插入结点操作在单链表上的实现，循环链表、双链表的结构特点，循环链表、双链表上删除与插入操作的实现。难点是线性链表的概念，线性表的顺序表示和实现方法，线性表与线性结构的联系与区别，链表与链式结构的联系与区别，指针操作，一元多项式的相加算法。

（四）建议学时 8学时

1、栈的定义、表示和实现

4、队列的定义、表示与实现

掌握栈和队列的结构特性和描述方法；熟练掌握出栈和入栈的基本操作，以及循环队列和链队列的出队列和入队列的基本操作实现算法；熟悉栈和队列的一些典型应用实例。

重点是栈和队列的基本概念、基本算法，栈的顺序存储表示与实现方法，利用栈实现行编辑，利用栈实现表达式求值，链队列的表示与实现。难点是栈和队列的应用算法，顺序栈的溢出判断条件。

（四）建议学时 6学时

掌握串的结构特性以及串的基本操作；掌握针对字符串进行操作的常用算法；熟练运用字符串处理函数。

重点是串的定义，串的表示和实现，串的模式匹配算法。难点是串的表示和实现，串的模式匹配算法。

（四）建议学时 2学时

4、广义表的定义及存储结构

掌握一维数组以及多维数组的存储和表示方法；掌握对特殊矩阵进行压缩存储时的下标变换公式；了解稀疏矩阵的三元组压缩存储表示方法及适用范围；掌握稀疏矩阵的三元组表示方法及矩阵转置算法；了解广义表的定义、存储结构和基本运算。

重点是数组的定义，数组的顺序表示方法，广义表的操作及意义，矩阵的压缩存储。难点是广义表存储结构。

（四）建议学时 4学时

1、树的定义和基本术语

2、二叉树定义、性质和存储结构

3、遍历二叉树和线索二叉树

5、森林与二叉树的转换

掌握树的基本定义及其相关术语的含义；熟练掌握二叉树的结构特性，了解相应的证明方法；熟悉三种遍历二叉树的递归算法；掌握二叉树线索化的实质及线索化的过程；掌握树、森林与二叉树的转换及其各自遍历的对应关系；掌握哈夫曼编码的原理及实现方法。

重点是二叉树的定义和逻辑特点，二叉树的基本运算，二叉树的链式存储结构的组织方式，二叉树的三种遍历方法及其算法，一般树转化为二叉树的方法，哈夫曼树及哈夫曼编码，哈夫曼编码的应用。难点是二叉树的递归定义，二叉树链式存储结构的组织方式，三种遍历的区别，哈夫曼编码。

（四）建议学时 10学时

5、有向无环图及其应用

掌握图的定义和术语；掌握图的两种存储结构和两种遍历策略；熟悉图的最小生成树的生成方法；掌握拓扑排序、关键路径的算法思想；掌握网络顶点之间的最短距离的计算思想。

重点是图的定义、术语及其含义，各种图的邻接矩阵表示方法，图的按深度优先搜索遍历方法和按广度优先搜索遍历方法，生成树和最小生成树的概念，Prim算法，拓扑序列和拓扑排序的概念和算法思想，关键路径的算法思想，最短路径的算法思想。难点是图的两种存储结构，关键路径、最短路径算法。

（四）建议学时 10学时

4、二叉排序树的构造和查找

5、平衡二叉树的定义及维护平衡的方法

6、B树及其基本操作、B+树的基本概念

7、散列（Hash）表

8、查找算法的分析及应用

掌握顺序表和有序表的查找方法；掌握查找效率的计算方法；熟练掌握二叉排序树的构造和查找方法；理解平衡二叉树的维护平衡的方法；掌握B树及其基本操作、B+树的基本概念；掌握散列函数构造方法及冲突解决方案。

重点是查找的基本概念，顺序查找、折半查找、二叉排序树的定义和查找算法，二叉平衡树的概念，B树及其基本操作、B+树的基本概念，散列表的基本思想，各种散列表的组织、解决冲突的方法。难点是二叉排序树上的插入和删除算法，平衡树、B树的建立，平衡二叉树的旋转平衡算法，散列表上的有关算法。

（四）建议学时 6学时

8、各种排序方法的比较

掌握排序的定义和各种排序方法的基本思想及其特点；理解各种排序方法的排序过程及其依据的原则；掌握快速排序和堆排序等方法；能够进行各种排序方法的时间复杂性分析。

重点是排序的基本概念，直接插入排序、快速排序、选择排序、 归并排序 、基数排序、最佳归并树的思想和算法。难点是快速排序算法，堆排序算法。

（四）建议学时 6学时

1、《数据结构（C语言版）》，严蔚敏等，清华大学出版社

2、《数据结构教程》（第3版），李春葆等，清华大学出版社

3、《数据结构与算法》，Sartaj Sahni著，汪诗林等译，机械工业出版社

4、《数据结构题集》，严蔚敏等，清华大学出版社

5、《数据结构习题与解析》，李春葆，清华大学出版社

1、 课程名称：数据结构与算法

3、 学时和学分：48学时，3学分

4、 适用专业：软件工程

5、 先修课程：程序设计基础，离散数学

6、 使用教材：Clifford A. Shaffer著，张铭，刘晓丹等译.数据结构与算法分析（第三版），电子工业出版社，2013年10月

（1）严蔚敏.《数据结构》.清华大学出版社，2000.

（2） 李春葆.《数据结构教程》.清华大学出版社，2002.

8、 课程描述（200-300字左右）：

《数据结构与算法》是软件工程本科专业的专业基础课程。课程的主要目的是使学生掌握数据结构与算法的基础理论和基本方法，提高学生对各种数据结构与算法的程序设计能力，以及提高学生对数据结构与算法的实际运用能力。课程主要内容包括线性表、栈和队列、二叉树、树、图、内排序、文件管理和外排序、检索、索引技术和分析技术。课程既包括基础概念、基本方法的理论学习，也包括数据结构与算法的C++语言实现，理论与和实践并重。

9、 教学目标（需明确各教学环节对人才培养目标的贡献）

知识贡献：掌握线性表、栈、队列、二叉树、树、图等基本数据结构的概念；掌握各类数据结构中元素的增加、修改、删除、查找等基本操作的算法流程；掌握二叉树、二叉检索树、高度平衡二叉树、堆、树等非线性数据结构的基本性质；掌握顺序查找、二分查找两种常见的线性表检索方法；掌握插入排序、选择排序、冒泡排序、快速排序、归并排序、堆排序等常见的排序方法；理解文件管理的概念，掌握常见的外排序算法；掌握图的基本概念、图的存储方法和实现方法，理解图的遍历、最短路径、最小生成树等方面的常用算法。

能力贡献：通过学习数据结构与算法的基本概念和基本原理，增强学生对抽象数据类型的理解能力；通过用C++编程语言实现数据结构和算法，增强学生的程序设计能力；掌握基本的算法分析技术，增强对算法流程和程序实现的分析能力；通过分析数据结构与算法的应用案例、上机练习以及数据结构与算法应用设计，培养学生利用所学知识解决具体问题的能力和创新能力。

素质贡献：在理论学习、编程实现、算法应用等各个环节中，养成认真、踏实、细心的良好习惯，提升专业素养。

课程讲授：讲解基础理论和基本方法，通过分析经典案例展示数据结构与算法的应用领域和应用方法

课外自学：通过Sakai平台提供教学资料，学生通过自学深化、拓展课程内容

上机练习：使用C++语言编写程序，验证基本的数据结构与算法

课外设计：结合案例分析，提供参考题目，学生自己设计解决方案，体验数据结构与算法的应用效果

11、考核及成绩评定方式：