＜数据结构＞单向链表-阿里云开发者社区

一、对比顺序表

在上一节中，我们学习了顺序表，已经深知其优缺点，如下：

优点：

连续物理空间，方便下标随机访问

缺点：

插入数据，空间不足时要扩容，扩容有性能消耗

头部或者中间位置插入删除数据，需要挪动数据，效率较低

增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。若每次扩容扩少一点，则会导致频繁扩容，频繁扩容同样也会有性能消耗。

综合顺序表的缺点，我们可以总结出以下结论：顺序表不能按需申请和释放空间，无法做到存一个数据申请一块空间，删除一个数据释放一块空间。

基于顺序表的缺点，就设计出了链表结构。正文开始：

二、概念

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表的结构有点类似于火车，火车的每一节车厢都由插销，和钩子链接起来

现在链表想要实现按需索取，那该如何管理呢？前文顺序表是有一个指针指向第一个数据的位置，就可以了，因为顺序表是连续存放的知道第一个，就知道第i个，而现在链表是要一个数据就malloc一个，不是物理上的空间连续了。

其实链表的管理很简单，需要一个指针指向第一个数据的节点，为了能够找到下一个数据，则需要在此节点再存一个指针，指向的是下一个数据的节点的地址，如果没有下一个节点，则为空NULL

画图解释：

代码演示：

int main()
{
  SListNode* slist = NULL;
  SListNode* n1 = malloc(sizeof(SListNode));
  SListNode* n2 = malloc(sizeof(SListNode));
  SListNode* n3 = malloc(sizeof(SListNode));
  n1->data = 1;
  n2->data = 2;
  n3->data = 3;
  n1->next = n2;
  n2->next = n3;
  n3->next = NULL;
  slist = n1;
  return 0;
}

我们根据上述代码进行F10调试来观察下单链表的形成过程：上述所画的图是逻辑结构，就是理想化结构，实际上是没有箭头指向的，为了方便理解才画出逻辑结构，但实际上操作的时候靠的是物理结构。注意：

从上图中可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续

现实中的节点一般都是从堆上申请出来的

从堆上申请的空间，是按照一定策略来分配的，两次申请的空间可能连续，也可能不连续

链表是不需要进行初始化的，因为链表在最开始为空的时候是没有节点的

三、必备工作

3.1、创建单链表结构

SList.h 文件：

typedef int SLTDataType; //方便以后存储其它类型数据，本文以int为例
//创建单链表结构
typedef struct SListNode
{
  SLTDataType data; //值
  struct SListNode* next; //存储下一个节点的地址
}SListNode, SLN;

3.2、动态申请节点

因为在后续的尾插和头插等操作时，需要链接这个新加进来的数据，所以需要申请一个节点，以此将新添加的数据链接起来

SList.c 文件：
SListNode* BuySListNode(SLTDataType x)
{
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  else
  {
    newnode->data = x;
    newnode->next = NULL;
  }
  return newnode;
}

3.3、单链表打印

思想：

链表可以为空，一个数据都没有，所以无需要assert断言。打印链表，首先要拿到第一个节点的地址，定义一个cur指针指向phead，当cur不为NULL，依次打印链表的数据，并将cur赋值为下一个节点的地址

SList.h 文件：
//打印单链表
void SListPrint(SListNode* phead);

SList.c 文件：

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

Test.c 文件：

int main()
{
  SListNode* slist = NULL;
  SListNode* n1 = malloc(sizeof(SListNode));
  SListNode* n2 = malloc(sizeof(SListNode));
  SListNode* n3 = malloc(sizeof(SListNode));
  n1->data = 1;
  n2->data = 2;
  n3->data = 3;
  n1->next = n2;
  n2->next = n3;
  n3->next = NULL;
  slist = n1;
  SListPrint(slist);
  return 0;
}

效果如下：

3.4、销毁单链表

思想：

一个一个数据释放，与顺序表不同。释放后别忘记把slist置为空

SList.h 文件：
//销毁单链表
void SListDestroy(SListNode** pphead);

SList.c 文件：

