链表类

时间：01-10来源：作者：点击数：63

链表结点类编写好了，我们可以向链表类进军了。链表是由一个个链表结点组成的，所以我们会在链表类中使用到链表结点类。链表结点类是一个很简单的类，链表类是一个功能更为强大的类。正是将一个个类不断地组合与扩充，使得面向对象的程序功能越来越强大。

让我们感兴趣的是，假设我们编写的链表需要有一个头结点作为成员数据，那么是先有链表呢，还是先有头结点？我们又该如何在给链表作初始化的同时初始化头结点呢？

当一个对象中包含别的对象时，我们可以在它的构造函数定义中用以下格式调用其成员对象的构造函数：
类名::构造函数名(参数表):成员对象名1(参数表)[,……成员对象名n(参数表)]

前一段和普通的构造函数一样，冒号之后则表示该类中的成员对象怎样调用各自的构造函数。

下面我们来看一个简单的面向对象的链表程序：（程序15.3）
//node.h同程序15.2.2
//linklist.h

#include "node.h"//需要使用链表结点类
#include <iostream>
using namespace std;
class Linklist
{
   public:
   Linklist(int i,char c);//链表类构造函数
   bool Locate(int i);//根据整数查找结点
   bool Locate(char c);//根据字符查找结点
   bool Insert(int i=0,char c='0');//在当前结点之后插入结点
   bool Delete();//删除当前结点
   void Show();//显示链表所有数据
   void Destroy();//清除整个链表
   private:
   Node head;//头结点
   Node * pcurrent;//当前结点指针
};
Linklist::Linklist(int i,char c):head(i,c)//类名::构造函数名(参数表):成员对象名1(参数表)，链表类构造函数，调用head对象的构造函数重载1，详见Node.h文件
{
   cout<<"Linklist constructor is running..."<<endl;
   pcurrent=&head;
}
bool Linklist::Locate(int i)
{
   Node * ptemp=&head;
   while(ptemp!=NULL)
   {
      if(ptemp->readi()==i)
      {
         pcurrent=ptemp;//将当前结点指针指向找到的结点
         return true;
      }
      ptemp=ptemp->readn();//查找下一个结点
   }
   return false;
}
bool Linklist::Locate(char c)
{
   Node * ptemp=&head;
   while(ptemp!=NULL)
   {
      if(ptemp->readc()==c)
      {
         pcurrent=ptemp;
         return true;
      }
      ptemp=ptemp->readn();
   }
   return false;
}
bool Linklist::Insert(int i,char c)
{
   if(pcurrent!=NULL)
   {
      Node * temp=new Node(i,c,pcurrent,pcurrent->readn());//调用Node类构造函数重载2
      if (pcurrent->readn()!=NULL)
      {
         pcurrent->readn()->setp(temp);
      }
      pcurrent->setn(temp);
      return true;
   }
   else
   {
      return false;
    }
}
bool Linklist::Delete()
{
   if(pcurrent!=NULL && pcurrent!=&head)//head结点不能删除
   {
      Node * temp=pcurrent;
      if (temp->readn()!=NULL)
      {
         temp->readn()->setp(pcurrent->readp());
      }
      temp->readp()->setn(pcurrent->readn());//先连
      pcurrent=temp->readp();
      delete temp;//后断
      return true;
   }
   else
   {
      return false;
   }
}
void Linklist::Show()
{
   Node * ptemp=&head;
   while (ptemp!=NULL)//链表的遍历
   {
      cout <<ptemp->readi() <<'\t' <<ptemp->readc() <<endl;
      ptemp=ptemp->readn();
   }
}
void Linklist::Destroy()
{
   Node * ptemp1=head.readn();
   while (ptemp1!=NULL)
   {
      Node * ptemp2=ptemp1->readn();
      delete ptemp1;
      ptemp1=ptemp2;
   }
   head.setn(NULL);//头结点之后没有其他结点
}

//main.cpp

#include "Linklist.h"
#include <iostream>
using namespace std;
int main()
{
   int tempi;
   char tempc;
   cout <<"请输入一个整数和一个字符：" <<endl;
   cin >>tempi >>tempc;
   Linklist a(tempi,tempc);//创建一个链表，头结点数据由tempi和tempc确定
   a.Locate(tempi);
   a.Insert(1,'C'); 
   a.Insert(2,'B');
   a.Insert(3,'F');
   cout <<"After Insert" <<endl;
   a.Show();
   a.Locate('B');
   a.Delete();
   cout <<"After Delete" <<endl;
   a.Show();
   a.Destroy();
   cout <<"After Destroy" <<endl;
   a.Show();
   return 0;
}

运行结果：
请输入一个整数和一个字符：
4 G
Node constructor is running...
Linklist constructor is running...
Node constructor is running...
Node constructor is running...
Node constructor is running...
After Insert
4 G
3 F
2 B
1 C
After Delete
4 G
3 F
1 C
After Destroy
4 G