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

【数据结构】线性表：链式存储--链表（8种） C语言实现_c语言链式存储

作者：不正经 | 2024-04-15 07:56:16

赞

踩

c语言链式存储

前言：请往下翻一翻，链表代码汇总（8种链表的实现代码），代码问题请评论区留言。

目录

链表的性质

性质

分类

头节点：

方向：

循环：

小结：

代码实现

1）单向--不带头--不循环链表

2）单向--不带头--循环链表

3）单向--带头--不循环链表

4）单向--带头--循环链表

5）双向--不带头--不循环链表

6）双向--不带头--循环链表

7）双向--带头--不循环链表

8）双向--带头--循环链表

参考资料：

链表的性质

性质

        线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。每个数据元素除了存储其本身的信息之外，还存储一个指示其直接后继的信息（基地址指针），所以数据元素有两个域：数据域和指针域。

 注意：这只是普通链表的性质，其他变式链表可基于此基础上改进（就看你设计的算法哪种数据结构支持的更好了），例如双向链表指针域由两部分组成。

分类

头节点：

按链表是否带有头节点：带头链表和不带头链表

方向：

按链表访问方向： 单向链表和双向链表

循环：

按链表是否构成循环：循环链表和不循环链表 

小结：

        链表常规分类一共8种。

  1. 单向--不带头--不循环链表
  2. 单向--不带头--循环链表
  3. 单向--带头--不循环链表
  4. 单向--带头--循环链表
  5. 双向--不带头--不循环链表
  6. 双向--不带头--循环链表
  7. 双向--带头--不循环链表
  8. 双向向--带头--循环链表

        常规操作是初始化、增、删、查、改、长度、清空释放等，具体要根据你的需求来具体设计。下面提供具体实现代码，仅供参考。

代码实现

1）单向--不带头--不循环链表

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef int data_t;
  5.  
  6. typedef struct node {
  7.     data_t data;
  8.     struct node* next;
  9. } Node;
  10.  
  11. // 创建新节点
  12. Node* createNode(data_t data) {
  13.     // 分配新节点的内存空间
  14.     Node* newNode = (Node*)malloc(sizeof(Node));
  15.     if (!newNode) {
  16.         printf("Memory allocation failed. The program will exit.\n");
  17.         exit(-1);
  18.     }
  19.  
  20.     // 设置新节点的数据和指针
  21.     newNode->data = data;
  22.     newNode->next = NULL;
  23.  
  24.     return newNode;
  25. }
  26.  
  27. // 初始化链表
  28. Node* initList() {
  29.     return NULL;
  30. }
  31.  
  32. // 头插法
  33. Node* insertAtHead(Node* head, data_t data) {
  34.     // 创建新节点
  35.     Node* newNode = createNode(data);
  36.  
  37.     // 将新节点插入链表头部
  38.     newNode->next = head;
  39.     head = newNode;
  40.  
  41.     return head;
  42. }
  43.  
  44. // 尾插法
  45. Node* insertAtTail(Node* head, data_t data) {
  46.     // 创建新节点
  47.     Node* newNode = createNode(data);
  48.  
  49.     // 如果链表为空，将新节点作为链表的头节点
  50.     if (head == NULL) {
  51.         return newNode;
  52.     }
  53.  
  54.     // 找到链表的尾部节点，将新节点插入尾部
  55.     Node* temp = head;
  56.     while (temp->next != NULL) {
  57.         temp = temp->next;
  58.     }
  59.     temp->next = newNode;
  60.  
  61.     return head;
  62. }
  63.  
  64. // 指定位置插入
  65. Node* insertAtPos(Node* head, data_t data, int pos) {
  66.     // 检查插入位置是否合法
  67.     if (pos < 0) {
  68.         printf("Invalid position.\n");
  69.         return head;
  70.     }
  71.  
  72.     // 头部插入
  73.     if (pos == 0) {
  74.         return insertAtHead(head, data);
  75.     }
  76.  
  77.     // 创建新节点
  78.     Node* newNode = createNode(data);
  79.  
  80.     // 插入位置不为头部，遍历链表找到插入位置
  81.     Node* temp = head;
  82.     int count = 0;
  83.     while (count < pos - 1 && temp != NULL) {
  84.         temp = temp->next;
  85.         count++;
  86.     }
  87.  
  88.     // 插入位置超出链表长度，位置无效
  89.     if (temp == NULL) {
  90.         printf("Invalid position.\n");
  91.         return head;
  92.     }
  93.  
  94.     // 插入新节点
  95.     newNode->next = temp->next;
  96.     temp->next = newNode;
  97.  
  98.     return head;
  99. }
  100.  
  101. // 头删法
  102. Node* deleteAtHead(Node* head) {
  103.     // 检查链表是否为空
  104.     if (head == NULL) {
  105.         printf("The list is empty.\n");
  106.         return head;
  107.     }
  108.  
  109.     // 删除头节点
  110.     Node* temp = head;
  111.     head = head->next;
  112.     free(temp);
  113.  
  114.     return head;
  115. }
  116.  
  117. // 尾删法
  118. Node* deleteAtTail(Node* head) {
  119.     // 检查链表是否为空
  120.     if (head == NULL) {
  121.         printf("The list is empty.\n");
  122.         return head;
  123.     }
  124.  
  125.     // 链表只有一个节点时，直接删除头节点
  126.     if (head->next == NULL) {
  127.         return deleteAtHead(head);
  128.     }
  129.  
  130.     // 找到尾节点的前一个节点
  131.     Node* temp = head;
  132.     while (temp->next->next != NULL) {
  133.         temp = temp->next;
  134.     }
  135.  
  136.     // 删除尾节点
  137.     Node* tail = temp->next;
  138.     temp->next = NULL;
  139.     free(tail);
  140.  
  141.     return head;
  142. }
  143.  
  144. // 指定位置删除
  145. Node* deleteAtPos(Node* head, int pos) {
  146.     // 检查删除位置是否合法
  147.     if (pos < 0) {
  148.         printf("Invalid position.\n");
  149.         return head;
  150.     }
  151.  
  152.     // 头部删除
  153.     if (pos == 0) {
  154.         return deleteAtHead(head);
  155.     }
  156.  
  157.     // 遍历链表找到删除位置的前一个节点
  158.     Node* temp = head;
  159.     int count = 0;
  160.     while (count < pos - 1 && temp != NULL) {
  161.         temp = temp->next;
  162.         count++;
  163.     }
  164.  
  165.     // 删除位置超出链表长度，位置无效
  166.     if (temp == NULL || temp->next == NULL) {
  167.         printf("Invalid position.\n");
  168.         return head;
  169.     }
  170.  
  171.     // 删除节点
  172.     Node* deletedNode = temp->next;
  173.     temp->next = deletedNode->next;
  174.     free(deletedNode);
  175.  
  176.     return head;
  177. }
  178.  
  179. // 查找节点
  180. Node* selectNode(Node* head, int pos) {
  181.     // 检查查找位置是否合法
  182.     if (pos < 0) {
  183.         printf("Invalid position.\n");
  184.         return NULL;
  185.     }
  186.  
  187.     // 遍历链表找到查找位置的节点
  188.     Node* temp = head;
  189.     int count = 0;
  190.     while (count < pos && temp != NULL) {
  191.         temp = temp->next;
  192.         count++;
  193.     }
  194.  
  195.     // 查找位置超出链表长度，位置无效
  196.     if (temp == NULL) {
  197.         printf("Invalid position.\n");
  198.         return NULL;
  199.     }
  200.  
  201.     return temp;
  202. }
  203.  
  204. // 更新节点
  205. void updateNode(Node* node, data_t newData) {
  206.     if (node != NULL) {
  207.         node->data = newData;
  208.     }
  209.     else {
  210.         printf("Node not found.\n");
  211.     }
  212. }
  213.  
  214. // 打印链表
  215. void displayList(Node* head) {
  216.     Node* temp = head;
  217.     while (temp != NULL) {
  218.         printf("%d -> ", temp->data);
  219.         temp = temp->next;
  220.     }
  221.     printf("NULL\n");
  222. }
  223.  
  224. // 清空链表
  225. void clearList(Node** head) {
  226.     Node* temp = *head;
  227.     Node* nextNode;
  228.     while (temp != NULL) {
  229.         nextNode = temp->next;
  230.         free(temp);
  231.         temp = nextNode;
  232.     }
  233.     *head = NULL;
  234. }
  235.  
  236. // 释放模块
  237. void destroyList(Node** head) {
  238.     clearList(head);
  239. }
  240.  
  241. int main() {
  242.     Node* head = initList();
  243.  
  244.     // 测试插入操作
  245.     head = insertAtHead(head, 3);
  246.     head = insertAtTail(head, 5);
  247.     head = insertAtPos(head, 7, 1);
  248.     displayList(head);
  249.  
  250.     // 测试删除操作
  251.     head = deleteAtHead(head);
  252.     head = deleteAtTail(head);
  253.     head = deleteAtPos(head, 0);
  254.     displayList(head);
  255.  
  256.     // 测试查找和更新操作
  257.     Node* node = selectNode(head, 0);
  258.     if (node != NULL) {
  259.         printf("Found Node with data = %d\n", node->data);
  260.         updateNode(node, 10);
  261.         printf("Updated Node data: %d\n", node->data);
  262.     }
  263.     else {
  264.         printf("Node not found!\n");
  265.     }
  266.  
  267.     // 清空链表
  268.     clearList(&head);
  269.     displayList(head);
  270.  
  271.     // 释放链表内存
  272.     destroyList(&head);
  273.     if (head == NULL) {
  274.         printf("List destroyed.\n");
  275.     }
  276.  
  277.     return 0;
  278. }

