阿烫的后花园

烫烫烫烫烫烫

发表于 更新于 分类于

Dijkstra算法使用了广度优先搜索解决了赋权有向图或无向图的单源最短路径问题。算法采用了贪心策略，分阶段的求解这个问题，这篇文章，我们进行详细的介绍。

这篇文章中，我们以图1.1中的赋权图作为示例。箭头上的数字为权值，圆圈中的字母为顶点中的数据，这里用一个字母表示。

1534060079132.png

我们依旧使用邻接表来表示图，那么上图中的有向图可以表示为图1.2的样子，如果不理解，可以看上篇拓扑排序中的内容。

1534060198241.png

实现步骤

首先，我们需要对每个顶点进行标记，每个顶点标记为Known（已知）的，或者标记为unKnown（未知的）。同时，每个顶点需要保留一个临时距离 dv 。这个距离实际上是使用已知顶点作为中间顶点从开始顶点 s 到 v 的最短路径的长。最后，我们记录 pv ，它是引起 dv 变化的最后的一个顶点。假如开始顶点 s 是 a ，那么用于Dijkstra算法的表的初始配置应当如图2.1所示。

1534064213351.png

Dijkstra算法按阶段进行，在每个阶段，Dijkstra算法选择一个顶点 v ，它在所有未知顶点中具有最小的dv，同时算法声明从 s 到 v 的最短路径是已知的。阶段的其余部分由dw值的更新工作组成。

图2.1表示我们初始配置，且开始节点为 s 为 a。

第一个选择的顶点是 a ，因为它在所有未知的顶点中具有最小的 dv ，dv 为0。将 a 标记为已知。既然 a 已知，那么某些表项就需要调整。观察图1.1，发现邻接到 a 的顶点有 b 和 d 。那么这两个顶点的项需要调整，调整后如图2.2所示。

1534065162883.png

继续选择一个未知的且具有最小 dv 的顶点，也就是 d ，顶点  c，e，f，g 是邻接的顶点，而且它们实际上都需要调整，如图2.3所示。

1534065701993.png

下一个被选取的顶点是 b ，其值为 2。d 是邻接的点，但已经是已知的，因此不必做对其做工作了。 e 也是邻接的点但不需要调整，因为结果 b 的值为 2+10=12。大于 e 已知的长度为3的路径。图 2.4指出这些顶点被选取以后的表。

1534066134468.png

下一个被选取的点为 c，其值为3 ，a 是邻接的点，但已知，不需要处理了。f 是邻接的点，因为 3+5<9,所以需要进行调整，如图 2.5所示。

1534066489981.png

下一个被选取的点是 e ，g 是唯一的邻接顶点，但不需要调整，因为 3+6>5。结果如图 2.6所示。

1534066684105.png

接着我们选取 g 。邻接的顶点只有 f ，因为 5+1<8，所以对 f 的距离需要下调到 6 。结果如图 2.7所示。

1534066812531.png

最后，我们选择顶点 f ，但其余所有顶点都已知，算法终止。最后的表在图 2.8中表出。

1534066911842.png

图3通过图形演示了在Dijkstra算法期间各边是如何标记为已知的以及顶点是如何更新的。顶点染成黄色说明此顶点标记为已知。

1534077874692.png

在算法结束后，我们最终得到了一张表（图 2.8）。在这张表里面，我们可以得到我们想得到的一切。例如 a 到 f 的最短路径为6。那么如何得到 a 到 f 的实际路径呢？我们可以编写一个递归来跟踪 pv 留下的痕迹。引起 f 的 dv 变化的最后的一个顶点是 g ，那么查询 g ；引起 g 的 dv 变化的最后的一个顶点是 d ，继续查 d ；引起 d 的 dv 变化的最后的一个顶点是 a ，也就是我们的开始节点，不需要继续查了， a 到 f 的最短路径就是 a->d->g->f 。 

代码实现

首先是图的顶点结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef string vertex;
struct Node
{
	vertex data;
	int weight = 0;
	Node *next = NULL;

	Node(vertex data,int weight, Node *next = NULL)
	{
		this-&gt;data = data;
		this-&gt;weight = weight;
		this-&gt;next = next;
	}
};

其次，我们还需要维护一个像上面的表，有known，dv，和pv。
表 不考虑负边

1
2
3
4
5
6
7
const int INFINITE = -1;  //距离 定义无限大
struct Box
{
	bool known = false;
	int dv = INFINITE;
	vertex path;
};

和上一篇拓扑排序中使用的方法一致，还是使用map来存储，比较方便。

