首页 > 其他分享 >数据结构模板整合

数据结构模板整合

时间：2022-10-29 11:24:20浏览次数：47  
标签：head ch void next tail 整合 数据结构 type 模板

栈

#include<iostream>
#include<cstdio>
#define maxn 100010

using namespace std;

int n,x;

template<typename type>
inline void read(type &x)
{
    x=0;bool flag(0);char ch=getchar();
    while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    flag?x=-x:0;
}

template<typename type>
inline void write(type x,bool flag=1)
{
    x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
    do Stack[++top]=x%10,x/=10;while(x);
    while(top) putchar(Stack[top--]|48);
    flag?putchar('\n'):putchar(' ');
}

class stack
{
    public:
        stack(){n=0;}
        void push(int x){a[++n]=x;}
        void pop(){n--;}
        int top(){return a[n];}
        int size(){return n;}
        bool empty(){return !n;}
        void traversal(){for(int i=1;i<=n;i++)write(a[i],0);puts("");}
    private:
        int n;
        int a[maxn];
}s;

signed main()
{
    read(n);
    for(int i=1;i<=n;++i) read(x),s.push(x);
    s.traversal();
    return 0;
}

队列

#include<iostream>
#include<cstdio>
#include<queue>
#define maxn 100010

using namespace std;

int n,x;

template<typename type>
inline void read(type &x)
{
    x=0;bool flag(0);char ch=getchar();
    while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    flag?x=-x:0;
}

template<typename type>
inline void write(type x,bool flag=1)
{
    x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
    do Stack[++top]=x%10,x/=10;while(x);
    while(top) putchar(Stack[top--]|48);
    flag?putchar('\n'):putchar(' ');
}

class queue
{
    public:
        queue(){head=tail=cnt=0;}
        void push(int x){a[tail]=x,tail=(tail+1)%maxn,cnt++;}
        void pop(){head=(head+1)%maxn,cnt--;}
        int front(){return a[head];}
        int back(){return a[tail];}
        int size(){return cnt;}
        bool empty(){return !cnt;}
        void traversal(){for(int i=0;i<cnt;++i)write(a[(head+i)%(tail+1)],0);puts("");}
    private:
        int head,tail,cnt,a[maxn];
}q;

signed main()
{
    read(n);
    for(int i=1;i<=n;++i) read(x),q.push(x);
    q.traversal();
    return 0;
}

双端队列

#include<iostream>
#include<cstdio>
#include<queue>
#define maxn 100010

using namespace std;

int n,x;

template<typename type>
inline void read(type &x)
{
    x=0;bool flag(0);char ch=getchar();
    while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    flag?x=-x:0;
}

template<typename type>
inline void write(type x,bool flag=1)
{
    x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
    do Stack[++top]=x%10,x/=10;while(x);
    while(top) putchar(Stack[top--]|48);
    flag?putchar('\n'):putchar(' ');
}

class deque
{
    private:
        int head,tail,n;
    public:
        int a[maxn];
        deque(){head=tail=n=0;}
        void push_front(int x){head=(head?head-1:maxn-1),a[head]=x,n++;}
        void push_back(int x){a[tail]=x,tail=(++tail^maxn?tail:0),n++;}
        void pop_front(){head=(++head^maxn?head:0),n--;}
        void pop_back(){tail=(tail?tail-1:maxn-1),n--;}
        int front(){return a[head];}
        int back(){return a[tail?tail-1:maxn-1];}
        int& operator [](int i){return a[head+i-1-(head+i-1<maxn?0:maxn)];}
        int size(){return n;}
        bool empty(){return !n;}
        void traversal(){for(int i=0;i<n;++i)write(a[head+i-(head+i<maxn?0:maxn)],0);puts("");}
}dq;


signed main()
{
    read(n);
    for(int i=1;i<=n;++i) read(x),dq.push_back(x);
    dq.traversal();
    return 0;
}

链表

#include<iostream>
#include<cstdio>

using namespace std;

int n,x;

template<typename type>
inline void read(type &x)
{
    x=0;bool flag(0);char ch=getchar();
    while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    flag?x=-x:0;
}

template<typename type>
inline void write(type x,bool mode=1)
{
    x<0?x=-x,putchar(' '):0;static short Stack[50],top(0);
    do Stack[++top]=x%10,x/=10;while(x);
    while(top) putchar(Stack[top--]|48);
    mode?putchar('\n'):putchar(' ');
}

class node
{
    public:
        int val;
        node *pre=NULL,*next=NULL;
};

class List
{
    public:
        node *head,*tail;
        List(){head=new node(),tail=new node(),head->next=tail,tail->pre=head;}
        ~List(){while(head!=tail)head=head->next,delete head->pre;delete tail;}
        void insert(node *p,int x)//insert x after p
        {
            node *t=new node();
            t->val=x,t->pre=p,t->next=p->next;
            p->next->pre=t,p->next=t;
        }
        void erase(node *p)
        {
            p->pre->next=p->next;
            p->next->pre=p->pre;
            delete p;
        }
}list;

