一、《数据结构》的地位和作用 1.数据结构和算法在计算机学科中的地位十分重要。我们生活的现实世界，面对着各种需要解决的科学与工程问题，如何将现实世界中的事与物信息化，将它们表示为计算机中的数据，是信息科学领域研究人员的重要研究课题之一。我们使用计算机的过程就是对数据进行加工处理的过程，数据的组织与结构被确立为计算机科学中最为基本的内容，这些数据在计算机中有着统一表示方法，因而成为被计算机程序处理的符号集合。研究数据在计算机中的表示方法、存储方法及其处理方法，是《数据结构》课程研究的主要内容。因而，《数据结构》课程以问题求解方法、程序设计方法及一些典型的数据结构算法为研究对象，要求学生学会分析数据对象特征，掌握数据组织方法和计算机的表示方法，为数据选择适当的逻辑结构、存储结构以及相应的处理算法，培养学生良好的程序设计风格。《数据结构》课程是计算机学科的一门核心课程，是计算机软件理论与技术的重要基石，也是理工科计算机相关专业必修的信息技术基础课程之一。目前，ACM/IEEE CC-2001教程已将算法与数据结构类课程列为核心课程之首，数据结构日益显示出其在信息科学中的重要地位。 2.数据结构是学好后续专业课程的基础。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，要更好的运用计算机解决实际问题，仅仅掌握集中计算机程序设计语言是难以应付当前众多复杂的问题的，而是要求我们掌握扎实的数据结构基础知识和基本技能。学好《数据结构》是学习计算机科学中其它课程，如《操作系统》、《数据库原理》、《计算机网络》、《面向对象技术》、《编译原理》、《软件工程》、《计算机算法分析与设计》、《人工智能》等都是十分重要的。计算机解决问题的步骤如下图所示： 从图中可以看出，问题的求解步骤可分解为 ①根据实际问题，利用数学、计算机等工具抽象出概念模型，确定数据与数据之间的关系，设计数据的逻辑结构； ②分析数据之间的逻辑关系，确定数据对象和数据关系，给出对数据的基本操作，确定抽象数据类型(ADT)； ③用合适的计算机语言的数据类型，设计一种存储结构，在计算机内部表示数据与数据之间的关系； ④根据存储结构和抽象数据类型的基本操作，设计算法； ⑤按照相应的计算机高级语言语法规则，实现算法； ⑥编写程序，调用算法，输入输出数据，得出实际问题的解。 数据结构的基本知识和应用水平是衡量软件开发人员计算机水平的重要标志之一。学生学好这门课程，对毕业后的软件开发能力有着直接的影响。我们所熟知的计算机软件资格考试中的软件设计师、程序员考试、计算机相关专业研究生入学考试、有些高校的计算机博士招生考试等等，都会出现数据结构的知识点，几乎所有的软件公司人才招聘笔试时都会涉及到数据结构的知识点。因此，数据结构与算法在计算机科学特别是软件开发中处于核心地位。 二、课程定位 数据结构是计算机等相关专业的一门十分重要的专业基础课，在计算机学科中起到承前启后的作用。它主要研究计算机加工对象的逻辑结构、在计算机中的表示形式以及实现各种基本操作的算法。要求学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析技术，培养学生数据抽象的能力。本课程主要讲授数据结构的基本概念、线性表、栈和队列、串和数组、树形结构、图结构、查找、排序等内容。 三、教学对象 本大纲适用于信息与计算科学、数学与应用数学、应用统计学等专业本科生。 四、主要内容 1．重点内容： 线性表中顺序表和单链表上实现的各种基本算法及相关的时间性能分析；栈和队列的顺序存储结构及其基本运算；串运算的实现和稀疏矩阵的压缩存储；二叉树的定义、性质、存储结构、遍历、线索化，二叉树的遍历算法和有关应用，树的存储结构、遍历以及树、森林与二叉树的转换，哈夫曼树及哈夫曼编码等；图的基本概念，两种常用的存储结构(邻接矩阵和邻接表)，两种遍历算法(DFS和BFS)及图的应用算法(最小生成树，求最短路径以及拓扑排序)等；顺序查找、二分查找、二叉树查找以及散列表上查找的基本思想和算法实现；插入排序、交换排序、选择排序等基本排序类的排序方法的基本思想及排序过程。 2．难点内容： 简单的算法复杂度的分析；运用有效算法解决与线性表相关的应用；循环队列中对边界条件的处理；稀疏矩阵的压缩存储；二叉树的遍历及其有关应用；图的存储结构、遍历算法及图的应用算法；插入排序、交换排序、选择排序等基本排序类的算法实现。 五、选用教材及主要参考书 1．本课程教材： [1] 《数据结构》，严蔚敏 吴伟民，清华大学出版社，1997.04 [2] 《数据结构题集》，严蔚敏 吴伟民，清华大学出版社，1999.02 2．主要参考书： [1］系列丛书《计算机程序设计艺术》，Knuth，人民邮电出版社 [2] 《计算与算法导论》，章小莉等译，电子工业出版社 [3] 《算法分析导论》，冯舜玺译，机械工业出版社 [4] 《数据结构与算法》，齐德笠编著，清华大学出版社 [5] 《数据结构——C++实现》，缪淮扣等编著，科学出版社 [6] 《算法设计与分析》，王红梅编著，清华大学出版社 [7] 《数据结构与算法》，许卓群编著，高等教育出版社 [8] 《数据结构习题与解析》，李春葆，清华大学出版社