算法基础模板()

  • 线性表链表
  • 链表
  • Tree遍历二叉搜索树AlV树
  • 遍历
  • 二叉搜索树
  • AlV树
  • 并查集并查集的实现
  • 并查集的实现
  • 图论算法遍历CreateDFS(Depth First Search)BFS(Breadth First Search)最短路径FloydDijkstraBellman-Ford——解决负权变应用:PTA-advande-1003 DijkstraBellman-Ford最小生成树PrimKruskal
  • 遍历CreateDFS(Depth First Search)BFS(Breadth First Search)
  • Create
  • DFS(Depth First Search)
  • BFS(Breadth First Search)
  • 最短路径FloydDijkstraBellman-Ford——解决负权变应用:PTA-advande-1003 DijkstraBellman-Ford
  • Floyd
  • Dijkstra
  • Bellman-Ford——解决负权变
  • 应用:PTA-advande-1003 DijkstraBellman-Ford
  • PTA-advande-1003 Dijkstra
  • Bellman-Ford
  • 最小生成树PrimKruskal
  • Prim
  • Kruskal
  • 数学算法进位制字符串加法
  • 进位制
  • 字符串加法
  • 排序冒泡排序优化:如果已经排好序,即没有交换,则退出循环选择排序插入排序希尔排序归并排序快速排序堆排序计数排序桶排序基数排序
  • 冒泡排序优化:如果已经排好序,即没有交换,则退出循环
  • 优化:如果已经排好序,即没有交换,则退出循环
  • 选择排序
  • 插入排序
  • 希尔排序
  • 归并排序
  • 快速排序
  • 堆排序
  • 计数排序
  • 桶排序
  • 基数排序

线性表

链表

操作:头插、尾插、插入指定数据、删除、反转

操作:头插、尾插、插入指定数据、删除、反转

 #include<stdio.h>
#include<stdlib.h>

typedef struct Node
{
    int data;
    struct Node *next;
}Node;

void printlist(Node *L);
Node* head_insert();//头插
Node* tail_insert();//尾插
void insert(Node*L,int n);//插入指定数据
void deletelist(Node *L,int n);//删除
Node* reverse(Node *L);//反转d
Node* combine(Node*L1,Node*L2);//链接
int ClearList(Node *L);//整个链表的删除

int main()
{   
    Node *L1;
    L1 = tail_insert();  
    //deletelist(L1,3);
    insert(L1,10);
    printlist(L1);

    //L1 = reverse(L1);
    // printlist(L1);
    

    // Node *L2;
    // L2 = tail_insert();
    // printlist(L2);

    // Node *L3;
    // L3 = combine(L1,L2);
    // printlist(L3);

    // ClearList(L1);
    // ClearList(L2);
    // ClearList(L3);

    return 0;
}
void printlist(Node *L)
{
    Node *p = L->next;
    while(p)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}
Node* head_insert()
{
    Node *head,*p;
    head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    int temp;
    while(scanf("%d",&temp)&&temp!=-1)
    {
        p = (Node*)malloc(sizeof(Node));
        p->data = temp;
        p->next = head->next;
        head->next = p;
    }
    return head;
}
Node* tail_insert()
{
    Node *head,*p,*tail;
    head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    tail = head;
    int temp;
    while(scanf("%d",&temp)&&temp!=-1)
    {
        p =(Node*)malloc(sizeof(Node));
        p->data = temp;
        tail->next = p;
        tail = p;
    }
    tail->next = NULL;
    return head;
}
void insert(Node *L,int n)
{
    Node *p=L,*new;
    while(p->next != NULL && p->next->data<n)
    {
        p = p->next;
    }
    new = (Node*)malloc(sizeof(Node));
    new->data = n;
    new->next = p->next;
    p->next = new;
    
}

void deletelist(Node *L,int n)
{
    Node *p=L->next,*pre=L;
    while(p!=NULL)
    {
        if(p->data==n){
            pre->next = p->next;
            free(p);
        }
        else
            pre = pre->next;
        p = pre->next;
    }
}
Node* reverse(Node *L)
{
    Node *p = L->next,*head,*tail=NULL;
    head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    while(p)
    {
        tail = p->next;
        p->next = head->next;
        head->next = p;
        p = tail;
    }
    return head;

}
Node* Reverse(Node *L, int k)
{
    Node *new, *old, *temp;
    new = L->next;
    old = new->next;
    int cnt = 1;
    while(cnt < k)
    {
        temp = old->next;
        old->next = new;
        new = old;
        old = temp;
        cnt++;
    }
    L->next->next = old;
    L->next = new;
    return L;
} 
Node* combine(Node*L1,Node*L2)
{
    if(!L1->next && L2->next)
        return L2;
    if(L1->next && !L2->next)
        return L1;
    if(!L1->next && !L2->next)
        return NULL;

    Node *p = L1->next,*q = L2->next,*head,*tail,*c;
    head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    tail = head;
    while(p&&q)
    {
        if(p->data<q->data){
            c = p;
            p = p->next;
        }
        else{
            c = q;
            q = q->next;
        }
        tail->next = c;
        tail = c;
    }
    if(p)
        tail->next = p;
    if(q){
        tail->next = q;
    }
    return head;
}
int ClearList(Node *L)
{
    Node *p,*q;
    p = L->next;
    while(p){
        q = p->next;
        free(p);
        p = q;
    }
    L->next = NULL;
    
    return 0;
}
/*
1 3 5 7 9 11 12 13 -1
2 4 6 8 10 -1
*/

Tree

遍历

前序: root->left->right
中序: left->root->right
后续: right->left->root
层序: 用队列

前序: root->left->right

中序: left->root->right

后续: right->left->root

层序: 用队列

void InorderTraversal( BinTree BT )
{
    if(BT)
    {
        InorderTraversal(BT->Left);
        printf(" %c", BT->Data);
        InorderTraversal(BT->Right);
    }
}
void PreorderTraversal( BinTree BT )
{
    if(BT)
    {
        printf(" %c", BT->Data);
        PreorderTraversal(BT->Left);
        PreorderTraversal(BT->Right);
    }
}
void PostorderTraversal( BinTree BT )
{
    if(BT)
    {
        PostorderTraversal(BT->Left);
        PostorderTraversal(BT->Right);
        printf(" %c", BT->Data);
    }
}
void LevelorderTraversal( BinTree BT )
{
        BinTree q[100], p;
    int front, rear;
    front = rear = 0;
    if(!BT)
        return;
    else
    {
        q[rear++] = BT;
        while(front != rear)
        {
            p = q[front++];
            printf(" %c", p->Data);
            if(p->Left)
                q[rear++] = p->Left;
            if(p->Right)
                q[rear++] = p->Right;
        }
    }
}
//中序遍历
void InOrderWithoutRecursion2(BTNode* root)
{
    //空树
    if (root == NULL)
        return;
    //树非空
    BTNode* p = root;
    stack<BTNode*> s;
    while (!s.empty() || p)
    {
        if (p)
        {
            s.push(p);
            p = p->lchild;
        }
        else
        {
            p = s.top();
            s.pop();
            cout << setw(4) << p->data;
            p = p->rchild;
        }
    }
}

求二叉树的高度

求二叉树的高度

int GetHeight( BinTree BT ){
    int HL,HR,MaxH;
    if(BT){
        HL = GetHeight(BT->Left);
        HR = GetHeight(BT->Right);
        MaxH = (HL>HR)?HL:HR;
        return MaxH+1;
    }else
        return 0;
}	

二叉搜索树

插入、删除、查找

插入、删除、查找

