3278 字
16 分钟
古早的笔记(自不用)
2023-09-07
OI
C语言
/
数据结构
/
算法

数据结构#


栈#

栈 stack FILO(first in last out) 如一个试管，只有一端可以控制进入输出，且进入输出都只能在栈顶进行，将压入栈顶为push，弹出栈顶为pop


手写栈#

#include <bits/stdc++.h>
using namespace std;


char s[20000];
int n = 0;


char pop() {
    return s[n--];
}
void push(int val) {
    s[++n] = val;
}


int main(void) {
    return 0;
}

STL#

#include <bits/stdc++.h>
using namespace std;


int main(void) {
    stack<int> s;      // 定义一个栈，栈中元素类型为int
    s.push(5);         // 将元素5压入栈顶
    s.pop();           // 弹出栈顶元素, 但不返回其值
    s.top();           // 返回栈顶元素, 但不删除该元素
    s.size();          // 返回栈中元素的个数
    s.empty();         // 判断栈是否为空，空则返回true，非空返回false


    return 0;
}

括号匹配#

#include <bits/stdc++.h>
using namespace std;
int main() {
    stack<char> s;
    string str;
    cin >> str;
    for (int i = 0; i < str.length(); i++) {
        if (str[i] == '(') {
            s.push('(');
        } else {
            if (s.empty()) {
                cout << "no" << endl;
                return 0;
            }
            s.pop();
        }
    }
    if (s.empty()) {
        cout << "yes" << endl;
    } else {
        cout << "no" << endl;
    }
     return 0;
}


队列#

队列 FIFO(first in first out)


手写队列#

#include <bits/stdc++.h>
using namespace std;


int q[20000];
int head = 1, tail = 0;


int pop() {
    if (head <= tail) {
        return q[head++];
    }
}


void push(int val) {
    q[++tail] = val;
}


int main(void) {
    return 0;
}

STL#

#include <bits/stdc++.h>
using namespace std;


int main(void) {
    queue<int> q;     // 定义一个队列，队列中元素类型为int
    q.push(5);        // 将元素5入队，放入队尾
    q.pop();          // 队首元素出队，但不返回其值
    q.front();        // 返回队首元素，但不删除该元素
    q.size();         // 返回队列中元素的个数
    q.empty();        // 判断队列是否为空，空则返回true，非空返回false


    return 0;
}

约瑟夫环#

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    queue<int> q;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        q.push(i);
    }
    int cur = 0;
    while (!q.empty()) {
        cur++;
        if (cur == m) {
            cout << q.front() << " ";
            q.pop();
            cur = 0;
        } else {
            q.push(q.front());
            q.pop();
        }
    }
    return 0;
}


图#

拓扑排序（用邻接表）

课程安排#

#include <bits/stdc++.h>
using namespace std;
unordered_map<int, vector<int>> adj;    // 定义个桶（即邻接表），桶的值为整型，位置为一个vector数组
int inDegree[200000];
int main() {
    int n,m; cin>>n>>m;
    stack<int> s;
    for (int i = 1; i<= m; i++) {       //该for循环为读图操作
        int x,y;
        cin >> x >> y;
        adj[x].push_back(y); //邻接表操作， 在课程编号为x的课程的vector数组里放入编号为y的课程，化为图即为x -> y
        inDegree[y] += 1;    //前置课程多了一个，等于该后置课程的入度加一
    }
    for (int i= 1; i<= n; i++) {
        if (inDegree[i]==0) { //将入度为零的（即没有前置课程）的课程放入栈s中，
            s.push(i);
        }
    }
    while (!s.empty()) {        //当栈s不为空时
        int cur = s.top();        //cur为当前入度最少的结点
        cout << s.top() << " ";
        s.pop();                //将该入度最少的结点弹出栈，即学习完该课程
        for (int i = 0; i < adj[cur].size(); i++) {        //该for循环作用为找出在刚刚弹出的结点（即刚学完的课程） 的桶中（即图中该结点指向的结点 ），在弹出该结点后入度为零的结点，将其压入栈顶，表示目前要最先学的课程
            if (inDegree[adj[cur][i]] - 1 == 0) {
                s.push[adj[cur][i]];
            }
        }
    }
    return 0;
}
  //注意：有多个结点入度为零时，那栈顶弹出的只有其中之一，接下来栈顶又会压入删去刚才弹出的那个结点后入度为零的，会把最开始的剩余结点覆盖，输出顺序不太对，但没关系，不用管


二叉树#

二叉树 相当于一个族谱 想要知道每个家族成员，那就需要遍历


