qidao123.com ToB IT社区-企服评测·应用市场»论坛 › 软件与程序人生 › DevOps与敏捷开发 › 单链表的实现(数据结构)

单链表的实现(数据结构)

[复制链接]
发表于 2025-12-30 18:24:29 | 显示全部楼层 |阅读模式
一. 单链表的实现

我们在上一篇中简单的认识了链表的构成和结构，并打印出链表，那么本日就来详细实现一下单链表对于数据增长、删减、插入等。
接下来就是我们在链表中对于数据的增、删、插的实现，对于我们的链表来说在任何地方增长数据都须要来申请一个新的结点，起首呢，SLDatatype是我们更改int范例的名称之后得来的，SL是结构体的名称，我们先申请一个结构体巨细的新结点node，然后再将新结点中的x的值赋给data，再让新结点的next指向NULL，申请新结点的函数写好之后我们就来写关于数据的增、删、插等，以是我们直接先来完成申请新结点的代码：
  1. SLDatatype* SLBuyNode(SLDatatype x)
  2. {
  3.         SL* node = (SL*)malloc(sizeof(SL));
  4.         if (node == NULL)
  5.         {
  6.                 perror("malloc fail!");
  7.                 exit(1);
  8.         }
  9.         node->data = x;
  10.         node->next = NULL;
  11.         return node;
  12. }
复制代码
 尾插：

  1. //尾插函数
  2. void SLPuchBack(SL** pphead, SLDatatype x)
  3. {
  4.         //申请新结点
  5.         //*pphead-->&plist
  6.         SL* newnode = SLBuyNode(x);
  7.         if (*pphead == NULL)
  8.         {
  9.                 *pphead = newnode;
  10.         }
  11.         else
  12.         {
  13.         //尾结点-->新结点
  14.             SL* pcur = *pphead;//找尾结点
  15.             while (pcur->next)
  16.             {
  17.                 pcur = pcur->next;
  18.             }
  19.             pcur->next = newnode;
  20.         }
  22. }
  23. void SLTest01()
  24. {
  25.         SL* plist = NULL;
  26.         SLPuchBack(&plist, 1);
  27.         SLprintf(plist);
  28.         SLPuchBack(&plist, 2);
  29.         SLPuchBack(&plist, 3);
  30.         SLprintf(plist);
  31. }
  33. int main()
  34. {
  35.         SLTest01();
  36.         return 0;
  37. }
复制代码

在实现让任何代码之前，我们都因该将思绪理清楚，尾插该留意什么，怎么去是实现?起首肯定是要找到末了一个结点，pphead是我们的头结点，我们一直会将pphead赋给一个新的指针pcur，使用while循环找到末了一个结点，但是如果while内里是pcur的那我们不就直接跳出循环，那我们还怎么找末了一个结点呢？以是我们不如使用while(pcur->next)，也就是当我们pcur指向3的时间我们的next刚好指向的是NULL，克制了循环，刚好pcur还指向尾结点，然后我们在将newnode赋值给我们的末了一个结点。在上面的代码中我们要留意的一点是SLPuchBack函数中传入的是形参，这个时间我们要使用传值调用，由于如果使用传值调用的话，形参的改变并不影响实参，以是在测试函数SLTest01中传入的是&plist，然而plist自己就是一个指针，以是我们在SLPuchBack中要使用二级指针即**pphead。
 头插：对于头插就简单许多，我们只须要申请一个新的结点，然后将结点与本来的头结点毗连，在让pphead指向如今新的结点。
  1. //头插函数
  2. void SLPuchFront(SL** pphead, SLDatatype x)
  3. {
  4.         assert(pphead);
  5.         SL* newnode = SLBuyNode(x);
  6.         newnode->next = *pphead;
  7.         *pphead = newnode;
  8. }
复制代码

