//【数据结构】用C++实现单循环链表的各种操作（包括头删，尾删，插入，逆序，摧毁，清空等等）

//头文件

#ifndef _CDLIST_H
#define _CDLIST_H


#include
  
   
using namespace std;


template
   
     class CDList; template
    
      class ListNode { friend class CDList
     
      ; public: ListNode() :data(Type()), next(NULL), prio(NULL) {} ListNode(Type d, ListNode
      
        *n = NULL, ListNode
       
         *m = NULL) :data(d), next(n), prio(m) {} ~ListNode() {} private: Type data; ListNode
        
          *next; ListNode
         
           *prio; }; template
          
            class CDList { public: CDList() { first = last = Buynode(); last->next = first; first->prio = last; } ~CDList() { destroy(); } public: void push_back(const Type &x) //尾插`` { ListNode
           
             *s = Buynode(x); last->next = s; s->prio = last; s->next = first; first->prio = s; last = s; first->data++; } void push_front(const Type &x) //头插`` { if (first->data == 0) { push_back(x); return; } ListNode
            
              *s = Buynode(x); s->next = first->next; first->next->prio = s; first->next = s; s->prio = first; first->data++; } void pop_back() //尾删`` { if (first->data == 0) return; ListNode
             
               *p = last; last = last->prio; last->next = first; first->prio = last; delete p; first->data--; } void pop_front() //头删`` { if (first->data == 0) { return; } else { ListNode
              
                *s = first->next; if (first->data == 1) { last = first; last->next = first; first->prio = last; } else { first->next = s->next; s->next->prio = first; } delete s; first->data--; } } void insert_val(const Type &x) //按值插入`` { ListNode 
               
                 *p = Buynode(x); ListNode 
                
                  *s = first; if (first->data == 0) { push_back(x); return; } while (s->next->data
                 
                  next->next != first) { s = s->next; } if (s->next->next == first) { if (s->next->data>x) { p->next = s->next; s->next->prio = p; s->next = p; p->prio = s; first->data++; } else push_back(x); } else { p->next = s->next; s->next->prio = p; s->next = p; p->prio = s; first->data++; } } void show_list() //显示`` { if (first->data == 0) { cout << "NULL" << endl; return; } ListNode
                  
                    *q = first->next; while (q != first) { cout << q->data << "->"; q = q->next; } cout << "NULL first->data=" << first->data << " last->next->data=" << last->next->data << " last->data=" << last->data << " first->prio->data=" << first->prio->data << " " << endl; } void sort() //排序`` { if (first->data == 0) { return; } ListNode
                   
                     *p = first->next; ListNode
                    
                      *q = p->next; p->next = first; first->prio = p; last = p; first->data = 1; ListNode
                     
                       *r; while (q != first) { insert_val(q->data); r = q; q = q->next; delete r; } } ListNode
                      
                       * find(const Type &x) //查找`` { ListNode
                       
                         *s; for (s = first->next; s != first; s = s->next) { if (s->data == x) { return s; } } return NULL; } int length() //求长度`` { return(first->data); } void delete_val(const Type &x) //按值删除`` { if (first->data == 0) { cout << "未找到该数：" << endl; return; } else { ListNode
                        
                          *p = find(x); if (p == NULL) { cout << "未找到该数：" << endl; return; } ListNode
                         
                           *q = first; while (q->next != p) { q = q->next; } if (q->next->next == first) { pop_back(); } else { q->next = p->next; p->next->prio = q; delete p; first->data--; } } } void clear() //清除`` { if (first->data == 0) return; while (first->next != first) { pop_back(); } } void resver() //逆序`` { if (first->data == 0) { return; } ListNode
                          
                            *p = first->next; ListNode
                           
                             *q = p->next; p->next = first; first->prio = p; last = p; first->data = 1; ListNode
                            
                              *r; while (q != first) { push_front(q->data); r = q; q = q->next; delete r; } } void quit_system(int &a) //退出`` { clear(); a = 0; } void destroy() //摧毁`` { clear(); delete first; } protected: ListNode
                             
                              * Buynode(Type x = Type()) { ListNode
                              
                                *p = new ListNode
                               
                                (x); return p; } private: ListNode
                                
                                  *first; ListNode
                                 
                                   *last; }; #endif //主函数 #include"CDList.h" void main() { CDList
                                  
                                    mylist; int select = 1; int Item; while (select) { cout << "**************************************" << endl; cout << "* [1] show_list [2] push_front *" << endl; cout << "* [3] push_back [4] pop_front *" << endl; cout << "* [5] pop_back [6] insert_val *" << endl; cout << "* [7] find [8] delete_val *" << endl; cout << "* [9]length [10] clear *" << endl; cout << "* [11] quit_system [12] destroy *" << endl; cout << "* [13] resver [14] sort *" << endl; cout << "**************************************" << endl; cout << "请选择:>"; cin >> select; switch (select) { case 1: mylist.show_list(); break; case 2: cout << "请输入要插入的值(-1结束):>"; while (cin >> Item, Item != -1) { mylist.push_front(Item); } break; case 3: cout << "请输入要插入的值(-1结束):>"; while (cin >> Item, Item != -1) { mylist.pus