描述1.txt

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

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

 
1、顺序表

Seqlist.h

const int DefaultSize=100;

template <typename Type> class SeqList{
public:
	SeqList(int sz=DefaultSize)
		:m_nmaxsize(sz),m_ncurrentsize(-1){
		if(sz>0){
			m_elements=new Type[m_nmaxsize];
		}
	}
	~SeqList(){
		delete[] m_elements;
	}
	int Length() const{					//get the length
		return m_ncurrentsize+1;
	}
	int Find(Type x) const;				//find the position of x
	int IsElement(Type x) const;		//is it in the list
	int Insert(Type x,int i);			//insert data
	int Remove(Type x);					//delete data
	int IsEmpty(){
		return m_ncurrentsize==-1;
	}
	int IsFull(){
		return m_ncurrentsize==m_nmaxsize-1;
	}
	Type Get(int i){					//get the ith data
		return i<0||i>m_ncurrentsize?(cout<<"can't find the element"<<endl,0):m_elements[i];
	}
	void Print();

private:
	Type *m_elements;
	const int m_nmaxsize;
	int m_ncurrentsize;
};

template <typename Type> int SeqList<Type>::Find(Type x) const{
	for(int i=0;i<m_ncurrentsize;i++)
		if(m_elements[i]==x)
			return i;
	cout<<"can't find the element you want to find"<<endl;
	return -1;
}

template <typename Type> int SeqList<Type>::IsElement(Type x) const{
	if(Find(x)==-1)
		return 0;
	return 1;
}

template <typename Type> int SeqList<Type>::Insert(Type x, int i){
	if(i<0||i>m_ncurrentsize+1||m_ncurrentsize==m_nmaxsize-1){
		cout<<"the operate is illegal"<<endl;
		return 0;
	}
	m_ncurrentsize++;
	for(int j=m_ncurrentsize;j>i;j--){
		m_elements[j]=m_elements[j-1];
	}
	m_elements[i]=x;
	return 1;
}

template <typename Type> int SeqList<Type>::Remove(Type x){
	int size=m_ncurrentsize;
	for(int i=0;i<m_ncurrentsize;){
		if(m_elements[i]==x){
			for(int j=i;j<m_ncurrentsize;j++){
				m_elements[j]=m_elements[j+1];
			}
			m_ncurrentsize--;
			continue;
		}
		i++;
	}
	if(size==m_ncurrentsize){
		cout<<"can't find the element you want to remove"<<endl;
		return 0;
	}
	return 1;
}

template <typename Type> void SeqList<Type>::Print(){
	for(int i=0;i<=m_ncurrentsize;i++)
		cout<<i+1<<":\t"<<m_elements[i]<<endl;
	cout<<endl<<endl;
}

Test.cpp

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

using namespace std;

int main()
{
	SeqList<int> test(15);
	int array[15]={2,5,8,1,9,9,7,6,4,3,2,9,7,7,9};
	for(int i=0;i<15;i++){
		test.Insert(array[i],0);
}
	test.Insert(1,0);
	cout<<(test.Find(0)?"can't be found ":"Be found ")<< 0 << endl<<endl;
	test.Remove(7);
	test.Print();
	test.Remove(9);
	test.Print();
	test.Remove(0);
	test.Print();
	return 0;
}
2、	单链表

ListNode.h

template<typename Type> class SingleList;

template<typename Type> class ListNode{
private:
	friend typename SingleList<Type>;

	ListNode():m_pnext(NULL){}
	ListNode(const Type item,ListNode<Type> *next=NULL):m_data(item),m_pnext(next){}
	~ListNode(){
		m_pnext=NULL;
	}

public:
	Type GetData();
	friend ostream& operator<< <Type>(ostream& ,ListNode<Type>&);

private:
	Type m_data;
	ListNode *m_pnext;
};

template<typename Type> Type ListNode<Type>::GetData(){
	return this->m_data;
}

template<typename Type> ostream& operator<<(ostream& os,ListNode<Type>& out){
	os<<out.m_data;
	return os;
}


SingleList.h

#include "ListNode.h"

template<typename Type> class SingleList{
public:
	SingleList():head(new ListNode<Type>()){}
	~SingleList(){
		MakeEmpty();
		delete head;
	}

public:
	void MakeEmpty();                       //make the list empty
	int Length();                           //get the length
	ListNode<Type> *Find(Type value,int n); //find thd 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 in the nth position
	Type Remove(int n=0);                   //remove the nth data
	bool RemoveAll(Type item);              //remove all the data which is equal to item
	Type Get(int n);                        //get the nth data
	void Print();                           //print the list

private:
	ListNode<Type> *head;
};

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

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

template<typename Type> ListNode<Type>* SingleList<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;i++){
		pmove=pmove->m_pnext;
	}
	if(pmove==NULL){
		cout<<"The n is out of boundary"<<endl;
		return NULL;
	}
	return pmove;
}

template<typename Type> ListNode<Type>* SingleList<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=pmove->m_pnext;
		if(pmove->m_data==value){
			count++;
		}

	}
	if(pmove==NULL){
		cout<<"can't find the element"<<endl;
		return NULL;
	}
	return pmove;
}

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

template<typename Type> bool SingleList<Type>::RemoveAll(Type item){
	ListNode<Type> *pmove=head;
	ListNode<Type> *pdel=head->m_pnext;
	while(pdel!=NULL){
		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 SingleList<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;i++){
		pmove=pmove->m_pnext;
	}
	if(pmove->m_pnext==NULL){
		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 SingleList<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(NULL==pmove){
			cout<<"The n is out of boundary"<<endl;
			exit(1);
		}
	}
	return pmove->m_data;
}

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

test.cpp

#include <iostream>
using namespace std;

#include "SingleList.h"


int main()
{
	SingleList<int> list;
	for(int i=0;i<20;i++){
		list.Insert(i*3,i);
	}
	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;

	cout<<*list.Find(18,1)<<endl;

	list.Find(100);

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

	return 0;
}

3、	双向链表

NodeList.h

template<typename Type> class DoublyList;

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

template<typename Type> Type ListNode<Type>::GetData(){
	return this->m_data;
}

DoubleList.h

#include "ListNode.h"

template<typename Type> class DoublyList{
public:
	DoublyList():head(new ListNode<Type>()){    //the head node point to itself
		head->m_pprior=head;
		head->m_pnext=head;
	}
	~DoublyList(){
		MakeEmpty();
		delete head;
	}