0x13.基础数据结构—链表与邻接表

2020-05-05 12:46 380人阅读评论(0)

本系列博客是《算法竞赛进阶指南》+《算法竞赛入门经典》+《挑战程序设计竞赛》的学习笔记，~~主要是因为我三本都买了~~ 按照《算法竞赛进阶指南》的目录顺序学习，包含书中的部分重要知识点、例题答案及我个人的学习心得和对该算法的补充拓展，仅用于学习交流和复习，无任何商业用途。博客中部分内容来源于书本和网络（我尽量减少书中引用），由我个人整理总结（~~习题和代码可全都是我自己敲哒~~）部分内容由我个人编写而成，如果想要有更好的学习体验或者希望学习到更全面的知识，请于京东搜索购买正版图书：《算法竞赛进阶指南》— 作者李煜东，强烈安利，好书不火系列，谢谢配合。

下方链接为学习笔记目录链接（中转站）

学习笔记目录链接

ACM-ICPC模板

一、链表

两种双向链表模板

0.指针

int n,m;

struct Node{
    int val;
    Node *prev,*next;
};
Node *head,*tail;

void initialize(){//建新结点
    head=new Node();
    tail=new Node();
    head->next=tail;
    tail->prev=head;
}

inline void insert(Node *p,int val){//在p的后面插入包含数据val的新结点
    q=new Node();
    q->val=val;
    p->next->prev=q;
    q->next=p->next;
    p->next=q;
    q->prev=p;
}

inline void remove(Node *p){//删除p
    p->prev->next=p->next;
    p->next->prev=p->prev;
    delete p;
}

inline void recycle(){//链表的内存回收
    while(head!=tail){
        head=head->next;
        delete head->prev;
    }
    delete tail;
}

1.数组

struct node
{
    int val;
    int pre, nex;
} List[SIZE];

int head, tail, cnt;

void init()
{
    cnt = 2;
    head = 1, tail = 2;
    List[head].nex = tail;
    List[tail].pre = head;
}

void insert(int p, int val)
{
    cnt++;
    int tmp = cnt;

    List[tmp].val = val;
    List[List[p].nex].pre = tmp;
    List[tmp].nex = List[p].nex;
    List[p].nex =tmp;
    List[tmp].pre = p;
}

void remove(int p)//用数组模拟链表的清空
{
    List[List[p].pre].nex = List[p].nex;
    List[List[p].nex].pre = List[p].pre;
}

AcWing 136. 邻值查找

https://www.acwing.com/problem/content/description/138/

1.平衡树

本题可以直接用平衡树来做，STL里自带的set，自动去重加自动排序。
注意STL里容器使用upper_bound什么的得到的都是迭代器，直接用auto 去接受就好。
注意两点：
本题的数据范围为1e9，所以数据直接全部改用long long ，容器也要用long long ，如果INF用long long 而容器用的是int，INF就会被压缩，然后就WA啦。
还有就是咱菜就不要炫技，能分开写几行完成就不要压到一行，因为这WA了是真的亏。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<math.h>
#include<set>
#include<limits.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register int i=s;i<=t;++i)
#define lver(i,t,s) for(register int i=t;i>=s;--i)
//#define int __int128
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;

const int N=1e7+7;
const int mod=1e9+7;
const ll INF=1e15+7;
const double EPS=1e-5;//趋近为0

int n,m;
ll val;
set< PLL >se;
//一旦题目范围达到了1e9求全部改成ll
int main()
{
    cin>>n;
    se.insert({INF,0});//设置两个边界哨兵
    se.insert({-INF,0});//INF设的是ll,那set里也必须是ll
    over(i,1,n){
        scanf("%lld",&val);
        if(i>1){
            auto it=se.upper_bound({val,0});//只会按照first来查找,second随意
            auto jt=it;jt--;//别乱压行，咱菜就分开写
            ll lval=abs((ll)val-jt->first),rval=abs(it->first-(ll)val);
            if(lval<=rval)printf("%lld %d\n",lval,jt->second);
            else printf("%lld %d\n",rval,it->second);
        }
        se.insert({val,i});
    }
    return 0;
}

2.链表

将序列A从小到大排序，然后依次串成一个链表，同时建立一个数组B，其中 $B_i$ 表示原始序列中 $A_i$ 的位置（指针）。
这样一来，指针 $B_n$ 指向的节点的前驱和后继就是原始序列中值和 $A_n$ 最相近的两个元素，即可以计算出 $A_n$ 对应的答案。
接下来，在链表中删除 $B_n$ 指向的元素，然后用同样的方法操作 $B_{n-1}$ ，如此往复。