//销毁单链表
void SListDestroy(SListNode** pphead)
{
  assert(pphead);
  SListNode* cur = *pphead;
  while (cur)
  {
    SListNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}

四、增删查改

4.1、插入数据

头插

思想：

头插的过程比后文的尾插相对简单点，它不需要像尾插一样找到尾部才能实现节点的链接，头插只需要将slist指向新头插的节点的地址，然后再把该节点指向原第一个数据即可。但是要注意头插同样需要像后文尾插一样传地址，因为形参的改变不会影响实参。

并且这里需要assert断言pphead，因为slist的地址pphead是不能为空的

画图演示（逻辑结构）：

SList.h 文件：

//头插
void SListPushFront(SListNode** pphead, SLTDataType x);

SList.c 文件：

//头插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
  assert(pphead);
  SListNode* newnode = BuySListNode(x); //创建一个新的节点
  newnode->next = *pphead;
  *pphead = newnode;
}

画图演示（物理结构）： Test.c 文件：

int main()
{
  SListNode* slist = NULL;
  for (int i = 0; i < 10; i++)
  {
    SListPushBack(&slist, i); //尾插10个数据
  }
  for (int i = -5; i < 0; i++)
  {
    SListPushFront(&slist, i); //头插5个数据
  }
  SListPrint(slist); //打印
  return 0;
}

效果如下：尾插

思想：

尾插要分两种情况，本身为空和不为空。

如果本身为空，则把新开的节点给phead

如果本身不为空，则需要将该新加的数据链接到原数据的最后一个节点处，此时就需要用遍历来找到原链表中的最后一个节点，只要创建一个指针变量tail指向phead，循环判断的tail->next是否为空，在为空时，循环自动停止，此时tail指向的就是原链表的最后一个节点

画图演示：

注意：

形参是实参的临时拷贝，形参的改变不影响实参，这里要改变slist，phead是slist的一份临时拷贝，phead的改变不影响slist，所以要传slist的地址，而slist本身就是指针，所以要传指针的地址，那么就要用二级指针来接收。

这里一定要assert断言pphead，pphead是一定不能为空的，哪怕链表是空，slist是地址，slist的地址pphead不能为空

SList.h 文件：

//尾插
void SListPushBack(SListNode** pphead, SLTDataType x);

SList.c 文件：

//尾插
void SListPushBack(SListNode** pphead, SLTDataType x) 
{
  assert(pphead);// pphead是一定不能为空的，哪怕链表是空，slist是地址，slist的地址不能为空
  SListNode* newnode = BuySListNode(x);
  if (*pphead == NULL) //pphead就是slist的地址，*pphead就是slist本身
  {
    *pphead = newnode;
  }
  else
  {
    //找尾
    SListNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}

Test.c 文件：

int main()
{
  SListNode* slist = NULL;
  for (int i = 0; i < 10; i++)
  {
    SListPushBack(&slist, i);
  }
  SListPrint(slist);
  return 0;
}

效果如下：

在pos位置前插入x

思想：

这里pos是节点的指针，而pos是通过SListFind函数找到的，比如想在3的节点前插入30，必须得找到pos的前一个节点，才能将链表的节点顺次链接起来，跟前文的尾插一样需要找尾，我们可以顶一个指针变量prev，依次遍历prev，如果它的next=pos就停止，不等于则继续，找到后创建一个新节点，实现节点顺次链接。当然，上述情况仅限于pos不在头节点处，如果在头节点处，则需另加讨论，因为此时prev就是NULL了，但此时又相当于头插，仅需调用头插函数即可

画图演示：

SList.h 文件：

//在pos位置之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);

SList.c 文件：

//在pos位置之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
  assert(pphead);
  assert(pos);
  //1、pos是第一个节点
  //2、pos不是第一个节点
  if (pos == *pphead)
  {
    SListPushFront(pphead, x);
  }
  else
  {
    SListNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SListNode* newnode = BuySListNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}

Test.c 文件：

int main()
{
  SListNode* slist = NULL;
  for (int i = 1; i < 4; i++)
  {
    SListPushBack(&slist, i); //尾插3个数据
  }
  SListPrint(slist); //打印
  SListNode* pos = SListFind(slist, 3); 
  if (pos != NULL)
  {
    SListInsert(&slist, pos, 300);
  }
  SListPrint(slist); //打印
  pos = SListFind(slist, 1);
  if (pos != NULL)
  {
    SListInsert(&slist, pos, 100);
  }
  SListPrint(slist); //打印
  return 0;
}

效果如下：在pos位置后插入x

思想：

其实单链表应该在pos位置后插入，因为这样就不需要传头pphead了。有两种方案，第一用next来记录pos的下一个节点，再创建一个新节点，让pos的下一个节点指向newnode，再让newnode的下一个节点指向next。第二不定义next，将newnode的下一个节点指向pos的下一个节点，再把pos的下一个节点指向newnode，这二者顺序不能颠倒。

SList.h 文件：

//在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x);

SList.c 文件：

//在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
  assert(pos);
  //法一：
  SListNode* next = pos->next;
  SListNode* newnode = BuySListNode(x);
  pos->next = newnode;
  newnode->next = next;
  /*
  法二：
  SListNode* newnode = BuySListNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
  */
}

