数据结构和算法

前言

为什么要写这一篇呢？原因是我不够熟练，大多时候，比如说要写一个栈，我想一想是能够写出来了，可是当我再去细致思考时，比如我用什么来实现呢？数组，链表。有比如我用数组去实现队列，是用循环队列呢？还是普通队列。我现在又想起这些问题的时候，我发现还是自己掌握的不够扎实。还有一点就是记忆，我刚去看了之前写的哈夫曼，虽然也用到了树结构，但是现在又去看，还是觉得在基础上模模糊糊的，虽然也敲了很多天代码才写成，但是什么也没有留下。所以这次决定从线性结构到图，把一般常用的数据结构以及算法再梳理一遍，所以这篇文章应该会比较长。

数据结构

线性

线性表
线性表也就是大部分常在使用的数组，所谓线性也就是跟一根线一样，直直的，所有的数据够挂在这根线上。这里不再讨论数组的实现和创建，一般这个比较简单，大部分语言已经集成了这个功能。此处就直接来讨论链式存储，链式存储就跟冰糖葫芦一样，只不过形式上和冰糖葫芦还不太像，因为冰糖葫芦是一根棍子穿着所有的山楂，把链这个字没有体现出来。不知道大家有没有见过一种武器，武器是由一个铁球和一条铁链子，这个铁球表面上还有很多坠状的金属，这个形状跟仙人球很像，不过没有仙人球的刺那么密但比仙人球的刺的比例要粗很多。如果把这种武器和冰糖葫芦结合在一起，也就是把冰糖葫芦中的那根棍去掉，取而代之的是这种武器上的铁链子，然后把每个山楂串起来。这样的一个形状来解释链表的形式就清楚了一些。
链表通常有三种操作，创建、删除节点、插入节点。
我之前经常在创建上发生疑惑，疑惑点有两个，其一是带头与不带头，其二就是大部分喜欢用双重指针来构建链表。今天我就把这两个问题重新模拟一遍，把我通常创建方法与这两种疑惑点进行对比来看看。
当我去思考上述两个问题的时候发现其实都是指针问题，而后我又把指针拿来揣摩了一番，其实大部分都跟我之前的认识是相同的，只不过长时间不去使用指针就把很多东西遗忘掉了，以至于不能熟练的去读懂别人的代码。接着我再次来详细的说明一下什么是指针，课堂中老师们经常用索引或者钥匙来说明指针，而在我眼里指针中其他int数据类型或者char数据类型一样也是一种数据类型只不过比较特殊。他特殊的一点在于他可以指向其实变量的地址，并且他通过一些特俗的操作可以去访问和修改他指向的那个变量的值。关于这点，如果有点汇编经验的同学可能一看就会明白，如果抛开汇编或者组成原理来讲这件事情的话就需要花费些心思了。如果把内存比作大海，指针就好比海里的鱼，还是那种比较凶猛的鱼，比如说鲨鱼。其实这个例子不太恰当，因为大海和内存不成正比，其二大海是三维的而内存是二维的。我接着说这个不太恰当的例子，首先鲨鱼也是鱼，就好比指针也是变量一样。这是事务的本质，这一点一定要看明白。其次，鲨鱼这种鱼可以游走是大海的任何地方，这一点就像指针一样，可以指向内存的从00000000-ffffffff任何一个地址。最后这个鲨鱼可以让所到之处变化样子，这就好比指针可以改变所指向变量的值一样。其实道理讲起来都比较简单，大家也都容易明白，但你依然过不好这一生，就像是你依然用不好指针一样。此处再来聊一聊双重指针或者多重指针，我感觉这个思想是有些递归的意味了，多重指针也就是指向多减1重指针的指针，比如说这里的多是i，那么也就是说，i重指针是指向i - 1重指针的指针，然而i - i重指针是指向i - 2重指针的指针，然后一路向前推，直到1重指针。这个意味有些螳螂捕蝉黄雀在后的感觉，只不过不是这3中动物，而是多种动物厮杀链。今天算是有看了一天关于指针的事情，自己也写了不少的测试代码。发现自己随便写的那些代码有很多UB的问题，UB也就是所谓的未定义的行为。关于指针其实还是要明白他的基本，指针只不过是一个变量，但是他存储的是其他变量的地址。
接着讨论线性表的创建。线性表的创建一般分为两种方式，头插和尾插。我这里只来说明这两者的本质吧，所谓头插就是找到头结点，在头结点之后插入新的节点即可。所谓尾插就是找到尾节点，在尾节点之后进行插入。这两个插入操作的时间复杂度都是O(n)，具体就看应用情况了，比如要实现链式存储的栈用头插就比较好，因为头插方法是按照先进后出的特点来输出元素的。下面的代码中我写了3中链表的创建方式，第一种是尾插的方法，也就跟我描述的一样找到尾节点，将其插入，如果链表是空的，就直接将带插入节点赋值给链表头指针即可。这里要谈一下头指针为何是双重指针，关于函数返回值，是有三种方式的，一种是return，一种的参数（地址传递），一种是全局变量，因为此处需要把p所指地址的内容传出去，故使用了双重指针，当然你也可以单指针，就好比我经常的写法，只不过要浪费掉一个节点。第二种是我经常使用的方法，是头插法，也就是输出内容的顺序与插入值得顺序是相反的。第三种也是头插法，此处你可以看到链表实现的方法是多种多样的，第三种是通过返回值来传出节点的地址的。写完这三种方法后，我得找一种我喜欢的，其实还是我经常写的那个比较顺手，但是浪费了一个节点。不过最主要的是这种思想，我之前出现的那些问题，现在也能想明白了，主要是关于指针和函数的返回值问题。现在看来都是基础的问题，实际中，你是要把基础的问题理解的深刻。

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
#include<stdio.h>
#include<stdlib.h>
typedef struct LinkList
{
	int key;
	struct LinkList *next;
}L;
void createoftail(L **head, int k)
{
	L *p = (L*)malloc(sizeof(L));
	p->next = NULL;
	p->key = k;
	if(*head == NULL)
	{
		*head = p;
	}
	else
	{
		L *t = *head;
		while(t->next != NULL)
			t = t->next;
		t->next = p;
	}
}
void me(L *head, int k)
{
	L *p = (L*)malloc(sizeof(L));
	p->key = k;
	p->next = head->next;
	head->next = p;
}
L *createofreturn(L *head, int k)
{
	L *p = (L*)malloc(sizeof(L));
	p->key = k;
	p->next = head;
	head = p;
	return head;
}
int test(L *head, int *a)
{
	L *p = head;	
	if(p == NULL)
		return 0;
	int f = 1;
	while(p != NULL)
	{
		if(*a != p->key)
		{
			f = 0;
			break;
		}
		a++;
		p = p->next;
	}
	if(f == 1)
		puts("passed");
	else
		puts("falied");
}
void testoftail()
{
	L *h = NULL;
	L **head = &h;
	createoftail(head, 4);
	createoftail(head, 3);
	createoftail(head, 1);
	int a[] = {4, 3, 1};
	test(h, a);
}
void testofme()
{
	L *head = (L*)malloc(sizeof(L));	
	head->next = NULL;
	me(head, 4);
	me(head, 3);
	me(head, 1);
	int a[] = {1, 3, 4};
	test(head->next, a);
}
void testofreturn()
{
	L *head = NULL;
	head = createofreturn(head, 4);
	head = createofreturn(head, 3);
	head = createofreturn(head, 1);
	int a[] = {1, 3, 4};
	test(head, a);
}
int main()
{
	testoftail();
	testofme();
	testofreturn();
	return 0;
}

