数据结构学习(用c语言实现)_数据结构教程在生活如何使用程序实现应用c语言

1. 数据结构

1.1 数据结构与算法

数据结构

数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

算法

算法(Algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

2. 算法的时间复杂度和空间复杂度

2.1 算法的复杂度

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

2.2 时间复杂度

2.2.1 时间复杂度概念

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。

// 请计算一下Func1中++count语句总共执行了多少次？
void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N ; ++ i)
	{
		for (int j = 0; j < N ; ++ j)
		{
			++count;
		}
	}

	for (int k = 0; k < 2 * N ; ++ k)
	{
		++count;
	}

	int M = 10;
	while (M--)
	{
		++count;
	}

	printf("%d\n", count);
}
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

Func1 执行的基本操作次数 ：
$$F(N)=N^2+2\ast N+10$$

• N = 10 F(N) = 130
• N = 100 F(N) = 10210
• N = 1000 F(N) = 1002010

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。

2.2.2 大O的渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

使用大O的渐进表示法以后，Func1的时间复杂度为：
$$O(N^2)$$

• N = 10 F(N) = 100
• N = 100 F(N) = 10000
• N = 1000 F(N) = 1000000

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。

另外有些算法的时间复杂度存在最好、平均和最坏情况：

​ 最坏情况：任意输入规模的最大运行次数(上界)

​ 平均情况：任意输入规模的期望运行次数

​ 最好情况：任意输入规模的最小运行次数(下界)

例如：在一个长度为N数组中搜索一个数据x

​ 最好情况：1次找到

​ 最坏情况：N次找到

​ 平均情况：N/2次找到

在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

2.2.3 常见时间复杂度计算举例

实例1：

// 计算Func2的时间复杂度？
void Func2(int N)
{
	int count = 0;
	for (int k = 0; k < 2 * N ; ++ k)
	{
		++count;
	}

	int M = 10;
	while (M--)
	{
		++count;
	}

	printf("%d\n", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

实例2:

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
	int count = 0;
	for (int k = 0; k < M; ++ k)
	{
		++count;
	}

	for (int k = 0; k < N ; ++ k)
	{
		++count;
	}
	printf("%d\n", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

实例3:

// 计算Func4的时间复杂度？
void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++ k)
	{
		++count;
	}
	printf("%d\n", count);
}
1
2
3
4
5
6
7
8
9
10

实例4:

// 计算strchr的时间复杂度？
const char * strchr ( const char * str, int character );
1
2

实例5:

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i-1] > a[i])
			{
				Swap(&a[i-1], &a[i]);
				exchange = 1;
			}
		}

		if (exchange == 0)
			break;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

实例6:

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
	assert(a);

	int begin = 0;
	int end = n-1;
 // [begin, end]：begin和end是左闭右闭区间，因此有=号
	while (begin <= end)
	{
		int mid = begin + ((end-begin)>>1);
		if (a[mid] < x)
			begin = mid+1;
		else if (a[mid] > x)
			end = mid-1;
		else
			return mid;
	}

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

实例7:

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
 if(0 == N)
     return 1;

 return Fac(N-1)*N;
}
1
2
3
4
5
6
7
8

实例8:

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
 if(N < 3)
     return 1;

 return Fib(N-1) + Fib(N-2);
}
1
2
3
4
5
6
7
8

实例答案及分析：

1. 实例1基本操作执行了2N+10次，通过推导大O阶方法知道，时间复杂度为 O(N)
2. 实例2基本操作执行了M+N次，有两个未知数M和N，时间复杂度为 O(N+M)
3. 实例3基本操作执行了10次，通过推导大O阶方法，时间复杂度为 O(1)
4. 实例4基本操作执行最好1次，最坏N次，时间复杂度一般看最坏，时间复杂度为 O(N)
5. 实例5基本操作执行最好N次，最坏执行了(N*(N+1)/2次，通过推导大O阶方法+时间复杂度一般看最坏，时间复杂度为 O(N^2)
6. 实例6基本操作执行最好1次，最坏O(logN)次，时间复杂度为 O(logN) ps：logN在算法分析中表示是底数为2，对数为N。有些地方会写成lgN。（建议通过折纸查找的方式讲解logN是怎么计算出来的）
7. 实例7通过计算分析发现基本操作递归了N次，时间复杂度为O(N)。
8. 实例8通过计算分析发现基本操作递归了2^N次，时间复杂度为O(2^N)。

2.3 空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。

空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

实例1：

// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i-1] > a[i])
			{
				Swap(&a[i-1], &a[i]);
				exchange = 1;
			}
		}

		if (exchange == 0)
			break;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

