数据结构

概念

  • 数据(Data)

    相当于记录的表，所有能输进电脑处理的都叫数据

  • 数据对象(Data object)

    是性质相同的数据元素的集合 是数据中的集合

  • 数据元素/记录/结点/顶点(Data Element)

    相当于个人的数据打包（表的元素）是数据中的个体（基本单位）

  • 数据项（Data Item)

    相当于个人的数据（数据元素的元素）（最小单元）

数据间的关系：

  • 线性排序Linear orderingsx < y , x = y, or  y < x

是一种对称关系。所有数据都能用这种关系存储。可以使用数组或链表来存储线性有序的集合。

需要操作能够知道谁是头、尾、任意给定排序的、元素某段给定范围的数据、给定元素位置后知道其前后元素

我们需要能排序元素

  • 层级排序hierarchical ordering x ≺ y

适用有从属、包含关系（先决条件）的数据。我们需要知道两个数据之间的关系（是否直接从属、是否在同深度、最近的共同根节点是哪个

  • 偏序Partial orderings x ≺ y

即不一定有共同的先决条件（不一定同根），两个元素之间的关系不唯一。我们需要知道哪个元素能最先接近某元素

  • 等价关系Equivalence relations x ~ y

两元素关系对称、传递、自反。

  • 弱序Weak orderings x ≲ y

可能有多个最小或最大元素
下一个或上一个元素可能是等效的

  • 邻接关系Adjacency relations x↔y

ADT=（D，R，O）

(Data数据对象,Relationship关系,Operations操作)

算法特性：

有穷性（有穷步骤，有穷时间）、确定性、可行性、具有0/多个输入和1/多个输出

finiteness, definiteness, effectiveness, input, output

算法设计评价要求：

正确性、可读性、健壮性（鲁棒性）、高效性

correctness, readability, robustness, efficiency(time and space)

数量级只需找最高次贡献最大的语句（只考虑基本操作）

时间复杂度

时间复杂度

f(n) = Q(g(n)) ⇔ g(n) = Q(f(n))

f(n) = O(g(n)) ⇔ g(n) = W(f(n))

f(n) = o(g(n))  ⇔ g(n) = w(f(n))

基本语句：执行次数最多，对时间贡献最大的语句

数据结构图

复杂度计算公式

$f(n)=\theta(g(n))$ ↔ $g(n)=\theta(f(n))$

$f(n)=\theta(f(n))$

$f(n)=\theta (g(n)),g(n)=\theta (h(n))$ ↔ $f(n)=\theta (h(n))$

$T(n)=\sum T_i(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))$

$T(n)=T_1(n)×T_2(n)=O(f(n))×O(g(n))=O(f(n)×g(n))$

比较公式：

$O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)$

顺序存储与链式存储

Sequential Storage Linked Storage
Space capacity× √
density√ ×
Time Access/retrieve ：$O(1)$ $O(n)$
Insert/erase:$O(n)$ $O(1)$

Stack

LIFO 后进先出，只有一个开口。

top可以指向当前（空时为-1）也可以指向下一个要插入的（空时为0）

对于LinkedList头尾操作差异

Front Back
Find $\theta(1)$ $\theta(1)$
Insert $\theta(1)$ $\theta(1)$
erase $\theta(1)$ $\theta(n)$

所以如果想用list实现，那就拿头当top

Array capacity数组扩容的Amortized Analysis：

2倍。（由平均扩容时移动的空间复杂度决定。）

1
2
3
4
5
6
7
8
9
T* newlist=new T[capacity*=2]

for(i)

newlist[i]=list[i];

delete[] list

list=newlist;

worstcase：

（原来有n个数据） 均摊下来每次复制做了多少搬运 插入过程中扩容n次要多做的搬运次数
+1 n-1 0
+m n-m m-1
*2 1 n
*r $\frac1{r-1}$ (r-1)n

逆波兰式

（3+4）*5-6

从左到右，（左序）数字在前符号在后，遇到符号就算包括符号的三个，这代表一个计算。每次只取三个数算，算完替代原来的位置。即为：

34+5*6-=（3+4）*5-6

345*+6-=3+（4*5）+3-6

3456-+=4（5-6）+3

