Data-Structure2

Before: JaneZ非常讨厌LinkList，but: 厌即是恋（ 过年精神状态真是越来越好了，喝点儿中药吧 ）

Data Structure 2 链表 LinkList

线性链表的链接存储

• 链接存储通过让每个结点保存与它有关系的结点的地址来保存结点之间的关系
• 线性表的链接存储是指将每个数据元素存放在一个独立的数据存储单元（结点）中
• 链表不需要事先准备空间，一般采用动态存储的方法

单链表

• 每个结点存储一个数据元素和一个后继指针
  
• 为防止忘记处理特殊情况，可以引入一个不存放数据的特殊结点——头结点（一种优化）
  

单链表的定义

template<class elemType>
class sLinkList: public list <elemType>{
private:
    struct node{
        elemType data;
        node *next;

        node(const elemType& x , node *n = nullptr){
            data = x;
            next = n;
        }
        node():next(nullptr){}
        ~node(){}
    };
node *head;
int currentLength;
node *move(int i)const;

public:
    sLinkList();
    ~sLinkList(){
        clear();
        delete head;
    }
    void clear();
    int length() const{
        return currentLength;
    }
    void insert(int i , const elemType &x);
    void remove(int i);
    int search(const elemType &x)const;
    elemType visit(int i) const;
    void traverse() const;
};

单链表的运算实现

• 私有成员函数move的实现

  template<class elemType>
  sLinkList<elemType>::node *sLinkList<elemType>::move(int i) const{
      node *p = head;
      while( i -- >= 0){
          p = p->next;
      }
      return p;
  }

• 单链表构造函数

  template<class elemType>
  sLinkList<elemType>::sLinkList(){
      head = new node;
      currentLength = 0;
  }

• 单链表清空函数
  

  template<class elemType>
  void sLinkList<elemType>::clear(){
      node *p = head->next;
      node *q;
      head -> next = nullptr;
      while(p != nullptr){
          q = p -> next;
          delete p;
          p = q;
      }
      currentLength = 0;
  }

• 单链表插入删除函数
  

  template<class elemType>
  void sLinkList<elemType>::insert(int i ,const elemType &x){
      node *pos;
      pos = move(i - 1);
      pos -> next = new node(x ,pos -> next);
      ++ currentLength;
  }

  template<class elemType>
  void sLinkList<elemType>::remove(int i){
      node *pos;
      node *delp;
      pos = move(i - 1);
      delp = pos -> next;
      pos -> next = delp -> next;
      delete delp;
      -- currentLength;
  }

• 单链表search visit traverse函数的实现

  template<class elemType>
  int sLinkList<elemType>::search(const elemType &x) const{
      node *p = head -> next;
      int i = 0 ;
      while(p != nullptr && p -> data != x){
          p = p -> next;
          ++ i;
      }
      if(p != nullptr){
          return i;
      }else{
          return -1;
      }
  }

  template<class elemType>
  elemType sLinkList<elemType>::visit(int i) const{
      return move(i) -> data;
  }

  template<class elemType>
  void sLinkList<elemType>::traverse() const{
      node *p = head -> next;
      while(p != nullptr){
          cout << p -> data <<" ";
          p = p -> next;
      }
      cout << endl;
  }

JaneZ发烧了，各位注意身体啊!