尾删：对于尾删我们并不能简单的将末了一个结点删除，由于如许会让前面一个指针变成野指针，可以把末了一个结点前面的结点的next指向NULL，然后将末了一个结点开释掉。
  1. //尾删函数
  2. void SLPopBack(SL** pphead)
  3. {
  4.         assert(pphead && *pphead);
  5.         //假如原本只有一个结点
  6.         if ((*pphead)->next == NULL)
  7.         {
  8.                 free(*pphead);
  9.                 *pphead = NULL;
  10.         }
  11.         else
  12.         {
  13.        SL* pcur = *pphead;
  14.            SL* front = NULL;
  15.            while (pcur->next)
  16.            {
  17.                   front = pcur;
  18.                   pcur = pcur->next;
  19.            }
  20.        front->next = NULL;
  21.            free(pcur);
  22.            pcur = NULL;
  23.         }
复制代码

头删： 
  1. //头删函数
  2. void SLPopFront(SL** pphead)
  3. {
  4.         assert(pphead && *pphead);
  5.         SL* pcur = (*pphead)->next;
  6.         free(*pphead);
  7.         *pphead = pcur;
  8. }
复制代码

 在指定位置之前插入数据：
  1. void SLInsertFront(SL** pphead, SL* pos, SLDatatype x)
  2. {
  3.         assert(pphead && pos);
  4.         SL* newnode = SLBuyNode(x);
  5.         SL* pcur = *pphead;
  6.         if (pos == *pphead)
  7.         {
  8.                 newnode->next = pos;
  9.                 *pphead = newnode;
  10.         }
  11.         else
  12.         {
  13.                 while (pcur->next != pos)
  14.                 {
  15.                         pcur = pcur->next;
  16.                 }
  17.                 newnode->next = pos;
  18.                 pcur->next = newnode;
  19.         }
  21. }
复制代码
 在指定位置之后插入数据：
  1. void SLInsertAfert(SL* pos, SLDatatype x)
  2. {
  3.         assert(pos);
  4.         SL* newnode = SLBuyNode(x);
  5.         newnode->next = pos->next;
  6.         pos->next = newnode;
  7. }
复制代码
 删除pos结点：
  1. void SLErase(SL** pphead, SL* pos)
  2. {
  3.         assert(pphead && *pphead);
  4.         assert(pos);
  5.         SL* pcur = *pphead;
  6.         if (pos == *pphead)
  7.         {
  8.                 SLPopFront(pphead);
  9.         }
  10.         else
  11.         {
  12.                 while (pcur->next != pos)
  13.                 {
  14.                         pcur = pcur->next;
  16.                 }
  17.                 pcur->next = pos->next;
  18.                 free(pos);
  19.                 pos = NULL;
  20.         }
  21.        
复制代码
 删除pos之后的结点：
  1. void SLEraseAfert(SL* pos)
  2. {
  3.         assert(pos&&pos->next);
  4.         SL* deal = pos->next;
  5.         pos->next = pos->next->next;
  6.         free(deal);
  7.         deal = NULL;
  8. }
复制代码
 烧毁链表：
  1. void SLDestroy(SL** pphead)
  2. {
  3.         SL* pcur = *pphead;
  4.         while (pcur)
  5.         {
  6.                 SL* next = pcur->next;
  7.                 free(pcur);
  8.                 pcur = next;
  9.         }
  10.         *pphead = NULL;
  11. }
复制代码
上面关于链表的指定位置插入、删除等算法，我们要留意的就是在我们更改链表中的数据的时间，要更改的这个数据会影响其他的数据吗？如果影响我们应该怎么做，提前设置好几个指针变量还是其他的办法，探求某一个结点的时间while循环的条件是什么，这些我们都要留意，上面已经给出较为详细的代码，各人可以参考，别的就是留意free指针之后肯定要将其置为空指针NULL，单链表完成之后我们就要拿一些算法题来练手，怎样使用单链表来完成一些算法题。
二. 算法题

移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/description/
   这个标题是移除链表元素，我们有两个思绪一个就是使用我们本来的单链表对指定位置的结点举行删除，尚有就是创建一个新的链表然后将符合的元素移到新的链表中，我们可以来实现第二中思绪： 创建一个新链表，遍历原链表，将不即是给定值  val  的节点依次添加到新链表中。
 
1. 创建新链表的哑节点（dummy node）：
- 目标是简化操纵，制止处理处罚新链表头节点为空的特殊情况。
- 比方，可以创建一个值为  0  的哑节点，将其  next  指针初始化为  null 。
2. 遍历原链表：
- 从原链表的头节点  head  开始遍历。
- 查抄当前节点的值是否即是  val 。
- 如果不即是  val ，则将该节点添加到新链表中。
3. 添加节点到新链表：
- 将原链表中不即是  val  的节点的  next  指针指向新链表的末了节点的  next 。
- 更新新链表的末了节点为该节点。
4. 返回新链表的头节点：
 - 新链表的头节点为哑节点的  next 。
 通过以上步调，就可以使用创建新链表的方法删除原链表中全部值为  val  的节点，并返回新的头节点。
   
  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. struct ListNode {
  5.     int val;
  6.     struct ListNode* next;
  7. };
  9. struct ListNode* createNode(int val) {
  10.     struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
  11.     newNode->val = val;
  12.     newNode->next = NULL;
  13.     return newNode;
  14. }
  16. struct ListNode* removeElements(struct ListNode* head, int val) {
  17.     struct ListNode* dummy = createNode(0);
  18.     struct ListNode* curr = dummy;
  19.     while (head) {
  20.         if (head->val!= val) {
  21.             curr->next = head;
  22.             curr = curr->next;
  23.         }
  24.         head = head->next;
  25.     }
  26.     curr->next = NULL;
  27.     return dummy->next;
  28. }
  30. void printList(struct ListNode* head) {
  31.     while (head) {
  32.         printf("%d -> ", head->val);
  33.         head = head->next;
  34.     }
  35.     printf("NULL\n");
  36. }
  38. void freeList(struct ListNode* head) {
  39.     struct ListNode* temp;
  40.     while (head) {
  41.         temp = head;
  42.         head = head->next;
  43.         free(temp);
  44.     }
  45. }
  46. int main() {
  47.     // 创建链表 1->2->6->3->4->5->6
  48.     struct ListNode* head = createNode(1);
  49.     head->next = createNode(2);
  50.     head->next->next = createNode(6);
  51.     head->next->next->next = createNode(3);
  52.     head->next->next->next->next = createNode(4);
  53.     head->next->next->next->next->next = createNode(5);
  54.     head->next->next->next->next->next->next = createNode(6);
  56.     int val = 6;
  57.     struct ListNode* newHead = removeElements(head, val);
  58.     printList(newHead);
  59.     freeList(newHead);
  60.     return 0;
  61. }
复制代码






免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金

本帖子中包含更多资源

您需要 登录 才可以下载或查看，没有账号？立即注册

×
回复

使用道具 举报

返回列表

卖不甜枣
+ 我要发帖

登录后关闭弹窗

登录参与点评抽奖  加入IT实名职场社区
去登录
快速回复 返回顶部 返回列表