用栈stack：遇到数字push进，遇到符号pop原来的数字，算完之后push回结果。以此类推直到栈空。

STL

在 C++ STL（比如 std::stack 和 std::queue）中，pop() 的返回值类型是 void，它绝对不返回任何内容（先top再pop防止pop中报错导致数据丢失）

Queue队列

FIFO头进尾出

Front Back
Find $\theta(1)$ $\theta(1)$
Insert $\theta(1)$ $\theta(1)$
erase $\theta(1)$ $\theta(n)$

因此，我们喜欢将尾部做头，将头部做尾，pop只在头发生，push只在尾发生

Doublelinkedlist双向链表

insert时要先利用prior更改cur的next连上，再将next的prior连上cur，此时已经不怕改prior会丢失next了。

然后，将cur与prior连上，再把prior的next指向cur。

remove时同样，要先将prior的next连next，再将next的prior连上prior的next，最后delete cur

deque双端列表（头&尾指针）

deque都是双向列表。头尾均可插入。

对于单项列表（但有尾指针）：

Front Back
Find $\theta(1)$ $\theta(1)$
Insert $\theta(1)$ $\theta(1)$
erase $\theta(1)$ $\theta(n)$

Circularlinklist循环链表

有head，tail的next指向head（在有哨兵节点时）

Circulararray

维护两个指针，一个指向front（头），一个指向back（下一个要填的）。

if back==capacity

back=0

判断满：back+1=front（牺牲一个空格来作为判满条件，否则会空和满是同一个条件。）

扩容

法1：在front和back中间加容量，即新开个数组，然后分别对头和尾进行分别赋值。

priority queue优先队列

法2：将头-尾以此按顺序整理并赋值。

总之不能直接copy

heap堆

先pop优先级最高的，每次insert要找自己位置来插入

Binary heap二叉堆

首先要注意，二叉堆两棵子树之间没有任何关系，他只负责把最大/最小的push到顶端，和二叉排序树时间有本质区别。

二叉排序树是有关系的，可以用于查找的，中序遍历之后是按顺序排好的。而二叉堆只管把最值往上送，本身不进行任何的排序。中序遍历出来并非顺序数列。二叉堆必须是完全二叉树。

有maxheap和minheap。

heap需要维持完全二叉树。

当heappop后不完全了，我们将最后一个进入的元素（叶子）放到栈顶，然后继续执行pop。

注意，如果题目没有说第0号位空，则默认从0开始。这里，堆树以层序遍历存储在数组中。

push

每插入一次，就要进行一次与根节点往上的比对进行上浮，插入只能在堆尾（叶子）

pop

堆顶一定是最值，在pop堆顶后，需要先把叶子节点（堆尾）放到堆顶，然后做recurs，与直属父节点对比，将子树中最小的提上来。（由层决定，每一层的较小者往上走）（下沉）

比较

pos和pos/=2比较（父节点）

Head push pop
$\theta(1)$ $O(ln(n))$ $O(ln(n))$

Tree

若从1开始：

结点：i

左孩子：2i 右孩子：2i+1

若从0开始：

结点：i

左孩子：2i+1 右孩子：2i+2

heapification条件变为$\frac{n-1}2$向上遍历

节点数=度数+1

树高不小于⌈$log_2(n+1)$⌉

概念

Root根节点 Internal leaf node叶子节点

Parent双亲 children孩子 sibling兄弟

Path路 Path length路长 height由叶子起始到根 depth深度，由根起始到叶子

Ancestors祖先 descendants后代

ordered 和 unordered tree有序树与无序树，左右子树交换若一样就是无序，不一样就是有序。无序树左右子树交换被视为同一棵树。

subtree子树

概念应用XHTML和CSS

树类型

Complete tree完全二叉树

树的n-1层以上都是满的。绝对靠左，绝不留空

Balanced Binary Tree/AVL tree平衡二叉树

存储结构

顺序存储：将空节点补上为0.使用数组进行层序遍历存储

链式存储：每个点有左右指针，指向下一个节点。没有孩子即为NULL。此时非空指针数量n-1.空指针n+1

遍历

下面列举二叉树的遍历。度数更多则有先根后子树和先子树后根（子树依旧从左到右。先根后子树和转换为二叉树的先序一致，先子树后根和转换为二叉树的中序一致。

