linklist.cpp

用C++完成的双链表源代码

// LinkList.cc
// author: Ke Song based C source from pp Sister XiuJie Chen ;)
// http://kesongemini.diy.163.com
#include "stdafx.h"
#include <iostream.h>
#include <stdlib.h>				// exit
#include "LinkList.h"

void 
LinkList_T::
init( void )
{
	_top		= (LinkListNode_T *)this;
	_bottom = (LinkListNode_T *)this;
	_current= (LinkListNode_T *)this;
}

void
LinkList_T::
prepend( CONTENTS contents )
{
	LinkListNode_T *pNode = new LinkListNode_T;

	if (pNode == NULL)
	{
		panic("prepend: new failed");
	}
	else
	{
		pNode->prev		= (LinkListNode_T *)this;
		pNode->next		= _top;
		if( _bottom == (LinkListNode_T *) this )
			_bottom = pNode;
		_top->prev		= pNode;
		_top					= pNode;		// I don't want bearing operands' order in mind
															// So don't use " A = B = C " 
		pNode->contents	= contents;
	}
}

void
LinkList_T::
append( CONTENTS contents )
{
	LinkListNode_T *pNode = new LinkListNode_T;

	if (pNode == NULL)
	{
		panic("append: new failed");
	}
	else
	{
		pNode->prev		= _bottom;
		pNode->next		= (LinkListNode_T *)this;
		if (_top == (LinkListNode_T *)this)
			
			_top = pNode ;

		_bottom->next	= pNode;
		_bottom				= pNode;

		pNode->contents = contents;
	}
}

CONTENTS
LinkList_T::
deleteFirst( void )
{
	LinkListNode_T *pNode = _top;
	CONTENTS  contents;

	if (pNode == (LinkListNode_T *)this)
		return ((CONTENTS)NULL);

	_top = pNode->next;
	_top->prev = (LinkListNode_T *)this;

	if (_current == pNode)
		_current = pNode->next;

	contents = pNode->contents;

	delete pNode;
	pNode = NULL;

	return contents;
}

CONTENTS
LinkList_T::
deleteLast( void )
{
	LinkListNode_T *pNode = _bottom;
	CONTENTS  contents;

	if (pNode == (LinkListNode_T *)this)
		return ((CONTENTS)NULL);

	_bottom = pNode->prev;
	_bottom->next = (LinkListNode_T *)this;

	if (_current == pNode)
		_current = pNode->prev;

	contents = pNode->contents;

	delete pNode;
	pNode = NULL;

	return contents;
}

CONTENTS
LinkList_T::
deleteCurrent( void )
{
	LinkListNode_T *pNode = _current;
	CONTENTS  contents;

	if (pNode == (LinkListNode_T *)this)
		return ((CONTENTS)NULL);

	_current						= pNode->next;
	pNode->prev->next	= pNode->next;
	pNode->next->prev	= pNode->prev;

	contents = pNode->contents;

	delete pNode;
	pNode = NULL;

	return contents;
}

void
LinkList_T::
append2current( CONTENTS contents )
{
	LinkListNode_T *pNode = new LinkListNode_T;

	if (pNode == NULL)
	{
		panic("append2Current: new failed");
	}
	else
	{
		pNode->prev					= _current;
		pNode->next					= _current->next;
		pNode->contents			= contents;
		_current->next->prev	= pNode;
		_current->next				= pNode;
	}
}

void
LinkList_T::
prepend2current( CONTENTS contents )
{
	LinkListNode_T *pNode = new LinkListNode_T;

	if (pNode == NULL)
	{
		panic("prepend2Current: new failed");
	}
	else
	{
		pNode->prev					= _current->prev;
		pNode->next					= _current;
		pNode->contents			= contents;
		_current->prev->next	= pNode;
		_current->prev				= pNode;
	}
}

void
LinkList_T::
deleteAll( void )
{
	while (!isEmpty())
		deleteFirst();
}

void
LinkList_T::
freeAll( void )
{
	while (!isEmpty())
		delete deleteFirst();
}

void
LinkList_T::
freeCurrent( void )
{
	delete deleteCurrent();
}

bool
LinkList_T::
freeMatch ( CONTENTS contents )
{
	LinkListNode_T *pNode;

	for(pNode = _top; 
			pNode != (LinkListNode_T *)this; 
			pNode = pNode->next)
	{
		if (pNode->contents == contents)
		{
			freeNode(pNode);
			return true;
		}
	}

	return false;
}

LinkListNode_T* 
LinkList_T::
findMatch(CONTENTS contents)
{
	LinkListNode_T *pNode;

	for(pNode = _top; 
			pNode != (LinkListNode_T *)this; 
			pNode = pNode->next)
	{
		if (pNode->contents == contents)
				return pNode;
	}

	return (LinkListNode_T *)NULL;
}

int
LinkList_T::
index ( CONTENTS contents )
{
	LinkListNode_T *pNode;
	int index = 0;

	for(pNode = _top; 
			pNode != (LinkListNode_T *)this; 
			pNode = pNode->next, index++)
	{
		if (pNode->contents == contents)
				return index;
	}

	return -1;
}

CONTENTS
LinkList_T::
contents( int index )
{
	LinkListNode_T *pNode;
	int count = 0;

	for(pNode = _top; 
			pNode != (LinkListNode_T *)this; 
			pNode = pNode->next, count++)
	{
		if (count == index)
			return pNode->contents;
	}

	return (CONTENTS)NULL;		// (CONTENTS)-1 //old
}

void
LinkList_T::
freeNode(LinkListNode_T *pNode)
{
	delete deleteNode(pNode);
}

CONTENTS
LinkList_T::
deleteNode(LinkListNode_T *pNode)
{
	CONTENTS contents;

	if (pNode == (LinkListNode_T *)this)
	{
		return ((CONTENTS)NULL);
	}
	else if (pNode == _current)
	{
		return deleteCurrent();
	}
	else
	{
		pNode->prev->next = pNode->next;
		pNode->next->prev = pNode->prev;
		contents = pNode->contents;

		delete pNode;

		return contents;
	}
}

void 
LinkList_T::
panic ( char *s )								//static
{
	cout<<s<<endl;
	exit(1);
}