devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构（C++版）_数据结构c++版

作者：笔触狂放9 | 2024-08-10 20:21:14

赞

踩

数据结构c++版

数据结构学习视频：数据结构-单链表_哔哩哔哩_bilibili

参考代码（C语言）：数据结构系列2-单链表 | tyrantlucifer

 

单链表

单链表是一种基础且重要的数据结构，它属于链式存储结构，用于存储线性表中的数据元素。在单链表中，数据不是以连续的内存空间形式存储，而是通过“节点”相互链接起来。

单链表的每个节点由两个部分组成：

  1. 数据域：用于存储实际的数据元素。
  2. 指针域（或称为链接域）：用于存储指向下一个节点地址的指针。

从逻辑结构上看，单链表中的节点按照一定的逻辑顺序链接在一起，形成一个线性序列。第一个节点通常被称为头节点，它的指针域指向第二个节点；后续每个节点的指针域都指向其后继节点，直到最后一个节点，它的指针域指向 NULL 或者 nullptr（在不同的编程语言中可能有不同的表示方式），表示链表的结束。

单链表的主要特点包括：

  • 插入和删除操作相对数组更灵活，因为不需要移动元素，只需更改相关节点的指针即可。
  • 访问链表中的元素需要从头节点开始遍历，不能像数组那样随机访问。
  • 单链表不预先分配存储空间，可以根据需要动态地增加或减少节点，适合于无法预知数据规模的情况。
  1. #include <iostream>
  2.  
  3. #define TRUE 1
  4. #define FALSE 0
  5.  
  6. /**
  7.  * Define the struct of list node
  8.  */
  9. struct Node {
  10.     int data;
  11.     Node* next;
  12. };
  13.  
  14. /**
  15.  * Initialize a linked list
  16.  * @return the head pointer of the linked list's head
  17.  */
  18. Node* initList() {
  19.     Node* L = new Node;
  20.     L->data = 0;
  21.     L->next = nullptr;
  22.     return L;
  23. }
  24.  
  25. /**
  26.  * Insert an item at the head of the linked list
  27.  * @param L the head pointer of the linked list
  28.  * @param data the data you want to insert
  29.  */
  30. void headInsert(Node* L, int data) {
  31.     Node* node = new Node;
  32.     node->data = data;              
  33.     node->next = L->next;           
  34.     L->next = node;                 
  35.     L->data++;                      
  36. }
  37.  
  38. /**
  39.  * Insert an item at the tail of the linked list
  40.  * @param L the head pointer of the linked list
  41.  * @param data the data you want to insert
  42.  */
  43. void tailInsert(Node* L, int data) {
  44.     Node* node = L;
  45.     // 遍历整个链表
  46.     for (int i = 0; i < L->data; i++) {
  47.         node = node->next;  // 得到尾节点
  48.     }
  49.     Node* n = new Node;
  50.     n->data = data;
  51.     n->next = nullptr;
  52.     node->next = n;     
  53.     L->data++;          
  54. }
  55.  
  56. /**
  57.  * Delete an item from the linked list
  58.  * @param L the head pointer of the linked list
  59.  * @param data the data you want to delete
  60.  * @return success flag
  61.  */
  62. int deleteNode(Node* L, int data) {
  63.     Node* preNode = L;
  64.     Node* node = L->next;  
  65.  
  66.     
  67.     while (node) {  
  68.         if (node->data == data) {           
  69.             preNode->next = node->next;     
  70.             delete node;                   
  71.             L->data--;                      
  72.             return TRUE;
  73.         }
  74.         preNode = node;
  75.         node = node->next;
  76.     }
  77.     return FALSE;
  78. }
  79.  
  80. /**
  81.  * Print all items in a linked list
  82.  * @param L the head pointer of the linked list
  83.  */
  84. void printList(Node* L) {
  85.     Node* node = L->next;
  86.     while (node) {
  87.         std::cout << "node = " << node->data << std::endl;
  88.         node = node->next;
  89.     }
  90. }
  91.  
  92. /**
  93.  * Main function
  94.  * @return 0
  95.  */
  96. int main() {
  97.     Node* L = initList();
  98.     headInsert(L, 1);
  99.     headInsert(L, 2);
  100.     headInsert(L, 3);
  101.     headInsert(L, 4);
  102.     headInsert(L, 5);
  103.     tailInsert(L, 6);
  104.     tailInsert(L, 7);
  105.     printList(L);
  106.  
  107.     if (deleteNode(L, 3)) {
  108.         std::cout << "Success delete" << std::endl;
  109.     }
  110.     else {
  111.         std::cout << "Fail delete" << std::endl;
  112.     }
  113.     printList(L);
  114.  
  115.     // Cleanup: free allocated memory
  116.     Node* current = L;
  117.     while (current) {
  118.         Node* next = current->next;
  119.         delete current;
  120.         current = next;
  121.     }
  122.  
  123.     return 0;
  124. }

 运行结果：