signed main()
{
    read(n);
    for(int i=1;i<=n;++i) read(x),list.insert(list.tail->pre,x);
    for(node *p=list.head->next;p!=list.tail;p=p->next) write(p->val,0);
    return 0;
}

二叉堆

#include<iostream>
#include<cstdio>
#define maxn 100010

using namespace std;
namespace ly
{
    auto swap=[](auto &a,auto &b){auto t=a;a=b,b=t;};
}

int n,x;

template<typename type>
inline void read(type &x)
{
    x=0;bool flag(0);char ch=getchar();
    while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    flag?x=-x:0;
}

template<typename type>
inline void write(type x,bool mode=1)
{
    x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
    do Stack[++top]=x%10,x/=10;while(x);
    while(top) putchar(Stack[top--]|48);
    mode?putchar('\n'):putchar(' ');
}

class heap
{
    public:
        heap(bool mode=0){type=mode,n=0;}
        void up(int i){while(i^1&&a[i]^a[i>>1]&&type^(a[i]<a[i>>1]))ly::swap(a[i],a[i>>1]),i>>=1;}
        void down(int i)
        {
            i<<=1;
            while(i<=n)
            {
                if(i^n&&a[i]^a[i+1]&&type^(a[i+1]<a[i])) i++;
                if(a[i]^a[i>>1]&&type^(a[i]<a[i>>1])) ly::swap(a[i],a[i>>1]),i<<=1;
                else break;
            }
        }
        void push(int x){a[++n]=x,up(n);}
        void pop(){ly::swap(a[1],a[n--]),down(1);}
        int top(){return a[1];}
        int size(){return n;}
        bool empty(){return !n;}
        void erase(int i){ly::swap(a[i],a[n--]),up(i),down(i);}
        void traversal(){heap t=*this;while(!t.empty())write(t.top(),0),t.pop();puts("");}
    private:
        bool type;//0:min_heap 1:max_heap
        int n;
        int a[maxn];
};

heap q1(0),q2(1);

signed main()
{
    read(n);
    for(int i=1;i<=n;++i) read(x),q1.push(x),q2.push(x);
    q1.traversal(),q2.traversal();
    return 0;
}

整合「封装+模板」

#include<iostream>
#include<cstdio>
#define maxn 1000010

using namespace std;
namespace IO
{
    template<typename type>
    inline void read(type &x)
    {
        x=0;bool flag(0);char ch=getchar();
        while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
        while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        flag?x=-x:0;
    }

    template<typename type>
    inline void write(type x,bool flag=1)
    {
        x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
        do Stack[++top]=x%10,x/=10;while(x);
        while(top) putchar(Stack[top--]|48);
        flag?putchar('\n'):putchar(' ');
    }
}using namespace IO;
namespace ly
{
    auto swap=[](auto &x,auto &y){auto t=x;x=y,y=t;};
    template<typename type>
    class stack
    {
        private:
            int n;
            type a[maxn];
        public:
            stack(){n=0;}
            void push(type x){a[++n]=x;}
            void pop(){n--;}
            type top(){return a[n];}
            int size(){return n;}
            bool empty(){return !n;}
            void traversal(){for(int i=1;i<=n;++i)write(a[i],0);puts("");}
    };
    template<typename type>
    class queue
    {
        public:
            queue(){head=tail=n=0;}
            void push(int x){a[tail]=x,tail=(tail+1)%maxn,n++;}
            void pop(){head=(head+1)%maxn,n--;}
            int front(){return a[head];}
            int back(){return a[(tail-1+maxn)%maxn];}
            int size(){return n;}
            bool empty(){return !n;}
            void traversal(){for(int i=0;i<n;++i)write(a[(head+i)%n],0);puts("");}
        private:
            int head,tail,n;
            type a[maxn];
    };
    template<typename type>
    class deque
    {
        private:
            int head,tail,n;
        public:
            type a[maxn];
            deque(){head=tail=n=0;}
            void push_front(type x){head=(head?head-1:maxn-1),a[head]=x,n++;}
            void push_back(type x){a[tail]=x,tail=(++tail^maxn?tail:0),n++;}
            void pop_front(){head=(++head^maxn?head:0),n--;}
            void pop_back(){tail=(tail?tail-1:maxn-1),n--;}
            type front(){return a[head];}
            type back(){return a[tail?tail-1:maxn-1];}
            type& operator [](int i){return a[head+i-1-(head+i-1<maxn?0:maxn)];}
            int size(){return n;}
            bool empty(){return !n;}
            void traversal(){for(int i=0;i<n;++i)write(a[head+i-(head+i<maxn?0:maxn)],0);puts("");}
    };
    template<typename type>
    class node
    {
        public:
            type val;
            node *pre,*next;
            node(){pre=NULL,next=NULL;}
    };
    template<typename type>
    class list
    {
        public:
            node<type> *head,*tail;
            list(){head=new node<type>(),tail=new node<type>(),head->next=tail,tail->pre=head;}
            ~list(){while(head!=tail)head=head->next,delete head->pre;delete tail;}
            void insert(node<type> *p,type x)
            {
                node<type> *t=new node<type>();
                t->val=x,t->pre=p,t->next=p->next;
                p->next->pre=t,p->next=t;
            }
            void erase(node<type> *p)
            {
                p->next->pre=p->pre;
                p->pre->next=p->next;
                delete p;
            }
            bool empty(){return head->next==tail;}
            void traversal(){for(auto i=head->next;i!=tail;i=i->next)write(i->val,0);puts("");}
    };
    template<typename T>
    class heap
    {
        private:
            bool type;//0:min_heap 1:max_heap
            int n;
            T a[maxn];
        public:
            heap(bool flag=1){type=flag,n=0;}
            void up(int i){while(i^1&&a[i]^a[i>>1]&&type^(a[i]<a[i>>1]))ly::swap(a[i],a[i>>1]),i>>=1;}
            void down(int i)
            {
                i<<=1;
                while(i<=n)
                {
                    if(i^n&&a[i]^a[i+1]&&type^(a[i+1]<a[i])) i++;
                    if(a[i]^a[i>>1]&&type^(a[i]<a[i>>1])) ly::swap(a[i],a[i>>1]),i<<=1;
                    else break;
                }
            }
            void push(T x){a[++n]=x,up(n);}
            void pop(){ly::swap(a[1],a[n--]),down(1);}
            T top(){return a[1];}
            int size(){return n;}
            bool empty(){return !n;}
            void erase(int i){ly::swap(a[i],a[n--]),up(i),down(i);}
            void traversal(){heap t=*this;while(!t.empty())write(t.top(),0),t.pop();puts("");}
    };
}

