您的位置: 首页  >  文章  >  （C++版）链表（四）——实现双向循环链表创建、插入、删除等简单操作

（C++版）链表（四）——实现双向循环链表创建、插入、删除等简单操作

分类: 文章 • 2024-08-05 19:31:28

http://blog.****.net/fisherwan/article/details/25649271

 链表（四）实现双向循环链表简单操作，代码如下：

[cpp] view plain copy
  1. <span style="font-size:18px;" deep="5">#include <iostream>  
  2. #include <stdlib.h>  
  3. using namespace std;  
  4.   
  5. //结点类  
  6. class Node {  
  7. public:  
  8.     int data;  
  9.     Node *pPre, *pNext;  
  10. };  
  11.   
  12. //双向循环链表类  
  13. class DoubleCircularLinkList {  
  14. public:  
  15.     DoubleCircularLinkList() {  
  16.         head = new Node;  
  17.         head->data = 0;  
  18.         head->pNext = head;  
  19.         head->pPre = head;  
  20.     }  
  21.     ~DoubleCircularLinkList() {delete head;}  
  22.     void CreateLinkList(int n);  
  23.     void InsertNode(int position, int d);  
  24.     void TraverseLinkList();  
  25.     bool IsEmpty();  
  26.     int GetLength();  
  27.     void DeleteNode(int posiiton);  
  28.     void DeleteLinkList();  
  29. private:  
  30.     Node *head;  
  31. };  
  32.   
  33. void DoubleCircularLinkList::CreateLinkList(int n) {  
  34.     if (n < 0) {  
  35.         cout << "输入结点个数错误！" << endl;  
  36.         exit(EXIT_FAILURE);  
  37.     }  
  38.     else {  
  39.         int i = 0;  
  40.         Node *pnew, *ptemp;  
  41.         ptemp = head;  
  42.         i = n;  
  43.   
  44.         while (n-- > 0) {  
  45.             pnew = new Node;  
  46.             cout << "输入第" << i - n << "个结点：";   
  47.             cin >> pnew->data;  
  48.             pnew->pNext = head;  
  49.             pnew->pPre = ptemp;  
  50.             ptemp->pNext = pnew;  
  51.             ptemp = pnew;  
  52.         }  
  53.     }  
  54. }  
  55.   
  56. void DoubleCircularLinkList::InsertNode(int position, int d) {  
  57.     if (position < 0 || position > GetLength() + 1) {  
  58.         cout << "输入位置错误！" << endl;  
  59.         exit(EXIT_FAILURE);  
  60.     }  
  61.     else {  
  62.         Node *pnew, *ptemp;  
  63.         pnew = new Node;  
  64.         pnew->data = d;  
  65.         ptemp = head;  
  66.         while (position-- > 1)  
  67.             ptemp = ptemp->pNext;  
  68.         pnew->pNext = ptemp->pNext;  
  69.         pnew->pPre = ptemp;  
  70.         ptemp->pNext = pnew;  
  71.         ptemp = pnew;  
  72.     }  
  73. }  
  74.   
  75. void DoubleCircularLinkList::TraverseLinkList() {  
  76.     Node *ptemp = head->pNext;  
  77.     while(ptemp != head) {  
  78.         cout << ptemp->data << " ";  
  79.         ptemp = ptemp->pNext;  
  80.     }  
  81.     cout << endl;  
  82. }  
  83.   
  84. bool DoubleCircularLinkList::IsEmpty() {  
  85.     if (head == head->pNext)  
  86.         return true;  
  87.     else  
  88.         return false;  
  89. }  
  90.   
  91. int DoubleCircularLinkList::GetLength() {  
  92.     int n = 0;  
  93.     Node *ptemp = head->pNext;  
  94.     while (ptemp != head) {  
  95.         n++;  
  96.         ptemp = ptemp->pNext;  
  97.     }  
  98.     return n;  
  99. }  
  100.   
  101. void DoubleCircularLinkList::DeleteNode(int position) {  
  102.     if (position < 0 || position > GetLength()) {  
  103.         cout << "输入位置错误！" << endl;  
  104.         exit(EXIT_FAILURE);  
  105.     }  
  106.     else {  
  107.         Node *pdelete, *ptemp;  
  108.         ptemp = head;  
  109.         while (position-- > 1)  
  110.             ptemp = ptemp->pNext;  
  111.         pdelete = ptemp->pNext;  
  112.         ptemp->pNext = pdelete->pNext;  
  113.         pdelete->pNext->pPre = ptemp;  
  114.         delete pdelete;  
  115.         pdelete = NULL;  
  116.     }  
  117. }  
  118.   
  119. void DoubleCircularLinkList::DeleteLinkList() {  
  120.     Node *pdelete, *ptemp;  
  121.     pdelete = head->pNext;  
  122.     while (pdelete != head) {  
  123.         ptemp = pdelete->pNext;  
  124.         head->pNext = ptemp;  
  125.         ptemp->pPre = head;  
  126.         delete pdelete;  
  127.         pdelete = ptemp;  
  128.     }  
  129. }  
  130.   
  131. //测试函数  
  132. int main() {  
  133.     DoubleCircularLinkList dcl;  
  134.     int position = 0, value = 0, n = 0;  
  135.     bool flag = false;  
  136.   
  137.     cout << "请输入需要创建双向循环链表的结点个数：";  
  138.     cin >> n;  
  139.     dcl.CreateLinkList(n);  
  140.   
  141.     cout << "打印链表值如下：";  
  142.     dcl.TraverseLinkList();  
  143.   
  144.     cout << "请输入插入结点的位置和值：";  
  145.     cin >> position >> value;  
  146.     dcl.InsertNode(position, value);  
  147.       
  148.     cout << "打印链表值如下：";  
  149.     dcl.TraverseLinkList();  
  150.   
  151.     cout << "请输入要删除结点的位置：";  
  152.     cin >> position;  
  153.     dcl.DeleteNode(position);  
  154.   
  155.     cout << "打印链表值如下：";  
  156.     dcl.TraverseLinkList();  
  157.   
  158.     dcl.DeleteLinkList();  
  159.     flag = dcl.IsEmpty();  
  160.     if (flag)  
  161.         cout << "删除链表成功！" << endl;  
  162.     else  
  163.         cout << "删除链表失败！" << endl;  
  164.   
  165.     return 0;  
  166. }</span>  

（C++版）链表（四）——实现双向循环链表创建、插入、删除等简单操作

相关推荐