直接给出代码，关键地方都已经打好注释

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
96
97
98
99
100
101
102
103
map<vertex, Box> Dijkstra(vertex v,map<vertex, Node> graph)
    {
    	map<vertex, Box> boxs = initBox(v, graph);
    	while (1)
    	{
    		map<vertex, Box>::iterator it = boxs.begin();
    		int min = 99999999;
    		//key为当前阶段应当标记为已知的顶点
    		vertex key;
    		int flag = 0;
    		while (it != boxs.end())
    		{
    			if (it->second->known==false&amp;&amp; it-&gt;second-&gt;dv!= INFINITE &amp;&amp;it-&gt;second-&gt;dv &lt; min)
    			{
    				min = it-&gt;second-&gt;dv;	//记录最短路径
    				key = it-&gt;first;		//记录最小路径的key
    				flag = 1;				//将flag置为1，说明，还有known为false的
    			}
    			it++;
    		}
    		//所有known都是true ，算法结束
    		if (flag == 0)
    		{
    			return boxs;
    		}

    		boxs[key]-&gt;known = true;		//将最小的顶点known置为true

    		//将所有与此顶点相邻接的点进行更新
    		Node* n = graph[key];
    		while (n != NULL)
    		{
    			//如果此顶点是已知的，就不虚要再处理了
    			if (boxs[n-&gt;data]-&gt;known == true)
    			{
    				n = n-&gt;next;
    				continue;
    			}
    			//此顶点计算出来到it2的路径
    			int d_new = boxs[key]-&gt;dv + n-&gt;weight;
    			//原本it2的路径长度
    		int d_old = boxs[n-&gt;data]-&gt;dv;

    			//需要更新
    			if (d_old == INFINITE || d_new &lt; d_old)
    			{
    		boxs[n-&gt;data]-&gt;dv = d_new;
    				boxs[n-&gt;data]-&gt;path = key;
    			}
    			n = n-&gt;next;
    		}
    	}
    }`</pre>

    输出算法的结果
    <pre>`string printp(vertex p, map&lt;vertex, Box*&gt; boxs)
    {
    	if (boxs[p]-&gt;dv == 0)
    	{
    		return p+"";
    	}
    	return printp(boxs[p]-&gt;path, boxs) + "-&gt;" + p;
    }
    //输出算法的结果
    map&lt;vertex, string&gt; printfDijkstra(map&lt;vertex, Box*&gt; boxs)
    {
    	//用来存放输出的内容
    	map&lt;vertex, string&gt; outs;
    	vertex aim;
    	//找到起点
    	map&lt;vertex, Box*&gt;::iterator it = boxs.begin();
    	while (it != boxs.end())
    	{
    		if (boxs[it-&gt;first]-&gt;dv == 0) {
    			aim = it-&gt;first;
    			break;
    }
    		it++;
    	}
    	it = boxs.begin();
    	while (it != boxs.end())
    	{
    		if (it-&gt;first != aim)
    		{
    			string path = printp(boxs[it-&gt;first]-&gt;path, boxs) + "-&gt;" + it-&gt;first;
    			outs.insert(pair&lt;vertex, string&gt;(it-&gt;first, path));
    	}

    		it++;
    	}
    	//outs已经存放好所有路径了
    	//打印数据
    	it = boxs.begin();
    	while (it != boxs.end())
    	{
    		if (it-&gt;first != aim)
    		{
    			cout &lt;&lt; it-&gt;first + "\t最短路径：" + to_string(boxs[it-&gt;first]-&gt;dv) + "\t路径：" + outs[it-&gt;first] &lt;&lt; endl;
    		}
    		it++;
    	}
    	return outs;
    }

1534089759880.png

完整测试代码

发表于 更新于 分类于

拓扑排序是对有向无圈图的顶点的一种排序，它使得如果存在一条从vi 到vj 的路径，那么排序中vj 在vi 的后面。如果图含有圈，那么拓扑排序是不可能的。此外，排序的结果不是唯一的，任何合理的排序都是可以的。

拓扑排序对应施工的流程图具有特别重要的作用，它可以决定哪些子工程要先执行，哪些子工程要在某些工程执行后才可以执行。选课课程同样如此，有些必须课必须要先修，有些要某些课程结束之后才能选修。

图的表示方法

图有两种表示方法，一种是邻接矩阵，它的空间需求是Θ(|V|²)，V为图的顶点个数。如果图是稠密的，那么这种方法是比较适合的 ，如果图是稀疏的，边的数量非常少，那么就会浪费大部分空间，这是很糟糕的，因为我们想要我们的数据结构表示那些实际存在的数据，而不是去表示不存在的数据。而大部分处理的图都是稀疏的，所以我们采用邻接表表示。邻接表是表示图的标准方法。对每一个顶点，使用一个表存放所有邻接的顶点，此时的空间需求为O(|E|+|V|)，如果是有向图，则存放的是指向的顶点。

1533652891196.png

对于上面的图，使用邻接表表示法的结果为下图所示

1533654312376.png

实现步骤

  1. 在有向图中选一个没有前驱，也就是入度为0 的顶点并且输出。
  2. 在图中删除该顶点以及和此顶点相关的边。
  3. 重复上述两步，直至所有顶点输出，或不存在没有前驱的节点为止。后者说明图是有环的。

观察图一，可以发现顶点1是没有前驱的，那么我们先输出1，然后删除顶点以及相关的边，得到下图。

1533659652842.png

继续寻找，发现2没有前驱，那么输出2，删除顶点以及边，得到下图。

1533659700303.png

继续寻找，5没有前驱，输出此节点后，得到下图。

1533659733346.png

继续寻找，4没有前驱，输出它得到下图。

1533659761851.png

此时，3和7都是没有前驱的，随意选择一个，输出3，得到下图。

1533659808925.png

然后输出7。

1533659857398.png

最后输出6，排序结束。

对于图一，1254376和1254736都是正确的拓扑排序。

代码实现

以下内容重写于 2021年 9月25日 夜 ，原来用的 c++ ，代码、解释也比较腌臜…

上图中说得很简单，看看哪个入度为 0，就删掉对应的节点和边。那咋快速知道哪个结点的入度为 0 ？当然就用一个数组了。这次演示，我们的结点都是用 0 - N 的数字标号，所以可以简单使用 List 和 int[] 来存储。如果结点的 key 是其他规则，则应该使用 Map。

edges 表示邻接矩阵， edges.get(i) 存储的是以 i 作为头结点的其它尾结点。 indeg 表示的是每个结点的入度书。

1
2
List<List<Integer>> edges = new ArrayList<>();
int[] indeg = new int[numCourses];

我们需要先初始化 邻接矩阵 和 每个结点的入度数

1
2
3
4
5
6
7
8
9
10
11
12
// N 是一共有多少个结点，是常量入参。
for (int i = 0; i < N; ++i) {
    edges.add(new ArrayList<>());
}
for (int[] edges : prerequisites) {
    int from = edges[0];
    int to = edges[1];

    adjacencyMatrix.get(from).add(to);
    // 入度 +1
    indeg[to]++;
}

接下来，要初始化队列，将所有入度为 0 的结点都先加入队列

1
2
3
4
5
6
Queue<Integer> zeroInDegreeQueue = new ArrayDeque<>();
for (int i = 0; i < N; i++) {
    if (indeg[i] == 0) {
        zeroInDegreeQueue.add(i);
    }
}

然后呢，就是不停地遍历队列直至为空，每次取出一个头结点，将相关尾结点的入度数 -1，如果 0 了，再将尾结点加入到队列中。你应该很清楚了，这就是个 BFS。

