include <bits/stdc++.h>

void getNext(int m)
{
next[0] = -1;
int i = 0, j = -1;
while (i < m)
{
if (j == -1 || p[i] == p[j])
p[++i] = ++j;
else
j = next[j];
}
}
int KMP(int n, int m)
{
getNext(m);
int i = 0, j = 0;
while (i < n && j < m)
{
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
j = next[j];
}
if (j == m)
return i - m + 1;
else
return -1;
}

求后缀表达式的值
void sum(string s1)
{
stack s;
for (int i = 0; s1[i] != ‘#‘; i++)
{
if (s1[i] >= ‘0‘ && s1[i] <= ‘9‘)
s.push(s1[i] - 48);
else
{
int b = s.top();
s.pop();
int a = s.top();
s.pop();
switch (s1[i])
{
case ‘+‘:
s.push(a + b);
break;
case ‘-‘:
s.push(a - b);
break;
case ‘*‘:
s.push(a * b);
break;
case ‘/‘:
s.push(a / b);
break;
}
}
}
cout << s.top() << endl;
}
求一棵二叉树的深度
int deep(tree *root)
{
if (root == NULL)
return 0;
return max(deep(root->left) + 1, deep(root->right) + 1);
}
在一棵二叉树中查找一个数字
tree *search(tree *root, int x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
if (serach(root->left, x))
return serch(root->left, x);
else
return serach(root->right, x);
}
求给定图生成树的数目
基于邻接矩阵的bfs void bfs(int k, int t) //k:节点个数，t:搜索起点
{
queue q;
q.push(t);
vis[t] = true;
cout << t;
while (!q.empty())
{
int x = q.front();
q.pop();
for (int i = 0; i < k; i++)
{
if (Map[x][i] && !vis[i])
{
q.push(i);
vis[i] = true;
cout << " " << i;
}
}
}
cout << endl;
}
基于邻接矩阵的dfs void dfs(int k, int t)
{
if (t == 0)
cout << t;
else
cout << " " << t;
vis[t] = true;
for (int i = 0; i < k; i++)
{
if (Max[t][i] && !vis[i])
{
dfs(k, i);
}
}
}
求数组最小和次小 +
void min(int a[], n)
{
int x, y;
if (a[0] > a[1])
{
x = a[1];
y = a[0];
}
else
{
x = a[0];
y = a[1];
}
for (int i = 2; i < n; i++)
{
if (a[i] < x)
{
y = x;
x = a[i];
}
else if (a[i] < y)
{
y = a[i];
}
}
}
克鲁斯卡尔
int Kruskal(Graph g)
{
int cost = 0;

int s[max];                  //并查集
for (int i = 1; i <= n; i++) //init
    s[i] = i;
//排序操作
sort(e + 1, e + m + 1);
//加边操作
for (int i = 1; i <= m; i++)
{
    int u = Find(e[i].u);
    int v = Find(e[i].v);
    if (u != v)
    {
        s[u] = v;
        cost += e[i].val;
    }
}
return cost;

}

for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
for (k = 1; k <= n; k++)
{
if (d[j][i] + d[i][k] < d[j][k])
{
d[j][k] = d[j][i] + d[i][k];
path[j][k] = path[j][i];
}
}

floyd算法 for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) for (k = 1; k <= n; k++)
{
if (d[j][i] + d[i][k] < d[j][k])
{
d[j][k] = d[j][i] + d[i][k];
path[j][k] = path[j][i];
}
}

数据结构备考

原文：https://www.cnblogs.com/dmxs/p/14244411.html