c++线性表实现（链式）

//编写本文中遇到的困难： //将类的声明放到list.h中，定义放在list.cpp中，运行时一直说找不到list，为什么呢？ //因为，用到了template，不支持分离式编译，所以把声明和定义全部写在了list.h中，问题解决。 /*----------node.h----------------*/ template<typename T> class Node { public: T data; Node *next; }; /*----------list.h----------------*/#include"node.h"#include<iostream>template<class T>class list{public: list(); ~list(); void push_back(const T data);//从后面插入元素 void push_front(const T data);//从前面插入元素 void printList() const; //打印线性表 void remove(const T data);//移除值为data的所有元素 int getLength() const //获取线性表的长度 { return length; } bool isEmpty() //判断是否为空 { if(length==0)return true; else return false; } T front() const //获取第一个元素的值 { return head->data; } T back() const //获取最后一个元素的值 { return tail->data; }private: Node<T> *head; Node<T> *tail; int length;};template<class T>list<T>::list(){ head = NULL; tail = NULL; length = 0;}template<class T>list<T>::~list(){ Node<T> *temp = new Node<T>; temp = head; while(temp!=NULL) { head = head->next; delete temp; temp = head; } delete temp; temp = NULL;}template<class T>void list<T>::push_back(const T data){ Node<T> *temp = new Node<T>; //创建一个临时结点，值为data，下一个结点设为NULL； temp->data = data; temp->next = NULL; if(head==NULL) //如果是第一个结点 { head = temp; tail = temp; } else { tail->next = temp; //先将结点接在tail后面，然后将tail指向他（不可颠倒） tail = temp; } length = length + 1; temp = NULL; //防止指针乱飞}template<class T>void list<T>::push_front(const T data){ Node<T> *temp = new Node<T>;//创建一个临时结点，值为data，下一个结点为head； temp->data = data; temp->next = head; head = temp; //将head指针指向temp，现在temp的位置为第一个结点 length = length + 1; delete temp; temp=NULL;}template<class T>void list<T>::printList() const{ if(head==NULL) { std::cout<<"空表"<<std::endl; return; } Node<T> *temp = new Node<T>; temp = head; while(temp!=NULL) { std::cout<<temp->data<<" "; temp = temp->next; } std::cout<<std::endl;} //如果A结点的值等于data，应该让A的前一个结点的next指向A的下一个结点，涉及三个结点，判断中间那个，所以我们先从头判断//如果head的值就等于data，就让head后移，并删除之前head结点，一直找到值不等于data的结点//这样我们确保三个结点中的第一个结点不等于data，接下来开始判断中间结点template<class T>void list<T>::remove(const T data){ if(length==0) { std::cout<<"空表"<<std::endl; return; } Node<T> *temp = new Node<T>; Node<T> *temp2 = new Node<T>; while(head!=NULL&&head->data==data) { temp = head; head = head->next; delete temp; length--; } if(head==NULL) { tail=NULL; return; } temp = head;//值一定不等于data temp2=temp->next;//接下来所要判断的结点 while(temp2!=NULL) { if(temp2->data==data) { temp->next = temp2->next; delete temp2; temp2 = temp->next; length--; } else { temp = temp->next; temp2 =temp2->next; } } temp = NULL; temp2 = NULL;} /*-------------主函数测试----------------*/ int main(){ list<int> L ; for(int i =0;i<10;i++) L.push_back(1); L.printList(); cout<<L.getLength()<<endl; L.remove(1); L.printList(); return 0;}