数据结构之双链表

DoubleList双链表学习代码

//*****************************************************************
//
//    DoubleList双链表学习代码
//    FreedomKnight_Duzhi 转载并添加注释
//
//*****************************************************************/
#ifndef __DOUBLE_LIST_H__
#define __DOUBLE_LIST_H__

#include <assert.h>
#include <crtdbg.h>

#ifdef _DEBUG
#define DEBUG_NEW new(_NORMAL_BLOCK, THIS_FILE, __LINE__)
#endif

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

#ifdef _DEBUG
#ifndef ASSERT
#define ASSERT assert
#endif
#else
#ifndef ASSERT
#define ASSERT
#endif
#endif

template < typename T >
class CNode
{
public:
T     data;
CNode< T >   *prior;
CNode< T >   *next;
CNode() : data(T()), prior(NULL), next(NULL) {}
CNode(const T& initdata) : data(initdata), prior(NULL), next(NULL) {}
};


template < typename T >
class CDList
{
protected:
int     m_nCount;
CNode< T >   *m_pNodeHead;
CNode< T >   *m_pNodeTail;
public:
CDList();
CDList(const T &initdata);
~CDList();
public:
int     IsEmpty() const;
int     GetCount() const;
int     InsertBefore(const int pos, const T data);
int     InsertAfter(const int pos, const T data);
int     AddHead(const T data);
int     AddTail(const T data);
void    RemoveAt(const int pos);
void    RemoveHead();
void    RemoveTail();
void    RemoveAll();
T&     GetTail();
T     GetTail() const;
T&     GetHead();
T     GetHead() const;
T&     GetAt(const int pos);
T     GetAt(const int pos) const;
void    SetAt(const int pos,const T data);
int     Find(const T data) const;
T&     GetPrev(int &pos);
T&     GetNext(int &pos);
};

//==============================================================

template < typename T >
inline CDList< T >::CDList()
: m_nCount(0),
m_pNodeHead(NULL),
m_pNodeTail(NULL)
{
}

//==============================================================

template < typename T >
inline CDList< T >::CDList(const T &initdata)
: m_nCount(0)
m_pNodeHead(NULL),
m_pNodeTail(NULL)
{
AddHead(initdata);
}

//==============================================================

template < typename T >
inline CDList< T >::~CDList()
{
   RemoveAll();
}

//==============================================================

template < typename T >
inline T& CDList< T >::GetNext(int &pos)
{
ASSERT(m_nCount != 0);
ASSERT(pos >=1 && pos <= m_nCount);

int i;
CNode< T > *pTmpNode = m_pNodeHead;

for (i = 1; i < pos; ++i)
{
   pTmpNode = pTmpNode->next;
}

++pos;
return pTmpNode->data;
}

//==============================================================

template < typename T >
inline T& CDList< T >::GetPrev(int &pos)
{
ASSERT(m_nCount != 0);
ASSERT(pos >= 1 && pos <= m_nCount);

int i;
CNode< T > *pTmpNode;

pTmpNode = m_pNodeHead;

for (i = 1; i < pos; ++i)
{
   pTmpNode = pTmpNode->next;
}

--pos;
return pTmpNode->data;
}

//==============================================================

template < typename T >
inline int CDList< T >::InsertBefore(const int pos, const T data)
{
int i;
CNode< T > *pTmpNode;
CNode< T > *pNewNode;
int nRetPos;

pNewNode = new CNode< T >;
if (pNewNode == NULL)
{
   return 0;
}

pNewNode->data = data;

if (m_pNodeHead == NULL)
{
   pNewNode->next = NULL;
   pNewNode->prior = NULL;
   m_pNodeHead = pNewNode;
   m_pNodeTail = pNewNode;
   ++m_nCount;
   nRetPos = 1;
   return nRetPos;
}

ASSERT(pos >= 1 && pos <= m_nCount);

if (pos == 1)
{
   pNewNode->next = m_pNodeHead;
   pNewNode->prior = NULL;
   m_pNodeHead->prior = pNewNode;
   m_pNodeHead = pNewNode;
   nRetPos = 1;
   ++m_nCount;
   return nRetPos;
}

pTmpNode = m_pNodeHead;
for (i = 1; i < pos; ++i)
{
   pTmpNode = pTmpNode->next;
}
pNewNode->next = pTmpNode;
pNewNode->prior = pTmpNode->prior;

pTmpNode->prior->next = pNewNode;
pTmpNode->prior = pNewNode;

if (NULL == pNewNode->next)
{
   m_pNodeTail = pNewNode;
}

nRetPos = pos;
++m_nCount;
return nRetPos;
}

//==============================================================

template < typename T >
inline CDList< T >::InsertAfter(const int pos, const T data)
{
int i;
int nRetPos;
CNode< T > *pTmpNode;
CNode< T > *pNewNode;

pNewNode = new CNode< T >;
if (NULL == pNewNode)
{
   return 0;
}

if (m_pNodeHead == NULL)
{
   pNewNode->next = NULL;
   pNewNode->prior = NULL;
   m_pNodeHead = pNewNode;
   m_pNodeTail = pNewNode;
   nRetPos = 1;
   ++m_nCount;
   return nRetPos;
}

ASSERT(pos >= 1 && pos <= m_nCount);

pTmpNode = m_pNodeHead;
if (i = 1; i < pos; ++i)
{
   pTmpNode = pTmpNode->next;
}
// 该部分进行了大段修正
pNewNode->prior = pTmpNode;
pNewNode->next = pTmpNode->next;

if (pTmpNode->next == NULL)
{
   m_pNodeTail = pNewNode;
}
else
{
   pTmpNode->next->prior = pNewNode;
}
pTmpNode->next = pNewNode;

++m_nCount;
nRetPos = pos + 1;
return nRetPos;
}
//==============================================================

