数据结构
数组
数组是将相同类型的元素存储于连续内存空间的数据结构，其长度不可变。
如下图所示，构建此数组需要在初始化时给定长度，并对数组每个索引元素赋值，代码如下：
//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}
可变数组（vector, List）
可变数组是经常使用的数据结构，其基于数组和扩容机制实现，相比普通数组更加灵活。常用操作有：访问元素、添加元素、删除元素。
//vector/List放入，弹出一个元素
//C++
vectorxx.push_back();
vectorxx.pop_back();
vectorxx.erase(vec.begin() + 1); // 移除第二个元素
vector<int> res(nums.size() 大小, 100 默认值);//构造函数初始化
//C#
listxx.Add();
Listxx.Remove(int index);
Listxx.RemoveAll();
int lastIndex = list.Count - 1;
list.RemoveAt(lastIndex);
链表
链表以节点为单位，每个元素都是一个独立对象，在内存空间的存储是非连续的。链表的节点对象具有两个成员变量：值 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
双向队列
//C++
deque<int> que;
que.push_back(x);
que.push_front(x);
que.pop_back();
que.pop_front();
que.front();
que.back();
//C#
//没有双向队列，用双向链表
LinkedList<int> que;
que.AddLast(x);
que.AddFirst(x);
que.RemoveLast();
que.RemoveFirst();
que.First.Value;
que.Last.Value;
堆（大小顶堆，优先级队列）
堆是一种基于「完全二叉树」的数据结构，可使用数组实现。以堆为原理的排序算法称为「堆排序」，基于堆实现的数据结构为「优先队列」。堆分为「大顶堆」和「小顶堆」，大（小）顶堆：父节点值总是大于（小于）子节点。
- 完全二叉树定义:设二叉树深度为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>();//默认小顶堆
散列表（Set&哈希表&字典）
//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);
树
树是一种非线性数据结构，根据子节点数量可分为二叉树和多叉树，最顶层的节点称为根节点 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为节点数量。因此，当边数量明显少于节点数量时，使用邻接矩阵存储图会造成较大的内存浪费。因此，邻接表适合存储稀疏图（顶点较多、边较少)﹔邻接矩阵适合存储稠密图（顶点较少、边较多)。
库函数
INT最大最小值
//C++
INT_MAX;
//C#
int.MaxValue;
最大值，最小值，绝对值
//C++
max(a,b);
min(a,b);
//C#
Math.Min(a,b);
Math.Max(a,b);
Math.Abs(a);
数组排序
//C++ 数组和vector
sort(nums.begin(), nums.end());
sort(nums.begin(), nums.end(), cmp);
static bool cmp(int a, int b) {
return abs(a) > abs(b); //按绝对值从大到小排序
}
//C# 数组和List
Array.Sort(nums);
Array.Sort(nums, CustomComparison);
public static int CustomComparison(int x, int y) {
// 自定义的排序逻辑
return Math.Abs(y).CompareTo(Math.Abs(x)); //按绝对值从大到小排序
}
数组分割
//C++
vector<int> a(x.begin(), mid);//左开右闭，不包含mid
vector<int> b(mid, x.end());//左闭右开，包含mid
交换元素
//C++
swap(s[i], s[j]);
//C#
没有
倒转数组
//C++
reverse(s.begin() , s.end());//左闭右开
//C#
Array.Reverse（nums, index, length）//(注意第三个参数是长度不是索引)
list.Reverse();
list.Reverse(int index, int count);//index开始，反转count个元素
空指针
//C++
nullptr
//C#
null
数组扩容
//C++
s.resize(s.size() + cnt);
//C#
char[] arr = s.ToCharArray();
Array.resize(ref arr, s.Length + cnt);
string ss = new string(arr); //C#string不能直接resize
string,char数组互转
//C++
char cc[1] = ss.data();
string ss = cc;
//C#
char[] arr = s.ToCharArray();
string ss = new string(arr);
string，int互转
//C++
int a = stoi("5");
string a1 = to_string(a);
//C#
int a = int.Parse("5");
int a = int.TryParse(s, out num);//转换失败返回false
string a1 = a.ToString();
switch case
C++switch只能判断int，short,long，longlong等整形，C#不限制。
//C++
siwtch(s) {
case 1:
xxx;
break;
}
//C#
switch(s) {
case "a":
xxxx;
break;
}
List转int
//C#
listxx.toArray();
获取字符串子串
//C++
string str = "abcdef";
string sub = str.substr(1, 3); // sub为"bcd"
//C#
string str = "Hello, world!";
string substr1 = str.Substring(7); // "world!"
string substr2 = str.Substring(0, 5); // "Hello"
向字符串中插入/删除元素
//C++
s.insert(s.begin() + i + 1 , '.'); // 在i的后面插入一个逗点
s.erase(s.begin() + i + 1); // 删掉i后面的逗点
//C#
string += ".";
string.Contact;
//需要注意的是，由于字符串在 C# 中是不可变的，所以每次使用 + 运算符拼接字符串时，都会创建一个新的字符串对象，而不是直接在原有的字符串对象中添加内容。如果需要频繁地对字符串进行修改操作，建议使用 StringBuilder 类型，可以避免这种额外的开销。
StringBuilder sb = new StringBuilder("Hello");//避免多次构建string实例，C#中string是不能直接改变的
// 向字符串中添加内容
s = s + "a";
sb.Append(", World!");
string result = sb.ToString(); // "Hello, World!"
string str = "Hello, World!";
// 从字符串中删除逗号和空格
str = str.Remove(5, 2); // "Hello World!"
StringBuilder sb = new StringBuilder("Hello, World!");
sb.Remove(7, 7); // 从字符串的第 7 个位置开始删除 7 个字符
Console.WriteLine(sb.ToString()); // 输出：Hello!
从文件中读取数组
#include<iostream>
#include<vector>
#include<fstream>
#include<string>
file.open("F:/CppBase/x64/Debug/test1.txt",ios::in);
if (!file.is_open()) {
cout << "文件打开失败" << endl;
return 0;
}
int buf;
while (file >> buf) {
res.push_back(buf);
}
京公网安备 11010502036488号