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

（图解）单链表删除结点值为x的结点算法_1、编写一个程序,实现单链表删除其元素值为x的结点(假若x是唯一的)。

作者：很楠不爱3 | 2024-04-18 05:21:48

赞

踩

1、编写一个程序,实现单链表删除其元素值为x的结点(假若x是唯一的)。

目录

一、非递归的算法

第一种算法思路如下：

第二种算法思路如下：

二、递归的算法

一、非递归的算法

第一种算法思路如下：

  1. 先判断链表L是否为空，空链表退出程序；
  2. 用p利用while循环从头到尾扫描单链表，pre指向 *p 结点的前驱；
  3. 在while循环中，用 if 语句判断是结点是否是要删除的结点，是的话就删除此结点并且pre->next指向p结点的后驱，否则让pre、p指向同步后移个结点。

时间复杂度：O(n)                空间复杂度：O(1)

  1. // 单链表的结点存储结构
  2.  
  3. typedef struct LNode{
  4.     ElemType data;           // 数据域
  5.     struct LNode *next;      // 结点域
  6. } LNode, *LinkList;

算法实现：

  1. void Del_x(LinkList L, ElemType x){
  2.     // L为带头结点的链表
  3.     LinkList p = L->next, pre = L, q;
  4.     if (p == NULL)
  5.     {
  6.         printf("链表为空！\n");
  7.         return;
  8.     }
  9.     while(p){
  10.         if (p->data == x) {
  11.             q = p;           // q指向要删除的结点
  12.             p = p->next;     // p->指向要删除结点的后驱
  13.             pre->next = p;   // q的前驱指向q的后驱
  14.             free(q);         // 释放q（需要删除的结点）
  15.         }
  16.         else{
  17.             pre = p;        // pre向下后移
  18.             p = p->next;    // p与pre同步向后移，这两步不能调换顺序
  19.         }
  20.     }
  21.     return;
  22. }

图解算法：

先看下面这个链表，咱们要删除 x = 2 的结点

 L指向头结点

pre开始指向头结点，p指向链表的第一个结点，通过while循环中的 if 语句判断，p->data \neq 2，故pre和q同步后移。

后移后p->data = 2，因此要删除这个结点，即指行while循环里面的 if 语句，q指向要删除的结点，

p指向要删除结点的后驱，pre不要移动。

 然后通过free()函数将 q 指向的空间释放，并且pre的后驱指向 p（即pre->next = p），此时链表没有 q指向的结点。

 然后再通过 if 语句判断，p->data \neq 2，pre 和 q 同步后移。

然后p->data = 2即要删除这个结点，p的后驱是空指针NULL，故最后 p = NULL，通过free()函数释放此结点，然后pre的后驱指向 p，即 pre->next = NULL。

然后p = NULL，循环结束，链表中无结点数据域等于2的结点，任务完成。

第二种算法思路如下：

  1. 利用尾插法建立单链表；
  2. p用来扫描L的所有结点，当其值不为x时，将其链接到L之后，否则将其释放。

时间复杂度：O(n)                空间复杂度：O(1)

算法实现：

  1. void Del_x(LinkList L, ElemType x){
  2.     LinkList p = L->next, r = L, q;
  3.     if ( p == NULL)
  4.     {
  5.         printf("链表为空！\n");
  6.         return;
  7.     }
  8.     while(p){
  9.         if (p->data != x){
  10.             r->next = p;  // p结点的值不为x，链接到L的尾部
  11.             r = p;        // 方便下次链接
  12.             p = p->next;   
  13.         }
  14.         else{
  15.             q = p;      // 保存要删除的结点
  16.             p = p->next;    // 指向要删除结点的后驱，继续扫描
  17.             free(q);       // 释放结点
  18.         }    
  19.     }
  20.     r->next = NULL;   // 插入结束后，尾结点的next域为NULL
  21.     return;
  22. }

图解算法：

 这个算法咱们可以这么理解，类似创建了新链表（在原链表上创建），然后往新链表插入结点的值不为x的结点，用的内存还是原来结点的内存（即指向的内存和原结点的地址一致），并不是新的分配的内存。和实际创建新链表（不在原链表上创建），通过复制结点后插入不同，复制插入的结点的地址不是原结点的地址（即指向的内存地址与原结点不一致），而是新分配的内存。

先看这个链表的初始情况

咱们为了更好的理解，可以将这个链表分为两个链表，一个为L指向头结点的链表，一个为p指向除头结点所有结点组成的链表 。

根据while循环的的 if 语句判断，p所指向的结点并不是要删除的结点，故p指向下一个节点，而刚才p指向的结点被链接到L所指向的链表上。

 r->next = p;  // p结点的值不为x，链接到L的尾部

 现在p指向的是要删除的结点，执行 if 语句的else部分，用q指向它，而p指向要删除结点的后驱。

 然后通过free()函数释放q所指向的结点。

