新学期马上就开始了，你准备好了吗？^_^

1. 课程性质和地位 

  “数据结构”是计算机科学与技术、数字媒体技术等专业本科生的专业基础课程中的一门重要的核心课程。

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

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

2. 课程介绍

    “数据结构”其实并不依赖于任何一种编程语言，这门课讲的是有效解决问题的方法和原理，编程语言是实现这些方法的工具而已。练习平台拼题A（https://pintia.cn/）提供了三十多种编程语言的编译器/解释器：gcc、g++、clang、clang++、octave、openjdk、python 2、python 3、ruby、bash、cat、clisp、fpc、gfortran、go、ghc、lua、luajit、mcs、node、ocamlc、php、perl、awk、dmd、racket、valac、vbnc、kotlinc、swiftc、gfortran、octave —— 你只要会用其中任何一种，就可以下课刷题玩啦~

    学过一门编程语言，你是否大概习惯了计算机的思维方式呢？这就像刚入门的泥瓦匠，学会了如何砌一堵坚实的矮墙，能成功砌起一圈猪圈并且因为一群猪都拱它不倒而暗自欣喜（总感觉哪里不对，谁是猪……）。而学习数据结构，就像学习构造更复杂建筑的原理，教你如何盖一座精巧的小型别墅，麻雀虽小但五脏俱全。今后如果你有兴趣了解建筑摩天大厦的技术，建议学习“软件工程”，学会如何把一个团队的人组织在一起，有条不紊地完成一个百万行以上代码量的软件产品。

    要学好这门课，你要有每周投入8小时（或者更多）的决心，其中听课只占一小部分 —— 每次讲课的时间一般只有1小时左右，重要的是课后的练习。光说不练嘴把势，只了解原理是远远不够的，你必须在实践中去深刻体会每一个概念的运用，才能真正知道经典的数据结构为什么存在、以及在什么情况下可以最好地解决什么样的问题。

3.  课堂教学设计

  课堂教学内容分在三大逻辑结构（线性结构、树型结构和图型结构）基础上，讲解存储模式及基本算法基本结构。

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

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

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

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

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

5. 实践教学设计

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

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

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

6. 教学模式设计

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

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

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

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

通过本课程的教学，使学习者懂得数据结构的一般原理，掌握表、树、图等基本结构的特点，学会对算法的评估方法。培养学习者的算法设计能力、程序设计能力，以及用软件方法处理问题的能力，培养学习者的分析、对比、归纳、综合和创新能力，为后续学习专业课程，设计系统程序打下坚实的理论基础。

  （1）个人综合成绩由单元测验、PTA测试、期末考试和课堂讨论组成

  （2）MOOC平台上的成绩，最后会折合成平时成绩的一部分

学习者应具备以下几个方面的基础知识：

 l 熟练掌握C/JAVA语言；

 l 掌握基本图论知识，初步概率知识；

 l 掌握常用的数学术语、集合和关系、对数、级数求和、递归和递推等概念；

 l 熟练运用一种编程环境。

（1）教材

   陈卫卫、王庆瑞编著 《数据结构与算法》（第三版） 高等教育出版社

（2）参考书

l 严蔚敏. 数据结构与算法．北京:清华大学出版社, 2020

l 陈越主编. 数据结构. 北京:高等教育出版社, 2021

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卷 排序与查找

本课程的学习者，要注意以下事项，确保教学活动能够深入、有效地进行。

l要事先具备基本的C语言基础知识，避免降低听课效果。

l视频授课的内容是基础的核心内容，要认真学习，细心领会。

l要按时完成教师指定的作业，尤其是上机实践作业。

l要积极参与师生互动，主动获得教师的指导。