C++実装シングルチェーンテーブル

3972 ワード

#include 
using namespace std;

//       
template
class SingleList
{
public:
	SingleList();
	~SingleList();

private:
	typedef struct tagNode		//     
	{
		_Ty		_elem;			//   
		struct tagNode* pNext;	//    
	}NODE,*PNODE;

	tagNode*	m_pHead;		//    
	tagNode*	m_pTitle;		//   		[             ]
	int			m_size;			//      

public:
	//          
	bool append(_Ty elem);
	//           
	bool insert(int pos,_Ty elem);
	//        
	_Ty front();
	//         
	_Ty last();
	//       
	int length(){return m_size};
	//         
	bool deletepos(int pos,_Ty& res);
	//         
	bool deleteall();
	//       
	bool empty();
	//     
	void traverse();
};

template
SingleList<_ty>::SingleList()
{
	m_pHead = (tagNode *)malloc(sizeof(tagNode));
	m_pTitle = m_pHead;
	m_size = 0;
}

template
SingleList<_ty>::~SingleList()
{	
	if(m_pHead->pNext != NULL)
	{
		deleteall();	//       
	}
	free(m_pHead);
}

//          
template
bool SingleList<_ty>::append(_Ty elem)
{
	tagNode* pNewNode = (tagNode *)malloc(sizeof(tagNode));
	if(pNewNode == NULL)
	{
		return false;	//         
	}
	pNewNode->_elem = elem;
	pNewNode->pNext = NULL;
	m_pTitle->pNext = pNewNode;
	m_pTitle = pNewNode;
	++m_size;
	return true;
}

//            
template
bool SingleList<_ty>::insert(int pos,_Ty elem)	// pos            1  
{	
	int i = 0;
	//        
	tagNode* pCursor = m_pHead;	
	while(pCursor != NULL && i < pos - 1)	 //          
	{
		pCursor = pCursor->pNext;
		++i;
	}
	if(i > pos-1 || pCursor == NULL)
	{
		return append(elem);
	}
	tagNode* pNewNode = (tagNode *)malloc(sizeof(tagNode));
	if(pNewNode == NULL)
	{
		return false;	//         
	}
	pNewNode->_elem = elem;
	pNewNode->pNext = pCursor->pNext;
	pCursor->pNext = pNewNode;
	++m_size;
	return true;
}

//         
template
bool SingleList<_ty>::deleteall()
{
	tagNode* pNode = m_pHead->pNext;
	tagNode* pTemp = NULL;
	while(pNode != NULL)
	{
		pTemp = pNode;
		pNode = pTemp->pNext;
		pTemp->_elem = 0;
		pTemp->pNext = NULL;
		free(pTemp);
		--m_size;
	}
	m_pHead->pNext = NULL;
	return true;
}

//         
template
bool SingleList<_ty>::deletepos(int pos,_Ty& res)
{	
	if(pos > m_size || m_pHead->pNext == NULL) //         
	{
		return false;
	}
	tagNode* pNode = m_pHead;
	int i = 0;
	while(pNode != NULL && i < pos -1)	//           
	{
		pNode = pNode->pNext;
		++i;
	}
	tagNode* pDelete = pNode->pNext;
	pNode->pNext = pDelete->pNext;
	pDelete->_elem = 0;
	pDelete->pNext = NULL;
	free(pDelete);
	--m_size;
	return true;
}

//        
template
_Ty  SingleList<_ty>::front()
{	
	return m_pHead->pNext->_elem;
}

//          
template
_Ty SingleList<_ty>::last()
{	
	return m_pTitle->_elem;
}

//         
template
bool SingleList<_ty>::empty()
{
	if(m_pHead->pNext == NULL || m_size == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//   
template
void SingleList<_ty>::traverse()
{
	tagNode* pTmp = m_pHead->pNext;
	if(pTmp == NULL || m_size == 0)
	{
		cout << "    "<_elem << "\t";
		pTmp = pTmp->pNext;
	}
	return;
}

int main(int _args,char* _argc)
{	
	
	SingleList* pList = new SingleList;

	pList->append(1);
	pList->append(2);
	pList->append(3);
	pList->traverse();
	cout << endl;
	cout << pList->front()<