单循链表

单循环链表是一种链式存储的数据结构，它是线性表的一种链式存储结构的变体。在单循环链表中，除了保留单链表的基本特性外，其特殊之处在于最后一个结点的指针域不再是指向空（NULL），而是指回链表的头结点，这样就形成了一个环状结构。

单循环链表主要由以下部分组成：

  1. 结点（Node）：每个结点包含两个部分，即数据域（Data Field）和指针域（Link Field）。

    • 数据域：用于存储具体的数据元素，它可以是任何类型的数据。
    • 指针域：也称链域，用于存储下一个结点的地址，指向链表中的下一个结点。

  2. 头结点（Header Node）：单循环链表通常有一个头结点，它不存放实际数据或者也可以存放特定信息，并且它的指针域指向链表中的第一个实际数据结点。

  3. 链表结构：通过各个结点之间的指针连接形成一个闭环，从任一结点出发，沿着指针方向不断遍历，最终都能回到起点，即头结点。

因此，单循环链表的特点是可以在不修改指针的情况下，从任何一个结点开始都可以连续地遍历到链表的所有元素，提高了某些算法的效率，例如在查找、排序等操作中有一定优势。

  1. #include <iostream>
  2.  
  3. #define TRUE 1
  4. #define FALSE 0
  5.  
  6. /**
  7.  * Define the struct of list node
  8.  */
  9. struct Node {
  10.     int data;
  11.     Node* next;
  12. };
  13.  
  14. /**
  15.  * Initialize a linked list
  16.  * @return the head pointer of the linked list's head
  17.  */
  18. Node* initList() {
  19.     Node* L = new Node();
  20.     L->data = 0;
  21.     L->next = L;
  22.     return L;
  23. }
  24.  
  25. /**
  26.  * Insert an item at the beginning of the linked list
  27.  * @param L the head pointer of the linked list
  28.  * @param data the data you want to insert
  29.  */
  30. void headInsert(Node* L, int data) {
  31.     Node* node = new Node();
  32.     node->data = data;
  33.     node->next = L->next;
  34.     L->next = node;
  35.     L->data++;
  36. }
  37.  
  38. /**
  39.  * Insert an item at the end of the linked list
  40.  * @param L the head pointer of the linked list
  41.  * @param data the data you want to insert
  42.  */
  43. void tailInsert(Node* L, int data) {
  44.     Node* n = L;
  45.     Node* node = new Node();
  46.     node->data = data;
  47.     while (n->next != L) {
  48.         n = n->next;        // 找到链表尾部
  49.     }
  50.     node->next = L;         // 新节点的next指向头节点
  51.     n->next = node;         // 原尾节点的next指向新节点
  52.     L->data++;
  53. }
  54.  
  55. /**
  56.  * Delete an item from the linked list
  57.  * @param L the head pointer of the linked list
  58.  * @param data the data you want to delete
  59.  * @return success flag
  60.  */
  61. int deleteNode(Node* L, int data) {
  62.     // 将新节点的next指向原链表的第一个元素，
  63.     // 再更新链表头的next指向新节点
  64.     Node* preNode = L;
  65.     Node* node = L->next;
  66.     while (node != L) {
  67.         if (node->data == data) {
  68.             preNode->next = node->next;
  69.             delete node;
  70.             L->data--;
  71.             return TRUE;
  72.         }
  73.         preNode = node;
  74.         node = node->next;
  75.     }
  76.     return FALSE;
  77. }
  78.  
  79. /**
  80.  * Print all items in a linked list
  81.  * @param L the head pointer of the linked list
  82.  */
  83. void printList(Node* L) {
  84.     Node* node = L->next;
  85.     while (node != L) {
  86.         std::cout << node->data << "->";
  87.         node = node->next;
  88.     }
  89.     std::cout << "NULL" << std::endl;
  90. }
  91.  
  92. /**
  93.  * Main function
  94.  * @return 0
  95.  */
  96. int main() {
  97.     Node* L = initList();
  98.     headInsert(L, 1);
  99.     headInsert(L, 2);
  100.     headInsert(L, 3);
  101.     headInsert(L, 4);
  102.     headInsert(L, 5);
  103.     tailInsert(L, 6);
  104.     tailInsert(L, 7);
  105.     printList(L);
  106.     deleteNode(L, 4);
  107.     deleteNode(L, 7);
  108.     printList(L);
  109.     return 0;
  110. }

 运行结果：

