数据结构-单链表-类定义C++

原理可访问https://www.cnblogs.com/yang901112/p/11674333.html

头文件

 #ifndef RLIST_H

 #define RLIST_H

 #include <iostream>

 template <class T> class List;

 template <class T>

 class ListNode

 {

     friend class List<T>;

 public:

     ListNode() { next = ; }

     ListNode(T el, ListNode* ptr = ) {

         data = el; next = ptr;

     }

 private:

     T data;

     ListNode *next;

 };

 template <class T>

 class List

 {

 public:

     List() {

         head = ;

         head = tail = ; }

     ~List();

     int isEmpty() {

         return head == ;

     }

     void addToHead(T);  //从头插入结点

     void addToTail(T);  //从尾部插入节点

     void disPlay() const;

     T deleteFromHead();  //从头删除结点//若不需要返回值可以使用void

     T deleteFromTail();  //从尾部删除节点

     void deleteNode(T);  //按值删除结点

     bool isInList(T) const;  //判断值是否在链表里

     void Invert();  //反转链表

 private:

     ListNode<T> *head, *tail;

 };

 template <class T>

 List<T>::~List() {

     for (ListNode<T> *p; !isEmpty();) {

         p = head->next;

         delete head;

         head = p;

     }

 }

 template <class T>

 void List<T>::addToHead(T el) {

     head = new ListNode<T>(el, head);

     if (tail == )

         tail = head;

 }

 template <class T>

 void List<T>::addToTail(T el) {

     if (tail != ) {

         tail->next = new ListNode<T>(el);

         tail = tail->next;

     }

     else head = tail = new ListNode<T>(el);

 }

 template <class T>

 T List<T>::deleteFromHead() {

     T el = head->data;

     ListNode<T> *tmp = head;

     if(head==tail)

     {

         head = tail = ;

     }

     else head = head->next;

     delete tmp;

     return el;

 }

 template <class T>

 T List<T>::deleteFromTail() {

     T el = tail->data;

     if(head==tail)

     {

         delete head;

         head = tail = ;

     }

     else {

         ListNode<T> *tmp;

         for (tmp = head; tmp->next != tail; tmp = tmp->next);

         delete tail;

         tail = tmp;

         tail->next = ;

     }

     return el;

 }

 template <class T>

 void List<T>::deleteNode(T el) {

     ListNode<T> *previous = ;

     ListNode<T> *current;

     for (current = head; current && current->data != el;

         previous = current, current = current->next);

     if (current)

     {

         if (previous) { previous->next = current->next; }

         else head = head->next;

         delete current;

     }

 }

 /*****************************************/

 //template <class T>

 //bool List<T>::isInList(T el) const {

 //    bool flag = false;

 //    ListNode<T> *tmp;

 //    tmp = head->next;

 //    while (tmp) {

 //        if (tmp->data == el) {

 //            flag = true;

 //            break;

 //        }

 //        tmp = tmp->next;

 //    }

 //    return flag;

 //}

 //可以使用for循环代替while代码可以简洁一些

 template <class T>

 bool List<T>::isInList(T el) const {

     ListNode<T> *tmp;

     for (tmp = head; tmp && tmp->data != el; tmp = tmp->next);

     return tmp != ;

 }

 /*****************************************/

 template <class T>

 void List<T>::Invert() {

     ListNode<T> *p = head, *q = ;

     while (p)

     {

         ListNode<T> *r = q; q = p;

         p = p->next;

         q->next = r;

     }

     head = q;

 }

 template <class T>

 void List<T>::disPlay() const{

     //ListNode<T>  *p;

     //p = head;

     //while (p)

     //{

     //    std::cout << p->data;

     //    if (p->next) { std::cout << "->"; } //就是仅在数字之间加"->"

     //    p = p->next;

     //}

     for (ListNode<T> *current = head; current; current = current->next)

     {

         std::cout << current->data;

         if (current->next) std::cout << "->";

     }

     std::cout << std::endl;

 }

 #endif

源文件

 #include <iostream>

 #include"Rlist.h"

 #include <iomanip>

 using namespace std;

 int main()

 {

     cout << "测试" << endl;

     List<int> ilist;

     ilist.addToTail();

     ilist.addToTail();

     ilist.addToTail();

     ilist.addToTail();

     ilist.disPlay();

     ilist.deleteFromHead();

     ilist.disPlay();

     List<int> ilist2;

     ilist2.addToHead();

     ilist2.addToHead();

     ilist2.addToHead();

     ilist2.addToHead();

     ilist2.disPlay();

     cout << ilist2.isInList() << endl;

     ilist2.deleteFromTail();

     ilist2.disPlay();

     cout << ilist2.isInList() << endl;

     List<char> charlist1;

     charlist1.addToTail('a');

     charlist1.addToTail('b');

     charlist1.addToTail('c');

     charlist1.addToTail('d');

     charlist1.disPlay();

     charlist1.Invert();

     charlist1.disPlay();

     charlist1.deleteNode('c');

     charlist1.disPlay();

     charlist1.deleteNode('e'); //虽然'e'不存在，但是不影响

     charlist1.disPlay();

     return ;

 }