1
2
3
4
5
6
7
8
9
while (!zeroInDegreeQueue.isEmpty()) {
    Integer nowVisit = zeroInDegreeQueue.poll();
    List<Integer> tos = adjacencyMatrix.get(nowVisit);
    for (Integer to : tos) {
        if (--indeg[to] == 0) {
            zeroInDegreeQueue.add(to);
        }
    }
}

到这里基本就差不多了。但是不是忘记了什么？
怎么判断是否可以进行拓扑排序（即无环），假如可以，则排序结果呢，在哪？

排序结果我们只需要再用一个 ans 数组，每次从队列取出队头元素进行访问的时候，将其加入到 ans 中，即可。

如何判断是否有环？你可以在最后再遍历一下 indeg 数组，只要有一个入度不为 0 的，则有环；或者每次访问队列的元素的时候用个计数器数数，如果最后和 N 不一致，则说明有元素的入度不为 0。

发表于 更新于 分类于

日常需要，fq是必需的。因为arch官方以及aur提供的都是shadowsocks，不是ssr。所以我们需要去github上使用一些开源的ssr项目。

具体配置过程不说明了。和windows下有所不同的是，谷歌浏览器还需要安装switchyomega插件来进行设置代理。

设置开机自动启动ssr服务，以及自动切换代理。

阅读全文 »

发表于 更新于 分类于

堆,也被称为优先队列，是一种特殊的完全二叉树。常见应用是堆排序和Topk问题（找出最大的或最小的k个元素）。

队列中允许的操作是先进先出，在队尾插入元素，在队头取出元素。而堆也是一样，在堆尾插入元素，在堆顶取出元素，但是，堆中元素的排列顺序不是像队列一样按照到来的先后顺序，而是按照一定的优先顺序。这个优先顺序，可以按照元素的大小或者其它规则。

下面这棵树就是按照元素大小排列的。不难发现这棵二叉树有一个特点，所有父节点都比子节点大（注意圆圈里的是值，圆圈上面的是节点的编号）。符合这样特点的完全二叉树我们就称之为大根堆。反之，父节点比孩子节点小的，称之为小根堆。当然，你也可以按照其他规则进行排列。

比较有趣的是，因为堆是完全二叉树，所以使用数组来进行存储最合适不过了，而不是链表。因为这样更加节省空间，并且可以快速访问某个节点。不难发现，某个元素的下标为i，那么它的左右孩子下标分别是2*i+1和2*i+2（如果有左右孩子的话）。

上面的堆映射到数组中便是下图的样子。

堆的建立

堆的建立分为自上而下和自下而上两种方式建立。

自下而上构建堆

这里的“下”不是指最后一个元素，而是指最后一个有孩子的父节点，即n/2-1,n为堆元素个数，也就是第一幅图中的5号节点。以父节点为线索，逐渐调整该节点的子节点。

下面有一棵树，如何将其构建为大根堆呢？

先找到最后一个父节点，也就是5号元素，将其和它的孩子进行比较，左孩子比父节点大，那么进行交换，调整结束。见图二

接下来对4号父节点开始调整，不过，两个孩子都没有父节点大，所以无需调整，调整结束。

接下来对3号父节点开始调整，需要和比它大的8号节点进行交换，交换后调整结束。

接下来对2号父节点开始调整，两个孩子都比父节点大，将最大的和父节点进行交换，交换后调整结束。

接下来对1号父节点开始调整，它的左孩子比父节点大，那么进行交换，交换后的结果见图五。

此时和之前有一些不同，之前调整的父节点（3、4、5号父节点），它的孩子就是叶子结点，所以不需要再次进行调整。但现在和1号父节点的孩子不是叶子节点，它也有孩子。比较大的孩子和比较小的父节点交换后，孩子就变小了，如果这个孩子也拥有自己的孩子，那么可能会破坏堆的性质。

如上图，3号父节点已经不满足堆的性质了，虽然我们之前调整过3号节点，但因为1号节点的调整，导致它被破坏了。所以我们需要对和父节点交换的孩子再次进行调整直至孩子是叶子节点。

3号节点调整后如下图，它的孩子是叶子结点了，所以调整可以结束了。

接下来对0号根节点进行调整。父节点需要与左孩子进行交换。

然后我们需要对和父节点进行交换的1号节点继续调整，如下图。

继续对3号节点进行调整，如下图。

3号节点的孩子已经是叶子节点了，所以不需要再次调整，此时0号节点也调整完毕，那么堆也构建完成了。图八就是我们最终的结果。


自上而下构建堆

自上到下很好理解，首先假设当前数组arr的前i个元素已经满足堆性质（arr[0]只有一个元素肯定满足）；然后每次在数组之后添加一个元素A[i]，调整当前节点i使其满足堆化，使得新的数组A[0~i]满足堆化性质。直到i为n时，调整完毕，即堆化完毕。

可以分为三个步骤

  1. 将新元素增加到堆的末尾
  2. 按照优先顺序，将新元素与其父节点比较，如果新元素小于父节点则将两者交换位置。
  3. 不断进行第2步操作，直到不需要交换新元素和父节点，或者达到堆顶。

最后就会得到我们想要的堆。

那么，我们还是以图一的那棵树进行详细的演示。

首先对0号节点调整，额，没啥调整的，结束。

然后对1号节点调整，它比父节点大，和父节点交换后，调整结束。

然后对2号节点进行调整，13比19小，无需调整，调整结束。

然后对3号节点进行调整，3号比其父节点大，进行交换。

交换后的结果如上图，由于3号节点的父节点不是堆顶，那么我们还需要对1号节点再次调整，不难发现0号节点的堆性质已经被破坏了。对1号节点调整后如下，1号节点的父节点已经是堆顶，所以无需再次调整。

然后对4号节点进行调整，其父节点比它大，所以无需调整。

5号节点同上，无需调整。

然后对6号节点进行调整，它需要和父节点进行交换，交换后如下图。然后对2号节点进行调整，发现2号节点比父节点小，不需要调整。6号节点调整结束。

然后对7号节点进行调整，需要交换，调整后如下图。然后对7的父节点进行调整，发现无需调整。7号节点调整完毕。