2）单向--不带头--循环链表

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef int data_t;
  5.  
  6. typedef struct node {
  7.     data_t data;
  8.     struct node* next;
  9. } Node;
  10.  
  11. // 创建新节点
  12. Node* createNode(data_t data) {
  13.     // 分配新节点的内存空间
  14.     Node* newNode = (Node*)malloc(sizeof(Node));
  15.     if (!newNode) {
  16.         printf("Memory allocation failed. The program will exit.\n");
  17.         exit(-1);
  18.     }
  19.  
  20.     // 设置新节点的数据和指针
  21.     newNode->data = data;
  22.     newNode->next = NULL;
  23.  
  24.     return newNode;
  25. }
  26.  
  27. // 初始化链表
  28. Node* initList() {
  29.     return NULL;
  30. }
  31.  
  32. // 头插法
  33. Node* insertAtHead(Node* head, data_t data) {
  34.     // 创建新节点
  35.     Node* newNode = createNode(data);
  36.  
  37.     // 如果链表为空，将新节点作为链表的头节点
  38.     if (head == NULL) {
  39.         newNode->next = newNode;
  40.         return newNode;
  41.     }
  42.  
  43.     // 找到链表的尾节点
  44.     Node* tail = head;
  45.     while (tail->next != head) {
  46.         tail = tail->next;
  47.     }
  48.  
  49.     // 将新节点插入链表头部
  50.     newNode->next = head;
  51.     tail->next = newNode;
  52.  
  53.     return newNode;
  54. }
  55.  
  56. // 尾插法
  57. Node* insertAtTail(Node* head, data_t data) {
  58.     // 创建新节点
  59.     Node* newNode = createNode(data);
  60.  
  61.     // 如果链表为空，将新节点作为链表的头节点
  62.     if (head == NULL) {
  63.         newNode->next = newNode;
  64.         return newNode;
  65.     }
  66.  
  67.     // 找到链表的尾节点
  68.     Node* tail = head;
  69.     while (tail->next != head) {
  70.         tail = tail->next;
  71.     }
  72.  
  73.     // 将新节点插入链表尾部
  74.     tail->next = newNode;
  75.     newNode->next = head;
  76.  
  77.     return head;
  78. }
  79.  
  80. // 指定位置插入
  81. Node* insertAtPos(Node* head, data_t data, int pos) {
  82.     // 检查插入位置是否合法
  83.     if (pos < 0) {
  84.         printf("Invalid position.\n");
  85.         return head;
  86.     }
  87.  
  88.     // 头部插入
  89.     if (pos == 0) {
  90.         return insertAtHead(head, data);
  91.     }
  92.  
  93.     // 创建新节点
  94.     Node* newNode = createNode(data);
  95.  
  96.     // 插入位置不为头部，遍历链表找到插入位置的前一个节点
  97.     Node* temp = head;
  98.     int count = 0;
  99.     while (count < pos - 1 && temp->next != head) {
  100.         temp = temp->next;
  101.         count++;
  102.     }
  103.  
  104.     // 插入位置超出链表长度，位置无效
  105.     if (temp->next == head && count < pos - 1) {
  106.         printf("Invalid position.\n");
  107.         return head;
  108.     }
  109.  
  110.     // 插入新节点
  111.     newNode->next = temp->next;
  112.     temp->next = newNode;
  113.  
  114.     return head;
  115. }
  116.  
  117. // 头删法
  118. Node* deleteAtHead(Node* head) {
  119.     // 检查链表是否为空
  120.     if (head == NULL) {
  121.         printf("The list is empty.\n");
  122.         return head;
  123.     }
  124.  
  125.     // 如果链表只有一个节点，删除后返回NULL
  126.     if (head->next == head) {
  127.         free(head);
  128.         return NULL;
  129.     }
  130.  
  131.     // 找到链表的尾节点
  132.     Node* tail = head;
  133.     while (tail->next != head) {
  134.         tail = tail->next;
  135.     }
  136.  
  137.     // 删除头节点
  138.     Node* temp = head;
  139.     head = head->next;
  140.     tail->next = head;
  141.     free(temp);
  142.  
  143.     return head;
  144. }
  145.  
  146. // 尾删法
  147. Node* deleteAtTail(Node* head) {
  148.     // 检查链表是否为空
  149.     if (head == NULL) {
  150.         printf("The list is empty.\n");
  151.         return head;
  152.     }
  153.  
  154.     // 如果链表只有一个节点，删除后返回NULL
  155.     if (head->next == head) {
  156.         free(head);
  157.         return NULL;
  158.     }
  159.  
  160.     // 找到链表的尾节点和尾节点的前一个节点
  161.     Node* tail = head;
  162.     Node* prev = NULL;
  163.     while (tail->next != head) {
  164.         prev = tail;
  165.         tail = tail->next;
  166.     }
  167.  
  168.     // 删除尾节点
  169.     prev->next = head;
  170.     free(tail);
  171.  
  172.     return head;
  173. }
  174.  
  175. // 指定位置删除
  176. Node* deleteAtPos(Node* head, int pos) {
  177.     // 检查删除位置是否合法
  178.     if (pos < 0) {
  179.         printf("Invalid position.\n");
  180.         return head;
  181.     }
  182.  
  183.     // 头部删除
  184.     if (pos == 0) {
  185.         return deleteAtHead(head);
  186.     }
  187.  
  188.     // 遍历链表找到删除位置的前一个节点
  189.     Node* temp = head;
  190.     int count = 0;
  191.     while (count < pos - 1 && temp->next != head) {
  192.         temp = temp->next;
  193.         count++;
  194.     }
  195.  
  196.     // 删除位置超出链表长度，位置无效
  197.     if (temp->next == head && count < pos - 1) {
  198.         printf("Invalid position.\n");
  199.         return head;
  200.     }
  201.  
  202.     // 删除节点
  203.     Node* deletedNode = temp->next;
  204.     temp->next = deletedNode->next;
  205.     free(deletedNode);
  206.  
  207.     return head;
  208. }
  209.  
  210. // 查找节点
  211. Node* selectNode(Node* head, int pos) {
  212.     // 检查查找位置是否合法
  213.     if (pos < 0) {
  214.         printf("Invalid position.\n");
  215.         return NULL;
  216.     }
  217.  
  218.     // 遍历链表找到查找位置的节点
  219.     Node* temp = head;
  220.     int count = 0;
  221.     while (count < pos && temp->next != head) {
  222.         temp = temp->next;
  223.         count++;
  224.     }
  225.  
  226.     // 查找位置超出链表长度，位置无效
  227.     if (temp->next == head && count < pos) {
  228.         printf("Invalid position.\n");
  229.         return NULL;
  230.     }
  231.  
  232.     return temp;
  233. }
  234.  
  235. // 更新节点
  236. void updateNode(Node* node, data_t newData) {
  237.     if (node != NULL) {
  238.         node->data = newData;
  239.     }
  240.     else {
  241.         printf("Node not found.\n");
  242.     }
  243. }
  244.  
  245. // 打印链表
  246. void displayList(Node* head) {
  247.     if (head == NULL) {
  248.         printf("The list is empty.\n");
  249.         return;
  250.     }
  251.  
  252.     Node* temp = head;
  253.     do {
  254.         printf("%d -> ", temp->data);
  255.         temp = temp->next;
  256.     } while (temp != head);
  257.     printf("HEAD\n");
  258. }
  259.  
  260. // 清空链表
  261. void clearList(Node** head) {
  262.     if (*head == NULL) {
  263.         return;
  264.     }
  265.  
  266.     Node* temp = *head;
  267.     Node* nextNode = NULL;
  268.     do {
  269.         nextNode = temp->next;
  270.         free(temp);
  271.         temp = nextNode;
  272.     } while (temp != *head);
  273.  
  274.     *head = NULL;
  275. }
  276.  
  277. // 释放链表内存
  278. void destroyList(Node** head) {
  279.     clearList(head);
  280. }
  281.  
  282. int main() {
  283.     // 初始化链表
  284.     Node* head = initList();
  285.  
  286.     // 插入操作
  287.     head = insertAtHead(head, 3);
  288.     head = insertAtTail(head, 5);
  289.     head = insertAtPos(head, 7, 1);
  290.     displayList(head);
  291.  
  292.     // 删除操作
  293.     head = deleteAtHead(head);
  294.     head = deleteAtTail(head);
  295.     head = deleteAtPos(head, 0);
  296.     displayList(head);
  297.     head = insertAtHead(head, 3);
  298.     head = insertAtTail(head, 5);
  299.     // 查找和更新操作
  300.     Node* node = selectNode(head, 0);
  301.     if (node != NULL) {
  302.         printf("Found Node with data = %d\n", node->data);
  303.         updateNode(node, 10);
  304.         printf("Updated Node data: %d\n", node->data);
  305.     }
  306.     else {
  307.         printf("Node not found!\n");
  308.     }
  309.  
  310.     // 清空链表
  311.     clearList(&head);
  312.     displayList(head);
  313.  
  314.     // 释放链表内存
  315.     destroyList(&head);
  316.     if (head == NULL) {
  317.         printf("List destroyed.\n");
  318.     }
  319.  
  320.     return 0;
  321. }

