// LinkedList.h: interface for the LinkedList class.
//
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_LINKEDLIST_H__4B3074E8_FF2A_4FDE_9798_A2DEC76350C0__INCLUDED_)
#define AFX_LINKEDLIST_H__4B3074E8_FF2A_4FDE_9798_A2DEC76350C0__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include "windows.h"
#define LINK_SUCCESS 1
#define LINK_ERROR -1
#define INDEX_IS_ERROR -2
#define BUFFER_IS_EMPTY -3
template <class T_ELE>
class LinkedList
{
public:
LinkedList();
~LinkedList();
public:
BOOL IsEmpty(); //判断链表是否为空
void Clear(); //清空链表
DWORD GetElement(IN DWORD dwIndex,OUT T_ELE& Element); //根据索引获取元素
DWORD GetElementIndex(IN T_ELE& Element); //根据元素获取链表中的索引
DWORD Insert(IN T_ELE Element); //新增元素
DWORD Insert(IN DWORD dwIndex,IN T_ELE Element);
DWORD Delete(IN DWORD dwIndex);
DWORD GetSize();
private:
typedef struct _NODE{
T_ELE Data;
_NODE* pNext;
}NODE,*PNODE;
PNODE GetIndexCurrentNode(DWORD dwIndex); //获取索引为dwIndex的指针
PNODE GetIndexPreviousNode(DWORD dwIndex); //获取索引为dwIndex的前一个节点的指针
PNODE GetIndexNextNode(DWORD dwIndex); //获取索引为dwIndex的后一个节点的指针
private:
PNODE m_pList; //链表头指针，指向第一个节点
DWORD m_dwLength; //元素的数量
};
//无参构造函数， 初始化成员
template<class T_ELE> LinkedList<T_ELE>::LinkedList():m_pList(NULL),m_dwLength(0)
{
}
//析构函数 清空元素
template<class T_ELE> LinkedList<T_ELE>::~LinkedList()
{
Clear();
}
//判断俩表是否为空
template<class T_ELE> BOOL LinkedList<T_ELE>::IsEmpty()
{
if(m_dwLength == 0)
{
return true;
}else
{
return false;
}
}
//清空链表
template<class T_ELE> void LinkedList<T_ELE>::Clear()
{
//1 判断链表是否为空
if(IsEmpty())
{
return;
}
//2 循环删除链表中的节点
PNODE pNode = m_pList;
while(pNode!=NULL)
{
PNODE pOldNode = pNode;
pNode = pNode->pNext;
delete pOldNode;
pOldNode->pNext = NULL;
m_pList = pNode;
}
//3 删除最后一个节点 并将链表长度 设置为0
delete m_pList;
m_pList = NULL;
m_dwLength = 0;
}
//根据索引获取元素
template<class T_ELE> DWORD LinkedList<T_ELE>::GetElement(IN DWORD dwIndex,OUT T_ELE& Element)
{
//1 判断索引是否有效
if(dwIndex<0 || dwIndex>=m_dwLength)
{
return INDEX_IS_ERROR;
}
//2 取得索引指向的节点
PNODE pNode = GetIndexCurrentNode(dwIndex);
//3 将索引指向节点的值复制到OUT参数
Element = pNode->Data;
return LINK_SUCCESS;
}
//根据元素内容获取索引
template<class T_ELE> DWORD LinkedList<T_ELE>::GetElementIndex(IN T_ELE& Element)
{
//1 判断链表是否为空
if(m_dwLength ==0)
{
return LINK_ERROR;
}
//2 循环遍历链表，找到与Element相同的元素
PNODE pNode = m_pList;
DWORD i = 0;
while(pNode!=NULL)
{
T_ELE CurrentData= pNode->Data;
if(CurrentData==Element )
{
return i;
}
i++;
pNode = pNode->pNext;
}
if(pNode==NULL)
{
printf("没有找到这个元素\n");
return INDEX_IS_ERROR;
}
return LINK_SUCCESS;
}
//在链表尾部添加节点
template<class T_ELE> DWORD LinkedList<T_ELE>::Insert(IN T_ELE Element)
{
PNODE pNode = (PNODE)malloc(sizeof(NODE));
pNode->Data = Element;
pNode->pNext = NULL;
//1 判断链表是否为空
if(m_dwLength == 0)
{
m_pList = pNode;
m_dwLength=1;
return LINK_SUCCESS;
}
//2 如果链表中已经有元素
PNODE pLastNode = GetIndexCurrentNode(m_dwLength-1);
pLastNode->pNext = pNode;
m_dwLength++;
return LINK_SUCCESS;
}
//将节点新增到指定的索引位置
template<class T_ELE> DWORD LinkedList<T_ELE>::Insert(IN DWORD dwIndex,IN T_ELE Element)
{
//1 判断链表是否为空
if(m_dwLength==0)
{
return LINK_ERROR;
}
//2 判断索引值是否有效
if(dwIndex<0 || dwIndex>=m_dwLength)
{
return INDEX_IS_ERROR;
}
//3 如果索引为0
if(dwIndex == 0)
{
PNODE pZeroNode = (PNODE)malloc(sizeof(NODE));
pZeroNode->Data = Element;
pZeroNode->pNext = NULL;
pZeroNode->pNext = m_pList;
m_pList = pZeroNode;
m_dwLength++;
return LINK_SUCCESS;
}
//4 如果索引为链表尾
PNODE pNewNode = (PNODE)malloc(sizeof(NODE));
pNewNode->Data = Element;
pNewNode->pNext = NULL;
if(dwIndex ==(m_dwLength-1))
{
PNODE pLastNode = GetIndexCurrentNode(m_dwLength-1);
pLastNode->pNext = pNewNode;
m_dwLength++;
return LINK_SUCCESS;
}
//5 如果索引为链表中
if(dwIndex>0 && dwIndex<(m_dwLength-1))
{
PNODE pSetNode = GetIndexPreviousNode(dwIndex);
pNewNode->pNext = pSetNode->pNext;
pSetNode->pNext = pNewNode;
m_dwLength++;
return LINK_SUCCESS;
}
return LINK_SUCCESS;
}
//根据索引删除节点
template<class T_ELE> DWORD LinkedList<T_ELE>::Delete(IN DWORD dwIndex)
{
//1 判断链表是否为空
if(m_dwLength == 0)
{
return LINK_ERROR;
}
//2 判断索引值是否有效
if(dwIndex<0 && dwIndex>=dwIndex-1)
{
return LINK_ERROR;
}
//3 如果链表只有头节点，且要删除头节点
if(m_dwLength==1&&dwIndex==0)
{
delete m_pList;
m_pList = NULL;
m_dwLength = 0;
return LINK_SUCCESS;
}
//4 如果链表要删除头节点
if(m_dwLength>1 && dwIndex == 0)
{
PNODE pSecList = m_pList;
m_pList = m_pList->pNext;
delete pSecList;
pSecList->pNext = NULL;
m_dwLength--;
return LINK_SUCCESS;
}
//5 其他情况
if(m_dwLength>1 && dwIndex>0)
{
PNODE pPreList = GetIndexPreviousNode(dwIndex);
PNODE pCurList = GetIndexCurrentNode(dwIndex);
pPreList->pNext = pCurList->pNext;
delete pCurList;
pCurList->pNext=NULL;
m_dwLength--;
return LINK_SUCCESS;
}
return LINK_SUCCESS;
}
//节点数量
template<class T_ELE> DWORD LinkedList<T_ELE>::GetSize()
{
return m_dwLength;
}
//获取dwIndex前面节点的地址
template<class T_ELE>
LinkedList<T_ELE>::PNODE LinkedList<T_ELE>::GetIndexPreviousNode(DWORD dwIndex)
{
//一个循环
PNODE PreNode = m_pList;
for(DWORD i=0;i<dwIndex-1;i++)
{
PreNode=PreNode->pNext;
}
return PreNode;
}
//获取dwIndex节点的地址
template<class T_ELE>
LinkedList<T_ELE>::PNODE LinkedList<T_ELE>::GetIndexCurrentNode(DWORD dwIndex)
{
//一个循环
PNODE CurNode = m_pList;
for(DWORD i=0;i<dwIndex;i++)
{
CurNode=CurNode->pNext;
}
return CurNode;
}
//获取dwIndex后面节点的地址
template<class T_ELE>
LinkedList<T_ELE>::PNODE LinkedList<T_ELE>::GetIndexNextNode(DWORD dwIndex)
{
//一个循环
//一个循环
PNODE NextNode = m_pList;
for(int i=0;i<=dwIndex;i++)
{
NextNode=NextNode->pNext;
}
return NextNode;
}
#endif // !defined(AFX_LINKEDLIST_H__4B3074E8_FF2A_4FDE_9798_A2DEC76350C0__INCLUDED_)