本章学习了数据结构的基本概念和术语,以及算法和算法时间复杂度的分析方法。主要内容如下:
(1)数据结构是一门研究非数值计算程序设计中操作对象,以及这些对象之间的关系和操作的学科。
(2)数据结构包括两个方面的内容:数据的逻辑结构和存储结构。同一逻辑结构采用不同的存储方法,得到不同的存储结构。
(3)抽象数据类型是指由用户定义的、表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称,具体包括三部分:数据对象、数据对象上关系的集合,以及对数据对象的基本操作的集合。
(4)算法是为了解决某类问题而规定的一个有限长的操作序列。算法具有5个特性:有穷性、确定性、可行性、输入和输出。
(5)算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度,以考察算法的时间和空间效率。
本章的学习要求如下:
- 掌握数据结构的相关概念,包括数据、数据元素、逻辑结构、存储结构等;
- 掌握数据结构所含两个层次的具体含义及相互关系;
- 了解抽象数据类型的定义、表示与实现方法;
- 了解算法的特性和评价标准;
- 重点掌握算法时间复杂度的分析方法。
本章练习:
教材P16页第1章习题1-6
本章学习建议完成时间:10月10日。