返回顶部

收藏

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

更多
#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

»更多 您可能感兴趣的代码
  1. 2012-11-03 19:34:50汉落塔算法 by bargain
  2. 2012-11-12 09:17:55矩阵顺时针旋转90度的算法实现 by sunqi
  3. 2012-12-06 21:45:10KMP匹配算法 by walker30
  4. 2014-04-05 21:47:42C++算法之通用数据结构 by niutao.linux
  5. 2014-04-27 17:47:31C++算法之A*算法 by 童学芬
  6. 2014-05-18 11:48:50冒泡排序,插入排序,基数排序,交互排序算法 by Kevin.
  7. 2014-05-30 15:32:20C++算法之链表逆转算法 by 小项
  8. 2014-06-04 11:11:39寻找出现奇数次的数 by lucasli
  9. 2014-06-18 11:38:34逆矩阵算法三 by sxgkwei
  10. 2014-06-28 18:54:15C++算法之内存数据 by Kevin.
  11. 2014-07-01 12:28:09Hanoi塔问题 by Kevin.
相关聚客文章
  1. leaver 发表 2013-06-02 07:44:22 阿里巴巴5月5日综合算法题详解
  2. dianlujitao 发表 2014-10-16 14:11:10 CodeForces 23A You’re Given a String…
  3. dianlujitao 发表 2013-10-14 02:23:16 WIKIOI 1501 二叉树最大宽度和高度
  4. dianlujitao 发表 2014-10-17 13:14:36 CodeForces 23B Party
  5. dianlujitao 发表 2014-10-17 13:32:08 POJ 2339 Rock, Scissors, Paper
  6. bystander 发表 2013-04-11 10:50:25 模板栈以及中缀表达式求值(C++实现)
  7. dianlujitao 发表 2014-10-17 13:42:33 POJ 3844 Divisible Subsequences
  8. dianlujitao 发表 2014-10-17 13:45:25 POJ 3122 Pie
  9. bystander 发表 2013-04-16 00:42:58 模板优先级队列及堆排序(C++实现)
  10. dianlujitao 发表 2014-10-17 13:52:22 POJ 2388 Who’s in the Middle
  11. abyssss 发表 2014-05-20 03:23:39 数据结构 最小堆 数组实现
  12. dianlujitao 发表 2014-10-17 13:56:48 POJ 1611 The Suspects

发表评论