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

【海贼王的数据航海】链表—单链表

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

1 -> 链表

1.1 -> 链表的概念及结构

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

现实中 数据结构中

注意：

  1. 上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续；
  2. 现实中的结点一般都是从堆上申请出来的；
  3. 从堆上申请的空间，是按照一定策略分配的，两次申请的空间可能连续，也可能不连续。

假设在32位系统上，结点中值域为int类型，则一个节点的大小为8个字节，则也可能有以下链表：

1.2 -> 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有八种链表结构：

1. 单向或双向

2. 带头或不带头

3. 循环或非循环

虽然有很多链表结构，但最常用的还是这两种：

1. 无头单向非循环链表

2. 带头双向循环链表

1. 无头单向非循环链表：结构简单，一般不会单独用来存储数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等。


2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

2 -> 无头+单向+非循环链表(单链表)

2.1 -> 接口声明

#pragma once
 
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
// 无头+单向+非循环链表增删查改实现
typedef int SLTDateType;
 
typedef struct SLTNode
{
  SLTDateType data;
  struct SLTNode* next;
}SLTNode;
 
// 动态申请一个结点
SLTNode* BuySLTNode(SLTDateType x);
 
// 单链表打印
void SLTPrint(SLTNode* phead);
 
// 单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x);
 
// 单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDateType x);
 
// 单链表的尾删
void SLTPopBack(SLTNode** pphead);
 
// 单链表头删
void SLTPopFront(SLTNode** pphead);
 
// 单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDateType x);
 
// 单链表在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
 
// 单链表在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDateType x);
 
// 单链表删除pos位置的值
void SLTErase(SLTNode** pphead, SLTNode* pos);
 
// 单链表删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos);

2.2 -> 接口实现

2.2.1 -> 动态申请一个结点

// 动态申请一个结点
SLTNode* BuySLTNode(SLTDateType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
 
  newnode->data = x;
  newnode->next = NULL;
 
  return newnode;
}

2.2.2 -> 单链表的打印

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

2.2.3 -> 单链表的尾插

// 单链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
  assert(pphead);
  SLTNode* newnode = BuySLTNode(x);
  if (*pphead == NULL)
  {
     *pphead = newnode;
  }
  else
  {
    SLTNode* cur = *pphead;
    while (cur->next != NULL)
    {
      cur = cur->next;
    }
    cur->next = newnode;
  }
}
// 尾插测试
void SLTTest1()
{
  SLTNode* plist = NULL;
 
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
 
  SLTPrint(plist);
}

2.2.4 -> 单链表的头插

// 单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
  assert(pphead);
  SLTNode* newnode = BuySLTNode(x);
 
  newnode->next = *pphead;
  *pphead = newnode;
}
// 头插测试
void SLTTest2()
{
  SLTNode* plist = NULL;
 
  SLTPushFront(&plist, 1);
  SLTPushFront(&plist, 2);
  SLTPushFront(&plist, 3);
  SLTPushFront(&plist, 4);
 
  SLTPrint(plist);
}

2.2.5 -> 单链表的尾删

// 单链表的尾删
void SLTPopBack(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead); // 暴力检查
 
   温柔的检查
  //if (*pphead == NULL)
  //{
  //  return;
  //}
 
  // 只有一个节点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  // 有多个节点
  else
  {
    SLTNode* prev = *pphead;
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
      prev = tail;
      tail = tail->next;
    }
 
    free(tail);
    tail = NULL;
 
    prev->next = NULL;
  }
}
// 尾删测试
void SLTTest3()
{
  SLTNode* plist = NULL;
 
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPrint(plist);
 
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
}

2.2.6 -> 单链表的头删

// 单链表的头删
void SLTPopFront(SLTNode** pphead)
{
  assert(*pphead);
  SLTNode* tail = *pphead;
 
  *pphead = (*pphead)->next;
  free(tail);
  tail = NULL;
}
// 头删测试
void SLTTest4()
{
  SLTNode* plist = NULL;
 
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPrint(plist);
 
  SLTPopFront(&plist);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
}

2.2.7 -> 单链表的查找

// 单链表的查找
SLTNode* SLTFind(SLTNode* phead, SLTDateType x)
{
  SLTNode* ptr = phead;
  while (ptr->next != NULL)
  {
    if (ptr->data == x)
    {
      return ptr;
    }
    else
    {
      ptr = ptr->next;
    }
  }
 
  return NULL;
}
// 查找测试
void SLTTest5()
{
  SLTNode* plist = NULL;
 
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPrint(plist);
 
  SLTNode* ans = SLTFind(plist, 1);
  if (ans)
    ans->data = 10;
  SLTPrint(plist);
}

2.2.8 -> 单链表在pos位置之前插入x

// 单链表在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
  assert(pphead);
  assert(pos);
  if (pos == *pphead)
  {
    SLTPushFront(pphead, x);
  }
  else
  {
    SLTNode* newnode = BuySLTNode(x);
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
 
    prev->next = newnode;
    newnode->next = pos;
  }
}
// 在pos位置之前插入x测试
void SLTTest6()
{
  SLTNode* plist = NULL;
 
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPrint(plist);
 
  SLTNode* pos = SLTFind(plist, 2);
  if (pos)
    SLTInsert(&plist, pos, 99);
  SLTPrint(plist);
}

