数据结构是为实现对计算机数据有效使用的各种数据组织形式，服务于各类计算机操作。不同的数据结构具有各自对应的适用场景，旨在降低各种算法计算的时间与空间复杂度，达到最佳的任务执行效率。
如下图所示，常见的数据结构可分为「线性数据结构」与「非线性数据结构」，具体为：「数组」、「链表」、「栈」、「队列」、「树」、「图」、「散列表」、「堆」。
数组
数组是将相同类型的元素存储于连续内存空间的数据结构，其长度不可变。
如下图所示，构建此数组需要在初始化时给定长度，并对数组每个索引元素赋值，代码如下：
//C++
// 初始化一个长度为 5 的数组 array
int array[5] = {0}; //全部初始化为00
int array[] = {2, 3, 1, 0, 2};
// 元素赋值
array[0] = 2;
array[1] = 3;
array[2] = 1;
array[3] = 0;
array[4] = 2;
//C# 和C+的初始化方式不一样，在堆上要new空间
int[] a = new int[3]; a[0]=2;a[1]=1;a[2]=2;
int[] a = new int[3]{1,2,3};
int[] a = {2,4,6}
链表
链表以节点为单位，每个元素都是一个独立对象，在内存空间的存储是非连续的。链表的节点对象具有两个成员变量：值 val和后继节点引用next。
//C++
struct ListNode {
int val; // 节点值
ListNode *next; // 后继节点引用
ListNode(int x) : val(x), next(NULL) {} //注意C++结构体构造函数的写法，方法体为空，格式为 : 变量名(初始化值)
};
//C#
//也有结构体，但一般直接用类来实现，节点本身就是类对象
class ListNode {
int val; // 节点值
ListNode next; // 后继节点引用
ListNode(int x) { val = x; }
}
建立此链表需要实例化每个节点，并构建各节点的引用指向。
//C++
// 实例化节点
ListNode *n1 = new ListNode(4); // 节点 head
ListNode *n2 = new ListNode(5);
ListNode *n3 = new ListNode(1);
// 构建引用指向
n1->next = n2;
n2->next = n3;
//C#
//安全模式下没有指针，类对象本身就是引用
// 实例化节点
ListNode n1 = new ListNode(4); // 节点 head
ListNode n2 = new ListNode(5);
ListNode n3 = new ListNode(1);
// 构建引用指向
n1.next = n2;
n2.next = n3;
栈
//C++
stack<int> st;
st.push(x);
st.pop();//void,无返回值
st.empty()//bool
st.top()//栈顶，只返回值不弹出
//C#
Stack<int> stack = new Stack<int>;//要new
stack.Push(x);//大写
int x = stackIn.Pop();//T，有返回值
stack.Count;
stack.Peek();//栈顶
队列
队列是一种具有 「先入先出」 特点的抽象数据结构，注意是尾进头出。
//C++
queue<int> que;
que.push(x);
que.pop();//无返回值
que.empty();
que.front();//队列头（队尾入队，队头出队）
que.back();//队列尾
//C#
Queue<int> que = new Queue<int>();
que.Enqueue(x);
que.Dequeue(x);//有返回值
que.Peek();//相当于C+的front
树
树是一种非线性数据结构，根据子节点数量可分为二叉树和多叉树，最顶层的节点称为根节点 root。以二叉树为例，每个节点包含三个成员变量：值val、左子节点left、右子节点right。
//C++
struct TreeNode {
int val; // 节点值
TreeNode *left; // 左子节点
TreeNode *right; // 右子节点
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//C#
class TreeNode {
int val; // 节点值
TreeNode left; // 左子节点
TreeNode right; // 右子节点
TreeNode(int x) { val = x; }
}
建立此二叉树需要实例化每个节点，并构建各节点的引用指向。
//C++
// 初始化节点
TreeNode *n1 = new TreeNode(3); // 根节点 root
TreeNode *n2 = new TreeNode(4);
TreeNode *n3 = new TreeNode(5);
TreeNode *n4 = new TreeNode(1);
TreeNode *n5 = new TreeNode(2);
// 构建引用指向
n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;
//C#
// 初始化节点
TreeNode n1 = new TreeNode(3); // 根节点 root
TreeNode n2 = new TreeNode(4);
TreeNode n3 = new TreeNode(5);
TreeNode n4 = new TreeNode(1);
TreeNode n5 = new TreeNode(2);
// 构建引用指向
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
图
图是一种非线性数据结构，由节点（顶点)vertex和边edge组成，每条边连接一对顶点。根据边的方向有无，图可分为有向图和无向图。以无向图为例开展介绍。
- 顶点集合： vertices = {1, 2, 3, 4, 5}
- 边集合： edges = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (3, 5), (4, 5)}
表示图的方法通常有两种：
- 邻接矩阵：使用数组vertices存储顶点，邻接矩阵edges存储边; edges[i]j代表节点i+1和节点j＋1(从1开始编号)之间是否有边。
- 邻接表：使用数组vertices存储顶点，邻接表edges存储边。edges为一个二维容器，第一维i代表顶点索引，第二维 edges[i]存储此顶点对应的边集和; 例如edges[0]=[1,2,3,4]代表vertices[0]的边集合为[1,2,3,4]。
//C++
int vertices[5] = {1, 2, 3, 4, 5};
vector<vector<int>> edges;
vector<int> edge_1 = {1, 2, 3, 4};
vector<int> edge_2 = {0, 3};
vector<int> edge_3 = {0, 4};
vector<int> edge_4 = {0, 1, 4};
vector<int> edge_5 = {0, 2, 3};
edges.push_back(edge_1);
edges.push_back(edge_2);
edges.push_back(edge_3);
edges.push_back(edge_4);
edges.push_back(edge_5);
//C#
int[] vertices = { 1, 2, 3, 4, 5 };
List<List<int>> edges = new List<List<int>>();
List<int> edge_1 = new List<int> { 1, 2, 3, 4 };
List<int> edge_2 = new List<int> { 0, 3 };
List<int> edge_3 = new List<int> { 0, 4 };
List<int> edge_4 = new List<int> { 0, 1, 4 };
List<int> edge_5 = new List<int> { 0, 2, 3 };
edges.Add(edge_1);
edges.Add(edge_2);
edges.Add(edge_3);
edges.Add(edge_4);
edges.Add(edge_5);
//C#里还有交错数组[][],所以有第二种写法
int[] vertices = { 1, 2, 3, 4, 5 };
int[][] edges = new int[5][];
edges[0] = new int[4] { 1, 2, 3, 4 };
edges[1] = new int[2] { 0, 3 };
edges[2] = new int[2] { 0, 4 };
edges[3] = new int[3] { 0, 1, 4 };
edges[4] = new int[3] { 0, 2, 3 };
邻接矩阵 VS 邻接表 ：
邻接矩阵的大小只与节点数量有关，即N2，其中N为节点数量。因此，当边数量明显少于节点数量时，使用邻接矩阵存储图会造成较大的内存浪费。因此，邻接表适合存储稀疏图（顶点较多、边较少)﹔邻接矩阵适合存储稠密图（顶点较少、边较多)。
散列表
散列表是一种非线性数据结构，通过利用 Hash 函数将指定的「键 key」映射至对应的「值 value」，以实现高效的元素查找。C+里有三种set，三种map，C#里有HashSet和Dictionary，分别对应只有key的集合和有key有value的字典（map）。
//C++
unordered_map<int,int> res;
res.find(x) != res.end();
res.count(x) > 0
res[x] = y;//C+往map里插入元素不用先Insert，直接访问索引+就好
for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) ;
unordered_set<int> res;
res.find(x) != res.end()
res.insert(x);
//C#
Dictionary<int, int> dic = new Dictionary<int, int>();
dic.ContainsKey(x);
dic.Add(x,y);
foreach(var item in dic);
HashSet<int> res = new HashSet<int>();
res.Contains(x);
res.Add(x);
//C++
unordered_map<int,int> res;
res.find(x) != res.end();
res.count(x) > 0
res[x] = y;//C+往map里插入元素不用先Insert，直接访问索引添加就好
for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) ;
unordered_set<int> res;
res.find(x) != res.end()
res.insert(x);
//C#
Dictionary<int, int> dic = new Dictionary<int, int>();
dic.ContainsKey(x);
dic.Add(x,y);
foreach(var item in dic);
HashSet<int> res = new HashSet<int>();
res.Contains(x);
res.Add(x);
堆
堆是一种基于「完全二叉树」的数据结构，可使用数组实现。以堆为原理的排序算法称为「堆排序」，基于堆实现的数据结构为「优先队列」。堆分为「大顶堆」和「小顶堆」，大（小）顶堆：父节点值总是大于（小于）子节点。
- 完全二叉树定义:设二叉树深度为k，若二叉树除第k层外的其它各层(第1至k-1层)的节点达到最大个数，且处于第k层的节点都连续集中在最左边，则称此二叉树为完全二叉树。
如下图所示，为包含1，4，2，6，8元素的小顶堆。将堆(完全二叉树）中的结点按层编号，即可映射到右边的数组存储形式。
通过使用「优先队列」的「压入 push()」和「弹出 pop()」操作，即可完成堆排序（压入相当于构造堆，不断弹出堆顶得到最大（小）的值）。
//C++
priority_queue<int, vector<int>, greater<int>> heap;
//C#
PriorityQueue<int> pq = new PriorityQueue<int>();//默认小顶堆
京公网安备 11010502036488号