C++数据结构原代码(持续更新)

因为上课老师都是说半C++(用到C++的代码但还是用C的思想), 没有我最喜欢的模板类, 我想挑战一下自己,所以我用了class来写了我的数据结构, 内容都是原创的, 后期会开放到我的GitHub, 欢迎大家一起来学习, 提交您的意见.
数据结构 | C++ | 原创 | alittlemc | 最后一次更新:2019/04/16

1. 线性结构

1.1. 顺序表

#include <iostream>
#include <algorithm> //排序
//using namespace std;//头文件用不了
#ifndef _ALM_ARR_
#define _ALM_ARR_ 1
template <class A> //原创,想了好久
class arr
{
    int len;
    int top; //假装是数组吧,我设定分配空间可以有空的存在,这个有利于循环
    A *data;
    void err()
    {
        std::cout << "err" << std::endl;
        return;
    }
    void new_arr(int s)
    {
        len = s;
        data = new A[s + 1];
    }
    void new_arr(A *ar, int l, int s, int e)
    {
        top = e - s;
        len = l > e - s ? l : e - s;
        data = new A[len + 1]; //在这里必须预留一个空值,用于空表判断,但是好像有bug..
        for (int i = 0; s <= e; s++, i++)
            data[i] = *(ar + s - 1);
    }

public:
    arr(int s)
    {
        new_arr(s);
    }

    arr(A *ar, int l, int s, int e)
    {
        new_arr(ar, l, s, e);
    }
    /*~arr()
    {
        delete[] data;
    }*/
    void NewArr(int s)
    {
        delete[] data;
        new_arr(s);
    }
    void NewArr(A *ar, int l, int s, int e)
    {
        delete[] data;
        new_arr(ar, l, s, e);
    }

    void Ins(A x, int i)
    {

        if (i < 0 || i > len)
            err();
        else
        {
            //int top=getTop();
            for (int j = top; i <= j && data[j] != data[len]; j--)
                data[j] = data[j - 1];
            data[i - 1] = x;
            top++;
        }
    }

    void Ins(A *x, int i, int s, int e) //这个还没有弄好,以后再弄
    {
        if (i < 0 || i >= len)
            err();
        else
        {
            int top = getTop();
            i = i > top ? top : i;
            for (int j = top; i + e - s <= j && data[j] != data[len]; j--)
                data[j] = data[j - 1];
            for (int k = i; s <= e; k++, s++)
                data[k] = *(x + s - 1);
        }
    }
    void Del(int i)
    {
        top--;
        if (i < 0 || i >= len)
            err();
        else
        {
            int j = i;
            for (; j <= len && data[j] != data[len]; j++)

                data[j - 1] = data[j];

            if (data[j + 1] != NULL) //??不知道为什么NULL不了
                data[j + 1] = data[len];
        }
    }

    A &operator[](int i) //这样就可以使用data[int]
    {
        if (i < 0 || i >= len)
            std::cout << "err "
                      << "data[" << i << "]full";
        else
            return data[i];
    }
    int getFine_id(A x, int i)
    {
        int c = 0;
        i = i < 0 || i > len ? 1 : i;
        for (int j = 0; data[j + 1] != data[len]; j++)
        {
            if (x == data[j])
            {
                c++;
                if (i == c)
                    return ++j;
            }
        }
        return 0;
    }
    void Cout(int s, int e)
    {
        if (e - s < 0 && data[len - 1])
            err();

        std::cout << "{[1]=" << data[s];
        for (int i = 2; s + 1 < e; s++, i++)
            std::cout << ",[" << i << "]=" << data[s + 1];
        std::cout << '}' << std::endl;
    }
    void Cout(char *a)
    {
        Cout(0, len);
    }
    void Cout()
    {
        Cout(0, top);
    }
    void int_Ins(A x) //有序表插入数
    {
        if ((typeid(A).name() == typeid(int).name()) || (typeid(A).name() == typeid(float).name()) && data[0] <= data[1])
        {
            int j = 0;
            //if(j <= len && x <= data[j] && data[j] != data[len])
            for (j = 0; j <= len && x >= data[j] && data[j] != data[len]; j++)
                ;

            Ins(x, j + 1);
        }
        else
            err();
    }

    int getTop()
    {
        return top;
    }

    void Sort(int s, int e) //排序
    {
        if (s < e || s > 0)
            std::sort(&data[s], &data[e]);
    }

};
#endif

int main() //测试
{
    typedef int A;
    A ar1[] = {1, 2, 3, 5, 6, 7, 8, 9};

    arr<A> arr1(ar1, 11, 1, 9);

    arr1.Cout();

    arr1.int_Ins(4); //插入依然有序
    arr1.int_Ins(120);//插入多个试试
    arr1.int_Ins(121);
    arr1.Cout();

    A ar2[] = {1, 2, -2, -1, 2, -1, -33, -5};

    arr<A> arr2(ar2, 11, 1, 9);
    arr2.Sort(0, arr2.getTop());//排序就可以了
   arr2.Cout();

    system("pause");
    return 0;
}