2.2.9 -> 单链表在pos位置之后插入x

// 单链表在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{
  assert(pos);
  SLTNode* newnode = BuySLTNode(x);
  SLTNode* tmp = pos->next;
 
  pos->next = newnode;
  newnode->next = tmp;
}
// 在pos位置之后插入x测试
void SLTTest7()
{
  SLTNode* plist = NULL;
 
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPrint(plist);
 
  SLTNode* pos = SLTFind(plist, 2);
  if (pos)
    SLTInsertAfter(pos, 99);
  SLTPrint(plist);
}

2.2.10 -> 单链表删除pos位置的值

// 单链表删除pos位置的值
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(*pphead);
  assert(pos);
  if (pos == *pphead)
  {
    SLTPopFront(pphead);
  }
  else
  {
    SLTNode* prev = *pphead;
    if (prev->next != pos)
    {
      prev = prev->next;
    }
 
    prev->next = pos->next;
    free(pos);
    pos = NULL;
  }
}
// 删除pos位置的值测试
void SLTTest8()
{
  SLTNode* plist = NULL;
 
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPrint(plist);
 
  SLTNode* pos = SLTFind(plist, 2);
  if (pos)
    SLTErase(&plist, pos);
  SLTPrint(plist);
}

2.3 -> 完整代码

2.3.1 -> SList.h

#pragma once
 
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
// 无头+单向+非循环链表增删查改实现
typedef int SLTDateType;
 
typedef struct SLTNode
{
  SLTDateType data;
  struct SLTNode* next;
}SLTNode;
 
// 动态申请一个结点
SLTNode* BuySLTNode(SLTDateType x);
 
// 单链表打印
void SLTPrint(SLTNode* phead);
 
// 单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x);
 
// 单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDateType x);
 
// 单链表的尾删
void SLTPopBack(SLTNode** pphead);
 
// 单链表头删
void SLTPopFront(SLTNode** pphead);
 
// 单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDateType x);
 
// 单链表在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
 
// 单链表在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDateType x);
 
// 单链表删除pos位置的值
void SLTErase(SLTNode** pphead, SLTNode* pos);
 
// 单链表删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos);

2.3.2 -> SList.c

#include "SList.h"
 
// 动态申请一个结点
SLTNode* BuySLTNode(SLTDateType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
 
  newnode->data = x;
  newnode->next = NULL;
 
  return newnode;
}
 
// 单链表的打印
void SLTPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
 
  printf("NULL\n");
}
 
// 单链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
  assert(pphead);
  SLTNode* newnode = BuySLTNode(x);
  if (*pphead == NULL)
  {
     *pphead = newnode;
  }
  else
  {
    SLTNode* cur = *pphead;
    while (cur->next != NULL)
    {
      cur = cur->next;
    }
    cur->next = newnode;
  }
}
 
// 单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
  assert(pphead);
  SLTNode* newnode = BuySLTNode(x);
 
  newnode->next = *pphead;
  *pphead = newnode;
}
 
// 单链表的尾删
void SLTPopBack(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead); // 暴力检查
 
   温柔的检查
  //if (*pphead == NULL)
  //{
  //  return;
  //}
 
  // 只有一个节点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  // 有多个节点
  else
  {
    SLTNode* prev = *pphead;
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
      prev = tail;
      tail = tail->next;
    }
 
    free(tail);
    tail = NULL;
 
    prev->next = NULL;
  }
}
 
// 单链表的头删
void SLTPopFront(SLTNode** pphead)
{
  assert(*pphead);
  SLTNode* tail = *pphead;
 
  *pphead = (*pphead)->next;
  free(tail);
  tail = NULL;
}
 
// 单链表的查找
SLTNode* SLTFind(SLTNode* phead, SLTDateType x)
{
  SLTNode* ptr = phead;
  while (ptr->next != NULL)
  {
    if (ptr->data == x)
    {
      return ptr;
    }
    else
    {
      ptr = ptr->next;
    }
  }
 
  return NULL;
}
 
// 单链表在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
  assert(pphead);
  assert(pos);
  if (pos == *pphead)
  {
    SLTPushFront(pphead, x);
  }
  else
  {
    SLTNode* newnode = BuySLTNode(x);
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
 
    prev->next = newnode;
    newnode->next = pos;
  }
}
 
// 单链表在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{
  assert(pos);
  SLTNode* newnode = BuySLTNode(x);
  SLTNode* tmp = pos->next;
 
  pos->next = newnode;
  newnode->next = tmp;
}
 
// 单链表删除pos位置的值
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(*pphead);
  assert(pos);
  if (pos == *pphead)
  {
    SLTPopFront(pphead);
  }
  else
  {
    SLTNode* prev = *pphead;
    if (prev->next != pos)
    {
      prev = prev->next;
    }
 
    prev->next = pos->next;
    free(pos);
    pos = NULL;
  }
}
 
