数据结构

1.绪论:

1. 1 定义:

数据是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据结构十数据对象在计算机中的组织方式.数据结构是一个二元组 Data_Structure ＝（D，R），其中，D 是数据元素的有限集，R 是 D 上关系的有限集。

1.2 逻辑结构与存储结构:

逻辑结构是指数据间的相互关系.通常分为四类结构:线性结构,集合,树,图或网.(还有什么有序表之类的)

存储结构是指数据结构在计算机中的表示，又称为数据的物理结构。通常由四种基本的存储方法实现：

（1）顺序存储方式

（2）链式存储方式

（3）索引存储方式

（4）散列存储方式

1.3 算法复杂度:

主要分为时间复杂度和空间复杂度.

1.3.1 空间复杂度:

空间复杂度是指执行程序时,额外占用的存储空间的大小.

1.3.2 时间复杂度:

时间复杂度是指执行程序时,占用时间的大小.

时间复杂度只与待解决问题的规模(n)有关,与一步基本操作的工作量无关.

时间复杂度只考虑问题的宏观渐进性,意识是求解的难度随着问题规模的增大逐渐增大的趋势.如线性增长(o(n)).

1.3.3 算法特性:

输入.输出.有穷性.确定性.可行性.

2.线性表:

2.1 定义:

线性表是n个相同类型的数据元素组成的有限序列.是最简单的.最基础的数据结构(逻辑结构).线性表包括顺序表(数组)和链表.

2.2 特征:

线性表的第一个元素叫第一元素,最后一个元素是最后元素,中间元素的上一个元素叫前驱,后一个元素叫后继.

2.3 顺序表基本运算的复杂度:

插入,删除都是o(n).

2.4 顺序表优缺点:

优点: 节省空间,查找元素第i个元素比较简单(头+元素大小✖i)

缺点:插入.删除都需要移动数据.比较不容易确定存储空间.

2.5 链表:

2.5.1: 头结点:

头结点不存储数据.指针指向第一个节点.

头插法:读入的数据元素的顺序与生成的链表中元素的顺序是相反的。

尾插法读入的数据元素的顺序与生成的链表中元素的顺序是一致的。

3.栈和队列:

3.1 定义:

栈和队列是一种特殊的线性表.先进后出为栈,先进先出为队列.

3.2 栈:

插入和删除均在特定的一端进行.

最先进入的一端叫栈底,进行操作的一端叫栈顶.入栈成为Push,出栈称为Pop.

栈的一种定义：

1
2
3
4
5
6
7
8
9
10
11
12
13

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

typedef struct
{
 SElemType *base;

SElemType *top;

int stacksize;

}SqStack;

top指针表示栈顶，入栈时，top指针存入数据后移动，成为新的栈顶。出栈时，top指针回退。

3.3 队列：

一种先进先出的线性表。

入队的地方称为队尾，出队的地方称为队头，队尾指针rear,队头指针front。

4.串:

5.数组和广义表：

6.树：

7.图：

7.1 定义：

由点的集合和边的集合构成的集合，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。

7.2 图的相关术语：

度：节点的边数。入读是指向该节点的边数，出度是从该节点出发的边数。

强连通图：任意两点之间都联通的图

路径、路径长度：顶点 vp到顶点 vq之间的路径是指顶点序列 vp,vi1,vi2, …, vim,vq.。路径上边的数目称为路径长度。

7.3 图的存储：

7.3.1 邻接矩阵：

7.3.2 邻接表：

是图的一种顺序存储与链式存储结合的存储方法，类似于树的孩子链表表示法。就是对于图 G 中的每个顶点 vi，将所有邻接于 vi的顶点 vj链成一个单链表，这个单链表就称为顶点 vi的邻接表，再将所有点的邻接表表头放到数组中，就构成了图的邻接表。

在邻接表中，每条边都会出现两次，如果是n个顶点，e条边的邻接表，总共需要n个头节点和2e个表节点，比较适合存储比较稀疏的图。

7.4：图的遍历：

从图的某一个顶点出发，访问所有的顶点。

7.4.1 深度优先搜索：

从某一个顶点开始，访问一个顶点后，接着访问与这个顶点相邻的，未被访问过的顶点，直到所有的顶点都被访问过为止。

1
2
3
4
5
6
7
8
9
10

void DFS(Graph G,int v ) /*从第 v 个顶点出发递归地深度优先遍历图 G*/

{ 
visited[v]=TRUE;Visit(v); /*访问第 v 个顶点*/

for(w=FisrtAdjVex(G,v);w>=0; w=NextAdjVex(G,v,w))

if (!visited[w]) DFS(G,w); /*对 v 的尚未访问的邻接顶点 w 递归调用 DFS*/

}

遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间则取决于所采用的存储结构。当以邻接矩阵为图的存储结构时，查找每个顶点的邻接点所需时间为O(n2 ) ，其中 n 为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为 O(e)，其中e 为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为 O(n+e) 。

7.4.2: 广度优先搜索：

