声明：大部分内容来自《大话数据结构》一书
Ch1 数据结构一些基本概念和术语
1.1 基本概念
- 数据
- 数据元素：组成数据的、有一定意义的基本单位。通常作为整体被计算机处理。也被称为记录
- 数据项：数据元素可由多个数据项组成，数据项是数据不可分割的最小单位
- 数据对象：性质相同的数据元素的集合，是数据的子集。
- 数据结构：相互之间存在一种或多种特定关系的数据元素的集合。
关系：
数据_由多个..组成>数据对象
^|
性质相同的数据元素的集合||包含多个
|v
数据元素_>数据项（最小单位）
eg：
生物——————————————>禽类
|
|
v
鸡——————>嘴/眼睛/….
1.2 逻辑结构和物理结构
- 逻辑结构：
- 集合结构：结构中的数据元素出了同属于一个集合外，没有其他关系
- 线性结构：一对一
- 树结构：一对多
- 图结构：多对多
- 物理结构：
- 顺序存储结构
- 链式存储结构
Ch2 算法
函数的渐进增长：
两个函数h(n)和g(n)，如果存在一个n值使得n选值大于此n时h(n)总大于g(n)，那么我们称h(n)的渐进增长快于g(n)。推导大O阶方法：
- 用常数1取代运行时间中的加法常数。（所以常数阶全都是O（1）而非O（某个常数））
- 在修改后的运行次数函数中，只保留最高阶项。
- 若最高阶项存在且不是1， 则去除与这个项相乘的常数。
- 常见的时间复杂度排序：
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2^n)<O(n!)<O(n^n)
左3：比较优秀；中2：一般：右：差
Ch3 线性表
零个或多个相同类型的数据元素的有限序列。
3.1 特点：
- a1~an-1有且只有一个后继元素，a2~an有且只有一个前驱元素
- 表内元素个数有限
- 表内元素从1开始标识（实现时使用的数组本身则是从0计数）
- n=0时称为空表
- 在较复杂的线性表中，一个数据元素可由多个数据项组成（eg：学号+姓名+性别+出生年月……）
3.2 存储结构
1) 顺序存储
指用一段地址连续的存储单元依次存储线性表的数据元素。
- 可用一维数组类实现顺序存储结构。
- 优点：查找复杂度O(1)；无需为表示表中元素间的逻辑关系增加额外的存储空间
- 缺点：插入/删除复杂度O(n)；线性表长度变化较大时，难以确定存储空间的容量；造成存储空间的碎片
由于顺序存储这样那样的问题，我们有了另外一种存储方法：
2) 链式存储
链式存储中，对每个数据元素来说，出了存储其本身的信息外，还要存储一个指示其直接后继（的存储位置）的信息。
数据域：存储数据元素信息的域
指针域：存储直接后继位置的域，指针域中存储的信息称作指针或链
结点：指针域和数据域组成的数据元素映像，称为结点
n个结点链结成一个链表，即为线性表的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以称为单链表
头指针：链表中第一个结点的存储位置称为头指针（是个指向第一个结点的指针），若链表有头结点，头指针则是指向头结点的指针。
- 线性链表的最后一个结点指针为“空”。
- 无论链表是否为空，头指针均不为空。头指针是链表的必要元素。
头结点：在单链表的第一个结点前附设一个结点，称为头结点，里面的数据域可以不存储任何信息，指针域存储指向第一个结点的指针
(！注意这个指针不是头指针，头指针指向的头结点本身)。
- 头结点不一定是链表必须要素
- 头结点是为了操作的统一/方便设定的，这样对第一元素结点前插入结点和删除第一结点放在第一元素的结点之前，其数据域一般无意义。
参考：http://blog.csdn.net/zhenyusoso/article/details/6092843 中图2
空表：线性表为空表时，头结点的指针域为“空”。
代码描述：p是指向线性表第i个元素的指针，则该结点ai的数据域可用p->data表示，p->data的值是一个数据元素，结点ai的指针域可用p-next来表示（指向第ai+1个元素的指针），如果p->data=ai，那么p->next->data=ai+1