3）单向--带头--不循环链表

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef int data_t;
  5.  
  6. typedef struct node {
  7.     data_t data;
  8.     struct node* next;
  9. } Node;
  10.  
  11. // 创建新节点
  12. Node* createNode(data_t data) {
  13.     // 分配新节点的内存空间
  14.     Node* newNode = (Node*)malloc(sizeof(Node));
  15.     if (!newNode) {
  16.         printf("Memory allocation failed. The program will exit.\n");
  17.         exit(-1);
  18.     }
  19.  
  20.     // 设置新节点的数据和指针
  21.     newNode->data = data;
  22.     newNode->next = NULL;
  23.  
  24.     return newNode;
  25. }
  26.  
  27. // 初始化链表
  28. Node* initList() {
  29.     // 创建头节点，并将其数据域设为0
  30.     Node* head = createNode(0);
  31.     head->next = NULL;
  32.  
  33.     return head;
  34. }
  35.  
  36. // 头插法
  37. void insertAtHead(Node* head, data_t data) {
  38.     // 创建新节点
  39.     Node* newNode = createNode(data);
  40.  
  41.     // 将新节点插入链表头部
  42.     newNode->next = head->next;
  43.     head->next = newNode;
  44. }
  45.  
  46. // 尾插法
  47. void insertAtTail(Node* head, data_t data) {
  48.     // 创建新节点
  49.     Node* newNode = createNode(data);
  50.  
  51.     // 找到链表的尾节点
  52.     Node* tail = head;
  53.     while (tail->next != NULL) {
  54.         tail = tail->next;
  55.     }
  56.  
  57.     // 将新节点插入链表尾部
  58.     tail->next = newNode;
  59. }
  60.  
  61. // 指定位置插入
  62. void insertAtPos(Node* head, data_t data, int pos) {
  63.     // 检查插入位置是否合法
  64.     if (pos < 0) {
  65.         printf("Invalid position.\n");
  66.         return;
  67.     }
  68.  
  69.     // 创建新节点
  70.     Node* newNode = createNode(data);
  71.  
  72.     // 插入位置不为头部，遍历链表找到插入位置的前一个节点
  73.     Node* temp = head;
  74.     int count = 0;
  75.     while (count < pos && temp->next != NULL) {
  76.         temp = temp->next;
  77.         count++;
  78.     }
  79.  
  80.     // 插入新节点
  81.     newNode->next = temp->next;
  82.     temp->next = newNode;
  83. }
  84.  
  85. // 头删法
  86. void deleteAtHead(Node* head) {
  87.     // 检查链表是否为空
  88.     if (head->next == NULL) {
  89.         printf("The list is empty.\n");
  90.         return;
  91.     }
  92.  
  93.     // 删除头节点
  94.     Node* temp = head->next;
  95.     head->next = temp->next;
  96.     free(temp);
  97. }
  98.  
  99. // 尾删法
  100. void deleteAtTail(Node* head) {
  101.     // 检查链表是否为空
  102.     if (head->next == NULL) {
  103.         printf("The list is empty.\n");
  104.         return;
  105.     }
  106.  
  107.     // 找到链表的尾节点和尾节点的前一个节点
  108.     Node* prev = head;
  109.     Node* tail = head->next;
  110.     while (tail->next != NULL) {
  111.         prev = tail;
  112.         tail = tail->next;
  113.     }
  114.  
  115.     // 删除尾节点
  116.     prev->next = NULL;
  117.     free(tail);
  118. }
  119.  
  120. // 指定位置删除
  121. void deleteAtPos(Node* head, int pos) {
  122.     // 检查删除位置是否合法
  123.     if (pos < 0) {
  124.         printf("Invalid position.\n");
  125.         return;
  126.     }
  127.  
  128.     // 遍历链表找到删除位置的前一个节点
  129.     Node* temp = head;
  130.     int count = 0;
  131.     while (count < pos && temp->next != NULL) {
  132.         temp = temp->next;
  133.         count++;
  134.     }
  135.  
  136.     // 删除位置超出链表长度，位置无效
  137.     if (temp->next == NULL) {
  138.         printf("Invalid position.\n");
  139.         return;
  140.     }
  141.  
  142.     // 删除节点
  143.     Node* deletedNode = temp->next;
  144.     temp->next = deletedNode->next;
  145.     free(deletedNode);
  146. }
  147.  
  148. // 查找节点
  149. Node* selectNode(Node* head, int pos) {
  150.     // 检查查找位置是否合法
  151.     if (pos < 0) {
  152.         printf("Invalid position.\n");
  153.         return NULL;
  154.     }
  155.  
  156.     // 遍历链表找到查找位置的节点
  157.     Node* temp = head->next;
  158.     int count = 0;
  159.     while (count < pos && temp != NULL) {
  160.         temp = temp->next;
  161.         count++;
  162.     }
  163.  
  164.     // 查找位置超出链表长度，位置无效
  165.     if (temp == NULL) {
  166.         printf("Invalid position.\n");
  167.         return NULL;
  168.     }
  169.  
  170.     return temp;
  171. }
  172.  
  173. // 更新节点
  174. void updateNode(Node* node, data_t newData) {
  175.     if (node != NULL) {
  176.         node->data = newData;
  177.     }
  178.     else {
  179.         printf("Node not found.\n");
  180.     }
  181. }
  182.  
  183. // 打印链表
  184. void displayList(Node* head) {
  185.     Node* temp = head->next;
  186.     while (temp != NULL) {
  187.         printf("%d -> ", temp->data);
  188.         temp = temp->next;
  189.     }
  190.     printf("NULL\n");
  191. }
  192.  
  193. // 清空链表
  194. void clearList(Node* head) {
  195.     Node* temp = head->next;
  196.     while (temp != NULL) {
  197.         Node* nextNode = temp->next;
  198.         free(temp);
  199.         temp = nextNode;
  200.     }
  201.     head->next = NULL;
  202. }
  203.  
  204. // 释放链表内存
  205. void destroyList(Node* head) {
  206.     clearList(head);
  207.     free(head);
  208. }
  209.  
  210. int main() {
  211.     // 初始化链表
  212.     Node* head = initList();
  213.  
  214.     // 插入操作
  215.     insertAtHead(head, 3);
  216.     insertAtTail(head, 5);
  217.     insertAtPos(head, 7, 1);
  218.     displayList(head);
  219.  
  220.     // 删除操作
  221.     deleteAtHead(head);
  222.     deleteAtTail(head);
  223.     deleteAtPos(head, 0);
  224.     displayList(head);
  225.  
  226.     // 查找和更新操作
  227.     Node* node = selectNode(head, 0);
  228.     if (node != NULL) {
  229.         printf("Found Node with data = %d\n", node->data);
  230.         updateNode(node, 10);
  231.         printf("Updated Node data: %d\n", node->data);
  232.     }
  233.     else {
  234.         printf("Node not found!\n");
  235.     }
  236.  
  237.     // 清空链表
  238.     clearList(head);
  239.     displayList(head);
  240.  
  241.     // 释放链表内存
  242.     destroyList(head);
  243.     printf("List destroyed.\n");
  244.  
  245.     return 0;
  246. }

