第一章：绪论
1.杂乱的数据不能表达和交流信息。
数据之间是有联系的。
数据之间是有结构的。
在某种数据结构上可定义一组运算。
综上所述：《DS》主要研究内容：
计算机的操作对象——数据；
数据的各种逻辑结构和物理结构，以及它们之间的相应关系；
并对每种结构定义相适应的各种运算；
设计出相应的算法；
分析算法的效率。
常见的数据结构有：数组、栈、队列、表、串、树、图、文件等。
2.数据（Data）：所有能被计算机处理的符号的集合。
数据元素(Data Element)：是数据这个集合中的一个个体。
数据项（Data Item）：数据元素通常还可以分为若干个数据项，数据项是数据具有意义的最小单位。
数据对象(Data Object)：具有相同特性的数据元素的集合。
数据元素是数据的一个个体，数据对象是数据的一个子集。
万事万物=>数据——>数据结构（数据及其中的关系和规律）
数据结构（Data Structure）:是带有结构的数据元素的集合。
所谓结构就是数据元素之间的关系，可有一种或多种特定的关系。
用集合的形式描述，数据元素是一个二元组：
DS=(D,R)
其中：D是数据元素的有限集，R是D上关系的有限集。
简言之，数据元素和其相互关系成为数据结构。
逻辑关系（Logic Structure）：数据元素之间的结构关系。
物理结构（Physical Struture）:指数据结构在机器内的表示。也称存储结构，通常由顺序存储结构和链式存储结构。
算法的设计取决于逻辑结构。
算法的实现依赖于物理结构。
数据类型（Data Type）：一个值的集合和定义在这个值集上的操作的总称。
基本操作的分类：
引用型：查找
加工型: 插入、删除、更新、排序
3.算法概念：算法是对特定问题求解步骤的一种描述，是指令的有限序列。
算法的基本特性：
有穷性：算法经过有限步结束。
确定性：每一步必须有明确的含义。
可行性：每一步是可执行的。
输入：有一个满足给定的约束条件的输入
输出：满足给定的约束条件的结果
算法与程序的区别
算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以由多种算法。
程序是用某种程序设计语言对算法的具体实现。
主要区别在：有穷性和描述方法
程序可以使无穷的，例如OS,算法是有穷的。
程序是用程序设计语言描述，在机器上可以执行。
算法还可以用框图、自然语言等方式描述。
算法分析
如何衡量一个正确算法的好坏？
衡量的三个尺度：
（1）运行所花费的时间（算法的时间特性）
（2）所占用存储空间的大小（算法的空间特性）
（3）其它（正确性、可读性、健壮性等）
时间和空间特性的巨大改进源于更好的数据结构和算法。
语句频度（Frequency Count）
语句可能执行的最大次数
时间复杂度（Time Complexity）
设算法中所有语句的语句频度为t(n),
f(n)是当n趋向无穷大时与t(n)为同阶无穷大，
则算法的时间复杂度是T(n) = O(f(n))
第二章：线性表
1.线性表是n个数据元素的有限序列，记为
L=（a(1),a(2),...,a(i-1),a(i),a(i+1),a(n)）
线性表数据元素之间的关系是：
a(i-1)领先于a(i),a(i)领先于a(i+1).
称a(i-1)是a(i)的直接前驱元素，a(i+1)是a(i)的直接后继元素。
除a(i)外，每个元素有且仅有一个直接前驱元素，
除a(n)外，每个元素有且仅有一个直接后继元素。
线性表中数据元素的个数n(n>=0)称为线性表的长度，
当n=0时，成为空表。
线性表形式化定义，Linear_list=(D,R)
其中，D={a(i) | a(i)属于D(0),i=1,2,...,n,n>=0}
R={<a(i-1),a(i)> | a(i-1),a(i)属于D(0),i=2,3,...,n}
D(0)为某个数据对象
R表示线性表中数据元素之间的相邻关系。
2.线性表十大基本运算
INITIATE(L) 初始化操作 设定一个空的线性表
LENGTH(L) 求长度函数 函数值为线性表L中数据元素的个数
GET(L,i) 取元素函数 1<=i<=LENGTH(L)时返回L中的第i个数据元素，否则为空元素NULL。i成为该元素在L中的位序。
PRIOR(L,elm) 求前驱函数 elm为L中的一个数据元素，若它的位序大于1，则函数值为elm前驱，否则为NULL
NEXT(L,elm) 求后继函数 若elm的位序小于表长，则函数值为elm的后继，否则为NULL
LOCATE(L,x) 定位函数 给定值x,若x不在表中，则返回0，否则，返回x在表中第一次出现的位序。
INSERT(L,i,b)插入操作 在第i个元素之前插入新元素b,i的取值范围为：1<=i<=n+1,i=n+1表示在表尾插入，n为表长。
DELETE(L,i) 删除操作 删除线性表L中的第i个元素，1<=i<=n
EMPTY(L) 判空表函数 判L为空表，则返回布尔值“true”，否则返回布尔值“false”
CLEAR(L) 表置空操作 将L置为空表
3.线性表的顺序存储结构
用一组地址连续的存储单元一次存储线性表的元素。设线性表的每个元素占用k个存储单元，则第i个元素a(i)的存储位置为：Loc(a(i)) = Loc(a(1)) + (i-1)*k,其中，Loc(a(1))为线性表的起址。
方法1
方法2
方法3
4.线性表的链式存储结构
用一组任意的存储单元（不要求地址连续）来存储线性表的元素，每个元素对应一组存储单元（称为结点），每个结点包括两个域：存储数据元素信息的数据域和存储直接后继所在位置的指针域。
n个结点通过指针域组成的表，称为线性链表（单链表）。
线性链表最后一个节点的指针域为“空”（NIL或^）;
用一个头指针指示链表中第一个结点的存储位置；
5.循环链表
6.双向链表（double linked list）
第三章：栈和队列
1.栈的表示和实现
2.队列的表示和实现
