链表 Linked List
链表分为单向链表和双向链表。以单向链表为例，链表由一系列节点组成，链表中的每一节点（Node）包含该节点的值以及它的下一个节点的指向。
单向链表：
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
| public class ListNode<T>
{
public T Data { get; set; }
public ListNode<T>? Next { get; set; }
public ListNode(T data)
{
Data = data;
Next = null;
}
}
public class LinkedList<T>
{
private int _count;
public int Count { get { return _count; } }
private ListNode<T>? _head, _tail;
public ListNode<T>? Head { get { return _head; } }
public ListNode<T>? Tail { get { return _tail; } }
public LinkedList()
{
_count = 0;
_head = null;
_tail = null;
}
public bool IsEmpty()
{
return (_count == 0);
}
public ListNode<T> GetAt(int index)
{
if ((index >= 0) && (index <= _count - 1))
{
if (index == 0)
{
return _head;
}
if (index == _count - 1)
{
return _tail;
}
ListNode<T> currentNode = _head;
for (int i = 0; i < index; i++)
{
currentNode = currentNode.Next;
}
return currentNode;
}
else
{
throw new IndexOutOfRangeException();
}
}
public void Append(T data)
{
ListNode<T> newNode = new ListNode<T>(data);
if (IsEmpty())
{
_head = newNode;
_tail = newNode;
}
else
{
_tail.Next = newNode;
_tail = newNode;
}
_count++;
}
public void Prepend(T data)
{
ListNode<T> newNode = new ListNode<T>(data);
if (IsEmpty())
{
_head = newNode;
_tail = newNode;
}
else
{
newNode.Next = _head;
_head = newNode;
}
_count++;
}
public void InsertAt(T data, int index)
{
if ((index >= 0) && (index <= _count))
{
if (index == 0)
{
Prepend(data);
}
else if (index == _count)
{
Append(data);
}
else
{
ListNode<T> newNode = new ListNode<T>(data);
ListNode<T> currentNode = GetAt(index - 1);
newNode.Next = currentNode.Next;
currentNode.Next = newNode;
_count++;
}
}
else
{
throw new IndexOutOfRangeException();
}
}
public void RemoveAt(int index)
{
if ((index >= 0) && (index <= _count - 1))
{
if (index == 0)
{
_head = _head.Next;
}
else if (index == _count - 1)
{
ListNode<T> newTail = GetAt(_count - 2);
newTail.Next = null;
_tail = newTail;
}
else
{
ListNode<T> currentNode = GetAt(index - 1);
currentNode.Next = currentNode.Next.Next;
}
_count--;
}
else
{
throw new IndexOutOfRangeException();
}
}
public void Clear()
{
_head = null;
_tail = null;
_count = 0;
}
}
|
可视化
栈 Stack 和队列 Queue
这是两种限定性的线性表结构。栈，先进后出。队列，先进先出。
栈：
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
| public class Stack<T>
{
private T[] _collection;
private int _index;
public int Count { get { return _index + 1; } }
public Stack(int size)
{
if (size < 1)
{
throw new ArgumentOutOfRangeException();
}
_collection = new T[size];
_index = -1;
}
public bool IsEmpty()
{
return (_index == -1);
}
public T? Peek()
{
if (_index == -1)
{
return default(T);
}
else
{
return _collection[_index];
}
}
public void Push(T item)
{
_index++;
_collection[_index] = item;
}
public T? Pop()
{
if (_index == -1)
{
return default(T);
}
else
{
_index--;
return _collection[_index + 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
| public class Queue<T>
{
private T[] _collection;
private int _head, _tail, _count;
public int Count { get { return _count; } }
public Queue(int size)
{
if (size < 1)
{
throw new ArgumentOutOfRangeException();
}
_collection = new T[size];
_head = 0;
_tail = 0;
_count = 0;
}
public bool IsEmpty()
{
return (_count == 0);
}
public T? Peek()
{
if (_count == 0)
{
return default(T);
}
else
{
return _collection[_head];
}
}
public void Enqueue(T item)
{
if (_tail == _collection.Length)
{
_resize(_collection.Length * 2);
}
_collection[_tail] = item;
_tail++;
_count++;
}
public T? Dequeue()
{
if (_count == 0)
{
return default(T);
}
else
{
T item = _collection[_head];
_collection[_head] = default(T);
_head++;
_count--;
if (_count < _collection.Length / 2)
{
_resize(_collection.Length / 2);
}
return item;
}
}
private void _resize(int newSize)
{
T[] tempCollection = new T[newSize];
Array.Copy(_collection, _head, tempCollection, 0, _count);
_collection = tempCollection;
_head = 0;
_tail = _count;
}
}
|
可视化
树 Tree
二叉搜索树（BST）是满足了下列条件的二叉树：
左子树上所有结点的值均小于它的根结点的值
右子树上所有结点的值均大于它的根结点的值
自平衡二叉查找树（AVL 树）是带了自平衡功能的二叉搜索树。当结点数量为 N 时，它能够使高度平衡为 O(log N)。不平衡的情况被树旋转（Tree Rotation）所解决。
AVL 树：
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
| public class AVLTreeNode<T> where T : IComparable<T>
{
public int Height { get; set; }
public AVLTreeNode<T>? LeftChild { get; set; }
public AVLTreeNode<T>? RightChild { get; set; }
public T Value { get; set; }
public AVLTreeNode(T value) : this(value, 0, null, null) { }
public AVLTreeNode(T value, int height, AVLTreeNode<T>? leftChild, AVLTreeNode<T>? rightChild)
{
Value = value;
Height = height;
LeftChild = leftChild;
RightChild = rightChild;
}
public void CalcHeight()
{
int leftHight = -1;
int rightHight = -1;
if (LeftChild != null) leftHight = LeftChild.Height;
if (RightChild != null) rightHight = RightChild.Height;
Height = Math.Max(leftHight, rightHight) + 1;
}
public int GetBalanceFactor()
{
int leftHight = -1;
int rightHight = -1;
if (LeftChild != null) leftHight = LeftChild.Height;
if (RightChild != null) rightHight = RightChild.Height;
return leftHight - rightHight;
}
}
public class AVLTree<T> where T : IComparable<T>
{
private AVLTreeNode<T>? _root;
private int _count;
public int Count { get { return _count; } }
public AVLTree()
{
_root = null;
_count = 0;
}
private AVLTreeNode<T> _insert(AVLTreeNode<T> currentNode, T value)
{
if (currentNode.Value.CompareTo(value) > 0)
{
if (currentNode.LeftChild != null)
{
currentNode.LeftChild = _insert(currentNode.LeftChild, value);
}
else
{
currentNode.LeftChild = new AVLTreeNode<T>(value);
_count++;
}
}
else if (currentNode.Value.CompareTo(value) < 0)
{
if (currentNode.RightChild != null)
{
currentNode.RightChild = _insert(currentNode.RightChild, value);
}
else
{
currentNode.RightChild = new AVLTreeNode<T>(value);
_count++;
}
}
else
{
return currentNode;
}
_rebalance(ref currentNode);
return currentNode;
}
private void _rebalance(ref AVLTreeNode<T> currentNode)
{
if (currentNode.GetBalanceFactor() >= 2)
{
if (currentNode.LeftChild != null)
{
if (currentNode.LeftChild.GetBalanceFactor() <= -1)
{
currentNode.LeftChild = _leftRotation(currentNode.LeftChild);
}
}
currentNode = _rightRotation(currentNode);
}
else if (currentNode.GetBalanceFactor() <= -2)
{
if (currentNode.RightChild != null)
{
if (currentNode.RightChild.GetBalanceFactor() >= 1)
{
currentNode.RightChild = _rightRotation(currentNode.RightChild);
}
}
currentNode = _leftRotation(currentNode);
}
currentNode.CalcHeight();
}
private AVLTreeNode<T> _leftRotation(AVLTreeNode<T> currentNode)
{
if (currentNode.RightChild != null)
{
AVLTreeNode<T> newNode = currentNode.RightChild;
currentNode.RightChild = newNode.LeftChild;
newNode.LeftChild = currentNode;
currentNode.CalcHeight();
newNode.CalcHeight();
return newNode;
}
else
{
return currentNode;
}
}
private AVLTreeNode<T> _rightRotation(AVLTreeNode<T> currentNode)
{
if (currentNode.LeftChild != null)
{
AVLTreeNode<T> newNode = currentNode.LeftChild;
currentNode.LeftChild = newNode.RightChild;
newNode.RightChild = currentNode;
currentNode.CalcHeight();
newNode.CalcHeight();
return newNode;
}
else
{
return currentNode;
}
}
public void Insert(T value)
{
if (_root == null)
{
_root = new AVLTreeNode<T>(value);
_count++;
}
else
{
_root = _insert(_root, value);
}
}
public bool Contains(T value)
{
AVLTreeNode<T>? currentNode = _root;
while (currentNode != null)
{
if (currentNode.Value.CompareTo(value) == 0)
{
return true;
}
else if (currentNode.Value.CompareTo(value) > 0)
{
currentNode = currentNode.LeftChild;
}
else
{
currentNode = currentNode.RightChild;
}
}
return false;
}
}
|
删除好麻烦不写了😭
可视化
堆 Heap
二叉堆，是完全二叉树。
二叉最大堆：
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
| public class Heap<T> where T : IComparable<T>
{
private T[] _collection;
private int _count;
public int Count { get { return _count; } }
public Heap(int size)
{
_collection = new T[size];
_count = 0;
}
public bool IsEmpty()
{
return _count == 0;
}
private void _swap(int index1, int index2)
{
T tempItem = _collection[index1];
_collection[index1] = _collection[index2];
_collection[index2] = tempItem;
}
private void _bubbleUp(int index)
{
while (index > 0)
{
if (_collection[index].CompareTo(_collection[(index - 1) / 2]) > 0)
{
_swap(index, (index - 1) / 2);
}
index = (index - 1) / 2;
}
}
private void _bubbleDown(int index)
{
int maxIndex;
while ((index * 2 + 1) < _count)
{
maxIndex = index * 2 + 1;
if (((index * 2 + 2) < _count) && (_collection[index * 2 + 2].CompareTo(_collection[index * 2 + 1]) > 0))
{
maxIndex = index * 2 + 2;
}
if (_collection[maxIndex].CompareTo(_collection[index]) > 0)
{
_swap(maxIndex, index);
index = maxIndex;
}
else
{
break;
}
}
}
public void Insert(T item)
{
_collection[_count] = item;
_bubbleUp(_count);
_count++;
}
public T? Peek()
{
if (_count == 0)
{
return default(T);
}
else
{
return _collection[0];
}
}
public T? ExtractMax()
{
if (_count == 0)
{
return default(T);
}
else
{
_swap(0, _count - 1);
_count--;
_bubbleDown(0);
return _collection[_count];
}
}
}
|
可视化
部分代码借鉴自
GitHub - aalhour/C-Sharp-Algorithms: Plug-and-play class-library project of standard Data Structures and Algorithms in C#
另见
System.Collections.Generic 命名空间 | Microsoft Docs
wechat
alipay
