数据结构的重要性:

在进行程序设计时,对于要处理的一类数据,程序员必须选择一种数据结构来进行这类数据的添加,修改,删除,存储等操作.
如果在选择数据结构时做了错误的决定,那么程序执行起来可能非常低效,如果选错了数据类型,后果不堪设想.

数据结构的分类:

基本数据类型: 整数,浮点,布尔,字符 
结构化数据类型: 字符串,数组,指针,列表,文件 
抽象数据类型: 堆栈

数据结构加上算法等于高效的可执行程序
精心选择的数据结构可以带来最优效率的算法,数据结构的选择至关重要!

数组

数组结构其实就是紧密相连的可数内存,数组的下标从内存的起始位置的第几区块.

数组分为:
一维数组,
Score[0]*5
二维数组,
number = [[11,12,13],[22,24,26],[33,35,37]]
多维数组,
arr = [ [ [11,22,33],[44,55,66] ],  [ [77,88,99],[12,12,12] ] ]

链表

许多相同数据类型的数据项按特定规则排序而成的线性表.

特点
各个数据项在计算机内存中的位置是不连续且随机存放的.
优点
数据的插入与删除都非常方便,有新数据加入就向系统申请一块内存空间,
数据被删除就把这块内存空间还给系统.
加入和删除都不需要移动大量的数据.
缺点
设计数据结构比较麻烦,并且查找数据时也无法像静态数据(如数组)那样可随机读取数据,必须按序查到该数据为止.

动态分配内存空间
最常使用的就是单向链表,单向链表基本上由数据字段和指针两个元素组成,指针会指向下一个元素在内存中的地址. 

单向链表的第一个节点是链表头指针,最后一个节点的指针为None,表示链表尾,不指向任何地方.

单向链表的所有结点都知道下一个节点在哪,但是不知道前一个结点的位置.
因此,在单向链表的所有操作中,第一个结点指针就显得尤为重要.只要知道表头指针就可以遍历整个链表,进行添加删除操作.
除非必要不可移动表头指针.

堆栈

堆栈是一组具有相同数据类型的组合,具有后进先出的特性.
所有的操作都是在堆栈的顶端进行的.

堆栈是抽象型数据类型(ADT)

基本操作
create  创建一个空堆栈
push    把数据压入堆栈顶端,并返回新堆栈
pop     从堆栈顶端弹出数据,并返回新堆栈
isEmpty 判断堆栈是否为空堆栈,是则返回true,不是则返回false
full    判断堆栈是否已满,是则返回true,不是则返回false

队列

先进先出的数据结构,和堆栈一样都是有序线性表的抽象数据类型(ADT)
拥有加入和删除两种基本操作,而且使用front和rear两个指针来分别指向队列的前端和末尾.

基本操作
create 创建空队列
add 将新数据加入队列末尾,返回新队列
delete 删除队列前端的数据,返回新队列
front 返回队列前端的值
empty 若队列为空,返回true,否则返回false

树

树形结构是非线性结构,操作系统和数据库管理系统都是树形结构
用来描述节点与节点之间的层次关系

由一个或一个以上的结点组成,特殊节点为root

每个节点可以代表一些数据和指针组合而成的记录
其余节点可以分为n>=0个互斥的集合,
每个子集本身也是一种树形结构及此根节点的子树.

一颗合法的树可以互相连接,但是不能形成无出口的环路

专有名词:
度数:结点的子树个数
层数:树的层数
高度:树的最大层数
树叶:终端结点
父节点:上一层结点
子节点:下一层结点
祖先:节点路径上的所有节点
子孙:节点下的任意节点
兄弟节点:
非终端节点:除终端节点以外的节点
同代:相同层数的节点
森林:n>=颗互斥树的集合

二叉树

一般的树形结构在内存中的存储形式以链表为主.
data|link1|link2|      |linkn

对于n叉树来说.因为每个节点的个数都不同,所以我们必须要为每个节点预留存放n个连接字段的最大存储空间.这种n叉树十分浪费存储空间.
n叉树有m个节点,链接浪费率为{m*(n-1)+1}/m*n
n=2时,二叉树的链接浪费率为1/2
n=3时,三叉树的链接浪费率为2/3
n=4时,四叉树的链接浪费率为3/4
当n=2时链接浪费率最低,所以为了改进存储空间浪费的特点,我们常用二叉树结构来取代其他的树形结构

二叉树是一个由有限节点所组成的集合,此集合可以为空集合,或由一个树根及其左右两个子树所组成.(二叉树最多只能有两个子节点)
llink|data|rlink
二叉树与一般树的区别:
树不可以是空集合,二叉树可以
树的度数为d>=0,二叉树的度数为[0,2]
树的子树之间没有次序,二叉树有次序,分为左子树和右子树,互斥.

图

讨论两个顶点之间是否连通,
在连接两顶点之间加上权值(成本,开销),这类图称为"网络".

无向图(A,B)
有边但是没有方向
V = {A,B,C,D}
E = {(A,B),(C,D),(B,C),(A,D)}

有向图<A,B>
有边有方向
V = {A,B,C,D}
E = {<A,B>,<C,D>,<B,C>,<A,D>}

哈希表

…