1.2. 链表

简单介绍C++ STL的链表

'头文件'
#include<list>
'初始化'
std::list<int> list1;
'API'
list1.push_front(10);//后插
'迭代器'
std::list<int>::iterator i=list1begin();//首迭代器指针
std::cout<<*i<<"->";
for(;i!=list1.end();i++)//尾迭代器
{
std::cout<<*i<<"->";
}

自己实现

#ifndef _ALM_NODELINK_
#define _ALM_NODELINK_ 1
#include <iostream>
template <class A>
class list; //前置声明,定义友元时使用了

template <class A>
class list_iterator; //前置声明,定义友元时使用了

template <class A>
class node //节点
{
    friend class list<A>; //list可以访问该class的内部,友元类,也可以嵌套node(public)到list
    friend class list_iterator<A>;

public:
    node(A x)
    {
        data = x;
        next = 0; //尾巴
    }

private:
    A data;
    node *next;
};

template <class A>
class list //链表
{
    friend class list_iterator<A>;

public:
    list() { first = 0; } //空

    list(A *arr, int s, int e, bool mod = true)
    {
        first = 0;

        if (s > 0 || e > s)
            if (mod)
                for (; s <= e - 1; e--)
                    Ins(*(arr + e - 1));
            else
                for (; s <= e - 1; s++)
                    Ins(*(arr + s - 1));
        else
            std::cout << "err";
    }

    void Ins(A x)
    {
        node<A> *newnode = new node<A>(x); //新开辟节点
        newnode->next = first;             //新节点连接旧的节点
        this->first = newnode;             //新节点为头
    }
    void Ins(A x, int i) //在第i个位置插入x
    {
        node<A> *p = first;
        i--;
        for (int j = 1; p->next && j < i; p = p->next, j++)
            ;

        if (p == first)
            Ins(x);
        else
        {
            node<A> *newnode = new node<A>(x); //新开辟节点
            newnode->next = p->next;           //新节点连接旧的节点
            p->next = newnode;
        }
    }

    A getMax(bool mod = true)
    {
        if ((typeid(A).name() == typeid(int).name()) || (typeid(A).name() == typeid(float).name()))
        {
            node<A> *p = first;
            A max = p->data;
            int i = 0, j = 0;
            for (; p; p = p->next, i++)
                if (p->data >= max)
                {
                    max = p->data;
                    j = i;
                }
            return mod ? max : j + 1;
        }
        std::cout << "err type!=int" << std::endl;
        return 0;
    }

    void Dle(A x, int i = 1)
    {
        node<A> *p1 = 0, *p2; //一个用于存储上一个,一个用于循环
        int j = 0;
        for (p2 = first; p2 && p2->data != x && i != j; p1 = p2, p2 = p2->next)
            j++; //for用于遍历,找到内容所对应的指针

        if (p2)
        {           //找到了p1(p2为true) 或 没找到p1(p2为false) 但是完成了遍历
            if (p1) //是不是头节点
                p1->next = p2->next;
            else
                this->first = first->next;
        }
        delete p2;
    }

    void Inv()
    {
        node<A> *p1 = first, *p2 = 0; //倒数第N个和第N个交换
        for (; p1;)
        {
            node<A> *p3 = p2;
            p2 = p1; //缓存p2在p3,p2交换p1交换

            p1 = p1->next; //步长+
            p2->next = p3;
        }
        this->first = p2;
    }
    void Char_a(list<A> &a, list<A> &B, list<A> &N)
    {
        node<A> *p = first;
        for (; p; p = p->next)
        {
            if (p->data > '0' && p->data < '9')
                N.Ins(p->data);
            if (p->data > 'A' && p->data < 'Z')
                B.Ins(p->data);
            if (p->data > 'a' && p->data < 'z')
                a.Ins(p->data);
        }
    }

    void Link(list<A> list_)
    {
        if (first) //本链表是不是空表
        {
            node<A> *p; //用于循环
            for (p = first; p->next; p = p->next)
                ;                  //无无其他条件遍历,用于找到尾巴
            p->next = list_.first; //和本链表尾巴连接上
        }
        else
            this->first = list_.first;
    }

    void Cout()
    {
        for (node<A> *p = first; p; p = p->next)
        {
            std::cout << p->data;
            if (p->next)
                std::cout << "->";
        }
        std::cout << std::endl;
    }
    

private:
    node<A> *first; //指向第一个节点的指针
};

template <class A> //迭代器
class list_iterator
{
public:
    list_iterator(const list<A> &l) : p1(l), p2(l.first){};