BinTree Insert(BinTree BST, ElementType X)
{
    if (BST == NULL)
    {
        BST = malloc(sizeof(struct TNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    }
    else if (X < BST->Data)
        BST->Left = Insert(BST->Left, X);
    else if (X > BST->Data)
        BST->Right = Insert(BST->Right, X);

    return BST;
}
BinTree Delete(BinTree BST, ElementType X)
{
    Position TemCell;
    if (BST == NULL)
        printf("Not Found\n");
    else if (X < BST->Data)
        BST->Left = Delete(BST->Left, X);
    else if (X > BST->Data)
        BST->Right = Delete(BST->Right, X);
    //左右儿子都存在
    else if (BST->Left && BST->Right)
    {
        TemCell = FindMin(BST->Right);
        BST->Data = TemCell->Data;
        BST->Right = Delete(BST->Right, BST->Data);
    }   
    else//z
    {
        TemCell = BST;
        if (BST->Left == NULL)
            BST = BST->Right;
        else if (BST->Right == NULL)
            BST = BST->Left;
        free(TemCell);
    }
    return BST;
}
Position Find(BinTree BST, ElementType X)
{
    if (BST == NULL)
        return NULL;
    if(X < BST->Data)
        return Find(BST->Left, X);
    else if(X > BST->Data)
        return Find(BST->Right, X);
    else
        return BST;
}
Position FindMin(BinTree BST)
{
    if (BST != NULL)
        while (BST->Left != NULL)
            BST = BST->Left;
    return BST;
}
Position FindMax(BinTree BST)
{
    if (BST != NULL)
        while (BST->Right != NULL)
            BST = BST->Right;
    return BST;
}

AlV树

1、左-左型:做右旋。
2、右-右型:做左旋转。
3、左-右型:先做左旋,后做右旋。

1、左-左型:做右旋。

2、右-右型:做左旋转。

3、左-右型:先做左旋,后做右旋。

4、右-左型:先做右旋,再做左旋。

4、右-左型:先做右旋,再做左旋。

//定义节点
class AvlNode {
   int data;
   AvlNode lchild;//左孩子
   AvlNode rchild;//右孩子
   int height;//记录节点的高度   
}

//在这里定义各种操作
public class AVLTree{
   //计算节点的高度
   static int height(AvlNode T) {
       if (T == null) {
           return -1;
       }else{
           return T.height;
       }
   }

   //左左型,右旋操作
   static AvlNode R_Rotate(AvlNode K2) {
       AvlNode K1;

       //进行旋转
       K1 = K2.lchild;
       K2.lchild = K1.rchild;
       K1.rchild = K2;

       //重新计算节点的高度
       K2.height = Math.max(height(K2.lchild), height(K2.rchild)) + 1;
       K1.height = Math.max(height(K1.lchild), height(K1.rchild)) + 1;

       return K1;
   }

   //进行左旋
   static AvlNode L_Rotate(AvlNode K2) {
       AvlNode K1;

       K1 = K2.rchild;
       K2.rchild = K1.lchild;
       K1.lchild = K2;

       //重新计算高度
       K2.height = Math.max(height(K2.lchild), height(K2.rchild)) + 1;
       K1.height = Math.max(height(K1.lchild), height(K1.rchild)) + 1;

       return K1;
   }

   //左-右型,进行右旋,再左旋
   static AvlNode R_L_Rotate(AvlNode K3) {
       //先对其孩子进行左旋
       K3.lchild = R_Rotate(K3.lchild);
       //再进行右旋
       return L_Rotate(K3);
   }

   //右-左型,先进行左旋,再右旋
   static AvlNode L_R_Rotate(AvlNode K3) {
       //先对孩子进行左旋
       K3.rchild = L_Rotate(K3.rchild);
       //在右旋
       return R_Rotate(K3);
   }

   //插入数值操作
   static AvlNode insert(int data, AvlNode T) {
       if (T == null) {
           T = new AvlNode();
           T.data = data;
           T.lchild = T.rchild = null;
       } else if(data < T.data) {
           //向左孩子递归插入
           T.lchild = insert(data, T.lchild);
           //进行调整操作
           //如果左孩子的高度比右孩子大2
           if (height(T.lchild) - height(T.rchild) == 2) {
               //左-左型
               if (data < T.lchild.data) {
                   T = R_Rotate(T);
               } else {
                   //左-右型
                   T = R_L_Rotate(T);
               }
           }
       } else if (data > T.data) {
           T.rchild = insert(data, T.rchild);
           //进行调整
           //右孩子比左孩子高度大2
           if(height(T.rchild) - height(T.lchild) == 2)
               //右-右型
               if (data > T.rchild.data) {
                   T = L_Rotate(T);
               } else {
                   T = L_R_Rotate(T);
               }
       }
       //否则,这个节点已经在书上存在了,我们什么也不做
       
       //重新计算T的高度
       T.height = Math.max(height(T.lchild), height(T.rchild)) + 1;
       return T;
   }
}

并查集

并查集的实现

#define MAX_N 100000
int par[MAX_N];
int rank[MAX_N];

void init (int n) {
    for (int i = 0; i < n; i++) {
        par[i] = i;
        rank[i] = 0;
    }
}

//查询树的根
int find(int x) {
    if (par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);
    }
}

//合并x和y所属集合
void unite (int x, int t) {
    x = find(x);
    y = find(y);
    if (x == y)  return;
    if (rank[x] < rank[y]) {
        par[x] = y;
    } else {
        par[y] = par[x];
        if (rank[x] == rank[y]) rank[x]++;
    }
}
//判断x和y是否属于同意集合
bool same (int x, int y) {
    return find (x) == find (y);
}

图论算法

遍历

Create

int e[10][10],book[10],n;
void Create()
{
	for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (i == j)
                e[i][j] = 0;
            else
                e[i][j] = 99999999;
    for (i = 1; i <= m; i++)
    {
        scanf("%d %d", &a, &b);
        e[a][b] = e[b][a] = 1;
    }
}

DFS(Depth First Search)

#include <stdio.h>

int e[10][10], book[10], n,sum;

void Dfs(int cur)
{
    book[cur] = 1;
    for(int i = 1; i <= n; i++)
       if(book[i] == 0 && e[cur][i] == 1)
           dfs(i);
    return;
}
/*
5 5
1 2
1 3
1 5
2 4
3 5
*/
//Dfs: 1 2 4 3 5

BFS(Breadth First Search)

void BFS(int e[][])
{
    int queue[10] = {0}, head, tail,i;
    head = tail = 1;
    book[1] = 1;
    queue[tail++] = 1;

    while(head < tail)
    {
        int cur = queue[head++];
        for (i = 1; i <= n; i++)
        {
            if(book[i] == 0 && e[cur][i] == 1)
            {
                queue[tail++] = i;
                book[i] = 1;
            }
        }
    }
    printf("BFS:");
    for (i = 1; i <= n; i++)
        printf(" %d",queue[i]);
}

最短路径

Floyd Dijkstra Bollman-Ford 优先队列的
Bellman-ford
空间复杂度 O(N2) O(M) O(M) O(M)
时间复杂度 O(N3) O(N2) O(MN) O(NM)
使用情况 稠密图和
顶点关系密切
稠密图和顶点关系密切 稀疏图
和边关系密切
稀疏图和边关系密切
负权 可以 不可 可以 可以

Floyd

求任意顶点到任意顶点的最短路径

求任意顶点到任意顶点的最短路径

for(k = 1; k <= n; k++)
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            if(e[i][j] > e[i][k] + e[k][j])
                e[i][j] = e[i][k] + e[k][j];

Dijkstra

基本思想:
每次找到离源点最近的一个顶点,然后以该顶点为中心进行扩展,最终得到远点到其余所有点的最短路径

基本思想:

每次找到离源点最近的一个顶点,然后以该顶点为中心进行扩展,最终得到远点到其余所有点的最短路径

#include<iostream>
using namespace std;
int n, m, s, d;
int e[501][501], dis[501], path[501];
bool visit[501];
const int inf = 99999999;
void dfs(int cur)
{
    if(cur == s){
        printf("%d", cur);
        return;
    }
    dfs(path[cur]);
    printf("->%d", cur);
}
int main()
{
    cin >> n >> m >> s >> d;
    fill(e[0], e[0] + 501 * 501, inf);
    fill(dis, dis + 501, inf);
    for (int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        e[a][b] = e[b][a] = c;
    }
    dis[s] = 0;
    for (int i = 1; i <= n; i++){
        int min = inf, u = -1;
        for (int j = 1; j <= n; j++){
            if(visit[j] == false && dis[j] < min){
                min = dis[j];
                u = j;
            }
        }
        if(u == -1)
            break;
        visit[u] = true;
        for (int v = 1; v <= n; v++){
            if(visit[v] == false && e[u][v] != inf){
                if(dis[v] > dis[u] + e[u][v]){
                    dis[v] = dis[u] + e[u][v];
                    path[v] = u;
                }
            }
        }
    }
    dfs(d);
    printf("\n%d", dis[d]);
    return 0;
}
/*
6 9 1 6
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
*/
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
struct edge{
    int to, cost;
};
typedef pair<int, int> P;
int n, m, s, d;
int dis[7], pre[7];
vector<edge> G[7];
const int inf = 99999999;
void dijkstra(int s)
{
    priority_queue<P, vector<P>, greater<P> > que;
    dis[s] = 0;
    que.push(P(0, s));
    while(!que.empty()){
        P p = que.top();
        que.pop();
        int v = p.second;
        if(dis[v] < p.first)
            continue;
        for(int i = 0; i < G[v].size(); i++){
            edge e = G[v][i];
            if (dis[e.to] > dis[v] + e.cost){
                dis[e.to] = dis[v] + e.cost;
                que.push(P(dis[e.to], e.to));
                pre[e.to] = v;
            }
        }
    }

}

int main()
{
    cin >> n >> m >> s >> d;
    fill(dis, dis + 7, inf);
    fill(pre, pre + 7, -1);
    for(int i = 1; i<= m; i++){
        int v;
        edge e;
        cin >> v >> e.to >> e.cost;
        G[v].push_back(e);
    }
    dijkstra(s);
    vector<int> path;
    for(int i = d; i != -1; i = pre[i])
        path.push_back(i);
    reverse(path.begin(), path.end());
    for(int i = 1; i <= n; i++)
        printf("%d ", dis[i]);
    printf("\n");
    for(auto it = path.begin(); it != path.end(); it++)
        printf("%d ", *it);
        
    return 0;
}
/*
6 9 1 6
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
*/

Bellman-Ford——解决负权变

核心代码:
看看能否通过u[i]->v[i](权值为w[i])这条边,使得1号顶点到v[i]号顶点的距离变短

核心代码:

看看能否通过u[i]->v[i](权值为w[i])这条边,使得1号顶点到v[i]号顶点的距离变短

for(k=1; k<=n-1; k++)
        for(i=1; i<=m; i++)
            if(dis[v[i]] > dis[u[i]] + w[i])
                dis[v[i]] = dis[u[i]] + w[i];

应用:

PTA-advande-1003 Dijkstra

#include<stdio.h>

int main()
{
    int n, m, c1, c2, a, b, c;
    int e[501][501],visit[501] = {0}, dis[501], weight[501], w[501] = {0}, num[501] = {0};
    const int inf = 99999999;
    scanf("%d %d %d %d", &n, &m, &c1, &c2);
    for(int i = 0; i < n; i++)
        scanf("%d",&weight[i]);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            e[i][j] = inf;
    for(int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        e[a][b] = e[b][a] = c; 
    }
    for(int i = 0; i < n; i++)
        dis[i] = inf;
    dis[c1] = 0;
    w[c1] = weight[c1];
    num[c1] = 1;
    for(int i = 0; i < n; i++)
    {
        int u = -1, min = inf;
        for(int j = 0; j < n; j++)
        {
            if(visit[j] == 0 && dis[j] < min)
            {
                u = j;
                min = dis[j];
            }
        }
        visit[u] = 1;
        if(u == -1)
            break;
        for(int v = 0; v < n; v++)
        {
            if(visit[v] == 0 && e[u][v] < inf)
            {
                if(dis[v] > dis[u] + e[u][v])
                {
                    dis[v] = dis[u] + e[u][v];
                    w[v] = w[u] + weight[v];
                    num[v] = num[u];
                }
                else if(dis[v] == dis[u] + e[u][v])
                {
                    num[v] += num[u];
                    if(w[v] < w[u] + weight[v])
                        w[v] = w[u] + weight[v];
                }
            }
        }
    }
    printf("%d %d", num[c2], w[c2]);
    return 0;
}
/*
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
*/

Bellman-Ford

#include<stdio.h>
void PrintPath(int n, int path[])
{
    if(path[n] == -1)
        return ;
    PrintPath(path[n],path);
    printf("%d->",path[n]);
}
int main()
{
    int dis[10],bak[10],i,k,n,m,u[10],v[10],w[10],check,flag;
    int inf = 99999999;
    scanf("%d%d",&n,&m);
    for(i=1; i<=m; i++)
        scanf("%d%d%d",&u[i],&v[i],&w[i]);
    for(i=1; i<=m; i++)
        dis[i] = inf;
    dis[1] = 0;
    int path[10];
    for(i = 0; i < 10; i++)
        path[i] = -1;
    //Bellman-Ford
    for(k=1; k<=n-1; k++)
    {   
        for(i=i; i<=n; i++) bak[i] = dis[i];

        for(i=1; i<=m; i++)
            if(dis[v[i]] > dis[u[i]] + w[i]){
                dis[v[i]] = dis[u[i]] + w[i];
                path[v[i]] = u[i];
            }
        check = 0;
        for(i=1; i<=n; i++) 
            if(bak[i] != dis[i])
            {
                check = 1;
                break;
            }
        if(check == 0)
            break;
    }
    flag = 0;
    for(i=1; i<=m; i++)
        if(dis[v[i]] > dis[u[i]] + w[i])
            flag = 1;
    if(flag==1)
        printf("此图有负权回路");
    else
    {
        for(i=1; i<=n; i++)
        printf("%d ",dis[i]);
    }
    printf("\n");
    PrintPath(5,path);
    printf("5");
    return 0;
}
/*
5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3
*/

最小生成树

Prim

#include<stdio.h>

int main()
{
    int n, m, i, j, k, min, t1, t2, t3;
    int e[7][7], dis[7], book[7] = {0};
    int inf = 99999999;
    int count = 0, sum = 0;
    scanf("%d %d", &n, &m);
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            if(i == j)  e[i][j] = 0;
            else    e[i][j] = inf;
        
    for(i = 1; i <= m; i++)
    {
        scanf("%d %d %d",&t1, &t2, &t3);
        e[t1][t2] = e[t2][t1] = t3;
    }
    for(i = 1; i <= n; i++)
        dis[i] = e[1][i];
    
    //Prim核心部分
    book[1] = 1;
    count++;
    while(count < n)
    {
        min = inf;
        for(i = 1; i <= n; i++)
        {
            if(book[i] == 0 && dis[i] < min)
            {
                min = dis[i];
                j = i;
            }
        }
        book[j] = 1;
        count++;
        sum += dis[j];
        for(k = 1; k <= n; k++)
        {
            if(book[k] == 0 && dis[k] > e[j][k])
                dis[k] = e[j][k];
        }
    }
    printf("%d",sum);
    return 0;
}
/*
6 9
2 4 11
3 5 13
4 6 3
5 6 4
2 3 6
4 5 7
1 2 1
3 4 9
1 3 2
*/

Kruskal

#include<stdio.h>
struct edge
{
    int u;
    int v;
    int w;
};
struct edge e[10];
int n, m;
int f[7] = {0}, sum = 0, count = 0;

void quicksort(int left, int right)
{
    int i, j;
    struct edge t;
    if(left > right)
        return;
    i = left;
    j = right;
    while(i != j)
    {
        while(e[j].w >= e[left].w && i < j)
            j--;
        while(e[i].w <= e[left].w  && i < j)
            i++;
        if(i < j)
        {
            t = e[i];
            e[i] = e[j]; 
            e[j] = t;
        }
    }
    t = e[left];
    e[left] = e[i];
    e[i] = t;
    quicksort(left, i-1);
    quicksort(i+1, right);
    return;
}
int Find(int f[], int v)
{
    while(f[v] > 0)
        v = f[v];
    return v;
}

int main()
{
    int i;
    scanf("%d %d", &n, &m);
    for(i = 1; i <= m; i++)
        scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w);
    quicksort(1, m);
    
    //Kruskalh
    for(i = 1; i <= m; i++)
    {
        int a = Find(f,e[i].u);
        int b = Find(f,e[i].v);
        if(a != b)
        {
            f[b] = a;
            count++;
            sum += e[i].w; 
        }
        if(count == n - 1)
            break;
    }
    printf("%d",sum);
    return 0;
}
/*
6 9
2 4 11
3 5 13
4 6 3
5 6 4
2 3 6
4 5 7
1 2 1
3 4 9
1 3 2
*/