从某一个顶点开始，先访问该顶点，再访问与该顶点相邻的所有未访问过的顶点，然后在对这些邻接顶点的邻接顶点做相同的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void BFS (Graph G,int v)

{
InitQueue(Q); /*置空的辅助队列 Q*/

visited[v]=TRUE; Visit(v); /*访问 v*/

EnQueue(Q,v); /*v 入队列*/

while (!QueueEmpty(Q)) 

{DeQueue(Q,u); /*队头元素出队并置为 u*/

for(w=FistAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))

if(!visited[w])

{visited[w]=TRUE; Visit(w);

 EnQueue(Q,w); /*u 尚未访问的邻接顶点 w 入队列 Q*/
}}

}
注意入队列的顺序，先入队列的点先出队列进行的下一步的bfs，可能会影响遍历顺序。

广度优先搜索遍历图的过程实质是通过边或弧找邻接点的过程，其时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。

7.5 最小生成树：

生成树：所谓连通图 G 的生成树，是 G 的包含其全部 n 个顶点的一个极小连通子图。它必定包含且仅包含 G 的 n-1 条边。

最小生成树是指在图的所有生成树中，边权和最小的树。

下面给出两种求最小生成数的算法。

7.5.1：Prim算法：

建立u，v(所有顶点集合)，t三个集合。任选一个顶点开始。把该顶点加入u，寻找一条边，这条边的两个顶点一个在u中，一个在v-u中，而且这条边的权值在符合所有的边中最小，把v-u中的那个点加入u，把这条边加入t，反复进行操作，知道u中包括了所有的顶点为止。

时间复杂度o（n2）(邻接矩阵)o(n+e)(邻接表)，比较适合于边稠密的网。

7.5.2: Kruskal 算法:

1
2
3
4
5
6
7
8
9
10
11
12
13

void Kruskal (G,T){
T=V;
ncomp=N;
while（ncomp>1）
{
	从G中找到取出并删除权值最小的边，记为x.
	if(x的两个顶点在T中并没有相连相连)
	{
		把这条边加入t；
		ncomp--；
	}
}
}

时间复杂度o（enlog2e）比较适合边稀疏的网。

7.6：最短路径：

7.6.1:单源最短路：

给定有向图g和源点v，求该点到所有顶点的最短距离。

Dijkstra 算法:

s是已经求出最短路的集合,v-s是未求出最短路的集合.

首先把顶点加入s,把与v最近的v1也加入s.

然后在v-s中寻找vx到vo与vx到v1,遍历找最短的加入s.

依次进行操作.

时间复杂度是 O(n 2 ).

7.6.2: 多源最短路:

从 Vi到 Vj的所有可能存在的路径中，选出一条长度最短的路径。时间复杂度是 O(n 3 ).

1
2
3
4
5
6
7
8
9
10
11
12

for(int k = 0 ; k < size ; k ++)
{
    for(int i = 0 ; i < size ; i ++)
    {
        for(int j = 0 ; j < size ; j ++)
        {
            if(zu[i][j] > zu[i][k] + zu[k][j]){
            	zu[i][j] = zu[i][k] + zu[k][j];
            } 
        }
    }
}	 

7.7: 拓扑排序:

7.7.1: AOE网:

是一张有向无环图.

顶点表示事件,边表示事件.

拓扑序列:如果存在vi到vj的路径,则在这个序列中i位于j之前.有向图的序列不唯一,无环图一定有拓扑序列,有环图一定没有拓扑序列.

算法:

(1)选图中入度为0的顶点输出.

(2)删除该顶点以及预期相连的所有边.

(3)重复进行 直到所以的顶点都被输出.

整个算法的时间复杂度 为 O（e+n）。拓扑排序的序列可能不唯一。

7.7.2: 关键路径:

首先要搞清楚几个概念:

7.7.2.1:事件的最早发生时间:

记为ve[k]

是从原点到发生事件的点的最长的路径长度.(含义是这个事件要在前面所有的事件都结束了之后这个事件才能就开始,所以所需要时间最长的活动为制约条件)

7.7.2.2:事件的最晚发生时间:

记为vl[k]

开始节点为0,汇点为其最早开始时间.对于其他节点,从汇点开始减去其到上一个顶点的路径长度.

7.7.2.3:活动的最晚发生时间:

事件最晚时间减去活动边.

7.7.2.2:活动的最早发生时间:

就是活动源头一侧的时间的最早发生时间.

活动的最早和最晚开始时间相同的活动就是关键活动.由关键活动组成的路径被称为关键路径.

整个工程完成的时间为：从有向图的源点到汇点的最长路径。

8.查找:

8.1: 顺序查找:

第一个元素向后,依次顺序查找.

8.2: 折半查找:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

int Search_Bin (SSTable ST, KeyType key ) 

{low = 1; high = ST.length; /*置区间初值*/

while(low <= high)

 {mid=(low + high)/2;

 if（

key == ST.elem[mid].key )

 return mid; /*找到待查元素*/

 else if(key<ST.elem[mid].key) )

 high = mid - 1; /*继续在前半区间进行查找*/

 else low = mid + 1;/*继续在后半区间进行查找*/

 }

 return 0; /*顺序表中不存在待查元素*/

}

