铁血石头 - C++博客

链表

出自：http://hi.baidu.com/caolei7299/blog/
//***********************************************************
//
// Author: _Stone_7299
// data: 2011-8-26
// From: 笃志http://www.rpgchina.net/read-htm-tid-28012.html
// AfterWritingAre: 笃志大侠的List 敲了一天
//***********************************************************/

#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;
CNode< T > *next;

public:
CNode(): data( T() ), next(NULL){};

CNode(const T &initdata):data(initdata), next(NULL){};

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: //常用的对外接口

/* 关于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 >::GetCount() const
{
return m_nCount;
}

//-----------------------------------
//返回值说明: 若返回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 少了一种情况
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;

/*注意: 和InsertBefore不同, 多加一次
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 >::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;
}
}

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

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

if(pos == 1)
{
m_pNodeHead = m_pNodeHead->next;
delete pTmpNode;
pTmpNode = NULL;

-- m_nCount;
return;
}

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

pDeskNode = pTmpNode->next;
pTmpNode->next = pDeskNode->next;
delete pDeskNode;
pDeskNode = NULL;

-- 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(GetCount());
}

//-----------------------------------
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 = 0;

m_pNodeHead = pTmpNode;
}
}

//-----------------------------------
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 >::GetTail()
{
ASSERT( m_nCount != 0);

int i;
int nCount;
CNode< T > *pTmpNode;
nCount = m_nCount;
pTmpNode = m_pNodeHead;
for(int 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;
nCount = m_nCount;
pTmpNode = m_pNodeHead;
for(int i = 0;i < nCount; ++i)
{
pTmpNode = pTmpNode->next;
}

return pTmpNode->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((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 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

//*****************************************************************
// Author: _Stone_7299
// data: 2011-08-26
// From: 笃志http://www.rpgchina.net/read-htm-tid-28012.html
//
//*****************************************************************/

//测试SinList
#include "stdafx.h"
#include <iostream>
#include"SinList.h"
using namespace std;

int main()
{
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();

return 0;
}

posted @ 2011-08-31 11:36 曹磊阅读(1454) | 评论 (0) | 编辑收藏

常用链接

留言簿

随笔档案

搜索

最新评论

2011年8月31日