Chinaunix首页 | 论坛 | 博客
  • 博客访问: 525216
  • 博文数量: 158
  • 博客积分: 4015
  • 博客等级: 上校
  • 技术积分: 1711
  • 用 户 组: 普通用户
  • 注册时间: 2009-01-27 14:00
文章分类

全部博文(158)

文章存档

2010年(71)

2009年(87)

我的朋友

分类: C/C++

2009-09-16 17:05:31

与上一个版本相比,修正了一些错误,提高了一些效率,可能还是会有些错误, 看到的朋友帮忙指出下。


#ifndef LIST_H
#define LIST_H
#include <iostream>
#include <cstddef>
#include <exception>
#include <stdexcept>
#include "Node.h"

template<class T>
class List {
  Node<T>* head;
  Node<T>* tail;
  int size;
 public:
  List();
  ~List();
  bool empty();
  T& front();
  T& back();
  void push_front(const T&);
  void pop_front();
  void push_back(const T&);
  void pop_back();
  void insert(int, const T&);
  void clear();
  int getSize();
  T& remove(int);
  void printAll();
};

template<class T>
List<T>::List() {
  head = tail = NULL;
  size = 0;
}
template<class T>
List<T>::~List() {
  clear();
}

template<class T>
bool List<T>::empty() {
  return (size == 0);
}

template<class T>
T& List<T>::front() {
  if(size == 0)
    throw std::logic_error("List is empty!");
  else
    return head->data;
}

template<class T>
T& List<T>::back() {
  if(size == 0)
    throw std::logic_error("List is empty!");
  else
    return tail->data;
}


template<class T>
void List<T>::push_front(const T& value) {
  Node<T>* tmp = new Node<T>(value, NULL);
  if(size == 0) {
    head = tail = tmp;
    size++;
  }
  else {
    tmp->next = head;
    head = tmp;
    size++;
  }
}

template<class T>
void List<T>::pop_front() {
  if(size == 0)
    throw std::logic_error("List is empty!");
  else if(size == 1) {
    head = tail = 0;
    delete head;
    size--;
  }
  else {
    Node<T>* tmp = head->next;
    delete head;
    head = tmp;
    size--;
  }
}

template<class T>
void List<T>::push_back(const T& value) {
  Node<T>* tmp = new Node<T>(value, NULL);
  if(size == 0) {
    head = tail = tmp;
    size++;
  }
  else {
    tail->next = tmp;
    tail = tmp;
    size++;
  }
}

template<class T>
void List<T>::pop_back() {
  if(size == 0)
    throw std::logic_error("You can't pop from a empty list!");
  else if(size == 1) {
    delete head;
    head = tail = 0;
    size--;
  }
  else {
    Node<T>* tmp = head;
    while(tmp->next != tail)
      tmp = tmp->next;
    tmp->next = 0;
    delete tail;
    tail = tmp;
    size--;
  }
}
template<class T>
void List<T>::insert(int k, const T& value) {
  if(size == 0) {
    if(k != 0)
      return;
    else {
      Node<T>* tmp = new Node<T>(value, 0);
      head = tail = tmp;
      size++;
    }
  }
  else {
    if(k < 0 || k > size)
      throw std::logic_error("out of range!");
    else {
      if(k == 0) {
    push_front(value);
      }
      else if(k == size) {
    push_back(value);
      }
      else {
    Node<T>* tmp = head->next;
    Node<T>* tmp_pre = head;
    int i = 1;
    while(i < k) {
     i++;
     tmp = tmp->next;
     tmp_pre = tmp_pre->next;
    }
    Node<T>* node = new Node<T>(value, 0);
    node->next = tmp;
    tmp_pre->next = node;
    size++;
      }
    }
  }
}

template<class T>
void List<T>::clear() {
    Node<T>* tmp = head;
    while(tmp != 0) {
      delete tmp;
      tmp = tmp->next;
    }
    size = 0;
}

template<class T>
int List<T>::getSize() {
  return size;
}

template<class T>
T& List<T>::remove(int k) {
  if(size == 0)
    throw std::logic_error("Can't remove from an empty list!");
  else if(size == 1) {
    if(k != 0) {
      throw std::logic_error("Remove from an unknown place!");
    }
    else {
      delete head;
      head = tail = 0;
      size--;
    }
  }
  else {
    if(k < 0 || k > size - 1)
      throw std::logic_error("Out of range!");
    else if(k == 0)
      pop_front();
    else if(k == size - 1)
      pop_back();
    else {
    Node<T>* tmp = head->next;
    Node<T>* tmp_pre = head;
    int i = 1;
    while(i < k) {
      i++;
      tmp = tmp->next;
      tmp_pre = tmp_pre->next;
    }
    tmp_pre->next = tmp->next;
    delete tmp;
    tmp = 0;
    size--;
    }
  }
}

template<class T>
void List<T>::printAll() {
  Node<T>* tmp = head;
  while(tmp != 0) {
    std::cout << tmp->data << ' ';
    tmp = tmp->next;
  }
}
#endif

阅读(790) | 评论(0) | 转发(0) |
0

上一篇:双链表的实现

下一篇:我写的双链表

给主人留下些什么吧!~~