数据结构基本概念
1 数据：数据是用来描述现实世界的数字、字符、图像、声音，以及能够输入到计算机中并能被计算机处理的符号集合
2 数据元素：数据元素是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理，通常也称为“元素”、“记录”、“节点”等
3 数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集
4 数据结构：在实际问题中，数据元素不是孤立存在的，而是在相互之间存在一种或多种特定的关系，这种数据元素相互间的关系称为“数据结构“
注：我觉得应该重点理解”数据元素“和”数据结构“
数据元素举例：在学生信息表中，可能含有姓名、学号、性别等字段（属性），每个学生的信息可以称为一条记录，也就是一个数据元素，并且一般作为整体处理
数据结构：包含数据逻辑结构和数据存储结构两方面的描述
一、数据的逻辑结构
1 集合结构 : 集合结构的数据元素除了同属于一个集合外,他们之间没有任何联系.
2 线性结构 : 数据元素存在”一对一”的关系
3 树形结构 : 数据元素存在”一对多”的关系
4 图形结构 : 数据元素存在”多对多”的关系
二、数据的存储结构
数据的存储结构就是数据元素及其相互关系的存储方式。要想用计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。
按照数据的存储结构，一般将数据结构分为顺序存储结构、链式存储结构、索引存储结构和散列存储结构。
1 顺序存储结构 : 主要特点是逻辑上相邻的数据元素在物理位置上也是相邻的。
2 链式存储结构 : 借助指针表达数据元素之间的逻辑关系。
3 索引存储结构 : 在存储数据元素的同时，还建立附加的索引表。通过索引表，可以快速的找到存储数据元素的节点。
4 散列数据结构 : 根据散列函数和处理冲突的方法确定数据元素的存储位置
说明：
数据的逻辑结构和数据的存储结构是指一个事物的两个方面，而不是两个事物。一种逻辑结构可以映射为多种存储结构，而一种存储结构也可以对应多种逻辑结构。
抽象数据类型：数据类型名称、数据对象、数据关系及其基本操作科学完整的描述
一般形式如下：
ADT <抽象数据类型名> {
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
} ADT <抽象数据类型名> ;
“线性表”抽象数据类型的定义
ADT List {
数据对象：D={ai|aiElemSet, i=1,2,3…,n, n>=0}
数据关系：R={<ai-1,ai>|ai-1,ai D, i=2,3,… n }
基本操作：
InitList(*L):建立一个空的线性表
ListEmpty(L):判定线性表是否为空。若为空，则返回True
ListLength(L):获取线性表中数据元素的个数
TraverseList(L):遍历线性表中数据元素
ListInsert(*L, i, e):将数据元素插入到线性表中第i个位置处，线性表长度加1
ListDelete(*L, i, *e):删除线性表中第i个位置的数据元素，并存放到e中，线性表长度减1
Find(L, e):查找数据元素e所在位置
GetElem(L, i, *e):从线性表中获取第i个位置处的数据元素，并存放到e中
GetPrior(L, x, *pre_e):在线性表中获取数据元素x的前一个数据元素的值，并存放到pre_e中
GetNext(L, x, *next_e):在线性表中获取数据元素x的后一个数据元素的值，并存放到next_e中
ClearList(*L):将线性表置空
} ADT List;
算法特征
定义：算法是对特定问题求解步骤的一种描述，它是指令的有限序列。
算法的5个重要特征：
（1） 可行性
（2） 有穷性：算法的有穷性是算法和程序的分界点。
（3） 确定性
（4） 有输入
（5） 有输出
算法的度量及分析
（1） 时间效率：时间复杂度 (time complexity)---算法开始运行到结束所需时间（假设执行每条语句的时间均为单位时间）
（2） 空间效率：空间复杂度 (space complexity)---算法所需存储空间的量度
*时间复杂度的分析
示例：T(n)=O(n2)
T(n)用来表示时间复杂度，O(n2)表示具体的时间复杂度为n2 ;
常见时间复杂度：
（1）常量阶：O(1)
（2）线性阶：O(n)
（3）平方阶和立方阶：O(n2)和O(n3)
（4）对数阶：通常以2为底—O(log2n)
（5）其他：指数阶—O(2n), 阶乘阶—O(n!)
常用时间复杂度所耗费的时间从小到大依次为：
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)