对这道题目和我的数据结构课程致以最崇高的敬意。
样例输入：
int main() {
LinkedList<int> * list = new LinkedList<int>;
LinkedList<int> * stack = new Stack<int>;
LinkedList<int> * queue = new Queue<int>;
cout << "LinkedList" << endl;
list->pushFront(1);
list->pushBack(2);
list->pushBack(3);
list->pushFront(4);
list->print();
list->popFront();
list->popBack();
list->print();
cout << list->size() << endl;
cout << stack->name() << endl;
stack->push(1);
stack->push(2);
stack->push(3);
stack->push(4);
cout << stack->peak() << endl;
stack->pop();
cout << stack->pop() << endl;
cout << stack->peak() << endl;
cout << queue->name() << endl;
queue->push(1);
queue->push(2);
queue->push(3);
queue->push(4);
cout << queue->peak() << endl;
queue->pop();
cout << queue->pop() << endl;
cout << queue->peak() << endl;
delete list;
delete stack;
delete queue;
return 0;
}
样例输出：
LinkedList
4 1 2 3
1 2
2
Stack
4
3
2
Queue
1
2
3
AC代码：
#include<iostream>
#include<cstdio>
using namespace std;
template <class T>
class LinkedList{
private:
struct Node{
T data;
Node *next, *prev;
Node(const T &x){
data = x;
next = NULL;
prev = NULL;
}
};
protected:
Node *head;
Node *tail;
int length;//c++11以后才可以初始化
void clear(){
Node *p = head, *q;
while(p){
q = p->next;
delete p;
p = q;
//p = p->next ;这样写也不对啊！！因为p也被删了没有next啊
//head = head->next ; 这样写绝对不对啊！！！你的head在前面已经被删了哪来的next
}
length = 0;
head = NULL;
tail = NULL;
//这里不清干净的话，派生类clear完了回到父类里面head和tail还有值，导致delete多了，出错
}
public:
LinkedList(){
head = NULL;
tail = NULL;//还不涉及到插入特定位置，不太需要头尾结点
length = 0;
}
void pushFront(T k){
Node *tmp = new Node(k);
tmp->next = head;
if(head) head->prev = tmp;
head = tmp;
if(!tail) tail = head;
length++;
}
void pushBack(T k){
Node *tmp = new Node(k);
tmp->prev = tail;
if(tail) tail->next = tmp;
tail = tmp;
if(!head) head = tail;
length++;
}
T popFront(){
if(head){
if(head==tail) tail = NULL;
Node *tmp = head;
head = head->next ;
if(head) head->prev = NULL; //可以不写
length--;
T x = tmp->data ;
delete tmp;
// cout<<"pop"<<x<<endl; 测试用的输出记得删掉……
return x;
}
else return T();
}
T popBack(){
//注意！！！！当删到最后一个的时候，head=tail，如果只维护tail不管head会出错！
if(tail){
if(head==tail) head = NULL;
Node *tmp = tail;
tail = tail->prev;
if(tail) tail->next = NULL;
//不维护tail怎么行…… 后路要截断
length--;
T x = tmp->data;
delete tmp;
// cout<<"pop"<<x<<endl;
return x;
}
else return T();
}
int size(){
return length;
}
LinkedList(const LinkedList &x){
Node *q = x.head;
while(q){
pushBack(q->data);
q = q->next ;
}
length = x.length;//不要写成q.length...
}
void print(){
Node *q = head;
while(q){
cout<<q->data <<" ";
q = q->next;
}
cout<<endl;
}
virtual ~LinkedList(){
clear();
}
virtual const char *name(){//虚函数在父类里面必须实现（如果你定义了父类或子类的对象）
return (char *)("LinkedList");
}
virtual T peak(){
return head->data;
}
virtual T pop() {
return popFront();
}
virtual void push(T val){
pushFront(val);
}
};
template <class T>
class Stack:public LinkedList<T>{
public:
const char *name(){
return (char *)("Stack");
}
T peak(){
return this->head->data;
}
T pop(){
return LinkedList<T>::popFront();
}
void push(T k){
LinkedList<T>::pushFront(k);
return;
}
~Stack(){
// cout<<"Stack clear"<<endl;
LinkedList<T>::clear();
}
};
template <class T>
class Queue:public LinkedList<T>{
public:
const char *name(){
return (char *)("Queue");
}
T peak(){
return LinkedList<T>::head->data;
}
T pop(){
return LinkedList<T>::popFront();
}
void push(T k){
LinkedList<T>::pushBack(k);
return;
}
~Queue(){
// cout<<"Queue clear"<<endl;
LinkedList<T>::clear();
}
};
本题反思：
1、类模板的写法！哪里加template？哪里加T？
2、Node采用内嵌类的写法，成为LinkedList的private部分，内嵌类可以被继承，private继承的内嵌类自然无法访问，但protected和public是可以被继承的，在使用Node *p定义一个指针p的时候，要在前面加关键字typename（详情请见后续附上的实验）
3、Node类型的变量和指针其实没有必要被子类使用，因为可以在基类里面写好函数，子类直接调用就可以了（如clear()）
4、Clear()写的时候要注意！！！不可以用已经被delete掉的变量再来->next，因为根本无法这样做啊啊啊！思路要清晰！遍历可以就一个指针不停往后跑因为没有删除操作，但是clear和pop必须定义两个指针，为了保证你删完了还找得到后续的结点，否则删完了就是删完了，后面也找不到了
5、注意子类调用析构函数结束后，是会调用父类的析构函数的！所以你在写clear的时候一定要把head和tail置为0，否则第二次析构的时候会再次析构一遍，导致RE！！（应该是RE吗）
6、注意popFront()和popBack()！弹出结点的时候注意，只剩一个结点时的情况比其他更复杂一些！如果按照之前的操作，删头只改头，删尾只改尾，会导致删完头了tail还在，删完尾了head还在，导致“链删完后再压入，本该回到初始状态（head，tail都为0），但实际上却不一样了（有的不为0）”（如果你用length判断该链表是否为空，也许会更不容易出错一些，但是引入一个length进入考虑会增加思考的复杂程度（其实也不会））总之，再clear就完完全全地清空好了！回到原先的初始状态一模一样总不会出错
7、注意tail的维护！！！！特别是删了尾巴以后要加if(tail) tail->next=NULL;否则next还指着一个地址，输出的时候就会出错！
8、结构体指针要用->，不可以用.!!!
9、虚函数！在父类里面必须实现啊！！（如果你根本没定义该父类或子类的对象，另当别论，因为它根本没实例化，自然不需要涉及这些语句）纯虚函数不需要实现。
10、类模板作为基类：注意二段式查找相关的理论！类模板作为基类，在实例化之前，它的子类并不知道自己继承了什么，所以会把父类的内部成员看作非成员，所以会显示你使用的东西没有被定义。解决方法是：使用指针this->f();或指明A<T>::f(); 根据资料，还可以写using A<T>::f();记得带上模板<T>
11、提交前还是检查下哈……该删的要删！免得罚时太多还搞得心里不停自我怀疑……
12、该自己造数据就快点造！比较好的习惯是：读题仔细，每一步想清楚，不清楚的写下来不要埋地雷，写下来后动手演示画图演算不要对着屏幕空想，样例过了自己造点数据测试一下，提交前检查也没有多余输出。
其余实验及反思：
1、结构体Node不内嵌：放在外面，也是模板，全是public，使用时需要加上模板参数<T>
2、protected和public内嵌，以及类模板作为基类继承：
实验代码如下，实验结果如上所示
#include<iostream>
#include<cstdio>
using namespace std;
template<class T>
class A{
public://或protected
struct B{
T data;
};
protected:
T x;
};
template <class T>
class C:public A<T>{
A<T>::x; //可以编译但有warning
C:A<T>::x;//可以编译，无warning
//C():A<T>::x;//不可以编译
typename A<T>::B *p;//可以编译
//A<T>::B *p;不可以编译
};
int main(){
}