然后对8号节点进行调整，需要和父节点交换。30这个数还是蛮大的，它会一直上浮。文字描述重复苍白，看图。

9号和10号无需调整。

然后对最后一个节点——11号节点进行调整，交换一次后，结束。

图十五就是我们调整的最终结果。


两种建立方式的区别

自下而上的方式，也叫做普通建堆，适合用于堆元素已经确定好的情况，时间复杂度实际上为O(n)。

自上而下的方式，也叫做插入建堆，适合动态的增加堆元素，时间复杂度为O(nlgn)。

所以，我们应当根据情况选择合适的建堆方式。


堆排序

如果掌握了上面两种建堆的方式，那么堆排序就相当简单了。堆排序十分巧妙，无需额外空间，直接在原数组内进行排序。

可以分为三个步骤

  1. 1.将数组堆化
  2. 2.将堆顶元素和最后一个元素交换
  3. 3.将剩余的n-1个节点重新进行堆化直到堆元素数量为1

重复步骤2、3就会得到一个有序的序列。

既然是排序，那么一般排序的元素都已经确定好了，所以堆排序构建堆的方式常用自下而上的方式。


代码实现

自上到下构造大根堆， 时间复杂度为O(nlgn)
void createHeapTop2Buttom(int arr[], int len)
{
	for (int i = 1; i < len; i++)
	{
		int c = i;
		int p = (c - 1) / 2;   //i父亲的下标
		while (arr[p] < arr[c])
		{
			//如果父亲比此节点小，则更换
			int tmp = arr[p];
			arr[p] = arr[c];
			arr[c] = tmp;
			//将当前节点更新为父节点继续调整
			c = p;
			p = (c - 1) / 2;
		}
		//满足大根堆，直接调整完毕
	}
}

自下到上构造大根堆， 时间复杂度为O(n)

void createHeapButtom2Top(int arr[], int len)
{
	for (int p = len / 2 - 1; p >= 0; p--)
	{
		//int p = p;
		int maxid = p;
		while (1)
		{
			//有孩子节点比父节点大
			if (p * 2 + 1 < len &&arr[maxid] < arr[p * 2 + 1])
			{
				maxid = p * 2 + 1;
			}
			if(p * 2 + 2 < len && arr[maxid] < arr[p * 2 + 2])
			{
				maxid = p * 2 + 2;
			}
			if (p == maxid)
			{
				break;
			}
			int tmp = arr[maxid];
			arr[maxid] = arr[p];
			arr[p] = tmp;
			p = maxid;
		}
	}
}

堆排序

void heapSort(int arr[], int len)
{
	while (len > 1)
	{
		createHeapButtom2Top(arr, len);
		int tmp = arr[0];
		arr[0] = arr[len - 1];
		arr[len - 1] = tmp;
		len--;
	}
}

下载代码







发表于 更新于 分类于

哈夫哈夫曼树（霍夫曼树）又称为最优二叉树。常用于哈夫曼编码，可以起压缩作用。
哈夫曼树的定义如下：

给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

定义中出现了以下几个概念

路径：树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
路径长度：路径上的分枝数目称作路径长度。
树的路径长度：从树根到每一个结点的路径长度之和。
结点的带权路径长度：在一棵树中，如果其结点上附带有一个权值，通常把该结点的路径长度与该结点上的权值之积称为该结点的带权路径长度（weighted path length）


对于哈夫曼编码，百度百科给的解释挺好，有兴趣可以读一下

在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。例如，需传送的报文为“AFTER DATA EAR ARE ART AREA”，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}。现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、011、100、101对“A，E，R，T，F，D”进行编码发送，当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符，则固定编码长度为5。然而，传送报文时总是希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。

哈夫曼树的构造

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。


举个例子，有如下八个权值，应该如何构造哈夫曼树呢？

先选出最小的两个权值，分别是2和3，将其合并，并将新的树放在森林中，将2和3作为新树的左右孩子，如图二

接下来继续选出最小的两个权值，分别是4和4，将其合并，并将新的树放在森林中，将4和4作为新树的左右孩子，如图三

继续重复以上步骤直至森林中只有一棵树

图八即是我们的最终的结果

代码实现

对于上面的例子，可以说主要思路就是对这个数组不停地取出最小的两个数然后相加再次放进这个数组里面。但对于代码，我们需要生成一棵实实在在的二叉树，那么这个森林该如何存储呢？如何取两个最小的相加再次放到数组里呢？

思考后决定，函数参数设置为一个数组。函数首先应该生成相应的节点，并且将这些节点放入vector中，对其进行排序之后，可以方便的找到最小的两个节点。取出后，生成一个新节点，将新节点放入vector中，原来最小的两个移除数组后重新排序，直到vector容器中只有一个元素为止，此元素就是哈夫曼树的根节点


二叉树结构体定义

struct BinaryTree
{
	int value = DEFAULT;
	BinaryTree *left = NULL;
	BinaryTree *right = NULL;
};

对sort函数重写比较方法

bool comp(const BinaryTree *a, const BinaryTree *b) {
	return a->value > b->value;
}

生成哈夫曼树，参数是一个数组，以及数组长度

BinaryTree* HuffmanTree(int nums[] ,int len)
{
	//初始化vector集合
	vector<BinaryTree*> nodes;
	for (int i = 0; i < len; i++)
	{
		BinaryTree *node = new BinaryTree;
		node->value = nums[i];
		nodes.push_back(node);
	}
	//对vector进行降序排列
	sort(nodes.begin(), nodes.end(), comp);
	while (nodes.size() > 1)
	{
		//删除最小的两个点
		BinaryTree *a = nodes[nodes.size() - 1];
		BinaryTree *b = nodes[nodes.size() - 2];
		nodes.pop_back();
		nodes.pop_back();
		//新增一个点
		BinaryTree *node = new BinaryTree;
		node->value = a->value + b->value;
		node->left = a;
		node->right = b;
		nodes.push_back(node);
		//重新排序
		sort(nodes.begin(), nodes.end(), comp);
	}

	return nodes[0];
}

测试代码

