数据结构之单链表

SingleList单链表学习代码
//*****************************************************************
//
//      SingleList单链表学习代码
//    FreedomKnight_Duzhi 转载并添加注释
//
//*****************************************************************/
// 本文件为SingleList全文件
// 附注: 遍历时间复杂度为O(N),查询结点时间复杂度为O(N/2)

#ifndef __SINGLE_LIST_H__
#define __SINGLE_LIST_H__

#include <assert.h>          // 用以支持断言
#include <crtdbg.h>          // 用以支持内存泄露检测

// DEBUG模式下,定义获得错误信息,文件名,行数
#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

// 若是DEBUG模式,则断言有效,否则使其无效
#ifdef _DEBUG
      #ifndef ASSERT
      #define ASSERT assert
      #endif
#else
      #ifndef ASSERT
      #define ASSERT
      #endif
#endif

// 单链表每一个结点结构
template < typename T >
class CNode
{
public:
      T data;
      // 因为是单链表，结点中除了数据,就仅有一个next指针了
      CNode< T > *next;
      // 构造函数初始化表
      CNode() : data( T() ), next(NULL){};
      // 重载构造函数
      CNode(const T &initdata) : data(initdata), next(NULL){};
      // 重载构造函数2
      CNode(const T &initdata, CNode< T > *p) : data(initdata), next(p)){};
};

// 整个单链表结构
template < typename T >
class CSList
{
protected:
      // 因为是单链表,仅仅需要知道链表长度和首指针就可以了
      int m_nCount;
      CNode< T > *m_pNodeHead;
public:
      CSList();
      CSList(const T &initdata);
      ~CSList();
public:          // 常用方法对外接口
      /* 注意该部分的const用法,修饰参数,修饰成员函数
      修饰成员函数时,此函数中不允许调用非const函数,且不许修改成员变量
      所以,这部分函数中都自定义了一套临时变量nCount而没有使用m_nCount
      */
      /* 关于T与T&返回值的说明.该部分的所有获取函数都实现了两次,
      目的是,返回值为T的,允许修改,即读写操作均允许.
      返回值为T&的,是其内存地址所写的常量值,不允许进行写操作,进行了保护
      const的目的在于进行函数重载,若不加的话,编译器认为是相同的函数
      */

      // 判断单链表是否为空
      bool      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&          GetHead();
      // 获取头结点数据
      T          GetHead() const;
      // 获取尾结点数据
      T&          GetTail();
      // 获取尾结点数据
      T          GetTail() const;
      // 获取指定位置结点
      T&          GetAt(const int pos);
      // 获取指定位置结点
      T          GetAt(const int pos) const;
      // 更改指定位置结点数据
      void      SetAt(const int pos, T data);
      // 查询指定数据位置
      int          Find(const T data) const;
};

/* 由于模版类不支持.h和.cpp分离,故实现也写在头文件中
除非编译器支持export关键字,而实际上基本没有编译器支持\(-_-)/ */
/* 代码短小常用的函数使用内联比较迅速 */
//-----------------------------------

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

//-----------------------------------

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

//-----------------------------------

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

//-----------------------------------

template< typename T >
inline bool CSList< T >::IsEmpty() const
{
      if( m_nCount == 0 )
      {
          return true;
      }
      else
      {
          return false;
      }
}

//-----------------------------------

template< typename T >
inline int CSList< T >::AddHead(const T data)
{
      CNode< T > *pNewNode;
      pNewNode = new CNode< T >;

      if( pNewNode == NULL )
      {
          return 0;
      }

      pNewNode->data = data;
      pNewNode->next = m_pNodeHead;

      m_pNodeHead = pNewNode;
      ++m_nCount;

      return 1;
}

//-----------------------------------

template< typename T >
inline int CSList< T >::AddTail(const T data)
{
      if( InsertAfter(GetCount(), data) )
      {
          return 1;
      }
      else
      {
          return 0;
      }
}

//-----------------------------------