数学算法

进位制

转换为10进制

转换为10进制

long long convert(string n, long long radix) {
 long long sum = 0;
 int index = 0, temp = 0;
 for (auto it = n.rbegin(); it != n.rend(); it++) {
 temp = isdigit(*it) ? *it - '0' : *it - 'a' + 10;
 sum += temp * pow(radix, index++);
 }
 return sum;
}

字符串加法

void add(string &n, string temp)
{
    int digit = 0;
    for(int i = n.length() - 1; i >= 0; i--)
    {
        n[i] = n[i] + temp[i] + digit - '0';
        digit = 0;
        if(n[i] > '9'){
            digit = 1;
            n[i] = n[i] - 10;
        }
    }
    if(digit == 1){
        n.insert(0,"1");
    }
}

排序

冒泡排序

void Bubble_Sort(int a[], int n)
{
    int i, j, c;
    for(i = 0; i < n-1; i++){
        for(j = 0; j < n - i; j++){
            if(a[j] > a[j+1]){
                c = a[j];
                a[j] = a[j+1];
                a[j+1] = c;
            }
        }
    }
}

优化:如果已经排好序,即没有交换,则退出循环

void Bubble_Sort(int a[], int n)
{
    int i, j, c;
    for(i = 0; i < n-1; i++){
        int flag = 1;
        for(j = 0; j < n - i; j++){
            if(a[j] > a[j+1]){
                flag = 0;
                c = a[j];
                a[j] = a[j+1];
                a[j+1] = c;
            }
        }
        if(flag == 1)
            break;
    }
}

