与上一个版本相比,修正了一些错误,提高了一些效率,可能还是会有些错误, 看到的朋友帮忙指出下。
#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) |