// 返回值说明:若返回0,则代表插入失败.若返回数字大于0,则记录插入结点的当前位置
template< typename T >
inline int CSList< T >::InsertBefore(const int pos, const T data)
{
      /* 将结点插入指定位置之前的操作要分为三种可能
      1:      空链表插入,头指针需要添加,新结点的指针无效
      2:    插入链表头部,头指针需要改变,新结点的指针赋值
      3:    插入链表中间,头指针不改变,改变位置前结点指针,自身指针赋值
      */
      int i;
      int nRetPos;                  // 结点实际所在位,0代表插入失败
      CNode< T > *pTmpNode;          // 目标位置前结点
      CNode< T > *pNewNode;          // 想插入的目标结点

      // 若创建结点失败
      pNewNode = new CNode< T >;
      if( pNewNode == NULL )
      {
          return 0;            
      }

      pNewNode->data = data;

      // 若表为空,则相当于将数据结点设置为首结点
      if(m_pNodeHead == NULL)
      {
          pNewNode->next = NULL;
          m_pNodeHead = pNewNode;
          nRetPos = 1;
          ++m_nCount;
          return nRetPos;
      }
    
      // 断言:传的参数必须在合理范围内
      ASSERT((1 <= pos) && (pos <= m_nCount));

      // 若插入的是链表头位置
      if(pos == 1)
      {
          pNewNode->next = m_pNodeHead;
          m_pNodeHead = pNewNode;
          nRetPos = 1;
          ++m_nCount;
          return nRetPos;
      }

      // 一般情况的处理
      pTmpNode = m_pNodeHead;
      for(i = 1; i < pos - 1; ++i)
      {    
          pTmpNode = pTmpNode->next;
      }
      // 通过循环获得的指定位置原来的结点的前一个结点pTmpNode
      pNewNode->next = pTmpNode->next;
      pTmpNode->next = pNewNode;

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

//-----------------------------------

template< typename T >
inline int CSList< T >::InsertAfter(const int pos, const T data)
{
      /* 比起InsertBefore来说, InsertAfter少了一种特殊情况处理
      1: 链表为空时依旧需要处理
      2: 插入点不可能为最前,若为最后的话,也可按照一般情况,所以仅
         需两种处理方式.
      */
      int i;
      int nRetPos;
      CNode< T > *pTmpNode;
      CNode< T > *pNewNode;

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

      pNewNode->data = data;

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

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

      pTmpNode = m_pNodeHead;
      /* 注意! 和InsertInsertBefore不同,此处循环多了一次
      InsertInsertBefore获得的是目标位置原结点的前一个结点
      InsertInsertAfter获得的是目标位置原结点
      */
      for (i = 1; i < pos; i++)
      {
          pTmpNode = pTmpNode->next;
      }
      // 通过循环获得的指定位置原结点pTmpNode
      pNewNode->next = pTmpNode->next;
      pTmpNode->next = pNewNode;
      ++m_nCount;
      nRetPos = pos + 1;      /* 注意: 此处加1 */
      return nRetPos;
}

//-----------------------------------

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

//-----------------------------------

template < typename T >
inline void CSList< T >::RemoveAt(const int pos)
{
      // 判断合法性
      ASSERT(pos >= 1 && pos <= m_nCount);

      int i;
      CNode< T > *pTmpNode;          // 目标结点的前一个结点
      CNode< T > *pDestNode;          // 目标位置结点    
      pTmpNode = m_pNodeHead;

      // 如果删除的是头结点
      if (pos == 1)
      {
          m_pNodeHead = m_pNodeHead->next;
          delete pTmpNode;
          --m_nCount;
          return ;
      }

      // 一般情况
      for (i = 1; i < pos - 1; ++i)
      {
          pTmpNode = pTmpNode->next;
      }
      pDestNode = pTmpNode->next;
      pTmpNode->next = pDestNode->next;
      delete pDestNode;
      --m_nCount;
}

//-----------------------------------

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

//-----------------------------------

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

//-----------------------------------

template < typename T >
inline void CSList< 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 T& CSList< T >::GetTail()
{
      ASSERT(m_nCount != 0);

      int i;
      int nCount;
      CNode < T > *pTmpNode;

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

//-----------------------------------

template < typename T >
inline T CSList< T >::GetTail() const
{
      ASSERT(m_nCount != 0);

      int i;
      int nCount;
      CNode < T > *pTmpNode;

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

//-----------------------------------

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

//-----------------------------------

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

//-----------------------------------

template < typename T >
inline T& CSList< 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 T CSList< T >::GetAt(const int pos) const
{
      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 void CSList<T>::SetAt(const int pos, T data)
{
      ASSERT(1 <= pos && pos <= m_nCount);

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

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

//-----------------------------------

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

      pTmpNode = m_pNodeHead;
      nCount = m_nCount;

      // 遍历所有的结点
      for (i = 0; i < nCount; ++i)
      {
          if (data = pTmpNode->data)
          {
              return i + 1;      // 结点号和索引号差1
          }
          pTmpNode = pTmpNode->next;
      }
      // 若未找到则返回空
      return 0;
}

//-----------------------------------

#endif





//*****************************************************************
//
//      SingleList单链表学习代码

//    FreedomKnight_Duzhi 转载并添加注释
//
//*****************************************************************/
// 本文件用以测试SinList


#include <iostream>
#include "SinList.h"
using namespace std;

int main(void)
{
      int i;
      int nCount;
      CSList< int > sList;

#ifdef _DEBUG
      /* 如果是DEBUG模式下,若main函数运行完毕,还有内存没有释放,则会将其信息反馈
      到编译器下方的调试窗口有提示(注:但是这句不进行错误位置的提示,所以若需要错误定位
      依旧需要依靠头文件中的__FILE__那一行) */
      _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

      sList.InsertAfter(sList.InsertAfter(sList.AddHead(1), 2), 3);      /* 1,2,3 */
      sList.InsertAfter(sList.InsertAfter(sList.GetCount(), 4), 5);      /* 1,2,3,4,5 */
      sList.InsertAfter(sList.GetCount(), 6);                              /* 1,2,3,4,5,6 */
      sList.AddTail(10);                                                  /* 1,2,3,4,5,6,10 */
      sList.InsertAfter(sList.InsertBefore(sList.GetCount(), 7), 8);    /* 1,2,3,4,5,6,7,8,10 */
      sList.SetAt(sList.GetCount(), 9);                                  /* 1,2,3,4,5,6,7,8,9    */
      sList.RemoveHead();                                                  /* 2,3,4,5,6,7,8,9    */
      sList.RemoveTail();                                                  /* 2,3,4,5,6,7,8    */

      nCount = sList.GetCount();
      for (i = 0; i < nCount; ++i)
      {
          cout << sList.GetAt(i + 1) << endl;
      }
      // 等待输入才退出
      getchar();
}
数据结构之单链表

Frankie

月记202411

月记202410

月记202409

月记202408

月记202407

从亚马逊丛林旅游归来所感

[计划]总结2024上半年,展望2024下半年

月记202406

选择环境的重要性

月记202405
