算法比赛数据结构复习
//基本数据结构练习
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
//算法比赛中数据结构使用
//数组
int a[N];
//队列模拟
int q[N], int hh = 0, tt = -1;//hh为队首,tt为队尾
int size = hh - tt+1;//队列元素个数
q[++tt]=x;//在队尾插入一个元素
hh++;//队首弹出一个元素
//用例
while (hh <= tt)
{
int t = q[hh++];//取队首元素并且弹出
}
//栈模拟
int s[N], top = 0;
int size = top;//元素个数
s[top++];//压栈
top--;//弹栈
s[top];//取栈顶元素
//用例
while (top > 0)
{
int t = s[top--];//取栈顶并且弹栈
}
//单链表模拟
// head存储链表头,e[]存储节点的值,ne[]存储节点的next指针,idx表示当前用到了哪个节点
int head, e[N], ne[N],val[N],idx;
void init()
{
idx = 0;
head = -1;
}
void add(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx++;
}
//将头结点删除
void remove()
{
head = ne[head];
}
//图
const int M = 2*N;
//无权图
int h[N], e[M], ne[N], idx;
void add(int a, int b)//添加一条a到b的边
{
e[idx] = h[a];
ne[idx] = b;
h[a] = idx++;
}
//有权图
int h[N], e[M], ne[M], W[M], idx;
void add(int a, int b, int c)//添加一条a到b的权值为c的边
{
e[idx] = h[a];
ne[idx] = b;
W[idx] = c;
h[a] = idx++;
}
int main()
{
//图的初始化
idx = 0;
memset(h, -1, sizeof(h));
}
//不经常用的并查集
//并查集
int Max = 1005;
int pa[Max]; int rank[Max]
void init(int n)
{
for (int i = 0; i < n; i++)
{
pa[i] = i;
rank[i] = 1;
}
}//初始化
//朴素版
int Find(int n)
{
if (pa[n] = n)
return n;
else Find(pa[n]);//它自己不是代表结点
}//查找
void Union(int m, int n)
{
pa[Find(n)] = Find(m);//集合m和n合并
}//合并
//优化,路径压缩
int find(int n)
{
if (pa[n] = n)
return n;
else {
pa[n] = find(pa[n]);//保存的为根结点
}
}
void u_nion(int m, int n) {
int rm = find[m], rn = find(n);
if (rank[rm] > rank[rn])
{
pa[rn] = rm;
}
else pa[rm] = rn;
if (rm != rn && rank[rm] = rank[rn])
rank[rn]++;
}