4）单向--带头--循环链表

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef int data_t;
  5.  
  6. typedef struct node {
  7.     data_t data;
  8.     struct node* next;
  9. } Node;
  10.  
  11. // 创建新节点
  12. Node* createNode(data_t data) {
  13.     // 分配新节点的内存空间
  14.     Node* newNode = (Node*)malloc(sizeof(Node));
  15.     if (!newNode) {
  16.         printf("Memory allocation failed. The program will exit.\n");
  17.         exit(-1);
  18.     }
  19.  
  20.     // 设置新节点的数据和指针
  21.     newNode->data = data;
  22.     newNode->next = NULL;
  23.  
  24.     return newNode;
  25. }
  26.  
  27. // 初始化链表
  28. Node* initList() {
  29.     // 创建头节点，并将其指针指向自身
  30.     Node* head = createNode(0);
  31.     head->next = head;
  32.  
  33.     return head;
  34. }
  35.  
  36. // 头插法
  37. void insertAtHead(Node* head, data_t data) {
  38.     // 创建新节点
  39.     Node* newNode = createNode(data);
  40.  
  41.     // 插入新节点
  42.     newNode->next = head->next;
  43.     head->next = newNode;
  44. }
  45.  
  46. // 尾插法
  47. void insertAtTail(Node* head, data_t data) {
  48.     // 创建新节点
  49.     Node* newNode = createNode(data);
  50.  
  51.     // 找到链表的尾节点
  52.     Node* tail = head;
  53.     while (tail->next != head) {
  54.         tail = tail->next;
  55.     }
  56.  
  57.     // 插入新节点
  58.     newNode->next = head;
  59.     tail->next = newNode;
  60. }
  61.  
  62. // 指定位置插入
  63. void insertAtPos(Node* head, data_t data, int pos) {
  64.     // 检查插入位置是否合法
  65.     if (pos < 0) {
  66.         printf("Invalid position.\n");
  67.         return;
  68.     }
  69.  
  70.     // 创建新节点
  71.     Node* newNode = createNode(data);
  72.  
  73.     // 插入位置不为头部，遍历链表找到插入位置的前一个节点
  74.     Node* temp = head;
  75.     int count = 0;
  76.     while (count < pos && temp->next != head) {
  77.         temp = temp->next;
  78.         count++;
  79.     }
  80.  
  81.     // 插入新节点
  82.     newNode->next = temp->next;
  83.     temp->next = newNode;
  84. }
  85.  
  86. // 头删法
  87. void deleteAtHead(Node* head) {
  88.     // 检查链表是否为空
  89.     if (head->next == head) {
  90.         printf("The list is empty.\n");
  91.         return;
  92.     }
  93.  
  94.     // 删除头节点
  95.     Node* temp = head->next;
  96.     head->next = temp->next;
  97.     free(temp);
  98. }
  99.  
  100. // 尾删法
  101. void deleteAtTail(Node* head) {
  102.     // 检查链表是否为空
  103.     if (head->next == head) {
  104.         printf("The list is empty.\n");
  105.         return;
  106.     }
  107.  
  108.     // 找到链表的尾节点和尾节点的前一个节点
  109.     Node* prev = head;
  110.     Node* tail = head->next;
  111.     while (tail->next != head) {
  112.         prev = tail;
  113.         tail = tail->next;
  114.     }
  115.  
  116.     // 删除尾节点
  117.     prev->next = head;
  118.     free(tail);
  119. }
  120.  
  121. // 指定位置删除
  122. void deleteAtPos(Node* head, int pos) {
  123.     // 检查删除位置是否合法
  124.     if (pos < 0) {
  125.         printf("Invalid position.\n");
  126.         return;
  127.     }
  128.  
  129.     // 遍历链表找到删除位置的前一个节点
  130.     Node* temp = head;
  131.     int count = 0;
  132.     while (count < pos && temp->next != head) {
  133.         temp = temp->next;
  134.         count++;
  135.     }
  136.  
  137.     // 删除位置超出链表长度，位置无效
  138.     if (temp->next == head) {
  139.         printf("Invalid position.\n");
  140.         return;
  141.     }
  142.  
  143.     // 删除节点
  144.     Node* deletedNode = temp->next;
  145.     temp->next = deletedNode->next;
  146.     free(deletedNode);
  147. }
  148.  
  149. // 查找节点
  150. Node* selectNode(Node* head, int pos) {
  151.     // 检查查找位置是否合法
  152.     if (pos < 0) {
  153.         printf("Invalid position.\n");
  154.         return NULL;
  155.     }
  156.  
  157.     // 遍历链表找到查找位置的节点
  158.     Node* temp = head->next;
  159.     int count = 0;
  160.     while (count < pos && temp != head) {
  161.         temp = temp->next;
  162.         count++;
  163.     }
  164.  
  165.     // 查找位置超出链表长度，位置无效
  166.     if (temp == head) {
  167.         printf("Invalid position.\n");
  168.         return NULL;
  169.     }
  170.  
  171.     return temp;
  172. }
  173.  
  174. // 更新节点
  175. void updateNode(Node* node, data_t newData) {
  176.     if (node != NULL) {
  177.         node->data = newData;
  178.     }
  179.     else {
  180.         printf("Node not found.\n");
  181.     }
  182. }
  183.  
  184. // 打印链表
  185. void displayList(Node* head) {
  186.     Node* temp = head->next;
  187.     while (temp != head) {
  188.         printf("%d -> ", temp->data);
  189.         temp = temp->next;
  190.     }
  191.     printf("HEAD\n");
  192. }
  193.  
  194. // 清空链表
  195. void clearList(Node* head) {
  196.     Node* temp = head->next;
  197.     while (temp != head) {
  198.         Node* nextNode = temp->next;
  199.         free(temp);
  200.         temp = nextNode;
  201.     }
  202.     head->next = head;
  203. }
  204.  
  205. // 释放链表内存
  206. void destroyList(Node* head) {
  207.     clearList(head);
  208.     free(head);
  209. }
  210.  
  211. int main() {
  212.     // 初始化链表
  213.     Node* head = initList();
  214.  
  215.     // 插入操作
  216.     insertAtHead(head, 3);
  217.     insertAtTail(head, 5);
  218.     insertAtPos(head, 7, 1);
  219.     displayList(head);
  220.  
  221.     // 删除操作
  222.     deleteAtHead(head);
  223.     deleteAtTail(head);
  224.     deleteAtPos(head, 0);
  225.     displayList(head);
  226.  
  227.     // 查找和更新操作
  228.     Node* node = selectNode(head, 0);
  229.     if (node != NULL) {
  230.         printf("Found Node with data = %d\n", node->data);
  231.         updateNode(node, 10);
  232.         printf("Updated Node data: %d\n", node->data);
  233.     }
  234.     else {
  235.         printf("Node not found!\n");
  236.     }
  237.  
  238.     // 清空链表
  239.     clearList(head);
  240.     displayList(head);
  241.  
  242.     // 释放链表内存
  243.     destroyList(head);
  244.     printf("List destroyed.\n");
  245.  
  246.     return 0;
  247. }