有几种不同的遍历方法，用如下二叉树来举例 1 2 3 4 5 6 7 1、层序遍历 从上往下一层一层的遍历 1 23 456 7


前序遍历#

递归思想，到了无法满足顺序时返回到上一层（下同），顺序是 中左右 1 2 4 5 7 3 6

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
    int l, r;
};


TreeNode tree[200000];


void preOrder(int root) { // void没有返回值
    if (root == -1) {
        return;
    }
    preOrder(tree[root].r);
    preOrder(tree[root].l);
    printf("%d ", root);
}


int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &tree[i].l, &tree[i].r);
    }
    preOrder(1);
    return 0;
}

中序遍历#

顺序是 左中右， 也可以通过所有数在竖列上的位置从左到右遍历，4 2 7 5 1 6 3

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
    int l, r;
};


TreeNode tree[200000];


void preOrder(int root) { // void没有返回值
    if (root == -1) {
        return;
    }
    preOrder(tree[root].l);
    printf("%d ", root);
    preOrder(tree[root].r);
}


int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &tree[i].l, &tree[i].r);
    }
    preOrder(1);
    return 0;
}

后序遍历#

顺序是 左右中， 4 7 5 2 6 3 1

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
    int l, r;
};


TreeNode tree[200000];


void preOrder(int root) { // void没有返回值
    if (root == -1) {
        return;
    }
    preOrder(tree[root].l);
    preOrder(tree[root].r);
    printf("%d ", root);
}


int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &tree[i].l, &tree[i].r);
    }
    preOrder(1);
    return 0;
}


Hash#

Hash（哈希） 数组下标下可以装字符，数字


单词统计#

#include <bits/stdc++.h>
//#include <tr1/unordered_map>  //版本问题，比赛中加上
using namespace std;
//using namespace std::tr1;
int main() {
    int n;
    int ans = 0;
    unordered_map<string, int> cnt;    //第一个为元素值 第二个为元素位置
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string tmp;
        cin >> tmp;
        cnt[tmp]++;
        ans = max(ans, cnt[tmp]);
    }
    cout << ans << endl;
}

字母统计#

#include <bits/stdc++.h>
//#include <tr1/unordered_map>
using namespace std;
//using namespace std::tr1;
int main() {
    string s;
    int ans = 0;
    unordered_map<char, int> cnt;
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        cnt[s[i]]++;
        ans = max(ans, cnt[s[i]]);
    }
    cout << ans << endl;
    return 0;
}

数字统计#

#include <bits/stdc++.h>
//#include <tr1/unordered_map>
using namespace std;
//using namespace std::tr1;
int main() {
    int n;
    cin >> n;
    unordered_map<int, int> cnt;
    for (int i = 1; i <= n; i++) {
        int tmp;
        cin >> tmp;
        cnt[tmp]++;
    }
    cout << cnt.size() << endl;
    return 0;
}


算法#


高精度#

高精度：因为int型范围有限，无法存储大整数，所以用字符串形式输入大整数，再转成int型存入数组中，用数组进行运算


加法#

#include <bits/stdc++.h>
using namespace std;


int a[501], b[501], c[502];


int main() {
  string x, y;
  cin >> x >> y;
  int len = max(x.length(), y.length());
  for (int i = len-1; i >= 0; i--) a[len-i] = x[i] - '0';   //将x倒着存进数组a,将字符转为整型
  for (int i = len-1; i >= 0; i--) b[len-i] = y[i] - '0';
  for (int i = 1; i <= len; i++) {
    c[i] += a[i] + b[i];
    c[i+1] = c[i] / 10;    //模拟进位
    c[i] %= 10;
  }
  if (c[len+1]) {   //进位可能导致长度加一
    len++;
  }
  for (int i = len; i >= 1; i--) {    //倒回来输出
    cout << c[i];
  }
  return 0;
}

乘法#

#include <bits/stdc++.h>
using namespace std;


int a[5010], b[5010], c[5020];


int main() {
  string x, y;
  cin >> x >> y;
  int lenx = x.length(); int leny = y.length();
  for (int i = lenx-1; i >= 0; i--) a[lenx-i] = x[i] - '0';
  for (int i = leny-1; i >= 0; i--) b[leny-i] = y[i] - '0';
  for (int i = 1; i <= lenx; i++) {   //模拟竖式乘法
    for (int j = 1; j <= leny; j++) {
      c[i+j-1] += a[i] * b[j];     //错位相加
    }
  }
  int len = lenx + leny;    //乘得的积的长度不大于两数长度之和
  for (int i = 1; i <= len; i++) {
    c[i+1] += c[i] / 10;    //模拟进位
    c[i] %= 10;
  }
  for (; !c[len] ;) {     //去掉先导零
    len--;
  }
  for (int i = max(1,len); i >= 1; i--) {    //倒回来输出
    cout << c[i];
  }
  return 0;
}