选择排序

插入排序

void Insertion_Sort(int a[], int N)
{
    int i, j;
    for( i = 0; i < N; i++)
    {
        int temp = a[i];
        for( j = i; j > 0 && a[j -1] > temp; j--)
            a[j] = a[j - 1];
        a[j] = temp;
    }
}

希尔排序

void shell_sort(vector<int> &v, int n)
{
    int gap, i, j;
	for (gap = n / 2; gap > 0; gap /= 2) {
		for (i = gap; i < n; i++) {
			int temp = v[i];
			for (j = i - gap; j >= 0 && v[j] > temp; j-= gap)
				v[j + gap] = v[j];
			v[j + gap] = temp;
		}	
	}
}

归并排序

递归

void Merge(vector<int> &a, vector<int> &temp, int left, int mid, int right) {
	int i = left;
	int j = mid + 1;
	int k = 0;
	// 两个有序数组的合并
	while (i <= mid && j <= right) {
		if (a[i] < a[j])
			temp[k++] = a[i++];
		else 
			temp[k++] = a[j++];
	}
	// 只剩下一个数组没合并
	while (i <= mid) 
		temp[k++] = a[i++];
	while (j <= right)
		temp[k++] = a[j++];
	// 把辅助数组的值都拷贝要求的数组里
	for (int i = 0; i < k; i++)
		a[left++] = temp[i];
}
void Msort(vector<int> &a, vector<int> &temp, int left, int right) {
	if (left < right) {
		int mid= (left + right) / 2;
		Msort(a, temp, left, mid); 
		Msort(a, temp, mid + 1, right);
		Merge(a, temp, left, mid, right);
	}
} 

非递归

void mergesort(int a[], int temp[], int N)
{
    for(int i = 1; i < N; i *= 2){
        int left = 0;
        int mid = left + i -1;
        int right = mid + i;
        while(right < N){
            Merge(a, temp, left, mid, right);
            left = right + 1;
            mid = left + i -1;
            right = mid + i;
        }
        if(left < N && mid < N)
        	Merge(a, temp, left, mid, N-1);
    }
}

快速排序

步骤

  • 从数列中找到一个基准
  • 重新排列,比基准小的元素排在基准前面,比基准大的排在基准右边
  • 分别递归小于基准的元素和大于基准的元素
void quicksort(vector<int> &v, int l, int r) {
	if (l > r) // 注意跳出递归的条件
		return;
	int first = l, last = r, key = v[first];
    // 最终使 first == last
	while (first < last) {
		while (first < last && v[last] >= key) last--;
		v[first] = v[last];
		while (first < last && v[first] <= key) first++;
		v[last] = v[first];
	}
	v[first] = key;
	quicksort(v, l, first - 1); // 递归左半部分
	quicksort(v, first + 1, r);	// 递归右半部分
}

堆排序

构建大顶堆
循环让最大的元素和最后一个元素交换,调整

构建大顶堆

循环让最大的元素和最后一个元素交换,调整

void downAdjust(int a[], int parent, int n)
{
    int temp = a[parent];
    int child = 2  * parent + 1; // 左孩子
    while(child <= n){
        if(child + 1 <= n && a[child] < a[child + 1])
            child++;
        if(a[child] <= temp)    
            break;
        a[parent] = a[child];
        parent = child;
        child = 2 * parent + 1;
    }
    a[parent] = temp;
}
void HeapSort(int a[], int n)
{
    //构建大顶堆
    //从最后一个非叶节点向上调整
    for(int i = n/2 - 1; i >= 0; i--){
        downAdjust(a, i, n -1);
    }
    //进行堆排序
        for (int i = n - 1; i >= 1; i--) {
            // 把堆顶元素与最后一个元素交换
            int temp = a[i];
            a[i] = a[0];
            a[0] = temp;
            // 把打乱的堆进行调整,恢复堆的特性
            downAdjust(a, 0, i - 1);
        }
}

计数排序

桶排序