int n,x;
ly::stack<int>s;
ly::queue<int>q;
ly::deque<int>dq;
ly::list<int>l;
ly::heap<int>h1(0),h2(1);

signed main()
{
    read(n);
    for(int i=1;i<=n;++i) read(x),s.push(x),q.push(x),dq.push_back(x),l.insert(l.tail->pre,x),h1.push(x),h2.push(x);
    s.traversal(),q.traversal(),dq.traversal(),l.traversal(),h1.traversal(),h2.traversal();
    return 0;
}

标签：head,ch,void,next,tail,整合,数据结构,type,模板
From： https://www.cnblogs.com/lingyunvoid/p/DS.html

相关文章

  • 二分法&三分法模板
    二分法求函数零点longdoublel=INT_MIN,r=INT_MAX,mid,eps=1e-6;while(r-l>eps){ mid=(l+r)/2; if(f(mid)<0)l=mid; elser=mid;}cout<<l<<endl;三分法......
  • 基于C语言的通用型数据结构与容器库
    仓库地址:github：https://github.com/hellototoro/hlibcgitee：https://gitee.com/totorohello/hlibclist双向序列容器，用于将它们的元素保持为线性排列，并允许在序列的任何......
  • 【模板】边双
    这里介绍一种与众不同的写法。前置知识：强联通分量回忆强联通分量的算法过程，我们利用有向图的dfn树将图上的所有边分成四种：树边、前向边、后向边和横向边。其中在原......
  • 数据结构 玩转数据结构 4-3 使用链表的虚拟头结点
    0课程地址https://coding.imooc.com/lesson/207.html#mid=13446 1重点关注1.1代码草图解析 1.2为何为链表头设立虚拟头节点为......
  • 2流高手速成记（之五）：Springboot整合Shiro实现安全管理
    废话不多说，咱们直接接上回上一篇我们讲了如何使用Springboot框架整合Nosql，并于文章最后部分引入了服务端Session的概念而早在上上一篇中，我们则已经讲到了如何使用Springb......
  • Spring整合Mybatis
    spring中整合mybatis一先添加spring框架1.创建一个maven项目2.在pom.xml中添加springjar包<!--Spring--><dependency><groupId>org.springframework</groupI......
  • 数据结构整理笔记(未完)
    链表本质上是一个结构体指向下一个结构体，第一个结构体为链头，重点是指向下一个(next)结构体代码实现创建链表structElement//链表元素{char*nam......
  • 二分模板
    二分模板一共有两个，分别适用于不同情况。算法思路：假设目标值在闭区间[l,r]中，每次将区间长度缩小一半，当l=r时，我们就找到了目标值。版本1当我们将区间[l,r]划分成[l,m......
  • 标准模板库 02 容器vector
    容器大致分为序列式容器（Sequence），关联式容器（Associative）和无序容器（Unordered），无序容器也可以归为关联式容器内。序列式容器（Sequence）array：数组，是一种固定大小的结构，静态空......
  • Spring整合Kafaka（二十六）
    1引入依赖<dependency><groupId>org.springframework.kafka</groupId><artifactId>spring-kafka</artifactId></dependency>2配置Kafka配置server、cons......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99