int main()
{
	int a[5] = { 3,8,1,7,9 };
	BinaryTree* tree = HuffmanTree(a, 5);
}

代码下载


发表于 更新于 分类于

广义表是一种复杂的数据结构，是线性表的扩展，能够表示树结构和图结构。

广义表是一 特殊的结构， 它兼有线性表、 树、图等结构的特点。 从各层元素各自具有的线性关系讲， 它应该是线性表的拓展; 从元素的分层方面讲，它有树结构的特点，但从元素的递归性和共享性等方面讲，它应该属于图结构。总之，它是一种更为复杂的非线性结构

设ai为广义表的第i个元素,则广义表Ls的一般表示与线性表相同：

            Ls=(a1,a2,…,ai,…,an)

其中n表示广义表的长度，即广义表中所含元素的个数，n≥0。如果ai是单个数据元素，则ai是广义表Ls的原子；如果ai是一个广义表，则ai是广义表Ls的子表，每一个ai称为Ls的直接元素。例如，下面的

            Ls=((a,b),c,(d,(e)))

就是一个合法的广义表表达式。

广义表具有如下重要的特性：
（1）广义表中的数据元素有相对次序；
（2）广义表的长度定义为最外层包含元素个数；
（3）广义表的深度定义为所含括弧的重数。其中原子的深度为0，空表的深度为1；
（4）广义表可以共享；一个广义表可以为其他广义表共享；这种共享广义表称为再入表；
（5）广义表可以是一个递归的表。一个广义表可以是自已的子表。这种广义表称为递归表。递归表的深度是无穷值,长度是有限值；

比较有趣的是第五点性质，一个广义表的可以是递归的，子表就是自己，那么就是这样  

        L=(a,L)=(a,(a,(a,(a,(a.......))))) ，这是一个无限的广义表，深度是无穷大，长度为2 。

广义表的结构有很多，有单链表广义表，有双链广义表等。这里描述的是单链广义表，采用以下结构

flag域为标记字段，该字段为0时，第二个域是Data，表示该节点是原子节点，flag为1时，表示该节点是子表，第二个域是SubList，存放子表第一个元素的地址。next是与本元素同一层的下一个元素所在节点的地址，当本元素是所在层的最后一个元素时，next域为NULL。

带头广义表会为每个节点设置一个表节点（称为元素的头结点），下图中，a、b、c、d四个节点的表节点就是橙色的节点，e、f的表节点是b，h、i的表节点的是f，以此类推。

有人可能会问，为什么要有最上面橙色的节点，答案是必须要有。如果没有最上面的橙色节点，那么上图的广义表就应该是 1,(3,((6),5)),2,(4)  ，而不是  (1,(3,((6),5)),2,(4))    去掉最上面橙色的表节点之后，我想求它的深度就很费解，它是指谁？a节点？a节点深度为 0，显然不对的。如果a节点的类型是子表，求出来的就是子表的深度。子表a的下一个节点是b，子表b的下一个节点是c，c的下一个节点是d，这样是四个广义表连在一起，而不是一个广义表！君不见任何一个广义表的表达式最外面都是一对括号嘛。所以我们必须加一个根结点（就是表节点），将a、b、c、d四个广义表作为根结点的子表。


广义表的代码结构设计如下

广义表有几个重要的操作——求广义表的深度、长度、遍历以及复制等。 在广义表中，同一层次的每个节点是通过next域链接起来的，所以可把它看做是由next域链接起来的单链表。这样,求广义表的长度就是求单链表的长度。


对于广义表的深度，等于所有子表中表的最大深度加1，如果为原子，深度为0。使用递归可以很好的解决这个问题。

对于表的遍历，使用递归也可以很快速解决。

广义表的复制也使用递归。


其实这种广义表的结构设计其实是有漏洞的。广义表的双链或单链表示都必须带头结点，否则对共享子表进行头插入和头删除操作将产生错误。举个栗子。

此时b和d是共享一个子表的，子表是e、f。

如果此时b对自己的子表进行头插了一个节点m，那么现在的情况是这样的，d指向的表头是错误的！而且实际情况中可能会有很多个节点共享这个子表。

所以比较完善的设计是为子表添加一个头结点，如下图。此时b和的依然共享一个子表，b和d任意操作，另外一个节点都不会出现错误。

发表于 更新于 分类于

下载安装包

wget http://download.redis.io/releases/redis-4.0.2.tar.gz

解压并安装

tar xzf redis-4.0.2.tar.gz
cd redis-4.0.2
make
make install

在Redis源代码目录的utils文件夹中有一个名为redis_init_script的初始化脚本文件。需要配置Redis的运行方式和持久化文件、日志文件的存储位置。步骤如下：

1、配置初始化脚本

首先将初始化脚本复制到/etc/init.d 目录中，文件名为 redis_端口号，其中端口号表示要让Redis监听的端口号，一般都是6379。客户端通过该端口连接Redis。然后修改脚本第6行的REDISPORT变量的值为同样的端口号。

2、建立以下需要的文件夹。

/etc/redis                    存放Redis的配置文件  
/var/redis/端口号        存放Redis的持久化文件  

3、修改配置文件

首先将配置文件模板（redis-4.0.2/redis.conf）复制到/etc/redis 目录中，以端口号命名（如“6379.conf”），然后按照下表对其中的部分参数进行编辑。

取消对bind 127.0.0.1 的注释，以便所有主机都都可以远程登录

daemonize 改为yes 使Redis以守护进程模式运行

pidfile改为/var/run/redis_你设定的端口号.pid ，设置Redis的PID文件位置


port 改为自己设定的端口号， 

设置Redis监听的端口号



dir改为

/var/redis/你的端口号  

设置持久化文件存放位置  


requirepass解除注释，并设置密码，不设置密码将会无法远程登录！


现在也可以使用下面的命令来启动和关闭Redis了

/etc/init.d/redis_6379 start
/etc/init.d/redis_6379 stop

让Redis随系统自动启动，这还需要对Redis初始化脚本进行简单修改，执行命令：

vim /etc/init.d/redis_6379

在打开的redis初始化脚本文件头部第四行的位置，追加下面两句

