备案控制台
开发者社区 云计算 文章 正文

【数据结构】- 链表之单链表(下)

2023-06-28 55
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构学习第六弹——链表之单链表（下）

前言

未来藏在迷雾中 叫人看来胆怯 带你踏足其中 就会云开雾散

本章是关于数据结构中的链表之单链表(下)

提示：以下是本篇文章正文内容，下面案例可供参考

一、单链表(下)

1.1 查找+修改

//SList.h
SLTNode* STFind(SLTNode* phead, SLTDataType x);
//SList.c
SLTNode* STFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
//Test.c
void TestSList()
{
  SLTNode* plist = NULL;
  SLPushFornt(&plist, 1);
  SLPushFornt(&plist, 2);
  SLPushFornt(&plist, 3);
  SLPushFornt(&plist, 4);
  SLTPrint(plist);
  SLTNode* pos = STFind(plist, 3);
  if (pos)//判断是否为空
  {
    pos->data = 30;
  }
  SLTPrint(plist);
}

1.2 在任意位置插入

1.2.1 在pos位置插入(也就是pos位置之前)

//SList.h
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在pos之前插入
//SList.c
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pphead);
  assert(pos);
  if (*pphead == pos)
  {
    SLPushFornt(pphead, x);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLTNode* newnode = BuyTNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}
//Test.c
void TestSList()
{
  SLTNode* plist = NULL;
  SLPushFornt(&plist, 1);
  SLPushFornt(&plist, 2);
  SLPushFornt(&plist, 3);
  SLPushFornt(&plist, 4);
  SLTPrint(plist);
  SLTNode* pos = STFind(plist, 3);
  if (pos)//判断是否为空
  {
    SLInsert(&plist, pos, 30);
  }
}

流程图

多个节点

一个节点

1.2.2 在pos位置之后插入

//SList.h
void SLInsertAfter(SLTNode* pos, SLTDataType x);//在pos之后插入
//SList.c
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newnode = BuyTNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
//Test.c
void TestSList()
{
  SLTNode* plist = NULL;
  SLPushFornt(&plist, 1);
  SLPushFornt(&plist, 2);
  SLPushFornt(&plist, 3);
  SLPushFornt(&plist, 4);
  SLTPrint(plist);
  SLTNode* pos = STFind(plist, 2);
  if (pos)//判断是否为空
  {
    SLInsertAfter(pos, 30);
  }
  SLTPrint(plist);
}

流程图：

注意：

下面这种写法就存在了问题newnode指向了它自己造成了错误

void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newnode = BuyTNode(x);
  pos->next=newnode;
  newnode->next=pos->next;
}

流程图：

1.3 在任意位置删除

1.3.1 删除pos位置得值

//SList.h
void SLErase(SLTNode** pphead, SLTNode* pos);
//SList.c
void SLErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(pos);
  if (pos == *pphead)
  {
    SLPopFornt(pphead);//头删
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}
//Test.c
void TestSList()
{
  SLTNode* plist = NULL;
  SLPushFornt(&plist, 1);
  SLPushFornt(&plist, 2);
  SLPushFornt(&plist, 3);
  SLPushFornt(&plist, 4);
  SLTPrint(plist);
  SLTNode* pos = STFind(plist, 3);
  if (pos)//判断是否为空
  {
    SLErase(&plist, pos);
  }
  SLTPrint(plist);
}

流程图：

1.3.2 删除pos位置后面的值

//SList.h
void SLEraseAfter(SLTNode* pos);
//SList.c
void SLEraseAfter(SLTNode* pos)
{
  assert(pos);
  assert(pos->next);
  SLTNode* next = pos->next;
  pos->next = next->next;
  free(next);
}
//Test.c
void TestSList()
{
  SLTNode* plist = NULL;
  SLPushFornt(&plist, 1);
  SLPushFornt(&plist, 2);
  SLPushFornt(&plist, 3);
  SLPushFornt(&plist, 4);
  SLTPrint(plist);
    SLTNode* pos = STFind(plist, 3);
  if (pos)//判断是否为空
  {
    SLEraseAfter(pos);
  }
  SLTPrint(plist);
}

流程图：

二、完整代码

