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()<