此时p指向的结点不是要删除的结点，p后移，p之前的结点链接到L指向的链表。

 r->next = p;  // p结点的值不为x，链接到L的尾部

此时p指向的是要删除的结点，p向后移，并且q指向此结点。

通过free()函数释放q结点，此时p指向NULL，while循环结束，将L指向的链表最后结点的next指向NULL。

总结来说，就是把结点不是删除结点，就链接到L指向的链表，是要删除的结点通过free()函数释放。

二、递归的算法

算法思路如下：

  1. 找到基线条件（就是递归中止的条件），即链表为空，
  2. 找到递归条件，即每次递归离空链表更进一点
  3. 所以若链表L为空，递归函数 Del_x(L,x)什么也不做
  4. 若L->data = x, f(L,x)删除结点L，并且执行函数 Del_x(L->next, x)，进行下次递归。
  5. 若L->data \neq x，执行函数 Del_x(L->next, x)，进行下次递归。

算法实现：

1、C++代码实现

  1. // C++代码 LinkList &L，是一个引用
  2. void Del_x(LinkList &L, ElemType x){
  3.     // L是不带头结点的链表
  4.     LinkList p;
  5.     if (L == NULL)        // 递归出口
  6.         return;
  7.     if (L->data == x){
  8.         p = L;                // 删除L，并让L指向下一个结点
  9.         L = L->next;
  10.         free(p);
  11.         Del_x(L, x);  // 递归调用
  12.     }
  13.     else            // 若L指向的结点不为x
  14.         Del_x(L->next, x); // 递归调用
  15.     return; 
  16. }
  17.

2、C语言代码实现

  1. void Del_x(LinkList* head, ElemType x)
  2. {
  3.     // head为指向不带头结点链表的第一个结点的指针的指针
  4.     // head为二级指针，需要修改内存上保存的指向LinkList的地址
  5.     LinkList p;   // 保存要删除的结点地址
  6.     if (*head == NULL) 
  7.         return;        // 空链表，退出程序
  8.     if ((*head)->data == x) // 判断结点的值是否为x
  9.     {
  10.         p = *head;  // 保存要删除的结点
  11.         *head = p->next;   // 保存要删除的结点后驱地址
  12.         Del_x(head, x);    // 递归函数
  13.     }
  14.     else
  15.     {
  16.         head = &((*head)->next);    // 指向下一个结点的地址的地址
  17.         Del_x(head, x);
  18.     }
  19. }

这个算法要区分结构体指针和指向结构体指针的指针，可以看看我写的博客来了解结构体指针和指向结构体指针的区别。

结构体指针与指向结构体指针的区别

