数据结构-双链表与循环链表

      由于之前写作业时没有把几个项目分开，所以Node.cpp修改过多次，所以在这里统一一下，涉及到get和set方法中带getprior的，Node.cpp就是有两个指针，没有prior相关方法的Node.cpp就是只有一个指针。
      Node.cpp

template<typename T>
class Node {
public:
	Node() {}
	Node(T data, Node<T> *nextptr, Node<T> *priorptr) :data(data), next(nextptr), prior(priorptr) {
	}
	~Node() {}
	T getData();
	void setData(T newData);
	Node<T> *getNext();
	void setNext(Node<T> *ptr);
	Node<T> *getPrior();
	void setPrior(Node<T> *priorptr);
private:
	T data;
	Node<T> *next;
	Node<T> *prior;
};
template<typename T>
T Node<T>::getData() {
	return data;
}
template<typename T>
void Node<T>::setData(T newData) {
	data = newData;
}
template<typename T>
Node<T> *Node<T>::getNext() {
	return next;
}
template<typename T>
void Node<T>::setNext(Node<T> *ptr) {
	next = ptr;
}
template<typename T>
Node<T> *Node<T>::getPrior() {
	return prior;
}
template<typename T>
void Node<T>::setPrior(Node<T> *priorptr) {
	prior = priorptr;
}

      DulList.cpp

#include"Node.cpp"
#include<iostream>
template<typename T>
class DulList {
public:
	DulList();
	DulList(T array[], int n);
	~DulList();
	Node<T> *getFirst() { return first; }
	void printList();
	void printListReverse();
private:
	Node<T> *first;
};
template<typename T>
DulList<T>::DulList() {
	first = new Node<T>;
	first->setNext(first);
	prior->setPrior(first);
}
template<typename T>
DulList<T>::DulList(T array[], int n) {
	first = new Node<T>;
	Node<T> *p = first;
	p->setNext(NULL);
	p->setPrior(NULL);
	Node<T> *q;
	for (int i = 0; i < n; i++) {
		q = new Node<T>;
		q->setData(array[i]);
		p->setNext(q);
		q->setPrior(p);
		p = q;
	}
	p->setNext(first);
	first->setPrior(p);
}
template<typename T>
DulList<T>::~DulList() {
	Node<T> *p = first;
	Node<T> *q;
	while (p->getNext() != first) {
		q = p->getNext();
		delete p;
		p = q;
	}
}
template<typename T>
void DulList<T>::printList() {
	Node<T> *p = first->getNext();
	while (p != first) {
		cout << p->getData() << " ";
		p = p->getNext();
	}
	cout << endl;
}
template<typename T>
void DulList<T>::printListReverse() {
	Node<T> *p = first->getPrior();
	while (p != first) {
		cout << p->getData() << " ";
		p = p->getPrior();
	}
	cout << endl;
}

      CycleLinkList.cpp

#include<iostream>
#include"Node.cpp"
template<typename T>
class CycleLinkList {
public:
	CycleLinkList();
	CycleLinkList(T array[], int length);
	~CycleLinkList();
	void printList();
	void add(T data);
private:
	Node<T> *first;
};
template<typename T>
CycleLinkList<T>::CycleLinkList() {
	first = new Node<T>;
	first->setNext(NULL);
}
template<typename T>
CycleLinkList<T>::CycleLinkList(T array[], int length) {
	first = new Node<T>;
	first->setNext(NULL);
	Node<T> *p, *q;
	p = first;
	for (int i = 0; i < length; i++) {
		q = new Node<T>;
		q->setData(array[i]);
		p->setNext(q);
		p = q;
	}
	//循环单链表指针
	p->setNext(first);
}
template<typename T>
CycleLinkList<T>::~CycleLinkList() {
	Node<T> *p = first->getNext();
	Node<T> *q;
	if (p == NULL) {
		return;
	}
	else {
		while (p != first) {
			q = p->getNext();
			delete p;
			p = q;
		}
	}
}
template<typename T>
void CycleLinkList<T>::printList() {
	Node<T> *p = first->getNext();
	Node<T> *q;
	if (p == NULL) {
		cout << "空链表！" << endl;
	}
	else {
		while (p != first) {
			q = p->getNext();
			cout << p->getData() << " ";
			p = q;
		}
		cout << endl;
	}
}
template<typename T>
void CycleLinkList<T>::add(T data) {
	Node<T> *p = first->getNext();
	//新节点
	Node<T> *s;
	s = new Node<T>;
	s->setData(data);
	if (p == NULL) {
		first->setNext(s);
		s->setNext(first);
		return;
	}
	while (p->getNext() != first) {
		p = p->getNext();
	}
	s->setNext(first);
	p->setNext(s);
}