实例2：

// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
 if(n==0)
      return NULL;

 long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
 fibArray[0] = 0;
 fibArray[1] = 1;
 for (int i = 2; i <= n ; ++i)
 {
     fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
 }

 return fibArray;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

实例3：

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
 if(N == 0)
     return 1;

	return Fac(N-1)*N;
}
1
2
3
4
5
6
7
8

实例答案及分析：

1. 实例1使用了常数个额外空间，所以空间复杂度为 O(1)
2. 实例2动态开辟了N个空间，空间复杂度为 O(N)
3. 实例3递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)

2.4 常见复杂度对比

一般算法常见的复杂度如下：

3. 线性表

3.1 线性表

线性表*（linear list）*是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

3.2 顺序表

3.2.1 概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素。
2. 动态顺序表：使用动态开辟的数组存储。

3.2.2 顺序表的实现

// sequence_list.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;

// 顺序表的动态存储
typedef struct SeqList
{
	SLDataType* array;  // 指向动态开辟的数组
	size_t size;       // 有效数据个数
	size_t capacity;   // 容量空间的大小
}SeqList;

// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl);
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);
// 顺序表修改
void SeqListModify(SeqList* psl, int pos, SLDataType x);
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

// sequence_list.c
#include"sequence_list.h"

// 顺序表初始化
void SeqListInit(SeqList* psl)
{
	assert(psl);
	psl->capacity = 4;
	psl->array = (SLDataType*)malloc(sizeof(SLDataType) * psl->capacity);
	if (psl->array == NULL)
	{
		perror("malloc fail");
		return;
	}
	psl->size = 0;
}
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl)
{
	assert(psl);
	if (psl->capacity == psl->size)
	{
		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		psl->capacity = newcapacity;
		SLDataType* tmp = (SLDataType*)realloc(psl->array,sizeof(SLDataType) * psl->capacity);
		if (tmp == NULL)
		{
			perror("malloc fail");
			return;
		}
		psl->array = tmp;
	}
}
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);
	SeqListInsert(psl, psl->size, x);
}
// 顺序表尾删
void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	SeqListErase(psl, psl->size - 1);
}
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);
	SeqListInsert(psl, 0, x);
}
// 顺序表头删
void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	SeqListErase(psl, 0);
}
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl);
	for (int i = 0; i <psl->size ; i++)
	{
		if (psl->array[i]==x)
		{
			return i;
		}
	}
	return -1;
}
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(0 <= pos && pos <= psl->size);
	CheckCapacity(psl);
	for (int i = psl->size; i >pos; i--)
	{
		psl->array[i] = psl->array[i -1];
	}
	psl->array[pos] = x;
	psl->size++;
}
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(0 <= pos && pos <= psl->size);
	for (int i = pos; i <psl->size-1 ; i++)
	{
		psl->array[i] = psl->array[i + 1];
	}
	psl->size--;
}
// 顺序表销毁
void SeqListDestory(SeqList* psl)
{
	assert(psl);
	free(psl->array);
	psl->array = NULL;
	psl->capacity = 0;
	psl->size = 0;
}
// 顺序表打印
void SeqListPrint(SeqList* psl)
{
	assert(psl);
	printf("size:%zu\n",psl->size);
	printf("capacity:%zu\n", psl->capacity);
	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->array[i]);
	}
	printf("\n");
}
// 顺序表修改
void SeqListModify(SeqList* psl, int pos, SLDataType x)
{
	assert(psl);
	assert(0 <= pos && pos < psl->size);
	psl->array[pos] = x;
}
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

3.2.3 顺序表的问题及思考

1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

3.3 链表

3.3.1 链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

3.3.2 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

3.3.3 单向链表的实现

无头+单向+非循环链表增删查改实现

//linked_list.h
#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

// 动态申请一个结点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表在pos位置之后删除
void SListEraseAfter(SListNode* pos);
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

//linked_list.c
#include"linked_list.h"