关于剩下两种操作，其一是插入节点，实际上创建的过程就是插入节点的过程，其二是删除节点。删除节点通常有两种方式，一种是通过索引的方式，一种是删除指定值得方式。C有一点不好的地方就是不能像Java那样垃圾回收，也就是你删除节点后还需要你的手动把这部分的存储空间释放掉，在C中释放存储空间的函数是free。删除节点的思路比较简单，第一步是找到这个节点，之后将这个节点之前的那个节点的线连接在这个节点之后的那个节点上就可以了。下面是代码的实现，一种是通过索引，一种是通过指定的值。

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
int del(L **head, int key)
{
	if(*head == NULL)
		return 0;
	L *one = *head;
	//链表中只有一个节点
	if(one->next == NULL)
		if(one->key == key)
		{
			free(one);
			*head = NULL;
			return 1;
		}
		else
			//删除值不在链表中
			return 0;
	//头结点是要删除的值
	else
	{
		if(one->key == key)
		{
			*head = (*head)->next;
			free(one);
			return 1;
		}
	}
	L *two = one->next;
	while(two != NULL)
	{
		if(two->key == key)
			break;
		two = two->next;
		one = one->next;
	}
	//删除值不再链表中
	if(two == NULL)
		return 0;
	//删除节点是尾节点
	if(two->next == NULL)
	{
		free(two);
		one->next = NULL;
		return 1;
	}
	else
	{
		one->next = two->next;
		free(two);
		return 1;
	}
}
void testofdel()
{
	L *head = (L*)malloc(sizeof(L));	
	head->next = NULL;
	me(head, 4);
	me(head, 3);
	me(head, 1);
	L *h = head->next;
	del(&h, 3);
	del(&h, 4);
	del(&h, 1);
	del(&h, 1);
	if(h == NULL)
		puts("passed");
	else
		puts("failed");
}