先序

根左右

最左边是根

1
2
3
4
5
6
7
void Preorder(Bitree t){
	if(t!=NULL){
		visit(t);
		Preorder(t->lchild);
		Preorder(t->rchild);
	}
}

中序

左根右

根在中间可以划分左右

1
2
3
4
5
6
7
void Inorder(Bitree t){
	if(t!=NULL){
		Inorder(t->lchild);
		visit(t);
		Inorder(t->rchild);
	}
}

后序

左右根

最后面是根

1
2
3
4
5
6
7
void Postorder(Bitree t){
	if(t!=NULL){
		Postorder(t->lchild);
		visit(t);
		Postorder(t->rchild);
	}
}

层次

根节点访问结束根节点出队，孩子入队。（队列）pop谁就push谁的孩子，从左到右pop。

1
2
3
4
5
6
7
8
9
10
11
void LevelOrder(BiTree t){
	InitQueue(q);
	BiTNode *p=T;
	Enqueue(q,p);
	while(!IsEmpty(q)){
		Dequeue(q,p);
		visit(p);
		if(p->lchild!=NULL)Enqueue(q,p->lchild);
		if(p->rchild!=NULL)Enqueue(q,p->rchild);
	}
}

树转二叉树

同一层兄弟变孩子，除了第一个孩子其他兄弟全部与双亲断开

转换完右子树为空

Binary Search Tree二叉排序树

左子树均大于根，右子树均小于根。

中序遍历二叉排序树，得到升序序列

插入

比较插入数据与根节点，比较到小于根则插入左子树，反之则插入右子树。插入时要在该子树为空情况下才可以。

新节点一定是叶子。

构造

按顺序插入子树，第一个为根。

删除

（1）若被删除的结点是叶子结点，则直接删除

（2）若结点只有一棵左子树或者右子树，则让该结点的子树成为其父结点的子树

（3）若结点有一棵左、右两棵子树，则令该结点的直接后继（直接前驱）代替该结点，然后从二叉排序树中删去这个直接后继〈直接前驱），这样就转换成了前两种情况

直接后继Inorder Successor：以现在为根节点的子树的右子树的最下面的左侧节点

直接前驱Inorder Predecessor：以现在为根节点的子树的左子树的最下面的右侧节点

Huffman tree哈夫曼树

节点被赋予一个代表意义的数值，即边带权。哈夫曼树即为带权路径长度最小的二叉树。

构造

构造哈夫曼树的步骤：

（1）将所有结点分别作为仅含一个结点的二叉树

（2）构造一个新结点，从中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和

（3）从中删除刚才选出的两棵树，同时将新得到的树加入森林中

（4）重复步骤（2）和（3），直至剩下一棵树为止

哈夫曼编码

在哈夫曼树的前提下对叶子进行编码,向左走即为0，向右走即为1.

