描述1.txt

1、顺序表 Seqlist.h Test.cpp 2、单链表 ListNode.h SingleList.h test.cpp 3、双向链表 NodeList.h

public:
	void MakeEmpty();   //make the list empty
	int Length();       //get the length of the list
	ListNode<Type> *Find(int n=0);  //find the nth data
	ListNode<Type> * FindData(Type item);   //find the data which is equal to item
	bool Insert(Type item,int n=0);     //insert item in the nth data
	Type Remove(int n=0);   //delete the nth data
	Type Get(int n=0);      //get the nth data
	void Print();           //print the list

private:
	ListNode<Type> *head;
};

template<typename Type> void DoublyList<Type>::MakeEmpty(){
	ListNode<Type> *pmove=head->m_pnext,*pdel;
	while(pmove!=head){
		pdel=pmove;
		pmove=pdel->m_pnext;
		delete pdel;
	} 
	head->m_pnext=head;
	head->m_pprior=head;
}

template<typename Type> int DoublyList<Type>::Length(){
	ListNode<Type> *pprior=head->m_pprior,*pnext=head->m_pnext;
	int count=0;
	while(1){
		if(pprior->m_pnext==pnext){
			break;
		}
		if(pprior==pnext&&pprior!=head){
			count++;
			break;
		}
		count+=2;
		pprior=pprior->m_pprior;
		pnext=pnext->m_pnext;
	}
	return count;
}

template<typename Type> ListNode<Type>* DoublyList<Type>::Find(int n = 0){
	if(n<0){
		cout<<"The n is out of boundary"<<endl;
		return NULL;
	}
	ListNode<Type> *pmove=head->m_pnext;
	for(int i=0;i<n;i++){
		pmove=pmove->m_pnext;
		if(pmove==head){
			cout<<"The n is out of boundary"<<endl;
			return NULL;
		}
	}
	return pmove;
}

template<typename Type> bool DoublyList<Type>::Insert(Type item,int n){
	if(n<0){
		cout<<"The n is out of boundary"<<endl;
		return 0;
	}
	ListNode<Type> *newnode=new ListNode<Type>(item),*pmove=head;
	if(newnode==NULL){
		cout<<"Application Erorr!"<<endl;
		exit(1);
	}
	for(int i=0;i<n;i++){   //find the position for insert
		pmove=pmove->m_pnext;
		if(pmove==head){
			cout<<"The n is out of boundary"<<endl;
			return 0;
		}
	}

    //insert the data
	newnode->m_pnext=pmove->m_pnext;
	newnode->m_pprior=pmove;
	pmove->m_pnext=newnode;
	newnode->m_pnext->m_pprior=newnode;
	return 1;
}

template<typename Type> Type DoublyList<Type>::Remove(int n = 0){
	if(n<0){
		cout<<"The n is out of boundary"<<endl;
		exit(1);
	}
	ListNode<Type> *pmove=head,*pdel;
	for(int i=0;i<n;i++){   //find the position for delete
		pmove=pmove->m_pnext;
		if(pmove==head){
			cout<<"The n is out of boundary"<<endl;
			exit(1);
		}
	}

    //delete the data
	pdel=pmove;
	pmove->m_pprior->m_pnext=pdel->m_pnext;
	pmove->m_pnext->m_pprior=pdel->m_pprior;
	Type temp=pdel->m_data;
	delete pdel;
	return temp;
}

template<typename Type> Type DoublyList<Type>::Get(int n = 0){
	if(n<0){
		cout<<"The n is out of boundary"<<endl;
		exit(1);
	}
	ListNode<Type> *pmove=head;
	for(int i=0;i<n;i++){
		pmove=pmove->m_pnext;
		if(pmove==head){
			cout<<"The n is out of boundary"<<endl;
			exit(1);
		}
	}
	return pmove->m_data;
}

