夜深了,发一个双向指针链表,注释不多,有兴趣朋友可以看看.

Question

一些宏 #ifndef NULL
#define NULL 0
#endif //NULL#ifndef TRUE
#define TRUE 1
#endif //TRUE#ifndef FALSE 
#define FALSE 0
#endif //FALSEtypedef  int BOOL;
typedef  void * HID;---------------------------头文件开始----------------------------#ifndef __PTRDEQUE_H__
#define __PTRDEQUE_H__class CfPtrDeque  
{
protected:
////
struct tagNode  
{
void * pData;
tagNode *pstPrev;  
tagNode *pstNext;
};
public:
CfPtrDeque();
virtual ~CfPtrDeque();protected:
//申请
void * AllocNode();
//释放
void   FreeNode(void * pNode);
protected:
//剪切
void  CutNode(tagNode * pNode );
public:
//添加到头
HID AddHead(void * pnewElement);
//添加到尾
HID AddTail(void * pnewElement);
//在...前插入
HID InsertAtBefore(HID pNode,void * pnewElement);
//在...后插入
HID InsertAtAfter(HID pNode,void * pnewElement);
//查找索引
HID FindIndex(int nIndex);
//头
HID GetHeadPosition();
//尾
HID GetTailPosition();
//取值
void * GetAt(HID pNode);
//移除,返回移除的值
void * RemoveAt(HID pNode);
//自头向尾枚举
void * GetNext(HID& pNextNode); 
//自尾向头枚举
void * GetPrev(HID& pPrevNode); 
//移除所有
void RemoveAll();
public:
//长度
int GetCount();

protected:
//头
tagNode* m_pHead ;
//尾
tagNode* m_pTail ;

protected:
//计数器
int m_nCount ; // num 1,2,3........
};
class CfPtrStack
{
public:
CfPtrStack(int nMode = modeExtrusion);
~CfPtrStack();
public:
//压入
BOOL Push(void * pnewElement);
//弹出
BOOL Pop(void *& poldElement);
public:
//移除所有
void RemoveAll();
//长度
int GetCount();
public:
enum
{
//先进先出
modeOrdinal = 0,
//先进后出
modeExtrusion = 1
};
protected:
//队列
CfPtrDeque m_ptrDeque;
//模式
int m_nMode;
public:
//设置模式
void SetMode(int nMode);
};
#endif //__PTRDEQUE_H__---------------------------头文件结束-------------------------------------------------------源文件开始----------------------------CfPtrDeque::CfPtrDeque()
{
m_pHead = NULL;
m_pTail = NULL;
m_nCount = 0; 
}CfPtrDeque::~CfPtrDeque()
{
RemoveAll();
}
void* CfPtrDeque::AllocNode()
{
tagNode* pNode =new tagNode;
if( NULL != pNode )
{
memset(pNode,0,sizeof(tagNode));
}
return pNode;
}
void CfPtrDeque::FreeNode(void * pVoid)
{
tagNode*  pNode = (tagNode*)pVoid;
if( pNode )
{
delete []pNode;
}
}void  CfPtrDeque::CutNode(tagNode * pNode )
{
//A <--->B<--->C
//分离节点B,使A和C以相连 A<--->C
if(pNode->pstNext)
pNode->pstNext->pstPrev = pNode->pstPrev;
if(pNode->pstPrev)
pNode->pstPrev->pstNext = pNode->pstNext;

//是头节点
if( pNode == m_pHead )
{
m_pHead = pNode->pstNext;
if( m_pHead )
m_pHead->pstPrev = NULL;
}
//是尾节点
if( pNode == m_pTail )
{
m_pTail = pNode->pstPrev;
if( m_pTail )
m_pTail->pstNext = NULL;
}
//清除分离后的节点
FreeNode(pNode);
//记数器减1
m_nCount--;

}
HID CfPtrDeque::AddHead(void * pnewElement)
{
tagNode* pNewNode = NULL;

if(  m_pHead )
{
if( pNewNode = (tagNode*)AllocNode() )
{
pNewNode->pData = pnewElement;

//添加到开头
pNewNode->pstNext = m_pHead;
m_pHead->pstPrev = pNewNode; 
m_pHead = pNewNode;

m_nCount++;
}
}
else
{
pNewNode = (tagNode*)AddTail(pnewElement);
}


return pNewNode;
}
HID CfPtrDeque::AddTail(void * pnewElement)
{
tagNode* pNewNode = NULL;

if( pNewNode = (tagNode*)AllocNode() )
{
pNewNode->pData = pnewElement;

if( NULL == m_pHead )
{
m_pHead = pNewNode;
m_pTail = pNewNode;
}
else
{
//添加到末尾
m_pTail->pstNext = pNewNode;
pNewNode->pstPrev = m_pTail; 
m_pTail = pNewNode;
}

m_nCount++;

}

return pNewNode;
}
HID CfPtrDeque::InsertAtBefore(HID pNode,void * pnewElement)
{
tagNode* pNewNode = NULL; if( pNode )
{
tagNode* pCurNode=(tagNode*)pNode; if( pNewNode = (tagNode*)AllocNode() )
{
pNewNode->pData = pnewElement;

//A<--->C
//插入B到A和C之间 A <--->B<--->C
pNewNode->pstPrev = pCurNode->pstPrev;
pNewNode->pstNext = pCurNode;
pCurNode->pstPrev = pNewNode;

if( pNewNode->pstPrev ) //不是头
{
pNewNode->pstPrev->pstNext = pNewNode;
} if( m_pHead == pCurNode )
{
m_pHead = pNewNode;
}

m_nCount++;
}
} return  pNewNode;
}HID CfPtrDeque::InsertAtAfter(HID pNode,void * pnewElement)
{
tagNode* pNewNode = NULL;

if( pNode  )
{
tagNode* pCurNode=(tagNode*)pNode; if( pNewNode = (tagNode*)AllocNode() )
{
pNewNode->pData = pnewElement;
//插入
pNewNode->pstNext = pCurNode->pstNext;
pNewNode->pstPrev = pCurNode;
pCurNode->pstNext = pNewNode;

if( pNewNode->pstNext ) //不是尾
{
pNewNode->pstNext->pstPrev = pNewNode;
}
if( m_pTail == pCurNode)
{
m_pTail = pNewNode;
}

m_nCount++;
}
}

return  pNewNode;
}HID CfPtrDeque::FindIndex(int nIndex)
{
tagNode* pFind = NULL;

if( nIndex >=0 && nIndex < m_nCount   ) 
{
if( nIndex < (m_nCount/2) )
{
//头-->当前节点
pFind = m_pHead;

while(nIndex--)
{
pFind = pFind->pstNext;
}
}
else
{
//尾-->当前节点
pFind = m_pTail;
//找另一部分
nIndex = m_nCount-nIndex-1;

while(nIndex--)
{
pFind = pFind->pstPrev;
}
}
}
return pFind;
}
//头
HID CfPtrDeque::GetHeadPosition()
{
return m_pHead;
}
//尾
HID CfPtrDeque::GetTailPosition()
{
return m_pTail;
}void * CfPtrDeque::GetAt(HID pNode)
{
void * pData = NULL;

if( pNode  )
pData = ((tagNode*)pNode)->pData; return pData;
}//
void * CfPtrDeque::GetNext(HID& pNextNode)
{
void * pData = NULL; if( pNextNode )
{
//
pData = ((tagNode*)pNextNode)->pData;
//
pNextNode = ((tagNode*)pNextNode)->pstNext; }
return pData;
}//
void * CfPtrDeque::GetPrev(HID& pPrevNode)
{
void * pData = NULL; if( pPrevNode )
{
//
pData = ((tagNode*)pPrevNode)->pData;
//
pPrevNode = ((tagNode*)pPrevNode)->pstPrev;

}
return pData;
}void * CfPtrDeque::RemoveAt(HID pNode)
{
void * pData = NULL; if( pNode )
{
pData = ((tagNode*)pNode)->pData; CutNode((tagNode*)pNode);
} return pData;
}
void CfPtrDeque::RemoveAll()
{
tagNode* pCfr = m_pHead; while(pCfr)
{
m_pHead = pCfr->pstNext;
FreeNode( pCfr);
pCfr=m_pHead;
} m_pHead = NULL;
m_pTail = NULL;
m_nCount = 0;
}
int CfPtrDeque::GetCount()
{
return m_nCount;
}
///////////////////////////////////////////////////////////////////////////
CfPtrStack::CfPtrStack(int nMode /*= modeExtrusion*/)
{
SetMode(nMode);
}
CfPtrStack::~CfPtrStack()
{

}
BOOL CfPtrStack::Push(void * pnewElement)
{
return (NULL != m_ptrDeque.AddTail(pnewElement));
}
BOOL CfPtrStack::Pop(void *& poldElement)
{
BOOL bResult = FALSE;

HID pCfr = NULL;

switch(m_nMode)
{
case modeOrdinal: 
{
pCfr = m_ptrDeque.GetHeadPosition();
}
break;
case modeExtrusion:
{
pCfr = m_ptrDeque.GetTailPosition();
}
break;
default:
{
pCfr = m_ptrDeque.GetTailPosition();
}
break;
}

if( bResult = ( NULL != pCfr) )
poldElement = m_ptrDeque.RemoveAt(pCfr); return bResult;
}
//移除所有
void CfPtrStack::RemoveAll()
{
m_ptrDeque.RemoveAll();
}
//长度
int CfPtrStack::GetCount()
{
return m_ptrDeque.GetCount();
}void CfPtrStack::SetMode(int nMode)
{
m_nMode = nMode;
}---------------------------源文件结束----------------------------

Answer 1

这里数据都只能以void指针添加吗？

Answer 2

不错，这些东西，上学的时候学数据结构的时候都写过
现在直接用STL和MFC里的了

Answer 3

顶一下，不过还是看CList原码的好，效率比较高的。虽然CArray效率很低，不如vector,CAtlList效率还是相当高的。