5）双向--不带头--不循环链表

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef int data_t;
  5.  
  6. typedef struct node {
  7.     data_t data;
  8.     struct node* prev;
  9.     struct node* next;
  10. } Node;
  11.  
  12. // 创建新节点，分配内存，并设置节点的数据和指针
  13. Node* createNode(data_t data) {
  14.     Node* newNode = (Node*)malloc(sizeof(Node));
  15.     if (!newNode) {
  16.         printf("Memory allocation failed. The program will exit.\n");
  17.         exit(-1);
  18.     }
  19.     newNode->data = data;
  20.     newNode->prev = NULL;
  21.     newNode->next = NULL;
  22.     return newNode;
  23. }
  24.  
  25. // 初始化链表，返回NULL，因为开始时链表是空的
  26. Node* initList() {
  27.     return NULL;
  28. }
  29.  
  30. // 在链表的开头插入新节点
  31. void insertAtHead(Node** head, data_t data) {
  32.     Node* newNode = createNode(data);
  33.     if (*head != NULL) {
  34.         (*head)->prev = newNode;
  35.     }
  36.     newNode->next = *head;
  37.     *head = newNode;
  38. }
  39.  
  40. // 在链表的末尾插入新节点
  41. void insertAtTail(Node** head, data_t data) {
  42.     Node* newNode = createNode(data);
  43.     if (*head == NULL) {
  44.         *head = newNode;
  45.         return;
  46.     }
  47.     Node* temp = *head;
  48.     while (temp->next != NULL) {
  49.         temp = temp->next;
  50.     }
  51.     temp->next = newNode;
  52.     newNode->prev = temp;
  53. }
  54.  
  55. // 在链表的指定位置插入新节点
  56. void insertAtPos(Node** head, data_t data, int pos) {
  57.     if (pos == 0) {
  58.         insertAtHead(head, data);
  59.         return;
  60.     }
  61.     Node* newNode = createNode(data);
  62.     Node* temp = *head;
  63.     for (int i = 0; i < pos - 1; i++) {
  64.         if (temp == NULL) {
  65.             printf("Invalid position.\n");
  66.             free(newNode);
  67.             return;
  68.         }
  69.         temp = temp->next;
  70.     }
  71.     newNode->next = temp->next;
  72.     newNode->prev = temp;
  73.     if (temp->next != NULL) {
  74.         temp->next->prev = newNode;
  75.     }
  76.     temp->next = newNode;
  77. }
  78.  
  79. // 删除链表的头节点
  80. void deleteAtHead(Node** head) {
  81.     if (*head == NULL) {
  82.         printf("The list is empty.\n");
  83.         return;
  84.     }
  85.     Node* temp = *head;
  86.     *head = (*head)->next;
  87.     if (*head != NULL) {
  88.         (*head)->prev = NULL;
  89.     }
  90.     free(temp);
  91. }
  92.  
  93. // 删除链表的尾节点
  94. void deleteAtTail(Node** head) {
  95.     if (*head == NULL) {
  96.         printf("The list is empty.\n");
  97.         return;
  98.     }
  99.     Node* temp = *head;
  100.     while (temp->next != NULL) {
  101.         temp = temp->next;
  102.     }
  103.     if (temp->prev != NULL) {
  104.         temp->prev->next = NULL;
  105.     }
  106.     else {
  107.         *head = NULL;
  108.     }
  109.     free(temp);
  110. }
  111.  
  112. // 删除链表的指定位置的节点
  113. void deleteAtPos(Node** head, int pos) {
  114.     if (*head == NULL) {
  115.         printf("The list is empty.\n");
  116.         return;
  117.     }
  118.     if (pos == 0) {
  119.         deleteAtHead(head);
  120.         return;
  121.     }
  122.     Node* temp = *head;
  123.     for (int i = 0; i < pos; i++) {
  124.         if (temp == NULL) {
  125.             printf("Invalid position.\n");
  126.             return;
  127.         }
  128.         temp = temp->next;
  129.     }
  130.     temp->prev->next = temp->next;
  131.     if (temp->next != NULL) {
  132.         temp->next->prev = temp->prev;
  133.     }
  134.     free(temp);
  135. }
  136.  
  137. // 查找链表的指定位置的节点
  138. Node* selectNode(Node* head, int pos) {
  139.     Node* temp = head;
  140.     for (int i = 0; i < pos; i++) {
  141.         if (temp == NULL) {
  142.             printf("Invalid position.\n");
  143.             return NULL;
  144.         }
  145.         temp = temp->next;
  146.     }
  147.     return temp;
  148. }
  149.  
  150. // 更新节点的数据
  151. void updateNode(Node* node, data_t newData) {
  152.     if (node != NULL) {
  153.         node->data = newData;
  154.     }
  155.     else {
  156.         printf("Node not found.\n");
  157.     }
  158. }
  159.  
  160. // 打印链表的数据
  161. void displayList(Node* head) {
  162.     Node* temp = head;
  163.     while (temp != NULL) {
  164.         printf("%d -> ", temp->data);
  165.         temp = temp->next;
  166.     }
  167.     printf("NULL\n");
  168. }
  169.  
  170. // 清空链表，删除除头节点外的所有节点
  171. void clearList(Node** head) {
  172.     Node* temp = *head;
  173.     while (temp != NULL) {
  174.         Node* next = temp->next;
  175.         free(temp);
  176.         temp = next;
  177.     }
  178.     *head = NULL;
  179. }
  180.  
  181. // 释放链表的内存，包括头节点
  182. void destroyList(Node** head) {
  183.     clearList(head);
  184. }
  185.  
  186. int main() {
  187.     Node* head = initList();
  188.     insertAtHead(&head, 3);
  189.     insertAtTail(&head, 5);
  190.     insertAtPos(&head, 7, 1);
  191.     displayList(head);
  192.     deleteAtHead(&head);
  193.     deleteAtTail(&head);
  194.     deleteAtPos(&head, 0);
  195.     displayList(head);
  196.     Node* node = selectNode(head, 0);
  197.     if (node != NULL) {
  198.         printf("Found Node with data = %d\n", node->data);
  199.         updateNode(node, 10);
  200.         printf("Updated Node data: %d\n", node->data);
  201.     }
  202.     else {
  203.         printf("Node not found!\n");
  204.     }
  205.     clearList(&head);
  206.     displayList(head);
  207.     destroyList(&head);
  208.     printf("List destroyed.\n");
  209.     return 0;
  210. }