懒得写了，放一个别人写的链接的吧
https://blog.csdn.net/weixin_43916947/article/details/86723767

3.线段树

这种查询大小的题怎么能少得了我大线段树呢？
~~主要是好久没有写了，看到有线段树的题解就想写一下练个手~~
思路：
先离散化，然后维护一颗权值线段树，先把 a[1] 加进去。
后面对于每个 i，先查询前面已经有多个比它小的，设为level。
此时序列中第 level 大的数即为 a[i] 的前驱，第 level+1 大的即为 a[i]a[i] 的后继（序列中的数各不相同）。
两者取个最小，若相等则选前驱。
思路来源：https://www.acwing.com/solution/acwing/content/4560/

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<math.h>
#include<map>
#include<limits.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r>>1)
#define over(i,s,t) for(register int i=s;i<=t;++i)
#define lver(i,t,s) for(register int i=t;i>=s;--i)
//#define int __int128
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;

const int N=1e5+7;
const int mod=1e9+7;
const ll INF=1e15+7;
const double EPS=1e-5;//趋近为0

struct node{
    int g;
    int l,r;
}tree[N<<2];
map<int,int>id;
int n,m;
int a[N],b[N];
int ans,tmp,now;

void build(int p,int l,int r){//建树
    tree[p].l=l,tree[p].r=r;
    if(l==r)return;
    build(ls,l,mid);
    build(rs,mid+1,r);
}
#undef mid
inline void add(int p,int x,int l,int r){//单点修改
    if(tree[p].l==tree[p].r){
        ++tree[p].g;
        return ;
    }
    int mid=(tree[p].l+tree[p].r)>>1;
    if(x<=mid)
        add(ls,x,l,r);
    else add(rs,x,l,r);
    tree[p].g=tree[ls].g+tree[rs].g;
}

inline int ask(int p,int k){//当前这棵树的查询第k大
    if(tree[p].l==tree[p].r)
        return tree[p].r;
    if(tree[ls].g>=k)//说明在左边
        return ask(ls,k);
    else return ask(rs,k-tree[ls].g);//右边
}

inline int ask_level(int p,int x){//查询<=x的数的个数
    if(tree[p].l==tree[p].r)
        return tree[p].g;
    int mid=tree[p].l+tree[p].r>>1;
    if(x<=mid)
        ask_level(ls,x);
    else return tree[ls].g+ask_level(rs,x);
}


int main()
{
    cin>>n;
    over(i,1,n){
        scanf("%d",&a[i]);
        b[i]=a[i];
        if(!id[a[i]])id[a[i]]=i;
    }
    sort(b+1,b+1+n);//离散化
    build(1,1,n);
    tmp=lower_bound(b+1,b+1+n,a[1])-b;//离散化
    add(1,tmp,1,n);
    over(i,2,n){
        int k=lower_bound(b+1,b+1+n,a[i])-b;//离散化后的值
        int level=ask_level(1,k-1);//查询小于a[i]的数的个数
        if(level)
            now=ask(1,level);//查找第level大（前驱）
        if(level+1<=i-1){
            tmp=ask(1,level+1);//后继
            if(!now||abs(a[i]-b[now])>abs(b[tmp]-a[i]))
                now=tmp;
        }
        printf("%d %d\n",abs(a[i]-b[now]),id[b[now]]);
        add(1,k,1,n);
    }
    return 0;
}

二、邻接表

~~这玩意不是应该叫链式前向星嘛~~

链式前向星–最通俗易懂的讲解

图片表示一张5个点，6条边的图，边按插入顺序为： $(1, 2),(2, 3),(2, 5),(3, 5),(5, 4),(5, 1)。$

$ver$ 数组储存终点， $edge$ 数组储存权值， $next$ 数组储存每一条边的下一条边 $head$ 储存以某一个点为起点的第一个点， $head$ 与 $next$ 储存的都是 $ver$ 的下表。

void add(int from, int to, int weight)
{
    cnt++;
    ver[cnt] = to;
    edge[cnt] = weight;
    next[cnt] = head[from];
    head[from] = cnt; 
    // 在链表开头插入，每一个链表代表从某一点开始所有能到达的点
}

// 访问从x出发的所有边
for (int i = head[x]; i; i = next[i])
{
    int from = x;
    int to = ver[i];
    int weight = edge[i];
    // 进行操作
}

注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧

转载：https://blog.csdn.net/weixin_45697774/article/details/105927458

查看评论

飞道的博客

飞道的博客

个人资料

文章分类

文章存档

阅读排行

评论排行

推荐文章