// 单链表删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos)
{
  assert(pos);
  assert(pos->next);
  SLTNode* tmp = pos->next->next;
 
  free(pos->next);
  pos->next = tmp;
}

2.3.3 -> Test.c

#include "SList.h"
 
// 尾插测试
void SLTTest1()
{
  SLTNode* plist = NULL;
 
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
 
  SLTPrint(plist);
}
 
// 头插测试
void SLTTest2()
{
  SLTNode* plist = NULL;
 
  SLTPushFront(&plist, 1);
  SLTPushFront(&plist, 2);
  SLTPushFront(&plist, 3);
  SLTPushFront(&plist, 4);
 
  SLTPrint(plist);
}
 
// 尾删测试
void SLTTest3()
{
  SLTNode* plist = NULL;
 
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPrint(plist);
 
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
}
 
// 头删测试
void SLTTest4()
{
  SLTNode* plist = NULL;
 
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPrint(plist);
 
  SLTPopFront(&plist);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
}
 
// 查找测试
void SLTTest5()
{
  SLTNode* plist = NULL;
 
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPrint(plist);
 
  SLTNode* ans = SLTFind(plist, 1);
  if (ans)
    ans->data = 10;
  SLTPrint(plist);
}
 
// 在pos位置之前插入x测试
void SLTTest6()
{
  SLTNode* plist = NULL;
 
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPrint(plist);
 
  SLTNode* pos = SLTFind(plist, 2);
  if (pos)
    SLTInsert(&plist, pos, 99);
  SLTPrint(plist);
}
 
// 在pos位置之后插入x测试
void SLTTest7()
{
  SLTNode* plist = NULL;
 
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPrint(plist);
 
  SLTNode* pos = SLTFind(plist, 2);
  if (pos)
    SLTInsertAfter(pos, 99);
  SLTPrint(plist);
}
 
// 删除pos位置的值测试
void SLTTest8()
{
  SLTNode* plist = NULL;
 
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPrint(plist);
 
  SLTNode* pos = SLTFind(plist, 2);
  if (pos)
    SLTErase(&plist, pos);
  SLTPrint(plist);
}
 
// 删除pos位置之后的值测试
void SLTTest9()
{
  SLTNode* plist = NULL;
 
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPrint(plist);
 
  SLTNode* pos = SLTFind(plist, 2);
  if (pos)
    SLTEraseAfter(pos);
  SLTPrint(plist);
}
 
int main()
{
 
 
 
  return 0;
}


感谢大佬们的支持！！！

互三啦！！！


文章标签：
存储
关键词：
数据航海链表
数据链表
链表数据
链表单链表
枫叶丹4
目录
相关文章
xxxhuxxx
|
1月前
|
存储 缓存 算法
链表全景：探索单链表、双向链表与循环链表【实战演练】
链表全景：探索单链表、双向链表与循环链表【实战演练】
xxxhuxxx
37 3
起飞的风筝
|
1月前
|
存储
【单链表】数据结构单链表的实现
【单链表】数据结构单链表的实现
起飞的风筝
49 0
知更鸟呆呆
|
16天前
|
存储
链表入门（单链表讲）
链表入门（单链表讲）
知更鸟呆呆
9 0
链表入门（单链表讲）
枫叶丹4
|
4天前
|
存储 缓存
【海贼王的数据航海】链表—双向链表
【海贼王的数据航海】链表—双向链表
枫叶丹4
4 0
兰雪簪轩
|
1月前
|
存储 编译器
单链表与双链表实现
单链表与双链表实现
兰雪簪轩
27 4
dulu~dulu
|
1月前
特殊链表（循环单链表，循环双链表，静态链表）
特殊链表（循环单链表，循环双链表，静态链表）
dulu~dulu
23 3
sky_qiyi
|
24天前
|
算法
数据结构和算法学习记录——线性表之单链表（下）-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
数据结构和算法学习记录——线性表之单链表（下）-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
sky_qiyi
22 0
sky_qiyi
|
24天前
|
存储 算法
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数（顺序表缺陷、单链表优点、链表打印）
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数（顺序表缺陷、单链表优点、链表打印）
sky_qiyi
16 0
碳基肥宅
|
1月前
|
Java
DAY-1 | Java数据结构之链表：删除无头单链表中等于给定值 val 的所有节点
力扣203题解：使用时间复杂度为O(n)的思路删除链表中所有值为key的元素。引入辅助指针pre，记录cur的前一个节点，遍历链表时，若cur.val!=key，pre和cur同时前进；若cur.val==key，则pre.next=cur.next，cur继续前进，确保pre不急于跟随以处理连续相同值的情况。遍历结束后，处理头节点可能需要删除的特殊情况。
碳基肥宅
30 0
GR鲸鱼
|
1月前
|
存储 算法 索引
数据结构与算法④(第二章下)链表概念+单链表的实现
数据结构与算法④(第二章下)链表概念+单链表的实现
GR鲸鱼
24 0