从而，要求每一个字符(每一个节点）的哈夫曼编码，只需找从根到该叶子经过的路径编码即可。

带权路径长度

wpl=每个叶子节点的权*其路长。

AVL树（内存）

前提：二叉搜索，保持节点{左子树高-右子树高|≤1

插入

对失衡节点进行操作：

左旋，冲突左孩变右孩

右旋，冲突右孩变左孩

最后，失衡节点的失衡侧孩子作为根。

冲突发生在孩子的**子树上：

LL右旋，冲突右孩变左孩

LR左旋左孩子，再右旋

RR左旋，冲突左孩变右孩

RL右旋右孩子，再左旋

多个节点失衡：对最近的失衡节点进行调整

删除：

删除叶子，然后沿着祖先依次向上检查节点是否失衡，逐个调整

红黑树（内存）

插入

左根右，根叶黑，不红红，黑路同（叶子为空）

最长路径不超过最短路径两倍

插入节点默认红（之可鞥违反根叶黑/不红红）

破坏调整：

插入结点是根结点，直接变黑

插入结点的叔叔是红色，叔父爷变色，爷爷变插入节点。

插入结点的叔叔是黑色，判断是LLRRLRRL，先旋转再变色（旋转点和旋转中心变色）

B树（硬盘）

多叉平衡搜索树，平衡、有序、多路

最多有几个分支就是几叉树（该节点就有n-1个数据）

数据下面还有节点（外部节点，失败节点）

数据结构图

访问结点是在硬盘上进行的

结点内的查找是在内存中进行的

插入

数据结构图

删除

数据结构图

非叶子、直接前驱后继替代

支持随即查找，不支持顺序查找。

B+树（硬盘）

数据结构图

数据结构图

m个分支的结点有m个元素

每个元素对应子结点最大值

非叶节点拿不到数据

兼顾顺序查找和随机查找（两个根，一个在树一个在链表）

顺序：root

随机：head

范围查找：结合上面两种，先随机，找到头尾位置，再顺序遍历头到尾巴。

排序

runtime:三种情况，$\theta(n), \theta(nln(n)), O(n^2)$

情景best，worst，general/average，不同情景的runtime非常不一样。

稳定性

对于相同的两个元素，排序后相对位置不发生变化，则稳定。

Inversions

交换对，即序列中的所有元素两两组为一对（共有$\frac{n(n-1)}2$对）。

对于每一组交换对，小在前大在后即为顺序对（符合要排的顺序），否则为逆序对。

对于随机的（generalcase），我们认为有一半逆序对一半顺序对。（$\frac{n(n-1)}4$=$O(n^2)$)。即，一个随机的数组里，平均含有 $O(n^2)$ 个逆序对,假设最简单的方法一次只交换一个逆序对，则时间复杂度就是$O(n^2)$。这也说明排序的时间复杂度上限是$O(n^2)$。

只要排序靠比较来工作的（前四个门派全都是），那么时间复杂度下限绝对不可能低于$n \log n$。原因：决策树 。因为 $n$ 个元素有 $n!$ 种排列组合，二叉树的叶子节点必须有 $n!$ 个，树的高度算下来就是 $n \log n$。

要想达到 $O(n)$，只能用不比较的分配类排序, 如基数排序和桶排序。

Sorting techniques（排序门派）：

  • 插入 (insertion)：直接插入、希尔排序。
  • 交换 (exchanging)：冒泡、快速排序。
  • 选择 (selection)：简单选择、堆排序。
  • 归并 (merging)：归并排序。
  • 分配 (distribution)：基数排序、桶排序（这种是不比大小的）

传统O(n)排序法

Selection Sort选择排序，Insertion Sort插入排序，Bubble sort冒泡排序。

selection sort

基本思想：第i趟排序即从i-n中选择关键字最小的元素与i交换

（找到最小后交换）

1
2
3
4
5
6
7
8
9
10
11
12
void SelectionSort(T a[],int n)
{
	for(i=0;i<n-1;i++)
	{
		min=i;
		for(j=i+i;j<n;j++)
		{
			if(a[j]<a[min])min=j;
		}
		if(min!=i)swap(a[i],a[min]);
	}
}

空间复杂度：$O(1)$

时间复杂度：

稳定性：不稳定

bubble sort

基本思想是：从后往前（或者从前往后）两两比较相邻元素的值，若为逆序，则进行交换，直到序列比较完，一趟冒泡结束，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置）

(只跟邻居比）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void BubbleSort(T a[],int n)
{
	for(i=0;i<n-1;i++}
	{
		flag=false;
		for(j=n-1;j>i;j--)
		{
			if(a[j-1]>a[j])
			{
				swap(a[j-1],a[j]);
				flag=true;
			}
		}
		if(flag==false)return;
	}
}

空间效率：$O(1)$

时间效率：$O(n^2)$

稳定性：稳定

insertion sort

将每一个待排序记录按照关键字大小插入前面的子序列中。（空间不变，指针按顺序遍历，逆序就switch，顺序不管。指针指到哪，哪里前面就是已经排好的序列。

（扑克牌法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void InsertSort(T A[],int n)
{
	int i,j;
	for(i=2;i<n;i++)
	{
		if(A[i]<A[i-1])
		{
			A[0]=A[i];
			for(j=i-1;A[0]<A[j-1];--j)
			{
				A[j+1]=A[i];
			}
			A[j+1]=A[0];
		}
	}
}

空间效率：$O(n)$

时间效率：$O(n^2)$

稳定性：稳定

快速$\theta(nln(n))$排序法

heap sort堆排序，quick sort快排，merge sort归并排序。

heap sort

双亲都比孩子小/大。

sort

排序按照pop和push方法排序

每次排好序i往后和最末尾的叶子交换，然后下次排序的末尾位数减一，出来就是逆序的序列。（或者按照相反的方法排序，那出来就是顺序了

或将pop出的数据依次存进新列里即排好序

heapification

先直接看作一个完全二叉树。然后再调整。

从⌊n/2⌋一直往前构建根堆（跟孩子比，把最值放在根节点）

时间复杂度：O(n)

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
26
27
28
29
30
31
32
33
void percDown(std::vector<int>& arr, int index, int heapSize) {
    int temp = arr[index];
    int child;

    for (; index * 2 + 1 < heapSize; index = child) {
        child = index * 2 + 1;   
        if (child != heapSize - 1 && arr[child + 1] > arr[child]) {
            child++; 
        }
  
        if (arr[child] > temp) {
            arr[index] = arr[child];
        } else {
            break;
    }
    arr[index] = temp;
}

void heapSort(std::vector<int>& arr) {
    int n = arr.size();
    // Heapification 
    for (int i = n / 2 - 1; i >= 0; i--) {
        percDown(arr, i, n);
    }

    // Sort
    // 这一步的时间复杂度是 O(N log N)
    for (int i = n - 1; i > 0; i--) {
        std::swap(arr[0], arr[i]); 
  
        percDown(arr, 0, i); 
    }
}

Quick sort

基本思想是：在待排序表中任取一个元素pivot作为枢轴（通常取首元素），通过一趟快速排序将待排序表划分为独立的两部分（枢轴前和后），pivot放在了最终位置K中。

两个指针，一个从头开始，一个从尾开始。将指针所指与pivot比较，若小于pivot则放到前方指针的位置，大于枢轴则放到后方指针的位置。（指针指的位置必有一个为空。）每次交换就换指针，并让新指针指向其下一个进行比较，等到两个指针重叠就完成了一个枢轴的排序（共同所指位置即为枢轴位置）。

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
26
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[low]; 
    while (low < high) {
        while (low < high && arr[high] >= pivot) {
            high--; 
        }
        arr[low] = arr[high]; 
        while (low < high && arr[low] <= pivot) {
            low++;
        }
        arr[high] = arr[low]; 
    }
  
    arr[low] = pivot; 
  
    return low; 
}

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivotPos = partition(arr, low, high);
  
        quickSort(arr, low, pivotPos - 1);
        quickSort(arr, pivotPos + 1, high);
    }
}

