数据结构和算法

1. 概述

• 数据data结构(structure)是一门研究组织数据方式的学科，有了编程语言也就有了数据结构.学好数据结构可以编写更加有效率的代码
• 程序 = 数据结构 + 算法

1.1. 数据结构的分类

• 线性结构：特点是数据元素之间存在一对一的线性关系：常见的有：数组、队列、链表和栈.有两种不同的存储结构，即顺序存储结构(数组)和链式存储结构(链表)
  • 顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的
  • 链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息
• 非线性结构包括：二维数组，多维数组，广义表，树结构，图结构

数据结构和算法

什么是回溯法

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。二叉树：以为使用了递归，其实还隐藏着回溯 (opens new window)。
回溯是递归的副产品，只要有递归就会有回溯。回溯函数也就是递归函数，指的都是一个函数。

回溯法并不是什么高效的算法。因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

那么既然回溯法并不高效为什么还要用它呢？因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。

数据结构和算法

图

• 图是由顶点（vertex）和边（edge）组成的数据结构，用来表示多对多关系

图的种类

• 有向图：图中边是有方向，加权无向图，图中的边有权值
• 无向图：图中边没有方向，加权有向图，图中的边有权值

图的相关概念

• 顶点（vertex）：图中的每个节点

• 边（edge）：图中节点与节点之间的连线

• 度：与该顶点相连的边的数量，

• 权：边可以有权重，代表从源顶点到目标顶点的距离、费用、时间或其他度量。

• 出/入度：在有向图中，每个节点有出度和入度。出度：从该节点出发的边的个数。入度：指向该节点边的个数。

  • A (2 out / 0 in)
  • B、C、E (1 out / 1 in)
  • D (2 out / 2 in)
  • F (0 out / 2 in)
    

• 连通性：在图中表示节点的连通情况，我们称之为连通性。

• 连通图：无向图中任何两个节点都是可以到达

• 非连通图：无向图中有节点不能到达其他节点

• 强连通图：有向图中任何两个节点是可以相互到达的

• 连通分量：在无向图中的极大连通子图

  • 无向图中节点1、2、5构成的子图就是一个连通分量，该子图所有节点都是相互可达到的。
  • 节点3、4、6构成的子图 也是一个连通分量。
  • 节点3、4 构成的子图并*不是**该无向图的联通分量吗？因为必须是极大联通子图才能是连通分量，所以必须是节点3、4、6构成的子图才是连通分量。
  • 图论中岛屿问题其实就是求连通分量
    

• 强连通分量：在有向图中极大强连通子图。

  • 节点1、2、3、4、5 构成的子图是强连通分量，因为这是强连通图，也是极大图。
  • 节点6、7、8 构成的子图 不是强连通分量，因为这不是强连通图，节点8 不能达到节点6。
  • 节点1、2、5 构成的子图 也不是 强连通分量，因为这不是极大图。