基数排序

————————
  • 线性表链表
  • 链表
  • Tree遍历二叉搜索树AlV树
  • 遍历
  • 二叉搜索树
  • AlV树
  • 并查集并查集的实现
  • 并查集的实现
  • 图论算法遍历CreateDFS(Depth First Search)BFS(Breadth First Search)最短路径FloydDijkstraBellman-Ford——解决负权变应用:PTA-advande-1003 DijkstraBellman-Ford最小生成树PrimKruskal
  • 遍历CreateDFS(Depth First Search)BFS(Breadth First Search)
  • Create
  • DFS(Depth First Search)
  • BFS(Breadth First Search)
  • 最短路径FloydDijkstraBellman-Ford——解决负权变应用:PTA-advande-1003 DijkstraBellman-Ford
  • Floyd
  • Dijkstra
  • Bellman-Ford——解决负权变
  • 应用:PTA-advande-1003 DijkstraBellman-Ford
  • PTA-advande-1003 Dijkstra
  • Bellman-Ford
  • 最小生成树PrimKruskal
  • Prim
  • Kruskal
  • 数学算法进位制字符串加法
  • 进位制
  • 字符串加法
  • 排序冒泡排序优化:如果已经排好序,即没有交换,则退出循环选择排序插入排序希尔排序归并排序快速排序堆排序计数排序桶排序基数排序
  • 冒泡排序优化:如果已经排好序,即没有交换,则退出循环
  • 优化:如果已经排好序,即没有交换,则退出循环
  • 选择排序
  • 插入排序
  • 希尔排序
  • 归并排序
  • 快速排序
  • 堆排序
  • 计数排序
  • 桶排序
  • 基数排序

线性表

链表

操作:头插、尾插、插入指定数据、删除、反转

操作:头插、尾插、插入指定数据、删除、反转

 #include<stdio.h>
#include<stdlib.h>

typedef struct Node
{
    int data;
    struct Node *next;
}Node;

void printlist(Node *L);
Node* head_insert();//头插
Node* tail_insert();//尾插
void insert(Node*L,int n);//插入指定数据
void deletelist(Node *L,int n);//删除
Node* reverse(Node *L);//反转d
Node* combine(Node*L1,Node*L2);//链接
int ClearList(Node *L);//整个链表的删除

int main()
{   
    Node *L1;
    L1 = tail_insert();  
    //deletelist(L1,3);
    insert(L1,10);
    printlist(L1);

    //L1 = reverse(L1);
    // printlist(L1);
    

    // Node *L2;
    // L2 = tail_insert();
    // printlist(L2);

    // Node *L3;
    // L3 = combine(L1,L2);
    // printlist(L3);

    // ClearList(L1);
    // ClearList(L2);
    // ClearList(L3);

    return 0;
}
void printlist(Node *L)
{
    Node *p = L->next;
    while(p)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}
Node* head_insert()
{
    Node *head,*p;
    head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    int temp;
    while(scanf("%d",&temp)&&temp!=-1)
    {
        p = (Node*)malloc(sizeof(Node));
        p->data = temp;
        p->next = head->next;
        head->next = p;
    }
    return head;
}
Node* tail_insert()
{
    Node *head,*p,*tail;
    head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    tail = head;
    int temp;
    while(scanf("%d",&temp)&&temp!=-1)
    {
        p =(Node*)malloc(sizeof(Node));
        p->data = temp;
        tail->next = p;
        tail = p;
    }
    tail->next = NULL;
    return head;
}
void insert(Node *L,int n)
{
    Node *p=L,*new;
    while(p->next != NULL && p->next->data<n)
    {
        p = p->next;
    }
    new = (Node*)malloc(sizeof(Node));
    new->data = n;
    new->next = p->next;
    p->next = new;
    
}

void deletelist(Node *L,int n)
{
    Node *p=L->next,*pre=L;
    while(p!=NULL)
    {
        if(p->data==n){
            pre->next = p->next;
            free(p);
        }
        else
            pre = pre->next;
        p = pre->next;
    }
}
Node* reverse(Node *L)
{
    Node *p = L->next,*head,*tail=NULL;
    head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    while(p)
    {
        tail = p->next;
        p->next = head->next;
        head->next = p;
        p = tail;
    }
    return head;

}
Node* Reverse(Node *L, int k)
{
    Node *new, *old, *temp;
    new = L->next;
    old = new->next;
    int cnt = 1;
    while(cnt < k)
    {
        temp = old->next;
        old->next = new;
        new = old;
        old = temp;
        cnt++;
    }
    L->next->next = old;
    L->next = new;
    return L;
} 
Node* combine(Node*L1,Node*L2)
{
    if(!L1->next && L2->next)
        return L2;
    if(L1->next && !L2->next)
        return L1;
    if(!L1->next && !L2->next)
        return NULL;

    Node *p = L1->next,*q = L2->next,*head,*tail,*c;
    head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    tail = head;
    while(p&&q)
    {
        if(p->data<q->data){
            c = p;
            p = p->next;
        }
        else{
            c = q;
            q = q->next;
        }
        tail->next = c;
        tail = c;
    }
    if(p)
        tail->next = p;
    if(q){
        tail->next = q;
    }
    return head;
}
int ClearList(Node *L)
{
    Node *p,*q;
    p = L->next;
    while(p){
        q = p->next;
        free(p);
        p = q;
    }
    L->next = NULL;
    
    return 0;
}
/*
1 3 5 7 9 11 12 13 -1
2 4 6 8 10 -1
*/

Tree

遍历

前序: root->left->right
中序: left->root->right
后续: right->left->root
层序: 用队列

前序: root->left->right

中序: left->root->right

后续: right->left->root

层序: 用队列

void InorderTraversal( BinTree BT )
{
    if(BT)
    {
        InorderTraversal(BT->Left);
        printf(" %c", BT->Data);
        InorderTraversal(BT->Right);
    }
}
void PreorderTraversal( BinTree BT )
{
    if(BT)
    {
        printf(" %c", BT->Data);
        PreorderTraversal(BT->Left);
        PreorderTraversal(BT->Right);
    }
}
void PostorderTraversal( BinTree BT )
{
    if(BT)
    {
        PostorderTraversal(BT->Left);
        PostorderTraversal(BT->Right);
        printf(" %c", BT->Data);
    }
}
void LevelorderTraversal( BinTree BT )
{
        BinTree q[100], p;
    int front, rear;
    front = rear = 0;
    if(!BT)
        return;
    else
    {
        q[rear++] = BT;
        while(front != rear)
        {
            p = q[front++];
            printf(" %c", p->Data);
            if(p->Left)
                q[rear++] = p->Left;
            if(p->Right)
                q[rear++] = p->Right;
        }
    }
}
//中序遍历
void InOrderWithoutRecursion2(BTNode* root)
{
    //空树
    if (root == NULL)
        return;
    //树非空
    BTNode* p = root;
    stack<BTNode*> s;
    while (!s.empty() || p)
    {
        if (p)
        {
            s.push(p);
            p = p->lchild;
        }
        else
        {
            p = s.top();
            s.pop();
            cout << setw(4) << p->data;
            p = p->rchild;
        }
    }
}

求二叉树的高度

求二叉树的高度

int GetHeight( BinTree BT ){
    int HL,HR,MaxH;
    if(BT){
        HL = GetHeight(BT->Left);
        HR = GetHeight(BT->Right);
        MaxH = (HL>HR)?HL:HR;
        return MaxH+1;
    }else
        return 0;
}	

二叉搜索树

插入、删除、查找

插入、删除、查找

