以链表为载体学习C++（2）

这是一个系列的文章，主要目的是让初学者掌握链表的实现方法，并且从C过渡到C++。

作者：重庆工程职业技术学院万青

在第1篇文章中，由于采用C语言实现，数据和操作是分离的，对链表的操作（如add、del、insert）中都包含一个参数List *li。

下面将采用C++实现，由于类的方法中隐含有this指针，在本类的方法中访问成员head、tail和length的时候，不再需要li作为参数。

也就是说，C版本中的li->head变成了this->head，而“this->”是可以省略的，所以直接写head。

另外，C++类中有构造函数和析构函数，所以创建链表的工作在构造函数中完成，清除链表的工作在析构函数中完成。

  1 #include<stdio.h>
  2  class CNode //节点类
  3  {
  4      public:
  5          int data;
  6          CNode *next;
  7  };
  8  class CList //链表类
  9  {
 10      private:
 11          CNode *head,*tail; //头、尾节点对象指针
 12          int length; //节点总数
 13      public:
 14          CList(); //构造函数(创建链表对象，并创建头节点，初始化头、尾指针等)
 15          void add(int num); //添加值为num的节点到链表末尾
 16          int insert(int num,int idx); //将数据num插入到链表的idx位置之后
 17          int del(int idx); //删除链表中的第idx个节点(idx从1开始计)
 18          CNode *getPointerByIndex(int idx);//获取第idx个节点的对象指针(idx从1开始计)
 19          void show(); //显示(遍历)链表的所有节点
 20          ~CList(); //析构函数(清除链表中的所有节点对象)
 21  };
 22  
 23  CList::CList()
 24  {
 25      CNode *p;
 26      p=new CNode();
 27      head=tail=p;
 28      tail->next=NULL;
 29      length=0;
 30  }
 31  
 32  void CList::add(int num)
 33  {
 34      CNode *p;
 35      p=new CNode();
 36      p->data=num; //给数据域赋值
 37      tail->next=p; 
 38      tail=p;//调整尾指针，指向新节点
 39      tail->next=NULL; //设置结束标志
 40      length++; //节点总数加1
 41  }
 42  
 43  CNode *CList::getPointerByIndex(int idx)
 44  {
 45      CNode *p;
 46      int i=1;
 47      if(idx<1 || idx>length) return NULL;
 48      p=head;
 49  
 50      while(i<=idx)
 51          {
 52              p=p->next;
 53              i++;
 54          }
 55      return p;
 56  }
 57  
 58  int CList::insert(int num,int idx)
 59  {
 60      CNode *p,*tmp;
 61      p=getPointerByIndex(idx);
 62      if(p!=NULL)
 63      {
 64          tmp=new CNode();
 65          tmp->data=num;
 66          tmp->next=p->next;
 67          p->next=tmp;
 68          length++;
 69          return 1; //成功，返回1
 70      }
 71      return 0; //失败，返回0
 72  }
 73  
 74  int CList::del(int idx)
 75  {
 76      CNode *p,*q;
 77      if(idx<1 || idx>length)
 78          return 0; //失败，返回0
 79  
 80      //获得要删除节点的前一个节点指针
 81      if(idx==1) p=head;
 82      else p=getPointerByIndex(idx);
 83  
 84      //删除p节点的后一节点
 85      q=p->next; //记住后一节点的指针
 86      p->next=q->next;
 87      delete(q);
 88      length--;
 89      return 1;//成功，返回1
 90  }
 91  
 92  void CList::show()
 93  {
 94      CNode *p;
 95      p=head;
 96      while(p->next!=NULL)
 97          {
 98              p=p->next; //head节点没有数据，先移动再读取
 99              printf("%d ",p->data);
100          }
101      printf("\n--------------\n");
102  }
103  
104  CList::~CList()
105  {
106      CNode *curr,*next;
107      curr=head;
108      while(curr->next!= NULL)
109          {
110              next=curr->next;
111              delete(curr);
112              curr=next;
113          }
114      delete(curr);
115  }
116  
117  void main()
118  {
119      CList *li=new CList();
120      li->add(100);
121      li->add(101);
122      li->add(102);
123      li->add(103);
124      li->show();
125      li->insert(200,2);
126      li->show();
127      li->insert(300,3);
128      li->show();
129      li->del(1);
130      li->show();
131      delete(li);
132  }