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

全部博文(158)

文章存档

2010年(71)

2009年(87)

我的朋友

分类: C/C++

2009-09-15 12:14:14

哎,问题太多, 我得重写它, 使它更有效率, 准备基本实现标准库的list
Node.h

#ifndef NODE_H
#define NODE_H

template <class T>
class Node {
 public:
T data;
 Node<T>* next;
  Node() {
    next = 0;
  }
  Node(const T& item, Node<T>* pNext = 0)
    : data(item), next(pNext) {}
};
#endif


        

myList.h

#include "Node.h"
#include <cstddef>
#ifndef MYLIST_H
#define MYLIST_H

template<class T>
class myList {
  Node<T>* head;
  Node<T>* tail;
 public:
  myList() {
    head = tail = 0;
  }
  ~myList();
  bool empty() {
    return head == 0;
  }
  T& front();
  T& back();
  void push_front(const T&);
  void pop_front();
  void push_back(const T&);
  void pop_back();
  void insert(const T&, const T&);
  void clear();
  T& remove(const T&);
  void printAll();
  size_t size();
};
#endif

myList.cpp实现文件:

#include <iostream>
#include <exception>
#include <stdexcept>
#include "myList.h"
using namespace std;

template<class T>
myList<T>::~myList() {
  if(empty())
    return;
  else if(head == tail) {
    delete head;
    head = tail = 0;
  }
  else {
    while(!empty()) {
      Node<T>* p = head->next;
      delete head;
      head = p;
    }
  }
}

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

template<class T>
void myList<T>::push_front(const T& value) {
  if(empty())
    head = new Node<T>(value, 0);
  else if(head == tail) {
    Node<T>* p = new Node<T>(value, 0);
    p->next = head;
    head = p;
  }
  else {
    Node<T>* p = new Node<T>(value, 0);
    p->next = head;
    head = p;
  }
}

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

template<class T>
void myList<T>::push_back(const T& value) {
  if(empty()) {
    Node<T>* p = new Node<T>(value, 0);
    head = tail = p;
  } else if(head == tail) {
    Node<T>* p = new Node<T>(value, 0);
    tail->next = p;
    tail = p;
  } else {
    Node<T>* p = new Node<T>(value, 0);
    tail->next = p;
    tail = p;
  }
}

template<class T>
void myList<T>::pop_back() {
  if(empty())
    throw logic_error("List is empty!");
  else if(head == tail) {
    delete tail;
    head = tail = 0;
  }
  else {
    Node<T>* p = head;
    while(p->next != tail) {
      p = p->next;
    }
    delete tail;
    tail = p;
  }
}

template<class T>
void myList<T>::insert(const T& ex, const T& value) {
  if(empty())
      throw logic_error("you can't add an value before another value"
            "when the list is empty!");
  else if(head == tail) {
    Node<T>* p = new Node<T>(value, 0);
    if( ex == head->data) {
      p->next = head;
      head = p;
    } else
      throw logic_error("can't find the element!");
  } else {
  Node<T>* p = new Node<T>(value, 0);
  Node<T>* tmp = head->next;
  Node<T>* pre = head;
  while(tmp != 0 && tmp->data != ex) {
    tmp = tmp->next;
    pre = pre->next;
  }
  p->next = tmp;
  pre->next = p;
 }
}

template<class T>
void myList<T>::clear() {
  if(empty())
    return;
  else if(head == tail) {
    delete head;
    head = tail = 0;
  }
  else {
    Node<T>* p = head;
    while(p != 0) {
      delete p;
      p = 0;
    }
  }
}

template<class T>
T& myList<T>::remove(const T& ex) {
  if(empty())
    throw logic_error("you can't remove an"
         "element from an empty list");
  else if(head == tail) {
    delete head;
    head = tail = 0;
  }
  else {
    Node<T>* tmp = head->next;
    Node<T>* pre = head;
    while(tmp != 0 && tmp->data != ex) {
      tmp = tmp->next;
      pre = pre->next;
    }
    if(tmp == tail) {
      delete tail;
      tail = pre;
    } else {
      pre->next = tmp->next;
      delete tmp;
      tmp = 0;
    }
  }
}

template<class T>
void myList<T>::printAll() {
  if(empty())
    return;
  else {
    Node<T>* iterator = head;
    while(iterator != 0) {
      cout << iterator->data << ' ';
      iterator = iterator->next;
    }
  }
}

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

上一篇:ftp有关设定

下一篇:双链表的实现

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