刚开始写的那会还觉得比较简单，可是回想到剑指offer上说的，把问题想全面就发现问题开始繁琐起来，其实我是挺讨厌这种繁琐的问题，繁琐的问题和难的问题是不一样的，繁琐是将这件事的复杂也就是说需要你每一步都能想到，这样才能得出完美的解答。如果稍不留神想不到一个点，那么代码就会出现bug。在写上面的删除节点的问题时候，刚开始是想通过两个方式来删除节点，索引和值删除，本来是想写在一个函数里的，后来我想了更多的，比如删除的节点是头结点或者尾节点或者链表中只有一个节点的情况，对于这些处理的方式都是不同的，因此你要思考好这些问题的关系，也就是谁包括谁的问题。后来我就改成了只写一种，通过值来删除节点，而后我又想起一个问题，如果有多个值如何处理，我发现这就又繁琐了起来， 后来想到如果有多个值可以通过函数的返回值来写，也就是我在函数内部实现删除一个值，在函数外部通过返回值来判断多个值是否删除。这样保持的函数本身的简洁性，后来我在考虑关于如何设计多个函数以及期间的关系，也就是软件工程中所说的耦合和内聚问题了。所以说，简单的事情并不简单。

栈和队列
栈和队列是特别简单的概念，估计任何你跟任何一个小学生聊这个问题，他们也是能明白什么是栈，什么是队列，这可能就是所谓的伟大的东西都是简单的东西。栈和队列在计算机领域是应用特别广泛和基础的两种数据结构，就拿栈来讲，函数的调用，其实这个具体实现我也不太明白，大家都拿这个来举例子，我也就再拿来这个来加深记忆。函数调用，比如在main()中调用，f1()，首先将main()的地址进栈，之后再将f1()的地址进栈。队列的应用我记得是在操作系统中比较常见，因为在进程调度中，很多进程等待着CPU的时候，会按照队列的形式在哪等着，就跟你去银行办理业务一样，得排队是一个道理。栈的性质是先进后出，队列的性质是先进先出。
接下来我分别用数组的形式来实现栈和队列的基本操作，常用的基本操作就是初始化栈或者队列，入栈、入队、出栈、出队，判断栈或者队列是否为空。因为用数组了，所以下面的代码我用Python来写。

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
# coding:utf-8

class s:
	def __init__(self):
		self.m = 65536
		self.top = -1
		self.l = []

	def push(self, key):
		if(self.top != self.m):
			self.l.append(key)
			self.top += 1

	def pop(self):
		if(self.top != -1):
			tmp = self.top
			self.top -= 1
			return self.l[tmp]
		else:
			return None

def test():
	k = s()
	a = []
	t = []
	a.append(4)
	a.append(3)
	a.append(2)
	a.append(1)

	for x in a:
		k.push(x)
	
	t.append(k.pop())
	t.append(k.pop())
	t.append(k.pop())
	t.append(k.pop())
	t.reverse()
	if(a == t):
		print("passed")
	else:
		print("failed")

test()

Python小记
本来说是用Python去写的，打开vim就搞了C，后来又写了Python的，不得不说Python的数据结构封装的太现成了，去实现这些都不知道从何下手了，应该说是下手的地方太多了。第一次写Python的类，Python的面向对象和Java和C#的差别的确有点大。其中静态变量之间定义在类体中，也省了static这关键词。而后的私有变量是__开头就行，省了private。我感觉通常使用self关键字就可以定义变量了，用的时候也这样用就行了，self中定义的变量通过类名是访问不了的。也就是说在类里定义变量的话，如果没有什么特殊要求，也就是设计模式那一套，来搞算法的话，self.varname就可以了。

