4.10 在pos位置之后插入节点

我们实现了在pos位置之前插入节点之后，是不是觉得实现的很难受，这么麻烦，还要实现，这明显不合理啊。

在pos位置之后插入更加合适吧？这样我根本不需要遍历链表，我只需要让 新节点newnode 和 pos 位置的下一个节点链接，然后将pos位置的next变为我的新节点即可。

// 在pos位置之后插入节点
void SListInsertAfter(SLTNode* pos, SLTDateType x)
{
  assert(pos); // 避免pos传参传错
  SLTNode* newnode = BuyListNode(x);
  newnode->next = pos->next;
  pos->next = newnode; 
}

4.11 删除pos位置的节点

删除pos位置的节点，需要考虑此时链表是否为空，但这只是一部分，只需要用断言处理一下就好。

而我们着重处理的为，头删和多个节点删除的情况。

如果是头删，那么删除的就是第一个节点，那么此时就需要将头变为pos->next，并且释放pos位置。头删情况也完美处理了单个节点删除时的情况。

如果是多个节点，那么就需要找到pos的前一个位置，将 pos 前一个位置(prev)的 next 链接为我当前 pos 的 next。然后释放我的pos节点。

// 删除pos位置的节点
void SListErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pos);
  // 处理头删
  if (*pphead == pos)
  {
    *pphead = pos->next;
    free(pos);
  }
  // 处理其他情况
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    pos = NULL;
  }
}

4.12 删除pos位置之后的节点

和在pos位置之前插入一样，我们发现删除pos位置的节点，也很麻烦。因为需要找pos的前一个位置，所以这种设计也比较麻烦。

所以有时我们会删除pos位置之后的节点，这样就很方便了。

既然要删除pos位置之后的节点，那么我就需要将 pos 位置的节点和pos位置的 next 的 next 链接起来。

那么我们首先用 next 拷贝记录一下 pos->next ，然后，再将pos->next赋值为next->next，也就是pos往后的两个节点。最后释放next位置的节点即可。

注意：我pos位置的下一个节点不能是尾结点后面的节点！

// 删除指定pos位置后的一个节点
void SListEraseAfter(SLTNode** pphead, SLTNode* pos)
{
  assert(pos);
  assert(pos->next);// 删除的不能是尾结点后面的位置
  SLTNode* next = pos->next;// 拷贝pos的下一个节点
  pos->next = next->next;// 将pos的next变为下一个节点的next
  free(next);// 释放之前pos的下一个节点
  next = NULL;
}

4.13 打印

打印整个链表，只需要遍历链表，控制好循环的停止条件：

// 打印
void SListPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}

4.14 销毁

销毁链表，如果仅仅释放我的*pphead，可行吗？这当然不可行。

因为单链表是由不同地址的节点串联起来的。它不像数组，存储连续，只要释放起始位置。

如果我仅仅释放*pphead，那么只释放了我的第一个节点，后面的节点没释放，函数调用结束后，这些节点也找不到了。所以我们需要逐个销毁。

首先，使用 cur 拷贝头部位置。然后使用循环迭代。迭代过程中，需要记住我的 cur->next ，否则 cur 被释放后，无法找到下一个节点，然后逐个释放就可以了。

注意：当销毁后，记得把*pphead 置空，防止销毁链表后对链表误操作而导致的野指针问题。

// 销毁
void SListDestory(SLTNode** pphead)
{
  SLTNode* cur = *pphead;
  while (cur)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL; // 置空
}

5. 完整代码

SList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
  int data;
  struct SListNode* next;
}SLTNode;
// 打印
void SListPrint(SLTNode* phead);
// 尾插
void SListPushBack(SLTNode** pphead, SLTDateType x);
// 头插
void SListPushFront(SLTNode** pphead, SLTDateType x);
// 尾删
void SListPopBack(SLTNode** pphead);
// 头删
void SListPopFront(SLTNode** pphead);
// 查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x);
// 在pos位置之前插入一个节点 
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
// 在pos位置之后插入一个节点
void SListInsertAfter(SLTNode* pos, SLTDateType x);
// 在指定位置删除一个节点
void SListErase(SLTNode** pphead, SLTNode* pos);
// 删除指定pos位置后的一个节点
void SListEraseAfter(SLTNode** pphead, SLTNode* pos);
// 销毁
void SListDestory(SLTNode** pphead);

SList.c

