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; }

二分法 二分查找本质上是按照某一性质每次一分为二查找左右边界 普通的二分查找 题目 题目解释:在一组有序无重复数组中查找某一个数，如果能查找到输出这个数是第几个数，否则输出-1. 我们可以使用二分法进行查找，即将数组一分为二，从中间的数进行判断是否大于或小于我们要查找的数，因为数组是有序递增的，所以如果中间数大于查找的数我们便查找左部分的数否则查找右部分的数。 代码示例:#include<iostream> #include<vector> using namespace std; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; vector<int>a(n + 1); for (int i = 1; i <= n; i++)cin >> a[i]; int l = 1, r = n;//因为数组大小为n所以左右边界为(1,n) int x; cin >> x;//输入要查找的数 while (l < r)//设置跳出循环的条件，即当l=r时退出循环 { int mid = (l + r) >> 1;//(l+r)/2,对中间数进行向下取整 if (a[mid] >= x)r = mid; //如果查询的数小于等于中间数，查询左部分，将右边界向左移 else l = mid + 1; //如果查询的数大于中间数，查询右部分，将左边界向右移，因为数组mid对应的数不对所以再右移一位 } //l下标对应的即是最后的查找 if (a[l] == x) cout << l << '\n'; else cout << -1 << '\n'; return 0; }二分查找左右边界 二分查找左边界 二分查找右边界 题目解释:左右边界意思是最左或最右，或者最小或最大。 如一组数12333445，查找3的左边界，答案为3.查找3的右边界，答案为5二分查找左边界 左边界代码://二分查找左边界 #include<iostream> #include<vector> using namespace std; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; vector<int>a(n + 1); for (int i = 1; i <= n; i++)cin >> a[i]; int y; cin >> y; while (y--) { int x; cin >> x; int l = 1, r = n; while (l < r) { int mid = (l + r) >> 1; if (a[mid] >= x)r = mid; else l = mid + 1; } if (a[l] == x)cout << l << ' '; else cout << -1 << ' '; } return 0; }可以看到查找左边界和普通二分查找原理相同，稍有的不同只是因为题目的需求不同，实际上普通二分查找是查找左右边界的特例，只不过是因为数组中的数是否重复而不同 下面给出右边界代码:#include<iostream> #include<vector> using namespace std; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; vector<int>a(n + 1); for (int i = 1; i <= n; i++)cin >> a[i]; int y; cin >> y; while (y--) { int x; cin >> x; int l = 1, r = n; while (l < r) { int mid = (l + r + 1) >> 1;//1.注意， 如果 l=r-1 && nums[mid] <= target 此时l不能变化，进入死循环因此 mid更新应该改变 ，即 +1 if (a[mid] <= x)l = mid;//2.注意 else r = mid - 1;//注意 } if (a[l] == x)cout << l << ' '; else cout << -1 << ' '; } return 0; }注意代码中的注意，为与左边界不同的地方 1.如果 l=r-1 && nums[mid] <= target 此时l不能变化，进入死循环，因此 mid更新应该改变 ，即 +12.l不能+1,如果r=l+1，可能存在mid =r =l +1让循环进入死循环3.r-1是因为当前mid对应的数不为查找的数查找最小值用左边界，查找最大值用右边界左右边界的不同可以简单记忆为:左加右减二分答案-以伐木工为例 伐木工 咋一看与二分无关，如果直接暴力容易超时，因此使用二分法。 具体思路为写一个check函数判断当前高度以上的数相加是否符合所需的木材 此时的左右边界设置为0与最高高度的树，因为我们需要求的是伐木的高度，因此我们使用的二分法是求右边界，边界范围只与给出树的最高高度有关，再高就不礼貌了。 代码示例#include<iostream> #include<vector> using namespace std; using ll = long long; bool check(ll mid, ll n, ll m, vector<ll>& a) { ll num = 0;//num求a中mid高度以上的树的和 for (ll i = 1; i <= n; i++) { if (a[i] > mid)num += (a[i] - mid); if (num >= m)return true;//如果相加的木材长度大于或等于需要的木材长度，返回true，继续增加高度 } return false; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); ll n, m; cin >> n >> m; vector<ll>a(n + 1); for (ll i = 1; i <= n; i++)cin >> a[i]; ll l = 0;//左边界 //找出最高的树作为右边边界 ll r = a[0]; for (ll i = 1; i <= n; i++) r = max(r, a[i]); //二分查找右边界 while (l < r) { ll mid = (l + r + 1) >> 1; if (check(mid, n, m, a)) l = mid; else r = mid - 1; } cout << l << '\n'; return 0; }洛谷-进击的奶牛 题解 本题查找相邻两头牛 最大 的最近距离，因此使用 右边界 选择好使用哪种二分后想想该怎么具体实现。我们想要对首先我们需要对输入的数组进行排序，然后取 l 为 1 ， r 为一个很大的值即可。 check 函数中我们需要定义一个 num 对间隔距离进行求和，当 num>=mid 时对牛牛数量进行加 1 并且让 num为0 ，重新计数，直到牛牛的数量 >= 输入的奶牛的数量 c 。 示例代码//洛谷 进击的奶牛 #include<iostream> #include<vector> #include<algorithm> using namespace std; const int N=0x3f3f3f3f; using ll = long long; ll n, c; vector<ll>a(1); bool check(ll mid){ ll num = 0; ll nn = 1; for(ll i = 2; i <= n; i++){ num += a[i] - a[i - 1]; if(num >= mid) { nn++; num = 0; } if(nn >= c) return true; } return false; } int main() { std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin >> n >> c; a.resize(n + 1); for(ll i = 1;i <= n; i++) cin >> a[i]; sort(a.begin(), a.end()); ll l = 0,r = N; while(l < r){ ll mid = (l + r + 1) >> 1; if(check(mid)) l = mid; else r = mid - 1; } cout << l <<'\n'; return 0; }