接着就来回忆一下队列。逻辑结构就不在细说了，队列的实现上，其实我觉得用链式是蛮简单的，一个尾指针和一个头指针，尾进，头出。如果队列为空的话就是尾指针和头指针相等。队列什么时候满这就要看内存空间大小了，当然你也可以人为的去设计一个计数器放在结构体中。之后来聊一聊数组实习的方式，数组通常是使用循环队列来实现的，这样的目的是为了提高空间利用率。队列为空的判断依旧是尾指针和头指针相等，队列为满的条件是尾指针 + 1 除以队列大小后去余数看是否等于头指针。这样的写法会使得队列损失一个元素，但不失为最好的方法。关于循环队列的实现关键其实是取余数运算，这样可以限制取得的余数一直在某个范围内，达到了循环的作用。算法导论里并没有使用取余操作，而是增加了一个判断，似的尾指针和头指针依旧在某个范围循环出现，操作是判断尾指针和头指针是否等于队列长度，如果等于就从新置为1。下面我用C来写队列的链式存储，用Python来写循环队列。

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
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
	int key;
	struct node *next;
}node;
typedef struct
{
	node *tail;
	node *head;
}Q;

void init(Q *q)
{
	q->tail = NULL;
	q->head = NULL;
}
void enqueue(Q *q, int key)
{
	node *p =(node*)malloc(sizeof(node));	
	p->key = key;
	p->next = q->tail;
	q->tail = p;
	if(q->head == NULL)
		q->head = p;
}
int dequeue(Q *q)
{
	if(q->tail == NULL || q->head ==NULL)
		return 0;
	if(q->tail == q->head)
	{
		int key = q->tail->key;
		free(q->tail);
		q->tail = q->head = NULL;
		return key;
	}
	node *t = q->head;
	int key = t->key;
	node *h = q->tail;
	//找到倒数第二个节点
	while(h != NULL)
	{
		if(h->next == t)
			break;
		h = h->next;
	}
	h->next = NULL;
	q->head = h;
	free(t);
	return key;
}
void test()
{
	Q *q = (Q*)malloc(sizeof(Q));;
	q->tail = NULL;
	q->head = NULL;
	enqueue(q, 1);
	enqueue(q, 2);
	enqueue(q, 3);
	enqueue(q, 4);
	int a[] = {1, 2, 3, 4};
	int i = 0;
	while(i < 4)
	{
		if(dequeue(q) == a[i])
			i++;
		else
			break;
	}
	if(i == 4)
		puts("passed");
	else
		puts("failed");
}
int main()
{
	test();

聊一聊用C写的链式存储，这次写的时候提前没有想明白，以至于去敲代码的时候发现了很多问题。其一链式的队列本质还是一个链表，不过是多了一个尾指针。之后就要考虑去实现了，关于参数的传出你可以用返回值或者函数参数的值传递。我觉得考虑这些跟如何设计结构体是有些关系的。我这里依旧使用了头插法，可能是习惯了，依旧用了头插的特性，插入后的值会是倒序，所以我就把插入的值用tail指针指着，这里从逻辑上讲有点相悖，也就是说我这种代码的可读性不会太高。因为在存储上讲它其实是头指针，而结合了队列去讲却成了尾指针。我之后说的都是结合队列来讲的，这里的头指针指向第一个入队的元素，出队操作写的就有些复杂了。其实我也考虑了尾插法因为尾巴插入在实现上是O(n)，入队和出队，在逻辑上讲解的话会比较容易明白。我的头插在入队时是O(1)，但在出队时是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
# coding:utf-8

class Q:
	def __init__(self):
		self.m = 65536
		self.l = []	
		self.tail = 0
		self.head = 0
	def enqueue(self, key):
		#损失一个存储空间,队列为满的情况
		if(((self.tail + 1) % self.m) == self.head):
			return None

		self.l.append(key)	
		self.tail = (self.tail + 1) % self.m

	def dequeue(self):
		if(self.tail == self.head):
			return None

		tmp = self.l[self.head]
		self.head = (self.head + 1) % self.m
		return tmp

def test():
	q = Q()	
	q.enqueue(1)
	q.enqueue(2)
	q.enqueue(3)
	q.enqueue(4)
	a = [1, 2, 3, 4]
	f = 1
	for i in a:
		if(i != q.dequeue()):
			f = 0
			break
	if(f == 1):
		print("passed")
	else:
		print("failed")

test()

写的是循环队列，损失一个存储空间的，我觉得这种写法是挺高效的，如果用标记去做也可以，但是觉得会增加多次判断，还不如损失一个空间来的实在，这里处理循环队列的主要方法是通过取余操作。
终于把线性结构总结完了，需要加快速度了，后面还有SQL和一些其他的琐碎东西到总结，不过线性结构是其他结构的基础。

非线性

树
树也是经典的数据结构，计算机里的树和现实生活中的树在结构上刚好相反，现实生活中，树的根是在土壤中，而计算机中的树的根是在天空上的，因此他们通常在解释树结构的时候会说成是一棵倒树。树可以推广到森林，但大部分情况下我们讨论的树是二叉树，当然森林也可以通过一些操作转为二叉树。二叉树就是说一棵树中每个节点只有0到2至亲个节点，通常把这些节点叫做父节点、左孩子、右孩子。
关于二叉树的一些性质：1. 二叉树的第i层最多有2^(i - 1)个节点。2. 深度为k的二叉树最多有2^k - 1个节点。3. 叶子节点为n0个，有两个孩子的节点为n2个，那么n0 = n2 + 1。4. 具有n个节点的完全二叉树的深度为lgn + 1，结果向下取整。接着来说说树的应用，现在想起来的是哈夫曼，也就是常用的压缩算法。然而我觉得在树上厉害的其实是这个数据结构，比如下面介绍的红黑树或者B树，通常是在树的这个结构上做一些限定性条件，之后会觉得在树上算法就稍微逊色了一点，要不就是树上的算法太厉害了，我这个级别的还没碰到关于在树上做算法文章的。
接着就来讨论一下树的实现，当然树也可以通过数组来实现，比如常用的堆就是通过数组来实现的，我当时也写过一个最小堆的树，不过我用的是兄弟孩子法。兄弟孩子法是链式存储，也就是一个节点有3个指针域，分别是左孩子、右孩子和父亲。其实关于树的创建上我是使用的比较少的，我记得之前写过一次树的创建，但是还得要求输入的次序好像还是前序什么的，记得不太清楚了，后来写了一个哈夫曼编码，当时用了最小堆，不过在最小堆结构和树的链式结构上没有抉择好，当时是浪费了好多存储空间。本来是想写压缩算法的，写到一半就放在那了。所以我认为树的创建应该有具体的应用场景，当然在这里我也得再重新温故一遍孩子兄弟法。

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
#include<stdio.h>
#include<stdlib.h>
typedef struct t
{
	int key;
	struct t *right;
	struct t *left;
}T;
void creat(T **t)
{
	int k;
	scanf("%c", &k);
	if(k == '#')
		*t = NULL;
	else
	{
		*t = (T*)malloc(sizeof(T));
		(*t)->key = k;
		creat(&(*t)->left);
		creat(&(*t)->right);
	}
}
void pre(T *root)
{
	if(root != NULL)
	{
		printf("%c ", root->key);
		pre(root->left);
		pre(root->right);
	}
}
int main()
{
	T *t = NULL;
	creat(&t);
	pre(t);
	puts("");
	return 0;
}

查阅了相关创建的二叉树的方法，有好几种，但我看着都没有什么意义。我写的这种是根据前序遍历来进行创建的，在输入的时候要将空指针输入成特殊的字符。比如一个二叉树的前序是abcd，那么它的形状是ab##cd###。也就是说在创建的时候要按照ab##cd###这样的输入。在C中又发现一个ub问题，%d是接受不了字符的，%d接受那些非数字外的其他字符都会输出1。
堆
红黑树
B树
图

算法

方法论

暴力
回溯
分治
减治
动态规划
贪心

排序和查找

归并
快速
哈希(散列)

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

本来以为<br>如果再活一次的话<br>也许会有什么不一样<br><br>结果<br>还是差不多<br>没有什么不同<br>只是突然觉得<br>再活一次的话<br>好像，真的没有必要