データ構造とアルゴリズム分析学習ノート---第三章(チェーン)
19173 ワード
シングルリスト:
///////////////////////////////////////////////////////////////////////////////
//
// FileName : slist( ).h
// Version : 0.10
// Author : Z X
// Date : 2014-4-29 19:58:38
// Comment :
//
///////////////////////////////////////////////////////////////////////////////
#include
#include
using namespace std;
#define ASSERT assert
template
class CNode
{
public:
T m_data; //
CNode *pnext; //
CNode(): m_data(T()) , pnext(NULL){}
CNode(const T &initdata) : m_data(initdata) , pnext(NULL){}
CNode(const T &initdata, const CNode *p) : m_data(initdata) , pnext(p){}
};
template
class CList
{
//
public:
CList(){m_pNodeHead = NULL;}
CList(const T &initdata){AddHead(initdata);}
~CList();
//
public:
CList* InitList();
int IsEmpty(); //
T& GetTail(); // ， 。
T GetTail() const; // ， 。
T& GetHead(); //
T GetHead() const;
T& GetAt(int pos); // pos ， 1 list
T GetAt(int pos) const;
void SetAt(int pos, const T &data); // pos data
int GetCount() const; //
int Find(const T &data) const; // data ，
int FindPrevious(const T &data); // data
void Delete(const T &data); // data
int InsertBefore(const int pos, const T data); // pos data
int InsertAfter(const int pos, const T data); // pos data
int AddHead(const T data); //
int AddTail(const T data); //
void RemoveAt(const int pos); // pos
void RemoveHead(); //
void RemoveTail(); //
void RemoveAll(); //
void PrintList(); //
void Test(); //
//
protected:
CNode *m_pNodeHead;
};
// 。 ， List m_count,
// http://www.luocong.com/dsaanotes/index-Z-H-3.htm#node_sec_2.1
template
CList::~CList()
{
RemoveAll();
if(m_pNodeHead)
delete m_pNodeHead;
m_pNodeHead = NULL;
}
template
CList *CList::InitList()
{
CNode *pNewNode = new CNode();
if(NULL == pNewNode)
return 0;
pNewNode->m_data = 0;
pNewNode->pnext = NULL;
m_pNodeHead = pNewNode;
return this;
}
template
int CList::AddHead(const T data)
{
ASSERT(m_pNodeHead);
CNode *pNewNode = new CNode();
if(NULL == pNewNode)
return 0;
pNewNode->m_data = data;
pNewNode->pnext = m_pNodeHead->pnext;
m_pNodeHead->pnext = pNewNode;
return 1;
}
template
int CList::AddTail(const T data)
{
ASSERT(m_pNodeHead);
CNode*pTempNode = m_pNodeHead;
CNode *pNewNode = new CNode();
if(NULL == pNewNode)
return 0;
while(pTempNode->pnext != NULL)
{
pTempNode = pTempNode->pnext;
}
pNewNode->m_data = data;
pNewNode->pnext = pTempNode->pnext;
pTempNode->pnext = pNewNode;
return 1;
}
template
int CList::IsEmpty()
{
return m_pNodeHead == NULL;
}
template
T& CList::GetHead()
{
ASSERT(m_pNodeHead);
return m_pNodeHead->pnext->m_data; // ， 。
}
template
T CList::GetHead() const
{
ASSERT(m_pNodeHead);
return m_pNodeHead->pnext->m_data; //
}
template
T& CList::GetTail()
{
ASSERT(m_pNodeHead);
CNode*pTempNode = m_pNodeHead->pnext;
while(pTempNode->pnext != NULL)
pTempNode = pTempNode->pnext;
return pTempNode->m_data;
}
template
T CList::GetTail() const
{
ASSERT(m_pNodeHead);
CNode*pTempNode = m_pNodeHead->pnext;
while(pTempNode->pnext != NULL)
pTempNode = pTempNode->pnext;
return pTempNode->m_data;
}
template
T& CList::GetAt(int pos)
{
ASSERT(m_pNodeHead);
int i = 1;
CNode*pTempNode = m_pNodeHead->pnext;
while(i != pos)
{
pTempNode = pTempNode->pnext;
++i;
}
return pTempNode->m_data;
}
template
T CList::GetAt(int pos) const
{
ASSERT(m_pNodeHead);
int i = 1;
CNode*pTempNode = m_pNodeHead->pnext;
while(i != pos)
{
pTempNode = pTempNode->pnext;
++i;
}
return pTempNode->m_data
}
template
void CList::SetAt(int pos, const T &data)
{
int i = 1;
ASSERT(m_pNodeHead);
CNode*pTempNode = m_pNodeHead->pnext;
while(i != pos)
{
pTempNode = pTempNode->pnext;
++i;
}
pTempNode->m_data = data;
}
template
int CList::GetCount() const
{
ASSERT(m_pNodeHead);
int i = 0;
CNode*pTempNode = m_pNodeHead->pnext;
while(pTempNode != NULL)
{
pTempNode = pTempNode->pnext;
++i;
}
return i;
}
template
int CList::Find(const T &data) const
{
ASSERT(m_pNodeHead);
int i = 1;
CNode*pTempNode = m_pNodeHead->pnext;
while(pTempNode->m_data != data && pTempNode != NULL)
{
pTempNode = pTempNode->pnext;
++i;
}
return pTempNode != NULL ? i : -1;
}
template
int CList::FindPrevious(const T &data)
{
ASSERT(m_pNodeHead);
int i = 0;
CNode*pTempNode = m_pNodeHead->pnext;
CNode*pTempPrevious = m_pNodeHead;
while(pTempNode->m_data != data && pTempNode != NULL)
{
pTempPrevious = pTempNode;
pTempNode = pTempNode->pnext;
++i;
}
return pTempNode != NULL ? i : -1;
}
template
void CList::Delete(const T &data)
{
ASSERT(m_pNodeHead);
CNode*pTempNode = m_pNodeHead->pnext;
CNode*pTempPrevious = m_pNodeHead;
while(pTempNode && pTempNode->m_data != data)
{
pTempPrevious = pTempNode;
pTempNode = pTempNode->pnext;
}
if(pTempNode != NULL)
{
pTempPrevious->pnext = pTempNode->pnext;
delete pTempNode;
pTempNode = NULL;
}
}
template
int CList::InsertBefore(const int pos, const T data)
{
ASSERT(m_pNodeHead);
int i = 1;
CNode*pTempNode = m_pNodeHead->pnext;
CNode*pTempPrevious = m_pNodeHead;
while(pTempNode && i != pos)
{
pTempPrevious = pTempNode;
pTempNode = pTempNode->pnext;
++i;
}
CNode*pInsertNode = new CNode();
if(pInsertNode == NULL)
return -1;
pTempPrevious->pnext = pInsertNode;
pInsertNode->pnext = pTempNode;
pInsertNode->m_data = data;
return i;
}
template
int CList::InsertAfter(const int pos, const T data) // ， pos ，
{
ASSERT(m_pNodeHead);
int i = 0;
CNode*pTempNode = m_pNodeHead;
while(pTempNode->pnext != NULL && i != pos)
{
pTempNode = pTempNode->pnext;
++i;
}
CNode*pInsertNode = new CNode();
if(pInsertNode == NULL)
return -1;
pInsertNode->pnext = pTempNode->pnext;
pTempNode->pnext = pInsertNode;
pInsertNode->m_data = data;
return i+1;
}
template
void CList::RemoveAt(const int pos)
{
ASSERT(m_pNodeHead);
ASSERT(pos);
int i = 1;
CNode*pTempNode = m_pNodeHead->pnext;
CNode*pTempPrevious = m_pNodeHead;
while(pTempNode && i != pos)
{
pTempPrevious = pTempNode;
pTempNode = pTempNode->pnext;
++i;
}
if(pTempNode != NULL)
{
pTempPrevious->pnext = pTempNode->pnext;
delete pTempNode;
pTempNode = NULL;
}
}
template
void CList::RemoveHead()
{
ASSERT(m_pNodeHead);
CNode*pTempNode = m_pNodeHead->pnext;
if(pTempNode != NULL)
{
CNode*pTempNextNode = pTempNode->pnext;
delete pTempNode;
pTempNode = NULL;
m_pNodeHead->pnext = pTempNextNode;
}
}
template
void CList::RemoveTail()
{
ASSERT(m_pNodeHead);
CNode*pTempNode = m_pNodeHead->pnext;
CNode*pPrevisNode = pTempNode;
if(pTempNode == NULL)
return;
while(pTempNode->pnext != NULL)
{
pPrevisNode = pTempNode;
pTempNode = pTempNode->pnext;
}
delete pTempNode;
pTempNode = NULL;
pPrevisNode->pnext = NULL;
}
template
void CList::RemoveAll() //!!!!!!!!!!! ， list 。
{
CNode*pTempNode = m_pNodeHead;
CNode*pTempRemove = m_pNodeHead->pnext;
if(pTempRemove == NULL)
return;
while(pTempNode!= NULL)
{
pTempNode = pTempRemove->pnext;
delete pTempRemove;
pTempRemove = pTempNode;
}
m_pNodeHead->pnext = NULL;
}
template
void CList::PrintList()
{
int i,nCount;
nCount = GetCount();
// print out elements
for (i = 0; i < nCount; ++i)
cout << GetAt(i + 1);
cout <
void CList::Test()
{
InsertAfter(InsertAfter(AddHead(1), 2), 3);
PrintList();
InsertAfter(InsertAfter(GetCount(), 4), 5);
PrintList();
InsertAfter(GetCount(), 6);
PrintList();
AddTail(10);
PrintList();
InsertAfter(InsertBefore(GetCount(), 7), 8);
PrintList();
SetAt(GetCount(), 9);
PrintList();
RemoveHead();
PrintList();
RemoveTail();
PrintList();
cout << Find(3)< #include
#include
#define ASSERY assert
using namespace std;
template
class CDNode
{
public:
Y m_data; //
CDNode *pnext; //
CDNode *ppre;
CDNode(): m_data(Y()) , pnext(NULL), ppre(NULL){}
CDNode(const Y &initdata) : m_data(initdata) , pnext(NULL), ppre(NULL){}
CDNode(const Y &initdata, const CDNode *p) : m_data(initdata) , pnext(p),ppre(NULL){}
};
template
class CDList
{
//
public:
CDList(){m_pNodeHead = NULL;}
CDList(const Y &initdata){AddHead(initdata);}
~CDList();
//
public:
CDList* InitList();
int IsEmpty(); //
Y& GetTail(); // ， 。
Y GetTail() const; // ， 。
Y& GetHead(); //
Y GetHead() const;
Y& GetAt(int pos); // pos ， 1 list
Y GetAt(int pos) const;
void SetAt(int pos, const Y &data); // pos data
int GetCount() const; //
int Find(const Y &data) const; // data ，
int FindPrevious(const Y &data); // data
void Delete(const Y &data); // data
int InsertBefore(const int pos, const Y data); // pos data
int InsertAfter(const int pos, const Y data); // pos data
int AddHead(const Y data); //
int AddTail(const Y data); //
void RemoveAt(const int pos); // pos
void RemoveHead(); //
void RemoveTail(); //
void RemoveAll(); //
void PrintList(); //
void Test(); //
//
protected:
CDNode *m_pNodeHead;
};
template
CDList::~CDList()
{
RemoveAll();
if(m_pNodeHead)
delete m_pNodeHead;
m_pNodeHead = NULL;
}
template
CDList *CDList::InitList()
{
CDNode *pNewNode = new CDNode();
if(NULL == pNewNode)
return 0;
pNewNode->m_data = 0;
pNewNode->pnext = NULL;
pNewNode->ppre = NULL;
m_pNodeHead = pNewNode;
return this;
}
template
int CDList::AddHead(const Y data)
{
ASSERY(m_pNodeHead);
CDNode *pNewNode = new CDNode();
if(NULL == pNewNode)
return 0;
pNewNode->m_data = data;
pNewNode->pnext = m_pNodeHead->pnext;
pNewNode->ppre = m_pNodeHead;
m_pNodeHead->pnext = pNewNode;
return 1;
}
template
int CDList::AddTail(const Y data)
{
ASSERY(m_pNodeHead);
CDNode*pYempNode = m_pNodeHead;
CDNode *pNewNode = new CDNode();
if(NULL == pNewNode)
return 0;
while(pYempNode->pnext != NULL)
{
pYempNode = pYempNode->pnext;
}
pNewNode->m_data = data;
pNewNode->pnext = pYempNode->pnext;
pYempNode->pnext = pNewNode;
pNewNode->ppre = pYempNode;
return 1;
}
template
int CDList::IsEmpty()
{
return m_pNodeHead->next == NULL;
}
template
Y& CDList::GetHead()
{
ASSERY(m_pNodeHead);
return m_pNodeHead->pnext->m_data; // ， 。
}
template
Y CDList::GetHead() const
{
ASSERY(m_pNodeHead);
return m_pNodeHead->pnext->m_data; //
}
template
Y& CDList::GetTail()
{
ASSERY(m_pNodeHead);
CDNode*pYempNode = m_pNodeHead->pnext;
while(pYempNode->pnext != NULL)
pYempNode = pYempNode->pnext;
return pYempNode->m_data;
}
template
Y CDList::GetTail() const
{
ASSERY(m_pNodeHead);
CDNode*pYempNode = m_pNodeHead->pnext;
while(pYempNode->pnext != NULL)
pYempNode = pYempNode->pnext;
return pYempNode->m_data;
}
template
Y& CDList::GetAt(int pos)
{
ASSERY(m_pNodeHead);
int i = 1;
CDNode*pYempNode = m_pNodeHead->pnext;
while(i != pos)
{
pYempNode = pYempNode->pnext;
++i;
}
return pYempNode->m_data;
}
template
Y CDList::GetAt(int pos) const
{
ASSERY(m_pNodeHead);
int i = 1;
CDNode*pYempNode = m_pNodeHead->pnext;
while(i != pos)
{
pYempNode = pYempNode->pnext;
++i;
}
return pYempNode->m_data
}
template
void CDList::SetAt(int pos, const Y &data)
{
int i = 1;
ASSERY(m_pNodeHead);
CDNode*pYempNode = m_pNodeHead->pnext;
while(i != pos)
{
pYempNode = pYempNode->pnext;
++i;
}
pYempNode->m_data = data;
}
template
int CDList::GetCount() const
{
ASSERY(m_pNodeHead);
int i = 0;
CDNode*pYempNode = m_pNodeHead->pnext;
while(pYempNode != NULL)
{
pYempNode = pYempNode->pnext;
++i;
}
return i;
}
template
int CDList::Find(const Y &data) const
{
ASSERY(m_pNodeHead);
int i = 1;
CDNode*pYempNode = m_pNodeHead->pnext;
while(pYempNode->m_data != data && pYempNode != NULL)
{
pYempNode = pYempNode->pnext;
++i;
}
return pYempNode != NULL ? i : -1;
}
template
int CDList::FindPrevious(const Y &data)
{
ASSERY(m_pNodeHead);
int i = 0;
CDNode*pYempNode = m_pNodeHead->pnext;
while(pYempNode->m_data != data && pYempNode != NULL)
{
pYempNode = pYempNode->pnext;
++i;
}
return pYempNode != NULL ? i : -1;
}
template
void CDList::Delete(const Y &data)
{
ASSERY(m_pNodeHead);
CDNode*pYempNode = m_pNodeHead->pnext;
while(pYempNode && pYempNode->m_data != data)
{
pYempNode = pYempNode->pnext;
}
if(pYempNode != NULL)
{
pYempNode->ppre->pnext = pYempNode->pnext;
pYempNode->pnext->ppre = pYempNode->ppre;
delete pYempNode;
pYempNode = NULL;
}
}
template
int CDList::InsertBefore(const int pos, const Y data)
{
ASSERY(m_pNodeHead);
int i = 1;
CDNode*pYempNode = m_pNodeHead->pnext;
while(pYempNode && i != pos)
{
pYempNode = pYempNode->pnext;
++i;
}
CDNode*pInsertNode = new CDNode();
if(pInsertNode == NULL)
return -1;
pYempNode->ppre->pnext = pInsertNode;
pInsertNode->ppre = pYempNode->ppre;
pInsertNode->pnext = pYempNode;
pInsertNode->m_data = data;
return i;
}
template
int CDList::InsertAfter(const int pos, const Y data) // ， pos ，
{
ASSERY(m_pNodeHead);
int i = 0;
CDNode*pYempNode = m_pNodeHead;
while(pYempNode->pnext != NULL && i != pos)
{
pYempNode = pYempNode->pnext;
++i;
}
CDNode*pInsertNode = new CDNode();
if(pInsertNode == NULL)
return -1;
pInsertNode->pnext = pYempNode->pnext;
if(pYempNode->pnext!=NULL)
pYempNode->pnext->ppre = pInsertNode;
pYempNode->pnext = pInsertNode;
pInsertNode->ppre = pYempNode;
pInsertNode->m_data = data;
return i+1;
}
template
void CDList::RemoveAt(const int pos)
{
ASSERY(m_pNodeHead);
ASSERY(pos);
int i = 1;
CDNode*pYempNode = m_pNodeHead->pnext;
while(pYempNode && i != pos)
{
pYempNode = pYempNode->pnext;
++i;
}
if(pYempNode != NULL)
{
pYempNode->ppre->pnext = pYempNode->pnext;
if(pYempNode->pnext != NULL)
pYempNode->pnext->ppre = pYempNode->ppre;
delete pYempNode;
pYempNode = NULL;
}
}
template
void CDList::RemoveHead()
{
ASSERY(m_pNodeHead);
CDNode*pYempNode = m_pNodeHead->pnext;
if(pYempNode != NULL)
{
m_pNodeHead->pnext = pYempNode->pnext;
if(pYempNode->pnext != NULL)
pYempNode->pnext->ppre = m_pNodeHead;
delete pYempNode;
pYempNode = NULL;
}
}
template
void CDList::RemoveTail()
{
ASSERY(m_pNodeHead);
CDNode*pYempNode = m_pNodeHead->pnext;
if(pYempNode == NULL)
return;
while(pYempNode->pnext != NULL)
{
pYempNode = pYempNode->pnext;
}
pYempNode->ppre->pnext = NULL;
delete pYempNode;
pYempNode = NULL;
}
template
void CDList::RemoveAll() //!!!!!!!!!!! ， list 。
{
CDNode*pYempNode = m_pNodeHead;
CDNode*pYempRemove = m_pNodeHead->pnext;
if(pYempRemove == NULL)
return;
while(pYempNode!= NULL)
{
pYempNode = pYempRemove->pnext;
delete pYempRemove;
pYempRemove = pYempNode;
}
m_pNodeHead->pnext = NULL;
}
template
void CDList::PrintList()
{
int i,nCount;
nCount = GetCount();
// print out elements
for (i = 0; i < nCount; ++i)
cout << GetAt(i + 1);
cout <
void CDList::Test()
{
InsertAfter(InsertAfter(AddHead(1), 2), 3);
PrintList();
InsertAfter(InsertAfter(GetCount(), 4), 5);
PrintList();
InsertAfter(GetCount(), 6);
PrintList();
AddTail(10);
PrintList();
InsertAfter(InsertBefore(GetCount(), 7), 8);
PrintList();
SetAt(GetCount(), 9);
PrintList();
RemoveHead();
PrintList();
RemoveTail();
PrintList();
cout << Find(3)<