//SList.h
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);
void SLPushFornt(SLTNode** pphead, SLTDataType x);
void SLPushBack(SLTNode** pphead, SLTDataType x);
void SLPopFornt(SLTNode** pphead);
void SLPopBack(SLTNode** pphead);
SLTNode* STFind(SLTNode* phead, SLTDataType x);
//任意位置插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在pos之前插入
void SLInsertAfter(SLTNode* pos, SLTDataType x);//在pos之后插入
void SLErase(SLTNode** pphead, SLTNode* pos);//删除pos位置的值
void SLEraseAfter(SLTNode* pos);//删除pos位置的值
//SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void SLTPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
SLTNode* BuyTNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}
void SLPushFornt(SLTNode** pphead, SLTDataType x)
{
  SLTNode* newnode = BuyTNode(x);
  newnode->next  = *pphead;
  *pphead = newnode;
}
void SLPushBack(SLTNode** pphead, SLTDataType x)
{
  SLTNode* newnode = BuyTNode(x);
  //空链表
  if(*pphead==NULL)
  {
    *pphead = newnode;
  }
  //非空链表
  else
  {
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
void SLPopFornt(SLTNode** pphead)
{
  //空链表
  assert(*pphead);
  //一个节点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  //多个节点:保存下一个节点，释放当前节点
  else
  {
    SLTNode* del = *pphead;
    *pphead = del->next;
    free(del);
  }
}
void SLPopBack(SLTNode** pphead)
{
  //空链表
  assert(*pphead);
  //有一个节点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  有多个节点
  else
  {
  SLTNode* prev = NULL;
  SLTNode* tail = *pphead;
  //找尾
  while (tail->next == NULL)//或者写成while(tail->next)
  {
    prev = tail;
    tail = tail->next;
  }
  free(tail);
  prev->next = NULL;
    while (tail->next->next != NULL)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}
SLTNode* STFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pphead);
  assert(pos);
  if (*pphead == pos)
  {
    SLPushFornt(pphead, x);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLTNode* newnode = BuyTNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}
//在pos之后插入
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newnode = BuyTNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
//删除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(pos);
  if (pos == *pphead)
  {
    SLPopFornt(pphead);//头删
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}
//删除pos位置后面的值
void SLEraseAfter(SLTNode* pos)
{
  assert(pos);
  assert(pos->next);
  SLTNode* next = pos->next;
  pos->next = next->next;
  free(next);
}
//Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void TestSList()
{
  SLTNode* plist = NULL;
  SLPushFornt(&plist, 1);
  SLPushFornt(&plist, 2);
  SLPushFornt(&plist, 3);
  SLPushFornt(&plist, 4);
  SLTPrint(plist);
  SLPushBack(&plist, 5);
  SLPopFornt(&plist);
  SLTPrint(plist);
  SLPopFornt(&plist);
  SLTPrint(plist);
  SLPopFornt(&plist);
  SLTPrint(plist);
  SLPopFornt(&plist);
  SLTPrint(plist);
  SLTNode* pos = STFind(plist, 3);
  if (pos)//判断是否为空
  {
    SLInsert(&plist, pos, 30);
  }
  SLTNode* pos = STFind(plist, 2);
  if (pos)//判断是否为空
  {
    SLInsertAfter(pos, 30);
  }
  SLTPrint(plist);
  SLTNode* pos = STFind(plist, 3);
  if (pos)//判断是否为空
  {
    SLErase(&plist, pos);
  }
  SLTPrint(plist);
  SLTNode* pos = STFind(plist, 3);
  if (pos)//判断是否为空
  {
    SLEraseAfter(pos);
  }
  SLTPrint(plist);
}
int main()
{
  TestSList();
  return 0;
}

总结

Ending,今天的链表之单链表(下)的内容就到此结束啦~，如果后续想了解更多，就请关注我吧。

关键词：
数据结构链表
数据结构单链表
链表数据结构
链表单链表
数据结构链表单链表
小沈熬夜秃头中
目录
相关文章
老秦包你会
|
10天前
|
存储
数据结构第二课 -----线性表之单向链表
数据结构第二课 -----线性表之单向链表
老秦包你会
19 0
Bigcrab__
|
1天前
|
存储 算法 Java
数据结构与算法 数组和链表
数据结构与算法 数组和链表
Bigcrab__
7 0
菜菜的后端私房菜
|
1天前
|
存储 Java
深入浅出数据结构之链表
深入浅出数据结构之链表
菜菜的后端私房菜
4 0
天玑y
|
1天前
|
C++
数据结构（循环单链表
数据结构（循环单链表
天玑y
7 2
天玑y
|
1天前
|
C++
数据结构（双链表
数据结构（双链表
天玑y
6 1
天玑y
|
1天前
|
C++
数据结构（单链表
数据结构（单链表
天玑y
5 0
小蜗牛~向前冲
|
4天前
|
存储 缓存
[数据结构]~双向+循环链表从(0~1）
[数据结构]~双向+循环链表从(0~1）
小蜗牛~向前冲
14 2
小蜗牛~向前冲
|
4天前
|
存储
[数据结构]单链表(从0-＞1)
[数据结构]单链表(从0-＞1)
小蜗牛~向前冲
17 3
老秦包你会
|
10天前
|
存储
数据结构第三课 -----线性表之双向链表
数据结构第三课 -----线性表之双向链表
老秦包你会
11 0
小谢在努力
|
11天前
|
存储 Java
数据结构奇妙旅程之顺序表和链表
数据结构奇妙旅程之顺序表和链表
小谢在努力
6 0