链表 链表是一种逻辑结构上的线性表，物理结构上的非线性表链表由许多节点组成，每个节点有对应的值和指向下一个节点的指针第一个节点称为首节点，最后一个节点称为尾节点，尾节点的指向为空.特点:查找某一节点都是由头开始遍历查找，增加节点的效率比顺序表快，删除节点的效率比顺序表快，查找节点的效率比顺序表慢代码示例:#include<iostream> using namespace std; //创建链表结构体,数据成员有值和指向下一节点的指针 struct list{ int value; list *next; list(int x){ value = x; next = nullptr; } }; //在n节点后插入p节点 void insert(list *n, list *p){ p->next = n->next; n->next = p; } //删除n节点的下一个节点 void remove(list *n){ if(n->next == nullptr){ return; } list *p = n->next; list *n1 = p->next; n->next = n1; delete p; } //访问索引index的节点 list *access(list *head, int index){ for(int i = 0; i < index; i++){ if(head == nullptr){ return nullptr; } head = head->next; } return head; } //查找值为target的节点,输出索引 int find(list *head, int target){ int index = 0; while(head != nullptr){ if(head->value == target){ return index; } head = head->next; index++; } return -1; } int main(){ //创建节点 list *n1 = new list(1); list *n2 = new list(2); list *n3 = new list(3); //连接节点 n1->next = n2; n2->next = n3; //测试函数 list *p = new list(10); insert(n1, p); remove(n2); list *p1 = access(n1, 1); cout << find(n1, 10) << endl; return 0; }

C++实现顺序表 顺序表,一种线性表,因此顺序表是线性的.因为顺序表在物理结构与逻辑结构都是连续的.意味着在内存中是连续存储的,形如数组的内存存储方式,我将用数组实现顺序表.实现顺序表的主要功能为:增删查改.顺序表是一种简单的数据结构,原理与实现并不难主要维护下标size,内存空间capacity的大小即可Seqlist.h头文件声明#pragma once #include<iostream> #include<cstdlib> #include<cassert> using namespace std; // 顺序表结构定义 typedef int SLDataType; class SeqList { public: SLDataType* arr; int size; int capacity; }; typedef SeqList SL; //检查顺序表容量是否合理 void checkSLCaoacity(SL* ps); //顺序表初始化 void SLInit(SL* ps); //顺序表的销毁 void SLDestroy(SL* ps); //顺序表的插入操作 //头插尾插 void SLPushFront(SL* ps,SLDataType x); void SLPushBack(SL* ps, SLDataType x); //头删尾删 void SLPopFront(SL* ps); void SLPopBack(SL* ps); //选择插入 void SLInsert(SL* ps,int i, SLDataType x); //选择删除 void SLDelete(SL* ps, SLDataType x); //顺序表的查找操作 void SLFind(SL* ps, SLDataType x); //顺序表的修改操作 void SLUpdate(SL* ps, int i, SLDataType x); //输出所以元素 void SLPrint(SL* ps);Seqlist.cpp原文件中存方法#include"SeqList.h" void SLInit(SL* ps) { ps->arr = NULL; ps->size=ps->capacity=0; } void SLDestroy(SL* ps) { if (ps->arr) { delete[] ps->arr; } ps->arr = NULL; ps->size = ps->capacity = 0; } void checkSLCaoacity(SL* ps) { //先判断空间够不够 if (ps->size == ps->capacity) { int newCapacity = (ps->capacity == 0) ? sizeof(SLDataType) : 2 * ps->capacity; SLDataType* temp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType)); if (!temp) { perror("realloc failed"); exit(1); } ps->arr = temp; //delete(temp); ps->capacity = newCapacity; } } //头插尾插 void SLPushFront(SL* ps, SLDataType x) { assert(ps);//传其他类型指针会导致崩溃，给爷爬 checkSLCaoacity(ps); //插入 for (int i = ps->size; i > 0; i--) { ps->arr[i] = ps->arr[i - 1]; } ps->arr[0] = x; ps->size++; } void SLPushBack(SL* ps, SLDataType x) { assert(ps); checkSLCaoacity(ps); ps->arr[ps->size++] = x; } //头删尾删 void SLPopFront(SL* ps) { assert(ps); if (ps->size == 0) { return; } for (int i = 0; i < (ps->size--) - 1; i++) { ps->arr[i + 1] = ps->arr[i]; } } void SLPopBack(SL* ps) { assert(ps); if (ps->size == 0) { return; } ps->size--; } //选择插入 void SLInsert(SL* ps, int i, SLDataType x) { assert(ps); checkSLCaoacity(ps); //1 2 3 4 5 size //0 1 2 3 4 for (int j = ps->size; j >i; j--) { ps->arr[j] = ps->arr[j - 1]; } ps->arr[i] = x; ps->size++; } //选择删除 void SLDelete(SL* ps, SLDataType x) { assert(ps); if (ps->size == 0) { return; } for (int j = 0; j < ps->size; j++) { if (ps->arr[j] == x) { for (int k = j; k < ps->size - 1; k++) { ps->arr[k] = ps->arr[k + 1]; } ps->size--; return; } } cout << "没有找到要删除的元素" << '\n'; } //顺序表的查找操作 void SLFind(SL* ps, SLDataType x) { assert(ps); for (int i = 0; i <= ps->size - 1; i++) { if (ps->arr[i] == x) { cout << "找到了第" << i + 1 << "个元素\n"; cout << "值为:" << ps->arr[i] << '\n'; return; } } cout << "没有找到要查找的元素" << '\n'; } //顺序表的修改操作 void SLUpdate(SL* ps, int i, SLDataType x) { assert(ps); checkSLCaoacity(ps); if (i <= 0 || i > ps->size - 1) { cout << "索引越界" << '\n'; return; } ps->arr[i - 1] = x; } //输出所有元素 void SLPrint(SL* ps) { assert(ps); checkSLCaoacity(ps); for (int i = 0; i < ps->size; i++) { cout << ps->arr[i] << " "; } cout << '\n'; }test.cpp源文件中用于测试实现的功能#include"SeqList.h" void test01() { SL s; SLInit(&s);//初始化 //增删查改 //使用for循环插入100个元素 for (int i = 1; i <= 100; i++) { if(i&1) SLPushFront(&s, i); else SLPushBack(&s, i); } //输出所有元素 SLPrint(&s); //查找元素 SLFind(&s, 55); SLFind(&s, 999); //删除元素 SLDelete(&s, 100); SLDelete(&s, 404); SLPrint(&s); //修改元素 SLUpdate(&s, 55, 969696); SLPrint(&s); SLDestroy(&s);//销毁 } int main() { test01(); return 0; }