要求数据顺序存储 且有序。

o（logn）

8.3：索引查找：

①查找表要求顺序存储；②查找表分成 n 块，当 i>j 时，第 i 块中的最小元素大于第 j 块中的最大元素。

过程：①首先确定所要查找关键字在哪一块中。②在所确定的块中用顺序查找查找关键字。

平均查找长度n+l+2➗2 其中l是每块长度 n是总长度 若要使平均次数最小 每块的长度是根号n

8.4： 监视哨：

不是带查找元素，是人为构造的一个数据，放在特定的位置，用来处理数组越界等情况。所以有监视哨的表，查询的元素要比待查元素多一个（失败时）成功就不需要了。

8.4：二叉排序树：

8.4.1： 静态查找表与动态查找表：

动态查找表：有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。

8.4.2： 定义：

空树或者对于所有的子树都有：左子树＜根节点＜右子树

查找时：

1
2
3
4
5
6
7
8
9
10
11
12
13

BSTree SearchBST(BiTree bt, KeyType key)/*在根指针 bt 所指二叉排序树中，递归查
找某关键字等于 key 的元素，若查找成功，则返回指向该元素结点指针，否则返回空指针 */
{if(!bt) return NULL; 

else if(bt->key==key) return bt; /*查找成功*/ 

else if(key＜bt->key)

return SearchBST(bt->lchild,key); /*在左子树中继续查找*/

 else return SearchBST(bt->rchild, key); /*在右子树中继续查找*/

} 

8.5：平衡二叉树：

或者是一棵空树，或者是具有下列性质的二叉排序树：它的左子树和右子树都是平衡二叉树，且左子树和右子树高度之差的绝对值不超过 1。

在插入过程中，采用平衡旋转技术：左单旋转；右单旋转；先左后右双向旋转；先右后左双向旋转。

在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡 树的深度，和 log2n 相当。

8.6：哈希表：

基本思想是首先在元素的关键字 key 和元素的存储位置 p 之间建立一个对应关系 H，使得 p=H(key)，H 称为散列函数。创建散列表时，把关键字为 key 的元素直接存入地址为 H(key)的单元；以后当查找关键字为 key 的元素时，再利用散列函数计算出该元素的存储位置 p=H(key)，从而达到按关键字直接存取元素的目的。

装填因子：

a=填入结点数/空间大小

①直接定址法：H(key) = a  key + b

适合于：地址集合的大小 = = 关键字集合的大小

⑤除留余数法：H(key) = key MOD p ，其中 p≤m (表长)并且 p 应为不大于 m 的素数

8.6.2： 解决冲突方法：

①开放定址法：当关键字 key 的散列地址 p= H（key）出现冲突时，以 p 为基础，产生另一

个散列地址 p1，如果 p1仍然冲突，再以 p 为基础，产生另一个散列地址 p2，……，直到找

出一个不冲突的散列地址 pi，将相应元素存入其中。

主要有以下三种：

●线性探测再散列

di=1，2，3，…:， m-1

特点：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

●二次探测再散列

di=±1 2，±2 2，…，±k 2 (k≤m/2)

特点：冲突发生时，在表的左右进行跳跃式探测，比较灵活。

●伪随机探测再散列

di=伪随机数序列。

②链地址法：将所有散列地址为 i 的元素构成一个称为同义词链的单链表，并将单链表的

头指针存在散列表的第 i 个单元中，因而查找、插入和删除主要在同义词链中进行。 链地

址法适用于经常进行插入和删除的情况。

平均查找长度与a（装填因子）和处理冲突的方法有关，与问题的规模无关。

9.排序：

排序的基本操作使比较数据和移动数据。

9.1： 内部排序与外部排序：

只使用内存的排序称之为内部排序，需要借助计算机外存的排序称为外部排序，外部排序的主要影响因素是内外存之间的交换次数。

9.2：插入排序：

将第一个元素看作是有序。第一趟使前两个元素有序，第二趟使前三个元素有序．．．．直到第n-１趟，使整体有序。

是稳定排序。（排序中存在相同关键字时，其相对位置保持不变）ｏ（ｎ２）.

9.３：折半插入排序：

在插入排序的基础上，使用折半搜索的思想进行插入。

9.４：希尔排序：

先将序列分为子序列，然后将子序列分别进行插入排序。

9.５：冒泡排序：

在有序时比较过一次之后直接结束，比较快。

9.６：快速排序：

找一个记录作为轴，小于的放在轴前，大于的放在轴后，然后对形成的子序列分别递归使用快速排序。

左右指针移动。

数据有序时会发生退化o(n2),平均分成两部分时效率最高。

9.７：选择排序：

9.８：堆排序：

建立堆，取走堆顶元素，重新建立堆，不断循环。

找出10000个元素中最大的十个元素最快的方法就是使用堆排序。

9.9: 归并排序：

消耗辅助空间最多的排序。稳定。

将两个以上的有序序列合并成一个有序序列。

o（nlogn）

合并时最多需要移动m+n-1（两个序列的个数）次