linkedlist.cpp

利用链队列判断字符串的中心对称问题

// 链表的类的实现文件 LinkedList.cpp
#include"LinkedList.h"	
#include<iostream.h>
#include<stdlib.h>

template <class T>
Node<T>*LinkedList<T>::GetNode(const T&item, Node<T>*ptr)    //申请结点空间的函数
{
	Node<T>*newNode=new Node<T>(item,ptr);  

	if(!newNode)                    //若动态内存申请失败，给出相应的提示并返回空指针
	{
		cerr<<" GetNode: Memoery allocation failed!"<<endl;
		return NULL;

	}

	return newNode;   //返回指向新生成结点的指针
}



template <class T>
void LinkedList<T>::FreeNode(Node<T>*ptr) //释放结点空间的函数
{
	if(!ptr)   //若ptr为空，则给出相应提示并返回
	{
		cerr<<"FreeNode: invaild node pointer!"<<endl;
		return ;

	}

	delete ptr;//释放结点占用的内存空间
}


template <class T>
LinkedList<T>:: LinkedList(void)//建立一个空链表
{
	front=NULL;
	rear=NULL;
	prevptr=NULL;
	currptr=NULL;
	size=0;
	postion=-1;

}
template <class T>
LinkedList<T>::~LinkedList(void) //析构函数
{
	Clear();                     //清空链表，释放所有的结点的内存空间
}


template <class T>
LinkedList<T>&LinkedList<T>::operator=(const LinkedList<T>&orglist) //重载赋值运算符的函数
{
	Node<T> *P=orgList.front;
	Clear();     //清空本链表

	while(p)    //将表orgLIst中的元素复制到本链表中
	{
		InsertAfter(P->data);
		p=p->NextNode();
	}
	
	Setpostion(orgList.postion); //设置当前结点

	return *this;
}


template <class T>
		
int LinkedList<T>::Size(void)const   // 取连表的大小的函数
{
	return size;

}


template<class T>
int LinkedList<T>::NextNode(void)  //将当后继结点设置为当前结点的函数
{
	
	if(position>=0&&position<size)//若当前结点存在，将其后继结点设置为当前结点
	{
	  position++:
	  prevptr=currptr;
	  currptr=currptr->NextNode();

	}

	else
	{
	
		position=size;	//否则将当前结点的位置设为表尾后
	}

	return position;  //返回新的位置
}




template <class T>  
int LinkedList<T>::SetPostion(int pos)  //重置当前结点位置的函数
{
	if(!size) return -1;              //若为空，则返回-1
	
	/*if(pos<0&&pos>size)   //若位置越界，则修正位置值
	{
		cerr<<"postion error: "<<endl;
		return -1;
	}*/

	prevptr=NULL;
	currptr=front;
	postion=0;

	for(int k=0;k<pos;k++)//寻找对应结点
	{
		postion++;
		prevptr=currptr;
		currptr=currptr->NextNode();
	}
         //返回当前结点位置
	return postion;

}

template <class T>
int  LinkedList<T>::InsertAt(const T&item) //在当前结点处插入新的结点的函数
{
  
	Node<T> L*newNode;  

    if(!size)   //在空表中插入
	{
	  newNode=GetNode(item,front);
	  front=rear=newNode;
	  postion=o;
	}

      else if(!prevptr)  //在表头结点插入

	  {
	      newNode=GetNode(item,front);
	      front=newNode;

	  }
	    else   //在表中间位置插入
		{
		  newNode=GetNode(item, currptr);
		  prevptr->InsertAfter(newNode);
		}

	  size++;         //增加链表的长度
	  currptr=newNode;//新插入的结点作为当前结点

}

template <class T>
void LinkedList<T>::InsertAfter(const T&item)   //在当前结点后插入新的结点的函数
{
	Node<T>*newNode;

  if(!size)      //在空表中插入
  {
	  newNode=GetNode(item,NULL);
	  front=rear=newNode;
	  postion=0;

  }
    else if(currptr==rear||!currptr)   //在表尾结点后插入
	{
		newNode=GetNode(item,NULL);
	    rear->InsertAfter(newNode);
	    prevptr=rear;
	    rear=newNode;
	    postion=size;
	}

	  else    //在链表的中间位置插入
	  {
		  newNode=GetNode(item, currptr);
		  currptr->InsertAfter(newNode);
		  prevptr=currptr;
		  postion++;
	  }

	  size++;           //增加表的长度
	  currptr=newNode;  //将插入的新结点作为当前结点
}





template <class T>
void LinkedList<T>::DeleteAt(void)  //删除当前结点的函数
{
	Node<T>*oldNode;

	if(!currptr)                 //若表为空或已到表尾之后，则给错误提示并返回
	{
		cerr<<" DeleteAt: currptr postion is invalid!"<<endl;
		return ;

	}

	if(!prevptr)            //删除的是表头结点
	{
		oldNode=front;
		front=currptr->NextNode();

	}

	else
	{
		oldNode=prevptr->DeleteAfter();  //删除的是表中的结点

	}


	  if(oldNode==rear)
	  {
	                                 //删除的是表尾结点，则修改表尾指针和当前结点位置
		rear=prevptr;
		postion--;
	  }

	currptr=oldNode->NextNode();  //后继结点作为新的当前结点
	FreeNode(oldNode);          //释放原当前结点
	size--;                    //链表的大小减1

}




 template <class T>      
	 
void LinkedList<T>::DeleteAfter(void)   //删除当前结点后继的函数
 { 
	 
	 Node<T>*oldNode;

	if(!currptr||currptr==rear)       //若表为空或已到表尾，则给出错误提示并返回

	{
		cerr<<" DeleteAfter: currptr postion is invalid!"<<endl;
		return ;
	}
	
  oldNode=prevptr->DeleteAfter();        //保存披删除结点是指针并从链表中删除该结点

  if(oldNode==rear)
  {  rear=currptr;}                 //删除的是表尾结点

	FreeNode(oldNode);          //释放披删除结点
	size--;                    //链表大小减1
 }




template<class T>

T LinkedList<T>::GeTData(void)const      //获取当前结点数据的函数
{ 
	if(!size||!currptr)					 //若表为空或已到表尾，则给出错误提示并退出

	{
		cerr<<" Data: currptr node not exist"<<endl;
		exit(1);
	}

	return currptr->data;

}

template<class T>
void LinkedList<T>::SetData(const T& item)       //修改当前结点数据的函数
{	
	if(!size||!currptr)                        //若表为空或已到表尾，则给出错误
	{
		cerr<<"Data:currptr node not exist"<<endl;
		exit(1);
	}

 currptr->data=item;                      //修改当前结点的值 

}

template <class T>
 
void LinkedList<T>::Clear(void)            //清空链表的函数
{
	Node<T>*currNode=front, *nextNode;

	while(currNode)
	{
		nextNode=currNode->NextNode();             //保存后继结点指针
		FreeNode(currNode);                       //释放当前结点
		currNode=nextNode;                       //原后继结点成为当前结点
	} 
	front=rear=prevptr=currptr=NULL;           //修改空链表数据
	size=0;
	postion=-1;
}



template <class T>
bool  LinkedList<T>::IsEmpty(void)const   // 判断表是否为空的函数
{
	return (size?false:true);
}