BinTree Insert(BinTree BST, ElementType X)
{
    if (BST == NULL)
    {
        BST = malloc(sizeof(struct TNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    }
    else if (X < BST->Data)
        BST->Left = Insert(BST->Left, X);
    else if (X > BST->Data)
        BST->Right = Insert(BST->Right, X);

    return BST;
}
BinTree Delete(BinTree BST, ElementType X)
{
    Position TemCell;
    if (BST == NULL)
        printf("Not Found\n");
    else if (X < BST->Data)
        BST->Left = Delete(BST->Left, X);
    else if (X > BST->Data)
        BST->Right = Delete(BST->Right, X);
    //左右儿子都存在
    else if (BST->Left && BST->Right)
    {
        TemCell = FindMin(BST->Right);
        BST->Data = TemCell->Data;
        BST->Right = Delete(BST->Right, BST->Data);
    }   
    else//z
    {
        TemCell = BST;
        if (BST->Left == NULL)
            BST = BST->Right;
        else if (BST->Right == NULL)
            BST = BST->Left;
        free(TemCell);
    }
    return BST;
}
Position Find(BinTree BST, ElementType X)
{
    if (BST == NULL)
        return NULL;
    if(X < BST->Data)
        return Find(BST->Left, X);
    else if(X > BST->Data)
        return Find(BST->Right, X);
    else
        return BST;
}
Position FindMin(BinTree BST)
{
    if (BST != NULL)
        while (BST->Left != NULL)
            BST = BST->Left;
    return BST;
}
Position FindMax(BinTree BST)
{
    if (BST != NULL)
        while (BST->Right != NULL)
            BST = BST->Right;
    return BST;
}

AlV树

1、左-左型:做右旋。
2、右-右型:做左旋转。
3、左-右型:先做左旋,后做右旋。

1、左-左型:做右旋。

2、右-右型:做左旋转。

3、左-右型:先做左旋,后做右旋。

4、右-左型:先做右旋,再做左旋。

4、右-左型:先做右旋,再做左旋。

//定义节点
class AvlNode {
   int data;
   AvlNode lchild;//左孩子
   AvlNode rchild;//右孩子
   int height;//记录节点的高度   
}

//在这里定义各种操作
public class AVLTree{
   //计算节点的高度
   static int height(AvlNode T) {
       if (T == null) {
           return -1;
       }else{
           return T.height;
       }
   }

   //左左型,右旋操作
   static AvlNode R_Rotate(AvlNode K2) {
       AvlNode K1;

       //进行旋转
       K1 = K2.lchild;
       K2.lchild = K1.rchild;
       K1.rchild = K2;

       //重新计算节点的高度
       K2.height = Math.max(height(K2.lchild), height(K2.rchild)) + 1;
       K1.height = Math.max(height(K1.lchild), height(K1.rchild)) + 1;

       return K1;
   }

   //进行左旋
   static AvlNode L_Rotate(AvlNode K2) {
       AvlNode K1;

       K1 = K2.rchild;
       K2.rchild = K1.lchild;
       K1.lchild = K2;

       //重新计算高度
       K2.height = Math.max(height(K2.lchild), height(K2.rchild)) + 1;
       K1.height = Math.max(height(K1.lchild), height(K1.rchild)) + 1;

       return K1;
   }

   //左-右型,进行右旋,再左旋
   static AvlNode R_L_Rotate(AvlNode K3) {
       //先对其孩子进行左旋
       K3.lchild = R_Rotate(K3.lchild);
       //再进行右旋
       return L_Rotate(K3);
   }

   //右-左型,先进行左旋,再右旋
   static AvlNode L_R_Rotate(AvlNode K3) {
       //先对孩子进行左旋
       K3.rchild = L_Rotate(K3.rchild);
       //在右旋
       return R_Rotate(K3);
   }

   //插入数值操作
   static AvlNode insert(int data, AvlNode T) {
       if (T == null) {
           T = new AvlNode();
           T.data = data;
           T.lchild = T.rchild = null;
       } else if(data < T.data) {
           //向左孩子递归插入
           T.lchild = insert(data, T.lchild);
           //进行调整操作
           //如果左孩子的高度比右孩子大2
           if (height(T.lchild) - height(T.rchild) == 2) {
               //左-左型
               if (data < T.lchild.data) {
                   T = R_Rotate(T);
               } else {
                   //左-右型
                   T = R_L_Rotate(T);
               }
           }
       } else if (data > T.data) {
           T.rchild = insert(data, T.rchild);
           //进行调整
           //右孩子比左孩子高度大2
           if(height(T.rchild) - height(T.lchild) == 2)
               //右-右型
               if (data > T.rchild.data) {
                   T = L_Rotate(T);
               } else {
                   T = L_R_Rotate(T);
               }
       }
       //否则,这个节点已经在书上存在了,我们什么也不做
       
       //重新计算T的高度
       T.height = Math.max(height(T.lchild), height(T.rchild)) + 1;
       return T;
   }
}

并查集

并查集的实现

#define MAX_N 100000
int par[MAX_N];
int rank[MAX_N];

void init (int n) {
    for (int i = 0; i < n; i++) {
        par[i] = i;
        rank[i] = 0;
    }
}

//查询树的根
int find(int x) {
    if (par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);
    }
}

//合并x和y所属集合
void unite (int x, int t) {
    x = find(x);
    y = find(y);
    if (x == y)  return;
    if (rank[x] < rank[y]) {
        par[x] = y;
    } else {
        par[y] = par[x];
        if (rank[x] == rank[y]) rank[x]++;
    }
}
//判断x和y是否属于同意集合
bool same (int x, int y) {
    return find (x) == find (y);
}

图论算法

遍历

Create

int e[10][10],book[10],n;
void Create()
{
	for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (i == j)
                e[i][j] = 0;
            else
                e[i][j] = 99999999;
    for (i = 1; i <= m; i++)
    {
        scanf("%d %d", &a, &b);
        e[a][b] = e[b][a] = 1;
    }
}

DFS(Depth First Search)

#include <stdio.h>

int e[10][10], book[10], n,sum;

void Dfs(int cur)
{
    book[cur] = 1;
    for(int i = 1; i <= n; i++)
       if(book[i] == 0 && e[cur][i] == 1)
           dfs(i);
    return;
}
/*
5 5
1 2
1 3
1 5
2 4
3 5
*/
//Dfs: 1 2 4 3 5

BFS(Breadth First Search)

void BFS(int e[][])
{
    int queue[10] = {0}, head, tail,i;
    head = tail = 1;
    book[1] = 1;
    queue[tail++] = 1;

    while(head < tail)
    {
        int cur = queue[head++];
        for (i = 1; i <= n; i++)
        {
            if(book[i] == 0 && e[cur][i] == 1)
            {
                queue[tail++] = i;
                book[i] = 1;
            }
        }
    }
    printf("BFS:");
    for (i = 1; i <= n; i++)
        printf(" %d",queue[i]);
}

最短路径

Floyd Dijkstra Bollman-Ford 优先队列的
Bellman-ford
空间复杂度 O(N2) O(M) O(M) O(M)
时间复杂度 O(N3) O(N2) O(MN) O(NM)
使用情况 稠密图和
顶点关系密切
稠密图和顶点关系密切 稀疏图
和边关系密切
稀疏图和边关系密切
负权 可以 不可 可以 可以

Floyd

求任意顶点到任意顶点的最短路径

求任意顶点到任意顶点的最短路径

for(k = 1; k <= n; k++)
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            if(e[i][j] > e[i][k] + e[k][j])
                e[i][j] = e[i][k] + e[k][j];

Dijkstra

基本思想:
每次找到离源点最近的一个顶点,然后以该顶点为中心进行扩展,最终得到远点到其余所有点的最短路径

基本思想:

每次找到离源点最近的一个顶点,然后以该顶点为中心进行扩展,最终得到远点到其余所有点的最短路径

#include<iostream>
using namespace std;
int n, m, s, d;
int e[501][501], dis[501], path[501];
bool visit[501];
const int inf = 99999999;
void dfs(int cur)
{
    if(cur == s){
        printf("%d", cur);
        return;
    }
    dfs(path[cur]);
    printf("->%d", cur);
}
int main()
{
    cin >> n >> m >> s >> d;
    fill(e[0], e[0] + 501 * 501, inf);
    fill(dis, dis + 501, inf);
    for (int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        e[a][b] = e[b][a] = c;
    }
    dis[s] = 0;
    for (int i = 1; i <= n; i++){
        int min = inf, u = -1;
        for (int j = 1; j <= n; j++){
            if(visit[j] == false && dis[j] < min){
                min = dis[j];
                u = j;
            }
        }
        if(u == -1)
            break;
        visit[u] = true;
        for (int v = 1; v <= n; v++){
            if(visit[v] == false && e[u][v] != inf){
                if(dis[v] > dis[u] + e[u][v]){
                    dis[v] = dis[u] + e[u][v];
                    path[v] = u;
                }
            }
        }
    }
    dfs(d);
    printf("\n%d", dis[d]);
    return 0;
}
/*
6 9 1 6
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
*/
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
struct edge{
    int to, cost;
};
typedef pair<int, int> P;
int n, m, s, d;
int dis[7], pre[7];
vector<edge> G[7];
const int inf = 99999999;
void dijkstra(int s)
{
    priority_queue<P, vector<P>, greater<P> > que;
    dis[s] = 0;
    que.push(P(0, s));
    while(!que.empty()){
        P p = que.top();
        que.pop();
        int v = p.second;
        if(dis[v] < p.first)
            continue;
        for(int i = 0; i < G[v].size(); i++){
            edge e = G[v][i];
            if (dis[e.to] > dis[v] + e.cost){
                dis[e.to] = dis[v] + e.cost;
                que.push(P(dis[e.to], e.to));
                pre[e.to] = v;
            }
        }
    }

}

int main()
{
    cin >> n >> m >> s >> d;
    fill(dis, dis + 7, inf);
    fill(pre, pre + 7, -1);
    for(int i = 1; i<= m; i++){
        int v;
        edge e;
        cin >> v >> e.to >> e.cost;
        G[v].push_back(e);
    }
    dijkstra(s);
    vector<int> path;
    for(int i = d; i != -1; i = pre[i])
        path.push_back(i);
    reverse(path.begin(), path.end());
    for(int i = 1; i <= n; i++)
        printf("%d ", dis[i]);
    printf("\n");
    for(auto it = path.begin(); it != path.end(); it++)
        printf("%d ", *it);
        
    return 0;
}
/*
6 9 1 6
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
*/

Bellman-Ford——解决负权变

核心代码:
看看能否通过u[i]->v[i](权值为w[i])这条边,使得1号顶点到v[i]号顶点的距离变短

核心代码:

看看能否通过u[i]->v[i](权值为w[i])这条边,使得1号顶点到v[i]号顶点的距离变短

for(k=1; k<=n-1; k++)
        for(i=1; i<=m; i++)
            if(dis[v[i]] > dis[u[i]] + w[i])
                dis[v[i]] = dis[u[i]] + w[i];

应用:

PTA-advande-1003 Dijkstra

#include<stdio.h>

int main()
{
    int n, m, c1, c2, a, b, c;
    int e[501][501],visit[501] = {0}, dis[501], weight[501], w[501] = {0}, num[501] = {0};
    const int inf = 99999999;
    scanf("%d %d %d %d", &n, &m, &c1, &c2);
    for(int i = 0; i < n; i++)
        scanf("%d",&weight[i]);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            e[i][j] = inf;
    for(int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        e[a][b] = e[b][a] = c; 
    }
    for(int i = 0; i < n; i++)
        dis[i] = inf;
    dis[c1] = 0;
    w[c1] = weight[c1];
    num[c1] = 1;
    for(int i = 0; i < n; i++)
    {
        int u = -1, min = inf;
        for(int j = 0; j < n; j++)
        {
            if(visit[j] == 0 && dis[j] < min)
            {
                u = j;
                min = dis[j];
            }
        }
        visit[u] = 1;
        if(u == -1)
            break;
        for(int v = 0; v < n; v++)
        {
            if(visit[v] == 0 && e[u][v] < inf)
            {
                if(dis[v] > dis[u] + e[u][v])
                {
                    dis[v] = dis[u] + e[u][v];
                    w[v] = w[u] + weight[v];
                    num[v] = num[u];
                }
                else if(dis[v] == dis[u] + e[u][v])
                {
                    num[v] += num[u];
                    if(w[v] < w[u] + weight[v])
                        w[v] = w[u] + weight[v];
                }
            }
        }
    }
    printf("%d %d", num[c2], w[c2]);
    return 0;
}
/*
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
*/

Bellman-Ford

#include<stdio.h>
void PrintPath(int n, int path[])
{
    if(path[n] == -1)
        return ;
    PrintPath(path[n],path);
    printf("%d->",path[n]);
}
int main()
{
    int dis[10],bak[10],i,k,n,m,u[10],v[10],w[10],check,flag;
    int inf = 99999999;
    scanf("%d%d",&n,&m);
    for(i=1; i<=m; i++)
        scanf("%d%d%d",&u[i],&v[i],&w[i]);
    for(i=1; i<=m; i++)
        dis[i] = inf;
    dis[1] = 0;
    int path[10];
    for(i = 0; i < 10; i++)
        path[i] = -1;
    //Bellman-Ford
    for(k=1; k<=n-1; k++)
    {   
        for(i=i; i<=n; i++) bak[i] = dis[i];

        for(i=1; i<=m; i++)
            if(dis[v[i]] > dis[u[i]] + w[i]){
                dis[v[i]] = dis[u[i]] + w[i];
                path[v[i]] = u[i];
            }
        check = 0;
        for(i=1; i<=n; i++) 
            if(bak[i] != dis[i])
            {
                check = 1;
                break;
            }
        if(check == 0)
            break;
    }
    flag = 0;
    for(i=1; i<=m; i++)
        if(dis[v[i]] > dis[u[i]] + w[i])
            flag = 1;
    if(flag==1)
        printf("此图有负权回路");
    else
    {
        for(i=1; i<=n; i++)
        printf("%d ",dis[i]);
    }
    printf("\n");
    PrintPath(5,path);
    printf("5");
    return 0;
}
/*
5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3
*/

最小生成树

Prim

#include<stdio.h>

int main()
{
    int n, m, i, j, k, min, t1, t2, t3;
    int e[7][7], dis[7], book[7] = {0};
    int inf = 99999999;
    int count = 0, sum = 0;
    scanf("%d %d", &n, &m);
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            if(i == j)  e[i][j] = 0;
            else    e[i][j] = inf;
        
    for(i = 1; i <= m; i++)
    {
        scanf("%d %d %d",&t1, &t2, &t3);
        e[t1][t2] = e[t2][t1] = t3;
    }
    for(i = 1; i <= n; i++)
        dis[i] = e[1][i];
    
    //Prim核心部分
    book[1] = 1;
    count++;
    while(count < n)
    {
        min = inf;
        for(i = 1; i <= n; i++)
        {
            if(book[i] == 0 && dis[i] < min)
            {
                min = dis[i];
                j = i;
            }
        }
        book[j] = 1;
        count++;
        sum += dis[j];
        for(k = 1; k <= n; k++)
        {
            if(book[k] == 0 && dis[k] > e[j][k])
                dis[k] = e[j][k];
        }
    }
    printf("%d",sum);
    return 0;
}
/*
6 9
2 4 11
3 5 13
4 6 3
5 6 4
2 3 6
4 5 7
1 2 1
3 4 9
1 3 2
*/

Kruskal

#include<stdio.h>
struct edge
{
    int u;
    int v;
    int w;
};
struct edge e[10];
int n, m;
int f[7] = {0}, sum = 0, count = 0;

void quicksort(int left, int right)
{
    int i, j;
    struct edge t;
    if(left > right)
        return;
    i = left;
    j = right;
    while(i != j)
    {
        while(e[j].w >= e[left].w && i < j)
            j--;
        while(e[i].w <= e[left].w  && i < j)
            i++;
        if(i < j)
        {
            t = e[i];
            e[i] = e[j]; 
            e[j] = t;
        }
    }
    t = e[left];
    e[left] = e[i];
    e[i] = t;
    quicksort(left, i-1);
    quicksort(i+1, right);
    return;
}
int Find(int f[], int v)
{
    while(f[v] > 0)
        v = f[v];
    return v;
}

int main()
{
    int i;
    scanf("%d %d", &n, &m);
    for(i = 1; i <= m; i++)
        scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w);
    quicksort(1, m);
    
    //Kruskalh
    for(i = 1; i <= m; i++)
    {
        int a = Find(f,e[i].u);
        int b = Find(f,e[i].v);
        if(a != b)
        {
            f[b] = a;
            count++;
            sum += e[i].w; 
        }
        if(count == n - 1)
            break;
    }
    printf("%d",sum);
    return 0;
}
/*
6 9
2 4 11
3 5 13
4 6 3
5 6 4
2 3 6
4 5 7
1 2 1
3 4 9
1 3 2
*/