// 动态申请一个结点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newNode->data = x;
	newNode->next = NULL;
	return newNode;
}
// 单链表打印
void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newNode = BuySListNode(x);
	newNode->next = NULL;
	if (*pplist == NULL)
	{
		*pplist = newNode;
		return;
	}
	SListNode* cur = *pplist;
	SListNode* next = cur->next;
	while (next)
	{
		cur = next;
		next = cur->next;
	}
	cur->next = newNode;
}
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newNode = BuySListNode(x);
	newNode->next = *pplist;
	*pplist = newNode;
}
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);
	SListNode* prev = NULL;
	SListNode* cur = *pplist;
	SListNode* next = cur->next;
	while (next)
	{
		prev = cur;
		cur = next;
		next = next->next;
	}
	free(cur);
	if (prev!=NULL)
	{
		prev->next = NULL;
	}
	else
	{
		*pplist = NULL;
	}
}
// 单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);
	SListNode* cur = *pplist;
	SListNode* next = cur->next;
	free(cur);
	if (next != NULL)
	{
		*pplist = next;
	}
	else
	{
		*pplist = NULL;
	}
}
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{

	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newNode = BuySListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}
// 单链表在pos位置之后删除
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	SListNode* next = pos->next;
	pos->next = next->next;
	free(next);
}
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

###3.3.4 双向链表的实现

带头+双向+循环链表增删查改实现

//doubly_linked_list.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;

LTNode* LTInit();
void LTPrint(LTNode* phead);

bool LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);

LTNode* LTFind(LTNode* phead, LTDataType x);

// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x);
// 删除pos位置的值
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);
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

//doubly_linked_list.c
#include "doubly_linked_list.h"

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}
LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
void LTPrint(LTNode* phead)
{
	assert(phead);
	if (LTEmpty(phead))
	{
		printf("sentinel\n");
	}
	else
	{
		printf("sentinel<==>");
		LTNode* cur = phead;
		while (cur->next != phead)
		{
			cur = cur->next;
			printf("%d<==>", cur->data);
		}
		printf("\n");
	}
}
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	
	return phead->next == phead;
}
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	/*LTNode* newNode = BuyLTNode(x);
	LTNode* prevNode = phead->prev;
	prevNode->next = newNode;
	newNode->prev = prevNode;
	newNode->next = phead;
	phead->prev = newNode;*/
	LTInsert(phead, x);
}
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	/*LTNode* newNode = BuyLTNode(x);
	LTNode* nextNode = phead->next;
	phead->next = newNode;
	newNode->prev = phead;
	newNode->next = nextNode;
	nextNode->prev = newNode;*/
	LTInsert(phead->next, x);
}
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	/*LTNode* prevNode = phead->prev->prev;
	free(phead->prev);
	prevNode->next = phead;
	phead->prev = prevNode;*/
	LTErase(phead->prev);
}
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	/*LTNode* nextNode = phead->next->next;
	free(phead->next);
	phead->next = nextNode;
	nextNode->prev = phead;*/
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead;
	while (cur->next != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newNode = BuyLTNode(x);
	LTNode* prevNode = pos->prev;
	prevNode->next = newNode;
	newNode->prev = prevNode;
	newNode->next = pos;
	pos->prev = newNode;
}
// 删除pos位置的值
void LTErase(LTNode* pos)
{
	LTNode* prevNode = pos->prev;
	LTNode* nextNode = pos->next;
	free(pos);
	prevNode->next = nextNode;
	nextNode->prev = prevNode;
}
void LTDestroy(LTNode* phead)
{
	LTNode* cur = phead;
	LTNode* next = cur->next;
	while (next!=phead)
	{
		cur = next;
		next = cur->next;
		free(cur);
	}
	free(phead);
}
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

3.4 顺序表和链表的区别

4. 栈

4.1 栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。**进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。**栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

4.2 栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

//stack.h
#pragma once
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<stdio.h>

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);
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

//stack.c
#include"stack.h"

// 初始化栈 
void StackInit(Stack* ps)
{
	assert(ps);
	ps->top = 0;
	ps->capacity = 0;
	ps->a = NULL;
}
// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType)*newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = data;
	ps->top++;
}
// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}
// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}
// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	if (ps->top == 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
// 销毁栈 
void StackDestroy(Stack* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
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

5. 队列

5.1 队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

5.2 队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

//queue.h
#pragma once
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<stdio.h>

typedef int QDataType;

// 链式结构：表示队列 
typedef struct QListNode
{
	struct QListNode* pNext;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;
	QNode* rear;
	int size;
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);
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

//queue.c
#include"queue.h"
// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newNode->data = data;
	newNode->pNext = NULL;
	if (QueueEmpty(q))
	{
		q->front = newNode;
		q->rear = newNode;
	}
	else
	{
		q->rear->pNext = newNode;
		q->rear = newNode;
	}
	q->size++;
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	QNode* Node = q->front;
	if (q->front->pNext == NULL)
	{
		assert(q->rear->pNext == NULL);
		q->front = NULL;
	}
	else
	{
		q->front = q->front->pNext;
	}
	free(Node);
	q->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->front->data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->rear->data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	QNode* cur = q->front;
	while (cur)
	{
		QNode* next = cur->pNext;
		free(cur);
		cur = next;
	}
}
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

