21ic电子技术开发论坛 › 单片机与嵌入式系统 › 芯源CW32 MCU › 单链表知识
返回列表 发新帖我要提问

[软件资料] 单链表知识

[复制链接]
4570|11
 楼主| jf101 发表于 2024-4-7 12:37 | 显示全部楼层 |阅读模式
struct, Tru, TI, unsigned, TE, BSP
所谓链表，就是由一个个「结点」组成的一个数据结构。每个结点都有「数据域」和「指针域」组成。其中数据域用来存储你想要存储的信息，而指针域用来存储下一个结点的地址。如图：

1.png

当然，链表最前面还有一个头指针，用来存储头结点的地址。

这样一来，链表中的每一个结点都可以不用挨个存放，因为有了指针把他们串起来。因此结点放在哪都无所谓，反正指针总是能够指向下一个元素。我们只需要知道头指针，就能够顺藤摸瓜地找到整个链表。

因此对于学籍数据库来说，我们只需要在Info结构体中加上一个指向自身类型的成员即可：

复制
  1. <p>struct Info</p><p>{</p><p>    unsigned long identifier;</p><p>    char name[20];</p><p>    struct Date date;</p><p>    unsigned int years;</p><p>    struct Info* next;</p><p>};</p>


回复

收藏 举报

相关帖子
 楼主| jf101 发表于 2024-4-7 12:38 | 显示全部楼层

1、在单链表中插入元素

头插法
这种每次都将数据插入单链表的头部（头指针后面）的插入法就叫头插法。

如果要把学生信息加入到单链表，可以这么写：

复制
  1. void addInfo(struct Info** students)//students是头指针
    

  2. {
    

  3.     struct Info* info, *temp;
    

  4.     info = (struct Info*)malloc(sizeof(struct Info));
    

  5.     if (info == NULL)
    

  6.     {
    

  7.         printf("内存分配失败！\n");
    

  8.         exit(1);
    

  9.     }
    

  10.     
    

  11.     getInput(info);
    

  12.     
    

  13.     if (*students != NULL)
    

  14.     {
    

  15.         temp = *students;
    

  16.         *students = info;
    

  17.         info->next = temp;
    

  18.     }
    

  19.     else
    

  20.     {
    

  21.         *students = info;
    

  22.         info->next = NULL;
    

  23.     }
    

  24. }

❝
由于students存放的是头指针，因此我们需要传入它的地址传递给函数，才能够改变它本身的值。而students本身又是一个指向Info结构体的指针，所以参数的类型应该就是struct Info**。

❞
往单链表里面添加一个结点，也就是先申请一个结点，然后判断链表是否为空。如果为空，那么直接将头指针指向它，然后next成员指向NULL。若不为空，那么先将next指向头指针原本指向的结点，然后将头指针指向新结点即可。

那么，打印链表也变得很简单：

复制
  1. void printStu(struct Info* students)
    

  2. {
    

  3.     struct Info* info;
    

  4.     int count = 1;
    

  5.     
    

  6.     info = students;
    

  7.     while (book != NULL)
    

  8.     {
    

  9.         printf("Student%d:\n", count);
    

  10.         printf("姓名：%s\n", info->name);
    

  11.         printf("学号：%d\n", info->identifier);
    

  12.         info = info->next;
    

  13.         count++;
    

  14.     }
    

  15. }

想要读取单链表里面的数据，只需要迭代单链表中的每一个结点，直到next成员为NULL，即表示单链表的结束。

最后，当然还是别忘了释放空间：

复制
  1. void releaseStu(struct Info** students)
    

  2. {
    

  3.     struct Info* temp;
    

  4.     
    

  5.     while (*students != NULL)
    

  6.     {
    

  7.         temp = *students;
    

  8.         *students = (*students)->next;
    

  9.         free(temp);
    

  10.     }
    

  11. }

尾插法
与头插法类似，尾插法就是把每一个数据都插入到链表的末尾。

复制
  1. void addInfo(struct Info** students)
    

  2. {
    

  3.     struct Info* info, *temp;
    

  4.     info = (struct Info*)malloc(sizeof(struct Info));
    

  5.     if (info == NULL)
    

  6.     {
    

  7.         printf("内存分配失败！\n");
    

  8.         exit(1);
    

  9.     }
    

  10.     
    

  11.     getInput(info);
    

  12.     
    

  13.     if (*students != NULL)
    

  14.     {
    

  15.         temp = *students;
    

  16.         *students = info;
    

  17.         //定位到链表的末尾的位置
    

  18.         while (temp->next != NULL)
    

  19.         {
    

  20.             temp = temp->next;
    

  21.         }
    

  22.         //插入数据
    

  23.         temp->next = info;
    

  24.         info->next = temp;
    

  25.     }
    

  26.     else
    

  27.     {
    

  28.         *students = info;
    

  29.         info->next = NULL;
    

  30.     }
    

  31. }

