#include <iostream.h>
#define NULL 0

class Node //节点类
{
public:
 Node(){}
 Node(int n){ num=n; next=NULL; }
 Node(int n, Node *p){ num=n; next=p;}

 void setNum(int n) {num =n;}
 void setNext(Node *p){next =p;}
 
 int getNum(){return num;}
 Node *getNext(){ return next;}

private:
 int num;
 Node *next;
};

class Linklist //链表类
{
public:
 Linklist(){head=NULL;}
 Linklist(int n){ head = new Node(n); }

 void addAtEnd(int n);
 void addAtEnd(Node *p);
 void visitAllNode();
 void addBeforeNum(Node *p, int num); //在节点值为num之前添加新节点p
 void deleteNum(int num);//删除值为num的节点
private:
 Node *head;
};

void Linklist::addAtEnd(int n)  //往链表尾添加节点
{
 Node *p=head;
 if(head==NULL){ head = new Node(n);}
 else
 {
  while(p->getNext()!=NULL)
  { p= p->getNext(); }//用p来指向最后一个节点
  p->setNext(new Node(n));//插入节点
 }
 
}
void Linklist::addAtEnd(Node *p) //往链表尾添加节点
{
 Node *pn=head;
 if(head==NULL) { head=p; }
 else
 {
  while(pn->getNext()!=NULL)
  { pn=pn->getNext(); }//用pn来指向最后一个节点
  pn->setNext(p);//插入节点
 }
 
}

void Linklist::visitAllNode()//遍历链表
{
 Node *p;
 p=head;

 if(p==NULL){cout<<"空链表!"<<endl;}
 else
 {
  cout<<"表头： ";
  while(p->getNext()!=NULL)
  {
   cout<<p->getNum()<<" --> ";
   p=p->getNext();
  }
  cout<<p->getNum()<<" 表尾"<<endl;
 }
}

void Linklist::addBeforeNum(Node *p, int num) //在节点值为num之前添加新节点p
{
 Node *pn=head,*follow=pn;
 if(pn==NULL)
 {
  cout<<"空链表！插入节点。";
  head= p;
  return;
 }

 while(pn->getNext() != NULL && pn->getNum() != num)
 // 查找指向节点值为num的节点
 { 
  follow = pn; //follow一直指向pn前的一个节点
  pn = pn->getNext();
 }
 if(pn==head && pn->getNum() == num)//找到节点，且为头指针
 {
  p->setNext(pn);
  head=p;
 }
 else if(pn->getNum() ==  num) //找到此节点，注：follow指向其上一节点
 {
  p->setNext(pn);
  follow->setNext(p);
 }
 else //没有找到节点,pn指向最后一个节点,将新节点插入链表尾
 {
  cout<<"没有找到，插入到链表尾。"<<endl;
  pn->setNext(p); 
 }
 
}

void Linklist::deleteNum(int num) //删除节点
{
 Node *p=head,*follow=p;
 if(p->getNum() == num)//若删除的节点为第1个节点
 {
  head = p->getNext();
  delete p;
 }
 else
 {
  while(p->getNext()!=NULL && p->getNum() != num)
  { 
   follow = p;//follow一直指向p的前一个节点
   p = p->getNext();
  }
  if(p->getNum() == num)
  {
   follow->setNext(p->getNext());
   delete p;
  }
  
 }
}

void main()
{
 Linklist *pl=NULL;
 int num, n;
 Node *p;
 char option;
 while(1)
 {
  cout<<"\n链表操作练习："<<endl;
  cout<<"1: 创建链表"<<endl;
  cout<<"2: 在链表尾插入新节点"<<endl;
  cout<<"3: 在节点值为num的节点前插入新节点"<<endl;
  cout<<"4: 删除节点"<<endl;
  cout<<"5: 遍历节点"<<endl;
  cout<<"0: 退出"<<endl;
  
  cout<<"\n请输入你的选择:";
  cin>>option;
  
  switch(option)
  {
  case '0':
   break;
  case '1':
   cout<<"请输入第一个节点值"<<endl;
   cin>>num;
   pl = new Linklist(num);
   pl->visitAllNode();
   break;
  case '2':
   cout<<"请输入节点值:";
   cin>>num;
   if(pl==NULL){ pl = new Linklist(num);}
   else
   {
    pl->addAtEnd(num); //pl->addAtEnd(new Node(num));
   }
   pl->visitAllNode();
   break;
  case '3':
   cout<<"请输入插入的节点值:";
   cin>>num;
   cout<<"请输入要插入到哪个节点前，以节点的值表示：";
   cin>>n;
   pl->addBeforeNum(new Node(num), n);
   pl->visitAllNode();
   break;
  case '4':
   cout<<"请输入要删除的节点的值：";
   cin>>num;
   pl->deleteNum(num);
   pl->visitAllNode();
   break;
  case '5':
   pl->visitAllNode();
   break;
  default:
   cout<<"你输入错误，请重新输入！"<<endl;
  }

  if(option == '0' )
   break;
 }

}