第五章
图的简介与二维数组
图就是由顶点和连接顶点的边组成的
表示图
我们利用二维数组表示图
二维数组的两个参数行列，均表示顶点，二者相交得到的即是距离
我们用正无穷(一般可以用999999代替)表示二者之间没有边，0是某点到自身的距离
比如e[a][b] = 3 ;就代表a到b的距离是3
图还分为有向图和无向图
顾名思义，有向图是有方向属性的，无向图则没有
换言之，对于无向图，我们有：
e[a][b] = e[b][a]
图的遍历
我们上一章学习了深度优先算法和广度优先算法
现在我们就利用它们来完成图的遍历
我们还是以一个例子来说吧
例题
假设我们在一个道路具有单向型的地方行走，我们想得到两点之间的路径和距离
1->5 10
1->2 2
2->5 7
2->3 3
3->1 3
3->4 4
4->5 5
5->3 3
现在，我们想要从1到达5的最短路径
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
| #include <stdio.h>
int min =9999999 ;
int book[101] ;
int e[101][101] ;
int n ;
void dfs(int cur,int dis){
int j ;
if(dis>min) return ;
if(cur == n)
{
if(dis<min) min = dfs ;
return ;
}
for(j=1;j<=n;j++)
{
if(e[cut][j] != 9999999 && book[j] = 0)
{
book[j] = 1 ;
dfs(j,dis+e[cur][j]) ;
book[j] = 0 ;
}
}
return ;
}
int main()
{
int i,j,m,a,b,c;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)
e[i][j] = 0;
else
e[i][j] = 9999999 ;
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&a,&b,&c);
e[a][b] = c ;
}
book[1] = 1 ;
dfs(1,0) ;
printf("%d",min) ;
getchar();getchar();
return 0 ;
}
|
第七章
由于第六章长度较长，先记下第七章
树的基本介绍
介绍
树其实就是不包含回路的连通无向图
因为这个特点，我们为树赋予了这些特性：
1.一棵树中的任意两个结点，有且仅有唯一的一条路径连通
2.一棵树如果有n个结点，那么它一定恰好有n-1条边
3.在一棵树中，加上一条边，那么就会得到一个回路
树是指任意两个结点间有且仅有一条路径的无向图
只要是没有回路的连通无向图，就是树
结点节点
我们把树中的每一个点叫做结点，当然也要叫节点的，无伤大雅
根又叫做根节点，即最开始的节点。一棵树有且仅有一个根节点
父亲结点简称父结点，儿子结点简称子结点
如果一个结点没有子结点，我们称它为叶结点
如果一个结点没有父结点，那它就是根结点
如果一个结点不是根结点也不是叶结点，那么它就是内部结点
深度：指从根到这个结点的层数，根结点所在的层数是第一层
二叉树与堆
二叉树是一种特殊的、常见的树
简介
二叉树的特点在于每个结点最多只有两个儿子
如果要使用更严格的递归定义，则是:
二叉树要么为空，要么由根结点、左子树、右子树组成
而左子树、右子树分别是一棵二叉树
二叉树是使用范围极广的树，一棵多叉树也可以转换为二叉树
二叉树类型
满二叉树：如果二叉树中每个内部结点都有两个儿子，这样的二叉树叫做满二叉树
完全二叉树：如果一棵二叉树除了最右边的位置上有一个或几个叶节点缺少外，其他都是丰满的，那么它就是完全二叉树
我们可以把满二叉树理解为一种特殊的，极其完美的完全二叉树
我们只需要用一个一维数组就能存储完全二叉树
我们将完全二叉树进行从上到下，从左到右的编号，可以得到下面这个结论：
如果已知子结点的编号是x,那么它父结点的编号就是x/2
堆
符合所有父结点都比子结点要小的树，就是最小堆
符合所有父结点都比子结点要大的树，就是最大堆
那么想要向堆中加入一个数据，需要怎么做呢？
比如说我们想要把23加入到一个最小堆中
1.我们把23放入堆顶，检查是否合适
2.如果不合适，我们就将这个数和它的两个儿子比较，并且选择较小者交换位置
3.继续向下交换，检查。重复1-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
26
27
28
29
30
31
32
33
34
35
36
37
38
| void siftdown(int i)
{
int t,flag = 0 ;
while( i*2 <= n && flag == 0 ){
if(h[i] > h[i*2])
t = i*2 ;
else
t = 1 ;
if(i*2+1 <= n)
{
if(h[t] > h[i*2 + 1])
t = i*2+1 ;
}
if(t!=i)
{
swap(t,i);
i = t ;
}
else{
falg = 1 ;
}
}
return ;
}
|
如果只是想新增一个值，而不要删除掉最小值，那么该怎么做呢？
直接将新元素插入到末尾，再根据情况判断元素是否需要上移，直到满足堆的特性为止
堆排序
与快速排序一样，，堆排序的时间复杂度是O(NlogN)
进行堆排序，需要我们建立对应的堆，每次删除顶部元素并将顶部元素输出或者放到一个数组中，直到堆空
最后输出的或者存放在新数组中的数，就是已经排序好的
下面以从小到大排序为例
代码实例_从小到大堆排序
1
2
3
4
5
6
7
8
9
10
11
|
int deletemin()
{
int t ;
t = h[1];
h[1] = h[n];
n--;
siftdown(1) ;
return t ;
}
|
完整的代码组成如下：
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
93
94
95
| #include <stdio.h>
int h[101];
int n ;
void swap(int x ,int y)
{
int t ;
t = h[x];
h[x] = h[y];
h[y] = t ;
return
}
void siftdown(int i)
{
int t,flag = 0 ;
while( i*2 <= n && flag == 0 ){
if(h[i] > h[i*2])
t = i*2 ;
else
t = 1 ;
if(i*2+1 <= n)
{
if(h[t] > h[i*2 + 1])
t = i*2+1 ;
}
if(t!=i)
{
swap(t,i);
i = t ;
}
else{
falg = 1 ;
}
}
return ;
}
void creat()
{
int i ;
for(i=n/2 ; i>=1;i--)
{
siftdown(i);
}
return ;
}
int deletmax()
{
int t ;
t = h[1];
h[1] = h[n];
b-- ;
siftdown(1);
return t ;
}
int main(){
int i , num ;
scanf("%d",&num);
for(i=1;i<num;i++)
scanf("%d",&h[i]);
n = num ;
creat();s
for(i=1;i<=num;i++)
printf("%d",deletemax());
getchar();getchar();
return 0 ;
}
|
小结
像这种，支持插入元素和寻找最值元素的数据结构被称为优先队列
堆就是一种优先队列的实现
并查集算法
并查集算法是一个利用结点关系，进行分类合组的算法
简介
并查集可以通过一个一维数组来实现
我们把每一个点视作一个”独立的，只有一个结点”的树
之后我们可以通过一些条件，逐渐将这些树合并成一棵大树
合并的过程，其实就是找统一的父节点的过程，我们可以自定两条原则：
1.相异的情况下，把右边的父节点改为左边的父节点。视作二者合并成了一组
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
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
| #include <stdio.h>
int f[1001] = {0} s,n,m,sum = 0 ;
void init()
{
int i ;
for(i=0;i<=n;i++)
f[i] = i ;
return ;
}
int getf(int v)
{
if(f[v] == v){
return ;
}
else
{
f[v] = getf(f[v]) ;
return f[v];
}
}
void merge(int v , int u)
{
int t1,t2 ;
t1 = getf(v);
t2 = getf(u);
if(t1!=t2){
f[t2] = t1 ;
}
return ;
}
int main()
{
int i,x,y;
scanf("%d %d",&n,&m);
init();
for(i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
merge(x,y);
}
for(i=1;i<=n;i++)
{
if(f[i] == i )
sum++;
}
printf("%d \n",sum);
getchar();getchar()
return 0 ;
}
|
并查集也被称为“不相交集”数据结构
