《大话数据结构》总结

计算机主修课程 / 数据结构
Word count: 5k   |   Reading time≈ 20 min

《大话数据结构》

线性表

对于第 i 个数据元素 ai 的存储位置： LOC(ai)=LOC(a1)+(i-1)*c //c 是每个数据元素占据的存储单元

如上公式所示，存取时间性能为 O(1),通常这一存储结构叫做随机存取结构

线性表的顺序存储结构：

存、读数据时，O(1);

插入、删除数据时，O(n)；

线性表的链式存储：

结点包括数据域(信息和数据,头结点可以为空)和指针域(指向下一个)

单链表的读取、插入删除：都是 O(n)

用数组描述的链表叫静态链表，或者叫游标实现法。即数组的元素都是由两个数据域组成，其中一个就相当于指针。

头插法和尾插法

头指针为 L，插入的是 p，则：

1
2
p->next=(*L)->next
(*L)->next=p;

栈和队列

栈

某出栈元素前面比它小的元素，一定是非入栈顺序，比如 123 入栈，出栈顺序就不能是 312；12345 入栈，出栈顺序不能是 34512；因为 5 大于 1、2，而 12 是入栈顺序，不可以。（此处感谢堃哥）

两栈共享空间

通常用于两个栈的空间需求有相反关系的时候，也就是一个栈增长一个栈减少。

使用：一个栈的栈地为数组的 0 处，另一个栈为数组的 n-1 处。这样两个栈如果增加元素，就是两端点向中间延伸。当 top1+1==top2 的时候，栈满。

逆波兰式：

9➕（3➖1）✖️3➕10➗2

逆波兰式：9 3 1 - 3 x + 10 2/ +

遇到优先级高的再写符号，比如 3-1 最先，要写 9 3 1➖，然后是和 3✖️，此时再和 9 相加，➗ 的优先级高于 ➕，最后再加一起。

队列

循环队列

判断队满：

  1. 设置标志变量 flag，当 front==rear && flag==0 时，队为空；front==rear &&flag==1 的时候，队为满。
  2. 队列空的时候，front==rear；但当队列满的时候，我们将修改其条件，保留一个元素空间（也就是说，队列满的时候，数组中还有一个空闲单元）。设队列的最大尺寸为 QueueSize，则：
1
2
(rear+1)% QueueSize == front      //队满
(rear-front+QueueSize)% QueueSize  //通用的队列长度计算公式

链队列和循环队列基本操作都是 O(1)的。循环队列事先申请好空间，使用期间不释放，链队列每次申请和释放有一定的时间开销。但是循环队列的长度固定，所以链队列更灵活。

串

KMP 模式匹配算法

当模式与主串之间存在许多“部分匹配”的情况下才能体现出它的优势，否则两者差异并不明显

主串 S=“abcdefgab”，要匹配的 T=“abcdex”，因为 T 的 a 和后面 bcdex 都不相等，也就是 a 不与自己后面子串中任何一个字符相等，那么第一次 T 与 S 匹配中 T 的 abcde 和 S 的 abcde，那么 T 的首字符 a 就不可能与 S 中的 bcde 相等了。不需要做此匹配判断。

KMP 算法改进

树：

表示法

双亲表示法，孩子表示法，孩子兄弟表示法

特殊的树

斜树，满二叉树，完全二叉树

