KJHの博客

链表是一个很重要的数据结构，它由一系列不必在内存中连续存储的结构组成。本文讨论单向链表的基本操作，涉及到链表的创建、尾端添加元素、指定位置插入元素、删除指定单个元素节点、删除指定元素所有节点、删除指定位置节点、顺序，逆序打印节点以及统计结点个数等基础操作。

既然是不连续的内存空间，我们要访问各个元素，就需要通过指针来寻找。链表结构中需要定义数据域和指针域。

1、单向链表的数据结构

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

typedef struct _Node
{
	int value;
	struct _Node *pnext;
}Node;
2、创建一个不带表头的单向链表
void createList(Node **ppListNode, int value)
{
	Node *pListNode = NULL;
	pListNode = (Node *)malloc(sizeof(Node));
	assert(pListNode != NULL);

	pListNode->value = value;
	pListNode->pnext = NULL;
	 
	*ppListNode = pListNode;
	 
	return;

}

3、往链表尾端添加元素

很久之前研读过Linux的内核源码，看到其中的内核数据结构，对链表的实现叹为观止，是迄今为止我见过的最为经典的链表实现（不是数据内嵌到链表中，而是把链表内嵌到数据对象中）。现在再来回顾这个经典的数据结构。

链表代码在头文件<linux/list.h>中声明（推荐Source Insight，源码版本：Linux-2.6.32.61，早期版本并没有引进这个list），其数据结构很简单有木有，直接就一个前后链表指针，前篇STL中list也有这么个结构

1、链表的初始化

迪科斯彻算法(Dijkstra)是有荷兰计算机科学家艾兹格·迪科斯彻（Edsger Wybe Dijkstra）发明的。算法解决的是有向图中单个源点到其他顶点的最短路径问题。

算法描述

这个算法是通过为每个顶点 v 保留目前为止所找到的从s到v的最短路径来工作的。初始时，原点 s 的路径长度值被赋为 0 （d[s] = 0），同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于 V 中所有顶点 v 除 s 外d[v] = ∞）。当算法结束时，d[v] 中储存的便是从 s 到 v 的最短路径，或者如果路径不存在的话是无穷大。 Dijkstra 算法的基础操作是边的拓展：如果存在一条从 u 到 v 的边，那么从 s 到 v 的最短路径可以通过将边（u, v）添加到尾部来拓展一条从 s 到 u 的路径。这条路径的长度是 d[u] + w(u, v)。如果这个值比目前已知的 d[v] 的值要小，我们可以用新值来替代当前 d[v] 中的值。拓展边的操作一直执行到所有的 d[v] 都代表从 s 到 v 最短路径的花费。这个算法经过组织因而当 d[u] 达到它最终的值的时候每条边（u, v）都只被拓展一次。

算法维护两个顶点集 S 和 Q。集合 S 保留了我们已知的所有 d[v] 的值已经是最短路径的值顶点，而集合 Q 则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从 Q 移动到 S。这个被选择的顶点是 Q 中拥有最小的 d[u] 值的顶点。当一个顶点 u 从 Q 中转移到了 S 中，算法对每条外接边 (u, v) 进行拓展。

算法实现
算法实现起来比较简单，当然这得归功于算法作者。

一、邻接矩阵实现

下面的两种搜索算法都是基于 图的邻接表存储 。

深度优先搜索（DFS）

深度优先搜索（depth-first search）是对先序遍历（preorder traversal）的推广。我们从某个顶点 v 开始处理 v，然后递归地遍历所有与 v 邻接的顶点。

实现思想：

在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续探测下去，当节点 v 的所有边都已被探寻过，探索将回溯到发现节点 v 有那条边的始节点，这一过程一直进行到已发现从源节点可达的所有节点位置。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个过程反复进行直到所有节点都被发现为止。

这里则介绍图的另外一种存储方式：邻接矩阵。参考资料《大话数据结构》《C算法：卷二》

一、图的数据结构

图的邻接矩阵存储方式是用两个数据来表示。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边的信息。

见下图：（图片来源于《大话数据结构》）

​