template < typename T >
inline T& CDList< T >::GetAt(const int pos)
{
ASSERT(pos >= 1 && pos <= m_nCount);

int i;
CNode< T > *pTmpNode;

pTmpNode = m_pNodeHead;
for (i = 1; i < pos; ++i)
{
   pTmpNode = pTmpNode->next;
}

return pTmpNode->data;
}

//==============================================================

template < typename T >
inline int CDList< T >::AddHead(const T data)
{
return InsertBefore(1, data);
}

//==============================================================

template < typename T >
inline int CDList< T >::AddTail(const T data)
{
return InsertAfter(GetCount(), data);
}

//==============================================================

template< typename T >
inline int CDList< T >::IsEmpty() const
{
if (0 == m_nCount)
{
   return 1;
}
else
{
   return 0;
}
}

//==============================================================

template< typename T >
inline int CDList< T >::GetCount() const
{
return m_nCount;
}

//==============================================================

template< typename T >
inline T& CDList< T >::GetTail()
{
ASSERT(0 != m_nCount);
return m_pNodeTail->data;
}

//==============================================================

template< typename T >
inline T CDList< T >::GetTail() const
{
ASSERT(0 != m_nCount);
return m_pNodeTail->data;
}

//==============================================================

template< typename T >
inline T& CDList< T >::GetHead()
{
ASSERT(0 != m_nCount);
return m_pNodeHead->data;
}

//==============================================================

template< typename T >
inline T CDList< T >::GetHead() const
{
ASSERT(0 != m_nCount);
return m_pNodeHead->data;
}

//==============================================================

template< typename T >
inline void CDList< T >::RemoveAt(const int pos)
{
ASSERT(pos >= 1 && pos <= m_nCount);

int i;
CNode< T > *pTmpNode = m_pNodeHead;

if (1 == pos)
{
   m_pNodeHead = pTmpNode->next;
   delete pTmpNode;
   --m_nCount;
   if (0 == m_nCount)
   {
    m_pNodeTail = NULL;
   }
   return ;
}

for (i = 1; i < pos; ++i)
{
   pTmpNode = pTmpNode->next;
}
pTmpNode->prior->next = pTmpNode->next;
delete pTmpNode;
--m_nCount;
}

//==============================================================

template < typename T >
inline void CDList< T >::RemoveHead()
{
ASSERT(0 != m_nCount);
RemoveAt(1);
}

//==============================================================

template< typename T >
inline void CDList< T >::RemoveTail()
{
ASSERT(0 != m_nCount);
RemoveAt(m_nCount);
}
//==============================================================

template< typename T >
inline void CDList< T >::RemoveAll()
{
int i;
int nCount;
CNode< T > *pTmpNode;

nCount = m_nCount;
for (i = 0; i < nCount; ++i)
{
   pTmpNode = m_pNodeHead->next;
   delete m_pNodeHead;
   m_pNodeHead = pTmpNode;
}
m_nCount = 0;
}

//==============================================================

template < typename T >
inline void CDList< T >::SetAt(const int pos, const T data)
{
ASSERT(pos >= 1 && pos <= m_nCount);
  
int i;
CNode< T >   *pTmpNode;

pTmpNode = m_pNodeHead;

for (i = 1; i < pos; ++i)
{
   pTmpNode = pTmpNode->next;
}

pTmpNode->data = data;
}

//==============================================================

template< typename T >
inline int CDList< T >::Find(const T data) const
{
int i;
int nCount;
CNode< T > *pTmpNode;

pTmpNode = m_pNodeHead;
nCount = m_nCount;

// 注意:此处是从i=0开始的循环
for (i = 0; i < nCount; ++i)
{
   if(data == pTmpNode->data)
   {
    return i + 1;
   }
   pTmpNode = pTmpNode->next;
}

return 0;
}

//==============================================================
#endif

//*****************************************************************
//
//    DoubleList双链表学习代码
//    FreedomKnight_Duzhi 转载并添加注释
//
//*****************************************************************/
#include <iostream>
#include "DoubleList.h"

int main()
{
int i;
int nCount;
CDList< int > dList;

#ifdef _DEBUG
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

dList.AddTail(1);    /* 1 */
//dList.AddTail(3);    /* 1,3 */
//dList.InsertBefore(2, 2); /* 1,2,3 */
//dList.AddHead(4);    /* 4,1,2,3 */
//dList.RemoveTail();    /* 4,1,2 */
//dList.InsertAfter(2, 5); /* 4,1,5,2 */

nCount = dList.GetCount();
for (i = 1; i <= nCount;)
{
   std::cout << dList.GetNext(i) << std::endl;
}
getchar();
}