链表

#include<bits/stdc++.h>

using namespace std;
class Chain;

class ChainNode
{
        friend Chain;
        friend void Merge(Chain& a,Chain& b,Chain& c);
        friend ostream& operator <<(ostream &cout,const Chain &chain);
    private:
        int data;
        ChainNode *link;
};

class Chain
{
    friend void Merge(Chain& a,Chain& b,Chain& c);
    public:
        Chain()
        {
            first=NULL;
        }
        ~Chain()
        {
            ChainNode *next;
            while(first)
            {
                next=first->link;
                delete first;
                first=next;
            }
        }
        bool IsEmpty()const
        {
            return first==NULL;
        }
        int Search(const int &x)const
        {
            ChainNode *current=first;
            int index=1;
            while(current&&current->data!=x)
            {
                current=current->link;
                index++;
            }
            if(current)return index;
            return 0;
        }
        bool Delete(int k)
        {
            if(k<=1||!first)
            {
                return false;
            }
            ChainNode *p=first;
            if(k==1)first=first->link;
            else
            {
                ChainNode *q=first;
                for(int index=1;index<k-1&&q;index++)
                {
                    q=q->link;
                }
                if(!q||!q->link)return false;
                p=q->link;
                q->link=p->link;
            }
            delete p;
            return true;
        }
        void Insert(int x)
        {
            ChainNode *y=new ChainNode;
            y->data=x;
            if(first==NULL||first->data>=x)
            {
                y->link=first;
                first=y;
                return;
            }else
            {
                ChainNode *cur=first;
                if(first->link==NULL)
                {
                    first->link=y;
                    return;
                }
                while(cur->link!=NULL&&cur->link->data<=x)
                {
                    cur=cur->link;
                }
                if(cur->link==NULL)
                {
                    cur->link=y;
                }else
                {
                    y->link=cur->link;
                    cur->link=y;
                }
            }

            return;
        }
        friend ostream& operator <<(ostream &cout,const Chain &chain);
    private:
        ChainNode *first;
};

ostream& operator <<(ostream &cout,const Chain &chain)
{
    ChainNode *cur=chain.first;
    if(cur==NULL)
    {
        cout<<"<null>"<<endl;
    }else
    {
        while(cur->link!=NULL)
        {
            cout<<cur->data<<",";
            cur=cur->link;
        }
        cout<<cur->data<<endl;
    }
    return cout;
}

void Merge(Chain& a,Chain& b,Chain& c)
{

    ChainNode *cura,*curb,*pos;
    cura=a.first;
    curb=b.first;
    while(cura!=NULL&&curb!=NULL)
    {
        int x;
        if(cura->data<=curb->data)
        {
            x=cura->data;
            cura=cura->link;
        }else
        {
            x=curb->data;
            curb=curb->link;
        }
        ChainNode *y=new ChainNode;
        y->data=x;
        if(c.first==NULL)
        {
            pos=c.first=y;
            continue;
        }
        pos->link=y;
        pos=pos->link;
    }
    while(cura!=NULL)
    {
        int x;
        x=cura->data;
        cura=cura->link;
        ChainNode *y=new ChainNode;
        y->data=x;
        if(c.first==NULL)
        {
            pos=c.first=y;
            continue;
        }
        pos->link=y;
        pos=pos->link;
    }
    while(curb!=NULL)
    {
        int x;
        x=curb->data;
        curb=curb->link;
        ChainNode *y=new ChainNode;
        y->data=x;
        if(c.first==NULL)
        {
            pos=c.first=y;
            continue;
        }
        pos->link=y;
        pos=pos->link;
    }
}       

int main()
{
    cout<<"Input1"<<endl;
    Chain a,b,c;
    while(1)
    {
        int x;
        cin>>x;
        if(!x)break;
        a.Insert(x);
    }
    cout<<"Output1"<<endl;
    cout<<a;
    while(1)
    {
        int x;
        cin>>x;
        if(!x)break;
        b.Insert(x);
    }
    cout<<"Output2"<<endl;
    cout<<b;
    Merge(a,b,c);
    cout<<"Combine"<<endl;
    cout<<c;
    cout<<"Insert"<<endl;
    int x;
    cin>>x;
    c.Insert(x);
    cout<<"Insertion"<<endl;
    cout<<c;
    cout<<"Delete"<<endl;
    cin>>x;
    cout<<"Deletion"<<endl;
    c.Delete(c.Search(x));
    cout<<c;
    cout<<"Find"<<endl;
    cin>>x;
    cout<<"Position"<<endl;
    cout<<c.Search(x)<<endl;
    cout<<"End"<<endl;
}