测试List的编写

// 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_)