数学算法

进位制

转换为10进制

转换为10进制

long long convert(string n, long long radix) {
 long long sum = 0;
 int index = 0, temp = 0;
 for (auto it = n.rbegin(); it != n.rend(); it++) {
 temp = isdigit(*it) ? *it - '0' : *it - 'a' + 10;
 sum += temp * pow(radix, index++);
 }
 return sum;
}

字符串加法

void add(string &n, string temp)
{
    int digit = 0;
    for(int i = n.length() - 1; i >= 0; i--)
    {
        n[i] = n[i] + temp[i] + digit - '0';
        digit = 0;
        if(n[i] > '9'){
            digit = 1;
            n[i] = n[i] - 10;
        }
    }
    if(digit == 1){
        n.insert(0,"1");
    }
}

排序

冒泡排序

void Bubble_Sort(int a[], int n)
{
    int i, j, c;
    for(i = 0; i < n-1; i++){
        for(j = 0; j < n - i; j++){
            if(a[j] > a[j+1]){
                c = a[j];
                a[j] = a[j+1];
                a[j+1] = c;
            }
        }
    }
}

优化:如果已经排好序,即没有交换,则退出循环

void Bubble_Sort(int a[], int n)
{
    int i, j, c;
    for(i = 0; i < n-1; i++){
        int flag = 1;
        for(j = 0; j < n - i; j++){
            if(a[j] > a[j+1]){
                flag = 0;
                c = a[j];
                a[j] = a[j+1];
                a[j+1] = c;
            }
        }
        if(flag == 1)
            break;
    }
}

