菜单 学习猿地 - LMONKEY

VIP

开通学习猿地VIP

尊享10项VIP特权 持续新增

知识通关挑战

打卡带练!告别无效练习

接私单赚外块

VIP优先接,累计金额超百万

学习猿地私房课免费学

大厂实战课仅对VIP开放

你的一对一导师

每月可免费咨询大牛30次

领取更多软件工程师实用特权

入驻
462
0

C++算法模板集合

原创
05/13 14:22
阅读数 35345

我的常用刷题网站:http://218.5.5.242:9018/JudgeOnline/

         https://www.luogu.com.cn/

排序

选择排序(selection sort)

void selection(int n,int* a){
    for (int i = 0;i < n;i++){
        for (int j = i + 1;j < n;j++){
            if (a[i] > a[j]){
                swap(a[i],a[j]);
            }
        }
    }
}
View Code

冒泡排序(bubble sort)

void bubble(int n,int* a){
    for (int i = 0;i < n;i++){
        for (int j = 0;j < n - 1;j++){
            if (a[j] > a[j + 1]){
                swap(a[j],a[j+1]);
            }
        }
    }
}
View Code

快速排序(quick sort)

void quicksort(int l,int r,int* a){
    int i,j,mid;
    i = l;j = r;
    mid = a[(i + j) / 2];
    do{
        while (a[i] < mid) i++;
        while (a[j] > mid) j--;
        if (i <= j){
            swap(a[i],a[j]);
            i++;j--;
        }
    }while (i <= j);
    if (l < j) quicksort(l,j,a);
    if (i < r) quicksort(i,r,a);
}
View Code

 

查找

枚举查找

bool search(int n,int* a,int x){
    for (int i = 0;i < n;i++){
        if (a[i] == x){
            return true;
        }
    }
    return false;
}
View Code

二分查找(binary search)

bool binary_search(long long* a,int x,int left,int right){
    while(left <= right){    
        int mid = (left + right) / 2;
        if(a[mid] > x) right = mid - 1;
        else if(a[mid] < x) left = mid + 1;
        else return true;
    }
    return false;
}
View Code

 

搜索

深度优先搜索(DFS)求连通块

void dfs(int x,int y,int id){        // id是连通块记号 
    if (是否越界) return;
    if (搜索过或不是指定符号) return;
    标记已搜索; 
    搜索下一步; 
}
View Code

这只是一个概括,详细代码样例参见C++算法代码——细胞问题

 

创建树

#include <iostream>
using namespace std;
typedef struct node;
typedef node *tree;

struct node{
    int data;               // 结点数值
    tree left,right;        // 左子树和右子树 
};
tree bt;
View Code

二叉树遍历

#include <iostream>
using namespace std;
typedef struct node;
typedef node *tree;

struct node{
    int data;                // 结点数值
    tree left,right;        // 左子树和右子树 
};
tree bt;

void preorder(tree bt){
    if (bt){                // 判断不为空二叉树 
        cout << bt.data;
        preorder(bt.left);    // 递归遍历左子树 
        preorder(bt.right); // 递归遍历右子树 
    }
}
void inorder(tree bt){
    if (bt){                // 判断不为空二叉树 
        inorder(bt.left);    // 递归遍历左子树 
        cout << bt.data;
        inorder(bt.right); // 递归遍历右子树 
    }
}
void postorder(tree bt){
    if (bt){                // 判断不为空二叉树 
        postorder(bt.left);    // 递归遍历左子树 
        postorder(bt.right); // 递归遍历右子树 
        cout << bt.data;
    }
}
View Code

 

图论

邻接矩阵

#include <iostream>
#include <cstring>
using namespace std;

double G[101][101];
int main(){
    int u,v,t,n,m;                        // 结点u到结点v的节点值为t
    cin >> n;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= n;j++){
            G[i][j] = 0x7fffffff;        // 初始化为无穷大 
        }
    }
    // 或者使用memset(G,0x7fffffff,sizeof(G))来初始化
    /*
    若是int类型数组,则采用memset(G,0x7f,sizeof(G)))
    0x7fffffff表示无穷大,若是无向图,那么要写成memset(G,0,sizeof(G))
    也可以定义成memset(G,oxaf,sizeof(G)),全都定义成很小的数。 
    */
    cin >> m;
    for (int i = 1;i <= m;i++){
        cin >> u >> v >> t;
        G[u][v] = t;G[v][u] = t;        // 邻接矩阵的值 
    }
    // 输出
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= n;j++){
            cout << G[i][j] << " ";
        }
        cout << endl;
    } 
    return 0;
}
View Code

邻接表

#include <iostream>
using namespace std;

const int maxn = 10001;
int head[maxn],num,n,m,u,v,t;
struct G{                            // 结构体图G 
    int next,to,dis;
}g[maxn];
void add(int u,int v,int t){        // 添加从结点u到v权值为t的单向边 
    g[++num].next = head[u];
    g[num].to = v;
    g[num].dis = t;
    head[u] = num;
}

int main(){
    num = 0;
    cin >> n >> m;                    // 输入 
    for (int i = 1;i <= m;i++){
        cin >> u >> v >> t;            // 结点u到结点v的权值为t 
        add(u,v,t);
    }
    return 0;
}
View Code

 最短路

 

数学专题

判断质数

bool prime(int n){
    for (int i = 2;i <= sqrt(n);i++){
        if (n % i == 0) return false;
    }
    return true;
}
View Code

 

 for循环宏定义

1 #define _for_1(i,a,b) for(i = (a);i <= (b);i++)
2 #define _for_2(i,a,b) for(i = (a);i >= (b);i--)
3 
4 // 可以这样应用:_for_1(i,1,n)
View Code

 

g++运行

>g++ 文件名.cpp -o 文件名
>./文件名
View Code

 

代码作者亲测,作者将持续更新……

发表评论

0/200
462 点赞
0 评论
收藏
为你推荐 换一批