二叉树性质：

  1. 在二叉树的第 i 层最多有 2^(i-1)个结点
  2. 深度为 k 的二叉树最多有 2^k-1 个结点
  3. 二叉树中，叶子结点为 n0，度为 2 的点为 n2，那么 n0=n2+1
  4. 具有 n 个结点的完全二叉树的深度为[log2n]+1([x]表示不大于 x 的最大整数）

遍历二叉树

前序中序后序

已知前序和后序是不能确定一棵二叉树的

线索二叉树

指向前驱和后继

树和森林转换

右子树为原来的兄弟 左子树为原来的孩子

赫夫曼树

树的路径长度就是从树的根结点到每一个结点的路径长度之和

带权路径长度 WPL 最小的是赫夫曼树

图

有权值的图叫网

图的存储

邻接矩阵

邻接表

十字链表（难）

对于有向图来说，可以将邻接表和逆邻接表结合起来，方便找到以 Vi 为头和尾的弧，因而可以快速求得顶点的入度和出度。（很好用）

顶点表结点结构：

data firstin firstout

firstin 表示入边表头指针，指向该顶点的入边表的第一个结点。firstout 表示“出”。

边表结点结构：

tailvex headvex headlink tailink

tailvex 表示弧起点在顶点表的下标，headvex 表示弧终点在顶点表中的下标，headlink 指入边表指针域，指向终点相同的下一条边，tailink 指边表指针域，指向起点相同的下一条边。如果是网，还可以加一个 weight 域表示权重。

邻接多重表（难）

ivex ilink jvex jlink

ivex 和 jvex 是与某条边依附的两个顶点在顶点表中的下标。ilink 指向依附顶点 ivex 的下一条边，jlink 指向依附顶点 jvex 的下一条边。这就是邻接多重表结构

ilink 指向的结点的 jvex 一定要和它本身的 ivex 的值相同

边集数组

应用：克鲁斯卡尔算法。适合对边进行操作，而不是对顶点。

图的遍历

深度优先

广度优先

最小生成树

普里姆（Prim）算法

以某个顶点为起点，遍历所有相邻边，选最小权值的边的下一个顶点，加入目前的数组，并将现有的所有点视为整体。算法的时间复杂度是 O(n^2)

克鲁斯卡尔（Kruskal）算法

首先令最小生成树的初始状态为只有 n 个顶点而无边的非连通图 T，每个点自成一个连通分量，直接找最小权值的边，若该边依附的顶点落在 T 中不同的连通分量上，将其加入到 T 中，否则舍去。直到 T 中所有点都在一个连通分量上。时间复杂度是 O(eloge)

最短路径

迪杰斯特拉（Dijkstra）算法

B 站讲 Dijsktra

首先用一个数组保存最短路径长度（一开始是无穷大，为 65535），点集 S 只有 v0 点，然后遍历所有和 v0 相连点，选最短的 v1 加入 S 集，更新数组中 0 到剩余顶点的长度；再把 v2、v3……加入 S 集，更新相应的数组数据即可。

弗洛伊德（Floyd）算法

适合求所有顶点到所有顶点的最短路径。

时间复杂度为 O(n^3)

对于对应顶点的最小路径的前驱矩阵，如果不可达，则为 0

YouTube 大佬的讲解（很明白）

拓扑排序

图中没有回路叫无环。

用顶点表示活动的网，叫 AOV 网（Activity On Vertex Network），AOV 网无环。

拓扑排序：选一个入度为 0 的点，输出并删去，然后输出并删除之后的顶点，直到输出全部顶点或者 AOV 网中不存在入度为 0 的点。

关键路径

AOE 网（Activity On Edge Network）

路径上各个活动所持续的时间之和叫做路径长度，从源点到汇点具有最大长度的路径叫做关键路径，在关键路径上的活动叫关键活动

查找

顺序表查找

有序表查找

折半查找（二分查找）

利用二叉树

插值查找

折半中的

1
mid=（low+high）/2

而插值查找中

1
mid=low+（high-low）*（key-a[low]）/（a[high]-a[low]）    //key就是要查的关键字

斐波那契查找

1
mid=low+F[k-1]-1   //F为斐波那契数组

折半用的是加法和除法，插值用的是四则，斐波那契用的是加减法，会略微影响效率。

斐波那契查找也是查找关键字在待查数组的位置，要优于二分查找。以上三种查找方式只是在分割点上选择不同，各有优劣。

线性索引查找

稠密索引

分块索引

倒排索引

二叉排序树（重点）

又称二叉查找树，左子树不空则其所有结点均小于根结点的值；右子树不空，则其所有结点均大于根结点。

平衡二叉树（AVL 树）（重点）

左子树的深度减去右子树的深度的值称为平衡因子 BF，AVL 树的 BF 只能为-1、0、1

构造 AVL 树时，如果根结点和子结点的 BF 符号不统一，要先转到统一再左右旋。

查找的时间复杂度是 O(logn),插入和删除也是 O(logn)

红黑树

红黑树与 AVL 树同属于二叉排序树，各有优劣

多路查找树

其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。

2-3 树（3 阶 B 树）

每一个结点都有 2 个孩子（2 结点）或者 3 个孩子（3 结点）

一个 2 结点包含 1 个元素（父亲）和 2 个孩子（或者没有孩子），整体称为一个结点。不会只有一个孩子

一个 3 结点包含 2 个元素（父亲）和 3 个孩子（或者没有孩子）

2-3 树的插入与删除

2-3-4 树（4 阶 B 树）

一个 4 结点包含 3 个元素（父亲）和 4 个孩子（或者没有孩子）

B 树

B 树是一种平衡的多路查找树，2-3 树和 2-3-4 树都是 B 树的特例。结点最大的孩子数目叫做 B 树的阶。

要处理的硬盘数据量很大时，无法一次全部装入内存；就会对 B 树调整，使得 B 树的阶数与硬盘存储的页面大小相匹配。

eg，一个结点包含 1000 个关键字，高度为 2，可以储存 10 亿个关键字，只要让根结点永久在内存中，那么在这棵树上，寻找某个关键字就只需要读 2 次硬盘。

由于 B 树每结点可以具有比二叉树多得多的元素，所以可以减少必须访问的结点和数据块的数量。

B 树的数据结构就是为了内外存的数据交互准备的。

B+树

将 B 树的父亲结点放在相应的叶子节点处，并将所有叶子结点连接在一起

散列表查找（哈希表）

记录存储位置和关键字之间的确定的对应关系。

散列表构造

直接定址

平方取中

折叠法

除留余数法

随机数

处理散列冲突

开放定址

冲突了就找下一个空的散列地址

二次探测法

增加平方运算，不让关键字都聚集在一块区域

随机探测法

设置相同的随机种子，则不断调用随机函数可以省车给你不会重复的数列

随机种子：一般计算机的随机数都是伪随机数，以一个真随机数（种子）作为初始条件，然后用一定的算法不停迭代产生随机数。

再散列函数法

用以上方法再散列

链地址法

散列表中只存储同义词子表的头指针，有冲突只是在当前位置给单链表加结点而已

公共溢出区

凡是冲突的都存储到溢出表中

排序

冒泡排序

1
2
3
4
5
6
7
8
9
10
void BubbleSort(SqList *L){
	int i,j;
	for(i=0;i<L->length;i++){
		for(j=L->length-1;j>=i;j--){
			if(L->r[j]>L->r[j+1]){
				swap(L,j,j+1)
			}
		}
	}
}

优化（如果已经有序，则不需要后续的循环）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 对顺序表L作改进冒泡算法 */
void BubbleSort2(SqList *L)
{
	int i,j;
	Status flag=TRUE;	/* flag用来作为标记 */
	for(i=1;i<L->length && flag;i++) /* 若flag为true说明有过数据交换，否则停止循环 */
	{
		flag=FALSE;				/* 初始为False */
		for(j=L->length-1;j>=i;j--)
		{
			if(L->r[j]>L->r[j+1])
			{
				 swap(L,j,j+1);	/* 交换L->r[j]与L->r[j+1]的值 */
				 flag=TRUE;		/* 如果有数据交换，则flag为true */
			}
		}
	}
}

简单选择

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void SelectSort(SqList *L)
{
	int i,j,min;
	for(i=1;i<L->length;i++)
	{
		min = i;						/* 将当前下标定义为最小值下标 */
		for (j = i+1;j<=L->length;j++)/* 循环之后的数据 */
        {
			if (L->r[min]>L->r[j])	/* 如果有小于当前最小值的关键字 */
                min = j;				/* 将此关键字的下标赋值给min */
        }
		if(i!=min)						/* 若min不等于i，说明找到最小值，交换 */
			swap(L,i,min);				/* 交换L->r[i]与L->r[min]的值 */
	}
}

直接插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void InsertSort(SqList *L)
{
	int i,j;
	for(i=2;i<=L->length;i++)
	{
		if (L->r[i]<L->r[i-1]) /* 需将L->r[i]插入有序子表 */
		{
			L->r[0]=L->r[i]; /* 设置哨兵 */
			for(j=i-1;L->r[j]>L->r[0];j--)
				L->r[j+1]=L->r[j]; /* 记录后移 */
			L->r[j+1]=L->r[0]; /* 插入到正确位置 */
		}
	}
}

希尔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void ShellSort(SqList *L)
{
	int i,j,k=0;
	int increment=L->length;
	do
	{
		increment=increment/3+1;/* 增量序列 */
		for(i=increment+1;i<=L->length;i++)
		{
			if (L->r[i]<L->r[i-increment])/*  需将L->r[i]插入有序增量子表 */
			{
				L->r[0]=L->r[i]; /*  暂存在L->r[0] */
				for(j=i-increment;j>0 && L->r[0]<L->r[j];j-=increment)
					L->r[j+increment]=L->r[j]; /*  记录后移，查找插入位置 */
				L->r[j+increment]=L->r[0]; /*  插入 */
			}
		}
		printf("	第%d趟排序结果: ",++k);
		print(*L);
	}
	while(increment>1);

}

堆

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
/* 已知L->r[s..m]中记录的关键字除L->r[s]之外均满足堆的定义， */
/* 本函数调整L->r[s]的关键字,使L->r[s..m]成为一个大顶堆 */
void HeapAdjust(SqList *L,int s,int m)
{
	int temp,j;
	temp=L->r[s];
	for(j=2*s;j<=m;j*=2) /* 沿关键字较大的孩子结点向下筛选 */
	{
		if(j<m && L->r[j]<L->r[j+1])
			++j; /* j为关键字中较大的记录的下标 */
		if(temp>=L->r[j])
			break; /* rc应插入在位置s上 */
		L->r[s]=L->r[j];
		s=j;
	}
	L->r[s]=temp; /* 插入 */
}

/*  对顺序表L进行堆排序 */
void HeapSort(SqList *L)
{
	int i;
	for(i=L->length/2;i>0;i--) /*  把L中的r构建成一个大根堆 */
		 HeapAdjust(L,i,L->length);

	for(i=L->length;i>1;i--)
	{
		 swap(L,1,i); /* 将堆顶记录和当前未经排序子序列的最后一个记录交换 */
		 HeapAdjust(L,1,i-1); /*  将L->r[1..i-1]重新调整为大根堆 */
	}
}

归并

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

/* 归并排序********************************** */

/* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */
void Merge(int SR[],int TR[],int i,int m,int n)
{
	int j,k,l;
	for(j=m+1,k=i;i<=m && j<=n;k++)	/* 将SR中记录由小到大地并入TR */
	{
		if (SR[i]<SR[j])
			TR[k]=SR[i++];
		else
			TR[k]=SR[j++];
	}
	if(i<=m)
	{
		for(l=0;l<=m-i;l++)
			TR[k+l]=SR[i+l];		/* 将剩余的SR[i..m]复制到TR */
	}
	if(j<=n)
	{
		for(l=0;l<=n-j;l++)
			TR[k+l]=SR[j+l];		/* 将剩余的SR[j..n]复制到TR */
	}
}


/* 递归法 */
/* 将SR[s..t]归并排序为TR1[s..t] */
void MSort(int SR[],int TR1[],int s, int t)
{
	int m;
	int TR2[MAXSIZE+1];
	if(s==t)
		TR1[s]=SR[s];
	else
	{
		m=(s+t)/2;				/* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */
		MSort(SR,TR2,s,m);		/* 递归地将SR[s..m]归并为有序的TR2[s..m] */
		MSort(SR,TR2,m+1,t);	/* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */
		Merge(TR2,TR1,s,m,t);	/* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */
	}
}

/* 对顺序表L作归并排序 */
void MergeSort(SqList *L)
{
 	MSort(L->r,L->r,1,L->length);
}

/* 非递归法 */
/* 将SR[]中相邻长度为s的子序列两两归并到TR[] */
void MergePass(int SR[],int TR[],int s,int n)
{
	int i=1;
	int j;
	while(i <= n-2*s+1)
	{/* 两两归并 */
		Merge(SR,TR,i,i+s-1,i+2*s-1);
		i=i+2*s;
	}
	if(i<n-s+1) /* 归并最后两个序列 */
		Merge(SR,TR,i,i+s-1,n);
	else /* 若最后只剩下单个子序列 */
		for(j =i;j <= n;j++)
			TR[j] = SR[j];
}

/* 对顺序表L作归并非递归排序 */
void MergeSort2(SqList *L)
{
	int* TR=(int*)malloc(L->length * sizeof(int));/* 申请额外空间 */
    int k=1;
	while(k<L->length)
	{
		MergePass(L->r,TR,k,L->length);
		k=2*k;/* 子序列长度加倍 */
		MergePass(TR,L->r,k,L->length);
		k=2*k;/* 子序列长度加倍 */
	}
}

非递归的迭代方法，避免了递归时深度为 log2n 的栈空间，只是申请到临时用的 TR 数组，空间复杂度为 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

/* 交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置 */
/* 此时在它之前(后)的记录均不大(小)于它。 */
int Partition(SqList *L,int low,int high)
{
	int pivotkey;

	pivotkey=L->r[low]; /* 用子表的第一个记录作枢轴记录 */
	while(low<high) /*  从表的两端交替地向中间扫描 */
	{
		 while(low<high&&L->r[high]>=pivotkey)
			high--;
		 swap(L,low,high);/* 将比枢轴记录小的记录交换到低端 */
		 while(low<high&&L->r[low]<=pivotkey)
			low++;
		 swap(L,low,high);/* 将比枢轴记录大的记录交换到高端 */
	}
	return low; /* 返回枢轴所在位置 */
}

/* 对顺序表L中的子序列L->r[low..high]作快速排序 */
void QSort(SqList *L,int low,int high)
{
	int pivot;
	if(low<high)
	{
			pivot=Partition(L,low,high); /*  将L->r[low..high]一分为二，算出枢轴值pivot */
			QSort(L,low,pivot-1);		/*  对低子表递归排序 */
			QSort(L,pivot+1,high);		/*  对高子表递归排序 */
	}
}

/* 对顺序表L作快速排序 */
void QuickSort(SqList *L)
{
	QSort(L,1,L->length);
}

/* **************************************** */

/* 改进后快速排序******************************** */

/* 快速排序优化算法 */
int Partition1(SqList *L,int low,int high)
{
	int pivotkey;

	int m = low + (high - low) / 2; /* 计算数组中间的元素的下标 */
	if (L->r[low]>L->r[high])
		swap(L,low,high);	/* 交换左端与右端数据，保证左端较小 */
	if (L->r[m]>L->r[high])
		swap(L,high,m);		/* 交换中间与右端数据，保证中间较小 */
	if (L->r[m]>L->r[low])
		swap(L,m,low);		/* 交换中间与左端数据，保证左端较小 */

	pivotkey=L->r[low]; /* 用子表的第一个记录作枢轴记录 */
	L->r[0]=pivotkey;  /* 将枢轴关键字备份到L->r[0] */
	while(low<high) /*  从表的两端交替地向中间扫描 */
	{
		 while(low<high&&L->r[high]>=pivotkey)
			high--;
		 L->r[low]=L->r[high];
		 while(low<high&&L->r[low]<=pivotkey)
			low++;
		 L->r[high]=L->r[low];
	}
	L->r[low]=L->r[0];
	return low; /* 返回枢轴所在位置 */
}

void QSort1(SqList *L,int low,int high)
{
	int pivot;
	if((high-low)>MAX_LENGTH_INSERT_SORT)
	{
		while(low<high)
		{
			pivot=Partition1(L,low,high); /*  将L->r[low..high]一分为二，算出枢轴值pivot */
			QSort1(L,low,pivot-1);		/*  对低子表递归排序 */
			/* QSort(L,pivot+1,high);		/*  对高子表递归排序 */
			low=pivot+1;	/* 尾递归 */
		}
	}
	else
		InsertSort(L);
}

/* 对顺序表L作快速排序 */
void QuickSort1(SqList *L)
{
	QSort1(L,1,L->length);
}
Donate
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2018-2020 Jee
  • Visitors: | Views:

如果您觉得此文章帮助到了您，请作者喝杯咖啡吧～

支付宝
微信