数据结构

课程概况

2019年1月课程被教育部评为国家精品在线开放课程。

1. 课程性质和地位

“数据结构”是计算机科学与技术、网络工程、信息安全等专业本科生的专业基础课程中的一门重要的核心课程。

在计算机学科中，本课程与其他课程的关系如图1所示。图中，大学数学、计算机基础、离散数学、C/C++语言等是本课程的先导课程，而其它课程（如操作系统、编译原理、计算机网络等）均以本课程作为先导课程。图中已罗列出一些专业课所用到本课程中的相关知识，比如，操作系统课程会用到队列、存储管理表等。本课程也是算法分析与设计、计算复杂性理论等高级课程的基础。因此，本课程在计算机教学工作中具有重要的地位。

图1 数据结构课程与其他课程的关系图

2. 课程目标

通过本课程的教学，使学习者懂得数据结构的一般原理，掌握表、树、图等基本结构的特点，各结构的存储表示和所涉及的运算，完成各运算的算法及其实现方法，学会对算法的评价方法。使学习者具有一定的算法设计能力，较强的程序设计能力，和实际应用能力，能够针对给定的简单问题设计出求解算法，包括问题的抽象、数据的提取、数据的组织、数据结构的确定（逻辑结构）、算法设计、数据的存储形式（物理结构）、编程实现、程序的调试和测试等。也为学习后续专业课程，设计系统程序打下坚实的理论基础和实践基础。

3. 教学环节

本课程通过视频授课、课外作业、教材阅读、上机实践，以及师生互动等环节实现课程目标。

学习者通过观看本课程提供的授课视频接受课堂教学，学习基本知识；通过阅读本课程指定的教材（《数据结构与算法》（第二版）．陈卫卫王庆瑞编著．北京：高等教育出版社. 2015.07），预习和复习视频授课内容；通过完成指定的“书面”练习题和上机练习题，巩固和充实课堂知识；学习者和教师互动，由一方向另一方提出问题请其解答，学习者以其释疑，教师则以其检查学习者完成学业的情况。

4. 课堂教学设计

课堂教学内容分为三大部分：基础知识（第一讲）、基本模型（第二至九讲）、基本问题（第十讲）。

基础知识部分是学习后续内容的基础，包括概念（算法的概念，数据结构的概念）、标准（对算法的评价标准）、方法（算法的描述方法和评价方法）。

基本模型部分是本课程最主要部分。这部分以查找、插入、删除运算为主线全面而系统地介绍表、树、图等基本数据结构的特点、存储方法、完成各运算的算法设计方法和实现程序、时空效率。因为，查找、插入、删除不仅是最基本的、最常用的，而且往往也是不可分的（通常联合使用，极少单独使用），其它某些运算还可以转化为这三种运算。将这三种运算构成的运算集作为一个整体，可以得出结构的整体时空效率。

最后一部分，以问题为导向（这里选用排序问题），介绍求解同一个问题的多种不同处理算法，通过对算法的评价，分析各算法的特点、效率、适用情况。

图2展示了这些课堂教学内容之间的关联关系。

图2 数据结构教学内容之间的概念图

5. 实践教学设计

本课程设计的实践教学（即上机实验）题分为基础性、综合性和设计性三大类。

基础性（即知识验证性）类实验题主要用于巩固课堂知识，其难度不大，实现程序不长（小程序），通常只需要将教材中的程序进行简单拼装，简单改造，简单模仿，简单细化。

综合性和设计性实验题属于大作业，实现程序较长，难度较大。顾名思义，完成综合性实验题需要将多个知识点进行综合，而完成设计性实验题则要实现从建模到解模的全过程，即实验者要独立完成：问题的抽象，数据的提取，数据的组织，数据结构的确定（逻辑结构），算法设计，数据的存储形式（物理结构），编程实现，程序的调试和测试等步骤。

6. 教学模式设计

对于基本概念，在讲清基本概念条文的同时，尽可能多地举例阐述概念的内涵，并强调规范术语用词，培养严谨的科学作风。

对于算法设计，遵循“少而精”的原则，突出重点，以点带面，通过对比，使学习者逐步建立设计“好”算法的意识。

对于表、树、图三大基本结构，依照“逻辑结构→物理结构→基本运算→基本算法→算法评价”这个脉络，研究每种结构的特点，给学习者一个清晰的研究主线，使学习者能够根据问题的特点选择合适的数据结构，进一步理解研究数据结构的意义。

