ADT链表实现

#include "stdafx.h"
#include
#include
using namespace std;

//ADT链表实现
/**********************************
*基本操作：
*      1、初始化表
*      2、检查表是否为空
*      3、输出表
*      4、确定表的长度
*    5、销毁表
*      6、检索包含在第一个结点中的info
*      7、检索包含在最后一个结点的info
*      8、搜索表中指定的项
*      9、在表中插入一项
*      10、从表中删除一项
*      11、复制一个链表
***********************************/

//ADT链表定义
template
struct nodeType
{
 Type info;
 nodeType *link;
};

template
class linkedlistType
{
 friend ostream& operator<< <>(ostream&,const linkedlistType&);
 //overload the stream insertion operator

public:
 const linkedlistType& operator=(const linkedlistType&);
 //overload the assignment operator
 void initList();
 bool isEmptyList();
 int length();
 void destroyList();
 Type front();
 Type back();
 bool search(const Type& searchItem);
 void insertFirst(const Type& newItem);
 void insertLast(const Type& newItem);
 void deleteNode(const Type& delItem);
 linkedlistType();
 linkedlistType(const linkedlistType& otherlist);
 ~linkedlistType();

protected:
 int count;
 nodeType *first;
 nodeType *last;
private://只使用该函数实现复制构造函数和重载赋值运算符的函数
 void copyList(const linkedlistType& otherList);
};

template
bool linkedlistType::isEmptyList ()
{
 return (first==NULL);
}

template
linkedlistType::linkedlistType ()
{
 count=0;
 first=NULL;
 last=NULL;
}

template
void linkedlistType::destroyList ()
{
 nodeType *temp;
 while(first!=NULL)
 {
  temp=first;
  first=first->link;
  delete temp;
 }
 last=NULL;
 count=0;
}

template
void linkedlistType::initList ()
{
 destroyList();
}

template
ostream& operator<<(ostream& os,const linkedlistType& list)
{
 nodeType *current;
 current=list.first ;
 while(current!=NULL)
 {
  os<info<<" ";
  current=current->link ;
 }
 return os;
}

template
int linkedlistType::length ()
{
 return count;
}

template
Type linkedlistType::front ()
{
 assert(first!=NULL);
 return first->info;
}

//检索最后一个节点的数据
template
Type linkedlistType::back ()
{
 assert(last!=NULL);
 return last->info;
}

//搜索一个指定的数据项
template
bool linkedlistType::search (const Type& searchItem)
{
 nodeType *current;
 bool found;
 current=first;
 found=false;
 while(current!=NULL)
 {
  if(current->info ==searchItem)
  {
   found=true;
   break;
  }
  else
   current=current->link ;
 }
 return found;
}

//在表头插入结点
template
void linkedlistType::insertFirst (const Type& newItem)
{
 nodeType *newNode;
 newNode=new nodeType;
 assert(newNode!=NULL);
 newNode->info=newItem;
 newNode->link=first;
 first=newNode;
 count++;
 if(last==NULL)
  last=newNode;
}

//在表尾插入结点
template
void linkedlistType::insertLast (const Type& item)
{
 nodeType *newNode;
 newNode=new nodeType;
 assert(newNode!=NULL);
 newNode->info =item;
 newNode->link =NULL;

 if(first==NULL)
 {
  first=newNode;
  last=newNode;
  count++;
 }
 else
 {
  last->link=newNode;
  last=newNode;
  count++;
 }
}

template
void linkedlistType::deleteNode (const Type& delItem)
{
 nodeType *current;
 nodeType *trailCurrent;
 bool found;

 if(first==NULL)
  cerr<<"cannot delete from an empty list.\n";
 else
 {
  if(first->info==delItem)
  {
   current=first;
   first=first->link ;
   count--;
   if(first==NULL)//has only one node
   {
    last=NULL;
    delete current;
   }
  }
  else
  {//search the list for the node with the given info
   found=false;
   trailCurrent=first;
   current=first->link;

   while(current!=NULL && !found)
   {
    if(current->info !=delItem)
    {
     trailCurrent=current;
     current=current->link;
    }
    else
     found=true;
   }
   if(found)
   {
    trailCurrent->link=current->link;
    count--;

    if(last==current)  //node to be deleted was the last node
     last=trailCurrent;
    delete current;
   }
   else
    cout<<"item to be deleted is not in the list."<  }

 }
}

template
void linkedlistType::copyList (const linkedlistType& otherlist)
{
 nodeType *newNode;
 nodeType *current;
 if(first!=NULL)
  destroyList();

 if(otherlist.first ==NULL)//otherlist is empty
 {
  first=NULL;
  last=NULL;
  count=0;
 }
 else
 {
  current=otherlist.first ;
  count=otherlist.count ;

  //copy the first node
  first=new nodeType;
  assert(first!=NULL);
  first->info =current->info;
  first->link =NULL;
  
  last=first;
  current=current->link ;

  //copy the remaining list
  while(current!=NULL)
  {
   newNode =new nodeType;
   assert(newNode!=NULL);
   newNode->info =current->info ;
   newNode->link =NULL;
   last->link =newNode;
   last=newNode;

   current=current->link;
  }

 }
}

template
linkedlistType::~linkedlistType()
{
 destroyList();
}

template
linkedlistType::linkedlistType(const linkedlistType& otherlist)
{
 first=NULL;//copyList通过检查first来验证原始链表是否为空，故应先初始化为NULL
 copyList(otherlist);
}

template
const linkedlistType& linkedlistType::operator =(const linkedlistType& otherlist)
{
 if(this!=&otherlist)
  copyList(otherlist);

 return *this;
}

//test program
int main()
{
    linkedlistType list1,list2;
 list1.initList ();
 list1.insertLast (23);
 cout< operator<<(cout,list1)<

 for(int i=0;i<10;i++)
  list1.insertFirst (10+i);

 //after insert 10 elements to list1
 cout<<"list1 elements:"< cout<<"length of list1 is:"< cout<<"the back element of list1 is:"< cout<<"the front element of list1 is :"<

 if(list1.search (18))
  cout<<"18 is in list1"< list1.deleteNode (23);
 cout<<"after delete 23:"< cout<

 list2=list1;
 cout<<"list2:"<

 if(list2.isEmptyList ())
  cout<<"list2 is empty"<

 linkedlistType list3(list2);
 cout<<"list3:"< const int num=23;
 cout<<"delete 23 from list3:"< list3.deleteNode (num);
 cout<<"after delete 23,list3:"< cout<

 return 0;
}