目录

一、栈

二、队列

三、树

四、图

五、参考

一、栈

1、栈是一种先进后出类型的数据结构，对于栈的理解和操作可以参考下图栈的模型[1]

2、栈的实现方法及例子：

#include

using namespace std;

int s[100005],tot=0;

#define push(x) s[++tot]=x

#define pop tot--

#define size tot

#define top s[tot]

对栈操作的例子（接上面的代码）：

int main(){

push(5);//5进栈

push(6);//6进栈

pop;//6出栈  

push(66);//66进栈

push(20);//20进栈

pop;//20出栈  

push(8);//8进栈

push(3);//3进栈

cout<<top<<endl;//取栈顶3

cout<<size;//输出栈大小

return 0;

}

3、简单例题：

（1）、后缀表达式：https://www.luogu.com.cn/problem/P1449

（2）、车厢调度(train)：http://ybt.ssoier.cn:8088/problem_show.php?pid=1357

二、队列

1、队列是一种先进先出类型的数据结构，队列的模型及操作见下图[2]：

2、队列的实现方法及例子

#include

using namespace std;

int s[100005],fnt=1,end=0;

#define push(x) s[++end]=x

#define pop fnt++

#define front s[fnt]

#define size end-fnt+1

关于队列操作的例子（接上面代码）：

int main(){

push(5);//5进队

push(6);//6进队

pop;//5出队

push(66);//66进队

pop;//6出队

push(20);//20进队

push(8);//8进队

push(3);//3进队

cout<<front<<endl;//取队首元素

cout<<size;//输出队大小

return 0;

}

3、简单例题

周末舞会：http://ybt.ssoier.cn:8088/problem_show.php?pid=1332

三、树

1、树的形式如图：

2、树的存储方法及例子：
说明：树的简单存储方法采用和图一样的存储方法：邻接表（当然你也可以用邻接矩阵，但是那样花费空间），哈哈，因为这样简单方便。对于有边权值和结点值的树具体实现如下：

#include

#include

using namespace std;

const int N=1e5+10;

struct Edge{

int v,w;

};

Edge make_Edge(int v,int w){

Edge cur;

cur.v=v;

cur.w=w;

return cur;

}

vector G[N];

void addedge(int u,int v,int w){

G[u].push_back(make_Edge(v,w));//添加孩子结点

}

对树操作的例子（接上面的代码）：

int main(){

addedge(5,8,10);//添加结点5到结点8的边，边权值为10

addedge(5,12,8);//添加结点5到结点12的边，边权值为8

addedge(8,4,25);//添加结点8到结点4的边，边权值为25

addedge(8,1,60);//添加结点8到结点1的边，边权值为60

addedge(12,15,7);//添加结点12到结点15的边，边权值为7

//输出结点5的孩子结点及其到孩子结点的边权值

for(int i=0;i

cout<<G[5][i].v<<" "<<G[5][i].w<<endl;

}

return 0;

}

3、简单例题：

找树根和孩子：http://ybt.ssoier.cn:8088/problem_show.php?pid=1336

四、图

1、图的形式，如图：

2、图的存储方法及例子

图的存储方式和上面一样，采用邻接表存储：

#include

#include

using namespace std;

const int N=1e5+10;

struct Edge{

int v,w;

};

Edge make_Edge(int v,int w){

Edge cur;

cur.v=v;

cur.w=w;

return cur;

}

vector G[N];

void addedge(int u,int v,int w){

G[u].push_back(make_Edge(v,w));//添加结点u到v的边，边权值为w

G[v].push_back(make_Edge(u,w));//添加结点v到u的边，边权值为w

}

对树操作的例子（接上面的代码）：

int main(){

addedge(5,8,10);//添加结点5到结点8的边，边权值为10

addedge(5,12,8);//添加结点5到结点12的边，边权值为8

addedge(8,4,25);//添加结点8到结点4的边，边权值为25

addedge(8,1,60);//添加结点8到结点1的边，边权值为60

addedge(12,15,7);//添加结点12到结点15的边，边权值为7

//输出结点5的孩子结点及其到孩子结点的边权值

for(int i=0;i8].size();i++){

cout<<G[8][i].v<<" "<<G[8][i].w<<endl;

}

return 0;

}

3、简单例题

输出图的所有结点的邻接结点

五、参考

[1].https://gss1.bdstatic.com/9vo3dSag_xI4khGkpoWK1HF6hhy/baike/s=220/sign=4b2162dc1bd5ad6eaef963e8b1cb39a3/8b82b9014a90f603eab7c55f3912b31bb051eda7.jpg

[2].https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/c0=baike80,5,5,80,26/sign=35768ebb0ff3d7ca18fb37249376d56c/cdbf6c81800a19d8116a4d8030fa828ba71e46ce.jpg

[3].https://class.luogu.com.cn/classroom/yugucamp7pj4