# chkconfig: 2345 90 10 


description: Redis is a persistent key-value database

追加后效果如下：

上图红色框中就是追加的两行注释，添加完毕后进行保存，即可通过下面的命令将Redis加入系统启动项里了

//设置开机执行redis脚本
chkconfig redis_6379 on

通过上面的操作后，以后也可以直接用下面的命令对Redis进行启动和关闭了，如下

service redis_6379 start
service redis_6379 stop


那么我们现在就差一个客户端了。客户端使用

RedisDesktopManager，在  gayhub 上可以下载。选择一个发行版之后下载，一路next安装完毕。如果你还无法登录的话，请检查防火墙

firewall-cmd --zone=public --add-port=6379/tcp --permanent
firewall-cmd --reload




发表于 更新于 分类于

之前使用scrapy，环境一直是自己的笔记本，但以后要使用分布式爬虫，所以linux下的环境也必须要搭建一遍。这里记录一下自己走过的坑。

centos系统默认安装的是python2.X，用 python -V 指令查看。

但是python3一定是趋势，不可避免的要使用这个版本的，而且我scrapy也是用python3编写的。

在搭建环境的时候，走过不少坑，这里记录下来。

主机使用的阿里云，centos版本号是7.3.1611，默认python2.7.5。由于我笔记本一直用的python3.6.4，所以打算所有主机都一致，以免出现不愉快的错误。

1.首先下载3.6.4版本的安装包

wget https://www.python.org/ftp/python/3.6.4/Python-3.6.4.tgz

2.解压

tar -xzvf Python-3.6.4.tgz

3.进入解压好的安装包路径

cd Python-3.6.4

4.编译安装包，指定安装路径
    注意：prefix参数用于指定将Python安装在新目录，防止覆盖系统默认安装的python

./configure --prefix=/usr/local/python36

make && make install

5.建立软连接（软连接可以理解为windows的快捷方式）

ln -s /usr/local/python36/bin/python3.6 /usr/bin/python3

这样python3就安装完了。直接运行python3就可以用python3了。

我曾经有过这样的想法，反正我不用python2.X，我直接软连接到python不可以么，这样我直接运行python，就可以用3了，少敲一个数字多好，网上也有这种办法。但是，这是不可取的！强烈不建议。因为centos默认是python2，那么不可以避免的很多东西都是依赖于python2的，比如yum。

我们可以用readlink获取一个软链接指向的目的路径。当一个软链接指向的是一个另外的软链接，而另外一个软链接又指向其他的目标。  这时可以使用-f选项直接获取最终的非软链接的目标。

如果我们把python指向的地址修改成了我们的python3，那么你又要修改一些东西了，可能还会出现其它错误。因为很多东西的文件头是这样的  #!/usr/bin/python ，你必须修改成这样 #!/usr/bin/python2  ，因为python 已经指向python 3了。曾经我改掉了python的软连接，很多东西报错，按网上的方法修改了很多文件，但还是报错，导致我彻底卸载python和yum，又重新安装，最终还是重做了系统，很烦心。所以，系统的东西就让他留着吧，别轻易改他。

此时，我们运行python3，输入 import ssl 回车，此时，应该会报错。如果没有最好，我的另外一个主机就没有，可能是因为装了宝塔面板，都帮我搞定了。遇到这种情况，退出python3 ，运行pthon ，同样输入 import ssl ，会发现没有报错。（如果也报错就另当别论）这说明了我们是安装了openssl的，只不过pyhon3没有找到而已。现在，我们要进入到python源码包解压后的那个目录下的Modules/Setup，将下面四行代码取消注释，重新 make &&make install

但此时又报了一个错误 找不到openssl/rsa 这个文件，执行 yum install openssl-devel 解决问题（我另外一台电脑是deepin，指令为 apt-get install libssl-dev ，Ubuntu，Debian应该一致），重新 make &&make install。完成之后就可以导入ssl了。

现在我们继续尝试import sqlite3，如果报错，检查自己有没有安装sqlite-devel，没有的话yum -y install sqlite-devel

然后还是在Python源码目录里面，命令行输入./configure，再一次make && make  install ，这样就可以基本解决问题了，若还不行，自习百度吧。

接着，我们开始安装scrapy的环境，常用的包管理工具有pip ，系统是有默认装好的

查看，可以发现是python2.7的，那么python3 怎么安装pip，两个版本的都有pip，我怎么知道是在用哪一个pip呢?其实很简单。首先我们安装python3的时候，已经给我们自动装好了pip，运行 python3 -m pip -V  查看版本。

当然，每次运行python3的pip都要写那么长的指令是不友好的，建议为pip建立软连接，

ln -s /usr/local/python36/bin/pip3 /usr/bin/pip3

使用

pip3 -V

查看是否成功建立，如果成功，以后只需要执行pip3 install ..... 就可以了。


最后安装scrapy。

pip3 install scrapy#or  python3 -m pip install scrapy

安装过程中可能会出现找不到Twisted的错误，安装此依赖即可，如下。

wget https://twistedmatrix.com/Releases/Twisted/17.1/Twisted-17.1.0.tar.bz2
tar -jxvf Twisted-17.1.0.tar.bz2
cd Twisted-17.1.0
python3 setup.py install

解压可能会遇到如下错误

tar (child): lbzip2: Cannot exec: No such file or directory 
tar (child): Error is not recoverable: exiting now 
tar: Child returned status 2 
tar: Error is not recoverable: exiting now

是因为还没有安装bzip2，通过 yum -y install bzip2 命令安装一下就好了 。

剩下一些需要使用到的库

pip3 install pycryptodome
pip3 install pymysql
pip3 install scrapy_redis



发表于 更新于 分类于

在分析网易云音乐API加密的时候，参考了网上很多博客，大致了解了流程，同时也用这些方法成功的拿到了好几个API的数据。

但是，在尝试获取用户的听歌排行时，却发生了问题，后台没有返回数据。第一想到的是，我是不是API调用错了，刷新了几次，排除了这个问题。第二，是不是这个API传的数据格式错了，查看Sources，找到这行代码，多猜测，多打印数据可以猜出来 JSON.stringify(i9b) 就是要传给后台的，即将加密的参数。

