《数据结构》课程教学大纲
一、课程说明：
《数据结构》是英语翻译专业机器翻译方向的一门选修课。

该课程教学使学生深透地理解数据的逻辑结构和物理结构的基本概念以及有关算法；熟悉它们在计算机科学中最基本的应用；了解编写算法的基本方法；为后继课程的学习打下一个理论基础及实践基础。

从第四学期至第八学期，学生可根据具体情况在其中任一学期选修该课程。

二、教学目的及要求：
该课程教学旨在使学生掌握如何根据问题的需求合理地组织数据，在计算机中有效地存储数据和处理数据，并初步了解算法设计和分析。

本课程从数据结构及其实现两个层次和相互关系的角度，系统地学习和掌握常用基本数据结构，包括线性表、栈、队列、树、二叉树、图、查找表和排序等，及它们的不同实现，包括不同的存储结构和算法，了解并掌握分析、比较和选择不同数据结构及不同存储结构、不同运算实现（算法）的原则和方法。

三、教学重点及难点：
重点：系统地学习和掌握各种常用基本数据结构及它们的不同实现，不同的存储结构和实现算法，了解并掌握分析、比较和选择不同数据结构及不同存储结构、不同运算实现（算法）的原则和方法。

难点：树、二叉树、图、查找和排序的综合应用及实现算法。

四、与其它课程的关系：
先修课程：《高等数学》和《程序设计》；后续课程：《操作系统》、《数据库》等。

五、学时与学分：
学时：54学时（包括上机18学时）。

学分：3学分（课堂教学2学分，上机1学分）。

六、教学内容：
第一章概论
本章主要教学内容：
基本概念和术语。

学习数据结构的意义。

算法的描述和分析。

本章教学目的及要求：
本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义，要求了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。

本章教学重点及难点：
本章重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系，难点是算法复杂度的分析方法。

第二章线性表
本章主要教学内容：
线性表的逻辑结构。

线性表的顺序存储结构。

线性表的链式存储结构。

顺序表和链表的比较。

本章教学目的及要求：
本章的目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的基本运算及其在存储结构上如何实现这些基本运算。

要求在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。

本章教学重点及难点：
本章重点是熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。

第三章栈和队列
本章主要教学内容：
栈。

队列。

栈和队列的应用。

本章教学目的及要求：
本章的目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算。

要求在掌握栈和队列的特点的基础上，懂得在什么样的情况下能够使用栈或队列。

本章教学重点及难点：
本章重点是掌握栈和队列在两种存储结构上实现的基本运算，难点是循环队列中对边界条件的处理。

第四章串
本章主要教学内容：
串及其运算。

串的存储结构。

本章教学目的及要求：
本章的目的是介绍串的逻辑结构、存储结构及其串上的基本运算，由于C语言及其它高级语言均以具备了较强的串处理功能。

本章教学重点及难点：
掌握串上实现的模式匹配算法。

第五章数组和广义表
本章主要教学内容：
数组。

矩阵的压缩存储。

广义表的概念。

本章教学目的及要求：
本章的目的是介绍数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，要求学生熟悉这些内容。

本章教学重点及难点：
本章重点是熟悉数组的存储方式、矩阵的压缩存储方式、广义表的定义及其求表头和表尾的运算，难点是稀疏矩阵的压缩存储表示下实现的算法。

第六章树
本章主要教学内容：
树的概念。

二叉树。

二叉树的遍历。

线索二叉树。

树和森林。

哈夫曼树及其应用。

本章教学目的及要求：
本章目的是介绍二叉树的定义、性质、存储结构、遍历、线索化，树的定义、存储结构、遍历、树和森林与二叉树的转换，哈夫曼树及哈夫曼编码等内容。

本章教学重点及难点：
重点掌握二叉树的遍历算法及其有关应用，难点是使用本章所学到的有关知识设计出有效算法，解决与与树或二叉树相关的应用问题。

第七章图
本章教学内容：
图的概念。

图的存储结构。

图的遍历。

生成树和最小生成树。

最短路径。

拓扑排序。

本章教学目的及要求：
本章目的是介绍图的基本概念、两种常用的存储结构、两种遍历算法以及图的应用算法。

本章教学重点及难点：
要求学生在熟悉这些内容的基础上，重点掌握在图的两种存储结构上实现的遍历算法。

本章难点是图的应用算法：求最小生成树，求最短路径以及拓扑排序，只要求学生掌握这些算法的基本思想及时间性能。

第八章查找
本章主要教学内容：
基本概念。

线性表的查找。

树的查找。

哈希表。

本章教学目的及要求：
本章目的是介绍线性表、树和散列表的查找方法、算法实现以及各种查找方法的时间性能（平均查找长度）分析。

本章教学重点及难点：
要求学生在熟悉这些内容的基础上，重点掌握顺序查找、二分查找、二叉查找树上查找
以及哈希表上查找的基本思想和算法实现。

本章难点是二叉查找树的删除算法及B-树上的插入和删除算法。

第九章排序
本章主要教学内容：
基本概念。

插入排序。

交换排序。

选择排序。

归并排序。

分配排序。

各种排序方法的比较和选择。

本章教学目的及要求：
本章目的是介绍五类内部排序的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。

本章教学重点及难点：
要求在熟悉这些内容的基础上，重点掌握快速排序、堆排序、归并排序和基数排序的基本思想及排序过程，本章难点是这四个排序算法的实现。

七、教材及参考书：
秦峰，《数据结构》（C语言版），中国科学技术大学出版社，2007
严蔚敏、吴伟民，《数据结构》（C语言版），清华大学出版社，2007。