template<typename Type> void DoublyList<Type>::Print(){
	ListNode<Type> *pmove=head->m_pnext;
	cout<<"head";
	while(pmove!=head){
		cout<<"--->"<<pmove->m_data;
		pmove=pmove->m_pnext;
	}
	cout<<"--->over"<<endl<<endl<<endl;

}

template<typename Type> ListNode<Type>* DoublyList<Type>::FindData(Type item){
	ListNode<Type> *pprior=head->m_pprior,*pnext=head->m_pnext;
	while(pprior->m_pnext!=pnext && pprior!=pnext){ //find the data in the two direction
		if(pprior->m_data==item){
			return pprior;
		}
		if(pnext->m_data==item){
			return pnext;
		}
		pprior=pprior->m_pprior;
		pnext=pnext->m_pnext;
	}
	cout<<"can't find the element"<<endl;
	return NULL;
}

Test.cpp

#include <iostream>
#include "DoublyList.h"

using namespace std;

int main()
{
	DoublyList<int> list;
	for(int i=0;i<20;i++){
		list.Insert(i*3,i);
	}
	cout<<"the Length of the list is "<<list.Length()<<endl;
	list.Print();
	for(int i=0;i<5;i++){
		list.Insert(3,i*3);
	}
	cout<<"the Length of the list is "<<list.Length()<<endl;
	list.Print();

	list.Remove(5);
	cout<<"the Length of the list is "<<list.Length()<<endl;
	list.Print();

	cout<<list.FindData(54)->GetData()<<endl;

	cout<<"The third element is "<<list.Get(3)<<endl;

	list.MakeEmpty();
	cout<<"the Length of the list is "<<list.Length()<<endl;
	list.Print();


	return 0;
}

4、	循环链表

ListNode.h

template<typename Type> class CircularList;

template<typename Type> class ListNode{
private:
	friend class CircularList<Type>;
	ListNode():m_pnext(NULL){}
	ListNode(const Type item,ListNode<Type> *next=NULL):m_data(item),m_pnext(next){}
	~ListNode(){
		m_pnext=NULL;
	}
	
private:
	Type m_data;
	ListNode *m_pnext;
};

CircularList.h

#include "ListNode.h"

template<typename Type> class CircularList{
public:
	CircularList():head(new ListNode<Type>()){
		head->m_pnext=head;	
	}
	~CircularList(){
		MakeEmpty();
		delete head;
	}
public:
	void MakeEmpty();	//clear the list
	int Length();		//get the length
	ListNode<Type> *Find(Type value,int n);	//find the nth data which is equal to value
	ListNode<Type> *Find(int n);			//find the nth data
	bool Insert(Type item,int n=0);			//insert the data into the nth data of the list
	Type Remove(int n=0);					//delete the nth data
	bool RemoveAll(Type item);				//delete all the datas which are equal to value
	Type Get(int n);	//get the nth data
	void Print();		//print the list

private:
	ListNode<Type> *head;

};

template<typename Type> void CircularList<Type>::MakeEmpty(){
	ListNode<Type> *pdel,*pmove=head;
	while(pmove->m_pnext!=head){
		pdel=pmove->m_pnext;
		pmove->m_pnext=pdel->m_pnext;
		delete pdel;
	}
}

template<typename Type> int CircularList<Type>::Length(){
	ListNode<Type> *pmove=head;
	int count=0;
	while(pmove->m_pnext!=head){
		pmove=pmove->m_pnext;
		count++;
	}
	return count;
}

template<typename Type> ListNode<Type>* CircularList<Type>::Find(int n){
	if(n<0){
		cout<<"The n is out of boundary"<<endl;
		return NULL;
	}
	ListNode<Type> *pmove=head->m_pnext;
	for(int i=0;i<n&&pmove!=head;i++){
		pmove=pmove->m_pnext;
	}
	if(pmove==head){
		cout<<"The n is out of boundary"<<endl;
		return NULL;
	}
	return pmove;
}