有人可能要问了，你怎么知道是这段代码进行的参数加密，原因很简单，通过network。record?这个是我们请求的api，这是用post进行请求的，可以看到form表单里面提交了两个数据，一个是params，另外一个是encSecKey，那么我们可以通过搜索这两个关键字，params比较大众，我们搜encSecKey这个关键字好了。

可以看到浏览器是请求了很多文件的

那么我们搜索哪一个文件？通过network，我们可以知道发起请求的是哪个文件

点进去，搜索即可。

好像有一点偏题了...我们继续讲。通过控制台打印这个字段，多次确认后，没有传错数据格式，排除此可能。

第三，是否是因为这个API接口的参数换了一种加密方式，导致我算出来的参数是错的？不应该吧，不同的接口用不同的加密方式，网易不累么。。。再次逐语句后，执行过程和之前的接口是一致的，加密的参数也一样，也排除了这种可能。这些就比较疑惑了，去网上搜索，发现有的Request请求必须要加上特定的Headers，恍然大悟。查看了下network，把所有headers全部添加到了postman里面，激动地点击send。返回200。没有数据。感到绝望。为什么？还能有什么原因？我遗漏了什么？浏览器里的请求和我在postman里的请求肯定是有某些地方不一样！它躲在了哪里？

一夜无话。

第二天，搜索postman的一些调试技巧，发现了直接从浏览器抓取request的方法，看到这个方法，很开心，这样就不需要我手动输入参数了，因为自己可能会输漏了什么。抓取的浏览器的request后，开始看看他的请求了。

8个请求头，两个表单参数，没什么特殊的啊。那么开始更换表单里的参数，替换成我自己的参数后，拿不到数据了。加密得到的参数错误了？网易云音乐的加密一共是进行了两次AES加密，一次RSA加密。第一次AES加密的key是固定的，第二次加密的key是随机的16位数，然后对随机的这个key进行一次RSA加密，结果也就是我们的encSecKey。

为了验证是否是加密错误，继续在浏览器中进行调试，拿到它随机的16位数之后，用自己的加密方法进行计算，果然，第二次AES加密后，不是正确的结果了。问题找到了，自己的加密算法出现了错误。但，为什么前几次API都能成功调用？继续查看第一次加密时的结果，和浏览器里的正确结果对比一下，是一致的，那么错误发生在，第二次加密身上。

手动将第一次的结果，放在加密函数的参数里，惊奇的发现pyCharm有一个警告

一行语句超过了120个字符，虽然不知道为什么有个120字符的要求，但问题肯定就出在这了，我所要加密的字符太长了。这下豁然开朗，之前几个API能成功，是因为，第一次加密返回的结果长度不是很长。因为他们的数据不是很长，前两个API的数据格式如下

{"ids":"[440208476]","br":128000,"csrf_token":""}
{"userId":"317556268","offset":"0","total":"true","limit":"20","csrf_token":""}

而这个API的数据格式是这样的

{"uid":"285056784","type":"-1","limit":"1000","offset":"0","total":"true" ,"csrf_token":""}

的确是长了很多。我的解决办法是删了无用的 "csrf_token":"" ，减少了一点长度，重新加密传给后台后，成功拿到数据。

当然这是治标不治本的方法。




发表于 更新于 分类于

最近两天又闲得慌了，学习了一下爬虫。爬虫，久闻大名，如雷贯耳，总觉得是个很牛逼的东西，难度不小。学了两天下来，发现是很牛逼，但是难度真的不大。

在学习之前，一片空白。大约一年前看过廖雪峰的Python教程，现在估计也忘得差不多，如果你也是Python小白的话，去看下廖雪峰的Python教程吧。花了小半天时间复习了一下Python，这门语言入门还是很简单的，如果有其它语言的基础，大约一个小时就能写点东西出来了。

那么我们再去查Python环境下如何实现爬虫，发现一个特别特别强大的框架——scrapy，那我们就用它了。嗯？网上不是说有很多东西么？urllib、urllib2、bs4、pyspider、beautifulsoup什么什么的？一张图你就懂了

1529911118779.png

先了解下爬虫的原理。

如果我们把互联网比作一张大的蜘蛛网，数据便是存放于蜘蛛网的各个节点，而爬虫就是一只小蜘蛛，沿着网络抓取自己的猎物（数据）爬虫指的是：向网站发起请求，获取资源后分析并提取有用数据的程序从技术层面来说就是 通过程序模拟浏览器请求站点的行为，把站点返回的HTML代码/JSON数据/二进制数据（图片、视频） 爬到本地，进而提取自己需要的数据，存放起来使用。
爬虫是通过网页的链接地址来寻找网页的。从网站某一个页面（通常是首页）开始，读取网页的内容，找到在网页中的其它链接地址，然后通过这些链接地址寻找下一个网页，这样一直循环下去，直到把这个网站所有的网页都抓取完为止。如果把整个互联网当成一个网站，那么爬虫就可以用这个原理把互联网上所有的网页都抓取下来。

废话不多说，我们直接开工，首先装环境，我装的Python3.6版本，win10系统。Python安装完成之后，前往pip的官网https://pip.pypa.io/en/stable/installing/，安装pip，提供了一个get-pip.py文件，下载之后运行即可。

_pip_是一个现代的，通用的 Python 包管理工具。提供了对 Python 包的查找、下载、安装、卸载的功能。

打开cmd，输入 pip -V ，检查pip版本，没有问题后开始安装scrapy，指令为 pip install scrapy ,安装完成之后，cmd输入 scrapy version,可以查看版本号，我使用的是1.5。
1529889528139.png

之后我们还要用到mysql，这里也顺便把包安装好，指令为 pip install pymysql。

现在我们需要创建一个scrapy的工程，在自己想建立工程的位置运行cmd，输入 scrapy startproject HelloScrapy, HelloScrapy是我们的工程名。
1529889459250.png

接下来，我们用PyCharm，打开我们创建的这个工程
1529889659786.png

