[砖头]我也来个链表
以前学数据结构时候,忘记在哪儿弄的的一份单向链表代码,如下,当时可真是加了不少注释//*****************************************************************
//
// SingleList单链表学习代码(2004.5.12日)
//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单链表学习代码(2004.5.12日)
//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();
}
其实实现的原理到是很基础的,不过这个格式值得学习,写引擎的专用方式.
页:
[1]