6. 二叉树

6.1 树的概念和结构

6.1.1 树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

• 有一个特殊的结点，称为根结点，根结点没有前驱结点
• 除根结点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
• 因此，树是递归定义的。

注意：树形结构中，子树之间不能有交集，否则就不是树形结构

6.1.2 树的相关概念

结点的度：一个结点含有的子树的个数称为该结点的度； 如上图：A的为6

叶结点或终端结点：度为0的结点称为叶结点； 如上图：B、C、H、I…等结点为叶结点

非终端结点或分支结点：度不为0的结点； 如上图：D、E、F、G…等结点为分支结点

双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点

孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点

兄弟结点：具有相同父结点的结点互称为兄弟结点； 如上图：B、C是兄弟结点

树的度：一棵树中，最大的结点的度称为树的度； 如上图：树的度为6

结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；

树的高度或深度：树中结点的最大层次； 如上图：树的高度为4

堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：H、I互为兄弟结点

结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先

子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙

森林：由m（m>0）棵互不相交的树的集合称为森林；

6.1.3 树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

typedef int DataType;
struct Node
{
 struct Node* firstChild1;    // 第一个孩子结点
 struct Node* pNextBrother;   // 指向其下一个兄弟结点
 DataType data;               // 结点中的数据域
};
1
2
3
4
5
6
7

6.1.4 树在实际中的运用（表示文件系统的目录树结构）

6.2 二叉树的概念及结构

6.2.1 概念

一棵二叉树是结点的一个有限集合，该集合:

1. 或者为空
2. 由一个根结点加上两棵别称为左子树和右子树的二叉树组成

从上图可以看出：

1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的：

6.2.2 特殊的二叉树

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是$2^k-1$ ，则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

6.2.3 二叉树的性质

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有$2^{(i-1)}$ 个结点.
2. 若规定根结点的层数为1，则深度为h的二叉树的最大结点数是$2^h-1$.
3. 对任何一棵二叉树, 如果度为0其叶结点个数为 $n_0$, 度为2的分支结点个数为 $n_2$,则有$n_0$＝$n_2$＋1
4. 若规定根结点的层数为1，具有n个结点的满二叉树的深度，h=$lo{g}_2(n+1)$. (ps：$lo{g}_2(n+1)$是log以2为底，n+1为对数)
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从0开始编号，则对于序号为i的结点有：
   1. 若i>0，i位置结点的双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
   2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
   3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

6.2.4 二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

1. 顺序存储

   顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

   

2. 链式存储

   二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链。

   

   

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
    struct BinTreeNode* left;   // 指向当前结点左孩子
    struct BinTreeNode* right;  // 指向当前结点右孩子
    BTDataType data;            // 当前结点值域
}

// 三叉链
struct BinaryTreeNode
{
    struct BinTreeNode* parent; // 指向当前结点的双亲
    struct BinTreeNode* left;   // 指向当前结点左孩子
    struct BinTreeNode* right;  // 指向当前结点右孩子
    BTDataType data;            // 当前结点值域
}；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

6.3 二叉树的顺序结构及实现

6.3.1 二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

6.3.2 堆的概念及结构

如果有一个关键码的集合K = {$k_0$，$k_1$， $k_2$，…，$k_{n-1}$}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：$K_i$ <= $K_{2\ast i+1}$ 且 $K_i$<= $K_{2\ast i+2}$ ($K_i$ >= $K_{2\ast i+1}$ 且 $K_i$ >= $K_{2\ast i+2}$) i = 0，1，2…，则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

堆的性质：

• 堆中某个结点的值总是不大于或不小于其父结点的值；
• 堆总是一棵完全二叉树。

6.3.3 堆的实现

6.3.3.1 堆的向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};
1

6.3.3.2 堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根结点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子结点的子树开始调整，一直调整到根结点的树，就可以调整成堆。

int a[] = {1,5,3,8,7,6}; 
1

6.3.3.3 建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个结点不影响最终结果)：

因此：建堆的时间复杂度为O(N)。

6.3.3.4 堆的插入

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

6.3.3.5 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