查看目录结构，scrapy为我们生成了很多东西，spiders文件夹下放的是我们写的爬虫代码，items.py是用来定义我们所需要获取的字段piplines.py是用来定义我们的存储，settings.py是定义的各种设置。现在不懂没关系，反正我们之后会用到，写一写就明白了。

现在，我们要做一件事，在根目录里，新建一个entrypoint.py文件，里面输入以下代码

1
2
from scrapy.cmdline import execute
execute(['scrapy', 'crawl', 'dingdian'])

因为Scrapy默认是不能在IDE中调试的，以后我们直接运行这个py文件就可以跑整个项目。

现在我们的项目应该是这样的
1529890346888.png

第二行中代码中的前两个参数是不变的，第三个参数是自己的spider的名字。

可是，我哪里来的myspider…别急，我们现在就来建立。首先，我们先找个爬取的目标——顶点小说，(对不住了) 现在的域名是www.x23us.com ，那么我们在IDE里面打开terminal 输入<span style="color: rgb(194, 79, 74);">scrapy genspider myspider www.x23us.com 回车之后，scrapy就会用模板给我们自动生成一个爬虫

1529896012275.png

查看项目结构，多了一个文件，还有一些代码。

1529896122906.png

其中，name这个字段就是我们的spider的名字，整个项目不可重复。
allowed_domains这个字段是用来过滤爬取的域名，如果一不小心爬到别的地方了，就可以通过这个字段过滤掉。
start_urls就是我们第一个爬取的起始地址，这是一个list，所以可以起始地址可以有很多个。

还有一个parse方法，每个网页请求成功之后，都会调用这个方法进行处理。

爬取一个网站，肯定要先分析它是如何组成的 。
1529894525794.png

打开首页，有很多分类，自己一个个点开会发现url后缀的变化，2_1.html,3_1.html,4_1.html等等。那么爬虫的入口地址就有了

玄幻魔幻：http://www.

x23us .com/class/1_1.html
武侠修真：http://www.

x23us .com/class/2_1.html
都市言情：http://www.

x23us .com/class/3_1.html
历史军事：http://www.

x23us .com/class/4_1.html
侦探推理：http://www.

x23us .com/class/5_1.html
网游动漫：http://www.

x23us .com/class/6_1.html
科幻小说：http://www.

x23us .com/class/7_1.html
恐怖灵异：http://www.23wx.com/class/8_1.html
散文诗词：http://www.23wx.com/class/9_1.html
其他：http://www.23wx.com/class/10_1.html

入口有两种写法，一种是用start_urls变量，直接把上述的url地址放进去，但是不太美观。还有一种是重写start_requests函数，重写这个函数之后，start_urls就不起作用了，我使用的后者，将地址拼接出来了。
1529897136123.png

现在运行entrypoint.py

1529905448568.png

可以看见控制台输出了一大堆日志
1529905739514.png

看见这些，就说明OK了。

现在我们要遍历所有的页面来获取所有小说
1529906200509.png

每个分类下面可以看到总页数，我们获取每个分类的总页数，然后循环，理论上就可以拿到所有页面了。如何获得这个总页数？这就需要用到xpath，找到这个元素在html的位置。不知道什么是xpath？没关系，多用用就明白了，没什么复杂的（其实我也不懂啥事xpath - -！）。我使用的谷歌浏览器，右键单击上图中的106

1529906491592.png

点击最下面的检查

1529906542263.png

右键单击蓝色高亮的代码，Copy -> Copy XPath 就能拿到位置，复制到的是

1
//*[@id="pagelink"]/a[14]

想要拿到它里面的值需要这样

1
response.xpath("//*[@id='pagelink']/a[14]/text()").extract_first()

/text()能够获得里面的值，response.xpath() 返回的是一个list，使用，如果列表里只有一个元素，使用extract_first()来提取，如果list里面有多个元素，就必须要使用extract()来获取全部元素。

1529907787391.png

我们构造完URL之后继续调用Reques，回调函数为parse_name()

1529907963986.png

我们要拿到每一个小说的名称和作者，和拿到最大值的流程一样，懒癌犯了，直接贴代码…..

分别获得三个列表，然后for循环一个个取出来，发现多了一个meta字典，这是Scrapy中传递额外数据的方法，因我们还有一些其他内容需要在下一个页面中才能获取到。

1529908241278.png

现在我们的爬虫到了这个页面，这个页面我们就取一个收藏数吧

1
collect_num_str=response.xpath('//*[@id="at"]/tr[2]/td[1]/text()').extract_first()  # 网页中含有<span style="color: inherit; font-size: inherit;"> 空格 ==> \xa0</span>``collect_num=int("".join(collect_num_str.split())) #去掉空格的编码 收藏数

pre宋体';font-size:10.5pt;"这里有个要注意的地方，网页中含有&nbsp;，我们提取出来的/pre宋体';font-size:10.5pt;"collect_num_str含有\xa0，我们需要去掉它。

1529908469449.png

至今为止我们，已经抓取了我们想要的内容了，小说名称，作者，链接，收藏数。上面的代码都打印出来了。

现在我们需要存到数据库里面。这时候我们需要编辑item.py了

1529909445417.png

写下这四个我们所需的字段。

在根目录下新建mysqlpiplines文件夹，文件夹下面建立sql.py。
1529909412510.png

我们要在sql.py里面编写我们的sql语句。打码的四个变量写上你自己的。
1529909158644.png

主要写了两个方法，一个插入，一个根据小说名称判断是否已经存在。

现在编辑piplines.py
1529909361390.png

接着我们修改一下我们的爬虫代码。
1529909600858.png

把我们拿到的数据传给item，剩下的就不需要我们做了。

最后一步，打开settings.py,关掉ITEM_PIPELINES的注释
1529909843437.png

这个300是优先级，现在不需要管它，关闭掉注释就可以了。

我们跑下项目，爬虫已经可以开始正常工作
1529909925822.png

大约爬了三十分钟，抓起了三万八千多条记录。是不是特别强大？

1529910021416.png

项目完整地址： https://github.com/peihuanhuan/dingdian

参考https://cuiqingcai.com/3472.html/comment-page-1

1

0%