测试结构与过程与上文在pos之前插入x一样，这里不过多赘述。

4.2、删除数据

头删

思想：

头删是要分类的，第一种是没有节点，本身就为空，直接返回即可。第二种是存在节点，可以创建一个指针变量next来保存第一个节点的下一个节点，然后将next赋给*pphead即可，但是要注意把第一个节点给释放掉。

画图演示：

SList.h 文件：

1. //头删
2. void SListPopFront(SListNode** pphead);

SList.c 文件：

//销毁单链表
void SListDestroy(SListNode** pphead)
{
  assert(pphead);
  SListNode* cur = *pphead;
  while (cur)
  {
    SListNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}

四、增删查改

4.1、插入数据

头插

思想：

并且这里需要assert断言pphead，因为slist的地址pphead是不能为空的

画图演示（逻辑结构）：

SList.h 文件：

//头插
void SListPushFront(SListNode** pphead, SLTDataType x);

SList.c 文件：

//头插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
  assert(pphead);
  SListNode* newnode = BuySListNode(x); //创建一个新的节点
  newnode->next = *pphead;
  *pphead = newnode;
}

画图演示（物理结构）： Test.c 文件：

int main()
{
  SListNode* slist = NULL;
  for (int i = 0; i < 10; i++)
  {
    SListPushBack(&slist, i); //尾插10个数据
  }
  for (int i = -5; i < 0; i++)
  {
    SListPushFront(&slist, i); //头插5个数据
  }
  SListPrint(slist); //打印
  return 0;
}

效果如下：尾插

思想：

尾插要分两种情况，本身为空和不为空。

如果本身为空，则把新开的节点给phead

画图演示：注意：

这里一定要assert断言pphead，pphead是一定不能为空的，哪怕链表是空，slist是地址，slist的地址pphead不能为空

SList.h 文件：

//尾插
void SListPushBack(SListNode** pphead, SLTDataType x);

SList.c 文件：

//尾插
void SListPushBack(SListNode** pphead, SLTDataType x) 
{
  assert(pphead);// pphead是一定不能为空的，哪怕链表是空，slist是地址，slist的地址不能为空
  SListNode* newnode = BuySListNode(x);
  if (*pphead == NULL) //pphead就是slist的地址，*pphead就是slist本身
  {
    *pphead = newnode;
  }
  else
  {
    //找尾
    SListNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}

Test.c 文件：

int main()
{
  SListNode* slist = NULL;
  for (int i = 0; i < 10; i++)
  {
    SListPushBack(&slist, i);
  }
  SListPrint(slist);
  return 0;
}

效果如下：在pos位置前插入x

思想：

画图演示：

SList.h 文件：

1. //在pos位置之前插入
2. void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);

SList.c 文件：

//在pos位置之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
  assert(pphead);
  assert(pos);
  //1、pos是第一个节点
  //2、pos不是第一个节点
  if (pos == *pphead)
  {
    SListPushFront(pphead, x);
  }
  else
  {
    SListNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SListNode* newnode = BuySListNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}

效果如下：在pos位置后插入x

思想：

SList.h 文件：

//在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x);

SList.c 文件：

//在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
  assert(pos);
  //法一：
  SListNode* next = pos->next;
  SListNode* newnode = BuySListNode(x);
  pos->next = newnode;
  newnode->next = next;
  /*
  法二：
  SListNode* newnode = BuySListNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
  */
}

测试结构与过程与上文在pos之前插入x一样，这里不过多赘述。

4.2、删除数据

头删

思想：

画图演示：

SList.h 文件：

1. //头删
2. void SListPopFront(SListNode** pphead);

SList.c 文件：

//头删
void SListPopFront(SListNode** pphead)
{
  assert(pphead);
  //1、空
  //2、非空
  if (*pphead == NULL)
  {
    return;
  }
  else
  {
    SListNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
  }
}

Test.c 文件：

int main()
{
  SListNode* slist = NULL;
  for (int i = 1; i < 10; i++)
  {
    SListPushBack(&slist, i); //尾插10个数据
  }
  SListPrint(slist); //打印
  for (int i = 0; i < 4; i++)
  {
    SListPopFront(&slist); //头删4次
  }
  SListPrint(slist); //打印
  return 0;
}