    bool Is_this_null() //当前迭代器指向是否为null
    {
        return p2 ? true : false;
    }

    bool Is_next_null() //当前节点的下一个节点是否为null
    {
        return p2 && p2->next ? true : false;
    }

    A *First()
    {
        return p1.first ? &p1.first->data : 0; //返回指针
    }
    const A *Next() //涉及const A与A类型转换
    {
        if (p2)
        {
            p2 = p2->next; //叠加p2
            return &p2->data;
        }
        else
            return 0;
    }
    void Cout() //迭代器打印模板
    {
        if (this->Is_this_null())
        {
            std::cout << *this->First();
            while (this->Is_next_null())
                std::cout << "->" << *this->Next();
            std::cout << std::endl;
        }
    }

private:
    const list<A> &p1;
    const node<A> *p2;
};

#endif

typedef int A;
int main()
{
    A arr[] = {10, 12, 3, 1, 300, 2, 3, 455, 67};
    list<A> list1(arr, 1, 9); //用数组初始化
    //list<A> list2();            //初始化空表
    list1.Cout();

    list1.Ins(550, 3); //插入(头)
    list1.Cout();      //class list打印

    list1.Ins(233,list1.getMax(0));//在最大值前面插入233
    list1.Cout();

    list1.Inv();//倒置
    list1.Cout();
    //list1.Dle(3, 2);            //删除第2个3
    //list1.Dle(3);               //删除第1个3
    //list_iterator<A> li(list1); //迭代器
    //li.Cout();                  //迭代器打印

    char *ch1="1ne34Hy9";
    list<char> ch(ch1,1,6);

    /*list<char> a();
    list<char> B();
    list<char> N();

    ch.Char_a(a,B,N);
    ch.Cout();

    a.Cout();
    B.Cout();
    N.Cout();*///
    //这个不知道为什么不可以
    system("pause");
    return 0;
}

1.3. 栈

1.3.1. 顺序栈

template<class S>
class stack_arr
{
    S *data;
    int top;
    int len;
void arr(S*arr,int s,int e)
    {
        if(e-s>len)
            return;
        for(int i=0;s<=e;s++,i++)
            data[i]=*(arr+s-1);
    }
public:
    stack_arr(int s)
    {
        top=len=s=s>0?s:1;
        data=new S[s];
    }

    stack_arr(S *arr,int l,int s,int e)
    {
        if(e-s<0) return;
        len=l=l>e-s?l:e-s;
        len--;
        data=new S[l];

        top=e-s+1;//+1是为了S_cout能正常显示,并且top对应元素个数
        arr(arr,s,e);
    }

    void Cout()
    {
        Cout(0,top);
    }

    void Cout(char *a)
    {
        Cout(0,len);
    }

    

    void Cout(int s,int e)
    {
        if(e-s<0)
        {
            std::cout<<"err"<<std::endl;
            return;
        }
        else if(top==0)
        {
            std::cout<<"{null}"<<std::endl;
            return;
        }
        std::cout<<'{'<<data[s];
        for(;s+1<e;s++)
            std::cout<<','<<data[s+1];
        std::cout<<'}'<<std::endl;
    }

    void Push(S x)
    {
        if(top<=len)
        {
        data[top]=x;
        top++;
        }else std::cout<<"Push err, Stack full"<<std::endl;
        }
    void Push(S *x,int s,int e)
    {
        for(;s<=e;s++)
            Push(*(x+s-1));
    }

    void Pop()
    {
        if(top==0)
        {
            std::cout<<"Del err, Stack==null"<<std::endl;
            return;
        }
        data[top-1]=NULL;
        top--;
    }

    void Clear()
    {
        Dle(top);
    }

    void Dle(int i)
    {
        for(;i>0;i--)
            Pop();

    }

    int getLen()
    {
        return len;
    }

    S getTop()
    {
        return data[top-1];
    }

    int getTop(bool a)
    {
        return top;
    }

};

链栈

template<class S>

template<class A>
class stack_list<A>;

//template<class A> class list_iterator;

template<class A>
class node
{
private:
    friend class stack_list<A>;
    //friend class list_iterator<A>;
public:
    node(A x)
    {
        data=x;
        next=0;
    }
private:
    A data;
    node* next;
    node* front;
};

class stack_list
{
private:
    node* top;
public:
    stack_list() {top=0;}

    stack_list(A x) 
    {
        node<A>* newnode=new node<A>(x);
        top=newnode;
        newnode->next=0;
    }
    
    void Push()
    {
    }
};

最后编辑于：2019.04.22 21:22:29

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,530评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 86,403评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,120评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,770评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,758评论 5赞 367
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,649评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,021评论 3赞 398
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,675评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,931评论 1赞 299
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,659评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,751评论 1赞 330
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,410评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,004评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,969评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,203评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,042评论 2赞 350
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,493评论 2赞 343