总体要求
• 了解数据结构的意义、数据结构在计算机领域的地位和作用
• 掌握数据结构各名词、术语的含义和有关的基本概念，以及数据的逻辑结构和存储结构之间的关系
• 了解使用Java语言对数据结构进行抽象数据类型的表示和实现的方法
• 了解算法的五要素
• 掌握计算语句频度估算算法时间复杂度的方法
相关知识点
• 相关术语：数据、数据元素、数据对象、数据结构
• 数据逻辑结构：集合、线性结构、树和图
• 数据的物理结构：顺序和非顺序结构
• 算法的五要素和时间复杂度及空间复杂度
学习重点
• 数据的逻辑结构和存储结构及其之间的关系
• 算法时间复杂度的计算
学习难点
• 算法时间复杂度的计算
1.1
1.2 基本概念和术语
1.2.1 基本概念和术语
1. 数据 信息的载体
2. 数据元素 数据的基本单位，由多个数据项组成
3. 数据对象 具有相同特征的数据元素的集合，是数据的一个子集
4. 数据结构 简称DS（Data Structure），是数据及数据元素的组织形式。
数据结构包含两个方面的内容，一是数据对象，二是数据对象中数据元素之间内在的关系。数据结构通常有四类基本形式：集合结构，线性结构，树型结构，图形结构或网状结构。
（1）集合结构：同处一个集合，没啥关系
（2）线性结构：一对一
（3）树型结构：一对多
（4）图状结构：多对多
5. 数据类型 一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合，如整数类型、字符类型等。
1.2.2 数据的逻辑结构。
从逻辑上可以把数据结构分为线性结构和非线性结构，上述数据结构的定义就是数据的逻辑结构（Logic Structure），主要包括：集合、线性、树和图形结构，其中集合、树和图形结构都属于非线性结构。
数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系集，它反映了D中各数据元素之间的前驱后继关系，通常记为R，即一个数据结构可以表示成二元组B=(D,R)。
注意，<x,y>意为x和y之间存在"x领先于y"的次序关系。而(x,y)表示x和y之间没有次序上的关系。
1.2.3 数据的物理结构
数据的物理结构又称存储结构，它的实现依赖于具体的计算机语言。数据存储结构有顺序和链式两种不同的方式。
顺序存储的特点是数据元素在存储器的相对位置来体现数据元素相互间的逻辑关系，顺序存储结构通常用高级编程语言中的一维数组来描述或实现。
整个数组在存储器中占用的是一片连续的存储空间。
在顺序存储结构的基础上，又可延伸出另外两种存储结构，即索引存储和散列存储。
索引存储就是在数据文件的基础上增加了一个索引表文件。通过索引表建立索引，可以把一个顺序表分成几个顺序子表，其目的是在查询时提高查找效率，避免盲目查找。
散列存储就是通过数据元素与存储地址之间建立起某种映射关系，使每个数据元素与每一个存储地址之间尽量达到一一对应的目的。这样，查找时同样可以大大提高效率。
链式存储结构是通过一组任意的存储单元来存储数据元素的，而这些存储单元可以是连续的，也可以是不连续的。
1.3 面向对象的数据结构表示
1.3.1 Java面向对象基础
1. 类的声明与实例化
2. 类的成员的定义与使用
3. 抽象类
4. 泛型类
典型 Map类 Map<K,V>
泛型类在使用时必须明确指定各类型参数对应的实际数据类型
1.3.2 面向对象的抽象数据类型
抽象数据类型（Abstract Data Type）。
在传统的数据结构教材中，抽象数据类型通常表示为｛D，S，P｝集合。
ADT抽象数据类型名
{
数据对象D：<数据对象的定义>
数据关系S：<数据关系的定义>
基本操作P：<基本操作的定义>
} ADT抽象数据类型名