效果如下：尾删

思想：

法一：

正常情况下，尾删首先要找尾，和尾插一样定义一个指针变量tail，当tail的next指向NULL时，即找到尾，当释放掉最后一个数据的时候，切记单链表的原则是最后一个节点指向空NULL，所以还需要定义一个指针变量prev，当tail遍历不为空时，将其赋给prev，当tail到尾的时候，prev就是前一个，此时将prev->next置为NULL即可。这种情况仅限于有多个节点，很难保证有极端情况，比如说只要一个节点或没有节点，所以要分多种情况处理

画图演示：

没有节点：

一个节点：

多个节点：

代码如下：（SList.c 文件）

//尾删 -- 法一
void SListPopBack(SListNode** pphead)
{
  assert(pphead);
  //1、空
  //2、一个节点
  //3、多个节点
  /*暴力检查为空：assert(*pphead != NULL);*/
  //温柔检查为空：
  if (*pphead == NULL)
  {
    return;
  }
  else if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SListNode* prev = NULL;
    SListNode* tail = *pphead;
    while (tail->next != NULL)
    {
      prev = tail;
      tail = tail->next;
    }
    free(tail);
    tail = NULL;
    prev->next = NULL;
  }
}

法二：

也可以只定义一个指针变量tail，寻找tail->next->next是否为NULL，如果是，把tail指向的next释放掉并置为空即可，此法看起来代码更加简洁，但容易写错，个人推荐法一，此法的弊端同法一只适用于多个节点，同样要考虑为空和一个节点的情况。

代码如下：（SList.c 文件）

//尾删
void SListPopBack(SListNode** pphead)
{
  assert(pphead);
//空…… 同上
//一个节点…… 同上
//多个节点：如下
  SListNode* tail = *pphead;
  while (tail->next->next != NULL)
  {
    tail = tail->next;
  }
  free(tail->next);
  tail->next = NULL;
}

Test.c 文件：

int main()
{
  SListNode* slist = NULL;
  for (int i = 1; i < 5; i++)
  {
    SListPushBack(&slist, i); //尾插4个数据
  }
  SListPrint(slist); //打印
  for (int i = 0; i < 5; i++)
  {
    SListPopBack(&slist); //尾删5次
  }
  SListPrint(slist); //打印
  return 0;
}

效果如下：删除pos后的数据

思想：

和插入pos处的数据一样，要先用SListFind函数找到它再删除，比如说我要删掉3，但是得有其哪一个节点，所以创建prev指向pos的前一个节点，再把自己free释放掉，再把prev的下一个节点指向pos的下一个节点，再把pos free释放掉。当然，上述情况仅限于pos不是头部，如果pos是头，那么prev即为空，所以需另加讨论，仅需调用头删即可

画图演示：

SList.h 文件：

//删除pos位置
void SListErase(SListNode** pphead, SListNode* pos);

SList.c 文件：

//删除pos位置
void SListErase(SListNode** pphead, SListNode* pos)
{
  assert(pphead);
  assert(pos);
  if (*pphead == pos)
  {
    SListPopFront(pphead);
  }
  else
  {
    SListNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    pos = NULL;
  }
}

Test.c 文件：

int main()
{
  SListNode* slist = NULL;
  for (int i = 1; i <= 5; i++)
  {
    SListPushBack(&slist, i); //尾插5个数据
  }
  SListPrint(slist); //打印
  SListNode* pos = SListFind(slist, 3); 
  if (pos != NULL)
  {
    SListErase(&slist, pos); //删3
  }
  SListPrint(slist); //打印
  pos = SListFind(slist, 1);
  if (pos != NULL)
  {
    SListErase(&slist, pos); //删1
  }
  SListPrint(slist); //打印
  return 0;
}

效果如下：删除pos处数据

思想：

相比较删除pos处，删除pos后更为方便，因为不需要传phead的地址。只需要用next保存pos的下一个节点，让pos的下一个节点指向next的下一个节点，实现链表的链接，再把pos free释放掉。但是要额外注意到当pos为尾的时候，pos的下一个节点next为空，所以需要另加讨论，仅需调用尾删即可。

SList.h 文件：

//删除pos后位置
void SListEraseAfter(SListNode* pos);

SList.c 文件：

//删除pos后位置
void SListEraseAfter(SListNode* pos)
{
  assert(pos);
  SListNode* next = pos->next;
  if (next)
  {
    pos->next = next->next;
    free(next);
    next = NULL;
  }
}

