circularlist.cpp

循环链表的实现程序

// circularList.cpp: implementation of the circularList class.
//
//////////////////////////////////////////////////////////////////////

#include "circularList.h"
#include <assert.h>

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

circularList::circularList():ptrToLastLink(0)
{
}

circularList::~circularList()
{
    deleteAllValues();
}

void circularList::addlast(int value)
{
    if(ptrToLastLink==0){
        ptrToLastLink = new link(value,0);
        ptrToLastLink->ptrToNextLink = ptrToLastLink;
    }
    else ptrToLastLink = ptrToLastLink->ptrToNextLink = new link(value,ptrToLastLink->ptrToNextLink);
}

void circularList::add(int value)
{
    if(ptrToLastLink==0){
        ptrToLastLink = new link(value,0);
        ptrToLastLink->ptrToNextLink = ptrToLastLink;
    }
    else ptrToLastLink->ptrToNextLink = new link(value,ptrToLastLink->ptrToNextLink);
}

void circularList::deleteAllValues()
{
    while(ptrToLastLink) removeFirst();
}

int circularList::firstElement() const
{
    assert(ptrToLastLink);
    if(ptrToLastLink->ptrToNextLink==ptrToLastLink) return (ptrToLastLink->value);
    else return ptrToLastLink->ptrToNextLink->value;
}

int circularList::includes(int value) const
{
    link *p = ptrToLastLink;
    do{
        if(p->value==value) return 1;
        p = p->ptrToNextLink;
    }while(p!=ptrToLastLink);
    
    return 0;
}

bool circularList::isEmpty() const
{
    return ptrToLastLink==0;
}

void circularList::removeFirst()
{
    assert(ptrToLastLink);
    if(ptrToLastLink==ptrToLastLink->ptrToNextLink){
        delete ptrToLastLink;
        ptrToLastLink = 0;
    }
    else{
        link *p = ptrToLastLink->ptrToNextLink;
        ptrToLastLink->ptrToNextLink = ptrToLastLink->ptrToNextLink->ptrToNextLink;
        delete p;
    }
}

circularList* circularList::duplicate() const
{   
    circularList *newlist = new circularList;
    if(ptrToLastLink){
        link *p = ptrToLastLink->ptrToNextLink,*q = newlist->ptrToLastLink = new link(ptrToLastLink->value,0);
        while(p!=ptrToLastLink){
            q = q->ptrToNextLink = new link(p->value,0);
            p = p->ptrToNextLink;
        }
        q->ptrToNextLink = newlist->ptrToLastLink; 
    }
    return newlist;
}

circularList::circularList(const circularList &source)
{
    if(source.isEmpty()) ptrToLastLink = 0;
    else{
        circularList *newlist;
        newlist = source.duplicate();
        ptrToLastLink = newlist->ptrToLastLink;
    }
}