#define _CRT_SECURE_NO_WARNINGS 1 
#include "SList.h"
// 创建新节点
SLTNode* BuyListNode(SLTDateType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);// 内存申请失败，说明几乎没有空间了，直接退出程序
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}
// 打印
void SListPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
// 尾插
void SListPushBack(SLTNode** pphead, SLTDateType x)
{ // 建立新节点
  SLTNode* newnode = BuyListNode(x);
  // 链表没有节点，给新节点
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    // 找到尾结点
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    // 尾结点链接新节点
    tail->next = newnode;
  } 
}
// 头插
void SListPushFront(SLTNode** pphead, SLTDateType x)
{
  assert(pphead);
  SLTNode* newnode = BuyListNode(x);
  newnode->next = *pphead;// 新节点链接之前plist的地址
  *pphead = newnode;// 头指针更改为newnode
}
// 尾删
void SListPopBack(SLTNode** pphead)
{
  // 温柔处理
  /*if (*pphead == NULL)
  {
    return;
  }*/
  // 暴力处理 一个节点
  assert(*pphead);
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else// 两个及以上节点
  {
    // plan1
    SLTNode* prev = NULL;// 记录上一个节点的地址
    SLTNode* tail = *pphead;
    //while (tail->next != NULL)// 计算逻辑表达式的值为真或假决定循环是否继续执行
    while (tail->next)// 当值为空指针，被隐式转换为0，结束循环
    {
      prev = tail;
      tail = tail->next;
    }
    free(tail);// 释放尾结点空间
    tail = NULL;
    // 将前一个节点的next置空
    prev->next = NULL;
  }
  // plan2：
  //SLTNode* tail = *pphead;
  //while (tail->next->next)// 如果当前tail的next的地址访问下一个next为空，则停止
  //{
  //  tail = tail->next;// 将尾结点赋值为最后一个节点的next
  //}
  //free(tail->next);// 释放最后一个节点
  //tail->next = NULL;// 最后一个节点置空
}
// 头删
void SListPopFront(SLTNode** pphead)
{
  // 处理空链表
  assert(*pphead);  
  // 处理1个及以上节点
  SLTNode* newpphead = (*pphead)->next;
  free(*pphead);
  *pphead = newpphead;
}
// 查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    else
    {
      cur = cur->next;
    }
  }
  return NULL;// 没找到
}
// 在pos位置之前插入节点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
  assert(pos);
  SLTNode* newnode = BuyListNode(x);
  // 头插情况特殊处理
  if (*pphead == pos)
  {
    newnode->next = *pphead;// newnode链接头
    *pphead = newnode;// 头变为newnode
  }
  // 其他位置插入
  else
  {
    // 找到pos前一个位置
    SLTNode* posPrev = *pphead;
    while (posPrev->next != pos)
    {
      posPrev = posPrev->next;
    }
    posPrev->next = newnode;// 将pos前一个位置链接到newnode
    newnode->next = pos;// newnode连接到pos
  }
}
// pos不太适合在节点前插入，适合在节点后插入
// 在pos后面 插入节点
void SListInsertAfter(SLTNode* pos, SLTDateType x)
{
  assert(pos);
  SLTNode* newnode = BuyListNode(x);
  newnode->next = pos->next;
  pos->next = newnode; 
}
// 删除pos位置的节点
void SListErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pos);
  // 处理头删
  if (*pphead == pos)
  {
    *pphead = pos->next;
    free(pos);
    // 直接调用头删
    // SListPopFront(pos);
  }
  // 处理其他情况
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    pos = NULL;
  }
}
// 删除指定pos位置后的一个节点
void SListEraseAfter(SLTNode** pphead, SLTNode* pos)
{
  assert(pos);
  assert(pos->next);// 删除的不能是尾结点后面的位置
  SLTNode* next = pos->next;// 拷贝pos的下一个节点
  pos->next = next->next;// 将pos的next变为下一个节点的next
  free(next);// 释放之前pos的下一个节点
  next = NULL;
}
void SListDestory(SLTNode** pphead)
{
  SLTNode* cur = *pphead;
  while (cur)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
    // 这里一定要置空，放置销毁链表后被误使用
  *pphead = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1 
#include "SList.h"
// 测试尾插、带节点的头插
void TestList1()
{
  SLTNode* plist = NULL;
  SListPushBack(&plist, 1);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);
  SListPushBack(&plist, 5);
  SListPrint(plist);
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPrint(plist);
}
// 测试头插、尾删
void TestList2()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPrint(plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  //SListPopBack(&plist);
  SListPrint(plist);
}
// 测试头删
void TestList3()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
}
//void TestList4()
//{
//  SLTNode* plist = NULL;
//
//  SListPushFront(&plist, 1);
//  SListPushFront(&plist, 2);
//  SListPushFront(&plist, 3);
//  SListPushFront(&plist, 2);
//  SListPushFront(&plist, 5);
//
//  SLTNode* pos = SListFind(plist, 2);
//  int i = 1;
//  while (pos)
//  {
//    printf("第%d个pos节点：%p->%d\n", i++, pos, pos->data); 
//    pos = SListFind(pos->next, 2);
//  }
//
//  // 修改 3->30
//  pos = SListFind(plist, 3);
//  if (pos)
//  {
//    pos->data = 30;
//  }
//  SListPrint(plist);
//}
void TestList5()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 5);
  // 3前面插入一个30
  SLTNode* pos = SListFind(plist, 3);
  if (pos)
  {
    SListInsert(&plist, pos, 30);
  }
  SListPrint(plist);
  // 5前面插入一个10
  pos = SListFind(plist, 5);
  if (pos)
  {
    SListInsert(&plist, pos, 10);
  }
  SListPrint(plist);
}
int main()
{
  //TestList1();
  //TestList2();
  //TestList3();
  TestList5();
  return 0;
}

到这里本篇博客就到此结束了，仔细阅读这篇文章，你会发现，链表其实也没有那么难！

但是光看懂了还不够，链表是一个面试常考点，所以是十分重要的！于是在接下来几期，anduin 会带着大家一起刷链表的OJ题，多写多练，手撕链表~

更多精彩内容敬请期待~

如果觉得anduin写的还不错的话，还请一键三连！如有错误，还请指正！

我是anduin，一名C语言初学者，我们下期见！

【数据结构】链表其实并不难 —— 手把手带你实现单链表2

4.10 在pos位置之后插入节点

4.11 删除pos位置的节点

4.12 删除pos位置之后的节点

4.13 打印

4.14 销毁

5. 完整代码

SList.h

SList.c

test.c

热门文章

最新文章

相关课程

相关电子书