4.3、单链表查找

思想：

单链表查找其实很简单，只需要定义一个指针cur指向头部phead，依次遍历cur（cur = cur -> next）看其指向的data是否等于x，如果相等，则返回cur，反之返回NULL。

SList.h 文件：

//查找
SListNode* SListFind(SListNode* phead, SLTDataType x);

SList.c 文件：

//查找
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
  SListNode* cur = phead;
  while (cur != NULL)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

Test.c 文件：

int main()
{
  SListNode* slist = NULL;
  for (int i = 1; i < 10; i++)
  {
    SListPushBack(&slist, i); //尾插10个数据
  }
  SListPrint(slist); //打印
  SListNode* pos = SListFind(slist, 3);
  if (pos != NULL)
  {
    printf("找到了,地址为%p\n", pos);
  }
  return 0;
}

效果如下：

4.4、修改单链表

修改就比较简单了，只需要在查找的基础上做出调整即可，当我们查到某个要修改的数据时，通过返回的地址对它进行修改。

Test.c 文件：

int main()
{
  SListNode* slist = NULL;
  for (int i = 1; i < 4; i++)
  {
    SListPushBack(&slist, i); //尾插10个数据
  }
  SListPrint(slist); //打印
  SListNode* pos = SListFind(slist, 3);
  if (pos != NULL)
  {
    printf("找到了,地址为%p\n", pos);
    pos->data *= 10;
  }
  SListPrint(slist); //打印
  return 0;
}

效果如下：

五、总代码

SList.h 文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType; //方便以后存储其它类型数据，本文以int为例
//创建单链表结构
typedef struct SListNode
{
  SLTDataType data; //值
  struct SListNode* next; //存储下一个节点的地址
}SListNode, SLN;
//打印单链表
void SListPrint(SListNode* phead);
//销毁单链表
void SListDestroy(SListNode** pphead);
//尾插
void SListPushBack(SListNode** pphead, SLTDataType x);
//头插
void SListPushFront(SListNode** pphead, SLTDataType x);
//尾删
void SListPopBack(SListNode** pphead);
//头删
void SListPopFront(SListNode** pphead);
//查找
SListNode* SListFind(SListNode* phead, SLTDataType x);
//在pos位置之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);
//在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x);
//删除pos位置
void SListErase(SListNode** pphead, SListNode* pos);
//删除pos后位置
void SListEraseAfter(SListNode* pos);