选择排序

插入排序

void Insertion_Sort(int a[], int N)
{
    int i, j;
    for( i = 0; i < N; i++)
    {
        int temp = a[i];
        for( j = i; j > 0 && a[j -1] > temp; j--)
            a[j] = a[j - 1];
        a[j] = temp;
    }
}

希尔排序

void shell_sort(vector<int> &v, int n)
{
    int gap, i, j;
	for (gap = n / 2; gap > 0; gap /= 2) {
		for (i = gap; i < n; i++) {
			int temp = v[i];
			for (j = i - gap; j >= 0 && v[j] > temp; j-= gap)
				v[j + gap] = v[j];
			v[j + gap] = temp;
		}	
	}
}

归并排序

递归

void Merge(vector<int> &a, vector<int> &temp, int left, int mid, int right) {
	int i = left;
	int j = mid + 1;
	int k = 0;
	// 两个有序数组的合并
	while (i <= mid && j <= right) {
		if (a[i] < a[j])
			temp[k++] = a[i++];
		else 
			temp[k++] = a[j++];
	}
	// 只剩下一个数组没合并
	while (i <= mid) 
		temp[k++] = a[i++];
	while (j <= right)
		temp[k++] = a[j++];
	// 把辅助数组的值都拷贝要求的数组里
	for (int i = 0; i < k; i++)
		a[left++] = temp[i];
}
void Msort(vector<int> &a, vector<int> &temp, int left, int right) {
	if (left < right) {
		int mid= (left + right) / 2;
		Msort(a, temp, left, mid); 
		Msort(a, temp, mid + 1, right);
		Merge(a, temp, left, mid, right);
	}
} 

非递归

void mergesort(int a[], int temp[], int N)
{
    for(int i = 1; i < N; i *= 2){
        int left = 0;
        int mid = left + i -1;
        int right = mid + i;
        while(right < N){
            Merge(a, temp, left, mid, right);
            left = right + 1;
            mid = left + i -1;
            right = mid + i;
        }
        if(left < N && mid < N)
        	Merge(a, temp, left, mid, N-1);
    }
}

快速排序

步骤

  • 从数列中找到一个基准
  • 重新排列,比基准小的元素排在基准前面,比基准大的排在基准右边
  • 分别递归小于基准的元素和大于基准的元素
void quicksort(vector<int> &v, int l, int r) {
	if (l > r) // 注意跳出递归的条件
		return;
	int first = l, last = r, key = v[first];
    // 最终使 first == last
	while (first < last) {
		while (first < last && v[last] >= key) last--;
		v[first] = v[last];
		while (first < last && v[first] <= key) first++;
		v[last] = v[first];
	}
	v[first] = key;
	quicksort(v, l, first - 1); // 递归左半部分
	quicksort(v, first + 1, r);	// 递归右半部分
}

堆排序

构建大顶堆
循环让最大的元素和最后一个元素交换,调整

构建大顶堆

循环让最大的元素和最后一个元素交换,调整

void downAdjust(int a[], int parent, int n)
{
    int temp = a[parent];
    int child = 2  * parent + 1; // 左孩子
    while(child <= n){
        if(child + 1 <= n && a[child] < a[child + 1])
            child++;
        if(a[child] <= temp)    
            break;
        a[parent] = a[child];
        parent = child;
        child = 2 * parent + 1;
    }
    a[parent] = temp;
}
void HeapSort(int a[], int n)
{
    //构建大顶堆
    //从最后一个非叶节点向上调整
    for(int i = n/2 - 1; i >= 0; i--){
        downAdjust(a, i, n -1);
    }
    //进行堆排序
        for (int i = n - 1; i >= 1; i--) {
            // 把堆顶元素与最后一个元素交换
            int temp = a[i];
            a[i] = a[0];
            a[0] = temp;
            // 把打乱的堆进行调整,恢复堆的特性
            downAdjust(a, 0, i - 1);
        }
}

计数排序

桶排序

基数排序