阿洲程式天地

#include <iostream>

#include <cstdlib>

template<class ElemType>

struct ForwardListNode {

  ElemType                   data;     

  ForwardListNode<ElemType> *link;     

};

template<class ElemType>

class ForwardList {

  typedef ForwardListNode<ElemType> Node;

 public:

  ForwardList() {

    size_ = 0;

    head_ = NULL;

  }

  explicit ForwardList(int n);

  ~ForwardList();

  int Size() const { return size_; }

  ElemType &At(int i);

  const ElemType &At(int i) const;

  void PushFront(const ElemType &elem);

  void PopFront();

  void Insert(int pos, const ElemType &elem);

  void Erase(int pos);

  ElemType &operator[](int i)             { return At(i); }

  const ElemType &operator[](int i) const { return At(i); }

  bool Empty() const;

  void Clear();

private:

  int size_;

  Node *head_; 

};

template<class ElemType>

ForwardList<ElemType>::ForwardList(int n) {

  size_ = n;

  head_ = n == 0 ? NULL : new Node();

  Node *cur = head_;

  for (int i = 1; i < n; ++i) {

    cur->link = new Node();

    cur = cur->link;

  }

  cur->link = 0;

}

template<class ElemType>

ForwardList<ElemType>::~ForwardList() {

  Node *cur = head_;

  while (cur != NULL) {

    Node *del = cur;

    cur = cur->link;

    delete del;

  }

}

template<class ElemType>

ElemType &ForwardList<ElemType>::At(int i) {

  return (ElemType&)((const ForwardList *)this)->At(i);

}

template<class ElemType>

const ElemType &ForwardList<ElemType>::At(int i) const {

  Node *cur = head_;

  for (int k = 0; k < i; ++k) {

    cur = cur->link;

  }

  return cur->data;

}

template<class ElemType>

void ForwardList<ElemType>::PushFront(const ElemType &elem) {

  Node *ins = new Node();

  ins->data = elem;

  ins->link = head_;

  head_ = ins;

  size_++;

}

template<class ElemType>

void ForwardList<ElemType>::PopFront() {

  Node *del = head_;

  head_ = head_->link;

  delete del;

  size_--;

}

template<class ElemType>

void ForwardList<ElemType>::Insert(int pos, const ElemType &elem) {

  if (pos == 0) {

    Node *ins = new Node();

    ins->data = elem;

    ins->link = head_;

    head_ = ins;

  } else {

    Node *p = head_;

    for (int i = 0; i < pos - 1; ++i) { p = p->link; } 

    Node *ins = new Node();

    ins->data = elem;

    ins->link = p->link;

    p->link = ins;

  }

  ++size_;

}

template<class ElemType>

void ForwardList<ElemType>::Erase(int pos) {

  if (pos == 0) {

    Node *del = head_;

    head_ = head_->link;

    delete del;

  } else {

    Node *p = head_;

    for (int i = 0; i < pos - 1; ++i) { p = p->link; }

    Node *del = p->link;

    p->link = del->link;

    delete del;

  }

  --size_;

}

template<class ElemType>

std::ostream &operator<<(std::ostream &lhs, const ForwardList<ElemType> &rhs) {

  for (int i = 0; i < rhs.Size(); ++i) {

    if (i > 0) { lhs << " "; }

    lhs << rhs[i];

  }

  return lhs;

}

template<class ElemType>

bool ForwardList<ElemType>::Empty() const {

  if(head_==NULL)

    return true;

  else

     return false;

}

void ForwardList<ElemType>::Clear() {

  if(size_>0) {

     Node *p = head_;

    while(p!=NULL){

       Node *ins = p;

       p = p->link;

       delete ins;

     }

     size_ = 0;

     head_ = NULL;

  }

  else {

    head_ = NULL;

  }

}