前缀和与差分 前缀和公式为 num[i] = num[i - 1] + a[i]差分公式为 diff[i] = a[i] - a[i - 1]前缀和与差分是能互相转换的前缀和数组进行一次差分可得原数组差分数组进行前缀和可得原数组原数组 ---前缀和---> 前缀和数组前缀和数组 ---差分---> 原数组原数组 ---差分---> 差分数组差分数组---前缀和---> 原数组前缀和数组 原数组 差分数组一维前缀和 题目描述 给定义一个数组𝑎，有𝑞+1次询问，对于每次询问：给定两个整数𝑙,𝑟，求出𝑎𝑙 + 𝑎𝑙+1 + ... + 𝑎𝑟的结果。输入描述 第一行一个整数表示样例个数T(1≤T≤10)。对于每组样例：第一行2个整数n(1≤n≤10^5),q(1≤q≤10^5)，分别表示数组长度和询问次数。第二行n个整数，表示数组a(−10^9≤ai≤10^9)。接下来q行，每行两个整数r(1≤l≤r≤n)表示询问的区间。输出描述 对于每组样例，一行一个整数表示答案。输入样例1 25 31 2 3 4 51 22 53 47 2-1 9 -10 8 2 6 111 52 7 输出样例1 3147826题解 根据输入的数组，建立一个每次相加前一位的数组如输入的为1 2 3 4 5根据前缀进行和1，1+2=3，3+3=6，6+4=10，10+5=15建立的数组为1 3 6 10 15对于查询的区间（l,r）只需进行算出：r位减去（l-1）位之间的值即可如查询（2,5）之间的和，15-1即是（2,5）区间的和代码样例#include<iostream> #include<vector> using namespace std; using ll = long long; void vol() { ll m, n; cin >> m >> n; vector<ll>ve(m + 1 , 0); for (ll i = 1; i <= m; i++) { cin >> ve[i]; } vector<ll>cop(m + 1, 0); for (ll i = 1; i <= m; i++) { cop[i] = cop[i - 1] + ve[i]; } ll l, r; for (ll i = 1; i <= n; i++) { cin >> l >> r; cout << cop[r] - cop[l - 1] << '\n'; } } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); ll t; cin >> t; while (t--) { vol(); } return 0; }一维差分 题目描述 给定一个长度为n的数组a，和两个整数p,q。先进行p次区间加操作：将区间[l,r]的数字都加上x。再进行q次区间查询操作：求出[l,r]的数字之和。对于每次区间查询操作，输出结果。 输入描述 第一行三个整数n,p,q。(1≤n≤10^5 ,0≤p≤10^5 ,0≤10^5 ≤q)第二行n个整数表示数组a。(−10^9 ≤ai ≤10^9 )接下来p行，每行三个整数l,r,x。(1≤l≤r≤n,−10^9 ≤x≤10^9 )接下来q行，每行两个整数(1≤l≤r≤n)输出描述 对于每次区间查询操作，输出结果。输入样例1 5 1 21 1 1 2 21 4 21 31 5 输出样例1 915题解 根据输入的数组建立一个差分数组如输入1,2,3,4,51-0=1，2-1=1，3-2=1，4-3=1，5-4=1因此建立的差分数组为1,1,1,1,1代码实例#include<iostream> using namespace std; const int N = 1e5+9; using ll = long long; ll a[N], diff[N], num[N]; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n , p , q ; cin >> n >> p >> q ; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) diff[i] = a[i] - a[i - 1]; while (p--) { ll l, r, x; cin >> l >> r >> x; diff[l] += x; diff[r + 1] -= x; } for (int i = 1; i <= n; i++) a[i] = diff[i] + a[i - 1]; for (int i = 1; i <= n; i++) num[i] = num[i - 1] + a[i]; while (q--) { ll l, r; cin >> l >> r; cout << num[r] - num[l - 1] << '\n'; } return 0; }二维前缀和 二维数组基本原理与一维前缀和几乎相同 注意重叠部分即可题目描述 给定一个n行m列的整数矩阵。 q个询问，每个询问格式为：x1,y1,x2,y2，表示一个子矩阵的左上角和右下角的坐标。对于每个询问，请回答子矩阵的所有数之和。输入格式 第一行包括三个整数n,m,q（1≤n,m≤10^3 ，1≤𝑞≤10^5,1≤q≤10^5 ）。接下来n行，每行包括m个整数，表示整数矩阵（每个整数的取值范围为[1,10^5 ]）。接下来q行，每行包括四个整数x1,y1,x2,y2(1<=x1<=x2<=n,1<=y1<=y2<=m)，表示一个询问的左上角、右下角坐标。输出格式 共q行，第i（1≤i≤q）行输出第i个询问的结果。样例输入1 7 3 23 5 1 6 2 4 7 9 10 4 3 6 3 9 9 6 10 1 9 10 4 2 2 7 32 1 4 2 样例输出1 7731代码实例#include<iostream> #include<vector> using namespace std; using ll = long long; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); ll n, m, q; cin >> n >> m >> q; vector<vector<ll> >a(n + 1, vector < ll >(m + 1, 0)); ll i, j; for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { cin >> a[i][j]; } } vector<vector<ll> >b(n + 1, vector < ll >(m + 1, 0)); for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { b[i][j] = b[i - 1][j] + b[i][j - 1] + a[i][j] - b[i - 1][j - 1]; } } while (q--) { ll x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; cout << b[x2][y2] - b[x1 - 1][y2] - b[x2][y1 - 1] + b[x1 - 1][y1 - 1] << '\n'; } return 0; }二维差分 题目描述给定一个n行m列的整数矩阵。有q个操作，每个操作格式为：x1,y1,x2,y2,c，其中(𝑥1,𝑦1)、(x2,y2)分别表示一个子矩阵的左上角和右下角的坐标，每个操作将对应的子矩阵的每个元素加上c。请输出进行完所有操作后的矩阵。输入描述第一行包括三个整数n,m,q（1≤n,m≤10^3 ,1≤q≤10^5 ）。输出描述共n行，每行包括m个整数，表示进行完所有操作后的矩阵。输入样例14 3 31 5 1 3 3 2 5 3 4 4 4 2 1 2 1 2 22 1 2 3 24 2 4 3 1输出样例11 7 1 5 5 4 5 3 4 4 5 3 代码示例//二维差分 #include<iostream> using namespace std; using ll = long long; const int N = 1e3 + 9; ll a[N][N], diff[N][N]; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, m, q; cin >> n >> m >> q; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; } } //差分 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { diff[i][j] += a[i][j]; diff[i + 1][j] -= a[i][j]; diff[i][j + 1] -= a[i][j]; diff[i + 1][j + 1] += a[i][j]; } } //修改 while (q--) { int x1, y1, x2, y2, c; cin >> x1 >> y1 >> x2 >> y2 >> c; diff[x1][y1] += c; diff[x2 + 1][y2 + 1] += c; diff[x2 + 1][y1] -= c; diff[x1][y2 + 1] -= c; } //求原数组 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + diff[i][j]; cout << a[i][j] << " "; } cout << '\n'; } return 0; }