双链表

双链表（也称为双向链表）是链表的一种复杂形式，它是一种线性数据结构，由一系列节点（或称为元素）构成，每个节点包含两部分：

  1. 数据域：用于存储特定类型的数据元素。
  2. 指针域：每个节点有两个指针域，分别称为“后继指针”和“前驱指针”。后继指针指向该节点的直接后继节点，而前驱指针则指向前一个节点。

因此，在双向链表中，从任何一个节点出发，不仅可以找到其下一个节点（如同单链表），还可以找到其前一个节点。这样的设计使得在双向链表上的操作（如插入、删除和遍历）更加灵活，特别是在需要频繁进行双向遍历时更为高效。

  1. #include <iostream>
  2.  
  3. #define TRUE 1
  4. #define FALSE 0
  5.  
  6. /**
  7.  * Define the struct of list node
  8.  */
  9. struct Node {
  10.     int data;
  11.     Node* pre;
  12.     Node* next;
  13. };
  14.  
  15. /**
  16.  * Initialize a linked list
  17.  * @return the head pointer of the linked list
  18.  */
  19. Node* initList() {
  20.     Node* L = new Node();
  21.     L->data = 0;
  22.     L->pre = nullptr;
  23.     L->next = nullptr;
  24.     return L;
  25. }
  26.  
  27. /**
  28.  * Insert an item at the head of the linked list
  29.  * @param L the head pointer of the linked list
  30.  * @param data the data you want to insert
  31.  */
  32. void headInsert(Node* L, int data) {
  33.     Node* node = new Node();
  34.     node->data = data;
  35.     node->next = L->next;
  36.     node->pre = L;
  37.     if (L->next) {
  38.         L->next->pre = node;    // 如果原链表非空，那么原头节点的下一个节点的前驱指针应该指向新插入的节点
  39.         L->next = node;         // 更新原头节点的 next 指针使其指向新插入的节点    
  40.     }
  41.     else {
  42.         L->next = node;         // 当链表为空时，新插入的节点成为链表的第一个节点
  43.     }
  44.     L->data++;
  45. }
  46.  
  47. /**
  48.  * Insert an item at the tail of the linked list
  49.  * @param L the head pointer of the linked list
  50.  * @param data the data you want to insert
  51.  */
  52. void tailInsert(Node* L, int data) {
  53.     Node* node = L;
  54.     Node* n = new Node();
  55.     n->data = data;
  56.     while (node->next) {
  57.         node = node->next;  // 找到链表尾部的节点
  58.     }
  59.     n->next = node->next;
  60.     node->next = n;
  61.     n->pre = node;
  62.     L->data++;
  63. }
  64.  
  65. /**
  66.  * Delete an item in the linked list
  67.  * @param L the head pointer of the linked list
  68.  * @param data the data you want to delete
  69.  * @return success flag
  70.  */
  71. int deleteNode(Node* L, int data) {
  72.     Node* node = L->next;
  73.     while (node) {
  74.         if (node->data == data) {
  75.             node->pre->next = node->next;
  76.             if (node->next) {
  77.                 node->next->pre = node->pre;
  78.             }
  79.             L->data--;
  80.             delete node;
  81.             return TRUE;
  82.         }
  83.         node = node->next;
  84.     }
  85.     return FALSE;
  86. }
  87.  
  88. /**
  89.  * Print all items in a linked list
  90.  * @param L the head pointer of the linked list
  91.  */
  92. void printList(Node* L) {
  93.     Node* node = L->next;
  94.     while (node) {
  95.         std::cout << node->data << " -> ";
  96.         node = node->next;
  97.     }
  98.     std::cout << "NULL" << std::endl;
  99. }
  100.  
  101. /**
  102.  * Main function
  103.  * @return null
  104.  */
  105. int main() {
  106.     Node* L = initList();
  107.     headInsert(L, 1);
  108.     headInsert(L, 2);
  109.     headInsert(L, 3);
  110.     headInsert(L, 4);
  111.     tailInsert(L, 5);
  112.     tailInsert(L, 6);
  113.     printList(L);
  114.     deleteNode(L, 6);
  115.     printList(L);
  116.     return 0;
  117. }