6）双向--不带头--循环链表

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef int data_t;
  5.  
  6. typedef struct node {
  7.     data_t data;
  8.     struct node* prev;
  9.     struct node* next;
  10. } Node;
  11.  
  12. // 创建新节点，分配内存，并设置节点的数据和指针
  13. Node* createNode(data_t data) {
  14.     Node* newNode = (Node*)malloc(sizeof(Node));
  15.     if (!newNode) {
  16.         printf("Memory allocation failed. The program will exit.\n");
  17.         exit(-1);
  18.     }
  19.     newNode->data = data;
  20.     newNode->prev = newNode; // 链表中的最后一个节点指向自己
  21.     newNode->next = newNode; // 链表中的第一个节点指向自己
  22.     return newNode;
  23. }
  24.  
  25. // 初始化链表，返回一个新节点，节点的数据为0
  26. Node* initList() {
  27.     return createNode(0);
  28. }
  29.  
  30. // 在链表的开头插入新节点
  31. void insertAtHead(Node* head, data_t data) {
  32.     Node* newNode = createNode(data);
  33.     newNode->next = head->next;
  34.     newNode->prev = head;
  35.     head->next->prev = newNode;
  36.     head->next = newNode;
  37. }
  38.  
  39. // 在链表的末尾插入新节点
  40. void insertAtTail(Node* head, data_t data) {
  41.     Node* newNode = createNode(data);
  42.     newNode->next = head;
  43.     newNode->prev = head->prev;
  44.     head->prev->next = newNode;
  45.     head->prev = newNode;
  46. }
  47.  
  48. // 在链表的指定位置插入新节点
  49. void insertAtPos(Node* head, data_t data, int pos) {
  50.     Node* temp = head;
  51.     for (int i = 0; i < pos; i++) {
  52.         temp = temp->next;
  53.         if (temp == head) {
  54.             printf("Invalid position.\n");
  55.             return;
  56.         }
  57.     }
  58.     Node* newNode = createNode(data);
  59.     newNode->next = temp->next;
  60.     newNode->prev = temp;
  61.     temp->next->prev = newNode;
  62.     temp->next = newNode;
  63. }
  64.  
  65. // 删除链表的头节点
  66. void deleteAtHead(Node* head) {
  67.     if (head->next == head) {
  68.         printf("The list is empty.\n");
  69.         return;
  70.     }
  71.     Node* temp = head->next;
  72.     temp->next->prev = head;
  73.     head->next = temp->next;
  74.     free(temp);
  75. }
  76.  
  77. // 删除链表的尾节点
  78. void deleteAtTail(Node* head) {
  79.     if (head->next == head) {
  80.         printf("The list is empty.\n");
  81.         return;
  82.     }
  83.     Node* temp = head->prev;
  84.     temp->prev->next = head;
  85.     head->prev = temp->prev;
  86.     free(temp);
  87. }
  88.  
  89. // 删除链表的指定位置的节点
  90. void deleteAtPos(Node* head, int pos) {
  91.     Node* temp = head;
  92.     for (int i = 0; i < pos; i++) {
  93.         temp = temp->next;
  94.         if (temp == head) {
  95.             printf("Invalid position.\n");
  96.             return;
  97.         }
  98.     }
  99.     temp = temp->next;
  100.     if (temp == head) {
  101.         printf("Invalid position.\n");
  102.         return;
  103.     }
  104.     temp->prev->next = temp->next;
  105.     temp->next->prev = temp->prev;
  106.     free(temp);
  107. }
  108.  
  109. // 查找链表的指定位置的节点
  110. Node* selectNode(Node* head, int pos) {
  111.     Node* temp = head;
  112.     for (int i = 0; i < pos; i++) {
  113.         temp = temp->next;
  114.         if (temp == head) {
  115.             printf("Invalid position.\n");
  116.             return NULL;
  117.         }
  118.     }
  119.     return temp->next;
  120. }
  121.  
  122. // 更新节点的数据
  123. void updateNode(Node* node, data_t newData) {
  124.     if (node != NULL) {
  125.         node->data = newData;
  126.     }
  127.     else {
  128.         printf("Node not found.\n");
  129.     }
  130. }
  131.  
  132. // 打印链表的所有节点
  133. void displayList(Node* head) {
  134.     Node* temp = head->next;
  135.     while (temp != head) {
  136.         printf("%d -> ", temp->data);
  137.         temp = temp->next;
  138.     }
  139.     printf("HEAD\n");
  140. }
  141.  
  142. // 清空链表，删除所有节点
  143. void clearList(Node* head) {
  144.     Node* temp = head->next;
  145.     while (temp != head) {
  146.         Node* next = temp->next;
  147.         free(temp);
  148.         temp = next;
  149.     }
  150.     head->prev = head;
  151.     head->next = head;
  152. }
  153.  
  154. // 释放链表的内存
  155. void destroyList(Node** headRef) {
  156.     clearList(*headRef);
  157.     free(*headRef);
  158.     *headRef = NULL;
  159. }
  160.  
  161. // 主函数，测试链表的功能
  162. int main() {
  163.     Node* head = initList();
  164.     insertAtHead(head, 1);
  165.     insertAtTail(head, 2);
  166.     insertAtPos(head, 3, 1);
  167.     displayList(head);
  168.     deleteAtHead(head);
  169.     deleteAtTail(head);
  170.     deleteAtPos(head, 0);
  171.     displayList(head);
  172.     Node* node = selectNode(head, 0);
  173.     if (node != NULL) {
  174.         printf("Found node with data = %d\n", node->data);
  175.         updateNode(node, 10);
  176.         printf("Updated node data = %d\n", node->data);
  177.     }
  178.     else {
  179.         printf("Node not found!\n");
  180.     }
  181.     clearList(head);
  182.     displayList(head);
  183.     destroyList(&head);
  184.     printf("List destroyed.\n");
  185.     return 0;
  186. }

