数据结构之单链表-2-阿里云开发者社区

数据结构之单链表-2

2023-11-15 53

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构之单链表

查找与修改

链表的查找实现就比较简单了，找到返回对应节点的地址，找不到返回NULL

大家有没有发现，其实能查找，也意味着能修改，因为我们获取了该节点的地址，自然能在外部解引用修改数据，这样，一个函数就有两个功能 ——查找和修改

运行结果

指针断言

这里说一下关于assert断言的情况，并不是所有函数参数的指针都需要断言，而是要根据实际情况分析而定。

打印与查找，则不需要断言，因为空链表也可以打印，也可以查找，就比如你的银行账户没有钱，就不能显示出来看看，不能查询吗？

头插与尾插，对于其二级指针需要断言，一级指针不用，因为pphead指向链表指针plist，所以不能为空，而链表指针可为空（即为空链表）

头删与尾删，其二级指针与一级指针都要断言，除了pphead不能为空，*pphead也不能为空，因为空链表就不能进行删除操作

指定插入

这里有两种插入方式，在pos前插入和在pos后插入

在pos前插入

首先断言pphead和pos，再找到pos前一个节点的地址（方法与尾删相同，创建prev指针），然后创建新节点，最后将它们链接起来

其次，再考虑特殊情况，如果pos为头部地址时，即为头插，可复用头插函数

在pos后插入

相比于在pos前插入，单链表其实更适合在pos后插入，直接创建新节点，进行链接即可

注意：链接的过程有顺序问题，不能写反了，要不然会环状链接

运行结果

指定删除

这里也有两种删除方式，在pos删除和在pos后删除

在pos删除

实现思路与指定插入大致相同

运行结果

在pos后删除

同样，相比于在pos位置删除，单链表其实更适合在pos后删除，这里用一个next指针，保存pos下一个节点的地址，在pos链接往后第二个节点后，方便对pos后节点空间释放

运行结果

销毁

链表的销毁也比较简单，在每次循环内临时创建一个新指针next，记录下一个节点的地址，让cur释放所指空间后，还可以找到下一个节点，最后把链表指针解引用置空

当然，这里你也可以传一级指针，不在函数内部把外部的链表指针置为NULL，而在外部手动置空，跟free函数的用法一样，实现半自动

这样我们就完成了对单链表的增删查改等功能的实现

单链表oj题

仅仅了解单链表的知识是不够的，让我们来刷刷题吧！

876.链表的中间结点（LeetCode）-CSDN博客

21.合并两个有序链表（LeetCode）-CSDN博客

19.删除链表的倒数第N个结点（LeetCode）-CSDN博客

206.反转链表（LeetCode）-CSDN博客

234.回文链表（LeetCode）-CSDN博客

面试题 02.04. 分割链表（LeetCode）-CSDN博客

160.相交链表（LeetCode）-CSDN博客

源代码

slist.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//单链表
typedef int SLDataType;
typedef struct SListNode
{
  SLDataType data;
  struct SListNode* next;
}SLNode;
//打印
void SLPrint(SLNode* phead);
//头插
void SLPushFront(SLNode** pphead, SLDataType x);
//尾插
void SLPushBack(SLNode** pphead, SLDataType x);
//头删
void SLPopFront(SLNode** pphead);
//尾删
void SLPopBack(SLNode** pphead);
//查找
SLNode* SLFind(SLNode* phead, SLDataType x);
//在pos前指定插入
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x);
//在pos后指定插入
void SLInsertAfter(SLNode* pos, SLDataType x);
//在pos指定删除
void SLErase(SLNode** pphead, SLNode* pos);
//在pos后指定删除
void SLEraseAfter(SLNode* pos);
//销毁
void SLDestroy(SLNode* phead);