类的构造函数与析构函数 构造函数 构造函数的定义 class 类名{ public: 类名();//构造函数 }构造函数无返回类型也不需要写void构造函数会自动调用，无定义时为空实现。因此需要我们定义构造函数进行数据的初始化构造函数可以有参数也可以无参数，因此根据参数的类型构造函数可发生重载，且构造函数只能被调用一次。构造函数可按有无参数分为有参构造函数和无参构造函数 构造函数按类型可分为普通构造函数和拷贝构造函数构造函数参数类型一无参构造函数普通构造函数二有参构造函数拷贝构造函数注意 不要用拷贝构造函数进行初始化匿名对象 编译器会认为book(b2);等于book b2;会造成重定义以下为调用构造函数的实例：#include<iostream> using namespace std; class book { public: book() { cout << "类的无参构造函数" << endl; } book(int a) { b = a; cout << "类的有参构造函数" << b << endl; } book(const book& b) { cout << "类的拷贝构造函数" << b.b << endl; } int b; }; void test() { //调用有三种方法调用 //括号法 book b1; book b2(10); book b3(b2); //显示法 book b4; book b5 = book(10); book b6 = book(b5); //隐式转换法 book b7 = 10; book b8 = b7; } int main() { test(); return 0; }注意括号法的第一个： book b1; 不要在b1后面加()，如果加了会造成二义性，编译器无法识别构造函数的实例中的显示法的book(10)为匿名对象析构函数 析构函数的定义 class 类名{ public: ~类名();//析构函数 }析构函数与构造函数的区别相同 都会自动调用 不同在类名前加"~"析构函数无返回值且无参数，因此不可发生重载析构函数发生在对象的销毁时析构函数主要用于数据的销毁工作以下为调用析构函数的实例：#include<iostream> using namespace std; class person { public: ~person() { cout << "类的析构函数" << endl; } }; void test() { person p1; } int main() { test(); person p2; system("pause"); return 0; }注意：当运行到system("pause");时暂停，p2仍在main函数中，main函数为结束，因此p2为进行销毁，所以p2还未调用析构函数，当按任意键继续时main函数结束，p2内存回收，因此才会调用析构函数打印出信息。

各种函数的用法 sort函数 algorithm头文件中的sort函数运用作用： 对范围内元素进行排序语法： 需要声明algorithm头文件sort( first ,last ,comp );其中first与last为起始与终末位置first与last为地址并非值。comp是接收两个元素并返回bool类型的函数，注意并非函数调用,因此在函数名后面无需添加()comp函数不改变值，可以是函数指针或函数对象comp可以省略，当省略时将使用默认排序，默认排序为从小到大排序。 实例：#include<iostream> #include<algorithm> using namespace std; bool comp(int x, int y) { return x > y;//从大到小排序 } int main() { int arr[5] = { 52,23,71,17,89 }; sort(arr, arr+5,comp); for (int i = 0; i < 5; i++) { cout << arr[i]<<" "; } cout<<endl; return 0; }getline函数 作用： 对字符串进行输入 特点： 与cin不同可以读入cin不能读入的空格。 此函数可读取整行，包括前导和嵌入的空格，并将其存储在字符串对象中。 语法： getline(cin, inputLine); inputline是接收输入的字符串string变量的名字。 实例：#include<iostream> #include<string> using namespace std; int main() { string str; getline(cin, str); cout << str << endl; return 0; }