7）双向--带头--不循环链表

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef int data_t;
  5.  
  6. typedef struct node {
  7.     data_t data;
  8.     struct node* prev;
  9.     struct node* next;
  10. } Node;
  11.  
  12. // 创建新节点，分配内存，并设置节点的数据和指针
  13. Node* createNode(data_t data) {
  14.     Node* newNode = (Node*)malloc(sizeof(Node));
  15.     if (!newNode) {
  16.         printf("Memory allocation failed. The program will exit.\n");
  17.         exit(-1);
  18.     }
  19.     newNode->data = data;
  20.     newNode->prev = NULL;
  21.     newNode->next = NULL;
  22.     return newNode;
  23. }
  24.  
  25. // 初始化链表，返回一个新节点，作为头节点
  26. Node* initList() {
  27.     return createNode(0);
  28. }
  29.  
  30. // 在链表的开头插入新节点
  31. void insertAtHead(Node* head, data_t data) {
  32.     Node* newNode = createNode(data);
  33.     newNode->next = head->next;
  34.     newNode->prev = head;
  35.     if (head->next != NULL) {
  36.         head->next->prev = newNode;
  37.     }
  38.     head->next = newNode;
  39. }
  40.  
  41. // 在链表的末尾插入新节点
  42. void insertAtTail(Node* head, data_t data) {
  43.     Node* newNode = createNode(data);
  44.     Node* temp = head;
  45.     while (temp->next != NULL) {
  46.         temp = temp->next;
  47.     }
  48.     newNode->prev = temp;
  49.     temp->next = newNode;
  50. }
  51.  
  52. // 在链表的指定位置插入新节点
  53. void insertAtPos(Node* head, data_t data, int pos) {
  54.     Node* temp = head;
  55.     for (int i = 0; i < pos; i++) {
  56.         if (temp->next == NULL) {
  57.             printf("Invalid position.\n");
  58.             return;
  59.         }
  60.         temp = temp->next;
  61.     }
  62.     Node* newNode = createNode(data);
  63.     newNode->next = temp->next;
  64.     newNode->prev = temp;
  65.     if (temp->next != NULL) {
  66.         temp->next->prev = newNode;
  67.     }
  68.     temp->next = newNode;
  69. }
  70.  
  71. // 删除链表的头节点
  72. void deleteAtHead(Node* head) {
  73.     if (head->next == NULL) {
  74.         printf("The list is empty.\n");
  75.         return;
  76.     }
  77.     Node* temp = head->next;
  78.     head->next = temp->next;
  79.     if (temp->next != NULL) {
  80.         temp->next->prev = head;
  81.     }
  82.     free(temp);
  83. }
  84.  
  85. // 删除链表的尾节点
  86. void deleteAtTail(Node* head) {
  87.     if (head->next == NULL) {
  88.         printf("The list is empty.\n");
  89.         return;
  90.     }
  91.     Node* temp = head;
  92.     while (temp->next != NULL) {
  93.         temp = temp->next;
  94.     }
  95.     temp->prev->next = NULL;
  96.     free(temp);
  97. }
  98.  
  99. // 删除链表的指定位置的节点
  100. void deleteAtPos(Node* head, int pos) {
  101.     Node* temp = head;
  102.     for (int i = 0; i < pos; i++) {
  103.         if (temp->next == NULL) {
  104.             printf("Invalid position.\n");
  105.             return;
  106.         }
  107.         temp = temp->next;
  108.     }
  109.     if (temp->next == NULL) {
  110.         printf("Invalid position.\n");
  111.         return;
  112.     }
  113.     Node* next = temp->next->next;
  114.     if (next != NULL) {
  115.         next->prev = temp;
  116.     }
  117.     free(temp->next);
  118.     temp->next = next;
  119. }
  120.  
  121. // 查找链表的指定位置的节点
  122. Node* selectNode(Node* head, int pos) {
  123.     Node* temp = head;
  124.     for (int i = 0; i < pos; i++) {
  125.         if (temp->next == NULL) {
  126.             printf("Invalid position.\n");
  127.             return NULL;
  128.         }
  129.         temp = temp->next;
  130.     }
  131.     return temp->next;
  132. }
  133.  
  134. // 更新节点的数据
  135. void updateNode(Node* node, data_t newData) {
  136.     if (node != NULL) {
  137.         node->data = newData;
  138.     }
  139.     else {
  140.         printf("Node not found.\n");
  141.     }
  142. }
  143.  
  144. // 打印链表的所有节点
  145. void displayList(Node* head) {
  146.     Node* temp = head->next;
  147.     while (temp != NULL) {
  148.         printf("%d -> ", temp->data);
  149.         temp = temp->next;
  150.     }
  151.     printf("NULL\n");
  152. }
  153.  
  154. // 清空链表，删除所有节点
  155. void clearList(Node* head) {
  156.     while (head->next != NULL) {
  157.         deleteAtHead(head);
  158.     }
  159. }
  160.  
  161. // 释放链表的内存
  162. void destroyList(Node** headRef) {
  163.     clearList(*headRef);
  164.     free(*headRef);
  165.     *headRef = NULL;
  166. }
  167.  
  168. // 主函数，测试链表的功能
  169. int main() {
  170.     Node* head = initList();
  171.     insertAtHead(head, 1);
  172.     insertAtTail(head, 2);
  173.     insertAtPos(head, 3, 1);
  174.     displayList(head);
  175.     deleteAtHead(head);
  176.     deleteAtTail(head);
  177.     deleteAtPos(head, 0);
  178.     displayList(head);
  179.     Node* node = selectNode(head, 0);
  180.     if (node != NULL) {
  181.         printf("Found node with data = %d\n", node->data);
  182.         updateNode(node, 10);
  183.         printf("Updated node data = %d\n", node->data);
  184.     }
  185.     else {
  186.         printf("Node not found!\n");
  187.     }
  188.     clearList(head);
  189.     displayList(head);
  190.     destroyList(&head);
  191.     printf("List destroyed.\n");
  192.     return 0;
  193. }