并查集 并查集 :并为合并(合并两个节点),查为查询(查询根节点),集是一个集合. 联通块问题 //各个节点的相连形成一个连通块.即使只有一个元素,因为可以自己连向自己所以也属于一个连通块 题解思路: 根据题意,我们可以使用并查集 先写一个 查 的函数,利用函数的递归不断寻找根(父)节点int root(int x) { //寻找根节点 return pre[x] = (pre[x] == x ? x : root(pre[x]));//路径压缩 } 接着可以写一个 并 的函数,利用 查函数 我们可以寻找到根节点,我们的合并只需要彼此的根节点相连即可void merge(int x, int y) { pre[root(x)] = root(y);//合并 }接下来就很简单了 AC代码:#include<iostream> #include<vector> #include<algorithm> using namespace std; const int N = 2e5 + 10; int pre[N], cnt[N]; int root(int x) { //寻找根节点 return pre[x] = (pre[x] == x ? x : root(pre[x]));//路径压缩 } void merge(int x, int y) { pre[root(x)] = root(y);//合并 } bool iscon(int x, int y) { return root(x) == root(y);//判断是否连通 } int main() { std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n, m; cin >> n >> m; for (int i = 1; i <= n; i++)pre[i] = i;//初始化 //读入边 for (int i = 1; i <= m; i++) { int u, v;cin>>u>>v; merge(u, v); } for(int i=1;i<=n;i++) cnt[root(i)]++;//统计连通分量 vector<int>v; for (int i = 1; i <= n; i++)if (cnt[i])v.push_back(cnt[i]); sort(v.begin(), v.end());//排序 for (auto& i : v) { cout << i << " "; } return 0; }

