《数据结构》课程教学大纲
本课程教学大纲依据网工专业2015级人才培养方案制定。
一、课程说明
课程名称：数据结构课程编号：1261D03
总学时：80学时总学分：5.5学分
学时分配：理论56学时，上机24学时
课程性质：专业必修课
先修课程：C语言程序设计适用专业：网工
开课学期：第二学期
二、教学目标与要求
教学目标：
通过本课程教学，使学生了解计算机科学各领域的数据结构知识，及有关的应用软件所要用到的各种数据结构知识，理解常用的数据结构及内在的逻辑关系，掌握计算机软件设计中的算法知识，熟悉软件设计和编程技能，旨在培养初步对不同的存储结构和相应算法的对比，有一定的算法改进能力，并为学生日后从事软件开发和程序员奠定基础。同时，作为编译程序、操作系统、数据库系统课程学习的理论基础，也为学生后续课程的顺利学习提供条件。
教学要求:
通过本课程的学习，在基础方面，要求学生能够掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。总言之，使应用者较全面的掌握各种常用的数据结构，提高运用数据结构解决实际问题的能力。
学习本课程必须具备高级语言程序设计（如C语言）的基础知识与基本技能。它的后续课程为操作系统、数据库原理等。数据结构中存储结构及基本运算的实现需要程序设计的基本知识和编程的经验及能力，本课程的大部分实例均是用C语言实现的，故要求较熟练地掌握C语言。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。
教学重点：
1.掌握数据结构的概念及术语。
2.掌握线性表（栈、队列）的存储结构（顺序和链式存储）、算法描述及应用。
3.掌握数组的顺序存储和特殊矩阵的压缩存储。
4.掌握树的基本概念和术语，掌握二叉树的基本性质和特点、存储结构及算法描述、二
叉树的遍历、树、森林与二叉树的转换。掌握最优二叉树（哈夫曼树）的特点及应用。
5.掌握图的基本概念和术语、存储结构（邻接矩阵、邻接表、十字链表、邻接多重表）、图的遍历、图的连通性（最小生成树）。
6.掌握查找的基本概念、基于线性表的查找方法（顺序、折半）。
7.掌握插入类排序（直接、折半、表、希尔等插入排序）、交换类排序（冒泡、快速排序）。
教学难点：
1.掌握算法时间复杂度。
2.掌握线性表的顺序和链式存储存储结构、算法描述及应用。
3.掌握数组的顺序存储和特殊矩阵的压缩存储。
4.掌握二叉树的基本性质和特点、存储结构及算法描述、二叉树的遍历、树、森林与二叉树的转换。掌握最优二叉树（哈夫曼树）的特点及应用。
5.掌握图的邻接矩阵、邻接表、十字链表、邻接多重表的存储结构、图的遍历、图的连通性（最小生成树）。
7.掌握哈希表的构造、查找方法（顺序、折半、快速）。
三、教学内容与目的
（一）绪论
1、什么是数据结构
2、基本概念和术语
3、抽象数据类型的表示与实现
4、算法和算法分析
教学目的：介绍数据结构课程的研究对象，基本术语，掌握算法的要领，描述算法的类语言。了解数据结构的发展概况及其在计算机中的地位。
教学重点：
1、熟悉各名词、术语的含义，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质；
2、了解抽象数据类型的定义、表示和实现方法；
3、理解算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）；
4、掌握计算语句频度和估算算法时间复杂度的方法。
教学难点：
1、掌握数据结构的意义及数据结构的基本内容；
2、掌握数据结构及数据、数据元素等相关概念；
3、掌握算法描述的方法；
4、算法时间复杂度的计算。
教学方法与手段：讲授式、讨论式、案例教学
作业形式：作业，辅导答疑
（二）线性表
1、线性表的类型定义
2、线性表的顺序表示和实现
3、线性表的链式表示和实现
4、一元多项式的表示及相加
教学目的：掌握线性表的逻辑结构、顺序存储结构和链式存储结构。掌握在线性表上实现基本运算的算法。
教学重点：
1、线性表的定义及逻辑上的特点；
2、顺序表上插入、删除和定位运算的实现；
3、单链表的结构特点及类型说明；
4、头指针和头结点的作用及区别；指针操作；
5、定位、删除、插入运算在单链表上的实现；
6、循环链表、双链表的结构特点；及其删除与插入运算的实现。
教学难点：
1、线性表与线性结构的联系与区别；
2、线性表的顺序存储结构及其运算；
3、头结点在链表中的作用和指针的操作；
4、单链表存储结构定义，删除、插入运算中的指针操作顺序；
5、单链表的基本运算的实现；
6、循环链表、双链表上指针的操作顺序及其相关运算。
教学方法与手段：讲授式、讨论式、案例教学
作业形式：作业，辅导答疑
（三）栈和队列
1、栈的类型定义
2、栈的应用举例
3、栈与递归的实现
4、队列的类型定义
教学目的：掌握栈和队列的逻辑结构定义，掌握在两种存储结构上如何实现栈和队列的