这么一来，程序执行的效率难免要降低很多，因为每次插入数据，都要先遍历一次链表。如果链表很长，那么对于插入数据来说就是一次灾难。不过，我们可以给程序添加一个指针，让它***都指向链表的尾部，这样一来，就可以用很少的空间换取很高的程序执行效率。

代码更改如下：

复制
  1. void addInfo(struct Info** students)
    

  2. {
    

  3.     struct Info* info, *temp;
    

  4.     static struct Info* tail;//设置静态指针
    

  5.     info = (struct Info*)malloc(sizeof(struct Info));
    

  6.     if (info == NULL)
    

  7.     {
    

  8.         printf("内存分配失败！\n");
    

  9.         exit(1);
    

  10.     }
    

  11.     
    

  12.     getInput(info);
    

  13.     
    

  14.     if (*students != NULL)
    

  15.     {
    

  16.         tail->next = info;
    

  17.         info->next = NULL;
    

  18.     }
    

  19.     else
    

  20.     {
    

  21.         *students = info;
    

  22.         info->next = NULL;
    

  23.     }
    

  24. }
回复

收藏 举报

 楼主| jf101 发表于 2024-4-7 12:39 | 显示全部楼层

2、搜索单链表

单链表是我们用来存储数据的一个容器，那么有时候需要快速查找信息就需要开发相关搜索的功能。比如说输入学号，查找同学的所有信息。

复制
  1. struct Info *searchInfo(struct Info* students, long* target)
    

  2. {
    

  3.     struct Info* info;
    

  4.     info = students;
    

  5.     while (info != NULL)
    

  6.     {
    

  7.         if (info->identifier == target)
    

  8.         {
    

  9.             break;
    

  10.         }
    

  11.         info = info->next;
    

  12.     }
    

  13.     
    

  14.     return book;
    

  15. };
    


  16. 

  17. void printInfo(struct Info* info)
    

  18. {
    

  19.     ...
    

  20. }
    

  21. ...
    


  22. 

  23. int main(void)
    

  24. {
    

  25.     ...
    

  26.     printf("\n请输入学生学号：");
    

  27.     scanf("%d", input);
    

  28.     info = searchInfo(students, input);
    

  29.     if (info == NULL)
    

  30.     {
    

  31.         printf("抱歉，未找到相关结果！\n");
    

  32.     }
    

  33.     else
    

  34.     {
    

  35.         do
    

  36.         {
    

  37.             printf("相关结果如下：\n");
    

  38.             printInfo(book);
    

  39.         } while ((info = searchInfo(info->next, input)) != NULL);
    

  40.     }
    

  41.     
    

  42.     releaseInfo(...);
    

  43.     return 0;
    

  44. }

回复

收藏 举报

 楼主| jf101 发表于 2024-4-7 12:40 | 显示全部楼层
3、插入结点到指定位置

到了这里，才体现出链表真正的优势。

设想一下，如果有一个有序数组，现在要求你去插入一个数字，插入完成之后，数组依然保持有序。你会怎么做？

没错，你应该会挨个去比较，然后找到合适的位置（当然这里也可以使用二分法，比较节省算力），把这个位置后面的所有数都往后移动一个位置，然后将我们要插入的数字放入刚刚我们腾出来的空间里面。

你会发现，这样的处理方法，经常需要移动大量的数据，对于程序的执行效率来说，是一个不利因素。那么链表，就无所谓。反正在内存中，链表的存储毫无逻辑，我们只需要改变指针的值就可以实现链表的中间插入。