6.3.3.6 堆的代码实现

//heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;
	int _size;
	int _capacity;
}Heap;

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n); 
// 堆的初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestroy(Heap* hp);
// 向上调整算法
void AdjustUp(HPDataType* a, int child);
// 向下调整算法
void AdjustDown(HPDataType* a, int n, int parent);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
// 堆的扩容
void CheckCapacity(Heap* hp);
// TopK
void PrintTopK(int* a, int n, int k);
// 堆排序
void HeapSort(int* a, int 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

//heap.c

#include "heap.h"

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp && a);
	hp->_a = (HPDataType*)malloc(sizeof(HPDataType)*n);
	if (hp->_a == NULL)
	{
		perror("malloc fail");
		return;
	}
	hp->_capacity = n;
	hp->_size = n;

	for (int i = 0; i < n; i++)
	{
		hp->_a[i] = a[i];
	}

	for (int i = (n-1-1)/2; i >=0 ; i--)
	{
		AdjustDown(hp->_a, hp->_size, i);
	}
}
// 堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->_a = NULL;
	hp->_capacity = 0;
	hp->_size = 0;
}
// 堆的销毁
void HeapDestroy(Heap* hp)
{
	assert(hp);
	free(hp->_a);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
// 向上调整算法
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}	
// 向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child+1<n && a[child] > a[child + 1])
		{
			child = child + 1;
		}
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent*2+1;
		}
		else
		{
			break;
		}
	}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	CheckCapacity(hp);
	hp->_a[hp->_size] = x;
	AdjustUp(hp->_a, hp->_size);
	hp->_size++;
}
// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	hp->_size--;
	Swap(&hp->_a[0], &hp->_a[hp->_size]);
	AdjustDown(hp->_a, hp->_size, 0);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	return hp->_a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->_size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
	return hp->_size == 0;
}
// 堆的扩容
void CheckCapacity(Heap*hp)
{
	assert(hp);
	if (hp->_capacity == hp->_size)
	{
		int newCapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->_a, newCapacity*sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		hp->_a = tmp;
		hp->_capacity = newCapacity;
	}
}
// TopK
void PrintTopK(int* a, int n, int k)
{
	// 1. 建堆--用a中前k个元素建堆
	Heap hp1;
	HeapInit(&hp1);
	HeapCreate(&hp1, a, k);
	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则替换
	for (int i = k; i < n; i++)
	{
		if (a[i] > hp1._a[0])
		{
			hp1._a[0] = a[i];
		}
		AdjustDown(hp1._a, k, 0);
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", hp1._a[i]);
	}
	printf("\n");
}
// 堆排序
void HeapSort(int* a, int n)
{
	for (int i = (n-1-1)/2; i >=0 ; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179

6.3.4 堆的应用

6.3.4.1 堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆
   • 升序：建大堆
   • 降序：建小堆
2. 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

6.3.4.2 TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆
   • 前k个最大的元素，则建小堆
   • 前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

void PrintTopK(int* a, int n, int k)
{
	// 1. 建堆--用a中前k个元素建堆
	Heap hp1;
	HeapInit(&hp1);
	HeapCreate(&hp1, a, k);
	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则替换
	for (int i = k; i < n; i++)
	{
		if (a[i] > hp1._a[0])
		{
			hp1._a[0] = a[i];
		}
		AdjustDown(hp1._a, k, 0);
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", hp1._a[i]);
	}
	printf("\n");
}

void TestTopk()
{
	int n = 10000;
	int* a = (int*)malloc(sizeof(int)*n);
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
    PrintTopK(a, n, 10);
}
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

6.4 二叉树链式结构的实现

6.4.1 二叉树的概念

二叉树是：

1. 空树
2. 非空：根结点，根结点的左子树、根结点的右子树组成的。

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
BTNode* CreatBinaryTree()
{
 BTNode* node1 = BuyNode(1);
 BTNode* node2 = BuyNode(2);
 BTNode* node3 = BuyNode(3);
 BTNode* node4 = BuyNode(4);
 BTNode* node5 = BuyNode(5);
 BTNode* node6 = BuyNode(6);

 node1->_left = node2;
 node1->_right = node4;
 node2->_left = node3;
 node4->_left = node5;
 node4->_right = node6;
 return node1;
}
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

从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。

6.4.2 二叉树的遍历

6.4.2.1 前序、中序以及后序遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的结点进行相应的操作，并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

6.4.2.2 层序遍历

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根结点所在层数为1，层序遍历就是从所在二叉树的根结点出发，首先访问第一层的树根结点，然后从左到右访问第2层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

6.4.3 节点的个数以及高度等

6.4.4 二叉树的创建和销毁

//binary_tree.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x);
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a,int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode * root); 
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

//binary_tree.c

#include "binary_tree.h"
#include "queue.h"

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a,int* pi)
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* node = BuyNode(a[*pi]);
	(*pi)++;
	node->left = BinaryTreeCreate(a, pi);
	node->right = BinaryTreeCreate(a, pi);
	return node;
}
// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root==NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (!(root->left || root->right))
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}

	BTNode* ret1 = BinaryTreeFind(root->left, x);
	if (ret1)
	{
		return ret1;
	}
	BTNode* ret2 = BinaryTreeFind(root->right, x);
	if (ret2)
	{
		return ret2;
	}
}
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeInOrder(root->left);
	printf("%d ", root->data);
	BinaryTreeInOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%d ", root->data);
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q,root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* node = QueueFront(&q);
		if (node->left)
		{
			QueuePush(&q, node->left);
		}
		if (node->right)
		{
			QueuePush(&q, node->right);
		}
		printf("%d ", node->data);
		QueuePop(&q);
	}
	printf("\n");
	BinaryTreeDestory(&q);
}
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* node = QueueFront(&q);
		if (node->left)
		{
			QueuePush(&q, node->left);
		}
		else
		{
			break;
		}
		if (node->right)
		{
			QueuePush(&q, node->right);
		}
		else
		{
			break;
		}
		QueuePop(&q);
	}
	if (QueueEmpty(&q))
	{
		QueueDestroy(&q);
		return 1;
	}
	else
	{
		while (!QueueEmpty(&q))
		{
			BTNode* node = QueueFront(&q);
			if (node->left && node->right)
			{
				QueueDestroy(&q);
				return 0;
			}
			QueuePop(&q);
		}
		QueueDestroy(&q);
		return 1;
	}
}
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206

