slist.cpp

是数据结构中单链表的VC++程序

// Slist.cpp: implementation of the Slist class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
//#include "CSLisDlg.h"
#include "Slist.h"

/*#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
*/
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

//Slist.CPP
#include <iostream.h>
template<class Type> class SList;
template<class Type> class SListnode//单链表节点类
{
    friend class SList<Type>;
    private:
		Type data;
		SListnode<Type> *next;
    public:
		SListnode(){data=NULL,next=NULL;}
		SListnode(Type data)
		  { this->data=data;next=NULL; }
		SListnode(const Type &data,SListnode<Type> *next)
		  { this->data=data;this->next=next; }
		SListnode *nextnode(){return next;}
		Type Getdata(){ return data; }
		SListnode<Type> *Getnext(){ return next; }
};
///////////////////////////////////////////////////////////
template<class Type> class SList//单链表类,含头节点
{
    private:
		SListnode<Type> *head;
		SListnode<Type> *current;//指向当前节点的指针
    public:
		SList();
		SList(char *fn);//根据文件创建单链表
		void Create(int n,bool InsertInHead);//创建n个节点的单链表,(头插法,尾插法)
		~SList();
		void MakeEmpty();//清空单链表
		int Length() const;
		void SetCurrent(SListnode<Type> *cp){ current=cp; }
		SListnode<Type> *GetCurrent(){ return current; }
		SListnode<Type> *Getnext(){ return current->next; }
		SListnode<Type> *Gethead(){ return head; }
		SListnode<Type> *Find(Type value);//查找值为value的节点
		SListnode<Type> *Getnode(int i);//取第i号结点
	
		void Insert(Type value,int i);//插在第i号结点前
		void Insert(Type value){Insert(value,1);};//插在第1号结点前
		void Insert(Type value,bool before);//在当前节点(前,后)插入一个节点
		void Remove(Type value);//删除值为value的结点
		void Delete(int i);//删除第i号结点
		void Delete();//删除当前结点
		Type *Getdata(int i);//取第i号结点的值
		Type *Current();//取当前结点的值
		Type *First();  //取第一个结点的值
		Type *Next();   //取下一个结点的值
		void Modifydata(Type value){current->data=value;}//修改当前节点的值
		void Invert();	//将单链表倒置
        void show();
};
///////////////////////////////////////////////////////////
template<class Type>
void SList<Type>::show()
{
    current=head;  
	while(current!=NULL)
	  {
	     cout<<current->data<<endl;
	     current=current->next;
	  }
}
template<class Type>
SList<Type>::SList()
{ 
	head=new SListnode<Type>;
	current=head;
}
///////////////////////////////////////////////////////////
template<class Type>
SList<Type>::~SList()
{ 
	MakeEmpty();
	delete head;
}
///////////////////////////////////////////////////////////
template<class Type>
void SList<Type>::Create(int n,bool InsertInHead)
{ 
     SListnode<Type> *q;   
	 if(0==n) return;
	 if(InsertInHead)
	   {
	     for(int i=0;i<n;i++)
		 {
		    
			 q=new SListnode<Type>((Type)(i+1),head->next);
             head->next=q;

		 }
	   }
       else
	   {
	   
	     for(int i=0;i<n;i++)
		 {
		     
			 q=new SListnode<Type>((Type)(i+1),NULL);
			 current->next=q;
			 current=current->next;
		 }
	   
	   }

      current=head;
}