复制
  1. //Example 03
    

  2. #include <stdio.h>
    

  3. #include <stdlib.h>
    


  4. 

  5. struct Node
    

  6. {
    

  7.     int value;
    

  8.     struct Node* next;
    

  9. };
    


  10. 

  11. void insNode(struct Node** head, int value)
    

  12. {
    

  13.     struct Node* pre;
    

  14.     struct Node* cur;
    

  15.     struct Node* New;
    


  16. 

  17.     cur = *head;
    

  18.     pre = NULL;
    


  19. 

  20.     while (cur != NULL && cur->value < value)
    

  21.     {
    

  22.         pre = cur;
    

  23.         cur = cur->next;
    

  24.     }
    


  25. 

  26.     New = (struct Node*)malloc(sizeof(struct Node));
    

  27.     if (New == NULL)
    

  28.     {
    

  29.         printf("内存分配失败！\n");
    

  30.         exit(1);
    

  31.     }
    

  32.     New->value = value;
    

  33.     New->next = cur;
    


  34. 

  35.     if (pre == NULL)
    

  36.     {
    

  37.         *head = New;
    

  38.     }
    

  39.     else
    

  40.     {
    

  41.         pre->next = New;
    

  42.     }
    

  43. }
    


  44. 

  45. void printNode(struct Node* head)
    

  46. {
    

  47.     struct Node* cur;
    


  48. 

  49.     cur = head;
    

  50.     while (cur != NULL)
    

  51.     {
    

  52.         printf("%d ", cur->value);
    

  53.         cur = cur->next;
    

  54.     }
    

  55.     putchar('\n');
    

  56. }
    


  57. 

  58. int main(void)
    

  59. {
    

  60.     struct Node* head = NULL;
    

  61.     int input;
    


  62. 

  63.     printf("开始插入整数...\n");
    

  64.     while (1)
    

  65.     {
    

  66.         printf("请输入一个整数，输入-1表示结束：");
    

  67.         scanf("%d", &input);
    

  68.         if (input == -1)
    

  69.         {
    

  70.             break;
    

  71.         }
    

  72.         insNode(&head, input);
    

  73.         printNode(head);
    

  74.     }
    


  75. 

  76.     return 0;
    

  77. }

运行结果如下：

复制
  1. //Consequence 03
    

  2. 开始插入整数...
    

  3. 请输入一个整数，输入-1表示结束：4
    

  4. 4
    

  5. 请输入一个整数，输入-1表示结束：5
    

  6. 4 5
    

  7. 请输入一个整数，输入-1表示结束：3
    

  8. 3 4 5
    

  9. 请输入一个整数，输入-1表示结束：6
    

  10. 3 4 5 6
    

  11. 请输入一个整数，输入-1表示结束：2
    

  12. 2 3 4 5 6
    

  13. 请输入一个整数，输入-1表示结束：5
    

  14. 2 3 4 5 5 6
    

  15. 请输入一个整数，输入-1表示结束：1
    

  16. 1 2 3 4 5 5 6
    

  17. 请输入一个整数，输入-1表示结束：7
    

  18. 1 2 3 4 5 5 6 7
    

  19. 请输入一个整数，输入-1表示结束：-1
回复

收藏 举报

 楼主| jf101 发表于 2024-4-7 12:41 | 显示全部楼层

4、删除结点

删除结点的思路也差不多，首先修改待删除的结点的上一个结点的指针，将其指向待删除结点的下一个结点。然后释放待删除结点的空间。

复制
  1. ...
    

  2. void delNode(struct Node** head, int value)
    

  3. {
    

  4.     struct Node* pre;
    

  5.     struct Node* cur;
    

  6.     
    

  7.     cur = *head;
    

  8.     pre = NULL;
    

  9.     while (cur != NULL && cur->value != value)
    

  10.     {
    

  11.         pre = cur;
    

  12.         cur = cur->next;
    

  13.     }
    

  14.     if (cur == NULL)
    

  15.     {
    

  16.         printf("未找到匹配项!\n");
    

  17.         return ;
    

  18.     }
    

  19.     else
    

  20.     {
    

  21.         if (pre == NULL)
    

  22.         {
    

  23.             *head = cur->next;
    

  24.         }
    

  25.         else
    

  26.         {
    

  27.             pre->next = cur->next;
    

  28.         }
    

  29.         free(cur);
    

  30.     }
    

  31. }

回复

收藏 举报

szt1993 发表于 2024-4-10 12:52 | 显示全部楼层
链表最前面还有一个头指针，用来存储头结点的地址。
回复

收藏 举报

小夏天的大西瓜 发表于 2024-4-10 13:52 | 显示全部楼层
链表就是由一个个「结点」组成的一个数据结构
回复

收藏 举报

中国龙芯CDX 发表于 2024-4-10 15:21 | 显示全部楼层
链表的增删改查都是基本操作，还需要多加熟练
回复

收藏 举报

 楼主| jf101 发表于 2024-4-14 15:21 | 显示全部楼层
中国龙芯CDX 发表于 2024-4-10 15:21
链表的增删改查都是基本操作，还需要多加熟练

非常正确
回复

收藏 举报

小小蚂蚁举千斤 发表于 2024-4-15 09:53 | 显示全部楼层
链表是不是跟数据库的做法差不多？
回复

收藏 举报

OKAKAKO 发表于 2024-4-19 18:46 | 显示全部楼层
链表中的每一个结点都可以不用挨个存放，因为有了指针把他们串起来。
回复

收藏 举报

星辰大海不退缩 发表于 2024-4-21 12:20 | 显示全部楼层
其中数据域用来存储你想要存储的信息，而指针域用来存储下一个结点的地址。
回复

收藏 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则

jf101

262

主题

1929

帖子

3

粉丝
快速回复 在线客服 返回列表 返回顶部