template<typename Type> ListNode<Type>* CircularList<Type>::Find(Type value,int n){
	if(n<1){
		cout<<"The n is illegal"<<endl;
		return NULL;
	}
	ListNode<Type> *pmove=head;
	int count=0;
	while(count!=n){
		pmove=pmove->m_pnext;
		if(pmove->m_data==value){
			count++;
		}
		if(pmove==head){
			cout<<"can't find the element"<<endl;
			return NULL;
		}
	}
	return pmove;
}

template<typename Type> bool CircularList<Type>::Insert(Type item, int n){
	if(n<0){
		cout<<"The n is out of boundary"<<endl;
		return 0;
	}
	ListNode<Type> *pmove=head;
	ListNode<Type> *pnode=new ListNode<Type>(item);
	if(pnode==NULL){
		cout<<"Application error!"<<endl;
		exit(1);
	}
	for(int i=0;i<n;i++){
		pmove=pmove->m_pnext;
		if(pmove==head){
			cout<<"The n is out of boundary"<<endl;
			return 0;
		}
	}

	pnode->m_pnext=pmove->m_pnext;
	pmove->m_pnext=pnode;
	return 1;
}

template<typename Type> bool CircularList<Type>::RemoveAll(Type item){
	ListNode<Type> *pmove=head;
	ListNode<Type> *pdel=head->m_pnext;
	while(pdel!=head){
		if(pdel->m_data==item){
			pmove->m_pnext=pdel->m_pnext;
			delete pdel;
			pdel=pmove->m_pnext;
			continue;
		}
		pmove=pmove->m_pnext;
		pdel=pdel->m_pnext;
	}
	return 1;
}

template<typename Type> Type CircularList<Type>::Remove(int n){
	if(n<0){
		cout<<"can't find the element"<<endl;
		exit(1);
	}
	ListNode<Type> *pmove=head,*pdel;
	for(int i=0;i<n&&pmove->m_pnext!=head;i++){
		pmove=pmove->m_pnext;
	}
	if(pmove->m_pnext==head){
		cout<<"can't find the element"<<endl;
		exit(1);
	}
	pdel=pmove->m_pnext;
	pmove->m_pnext=pdel->m_pnext;
	Type temp=pdel->m_data;
	delete pdel;
	return temp;
}

template<typename Type> Type CircularList<Type>::Get(int n){
	if(n<0){
		cout<<"The n is out of boundary"<<endl;
		exit(1);
	}
	ListNode<Type> *pmove=head->m_pnext;
	for(int i=0;i<n;i++){
		pmove=pmove->m_pnext;
		if(pmove==head){
			cout<<"The n is out of boundary"<<endl;
			exit(1);
		}
	}
	return pmove->m_data;
}

template<typename Type> void CircularList<Type>::Print(){
	ListNode<Type> *pmove=head->m_pnext;
	cout<<"head";
	while(pmove!=head){
		cout<<"--->"<<pmove->m_data;
		pmove=pmove->m_pnext;
	}
	cout<<"--->over"<<endl<<endl<<endl;
}

Test.cpp

#include <iostream>
#include "CircularList.h"

using namespace std;

int main()
{
	CircularList<int> list;
	for(int i=0;i<20;i++){
		list.Insert(i*3,i);
	}
	cout<<"the Length of the list is "<<list.Length()<<endl;
	list.Print();
	for(int i=0;i<5;i++){
		list.Insert(3,i*3);
	}
	cout<<"the Length of the list is "<<list.Length()<<endl;
	list.Print();

	list.Remove(5);
	cout<<"the Length of the list is "<<list.Length()<<endl;
	list.Print();

	list.RemoveAll(3);
	cout<<"the Length of the list is "<<list.Length()<<endl;
	list.Print();

	cout<<"The third element is "<<list.Get(3)<<endl;

	list.MakeEmpty();
	cout<<"the Length of the list is "<<list.Length()<<endl;
	list.Print();


	return 0;
}