#算法竞赛学习笔记
基础数据结构
- 链表
- 队列
- 栈
- 二叉树和哈夫曼树
- 堆
===================================
链表
一般是静态数组和stl list 来实现的
#include<iostream>
#include<list>//list 是双向链表
using namespace std;
void solve(){
list<type>node;//type 输入数据类型
for(int i=0;i<n;++i)node.push_back(i);//push.back()建立链表结点
list<type>::iterator it= node.begin();//创建遍历指针
node.erase(it);//删除结点
}
int main(){
solve();
return 0;
}
STL list相关具体知识点链接
队列
队列和栈的主要问题是查找比较慢，需要从头到尾一个个查找优先队列：优先级最高的先出队列（比如最大数或最小数先出队）
注意：在竞赛中，一般用手写静态数组（使用循环队列的形式）或者STL queue来实现队列。。
using namespace std;
void sovle(){
queue<type>q;
q.push(i);//i进队
q.front();//返回队首元素，但不会删除元素
q.pop();//删除队首元素
q.back();//返回队尾元素
q.size();//返回队列元素个数
q.empty();//判断是否为空
}
int main(){
sovle();
return 0;
}
======================================
手写循环队列（静态数组）
#include<iostream>
using namespace std;
const int N=1e4;
struct queue{
int data[N];
int head,rear;//队头队尾
bool init(){//初始化
if(!Q.data)return false;
head=rear=0;
return true;
}
int size(){//返回元素个数
return (rear-head+N)%N;
}
bool empty(){//判断是否为空
if(size()==0)return true;
else return false;
}
bool push(int e){//队尾插入新元素
if((rear+1)%N==head)return false;
data[rear]=e;
rear=(rear+1)%N;
return true;
}
bool pop(int &e){//出队，删除队头元素
if(head==rear)return false;
e=data[head];
head=(head+1)%N;
return true;
}
int front(){//返回队首
return data[head];
}
}Q;
void solve()
{
}
int main(){
solve();
return 0;
}
===================================
双端队列和单调队列：双端队列同时具有队列和栈的性质，比较特殊，能在两端进行插入和删除，而且也只能在两端插入和删除
=========================================
栈
注意：一般竞赛中使用STL stack或者手写栈来实现，为避免爆栈，需要控制栈的大小。**递归栈溢出：**递归本质上也是使用栈来存在变量答案，如果递归的深度太大，或者进栈的数组太大，那么总数会超过系统分配的空间，就会出现栈溢出的问题
STL stack
#include<iostream>
#include<stack>
using namespace std;
void solve(){
stack<int> s;//int, float, double ,char等
s.push(it);//进栈
s.top();//返回栈顶
s.pop();//删除栈顶
s.size();//返回栈中的元素个数
s.empty();//判断是否为空
}
int main(){
solve();
return 0;
}
================================
手写栈：
#include<iostream>
// #include<stack>
using namespace std;
const int N=1e4;
struct stack_1{
int a[N];
int t=0;
void push(int n){
a[t++]=n;
}
int top(){
return a[t];
}
void pop(){
t--;
}
int size(){
return t;
}
int empty(){
return t==0?1:0;
}
}s;
int main(){
solve();
return 0;
}
=====================================
单调栈：本质上还是一个普通栈，只是将栈中的元素按照单调性进栈，始终保持元素从小到大，或者从大到小。
============================================
二叉树和哈夫曼树
#include<iostream>
using namespace std;
const int N=1e4;
//动态二叉树'
struct node{
int data;
node* lson,*rson;
}t;
//静态二叉树,一般用静态数组实现
struct node{
int data;
int l,r;
}t[N];
====================
//二叉树的遍历,
// 前序遍历
void preorder(node*t){
cout<<t->data;//输出对应结点
preorder(t->l);//递归左子树
preorder(t->r);//递归右子树
}
// 中序遍历
void inorder(node*t){
inorder(t->l);
cout<<t->data;
inorder(t->r);
}
// 后序遍历
void postorder(node*t){
postorder(t->l);
postorder(t->r);
cout<<t->data;
}
=========================================