数据结构”课程教学大纲和教学规程1. 课程基本信息课程编号：课程名称（中文）：数据结构课程名称（英文）：Data Structures开课学期：见培养方案与教学计划课程类别： 核心专业基础课程总学时数与学分： 68 学时（4 学分，不含实验课时，4 学时/周）先修课程： 计算机科学与技术导论、高级语言程序设计、高等数学或数学分析、线性代数或高等代数、集合论与图论、近世代数（可缺省） 教学形式： 课堂讲授 + 课外教学 + 实验教学（实验部分实行单列）使用教材： 许卓群等编著， 《数据结构》 ，高等教育出版社，1987 年 5 月第 1 版教学参考书： 颜蔚敏等编， 《数据结构》 ，清华大学出版社注：上述两本书可以互为教材和教学参考书大纲制定者： 赵致琢、李慧琪（厦门大学计算机科学系）大纲审定者： 此外，配合实验课程的教学中，学生应理论联系实际，理论指导实践，通过规范地完成一系列数据结构实验进一步巩固所学的相关书本知识，在知识、能力、素质上得到进一步的提高2．课程性质、类别与任务“数据结构”是计算机科学与技术专业一门重点专业基础课程，也是学科专业核心专业基础课程之一，属于必修课程本课程的教学任务是针对大量的信息处理对象，介绍对象信息与数据表示的各种抽象的、基本的逻辑结构及其上的基本运算操作。
通过研究各种基本数据结构内在的逻辑关系和它们在计算机中的存储表示方式，初步建立数据结构上基本运算操作的正确性概念，同时，结合各种典型问题讨论其上的各种基本运算操作及其基本算法，讲授各种数据结构的特点、适用范围，以及对一些基本算法效率的定性和定量分析方法，为后续课程提供必要的数据结构基础此外，配合实验课程的教学中，学生应理论联系实际，理论指导实践，通过规范地完成一系列数据结构实验进一步巩固所学的相关书本知识，在知识、能力、素质上得到进一步的提高3．课程教学的基本要求（教学内容和教学重点）“数据结构”内容的重点是各种数据表示抽象的逻辑结构及其上基本的运算操作课程教学的基本要求是通过教学活动，使每一个学生较好地掌握课程的主要内容，能够运用数据结构的理论、方法与技术解决相应的、一般的实际问题课程的教学内容主要包括如下知识点，其中，属于重点的内容用黑体标示，今后教学改革拟增加的内容用绛红色标示，部分非重要内容用括弧标注为“一般了解”：数据结构的概念；数据的逻辑结构；数据的存储结构；线性表；非线性表；四种基本的存储映像方法：顺序、链接、索引、散列；数据结构上的基本运算；几种常用的运算；可支撑算法运行的计算模型；算法；算法的特性；计算正确性；数据结构上运算的正确性；数据结构的选择和评价标准；线性结构与顺序表；向量；向量的运算；栈；栈的基本运算；栈的应用（一般了解） ；递归的概念；栈和递归的关系；队列；队列的基本运算；限制存取点的表：双端队列、双栈、超队列、超栈；数据掩蔽与操作封装；抽象数据类型；基本数据结构上运算的正确性：VDM 元语言或抽象机、操作语义、栈运算的操作语义；2链表与动态存储管理；单链表；单链表的存储结构；单链表的基本运算；栈和队列的链接存储表示；栈的链式存储结构及单链形式栈的运算；队列的链式存储结构及单链形式队列的运算；线性表的其他链接存储表示；循环表及其基本运算；双链表及其基本运算；对称表及其基本运算（一般了解） ；串；串的存储表示；串的顺序存储；串的索引存储及链式存储；串的基本运算及其实现；模式匹配；一些基本的匹配算法；内排序与外排序；排序码；排序；“稳定的”和“不稳定的”排序方法；排序算法好坏的评价标准；一些常用的基本的排序方法：插入排序、直接插入排序、二分插入排序、表插入排序、shell 排序、选择排序、直接选择排序、 树形选择排序、 交换排序、起泡排序、快速排序、分配排序、归并排序、基数排序；线性表的检索；衡量一个检索算法效率的主要标准：平均检索长度；一些基本的检索方法：顺序检索、二分法检索、分块检索、散列表的检索；散列表的检索：散列函数、碰撞、同义词、负载因子；碰撞的处理方法：拉链法、开地址法、插入算法；基于属性的检索：倒排表（一般了解） 、多重表（一般了解） ；树形结构；树；树的递归定义；有序树；森林；二叉树；满二叉树；完全二叉树；树的二叉树表示；森林与二叉树的转换；周游；树形结构的周游；二叉树的周游方式：前序法、后序法、中序法；周游树和树林的主要方式：深度优先周游（先根次序、后根次序） 、宽度优先周游、D-检索；树形结构的存储；链式存储：二叉树和树的 llink-rlink 法存储表示、树的三重链接法存储表示；穿线树：对称序穿线树的概念、按对称序线索化二叉树、按对称序周游对称序穿线树；穿线树上的基本运算操作；顺序存储；完全二叉树的顺序存储；带右链的先根次序表示法；带双标记位的先根次序表示法；带右链的层次次序表示法；带度数的后根次序表示法；不同表示法之间的转换；二叉树周游算法：使用栈的周游算法、使用栈对二叉树进行后序周游、逆转链的周游算法、穿线树、用逆转链的方法对二叉树进行前序周游、Robson 周游算法、用 Robson 算法对二叉树进行后序周游、Siklossy 周游算法、用 Siklossy 算法对二叉树进行对称序周游；树目录；二叉排序树；二叉排序树上的基本运算；最佳二叉排序树；外部路径长度和内部路径长度；最佳二叉排序树的构造方法；具有不等权值结点的最佳二叉排序树的构造方法；平衡的二叉排序树：结点的平衡因子、AVL 树的检索和插入算法；字符树（一般了解） ；双链树；双链树的检索和插入算法；trie 结构；trie 结构的检索算法；树形结构的其他应用：Huffman 算法及其应用；求具有最小带权外部路径长度的扩充二叉树的方法；堆、堆排序；用筛选法建堆的算法和堆排序算法；决策树（一般了解） ；博弈树（一般了解） ；图；图的存储表示法：图的相邻矩阵表示法、图的邻接表表示法、图的邻接多重表表示法；图的周游和生成树；图的深度优先周游和宽度优先周游方法、构造网络的最小生成树方法；最短路径；求带权图中从一个结点到其他各结点的最短路径：Dijkstra 算法；求带权图中每一对结点之间的最短路径的算法；拓扑排序：有向图的拓扑排序、在有向图的邻接表表示上实现拓扑排序；关键路径（一般了解） ；数组结构：多维数组、稀疏矩阵和广义表；多维数组：多维数组的行优先和列优先顺序序列；稀疏矩阵：稀疏矩阵的顺序存储、链式存储和散列存储；稀疏矩阵的乘法（一般了解） ；广义表：广义表、再入表、递归表；广义表的存储：广义表的单链表示法、广义表的双链表示法；文件：顺序文件、文件结构概述、文件的逻辑结构和存储结构、文件上的基本运算操作； 顺序文件；顺序文件的分块插值检索（一般了解） ；散列文件；按桶散列；按桶散列方法的文件组织及查找、修改、插入、删除等运算；索引顺序文件；索引文件的存储结构：静态索引结构、多分树应用；动态索引结构；B-树及其应用、B +树及其应用；类型文件；面向对象表示法：从抽象数据类型到对象结构、类与对象、属性继承、面向对象的数据结构表示方法、对象的基本运算。
3抽象数据类型的代数语义（有条件的学校和学生作为选修） 4．教学目标、教学内容的初步论证和教学过程中应该注意的事项在抽象数据类型和面向对象程序设计技术出现以前，各种数据结构大多数都是静态的，数据表示抽象的逻辑结构和其上的运算操作之间是分离的，其上的运算操作大都借助一些简单的算法加以刻画为了保护程序设计中数据的安全，人们提出了数据掩蔽与操作封装的构想，抽象数据类型的概念随之产生，并由此派生出对象的概念，发展了面向对象的程序设计概念、方法和技术，直至今日的 Agent 和智能 Agent从那时起，数据掩蔽与操作封装的思想、分层描述与属性继承的思想成为数据描述与程序设计的主导思想之一在计算机科学与技术的发展过程中，大量的例子已经充分说明，一个问题求解质量好坏和效率的高低，更多地将是取决于问题抽象之后对象信息表示的数据结构而不是施加在数据结构上的操作因此，数据结构课程的重点要落实在各种数据结构及其上的基本运算操作而不是解决各种问题的算法方面（算法问题将来主要由“算法设计与分析”课程去解决） ，并特别注意以下几点：第一，在介绍各种基本的数据结构时，注意到许多具体数据结构与离散数学密切相关，应该借助离散数学提高数据结构描述的抽象化程度，同时帮助学生建立数据的逻辑结构与存储结构之间的关系，以及如何在数据结构与程序设计语言之间建立有机的联系，这样有利于学生深入掌握计算机科学与技术；第二，算法作为刻画数据结构上基本运算操作的一种载体，应该严格限定在一些简单的基本算法的范围内，同“算法设计与分析”课程之间形成一个合理的分工，不应该过多涉及如何寻找算法和研究算法设计的方法。
算法复杂性的分析也是需要的，但此处仅仅是用于比较不同数据结构的优劣；第三，为了提高抽象化程度，体现学科抽象描述求解问题与具体实现解决问题相分离的特点，防止学生面对一个具体问题，先入为主地带上程序或过程的观点去分析、解决问题，数据结构中对算法的描述不应该使用高级程序设计语言，而应该采用数学语言（带自然语言的算术、代数运算、函数运算等） ，更不应该片面强调教材中的算法都在计算机上运算通过，因为所有这些算法在今天看来都是最基本的、简单的，它们的正确性是容易判定的而且，采用算法刻画数据结构上的基本运算操作，应该介绍可支持算法执行的计算模型；第四，使用抽象的数学语言描述数据结构上的基本运算，欲说明这种运算的含义和正确性，应该介绍操作语义的描述方法（至少要说明存在计算的正确性问题） ，通过对简单数据结构上基本运算语义的描述，帮助学生初步建立计算的正确性这样一种认识和概念但是，这样一种客观的要求在涉及一些诸如动态数据结构那样的对象时，限于学生的基础和课时，进一步的内容应该将来由程序设计方法学、形式语义学等课程去完成事实上，一旦采用数学语言来刻画算法的运算操作，就比较容易引入操作语义方法来描述语义此时，由于算法描述采用数学语言，引入了支持描述语言的计算模型，因此，无论是采用状态机或元语言描述基本运算操作，建立操作语义将是自然的，而且，有助于学生深入认识数据结构知识；第五，对抽象数据类型的讨论可适当深入，以便引出面向对象表示方法。
从内涵发展的角度考虑，为了支持未来面向对象程序设计方法和技术的学习， “数据结构”课程的内容中拟加强抽象数据类型、数据的对象表示等内容，并展示面向对象方法、面向对象程序设计方法与技术及其发展前景，但不作深入讨论学生基础好、师资力量强的学校可通过抽象数据类型的代数理论，可概要介绍刻画复杂对象语义的基本方法和发展前景第六，鼓励教师结合学科范型（也称范式） ，将学科方法论的内容融入教学过程之中（对教师暂不作基本要求） ，以帮助学生建立与“数据结构”课程内容相关的科学的思想方法通过上述分析， “数据结构”课程的教学应该注意两个层面的交叉线索从学科抽象描述求解问题与具体实现解决问题相分离的发展要求出发，第一条线索是从基本数据结构的角度，介绍数据类型、结构类型、存储结构、表、字符串、数据存储、树、图、指针、文件等内容，第二条线索是从运算及其正确性和比较数据结构优劣的角度介绍计算模型、算4法、效率、基本运算操作及其语义正确性，并努力将科学哲学的思想方法融入到教学内容之中两条线索在抽象数据类型处实现合一然后介绍抽象数据类型、抽象数据类型的代数理论（抽象数据类型的语义） 、对象、面向对象的数据表示方法，对象理论（不涉及对象的语义理论） ，突出数据掩蔽与操作封装、分层分类描述与属性继承的思想，反映数据结构发展的潮流。
这样一种内容设计上的安排，不仅可以从内涵的角度支持面向对象的程序设计和（移动、智能）Agent 计算，而且可以支持人工智能知识表示中从框架、状态空间树向语义网络的发展，向学生展示一个新的发展天地，并且，减少了将来研究生学位课程“形式语义学”中可取材内容偏多的压力，为后续课程提供必要的基础5．课外教学要求本课程的课外教学内容和形式主要由学生读书。