SList.c 文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
//打印单链表
void SListPrint(SListNode* phead)
{
  SListNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
//创建新节点
SListNode* BuySListNode(SLTDataType x)
{
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  else
  {
    newnode->data = x;
    newnode->next = NULL;
  }
  return newnode;
}
//销毁单链表
void SListDestroy(SListNode** pphead)
{
  assert(pphead);
  SListNode* cur = *pphead;
  while (cur)
  {
    SListNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}
//查找
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
  SListNode* cur = phead;
  while (cur != NULL)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
//尾插
void SListPushBack(SListNode** pphead, SLTDataType x)
{
  assert(pphead);// pphead是一定不能为空的，哪怕链表是空，slist是地址，slist的地址不能为空
  SListNode* newnode = BuySListNode(x);
  if (*pphead == NULL) //pphead就是slist的地址，*pphead就是slist本身
  {
    *pphead = newnode;
  }
  else
  {
    //找尾
    SListNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
//头插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
  assert(pphead);
  SListNode* newnode = BuySListNode(x); //创建一个新的节点
  newnode->next = *pphead;
  *pphead = newnode;
}
//尾删 
void SListPopBack(SListNode** pphead)
{
  assert(pphead);
  //1、空
  //2、一个节点
  //3、多个节点
  /*暴力检查为空：assert(*pphead != NULL);*/
  //温柔检查为空：
  if (*pphead == NULL)
  {
    return;
  }
  else if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    //法一：
    SListNode* prev = NULL;
    SListNode* tail = *pphead;
    while (tail->next != NULL)
    {
      prev = tail;
      tail = tail->next;
    }
    free(tail);
    tail = NULL;
    prev->next = NULL;
    //法二：
    /*SListNode* tail = *pphead;
    while (tail->next->next != NULL)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;*/
  }
}
//头删
void SListPopFront(SListNode** pphead)
{
  assert(pphead);
  //1、空
  //2、非空
  if (*pphead == NULL)
  {
    return;
  }
  else
  {
    SListNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
  }
}
//在pos位置之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
  assert(pphead);
  assert(pos);
  //1、pos是第一个节点
  //2、pos不是第一个节点
  if (pos == *pphead)
  {
    SListPushFront(pphead, x);
  }
  else
  {
    SListNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SListNode* newnode = BuySListNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}
//在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
  assert(pos);
  //法一：
  SListNode* next = pos->next;
  SListNode* newnode = BuySListNode(x);
  pos->next = newnode;
  newnode->next = next;
  /*
  法二：
  SListNode* newnode = BuySListNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
  */
}
//删除pos位置
void SListErase(SListNode** pphead, SListNode* pos)
{
  assert(pphead);
  assert(pos);
  if (*pphead == pos)
  {
    SListPopFront(pphead);
  }
  else
  {
    SListNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    pos = NULL;
  }
}
//删除pos后位置
void SListEraseAfter(SListNode* pos)
{
  assert(pos);
  SListNode* next = pos->next;
  if (next)
  {
    pos->next = next->next;
    free(next);
    next = NULL;
  }
}

Test.c 文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
//void test1()
//{
//  SListNode* slist = NULL;
//  SListNode* n1 = malloc(sizeof(SListNode));
//  SListNode* n2 = malloc(sizeof(SListNode));
//  SListNode* n3 = malloc(sizeof(SListNode));
//  n1->data = 1;
//  n2->data = 2;
//  n3->data = 3;
//  n1->next = n2;
//  n2->next = n3;
//  n3->next = NULL;
//  slist = n1;
//  SListPrint(slist);
//}
void test2()
{
  SListNode* slist = NULL;
  for (int i = 0; i < 10; i++)
  {
    SListPushBack(&slist, i); //尾插10个数据
  }
  for (int i = -5; i < 0; i++)
  {
    SListPushFront(&slist, i); //头插5个数据
  }
  SListPrint(slist); //打印
}
void test3()
{
  SListNode* slist = NULL;
  for (int i = 1; i < 5; i++)
  {
    SListPushBack(&slist, i); //尾插4个数据
  }
  SListPrint(slist); //打印
  for (int i = 0; i < 5; i++)
  {
    SListPopBack(&slist); //尾删5次
  }
  SListPrint(slist); //打印
}
void test4()
{
  SListNode* slist = NULL;
  for (int i = 1; i < 10; i++)
  {
    SListPushBack(&slist, i); //尾插10个数据
  }
  SListPrint(slist); //打印
  for (int i = 0; i < 4; i++)
  {
    SListPopFront(&slist); //头删4次
  }
  SListPrint(slist); //打印
}
void test5()
{
  SListNode* slist = NULL;
  for (int i = 1; i < 4; i++)
  {
    SListPushBack(&slist, i); //尾插10个数据
  }
  SListPrint(slist); //打印
  SListNode* pos = SListFind(slist, 3);
  if (pos != NULL)
  {
    printf("找到了,地址为%p\n", pos);
    pos->data *= 10;
  }
  SListPrint(slist); //打印
}
void test6()
{
  SListNode* slist = NULL;
  for (int i = 1; i < 4; i++)
  {
    SListPushBack(&slist, i); //尾插10个数据
  }
  SListPrint(slist); //打印
  SListNode* pos = SListFind(slist, 3);
  if (pos != NULL)
  {
    SListInsert(&slist, pos, 300);
  }
  SListPrint(slist); //打印
  pos = SListFind(slist, 1);
  if (pos != NULL)
  {
    SListInsert(&slist, pos, 100);
  }
  SListPrint(slist); //打印
}
int main()
{
  SListNode* slist = NULL;
  for (int i = 1; i <= 5; i++)
  {
    SListPushBack(&slist, i); //尾插5个数据
  }
  SListPrint(slist); //打印
  SListNode* pos = SListFind(slist, 3); 
  if (pos != NULL)
  {
    SListErase(&slist, pos); //删3
  }
  SListPrint(slist); //打印
  pos = SListFind(slist, 1);
  if (pos != NULL)
  {
    SListErase(&slist, pos); //删1
  }
  SListPrint(slist); //打印
  return 0;
}

＜数据结构＞单向链表

3.2、动态申请节点

3.3、单链表打印

3.4、销毁单链表

4.3、单链表查找

4.4、修改单链表

五、总代码

SList.h 文件

SList.c 文件

Test.c 文件

热门文章

最新文章

相关课程

相关电子书