空间效率：$O(ln(n))$

时间效率：$O(nln(n))$

稳定性：不稳定

是所有内部排序中平均性能最优，但不适用于基本有序的序列进行排序

merge sort

核心思想：Merge Two List将两个有序表合成一个新的有序表。

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
26
27
28
int* mergeTwoArrays(int* array1, int n1, int* array2, int n2) {
{  
    int* result = new int[n1 + n2];
				while(i1<n1&&i2<n2)
				{
					if(array1[i1]<=array2[i2]){
						arrayout[k] =array1[i1];
						++i1;
					}
					else{
						arrayout[k]  =array2[i2];
						++i2;
					}
					++k;
				}
				while (i1 < n1) {
		        arrayout[k] = array1[i1];
		        ++i1;
		        ++k;
		    }
		    while (i2 < n2) {
		        arrayout[k] = array2[i2];
		        ++i2;
		        ++k;
		    }
    return result;
}
记住还要释放原来的内存

空间复杂度：O(n)

时间复杂度：$O(nln(n))$

稳定性：稳定

时间线性增长$O(n)$排序法

Bucket sort桶排序，Radix sort基数排序

Radix Sort

基于关键字各个位的大小进行排序（每个位数维护一个指针数组，数组下标即为该位数字）

从低位到高位进行排序，每排一次进行一次收集制作为链表，然后再根据高一位对已排好序的链表进行按顺序排序（！要基于前面的顺序，不能拆散重排

空间复杂度：O(r) (基数个数，数字的话就是十个位）

时间复杂度：$O(d(n+r))$(d收集趟数，与位数有关)

稳定性：稳定

bucket sort

设置n个堆（顺序堆，0到m，m到m+n）将数据丢到n个bucket里面，在堆里面排好序再按顺序拿出来。分发（distribute）不靠比较，而靠数学映射（如n/10=1）进行。

桶排序(Bucketsort）是一种非比较型的排序算法，其核心思想基于分治策略。它把待排序的元素分配到一系列预先设定好的桶中，每个桶可以被视为一个小的子集合，并且这些桶是按照一定顺序排列的。之后，对每个桶内的元素分别进行排序，最后将各个桶中的元素按顺序依次取出并合并，从而得到一个完整的有序序列。

稳定性由桶内的排序算法决定。适用于均匀分布。

数据结构图

排序算法 (Algorithm) 最好时间复杂度 (Best Case) 平均时间复杂度 (Average Case) 最坏时间复杂度 (Worst Case) 空间复杂度 (Space Complexity) 稳定性 (Stability)
直接插入排序 (Insertion) $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
希尔排序 (Shell) $O(n)$ $O(n^{1.3})$ ~ $O(n^{1.5})$ $O(n^2)$ $O(1)$ 不稳定
冒泡排序 (Bubble) $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
快速排序 (Quick) $O(n \log n)$ $O(n \log n)$ $O(n^2)$ 平均$O(\log n)$，最坏 $O(n)$ 不稳定
简单选择排序 (Selection) $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定
堆排序 (Heap) $O(n)$(所有进来的都是一样的） $O(n \log n)$ $O(n \log n)$ $O(1)$完全内部排序 不稳定
归并排序 (Merge) $O(n \log n)$ $O(n \log n)$ $O(n \log n)$ $O(n)$ 稳定
桶排序 (Bucket) $O(n+m)$ $O(n+m)$ $O(n^2)$ $O(n+m)$ 稳定
基数排序 (Radix) $\Theta(n \ln(m))$ $\Theta(n \ln(m))$ $\Theta(n \ln(m))$ $O(n)$ 稳定

只有当 $n$ 远大于 $m$ 时，用基数排序代替快排才有意义

Graph

概念

有向图<v,w>:v→w,<w,v>:w→v

无向图(v,w)=(w,v)

简单图：不存在重复边，不存在顶点到自身的边

多重图：与简单图概念相反

完全图：（简单完全图）

对于无向图，任意两个顶点之间都存在边。边数：$\frac{n(n-1)}2$

对于有向图，任意两个顶点之间都存在方向相反的两条弧，边数：$n(n-1)$

子图：路径和顶点都在原图集合之中

生成子图：顶点集合=原图集合，路径属于原图集合子集

连通：两个顶点之间有路径可以链接，即a到b有路径则称为a到b连通。无向图a连通b相当于b连通a，而有向图有单向联通。

强连通 (Strongly Connected)：一个有向图里，任意两个顶点都能互相到达，就叫强连通图。它的极大强连通子图叫“强连通分量”。

弱连通 (Weakly Connected)：如果把它降级当成无向图看，发现连通，就叫弱连通。

连通图：图中任意两个顶点都是连通的

极小连通子图：既要保持图连通又要使得边数最少的子图（顶点集合为原图子集）

生成树：包含图中全部顶点的一个极小连通子图（边数=顶点数-1）

顶点的度、入度与出度：

无向图的全部顶点的度的和等于边数的两倍

对于有向图，入度是以顶点v为终点的有向边的数目，出度是以顶点v为起点的有向边的数目，顶点的度等于入度和出度之和。有向图的全部顶点的入度之和与出度之和相等，并且等于边数。

边的权和网：带权图即为网

路径．路径长度和回路/环

存储方式

邻接矩阵

一个n*n的矩阵。

数据结构图

对无向图，一定是对称矩阵。有向图则不是。

对于带权图：

数据结构图

邻接表

数据结构图

顶点后面接自己能直接access到的。

数据结构图

空间复杂度：

有向图$O(|V|+2|E|)$顶点数+2倍边数

无向图$O(|V|+|E|)$顶点数+边数

邻接表不唯一

还有十字链表和邻接多重表

遍历

广度优先：类似层序遍历，访问过的不再访问。序列不唯一。

深度优先：类似于树的先序遍历。访问过的不在访问，此时退回上一个顶点进行继续遍历。序列不唯一。

可用栈/队列实现。

如果从一个无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是连通图

最小生成树

带权连通无向图中，所有生成树中权值之和最小的生成树

Prim加边

  1. 任取一顶点，去掉所有边
  2. 选择一个与当前顶点集合距离最近的顶点，并将该顶点和相应的边加入进来，同时不能形成回路
  3. 重复2.，直至图中所有顶点都并入

Kruskal加点

  1. 去掉所有边
  2. 选边（权最小，且不构成回路）
  3. 重复2.，直至图中所有顶点都并入

最短路径

Dijkstra

画表，每次求得到某点的最小路径，就将其中的min值加入集合，并不再算后续。下一次以加入合集的顶点为起始，寻找其有无更短新路径。若后续有更小的，就将其与现有最小值替换。否则按照原路径，直到所有点都加入集合。

数据结构图

拓扑排序

AOV网

拓扑排序的算法的步骤：

  1. 从AOV网中选择一个没有前驱的顶点并输出
  2. 从网中删除该顶点和所有以它为起点的有向边
  3. 重复1和2直到当前的AOV网为空或当前网中不存在无前驱的顶点为止

关键路径

AOE网

AOE网：以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销

关键路径：从开始顶点(源点)到结束顶点(汇点)的所有路径中，具有最大路径长度的路径

关键活动：关键路径上的活动

事件vk的最早发生时间ve(k)：指从源点的到顶点的最长路径长度

数据结构图

事件vk的最迟发生时间vl(j)：指在不推迟整个工程完成的前提下，即保证它的后续事件vj在其最迟发生时间vl(j）能够发生时，该事件最迟必须发生的时间

数据结构图

从后往前

数据结构图

数据结构图

数据结构图

Forest森林

无环图

  • 边的数量始终小于顶点的数量：∣E∣<∣V∣。
  • 森林中包含的树的数量等于：∣V∣−∣E∣。
  • 移除森林中的任何一条边，都会在森林中额外增加一棵树。

森林变树

利用“左孩子/右兄弟”（left-child/right-sibling）表示法，将森林中所有独立树的根节点相互视为“兄弟”（siblings）并用右指针链接起来，从而合并成一棵二叉树

森林也一样，树从左到右遍历，先根后子树和先子树后根（子树依旧从左到右。先根后子树和转换为二叉树的先序一致，先子树后根和转换为二叉树的中序一致。

Search查找

（1）查找：在数据集合中，寻找满足某种条件的数据元素的过程

（2）查找表（查找结构）：用于查找的数据集合

（3）关键字：主关键字：数据元素中某个数据项的值，用它可以标识一个数据元素关键字可以唯一地标识一个记录

（4）平均查找长度：所有查找过程中进行关键字的比较次数的平均值$ASL=\sum PiCi$

顺序查找

从线性表的一端开始，逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足条件，则查找成功，返回该元素在线性表中的位置。若查查找到表的另一端，仍未找到符合给定条件的元素，则返回查找失败的信息

0位置腾出来=key作为哨兵，避免越界

数据结构图

折半查找（二分法）

折半查找〈二分查找），仅适用于有序的顺序表

三个指针，low，high，mid。

用mid来比，大小决定lowhigh的变化。

直到low<=high的条件不满足，查找结束。

数据结构图

数据结构图

Harshing哈希表

数据结构图

同义词synonyms

数据结构图

数据结构图

数据结构图

数据结构图

数据结构图

并查集

并查集（Union/Find 算法）的本质和底层数据结构就是森林。

数据结构图

数据结构图

合并：若要合并的两个元素的根不一样，就让一个根指向另一个根。否则不用管。

Find

数据结构图

数据结构图

数据结构图

数据结构图

将查找路径上的元素直接指向根下次查询时就是O(n)的复杂度

路径压缩可能会改变树的高度,此时h数组记录的是估计的高度

Union

按秩合并 时间：常数级别（阿克曼函数）O(n)

高度合并

数据结构图

路径压缩可能会改变树的高度,此时h数组记录的是估计的高度

大小合并

路径压缩不会改变树的结点个数

结点数少的树有可能高于结点数多的树

数据结构图

改进

数据结构图

数据结构图