8）双向--带头--循环链表

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef int data_t;
  5.  
  6. typedef struct node {
  7.     data_t data;
  8.     struct node* prev;
  9.     struct node* next;
  10. } Node;
  11.  
  12. // 创建新节点，分配内存，并设置节点的数据和指针
  13. Node* createNode(data_t data) {
  14.     Node* newNode = (Node*)malloc(sizeof(Node));
  15.     if (!newNode) {
  16.         printf("Memory allocation failed. The program will exit.\n");
  17.         exit(-1);
  18.     }
  19.     newNode->data = data;
  20.     newNode->prev = NULL;
  21.     newNode->next = NULL;
  22.     return newNode;
  23. }
  24.  
  25. // 初始化链表，返回一个新节点，作为头节点
  26. Node* initList() {
  27.     Node* head = createNode(0);
  28.     head->next = head;
  29.     head->prev = head;
  30.     return head;
  31. }
  32.  
  33. // 在链表的开头插入新节点
  34. void insertAtHead(Node* head, data_t data) {
  35.     Node* newNode = createNode(data);
  36.     newNode->next = head->next;
  37.     newNode->prev = head;
  38.     head->next->prev = newNode;
  39.     head->next = newNode;
  40. }
  41.  
  42. // 在链表的末尾插入新节点
  43. void insertAtTail(Node* head, data_t data) {
  44.     Node* newNode = createNode(data);
  45.     newNode->next = head;
  46.     newNode->prev = head->prev;
  47.     head->prev->next = newNode;
  48.     head->prev = newNode;
  49. }
  50.  
  51. // 在链表的指定位置插入新节点
  52. void insertAtPos(Node* head, data_t data, int pos) {
  53.     Node* temp = head;
  54.     for (int i = 0; i < pos; i++) {
  55.         if (temp->next == head) {
  56.             printf("Invalid position.\n");
  57.             return;
  58.         }
  59.         temp = temp->next;
  60.     }
  61.     Node* newNode = createNode(data);
  62.     newNode->next = temp->next;
  63.     newNode->prev = temp;
  64.     temp->next->prev = newNode;
  65.     temp->next = newNode;
  66. }
  67.  
  68. // 删除链表的头节点
  69. void deleteAtHead(Node* head) {
  70.     if (head->next == head) {
  71.         printf("The list is empty.\n");
  72.         return;
  73.     }
  74.     Node* temp = head->next;
  75.     head->next = temp->next;
  76.     temp->next->prev = head;
  77.     free(temp);
  78. }
  79.  
  80. // 删除链表的尾节点
  81. void deleteAtTail(Node* head) {
  82.     if (head->next == head) {
  83.         printf("The list is empty.\n");
  84.         return;
  85.     }
  86.     Node* temp = head->prev;
  87.     head->prev = temp->prev;
  88.     temp->prev->next = head;
  89.     free(temp);
  90. }
  91.  
  92. // 删除链表的指定位置的节点
  93. void deleteAtPos(Node* head, int pos) {
  94.     Node* temp = head;
  95.     for (int i = 0; i < pos; i++) {
  96.         if (temp->next == head) {
  97.             printf("Invalid position.\n");
  98.             return;
  99.         }
  100.         temp = temp->next;
  101.     }
  102.     if (temp->next == head) {
  103.         printf("Invalid position.\n");
  104.         return;
  105.     }
  106.     Node* next = temp->next->next;
  107.     next->prev = temp;
  108.     free(temp->next);
  109.     temp->next = next;
  110. }
  111.  
  112. // 查找链表的指定位置的节点
  113. Node* selectNode(Node* head, int pos) {
  114.     Node* temp = head;
  115.     for (int i = 0; i < pos; i++) {
  116.         if (temp->next == head) {
  117.             printf("Invalid position.\n");
  118.             return NULL;
  119.         }
  120.         temp = temp->next;
  121.     }
  122.     if (temp->next == head) {
  123.         printf("Invalid position.\n");
  124.         return NULL;
  125.     }
  126.     return temp->next;
  127. }
  128.  
  129. // 更新节点的数据
  130. void updateNode(Node* node, data_t newData) {
  131.     if (node != NULL) {
  132.         node->data = newData;
  133.     }
  134.     else {
  135.         printf("Node not found.\n");
  136.     }
  137. }
  138.  
  139. // 打印链表的所有节点
  140. void displayList(Node* head) {
  141.     Node* temp = head->next;
  142.     while (temp != head) {
  143.         printf("%d -> ", temp->data);
  144.         temp = temp->next;
  145.     }
  146.     printf("NULL\n");
  147. }
  148.  
  149. // 清空链表，删除所有节点
  150. void clearList(Node* head) {
  151.     while (head->next != head) {
  152.         deleteAtHead(head);
  153.     }
  154. }
  155.  
  156. // 释放链表的内存
  157. void destroyList(Node** headRef) {
  158.     clearList(*headRef);
  159.     free(*headRef);
  160.     *headRef = NULL;
  161. }
  162.  
  163. // 主函数，测试链表的功能
  164. int main() {
  165.     Node* head = initList();
  166.     insertAtHead(head, 1);
  167.     insertAtTail(head, 2);
  168.     insertAtPos(head, 3, 1);
  169.     displayList(head);
  170.     deleteAtHead(head);
  171.     deleteAtTail(head);
  172.     deleteAtPos(head, 0);
  173.     displayList(head);
  174.     Node* node = selectNode(head, 0);
  175.     if (node != NULL) {
  176.         printf("Found node with data = %d\n", node->data);
  177.         updateNode(node, 10);
  178.         printf("Updated node data = %d\n", node->data);
  179.     }
  180.     else {
  181.         printf("Node not found!\n");
  182.     }
  183.     clearList(head);
  184.     displayList(head);
  185.     destroyList(&head);
  186.     printf("List destroyed.\n");
  187.     return 0;
  188. }

参考资料：

  1. 程杰：《大话数据结构》
  2. 王晓华：《算法的乐趣》
  3. 严蔚敏、吴伟民：《数据结构（C语言版）》
  4. 渡部有隆：《挑战程序设计竞赛2》
  5. 石田保辉：《我的第一本算法书》
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/426639
推荐阅读
相关标签

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

  

闽ICP备14008679号