对于学习者，可以按照“读、仿、改、究”的学习模式逐步提升自己的程序（算法）设计能力，并以此衡量自己当前达到的水平。具体地说，“读”就是研读（本课程中给出的）经典算法及其实现代码，领会算法设计思路、描述方式和实现代码的程序结构；“仿”是指对现有的求解原问题的算法进行简单搭建和修改，写出用来求解与原问题相近的新问题的模仿算法；而“改”则是，当应用场景或用户需求发生较大改变时，能够对现有算法进行改进，写出改进算法，这一阶段至关重要，不仅起到了深化理解知识的作用，而且对算法设计能力、分析能力，改进点的定位，改进措施的选定都是极大考验和锻炼；“究”指的是研究和探索给定问题的性质、特征，确定求解策略，设计出性能良好的求解算法。

课程大纲

第一周数据结构概述（总时长19'23''）
（一）为什么要学习数据结构(6'33")
（二）数据结构的概念(5'42")
（三）算法的概念和描述(7'48")
（四）算法的评价
概述单元测试

第二周顺序表（总时长30'44''）
（一）表结构的基本概念（5'52''）
（二）顺序表的插入和删除（5'45''）
（三）顺序表的查找（14'28''）
（四）应用示例（4'39''）
顺序表单元测验

第三周链表（上）(总时长22'57''）
（一）基本概念（11'19''）
（二）单向链表的构造（8'25''）
（三）单向链表的输出和查找（3'13"）
链表（上）单元测验

第三周链表（下）(总时长18'38''）
（一）链表的种类（4'02''）
（二）复杂链表的基本操作（4'30''）
（三）有序链表的构造（4'28''）
（四）应用示例-稀疏多项式求和问题（4'00''）
（五）小结（1'38")
链表（下）单元测验

第四周栈和队（总时长24'53''）
（一）栈（15'24''）
（二）队（9'29''）
栈和队单元测验

第四周散列表(总时长30'11'')
（一）散列函数(7'08'')
（二）散列表的处理算法(23'03'')
散列表单元测试

第五周树结构（上）（总时长53'24"）
（一）树的基本概念和存储方法（24'00"）
（二）二叉树的遍历（15'54"）
（三）二叉树的构造（13'30"）
树结构（上）单元测验

第六周树结构（下）（总时长57'13"）
（一）检索树（17'32"）
（二）平衡树（26'43"）
（三）哈夫曼树（12'58"）
树结构（下）单元测验

第七周图结构（上）（总时长48'07''）
（一）图的定义和有关术语(14'57")
（二）图的存储方法(8'08")
（三）图的遍历(15'50")
（四）图遍历算法的应用示例(9'12")
图结构（上）单元测验

第八周图结构（下）（总时长40'56''）
（一）最小生成树（27'11"）
（二）最短路径（13'45"）
图结构（下）单元测验

第九周排序（上）(总时长51'51"）
（一）排序的基本概念(4'41'')
（二）插入排序(14'14'')
（三）交换排序(18'11'')
（四）选择排序(14'45'')
排序（上）单元测试

第十周排序（下）（总时长17'29"）
（一）合并排序(7'45'')
（二）基数排序(9'44'')
排序（下）单元测试

预备知识

学习者应具备以下几个方面的基础知识：
 l 熟练掌握C/C++（传引用）语言；
 l 掌握基本图论知识，初步概率知识；
 l 掌握常用的数学术语、集合和关系、对数、级数求和、递归和递推等概念；
 l 熟练运用一种编程环境（例如，VC编译环境）。

参考资料

（1）教材
陈卫卫,王庆瑞编著．数据结构与算法（第二版）．北京：高等教育出版社, 2015.07
（“十二五”普通高等教育本科国家级规划教材）
部分参考答案下载地址：https://pan.baidu.com/s/1o83yAi2 （pdf文件，若下载后后缀消失，请手工添加文件后缀）
（2）参考书
l 张铭等编著. 数据结构与算法．北京:高等教育出版社, 2008
l 陈越主编. 数据结构. 北京:高等教育出版社, 2012
l Robert Sedgewick著，周良忠译．C算法（第一卷，基础、数据结构、排序和搜索）（第三版）．北京：人民邮电出版社 POSTS & TELECOM PRESS,2004
l Robert Sedgewick著，周良忠译．C算法（第二卷图算法）．北京：人民邮电出版社 POSTS & TELECOM PRESS,2004
l 计算机程序设计艺术（第3版）．Donald E.Knuth 著，苏运霖译．北京：国防工业出版社 Addison Wesley,2002
第1卷基本算法
第2卷半数值算法
第3卷排序与查找