常用的数据结构及算法

一、数据结构

（一）线性结构：一对一。

1.可以使用数组、链表来表示。数组又分为静态数组和动态数组两种。链表常用的是单链表。

2.两种特殊的线性结构：队列和栈。其中队列是先进先出（排队），栈是后进先出（类似弹夹）

（二）树形结构：一对多。

拓扑结构上是一对多的情况，逻辑存储上还是通过数组、链表（不是单链表了，因为不是一对一了）实现。

1.有双亲表示法、孩子表示法、孩子兄弟表示法。

1）双亲表示法：通过静态数组的方式，存储当前结点的数据、双亲的位置（根节点的双亲结点设置为-1）。该方法的优点是容易找到结点的双亲结点，但是找结点的孩子结点就需要遍历。

优化方式：除双亲的位置外，再增加一个长子域（最左孩子的位置），如结点无孩子结点，长子域设置为-1。

2）孩子表示法：链表形式，通过指针域指向各个孩子结点（一般的树，设置的指针域的个数为树的度；二叉树，就是两个指向孩子结点的指针域）。

优化方式一：因为每个结点的度不同，按树的度来设置指针域的话，容易造成资源浪费。

所以，可以增加当前结点的度，然后根据每个结点的度来设置指针域的个数。但该方法不同的结点度不同，而且还要维护度数据，维护复杂。

优化方式二：将每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为,空。然后n个头指针又组成一个线性表，采用顺序存储结构，存在一维数组中。

图中，child中的数据域，是表头中该元素的下标值。 

firstchild是指向子节点的头指针。

但该方法，寻找双亲结点又需要遍历，下图就是将双亲表示法和孩子表示法结合。

3）孩子兄弟表示法：任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，可以设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

上图调整了下形状，就是二叉树

2.常用的是二叉树。

每个阶段都是两种结果，比如开和关、0和1、真和假、上和下等等，都适合用二叉树结构来建模。

树2是左斜树，树5是右斜树，是线性结构，所以说线性结构是一种特殊的树形结构。 

满二叉树

完全二叉树 

3.二叉树的性质

1） 在二叉树的第i层上至多有个结点（i>=1）

2）深度为k的二叉树至多有个结点（k>=1）

3）对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1(青出于蓝而胜于蓝）

4）具有n个结点的完全二叉树的深度为，表示不大于x的最大整数

5）如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第）对任意结点i有：

4.二叉树的存储结构

1）顺序存储：一般只用于完全二叉树，否则会浪费存储空间（如下图所示，会造成空间的浪费）

2）二叉链表（一般用这种形式）

当前结点数据及左右孩子指针

线索二叉树：指向前驱和后继（前驱和后继是按照遍历的方式的定的，不是根据双亲和子结点）的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树 称为线索二叉树。

 

3.二叉树三种遍历方式：前序、中序、后序

（三）图结构：多对多。

二、算法

（一）查找

1.顺序查找：

优化方式：设置哨兵位置。

2.插值查找

3.

4.

5.

6.

7.哈希查找：上述的查找方式是通过将要查找的关键字与记录中的中关键字进行比较；

哈希查找则是通过构建哈希函数，将查找记录的关键词与存储的位置绑定，

（二）排序