运行结果：

 

 

双循环列表

双循环链表是一种特殊类型的链表数据结构，它是双向链表与循环链表特性的结合。

组成部分：

  1. 节点（Node）：双循环链表中的每个节点通常包含三个主要部分：

    • 数据域（Data Field）：存储实际的数据元素或对象。
    • 前驱指针（Previous Pointer/Prev）：指向该节点的直接前驱节点。
    • 后继指针（Next Pointer/Next）：指向该节点的直接后继节点。

  2. 链表结构：整个链表通过这些节点相互连接形成，每个节点的“后继指针”指向下一个节点，“前驱指针”指向前一个节点。

  1. #include <iostream>
  2.  
  3. /**
  4.  * Define the struct of list node
  5.  */
  6. struct Node {
  7.     int data;
  8.     Node* pre;
  9.     Node* next;
  10. };
  11.  
  12. /**
  13.  * Init a linked list
  14.  * @return The head pointer of the linked list's head
  15.  */
  16. Node* initList() {
  17.     Node* L = new Node();
  18.     L->data = 0;
  19.     L->pre = L;
  20.     L->next = L;
  21.     return L;
  22. }
  23.  
  24. /**
  25.  * Insert item at the head of the linked list
  26.  * @param L The head pointer of the linked list
  27.  * @param data The data you want to insert
  28.  */
  29. void headInsert(Node* L, int data) {
  30.     Node* node = new Node();
  31.     node->data = data;
  32.     node->next = L->next;
  33.     node->pre =  L;
  34.     L->next->pre = node;
  35.     L->next = node;
  36.     L->data++;
  37. }
  38.  
  39. /**
  40.  * Insert item at the tail of the linked list
  41.  * @param L The head pointer of the linked list
  42.  * @param data The data you want to insert
  43.  */
  44. void tailInsert(Node* L, int data) {
  45.     Node* node = L;
  46.     while (node->next != L) {
  47.         node = node->next;
  48.     }
  49.     Node* n = new Node();
  50.     n->data = data;
  51.     n->pre = node;
  52.     n->next = L;
  53.     L->pre = n;
  54.     node->next = n;
  55.     L->data++;
  56. }
  57.  
  58. /**
  59.  * Delete item in the linked list
  60.  * @param L The head pointer of the linked list
  61.  * @param data The data you want to delete
  62.  * @return Success flag
  63.  */
  64. int deleteNode(Node* L, int data) {
  65.     Node* node = L->next;
  66.     while (node != L) {
  67.         if (node->data == data) {
  68.             node->pre->next = node->next;
  69.             node->next->pre = node->pre;
  70.             delete node;
  71.             L->data--;
  72.             return 1;
  73.         }
  74.         node = node->next;
  75.     }
  76.     return 0;
  77. }
  78.  
  79. /**
  80.  * Print all items in a linked list
  81.  * @param L The head pointer of the linked list
  82.  */
  83. void printList(Node* L) {
  84.     Node* node = L->next;
  85.     while (node != L) {
  86.         std::cout << node->data << " -> ";
  87.         node = node->next;
  88.     }
  89.     std::cout << "NULL" << std::endl;
  90. }
  91.  
  92. /**
  93.  * Main function
  94.  * @return Null
  95.  */
  96. int main() {
  97.     Node* L = initList();
  98.     headInsert(L, 1);
  99.     headInsert(L, 2);
  100.     headInsert(L, 4);
  101.     headInsert(L, 5);
  102.     printList(L);
  103.     tailInsert(L, 6);
  104.     tailInsert(L, 7);
  105.     printList(L);
  106.     deleteNode(L, 7);
  107.     printList(L);
  108.     return 0;
  109. }

运行结果：

 

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号