重载板子#

#include <bits/stdc++.h>
using namespace std;
struct Int{
  int len;
  int a[155];
  void init(){
    len=0;
    memset(a,0,sizeof a);
  }
  Int(){init();}
  Int(int x){
    init();
    if(x==0) ++len;
    while(x){
      a[++len]=x%10;
      x/=10;
    }
  }
  Int operator=(int x){
    init();
    if(x==0) ++len;
    while(x){
      a[++len]=x%10;
      x/=10;
    }
    return *this;
  }
  Int operator=(Int x){
    init();
    len=x.len;
    for(int i=1;i<=len;i++) a[i]=x.a[i];
    return *this;
  }
  void print(){
    for(int i=len;i>0;i--){
      printf("%d",a[i]);
    }
  }
};
Int operator+(const Int a,const Int b){
  Int ans;
  ans.len=max(a.len,b.len);
  for(int i=1;i<=ans.len;i++){
    if(i<=a.len) ans.a[i]+=a.a[i];
    if(i<=b.len) ans.a[i]+=b.a[i];
    ans.a[i+1]+=ans.a[i]/10;
    ans.a[i]%=10;
  }
  while(ans.a[ans.len+1]>0) ans.a[ans.len+1]+=ans.a[ans.len]/10,ans.a[ans.len]%=10,ans.len++;
  return ans;
}


Int a[4] = {1,1,1,1};
Int b[4] = {1,999,1,1};


int main() {
  (a[1]+b[1]).print();   //输出为1000
  return 0;
}


排序#


归并#

主要体现分治思想，复杂度O(nlogn)


int a[MAXN]; int b[MAXN];


void merge(int l, int mid, int r) {
  memset(b,0,sizeof(b));
  int i = l, j = mid+1, k = 0;
  while(i<=mid&&j<=r) {
    if (a[i]<=a[j]) b[++k] = a[i++];
    else b[++k] = a[j++];
  }
  while(i<=mid) b[++k] = a[i++];
  while(j<=r) b[++k] = a[j++];
  for (int i = 1; i <= k; i++) a[l++] = b[i];
}


void mergesort(int l, int r) {
  if (l < r) {
    int mid = l+r>>1;
    mergesort(l,mid);
    mergesort(mid+1,r);
    merge(l,mid,r);
  }
  return;
}

快排#

在数组中随机选择一个数作为标准，比标准小的放标准左边，大的放右边，然后递归分治


#include <bits/stdc++.h>
using namespace std;


int a[2000000];


void qsort(int a[], int l, int r) {
    int i = l, j = r;
    int p = a[rand() % (r - l + 1) + l];
             // ① 如何选取基准数（pivot）No.2 a[(r - l) / 2 + l] No.3 a[l]
    while (i <= j) {
        while (a[i] < p) i++;            // ② 与pivot相等的数，要不要交换？
        while (a[j] > p) j--;
        if (i <= j) {                    // ③ 为什么要写if？为什么要加等号？
            swap(a[i++], a[j--]);
        }
    }


    if (l < j) qsort(a, l, j);           // ④ 这两条语句什么含义
    if (i < r) qsort(a, i, r);
}


int main(void) {
    int n;


    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }


    qsort(a, 1, n);


    for (int i = 1; i <= n - 1; i++) {
        printf("%d ", a[i]);
    }
    printf("%d\n", a[n]);
}


暴力枚举#

枚举，很暴力！ 将数据全部枚举一遍，加以判断或统计 如果全部枚举会超范围，就要考虑更换枚举的元素或剪枝（减少枚举量），即优化枚举


循环枚举-烤鸡#

#include <bits/stdc++.h>
#define rep(a, i, j) for (int a = i; a <= j; a++)     //利用宏（define）构造语句的功能，简化for循环，前者等价于后者
using namespace std;
int main() {
  int n, a, b, c, d, e, f, g, h, i, j;
  scanf("%d", &n);
  int ans = 0;
  rep(a, 1, 3) rep(b, 1, 3) rep(c, 1, 3) rep(d, 1, 3) rep(e, 1, 3)      //优雅的枚举
    rep(f, 1, 3) rep(g, 1, 3) rep(h, 1, 3) rep(i, 1, 3) rep(j, 1, 3)
      if (a+b+c+d+e+f+g+h+i+j == n)
        ans++;
  printf("%d\n", ans);
  rep(a, 1, 3) rep(b, 1, 3) rep(c, 1, 3) rep(d, 1, 3) rep(e, 1, 3)
    rep(f, 1, 3)rep(g, 1, 3)rep(h, 1, 3)rep(i, 1, 3)rep(j, 1, 3)
      if (a+b+c+d+e+f+g+h+i+j == n)
        printf("%d %d %d %d %d %d %d %d %d %d\n", a, b, c, d, e, f, g, h, i, j);
  return 0;
}