slist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"slist.h"
void SLPrint(SLNode* phead)
{
  SLNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
SLNode* BuySLNode(SLDataType x)
{
  SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}
void SLPushFront(SLNode** pphead, SLDataType x)
{
  assert(pphead);
  SLNode* newnode = BuySLNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}
void SLPushBack(SLNode** pphead, SLDataType x)
{
  assert(pphead);
  //1.空链表
  //2.非空链表
  SLNode* newnode = BuySLNode(x);
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    SLNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
void SLPopFront(SLNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  SLNode* cur = *pphead;
  *pphead = (*pphead)->next;
  free(cur);
}
void SLPopBack(SLNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  //空链表
  //一个节点
  //多个节点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLNode* tail = *pphead;
    while (tail->next->next)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
    //SLNode* prev = NULL;
    //SLNode* tail = *pphead;
    //while (tail->next)
    //{
    //  prev = tail;
    //  tail = tail->next;
    //}
    //free(tail);
    //prev->next = NULL;
  }
}
SLNode* SLFind(SLNode* phead, SLDataType x)
{
  SLNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{
  assert(pphead);
  assert(pos);
  if (pos == *pphead)
  {
    SLPushFront(pphead, x);
  }
  else
  {
    SLNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLNode* newnode = BuySLNode(x);
    newnode->next = pos;
    prev->next = newnode;
  }
}
void SLInsertAfter(SLNode* pos, SLDataType x)
{
  assert(pos);
  SLNode* newnode = BuySLNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
void SLErase(SLNode** pphead, SLNode* pos)
{
  assert(pphead);
  assert(pos);
  if (pos == *pphead)
  {
    SLPopFront(pphead);
  }
  else
  {
    SLNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}
void SLEraseAfter(SLNode* pos)
{
  assert(pos);
  assert(pos->next);
  SLNode* next = pos->next;
  pos->next = pos->next->next;
  free(next);
}
//void SLDestroy(SLNode** pphead)
//{
//  assert(pphead);
//  SLNode* cur = *pphead;
//  while (cur)
//  {
//    SLNode* next = cur->next;
//    free(cur);
//    cur = next;
//  }
//  *pphead = NULL;
//}
void SLDestroy(SLNode* phead)
{
  SLNode* cur = phead;
  while (cur)
  {
    SLNode* next = cur->next;
    free(cur);
    cur = next;
  }
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"slist.h"
void TestSList1()
{
  SLNode* plist = NULL;
  //头插
  SLPushFront(&plist, 1);
  SLPushFront(&plist, 2);
  SLPushFront(&plist, 3);
  SLPushFront(&plist, 4);
  SLPushFront(&plist, 5);
  //尾删
  SLPopBack(&plist);
  SLPopBack(&plist);
  //打印
  SLPrint(plist);
}
void TestSList2()
{
  SLNode* plist = NULL;
  //尾插
  SLPushBack(&plist, 1);
  SLPushBack(&plist, 2);
  SLPushBack(&plist, 3);
  SLPushBack(&plist, 4);
  //打印
  SLPrint(plist);
}
void TestSList3()
{
  SLNode* plist = NULL;
  //尾插
  SLPushBack(&plist, 1);
  SLPushBack(&plist, 2);
  SLPushBack(&plist, 3);
  SLPushBack(&plist, 4);
  //尾删
  SLPopBack(&plist);
  SLPopBack(&plist);
  //SLPopBack(&plist);
  //SLPopBack(&plist);
  //SLPopBack(&plist);
  //打印
  SLPrint(plist);
}
void TestSList4()
{
  SLNode* plist = NULL;
  //尾插
  SLPushBack(&plist, 1);
  SLPushBack(&plist, 2);
  SLPushBack(&plist, 3);
  SLPushBack(&plist, 7);
  SLPushBack(&plist, 6);
  SLPushBack(&plist, 5);
  SLPushBack(&plist, 4);
  //头删
  SLPopFront(&plist);
  SLPopFront(&plist);
  SLPopFront(&plist);
  SLPopFront(&plist);
  //打印
  SLPrint(plist);
}
void TestSList5()
{
  SLNode* plist = NULL;
  //头插
  SLPushFront(&plist, 1);
  SLPushFront(&plist, 2);
  SLPushFront(&plist, 3);
  SLPushFront(&plist, 4);
  SLPushFront(&plist, 5);
  //查找
  SLNode* pos = SLFind(plist, 3);
  if (pos)
  {
    SLInsert(&plist, pos, 40);
    SLInsertAfter(pos, 50);
  }
  //打印
  SLPrint(plist);
}
void TestSList6()
{
  SLNode* plist = NULL;
  //头插
  SLPushFront(&plist, 1);
  SLPushFront(&plist, 2);
  SLPushFront(&plist, 3);
  SLPushFront(&plist, 4);
  SLPushFront(&plist, 5);
  //查找
  SLNode* pos = SLFind(plist, 3);
  if (pos)
  {
    SLErase(&plist, pos);
    SLEraseAfter(pos);
  }
  //打印
  SLPrint(plist);
}
void TestSList7()
{
  SLNode* plist = NULL;
  //尾插
  SLPushBack(&plist, 1);
  SLPushBack(&plist, 2);
  SLPushBack(&plist, 3);
  SLPushBack(&plist, 4);
  //打印
  SLPrint(plist);
  //销毁
  SLDestroy(plist);
  plist = NULL;
}
int main()
{
  TestSList7();
  return 0;
}

写得这么详细（写得很辛苦……），换你们的点赞收藏关注，可不可以啊？嘻嘻~

数据结构之单链表-2

查找与修改

指针断言

指定插入

指定删除

销毁

单链表oj题

源代码

slist.h

slist.c

test.c

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构之单链表-2

查找与修改

指针断言

指定插入

指定删除

销毁

单链表oj题

源代码

slist.h

slist.c

test.c

热门文章

最新文章

相关课程

相关电子书