排序算法 一.插入排序(Insertion Sort) 插入排序，如打扑克时的理牌一样，左手为空，从牌堆摸牌，将摸到的牌从右往左对比，放到比其小的牌的右边。代码示例:#include<iostream> using namespace std; int main() { int a[10]; for (int i = 0; i < 10; i++) { cin >> a[i]; } //4 5 2 8 1 9 3 7 6 0 a数组的key //0 1 2 3 4 5 6 7 8 9 i下标 for (int i = 2; i < 10; i++) { int key = a[i];//选定一个数将其与左边的数一一对比 int j = i - 1; while (j >= 0 && a[j] < key) //如果比选定的数字大则将其右移 { a[j + 1] = a[j]; j--; } a[j + 1] = key; } for (int i = 0; i < 10; i++) { cout << a[i] << " "; } return 0; }二.选择排序(Selection sort) 遍历数组，找到最小的数，交换位置，让最小的数排在前面代码示例:#include<iostream> using namespace std; int main() { int a[10]; for (int i = 0; i < 10; i++)cin >> a[i]; for (int i = 0; i < 10; i++) { int temp = i; for (int j = i; j < 10; j++) { if (a[j] < a[temp]) { temp = j; } } swap(a[i], a[temp]); } for (int i = 0; i < 10; i++) { cout << a[i] << " "; } return 0; }三.冒泡排序(Bubble Sort) 每次就行两个数之间的比较,将大(小)的数放在右边,每次循环更大(小)的数会像泡泡一样飘到最右边.代码示例:#include<iostream> using namespace std; int main() { // 定义包含10个元素的整数数组 int a[10]; for (int i = 0; i < 10; i++) { // 从标准输入流读取用户输入的整数，并存储到数组a中 cin >> a[i]; } // 使用冒泡排序算法对数组a进行排序 for (int i = 0; i < 10; i++) { for (int j = i + 1; j < 10; j++) { // 如果当前元素大于后续元素，则交换它们的位置 if (a[i] > a[j]) { int temp=a[i]; a[i] = a[j]; a[j] = temp; } } } // 输出排序后的数组a for (int i = 0; i < 10; i++) { cout << a[i] << " "; } // 返回程序运行成功状态 return 0; } 四.合并排序(Merge sort) 利用递归,将原数组拆分,接着合并的同时排序,如图 代码示例:#include<iostream> #include<vector> using namespace std; // 归并排序的辅助函数，用于将两个已排序的子数组合并为一个排序数组 void merge(vector<int>& a, int l, int mid, int r) { int nx = mid - l + 1; // 计算第一个子数组的大小 int ny = r - mid; // 计算第二个子数组的大小 vector<int>P(nx); // 创建第一个子数组 vector<int>Q(ny); // 创建第二个子数组 // 将元素复制到临时数组P和Q中 for (int i = 0; i < nx; i++) { P[i] = a[l + i]; } for (int i = 0; i < ny; i++) { Q[i] = a[mid + 1 + i]; } int i = 0, j = 0, k = l; // 合并两个子数组 while (i < nx && j < ny) { if (P[i] <= Q[j]) { a[k] = P[i]; i++; } else { a[k] = Q[j]; j++; } k++; } // 将剩余的元素复制回原数组 while (i < nx) { a[k] = P[i]; i++; k++; } while (j < ny) { a[k] = Q[j]; j++; k++; } } // 归并排序算法的主要逻辑，递归地将数组分为较小的数组，并调用merge函数进行合并 void merge_sort(vector<int>& a, int l, int r) { if (l < r) { int mid = (l + r) / 2; // 计算中间索引 merge_sort(a, l, mid); // 递归排序左半部分 merge_sort(a, mid + 1, r); // 递归排序右半部分 merge(a, l, mid, r); // 合并两个已排序的子数组 } } int main() { vector<int>a(10); // 创建一个包含10个元素的向量 // 从标准输入中读取输入元素并存储在向量中 for (int i = 0; i < 10; i++) { cin >> a[i]; } merge_sort(a, 0, a.size() - 1); // 对输入的数组进行归并排序 // 输出排序后的数组元素 for (int i = 0; i < 10; i++) { cout << a[i] << " "; } return 0; } 五.快速排序(Quick Sort) 快速排序维护左右指针left,right和基准点base 先让right不断向左扫,找到比base大(小)的值然后与left指向的值交换 然后left不断向右扫,找到比base小(大)的值然后与right指向的值交换 一次操作后会形成两个区间,然后分别对两个区间进行上述操作 代码示例中用了两种方法,一种普通的,一种使用分治代码示例:#include<iostream> using namespace std; void quickSort_num1(int arr[], int star, int end) { //确定左右指针的位置 int left = star, right = end; //设置基准点 int base = arr[star]; if (left < right) { while (left < right) { //先让由指针不断往左寻找比 base 小的值,找到了便交换 //如果没找到,此时left = right 等于没交换 while (left < right && arr[right] >= base) { right--; } arr[left] = arr[right]; //先让由指针不断往右寻找比 base 大的值,找到了便交换 //如果没找到,此时left = right 等于没交换 while (left < right && arr[left] <= base) { left++; } arr[right] = arr[left]; } //arr[right] = base 也可以,因为最终left=right arr[left] = base; //接着再让分割好的两个小区间进行上述操作 //左边区间为比base小的值 quickSort_num1(arr, star, left - 1); //右边区间为比base大的值 quickSort_num1(arr, left + 1, end); } } //采用分治的方法,先找分割点 //partition为寻找分割点的函数 int partition(int arr[], int left, int right) { int base = arr[left]; while (left < right) { //先让由指针不断往左寻找比 base 小的值,找到了便交换 //如果没找到,此时left = right 等于没交换 while (left < right && arr[right] >= base) { right--; } arr[left] = arr[right]; //先让由指针不断往右寻找比 base 大的值,找到了便交换 //如果没找到,此时left = right 等于没交换 while (left < right && arr[left] <= base) { left++; } arr[right] = arr[left]; } arr[left] = base; return left; } void quickSort_num2(int arr[], int left, int right) { if (left < right) { //确定分割点 int pos = partition(arr, left, right); //左右区间,再重复操作 quickSort_num2(arr, left, pos - 1); quickSort_num2(arr, pos + 1, right); } } int main() { int arr1[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 10}; quickSort_num1(arr1, 0, 9); for (int i = 0; i < 10; i++) { cout << arr1[i] << " "; } cout << '\n'; //采用分治思想 int arr2[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 10}; quickSort_num2(arr2, 0, 9); for (int i = 0; i < 10; i++) { cout << arr2[i] << " "; } cout << '\n'; return 0; }

