数据结构笔记归档

因为学算法主要是为了做题打打力扣周赛，为了效率高多数数据结构使用数组模拟。

链表

1. 单链表 http://zsenhe.com/article/19

#include <iostream>
using namespace std;
const int N = 1e5+50;
int e[N],ne[N],idx,head;
//初始化单链表
void init(){
  head = -1;
  idx = 0;
}
//插入头节点x
void inser_head(int x){
  e[idx] = x,ne[idx] = head;head = idx++;
}
//在k节点后插入x
void insert(int k,int x){
  e[idx] = x,ne[idx] = ne[k],ne[k] = idx++;
}
//删除k节点后的一个元素
void remove(int k){
  ne[k] = ne[ne[k]];
}

2. 双链表

   #include <iostream>
   using namespace std;
   const int N = 1e5+50;
   int l[N],r[N],e[N],idx;
   void init(){
     //0左端点，1右端点
     r[0] = 1,l[1] = 0;
     idx = 2;
   }
   //在节点k后插入x
   void inset(int k,int x){
     e[idx] = x;
     l[idx] = k;
     r[idx] = r[k];
     l[r[k]] = idx,r[k] = idx++;
   }
   //删除节点k
   void remove(int k){
     l[r[k]] = l[k];
     r[l[k]] = r[k];
   }

   tip: 当需在k左边插入元素时，调用insert(l[k],x)即可

栈和队列

1. 栈: http://zsenhe.com/article/25

   #include <iostream>
   using namespace std;
   const int N = 1e5+10;
   int stk[N],tt=0;
   
   //将x压入栈
   stk[++tt] = x;
   
   //弹出栈顶元素
   int tt = stk[tt--];
   
   //判断栈不为空
   return tt>0;

2. 队列 http://zsenhe.com/article/27

   #include <iostream>
   using namespace std;
   const int N = 1e5+10;
   int q[N];
   //队头索引
   int hh;
   //队尾索引
   int tt = -1;
   //加入队列
   void push(int x){
     q[++tt] = x;
   }
   //出队
   int pop(){
    return q[hh++];
   }
   //判断队列是否为空
   return hh > tt;

..整理中