7. 排序

7.1 排序的概念及其运用

7.1.1 排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

7.1.2 常见的排序算法

// 排序实现的接口

// 插入排序
void InsertSort(int* a, int n);

// 希尔排序
void ShellSort(int* a, int n);

// 选择排序
void SelectSort(int* a, int n);

// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);

// 冒泡排序
void BubbleSort(int* a, int n)

// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
void QuickSort(int* a, int left, int right);

// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)

// 归并排序递归实现
void MergeSort(int* a, int n)
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)

// 计数排序
void CountSort(int* a, int n)

// 测试排序的性能对比
void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int)*N);
	int* a2 = (int*)malloc(sizeof(int)*N);
	int* a3 = (int*)malloc(sizeof(int)*N);
	int* a4 = (int*)malloc(sizeof(int)*N);
	int* a5 = (int*)malloc(sizeof(int)*N);
	int* a6 = (int*)malloc(sizeof(int)*N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];

	}

	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	QuickSort(a5, 0, N-1);
	int end5 = clock();

	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
}
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

排序OJ(可使用各种排序跑这个OJ)OJ链接

7.2 常见排序算法的实现

7.2.1 插入排序

####7.2.1.1 基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

7.2.1.2 直接插入排序

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

void InsertSort(int* a, int n)
{
	for (int i = 1; i< n; i++)
	{
		int end = i - 1;
		int tmp = a[i];
		while (end>=0)
		{
			if (a[end]>tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
			a[end + 1] = tmp;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

7.2.1.3 希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：

   《数据结构(C语言版)》— 严蔚敏

《数据结构-用面相对象方法与C++描述》— 殷人昆

因为我们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照：$O(n^{1.25})$ 到 $O(1.6\ast n^{1.25})$来算。

4. 稳定性：不稳定

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap>1)
	{
		gap = gap / 3+1;
		for (int i = 0; i < n-gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end>=0)
			{
				if (a[end]>tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}
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

7.2.2 选择排序

2.2.1基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

2.2.2 直接选择排序:

• 在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素

• 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换

• 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
1
2
3
4

void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n-1;
	while (begin<=end)
	{
		int mini = begin;
		int maxi = begin;
		for (int i = begin; i <= end; i++)
		{
			if (a[mini] > a[i])
			{
				mini = i;
			}
			if (a[maxi]<a[i])
			{
				maxi = i;
			}
		}
		Swap(&a[mini], &a[begin]);
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
}
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

7.2.2.3 堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

直接选择排序的特性总结：

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

7.2.3 外交排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

7.2.3.1 冒泡排序

冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定

void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		bool exchange = false;
		for (int j = 1; j < n-i; j++)
		{
			if (a[j-1]>a[j])
			{
				int tmp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = tmp;
				exchange = true;
			}
		}

		if (exchange==false)
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

7.2.3.2 快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

void QuickSort(int* a, int begin, int end)
{
	if (end-begin<=1)
		return;

	if (end-begin < 10)
	{
		InsertSort(a + begin, end -begin);
	}
	else
	{
		int pivot = PartSort2(a, begin, end);
		QuickSort(a, begin, pivot);
		QuickSort(a, pivot + 1, end);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

将区间按照基准值划分为左右两半部分的常见方式有：

1. hoare版本

int PartSort1(int* a, int begin, int end)
{
	int midindex = GetMidIndex(a, begin, end);
	Swap(&a[begin], &a[midindex]);

	int key = a[begin];
	int left = begin;
	int right = end - 1;
	/*
	这里要从右边走，如果从左边走，
	可能最后一步，如果找不到大于
	基准值的，会导致left == right
	即相遇，但是右边还没有走，所以
	这里的值一定大于基准值，最后交换
	就会出问题，所以一定要从右边走，
	即使最后一次找不到小于基准值的，
	会和左边相遇，而左边此时还没走，
	一定比基准值小，最后交换肯定没有问题
	*/
	while (left < right)
	{
		while (left < right && a[right] >= key)
			right--;

		while (left < right && a[left] <= key)
			left++;

		Swap(&a[left], &a[right]);
	}
	Swap(&a[begin], &a[left]);
	return left;
}
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

2. 挖坑法

int PartSort2(int* a, int begin, int end)
{
	int left = begin;
	int right = end - 1;
	int key = a[begin];
	while (left < right)
	{
		while (left < right && a[right] >= key)
			right--;

		a[left] = a[right];

		while (left < right && a[left] <= key)
			left++;

		a[right] = a[left];
	}
	a[left] = key;
	return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3. 前后指针版本

int PartSort3(int* a, int begin, int end)
{
	int midindex = GetMidIndex(a, begin, end);
	Swap(&a[begin], &a[midindex]);

	int key = a[begin];
	int prev = begin;
	int cur = begin + 1;

	while (cur < end)
	{
		// cur找小，把小的往前翻，大的往后翻
		if (a[cur] < key && ++prev != cur)
			Swap(&a[cur], &a[prev]);

		++cur;
	}

	Swap(&a[begin], &a[prev]);

	return prev;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

7.2.3.3 快速排序优化

1. 三数取中法选key
2. 递归到小的子区间时，可以考虑使用插入排序

int GetMidIndex(int* a, int begin, int end)
{
	int mid = begin + ((end - begin) >> 1);
	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
		{
			return mid;
		}
		else if (a[begin] > a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
	else // begin >= mid
	{
		if (a[mid] > a[end])
		{
			return mid;
		}
		else if (a[begin] < a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
}
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

7.2.3.4 快速排序非递归

void QuickSortNonR(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	Stack st;
	StackInit(&st, 10);
	//先入大区间
	if (left < right)
	{
		StackPush(&st, right);
		StackPush(&st, left);
	}
	//栈不为空，说明还有没处理的区间
	while (!StackEmpty(&st))
	{
		left = StackTop(&st);
		StackPop(&st);
		right = StackTop(&st);
		StackPop(&st);
		//快排单趟排序
		int div = PartSort3(a, left, right);

		// 把大于1个数的区间继续入栈
		if (left < div)
		{
			StackPush(&st, div);
			StackPush(&st, left);
		}

		if (div + 1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, div + 1);
		}
	}
}
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

快速排序的特性总结：

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

2. 时间复杂度：O(N*logN)

   

3. 空间复杂度：O(logN)

4. 稳定性：不稳定

7.2.4 归并排序

基本思想：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序核心步骤：

归并排序的特性总结：

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定

void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)
	{
		return;
	}
	int mid = left + ((right - left) >> 2);
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid+1, right, tmp);
	int l1 = left;
	int r1 = mid;
	int l2 = mid + 1;
	int r2 = right;
	int i = 0;
	while (l1 <= r1 && l2 <= r2)
	{
		if (a[l1] < a[l2])
		{
			tmp[i] = a[l1];
			l1++;
		}
		else
		{
			tmp[i] = a[l2];
			l2++;
		}
		i++;
	}
	while (l1 <= r1)
	{
		tmp[i] = a[l1++];
		i++;
	}
	while (l2 <= r2)
	{
		tmp[i] = a[l2++];
		i++;
	}
	memcpy(a + left, tmp, sizeof(int) * (right - left + 1));
}
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}
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

归并排序非递归

void Merge(int* a, int left, int mid, int right, int* tmp)
{
	int l1 = left;
	int r1 = mid;
	int l2 = mid+1 ;
	int r2 = right;
	int i = 0;
	while (l1 <= r1 && l2 <= r2)
	{
		if (a[l1] < a[l2])
		{
			tmp[i] = a[l1];
			l1++;
		}
		else
		{
			tmp[i] = a[l2];
			l2++;
		}
		i++;
	}
	while (l1 <= r1)
	{
		tmp[i] = a[l1++];
		i++;
	}
	while (l2 <= r2)
	{
		tmp[i] = a[l2++];
		i++;
	}
	memcpy(a + left, tmp, sizeof(int) * (right - left + 1));
}
void MergeSortNonR(int* a, int n)
{
	int k = 1;
	int* tmp = (int*)malloc(sizeof(int) * n);
	while (k < n)
	{
		int i = 0;
		while (i+k-1 < n)
		{
			int left = i;
			int mid = i + k-1;
			int right = mid + k;
			if (right >=n)
			{
				right = n - 1;
			}
			Merge(a, left, mid, right, tmp);
			i += k;
		}
		k *= 2;
	}
	free(tmp);
}
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

7.2.5 非比较排序

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
操作步骤：

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

计数排序的特性总结：

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)
4. 稳定性：稳定

void CountSort(int* a, int n)
{
	int max = a[0], min = a[0];
	for (int i = 0; i < n; ++i)
	{
		if (a[i] > max)
			max = a[i];

		if (a[i] < min)
			min = a[i];
	}
	//找到数据的范围
	int range = max - min + 1;
	int* countArray = (int*)malloc(range * sizeof(int));
	memset(countArray, 0, sizeof(int) * range);
	//存放在相对位置，可以节省空间
	for (int i = 0; i < n; ++i)
	{
		countArray[a[i] - min]++;
	}
	//可能存在重复的数据，有几个存几个
	int index = 0;
	for (int i = 0; i < range; ++i)
	{
		while (countArray[i]--)
		{
			a[index++] = i + min;
		}
	}
}
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

7.3 排序算法复杂度及稳定性分析

8. OJ题

8.1 复杂度OJ题

消失的数字OJ链接：https://leetcode-cn.com/problems/missing-number-lcci/

旋转数组OJ链接：https://leetcode-cn.com/problems/rotate-array/

##8.2 数组OJ题

1. 原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。OJ链接
2. 删除排序数组中的重复项。OJ链接
3. 合并两个有序数组。OJ链接

##8.3 链表OJ题

1. 删除链表中等于给定值 val 的所有结点。 OJ链接

2. 反转一个单链表。 OJ链接

3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。OJ链接

4. 输入一个链表，输出该链表中倒数第k个结点。 OJ链接

5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。OJ链接

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。OJ链接

7. 链表的回文结构。OJ链接

8. 输入两个链表，找出它们的第一个公共结点。OJ链接

9. 给定一个链表，判断链表中是否有环。 OJ链接

   【思路】

   ​ 快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，如果链表

   ​ 带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。

   【扩展问题】

   • 为什么快指针每次走两步，慢指针走一步可以？

     假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

   • 快指针一次走3步，走4步，…n步行吗？

     

10. 给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 NULL OJ链接

    • 结论

      让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。

    • 证明

11. 给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点或空结点。

    要求返回这个链表的深度拷贝。OJ链接

12. 其他 。Leetcode OJ链接](https://leetcode-cn.com/tag/linked-list/) + 牛客 OJ链接

8.4 栈和队列OJ题

1. 括号匹配问题。OJ链接
2. 用队列实现栈。OJ链接
3. 用栈实现队列。OJ链接
4. 设计循环队列。OJ链接

8.5 二叉树OJ题

1. 单值二叉树。OJ链接
2. 检查两颗树是否相同。OJ链接
3. 二叉树最大深度。OJ链接
4. 对称二叉树。OJ链接
5. 翻转二叉树。OJ链接
6. 另一颗树的子树。OJ链接
7. 二叉树的构建及遍历。OJ链接
8. 判断一颗二叉树是否是平衡二叉树。OJ链接