投稿
  1. 高性能架构探索首页
  2. C/C++

C++有序双向链表

admin • • C/C++ • 阅读 236

1. 遍历的时候不只用value check， 还会用到address check

2. C++ 生成随机数

 

主要函数：

1. 在双向链表插入新节点

2. 计算双向链表中元素的总个数

2. 删除某个值的所有元素

3. 删除某个值的单个元素

4. 统计等于某个值的元素个数

 

此外有一个Output函数用来输出测试结果

头结点是head, 如为NULL则该双向链表为空

 

感悟：

觉得在处理特殊单个节点的情况比较麻烦，要额外考虑出来

此外，用地址检测来确认遍历一圈，而不是用值data来检测

 

代码（包括测试的main函数）：

 

[cpp] view plaincopy

  1. #include <iostream>  
  2. #include <ctime>  
  3. #include <cstdlib>  
  4. using namespace std;  
  5.   
  6. //Forward Declaration  
  7. template<class Type>  
  8. class DoubleLinkedList;  
  9.   
  10.   
  11. //Node with two pointers *next and *prev  
  12. template<class Type>  
  13. class Node{  
  14.     friend class DoubleLinkedList<Type>;  
  15. private:  
  16.     Type data;  
  17.     Node *next;  
  18.     Node *prev;  
  19. public:  
  20.     Type getData(){  
  21.         return data;  
  22.     }  
  23.     Node(): next(NULL),prev(NULL){}  
  24.     Node(const Type& data){  
  25.         Node::data = data;  
  26.         next = NULL;  
  27.         prev = NULL;  
  28.     }  
  29. };  
  30.   
  31. template<class Type>  
  32. class DoubleLinkedList{  
  33. private:  
  34.     Node<Type> *head;  
  35. public:  
  36.     DoubleLinkedList(): head(NULL){}  
  37.     DoubleLinkedList(Node<Type>* head){  
  38.         DoubleLinkedList::head = head;  
  39.         head->next = head;  
  40.         head->prev = head;  
  41.     }  
  42.     ~DoubleLinkedList();  
  43.     //Insert a new Node into the Double Linked List  
  44.     Node<Type>* Insert(const Type& data);  
  45.   
  46.     //Delete all elements equal @parameter data  
  47.     void DeleteAllElementsEqual(const Type& data);  
  48.   
  49.     //Delete one element equal @parameter data  
  50.     void DeleteOneElementEqual(const Type& data);  
  51.   
  52.     //Get Count Of Element equal @parameter data  
  53.     int GetCountOfElmentsEqual(const Type& data);  
  54.     int getSize();  
  55.     void Clear();  
  56.     void Output();  
  57. };  
  58.   
  59. template<class Type>  
  60. Node<Type>* DoubleLinkedList<Type>::Insert(const Type& data){  
  61.     if(head == NULL){  
  62.         DoubleLinkedList::head = new Node<Type>(data);  
  63.         head->next = head;  
  64.         head->prev = head;  
  65.         return head;  
  66.     }else{  
  67.         Node<Type> *currentNode = head;  
  68.         while(true){  
  69.             /* 
  70.              * if it traverses all the link , and has insert it in the last place 
  71.              * or,  finds the correct place to insert, 
  72.              * then create the new Node(data), 
  73.              * if new data smaller than the head , 
  74.              * then change the head pointer to the new inserted node 
  75.              */  
  76.             if(currentNode->next == head || currentNode->data == data ||  
  77.                     (currentNode->data < data && data < currentNode->next->data)){  
  78.                 Node<Type>* newNode = new Node<Type>(data);  
  79.                 newNode->next = currentNode->next;  
  80.                 currentNode->next = newNode;  
  81.                 //here we insert a new Node, but  
  82.                 //its next pointer has been already modified!  
  83.                 newNode->prev = currentNode;  
  84.                 newNode->next->prev = newNode;  
  85.                 if(newNode->data < head->data)  
  86.                     head = newNode;  
  87.                 return newNode;  
  88.             }  
  89.             currentNode = currentNode->next;  
  90.         }  
  91.     }  
  92. }  
  93.   
  94. template<class Type>  
  95. void DoubleLinkedList<Type>::Output(){  
  96.     cout << endl << "OUTPUT: " << endl;  
  97.     if(head == NULL){  
  98.         cout << "\nNULL LIST! " << endl;  
  99.         return;  
  100.     }  
  101.     Node<Type>* currentNode = head;  
  102.     //Sequential Traversal from head  
  103.     cout << "Sequential Traversal from head: " << endl;  
  104.     for(int i = 0;i < getSize();i++){  
  105.         cout << currentNode->data << ", ";  
  106.         currentNode = currentNode->next;  
  107.     }  
  108.     //Conversal Traversal from head  
  109.     currentNode = head;  
  110.     cout << endl << "Converse Traversal from head: " << endl;  
  111.     for(int i = 0;i < getSize();i++){  
  112.         cout << currentNode->data << ", ";  
  113.         currentNode = currentNode->prev;  
  114.     }  
  115.     cout << endl;  
  116. }  
  117.   
  118.   
  119. template<class Type>  
  120. int DoubleLinkedList<Type>::getSize(){  
  121.     int size = 0;  
  122.     if(head == NULL)  
  123.         return size;  
  124.     else{  
  125.         Node<Type> *currentNode = head;  
  126.         do{  
  127.             size++;  
  128.         }while((currentNode = currentNode->next) != head);  
  129.     }  
  130.     return size;  
  131. }  
  132.   
  133.   
  134. template<class Type>  
  135. void DoubleLinkedList<Type>::DeleteAllElementsEqual(const Type& data){  
  136.     if(head == NULL)  
  137.         return;  
  138.     Node<Type> *currentNode = head;  
  139.     //First, find the node whose value equal data  
  140.     bool isExisted = false;  
  141.     do{  
  142.         if(currentNode->data == data){  
  143.             isExisted = true;  
  144.             break;  
  145.         }  
  146.     }while((currentNode = currentNode->next) != head);  
  147.   
  148.     if(isExisted){  
  149.         while(currentNode->data == data){  
  150.             //only one node left  
  151.             if(currentNode == currentNode->next){  
  152.                 delete head;  
  153.                 head = NULL;  
  154.                 return;  
  155.             }  
  156.             //more than one node left  
  157.             Node<Type> *tempNode = currentNode;  
  158.             currentNode->prev->next = currentNode->next;  
  159.             currentNode->next->prev = currentNode->prev;  
  160.             currentNode = currentNode->next;  
  161.             delete tempNode;  
  162.         }  
  163.     }  
  164. }  
  165.   
  166.   
  167. template<class Type>  
  168. void DoubleLinkedList<Type>::DeleteOneElementEqual(const Type& data){  
  169.     if(head == NULL)  
  170.         return;  
  171.     Node<Type> *currentNode = head;  
  172.     bool isExisted = false;  
  173.     do{  
  174.         if(currentNode->data == data){  
  175.             isExisted = true;  
  176.             break;  
  177.         }  
  178.     }while((currentNode = currentNode->next) != head);  
  179.     if(isExisted){  
  180.         //only one node left  
  181.         if(currentNode == currentNode->next){  
  182.             delete head;  
  183.             head = NULL;  
  184.         }  
  185.         //More than one node left  
  186.         Node<Type> *tempNode = currentNode;  
  187.         currentNode->prev->next = currentNode->next;  
  188.         currentNode->next->prev = currentNode->prev;  
  189.         delete tempNode;  
  190.     }  
  191. }  
  192.   
  193.   
  194. template<class Type>  
  195. void DoubleLinkedList<Type>::Clear(){  
  196.     if(head == NULL)  
  197.         return;  
  198.     Node<Type> *currentNode = head;  
  199.     do{  
  200.         Node<Type> *tempNode = currentNode;  
  201.         currentNode = currentNode->next;  
  202.         delete tempNode;  
  203.     }while(currentNode != head);  
  204.     head = NULL;  
  205. }  
  206.   
  207.   
  208. template<class Type>  
  209. int DoubleLinkedList<Type>::GetCountOfElmentsEqual(const Type& data){  
  210.     int count = 0;  
  211.     Node<Type> *currentNode = head;  
  212.     do{  
  213.         if(currentNode->data == data)  
  214.             count++;  
  215.     }while((currentNode = currentNode->next) != head);  
  216.     return count;  
  217. }  
  218.   
  219.   
  220. template<class Type>  
  221. DoubleLinkedList<Type>::~DoubleLinkedList(){  
  222.     if(head == NULL)  
  223.         return;  
  224.     Node<Type> *currentNode = head->next;  
  225.     while(currentNode != head){  
  226.         Node<Type> *tempNode = currentNode;  
  227.         currentNode = currentNode->next;  
  228.         delete tempNode;  
  229.         tempNode = NULL;  
  230.     }  
  231.     delete head;  
  232.     head = NULL;  
  233. }  
  234.   
  235.   
  236.   
  237. //Test Main  
  238. int main() {  
  239.     DoubleLinkedList<int> *dList = new DoubleLinkedList<int>();  
  240.     cout << "RANDOM INPUT: " << endl;  
  241.     srand(unsigned(time(0)));  
  242.     for(int i = 0;i < 20;i++){  
  243.         int newNumber = rand() % 10;  
  244.         cout << dList->Insert(newNumber % 6)->getData() << " , ";  
  245.     }  
  246.     cout << "\nlist size: " << dList->getSize();  
  247.     dList->Output();  
  248.   
  249.     cout << endl << "Count Elements equal 1: ";  
  250.     cout << endl << "Number of All Elements equal 1: "  
  251.                     << dList->GetCountOfElmentsEqual(1) << endl;  
  252.   
  253.     cout << endl << "Delete One Elements equal 2: ";  
  254.     dList->DeleteOneElementEqual(2);  
  255.     cout << endl << "list size after Delete One Element: " << dList->getSize();  
  256.     dList->Output();  
  257.   
  258.     cout << endl << "Delete All Elements equal 3: ";  
  259.     dList->DeleteAllElementsEqual(3);  
  260.     cout << endl << "list size after Delete: " << dList->getSize();  
  261.     dList->Output();  
  262.   
  263.     cout << endl << "Clear List: ";  
  264.     dList->Clear();  
  265.     cout << endl << "list size after Clear: " << dList->getSize();  
  266.   
  267.     return 0;  
  268. }  

 

 

 

输出：

C++有序双向链表

 

 

原文链接: https://www.cnblogs.com/hktk/archive/2012/09/22/2698365.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

    C++有序双向链表

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/63444

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年2月9日 上午10:58
下一篇 2023年2月9日 上午10:58

相关推荐