算法需要一个递归工作栈，深度为O(n)，时间复杂度为O(n)。

 测试程序：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4.  
  5. #define FLAG  -1
  6.  
  7. typedef int ElemType;
  8. typedef struct Node
  9. {
  10.     ElemType data;
  11.     struct Node* next;
  12. }LinkNode, * LinkList;
  13.  
  14. LinkList AddHead2(int flag);
  15. void ShowLinkList(LinkList head);
  16. int ListLength(LinkList head);
  17. bool Insert(LinkList head, ElemType x, int i, int ListLength);
  18. bool Delete(LinkList head, int i, int ListLength);
  19. int ShowMeanu();
  20. //void Del_x(ElemType x, LinkList head);
  21. void Del_x(LinkList* head, ElemType x);
  22.  
  23. int main(void)
  24. {
  25.     int choice;
  26.     LinkList head = (LinkList)malloc(sizeof(LinkNode));
  27.     head->next = NULL;
  28.     while (true)
  29.     {
  30.         choice = ShowMeanu();
  31.         switch (choice)
  32.         {
  33.         case 0:    exit(0);
  34.             break;
  35.         case 1:    head = AddHead2(FLAG);
  36.             break;
  37.         case 2:    ShowLinkList(head);
  38.             break;
  39.         case 3: {
  40.             int i, x;
  41.             printf("请输入你要插入结点的位置：");
  42.             scanf("%d", &i);
  43.             printf("请输入你要插入结点的数据域的值：");
  44.             scanf("%d", &x);
  45.             int length = ListLength(head);
  46.             Insert(head, x, i, length);
  47.         }
  48.               break;
  49.         case 4: {
  50.             int i;
  51.             printf("请输入你要插入结点的位置：");
  52.             scanf("%d", &i);
  53.             Delete(head, i, ListLength(head));
  54.         }
  55.               break;
  56.         case 5: {
  57.             int length;
  58.             length = ListLength(head);
  59.             printf("链表的长度为：%d\n");
  60.         }
  61.               break;
  62.         case 6: {
  63.             int x;
  64.             printf("请输入要删除所有结点为x的值：");
  65.             scanf("%d", &x);
  66.             LinkList p = &(head->next);
  67.             //Del_x(head, x);
  68.             Del_x(p, x);
  69.         }
  70.               break;
  71.         default:   printf("请输入恰当的值!!!!\n");
  72.         }
  73.     }
  74.     return 0;
  75. }
  76.  
  77. int ShowMeanu()
  78. {
  79.     int choice;
  80.     printf("欢迎来到链表测试功能！！！！！！\n");
  81.     printf("1.创建单链表              2.显示单链表中的结点\n");
  82.     printf("3.在链表i位置插入节点      4.删除链表第i个结点\n");
  83.     printf("5.单链表的表长            6.删除链表为x的所有结点\n");
  84.     printf("0.退出程序\n");
  85.     printf("请输入你想测试的功能序号：");
  86.     scanf("%d", &choice);
  87.     return choice;
  88. }
  89.  
  90. LinkList AddHead2(int flag)
  91. {
  92.     printf(" 输入 -1 停止创建单链表\n");
  93.     LinkList head, p, q;
  94.     head = (LinkList)malloc(sizeof(LinkNode));
  95.     head->next = NULL;
  96.     p = head;
  97.     ElemType x;
  98.     scanf("%d", &x);
  99.     while (x != flag)
  100.     {
  101.         q = (LinkList)malloc(sizeof(LinkNode));
  102.         q->data = x;
  103.         if (head->next == NULL)
  104.             head->next = q;
  105.         else
  106.             p->next = q;
  107.         p = q;
  108.         scanf("%d", &x);
  109.     }
  110.     if (p != NULL)
  111.         p->next = NULL;
  112.     return head;
  113. }
  114.  
  115. void ShowLinkList(LinkList head)
  116. {
  117.     LinkList p = head->next;
  118.     while (p != NULL)
  119.     {
  120.         printf("%d", p->data);
  121.         p = p->next;
  122.     }
  123.     printf("\n");
  124. }
  125.  
  126. int ListLength(LinkList head)
  127. {
  128.     int len = 0;
  129.     LinkList p = head;
  130.     while (p->next != NULL)
  131.     {
  132.         len++;
  133.         p = p->next;
  134.     }
  135.     return len;
  136. }
  137.  
  138. bool Insert(LinkList head, ElemType x, int i, int ListLength)
  139. {
  140.     LinkList p = head;
  141.     if (i > ListLength || p->next == NULL)
  142.         return false;
  143.     while (--i)
  144.         p = p->next;
  145.     LinkList q = (LinkList)malloc(sizeof(LinkNode));
  146.     q->data = x;
  147.     q->next = p->next;
  148.     p->next = q;
  149.     return true;
  150. }
  151.  
  152. bool Delete(LinkList head, int i, int ListLength)
  153. {
  154.     LinkList p = head;
  155.     if (i > ListLength || p->next == NULL)
  156.         return false;
  157.     while (--i)
  158.         p = p->next;
  159.     LinkList q = p->next;
  160.     p->next = q->next;
  161.     free(q);
  162.     return false;
  163. }
  164.  
  165. /*void Del_x(ElemType x, LinkList head)
  166. {
  167.     LinkList p = head->next, pre = head, q;
  168.     if (p == NULL)
  169.     {
  170.         printf("链表为空\n");
  171.         return;
  172.     }
  173.     while (p)
  174.     {
  175.         if (p->data == x)
  176.         {
  177.             q = p;
  178.             p = q->next;
  179.             pre->next = p;
  180.             free(q);
  181.         }
  182.         else
  183.         {
  184.             pre = p;
  185.             p = p->next;
  186.         }
  187.     }
  188.     return;
  189. }*/
  190.  
  191. /*void Del_x(ElemType x, LinkList L) {
  192.     LinkList p = L->next, r = L, q;
  193.     if (p == NULL)
  194.     {
  195.         printf("链表为空！\n");
  196.         return;
  197.     }
  198.     while (p) {
  199.         if (p->data != x) {
  200.             r->next = p;  // p结点的值不为x，链接到L的尾部
  201.             r = p;        // 方便下次链接
  202.             p = p->next;
  203.         }
  204.         else {
  205.             q = p;      // 保存要删除的结点
  206.             p = p->next;    // 指向要删除结点的后驱，继续扫描
  207.             free(q);       // 释放结点
  208.         }
  209.     }
  210.     r->next = NULL;   // 插入结束后，尾结点的next域为NULL
  211.     return;
  212. }*/
  213.  
  214. void Del_x(LinkList* head, ElemType x)
  215. {
  216.     LinkList p;
  217.     if (*head == NULL)
  218.         return;
  219.     if ((*head)->data == x)
  220.     {
  221.         p = *head;
  222.         *head = p->next;
  223.         Del_x(head, x);
  224.     }
  225.     else
  226.     {
  227.         head = &((*head)->next);
  228.         Del_x(head, x);
  229.     }
  230. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/444216
推荐阅读
相关标签

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

  

闽ICP备14008679号