单调栈 (单调栈模板题)题目描述给定一个长度为n的整数数组a，你需要求出每个元素的左边离它最近且比它小的元素。输入描述第一行：一个整数n(1≤n≤2×10^5)第二行：n个整数，表示整数数组a.(1≤a≤10^9)输出描述共一行，n个整数，表示每个元素的左边第一个比它小的元素，若不存在则为−1。输入样例157 8 5 6 7输出样例1-1 7 -1 5 6我们可以使用STL中的stack实现思路主要为将数组中的数值于栈中的数值进行对比，但栈中的数组比数组中的值大时，我们需要舍弃栈中的数，否则将数组中的值压入栈中代码示例:#include<iostream> #include<stack> using namespace std; const int N = 2e5; int a[N], b[N]; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++)cin >> a[i]; stack<int>q; for (int i = 1; i <= n; i++) { while (!q.empty() && q.top() >= a[i])q.pop(); if (q.empty())b[i] = -1; else b[i] = q.top(); q.push(a[i]); } for (int i = 1; i <= n; i++)cout << b[i] << " "; return 0; }使用stack是一种选择，但是更推荐使用数组模拟来实现单调栈，因为数组能进行更多操作，对于题目的适应与灵活度更高。但是因为数组空间固定要注意数组栈的溢出问题。下面给出数组实现的代码:#include<iostream> using namespace std; const int N = 2e5; int a[N], b[N], stk[N], top; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++)cin >> a[i]; for (int i = 1; i <= n; i++) { while (top && a[stk[top]] >= a[i])top--; if (top)b[i] = a[stk[top]]; else b[i] = -1; stk[++top] = i; } for (int i = 1; i <= n; i++)cout << b[i] << " "; return 0; }