///////////////////////////////////////////////////////////
template<class Type>
void SList<Type>::MakeEmpty()
{
    while(head->next!=NULL)
	{
	   SListnode<Type> * q;
	   q=head->next;
	   head->next=q->next;
	   delete q;
	}
}
///////////////////////////////////////////////////////////
template<class Type>
int SList<Type>::Length() const
{
	SListnode<Type> *q;
	q=head;
	int n=0;
	while(q->next!=NULL)
	{
	      n++;
		  q=q->next;
	}
    return n;
}
///////////////////////////////////////////////////////////
template<class Type>
SListnode<Type> * SList<Type>::Find(Type value)
{
    SListnode<Type> *p=head->next;
    while(p!=NULL&&p->data!=value)
		p=p->next;
	
    return p;
}
///////////////////////////////////////////////////////////
template<class Type>
SListnode<Type> * SList<Type>::Getnode(int i)
{
    if(i<0)  return NULL;
    if(i==0)  return head;
    SListnode<Type> *p=head;
    for(int j=1;p!=NULL&&j<=i;j++)
		p=p->next;
    return p;
}
///////////////////////////////////////////////////////////
template<class Type>
Type * SList<Type>::Getdata(int i)
  {
    SListnode<Type> *p=Getnode(i);
    if(p==NULL||p==head)
		return NULL;
    else
		return &(p->data);
  }
///////////////////////////////////////////////////////////
//插在第i号节点前
template<class Type>
void SList<Type>::Insert(Type value,int i)
{
   SListnode<Type> *q=Getnode(i-1);   // 第i-1个节点的地址
   SListnode<Type> *p=q->next;    // 第i个节点的地址
   q->next=new SListnode<Type>(value,p);
}
///////////////////////////////////////////////////////////
template<class Type>
void SList<Type>::Insert(Type value,bool before)
{
	SListnode<Type> *q;
	if(before)
	{
	    q=current->next;
		current->next=new SListnode<Type>(value,q);
	}
	else
	{
	  if(current==head)
		  return;
	  else
	  { 
	      q=head;
		  while(q->next!=current)
		  {
		         q=q->next;
		  }
	      q->next=new SListnode<Type>(value,current);

	  
	  }
	}
}
///////////////////////////////////////////////////////////
template<class Type>
void SList<Type>::Delete(int i)
{
   SListnode<Type> *q=Getnode(i-1); //得到第i-1个节点的地址
   SListnode<Type> *p=q->next;      //得到第i个节点的地址
   q->next=p->next;
   delete p;
}
///////////////////////////////////////////////////////////
template<class Type>
void SList<Type>::Delete()
{
   //当只剩下头接点，时return
	if(current==head)
	   return;
	if(this->Length()<1)
	   return;
	SListnode<Type> *q;   //q为当前节点的前一个节点
	SListnode<Type>  *p;
	q=head;	
	//找到当前节点的前一个节点
	while(q->next!=current)
	  {
		 q=q->next;
	 
	  }	 
	p=current;
    q->next=current->next;  //q指向当前节点的下一个节点
//当删除的是第一个节点时
	if(q==head)
	{
		if(p->next==NULL)
            current=head;
		else
		    current=(p->next);
		delete p;
		return;
	}
	//当删除的是最后一个节点时	
	if(q->next!=NULL)
	{current=q->next; }  //current指针移到后一个节点
	else
	 {current=q;}


		delete p;
}
///////////////////////////////////////////////////////////
template<class Type>
void SList<Type>::Remove(Type value)
{
   SListnode<Type> *q=Find(value);
   SListnode<Type> *tem=head;
   
   while(tem->next!=q)
   {
      tem=tem->next;
   }
   tem->next=q->next;
   delete q;
}
//////////////////////////////////////////////////////////
template<class Type>
Type * SList<Type>::First()
{
	if(head->next!=NULL)
	   current=head->next;

    return &(current->data);
}
///////////////////////////////////////////////////////////
template<class Type>
Type * SList<Type>::Next()
{
    if(current->next!=NULL)
	   	
		current=current->next;
	    return &(current->data);

}
///////////////////////////////////////////////////////////
template<class Type>
Type * SList<Type>::Current()
{
    return &(current->data);
}
///////////////////////////////////////////////////////////
template<class Type>
void SList<Type>::Invert()//将单链表倒置
{
    SListnode<Type> *p;
    SListnode<Type> *q;
	p=head->next;
	q=p->next;
	p->next=NULL;
    SListnode<Type> *tem;
    while(q!=NULL)
	{  tem=q->next;
	   q->next=p;
	   p=q;
	   q=tem;
	}	
    head->next=p;
}