list.h

自己在以前学数据结构时用C++模板写的一些常用数据,都测试过

/////////////////////////// 
//    // 
//   链表数据结构  List.h // 
//    // 
////////////////////////// 

template<class Type> 
class List; 
template<class Type> //定义链表结点类
class ListNode 
{ 
public: 
	friend class List<Type>; 
private: 
	Type data; 
	ListNode<Type> * next; 
}; 
//////////////////////////定义链表类//////////
template<class Type> 
class List 
{ 
public: 
	List(); 
	~List(); 
	void InsertEnd(Type); //向链表尾部插入元素 
	bool Insert(Type,int); //向链表任意位置插入元素 
	void DelNode(int pos);  //删除元素 
	int Find(Type T);   //查找元素 
	void MakeEmpty();   //销毁链表 
	void SelectSort();	//选择排序
	bool Print();  //打印链表 
	bool IsEmpty(){return length==0;}
	int GetLen();  //得到链表长度 
private: 
	ListNode<Type> *first,*last; //定义链表的头和尾
	int length;						//记录链表的长度
}; 

template<class Type> 
void InitList(Type &tmp); 

template<class Type> 
void List_exit(List<Type> &L,Type tmp); 

void Initation(); 

template<class Type> 
void List_insertend(List<Type> &L,Type tmp); 


template<class Type> 
int List<Type>::GetLen() 
{ 
	return length; 
} 

template<class Type> 
void List<Type>::MakeEmpty() 
{ 
	ListNode<Type> *p1,*p2; 
	p1=first->next; 
	first->next=NULL; 
	while(p1!=NULL) 
	{ 
		p2=p1; 
		p1=p1->next; 
		delete p2; 
	} 
	length=0;  
} 

template<class Type> 
void List<Type>::InsertEnd(Type t) 
{ 
	ListNode<Type> *p; 
	p=new ListNode<Type>; 
	p->data=t; 
	p->next=NULL; 
	last->next=p; 
	last=p; 
	length++; 
} 

template<class Type> 
bool List<Type>::Insert(Type t,int pos) 
{ 
	ListNode<Type> *p; 
	p=first; 	
	int k=1; 
	while(p!=NULL&&k<pos) 
	{ 
		p=p->next; 
		k++; 
	} 
	if(p==NULL&&k!=pos) 
		return false; 
	else 
	{ 
		ListNode<Type> *tp; 
		tp=new ListNode<Type>; 
		tp->data=t; 
		tp->next=p->next; 
		p->next=tp; 
		length++;  
		return true; 
	} 
} 

template<class Type> 
void List<Type>::DelNode(int pos) 
{ 
	int k=1; 
	ListNode<Type> *p,*t; 
	p=first; 
	while(p->next!=NULL&&k!=pos) 
	{ 
		p=p->next; 
		k++; 
	} 
	t=p->next; 
	cout<<"你已经将数据项 "<<t->data<<"删除"<<endl; 
	p->next=p->next->next; 
	length--; 
	delete t; 
} 

template<class Type> 
bool List<Type>::Print() 
{ 
	ListNode<Type> *p=first->next; 
	if(length==0) 
		return false; 
	else 
	{ 
		cout<<"链表中有"<<length<<"项数据: "<<endl; 
		while(p) 
		{ 
			cout<<p->data<<" "; 
			p=p->next; 
		} 
	} 
	cout<<endl; 
	return true; 
} 

template<class Type> 
int List<Type>::Find(Type T) 
{ 
	ListNode<Type> *p=first->next; 
	int i=1; 
	while(p&&p->data!=T) 
	{ 
		p=p->next; 
		i++; 
	} 
	if(p) 
		return i; 
	else 
	return 0; 
} 


template<class Type> 
List<Type>::~List()
{ 
	delete first; 
	cout<<"欢迎再次使用 (!^!) "<<endl; 
} 

template<class Type> 
List<Type>::List() 
{ 
    ListNode<Type> *node=new ListNode<Type>; 
	node->next=NULL; 
	first=last=node; 
	length=0; 
} 
template<class Type>
void List<Type>::SelectSort()
{
	ListNode<Type> *sortedfirst=NULL,*sortedlast=NULL;
	ListNode<Type> *p=NULL,*q=NULL,*min=NULL,*minprior=NULL;
	do
	{
		min=first;
		p=first->next;
		q=first;
		while(p!=NULL)
		{
			if(p->data<min->data)
			{
				minprior=q;
				min=p;
			}
			q=p;
			p=p->next;
		}
		if(min==first)
			first=first->next;
		else
			minprior->next=min->next;
		min->next=NULL;
		if(sortedfirst==NULL)
			sortedfirst=min;
		else
			sortedlast->next=min;
		sortedlast=min;
	}while(first!=NULL);
	first=sortedfirst;
}