返回顶部

收藏

线性表之不带头结点的双向循环链表

更多
#include<iostream>
using namespace std;
template<typename T>struct node{
    T data;
    node<T> *prior,*next;
};
template <typename T> class nLink
{
private:
    node<T> *head;
public:
    nLink()
    {
        head=NULL;
    }
    ~nLink()
    {
        clearLink();
    }
    void clearLink()
    {
        node<T> *p=head;
        if(p!=NULL)
        {
        p->prior->next=NULL;
        do{
            p=p->next;
            delete head;
            head=p;
        }
        while (p!=NULL);
    }
    }
    bool empty()
    {
        return head==NULL;
    }
    int linkLength()
    {
        node<T> *p=head;
        int i=1;
        while (p->next!=head)
        {
            i++;
            p=p->next;
        }
        return i;
    }
    node<T> *getAddress(int i)
    {
        node <T> *p=head;
        int j=1;
        if(i<1 || head ==NULL)
            return NULL;
        else {
            if(i==1)
                return p;
            do {
                j++;
                p=p->next;
            }while(p!=head && j<i);
                if(p==head)
                {
                    return NULL;
                }
                else return p;
        }
    }
    bool getElem(int i,T &e)
    {
        node<T> *p;
        if(!getAddress(i))
            return false;
        else {
            p=getAddress(i);
            e=p->data;
            return true;
        }
    }
    bool Insert(int i,T e)
    {
        node<T> *s,*p=getAddress(i-1);
        s=new node<T>;
        s->data=e;
        if(i==1)
        {
            if(head==NULL)
            {
                s->prior=s->next=s;
            }
            else {
            s->next=head;
            s->prior=head->prior;
            s->next->prior=s;
            s->next->prior=s;
        }
        head=s;
        return true;
    }
        else {
            if(p==NULL)
                return false;
            else {
                s->next=p->next;
                s->prior=p;
                s->next->prior=s;
                p->next=s;
                return true;
            }
        }
}
    bool deleteElem(int i,T &e)
        {
            node<T> *p=getAddress(i);
            if(p==NULL)
                return false;
            e=p->data;
            if(p->next==p)
            {
                head=NULL;
            }
            else {
                p->prior->next=p->next;
                p->next->prior=p->prior;
                if(p==head)
                    head=p->next;
            }
            delete p;
            return true;
        }
    void print()
    {
        node<T> *p=head;
        if(p!=NULL)
            do{
                cout<<p->data<<" ";
                p=p->next;
            }while(p!=head);
        cout<<endl;
    }
    template <class T>
    friend  ostream & operator <<(ostream &,nLink<T> &);
    template <class T>
    friend void MergeLink(nLink<T> &,nLink<T> &);
};
template <class T>
ostream & operator <<(ostream &out,nLink<T> &a)
{
    node<T> *p=a.head;
    if(p!=NULL)
    {
        do{
            out<<p->data<<" ";
            p=p->next;
        }while(p!=a.head);
    }
    out<<endl;
    return out;
}
template <class T>
void MergeLink(nLink<T> &a,nLink<T> &b)
{
    node<T> *pa,*pb,*p,*t;
    pa=a.head;
    pb=b.head;
    p=new node<T>;
    t=p;
    if(pa)
        pa->prior->next=NULL;
    if(pb)
        pb->prior->next=NULL;
    while(pa && pb)
    {
            if(pa->data<=pb->data)
            {
                p->next=pa;
                pa->prior=p;
                p=pa;
                pa=pa->next;
            }
            else {
                p->next=pb;
                pb->prior=p;
                p=pb;
                pb=pb->next;
            }
    }
    while (pa)
            {
                p->next=pa;
                pa->prior=p;
                p=pa;
                pa=pa->next;
            }
    while (pb)
            {
                p->next=pb;
                pb->prior=p;
                p=pb;
                pb=pb->next;
            }
        p->next=t->next;
        t->next->prior=p;
        a.head=p->next;
        b.head=NULL;
}
int main()
{
    nLink<int > La,Lb;
    cout<<"La是否为空?"<<boolalpha<<La.empty ()<<endl;
    for(int i=1;i<4;i++)
    {
        La.Insert(i,i);
    }
    cout<<La;
    for(int i=1;i<4;i++)
    {
        Lb.Insert(i,i+1);
    }
    cout<<Lb;
    MergeLink(La,Lb);
    cout<<La;
    cout<<Lb;
    return 0;
}
//该片段来自于http://outofmemory.cn

标签:c++,算法

收藏

0人收藏

支持

0

反对

0

发表评论