单链表的基础操作方法

/*
 单链表的基本操作
 具体操作包括:
  链表的初始化,清空
  3种插入方法:在第一个结点之前,最后一个结点之后,任位置插入
  2种查找方法:1.查找某一元素值的位置2.查找某一位置的元素
  2种删除方法:1.删除给定值的第一个结点 2.删除给定值的所有结点
  2种修改方法:1.修改给定值的第一个结点并赋其指定的新值 2.修改给定值的所有结点为其新值
  1种遍历方法:打印所有的元素值
*/
#include 
using namespace std;
typedef int T;//自定义数据类型
/*
 定义结点
*/
struct Node{
 T data;
 Node * next;
 Node(const T& n):data(n),next(NULL){}
};
/*
 定义链表
*/
class LinkList{
 private:
  Node* head;
  
 public:
  /*
   初始化一个带头结点的链表
  */
  LinkList(){
   head = new Node(0);
  }
  
  /*
   销毁该链表,并释放内存空间
  */
  ~LinkList(){
   Node *p = head;
   while(p != NULL){
    head = head->next;
    delete p;
    p = head;
   }
  }
  /*
   将链表置为空表,并释放原链表结点的内存空间
  */
  void clear(){
   Node *p = head->next;
   while(p != NULL){
    head->next = p->next;
    delete p;
    p = head->next;
   }
  }
  
  
  /*
   将无素插入到第一个结点之前
  */
  void insertFirst(const T &e){
   Node *p = new Node(e);
   p->next = head->next;
   head->next = p;
  }
  
  /*
   将无素插入到最后一个结点之后
  */
  void insertLast(const T &e){
   Node *s = new Node(e);
   Node *p= head;
   while(p->next != NULL){
    p = p->next;
   } 
   p->next = s;  [Page]
  }
  
  /*
   在链表的第i个位置之前插入元素e
   前置条件:i大于0,小于l.length()+1
  */
  void insert(int index,const T &e){
   if(index < 1 || index > length()+1){
    cout << \"invalid index:\" << index;
    return;
   }
   Node *s = new Node(e);
   Node *p = head;
   int j = 1;
   while(j < index){
    p = p->next;
    j++;
   }
   
   s->next = p->next;
   p->next = s;
 
  }
  
 
  /*
   查找第元素e在链表中的位置,不存在,则返回-1
  */
  int indexOf(const T &e){
   int i=0;
   Node *p = head->next;
   while(p != NULL){
    i++;
    if(e == p->data){
     return i;
    }
    p = p->next;
   }
   return -1;
  }
  
  /*
   返回元素第一个结点的值
  */
  T getFrist(){
   if(head->next == NULL){
    cout << \"this  is a empty LinkList\" << endl;
    return -1;
   }
   return head->next->data;
  }
  
  /*
   返回元素最后一个结点的值
  */
  T getLast(){
   Node *p = head;

[NextPage]

 while(p->next != NULL){
    p = p->next;
   }
   return p->data;
  }
  /*
   返回链表从工作出发第一个结点开始,第index位置的元素值
  */
  T getElement(int index){
   if(index < 1 || index > length()+1){
    cout << \"invalid index:\" << index; [Page]
    throw \"erro\";
   }
   Node *p = head->next;
   int j = 1;
   while(j < index){
    p = p->next;
    j++;
   }
   return p->data;
  }
  
  /*
   删除所有结点值为e的所有结点
  */
  void removeAll(const T &e){
   Node *p = head;
   Node *q = head;
   while(p != NULL && p->next != NULL){
    q = p->next;
    if(e == q->data){
     p->next = q->next;
     delete q;
     continue;
    } 
    p = p->next;
   }
  }
  
  /*
   将所有结点值为e的结点的值替换为一个新值
  */
  void updateAll(const T &e,const T &ne){
   Node *p = head;
   Node *q = head;
   while(p != NULL && p->next != NULL){
    q = p->next;
    if(e == q->data){
     q->data = ne;
     continue;
    } 
    p = p->next;
   }
  }
  
  /*
   删除第一个值为e的结点
  */
  void remove(const T &e){
   Node *p = head;
   Node *q = head;
   while(p != NULL && p->next != NULL){
    q = p->next;
    if(e == q->data){
     p->next = q->next;
     delete q;
     return;
    } 
    p = p->next;
   }
  } 
   [Page]
  
  /*
   返回链表的长度
  */
  int length(){
   Node *p = head;
   int i = 0;
   while(p->next != NULL){
    p = p->next;
    i++;
   }
   return i;
  }
  
  /*
   打印链表的所有无素
  */
  void travel(){
   Node *p = head->next;
   if(p == NULL){
    cout<< \"has no items\" << endl;
   } 
   while(p != NULL){
    cout << p->data << ’ ’;
    p = p->next;
   }
   cout << endl;
  }
};
int main(){
 LinkList l;
 for(int i=1;i<=20;i++){
  //l.insertFirst(i);
  //l.insertLast(i);
  l.insert(i,i);
 }
 l.insert(15,15);
 l.insert(17,15);
 l.insert(8,15);
 l.travel();
 //cout << l.indexOf(15) << endl;
 // cout << l.getElement(0) << endl;
 l.updateAll(15,888);
 l.travel();
 cout << l.getLast() << endl;
 l.clear();
 l.travel();
 
 return 0;
}