list.h

数据结构的一个试验

/*************************线性的链表表示****************************************

时间：2004-10-21
功能：运用了模板技术，封装了线性链表的常规操作包括添加删除元素，查找元素，链表排序
作者：赵宏涛
*********************************************************************************/
#pragma once
#include "afx.h"
template<class T>
class CMlist :
	public CObject
{
public:
	//typedef T _PtrClass;
	
	CMlist(void)
	{
	
		m_Head=new LNode;
		m_Tail=m_Head;
		m_Head->next=NULL;
		m_iCount=0;
		//m_Head=m_Tail=NULL;
	}
	
	~CMlist(void){this->RemoveAll();delete m_Head;}
private:
	struct LNode
	{
		T data;
		struct LNode*next;
	};

	LNode *m_Head;
	LNode *m_Tail;

	LNode* NewNode(T data)
	{
		LNode *p;
		p=new LNode;
		p->data=data;
		p->next=NULL;
		return p;
	}
	int m_iCount;

public:
	//在表头插入元素
	//template<class T>
	CMlist<T> &operator =(const CMlist<T>& mlist)
	{
		this->RemoveAll();
		LNode *p=mlist.m_Head->next;
		while(p!=NULL)
		{
			this->InsertTail(p->data);
			p=p->next;
		}
		return *this;
	}
	void InsertHead(T data)
	{
		LNode*p=NewNode(data);
		if(IsEmpt())
		{
			m_Head->next=p;
			m_Tail=p;
		}
		else
		{

			p->next=m_Head->next;
			m_Head->next=p;
		}
		m_iCount++;
	}
	//在表尾插入元素
	void InsertTail(T data)
	{
		if(IsEmpt())
		{
			this->InsertHead(data);
		}
		else
		{
			LNode*p=NewNode(data);
			m_Tail->next=p;
			m_Tail=p;
			m_iCount++;
		}
	}
	//得到表头元素
	T GetHead(void)
	{
		if(!IsEmpt())
			return m_Head->next->data;
	}
//得到表尾的元素
	T GetTail(void)
	{
		if(!IsEmpt())
			return m_Tail->data;
		else return T();
	}
	//得到指定位置的元素
	T GetAt(int iIndex)
	{
		if(iIndex>=0&&iIndex<m_iCount)
		{
			int i=0;
			LNode * p=m_Head;
			while(i!=iIndex)
			{
				p=p->next;
				i++;

			}
			return p->next->data;
		}
		else 
		{
			return T();
		}
		
	}
//在制定的位置插入元素
	void InsertAt(int iIndex, T data)
	{
		if(iIndex>=0&&iIndex<=m_iCount)
		{
			int i=0;
			LNode * p=m_Head;
			while(i!=iIndex)
			{
				p=p->next;
				i++;

			}
			LNode *temp=NewNode(data);
			temp->next=p->next;
			p->next=temp;
			m_iCount++;
		}
	}
//返回链表的元素数
	int GetCount(void)
	{
		return m_iCount;
	}
//判断链表是否为空为空返回TRUE否则返回FALSE.
	BOOL IsEmpt(void)
	{
		if(m_iCount==0)
			return TRUE;
		else
			return FALSE;
	}

	// 删除表头元素
	void RemoveHead(void)
	{
		if(!IsEmpt())
		{
			LNode *p;
			p=m_Head->next;
			m_Head->next=p->next;
			delete p;
			m_iCount--;

		}
	}
//删除所有数据
	void RemoveAll(void)
	{
		while(!IsEmpt())
		{
			RemoveHead();
		}
		
	}

	// 删除指定的元素
	void RemoveAt(int iIndex)
	{
		if(!IsEmpt())
		{
			int i=0;
			LNode * p=m_Head;
			if(iIndex!=m_iCount)
			{
				while(i!=iIndex)
				{
					p=p->next;
					i++;
				}
				LNode *temp=p->next;
				p->next=temp->next;
				//delete temp;
				m_iCount--;
			}
			else RemovTail();

		}
	}

	// //逆转链表
	void Reversal(void)
	{
		LNode*p=m_Head;


		if(!IsEmpt()&&m_iCount>1)
		{
			p=p->next;
			while(p!=NULL&&p->next!=NULL)
			{

				LNode *temp=m_Head->next;
				m_Head->next=p->next;
				LNode *temp2,*temp3;
				temp2=temp3=p->next;
				temp3=temp3->next;
				temp2->next=temp;
				p->next=temp3;
			}

		}

	}

	// 排序函数,排序结果是根据关键字由大到小排列的
	void Sort(void)
	{

		int out,iner;
		out=m_iCount;
		while(out--!=0)
		{
			iner=m_iCount;
			LNode*prev=m_Head;
			LNode*p=m_Head->next;
			while(--iner!=0)
			{
				if(p->data<p->next->data)
				{
					LNode*temp1,*temp2;
					temp1=p->next;
					if(temp1->next!=NULL)
					{
						temp2=temp1->next;
						prev->next=temp1;
						temp1->next=p;
						p->next=temp2;
					}
					else
					{
						prev->next=temp1;
						temp1->next=p;
						p->next=NULL;
						m_Tail=p;
					}
				}
				else 
				{
					p=p->next;
				}
				prev=prev->next;
			}


		}


	}
	

	void RemovTail(void)
	{
		LNode*p;
		p=m_Head;
		while(p->next!=m_Tail)
		{
			p=p->next;
		}
		LNode*temp=m_Tail;
		m_Tail=p;
		delete temp;
		m_iCount--;
	}
};