排列枚举-全排列#

即将每种情况排列，用STL中函数next_permutation（start,end）即可解决 next_permutation函数求的是给定范围中按顺序的下一个排列，若没有下一个排列则返回0

#include <bits/stdc++.h>
using namespace std;


int a[11];


int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    a[i] = i;    //因为next需要数据范围，所以将i赋值到数组，而不是直接用i
  }
  do {        //用do-while是为了使最后一个排序能够输出，while和for需要特判
    for (int i = 1; i <= n; i++) {
      cout << setw(5) << a[i];  //场宽5
    }
    cout << endl;
  } while (next_permutation(a+1, a+1+n));    //指针操作 next所到之处，就是当前次数下的排列
  return 0;
}


递归#

递归 就是套娃，自己算自己 相当于一个公司，用函数调用手下去算 通过函数中的return不断返回，当不断返回然后不能返回了就输出或达到某种要求输出 一定要有退出条件

递归分为两种：数值类和非数值类， 数值类更加简单，根据函数定义直接找出递归边界和递归语句（注意要用if-else连接） 非数值类则需模拟，找规律，再重复数值类步骤


斐波那契数列#

#include <bits/stdc++.h>
using namespace std;
int calc(int a) {
  if (a == 1 || a == 2) {
    return 1;
  }
  return calc(a - 1) + calc(a - 2);
}
int main() {
  int k;
  cin >> k;
  cout << calc(k) << endl;
  return 0;
}

最大公约数#

#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}
int main() {
  int a, b;
  cin >> a >> b;
  cout << gcd(a, b) << endl;
  return 0;
}

二叉树最大节点#

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
  int val;
  int l, r;
};
vector<TreeNode> tree(200000);
int getMax(int root) {
  if (root == -1) {
    return INT_MIN;
  }
  int lMax = getMax(tree[root].l);
  int rMax = getMax(tree[root].r);
  int ans = max(lMax, rMax);
  ans = max(ans, tree[root].val);
  printf("%d ", ans);
  return ans;
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d %d %d", &tree[i].val, &tree[i].l, &tree[i].r);
  }
  getMax(1);
  return 0;
}


二分法#

二分法，就是把一组数砍成两段，中间的点跟所给数比，如果中间数大，那么去左边的数组，如果中间数小，那么去右边的数组


排序数组中查找#

#include <bits/stdc++.h>
using namespace std;
int a[200000];
int n;
int find(int t) {
  int l = 1, r = n;
  while (l <= n) {
    int mid = l + (r - l) / 2;
    if (a[mid] == t) {
      return mid;
    }
    if (a[mid] < t) {
      l = mid + 1;
    }
    if (a[mid] > t) {
      r = mid - 1;
    }
  }
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  int m;
  cin >> m;
  while (m--) {
    int t;
    cin >> t;
    cout << find(t) << endl;
  }
  return 0;
}


DFS#

又称深度优先搜索或回溯法


摸球问题#

#include <bits/stdc++.h>
using namespace std;
int n, m;
void dfs(int x, string path) {
  if (x == n + 1) {
    printf("%s\n", path.c_str());
    return;
  }
  for (int i = 1; i <= m; i++) {
    dfs(x + 1, path + (char)(i + '0'));
  }
}
int main() {
  scanf("%d %d", &n, &m);
  dfs(1, "");
  return 0;
}

全排列#

#include <bits/stdc++.h>
using namespace std;
int n;
bool v[100];
void dfs(int x, string path) {
  if (x == n + 1) {
    printf("%s\n", path.c_str());
    return;
  }
  for (int i = 1; i <= n; i++) {
    if (v[i]) {
      continue;
    }
    v[i] = true;
    dfs(x + 1, path + (char)(i + '0'));
    v[i] = false;
  }
}
int main() {
  scanf("%d", &n);
  dfs(1, "");
  return 0;
}
古早的笔记(自不用)
https://c0d4.ink/posts/古早的笔记-自不用/
作者
Coda
发布于
2023-09-07
许可协议
CC BY-NC-SA 4.0
字符串
计算机基础知识
© 2026 Coda. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari