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

【数据结构】单链表(一)

2023-06-10 57
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 目录前言： 单链表的结构 ： 逻辑结构：物理结构：BuySLTNode（动态申请一个结点）： CreateSList(//循环创建结点)：SLTPrint（单链表打印）： 单链表的功能： SLTPushBack尾插:plist不为NULL： plist为NULL：SLTPopBack（尾删）：SLTPushFront（头插）：SLTPopFront（头删）：SLTFind(查找)：SLTInsertAfter（在pos位置之后插入）： SLTInsertFront（在pos位置之前插入）：SLTEraseAfter（删

想变成仲夏夜的一只萤火虫，只要抓住你的注意力，就已经满足了。

目录


前言：


单链表的结构 ：


逻辑结构：


物理结构：


BuySLTNode（动态申请一个结点）：


CreateSList(//循环创建结点)：


SLTPrint（单链表打印）：


单链表的功能：


SLTPushBack尾插:


plist不为NULL：


plist为NULL：


SLTPopBack（尾删）：


SLTPushFront（头插）：


SLTPopFront（头删）：


SLTFind(查找)：


SLTInsertAfter（在pos位置之后插入）：


 SLTInsertFront（在pos位置之前插入）：


SLTEraseAfter（删除pos之后的位置）：


SLTErase（删除pos位置）：


SLTDestory（释放空间）：


完整代码：


text.c：


SList.c:


SList.h:


前言：

我们之前学习了顺序表，那么，朋友们知道顺序表有什么缺陷吗？

顺序表的缺陷：

  1. 空间不够的时候，需要扩容。扩容（尤其是异地扩容）是由一定价值的。其次还可能存在一定的空间浪费。
  2. 头部或者中部插入删除，需要挪动数据，效率低下。

优化方案：

  1. 按需申请释放
  2. 不需要挪动数据

这就需要链表来实现


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


简单来说，单链表是一种链式存取的 数据结构 ，用一组地址任意的存储单元 存放线性表中的数据元素。 链表中的数据是以结点来表示的，每个结点的构成：元素 ( 数据元素) + 指针 (指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的 地址 数据。 链表中的数据是以结点来表示的，每个结点的构成：元素 ( 数据元素 的映象) + 指针 (指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。 以“结点的序列”表示线性表称作 线性链表 （单链表），单链表是链式存取的结构。 链接方式存储的线性表简称为链表（Linked List）。 ② 链表中结点的逻辑次序和物理次序不一定相同。

单链表的结构 ：

typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data;//数据元素
  struct SListNode* next;//指向下一个与本结构体相同的结构体变量的指针
}SLTNode;

逻辑结构：

物理结构：

BuySLTNode（动态申请一个结点）：

函数实现：

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

CreateSList(//循环创建结点)：

首先，为了防止最后找不到头指针，我们再定义一个结构体变量ptail来进行后续的操作实现

这个图中的代码是四个结点连接的操作，可以结合图理解一下。

那么在实际操作中，实现n个创建利用for循环来实现，利用BuyTNode创建动态结构体，我们再将下一个结构体的地址传给结构体的next指针以此类推.....

下面是循环创建结点的代码实现：

函数实现：

//循环创建结点
SLTNode* CreateSList(int n)
{
  SLTNode* phead = NULL, * ptail = NULL;
  for (int i = 0; i < n; ++i)
  {
    SLTNode* newnode = BuySLTNode(i);
    if (phead == NULL)
    {
      phead = ptail = newnode;
    }
    else
    {
      ptail->next = newnode;
      ptail = newnode;
    }
  }
  return phead;
}

SLTPrint（单链表打印）：

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

单链表的功能：

SLTPushBack尾插:

plist不为NULL：

尾插需要先找尾部，即NULL的地方，然后将newnode插到null后面

注：

  • tail为NULL和tail->next为NULL对于循环条件来说是不一样的。
  • tail为NULL代表没有这个结构体
  • tail->next为NULL代表没有下一个结构体了
void SLTPushBack(SLTNode* phead, SLDataType x)
{//尾插
    SLTNode* newnode = BuySLTNode(x);
    SLTNode* tail = phead;
    while (tail->next)
    {
        tail = tail->next;
    }
        tail->next = newnode;
}

plist为NULL：

注：这里要传地址

因此我们要改变NULL这个指针，我们需要传SLTNode**pphead进去，那我们*pphead就可以改变NULL的值了！

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
  SLTNode* newnode = BuySLTNode(x);
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
    //找尾
  {
    SLTNode* tail = *pphead;
    while (tail->next)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}

SLTPopBack（尾删）：

找到尾部next指向为NULL的，将其释放掉，然后创建结构体第三变量prev记录前一个位置的next，将prev->next=NULL；

void SLTPopBack(SLTNode** pphead)
{
  assert(*pphead);
  if ((*pphead) == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTNode* tail = *pphead;
    SLTNode* prev = NULL;
    while (tail->next)
    {
      prev = tail;
      tail = tail->next;
    }
    free(tail);
    prev->next = NULL;
  }
}

SLTPushFront（头插）：

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}

SLTPopFront（头删）：

void SLTPopFront(SLTNode** pphead)
{
  assert(*pphead);
  SLTNode* next = (*pphead)->next;
  free(*pphead);
  *pphead = next;
}

SLTFind(查找)：

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

SLTInsertAfter（在pos位置之后插入）：

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

b069747ec232e57aa6f5bd3c0cb480ad_a1804d8542274dd99dca2baa5ebc7ff5.png

SLTInsertFront（在pos位置之前插入）：

有两种情况：

  • pos为链表第一个，那就相当于头插；
  • 除去第一个以外的位置：

        

// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pos);
  if (pos == *pphead)
  {
    SLTPushFront(pphead,x);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLTNode* newnode = BuySLTNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}

SLTEraseAfter（删除pos之后的位置）：

找pos位置的下一个位置将它赋给一个指针nextNode，将pos的next连接到nextNode的下一个结构体的位置，这样就跳过这个指针了，最后释放这个被跳过的空间！！！

void SLTEraseAfter(SLTNode* pos)
{
  assert(pos);
  if (pos->next == NULL)
  {
    return;
  }
  else
  {
    SLTNode* nextNode = pos->next;
    pos->next = nextNode->next;
    free(nextNode);
  }
}

SLTErase（删除pos位置）：

// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pos);
  if (pos==*pphead)
  {
    SLTPopFront(pphead);  
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}

SLTErase（删除pos位置）：

// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pos);
  if (pos==*pphead)
  {
    SLTPopFront(pphead);  
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}

SLTDestory（释放空间）： 

void SLTDestory(SLTNode** pphead)
{
  SLTNode* cur = *pphead;
  while (cur)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur=next;
  }
  *pphead = NULL;
}

完整代码：

首先，我将通讯录分成了三个部分：


1、text.c                   //通讯录的菜单以及主函数


2、SList.h             //结构体和函数的声明，以及头文件的引用


3、SList.c              //通讯录各种功能函数的实现  

text.c：

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
TextSList1()
{
  SLTNode* plist = CreateSList(10);
  SLTPrint(plist);
}
TextSList2()
{
  SLTNode* plist =NULL;
  SLTPushBack(&plist, 100);
  SLTPushBack(&plist, 200);
  SLTPushBack(&plist, 300);
  SLTPushBack(&plist, 400);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
}
TextSList3()
{
  SLTNode* plist = NULL;
  SLTPushFront(&plist, 100);
  SLTPushFront(&plist, 200);
  SLTPushFront(&plist,500);
  SLTPushFront(&plist, 800);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
}
TextSList4()
{
  SLTNode* plist = NULL;
  SLTPushFront(&plist, 100);
  SLTPushFront(&plist, 200);
  SLTPushFront(&plist, 500);
  SLTPushFront(&plist, 800);
  SLTPrint(plist);
  SLTNode* pos = SLTFind(plist,200);
  if (pos)
  {
    printf("找到了\n");
  }
  else
  {
    printf("找不到\n");
  }
}
TextSList5()
{
  SLTNode* plist = NULL;
  SLTPushBack(&plist, 100);
  SLTPushBack(&plist, 200);
  SLTPushBack(&plist, 300);
  SLTPushBack(&plist, 400);
  SLTPrint(plist);
  SLTNode* p = SLTFind(plist, 200);
  if (p)
  {
    SLTInsertAfter(p, 2);
    printf("找到了\n");
    SLTPrint(plist);
    SLTEraseAfter(p);
    SLTPrint(plist);
    SLTErase(&plist, p);
    SLTPrint(plist);
  }
  else
  {
    printf("找不到\n");
  }
}
TextSList6()
{
  SLTNode* plist = NULL;
  SLTPushBack(&plist, 100);
  SLTPushBack(&plist, 200);
  SLTPushBack(&plist, 300);
  SLTPushBack(&plist, 400);
  SLTPrint(plist);
  SLTNode* p = SLTFind(plist, 200);
  if (p)
  {
    SLTInsert(&plist, p, 1);
    SLTPrint(plist);
    SLTDestory(&plist);
    SLTPrint(plist);
  }
  else
  {
    printf("找不到了\n");
  }
}
int main()
{
  TextSList6();
  return 0;
}

SList.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
//动态申请一个结点
SLTNode* BuySLTNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc fail:");
    exit(-1);
  }
  else
  {
    newnode->data = x;
    newnode->next = NULL;
  }
  return newnode;
}
//循环创建结点
SLTNode* CreateSList(int n)
{
  SLTNode* phead = NULL, * ptail = NULL;
  for (int i = 0; i < n; ++i)
  {
    SLTNode* newnode = BuySLTNode(i);
    if (phead == NULL)
    {
      phead = ptail = newnode;
    }
    else
    {
      ptail->next = newnode;
      ptail = newnode;
    }
  }
  return phead;
}
// 单链表打印
void SLTPrint(SLTNode *phead)
{
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
  SLTNode* newnode = BuySLTNode(x);
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
    //找尾
  {
    SLTNode* tail = *pphead;
    while (tail->next)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
void SLTPopBack(SLTNode** pphead)
{
  assert(*pphead);
  if ((*pphead) == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTNode* tail = *pphead;
    SLTNode* prev = NULL;
    while (tail->next)
    {
      prev = tail;
      tail = tail->next;
    }
    free(tail);
    prev->next = NULL;
  }
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}
void SLTPopFront(SLTNode** pphead)
{
  assert(*pphead);
  SLTNode* next = (*pphead)->next;
  free(*pphead);
  *pphead = next;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
void SLTEraseAfter(SLTNode* pos)
{
  assert(pos);
  if (pos->next == NULL)
  {
    return;
  }
  else
  {
    SLTNode* nextNode = pos->next;
    pos->next = nextNode->next;
    free(nextNode);
  }
}
// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pos);
  if (pos == *pphead)
  {
    SLTPushFront(pphead,x);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLTNode* newnode = BuySLTNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}
// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pos);
  if (pos==*pphead)
  {
    SLTPopFront(pphead);  
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}
void SLTDestory(SLTNode** pphead)
{
  SLTNode* cur = *pphead;
  while (cur)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur=next;
  }
  *pphead = NULL;
}

SList.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
}SLTNode;
SLTNode* BuySLTNode(SLTDataType x);
SLTNode* CreateSList(int n);
void SLTPrint(SLTNode* phead);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopFront(SLTNode** pphead);
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SLTEraseAfter(SLTNode* pos);
// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
void SLTDestory(SLTNode** pphead);
文章标签：
存储
关键词：
数据结构单链表
日出等日落
目录
相关文章
睡觉待开机
|
4月前
【数据结构】单链表(长期维护)（1）
【数据结构】单链表(长期维护)（1）
睡觉待开机
31 0
java冯坚持
|
2月前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
40 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
白子寰
|
2月前
|
存储
[数据结构] -- 单链表
[数据结构] -- 单链表
白子寰
26 1
杀死一只知更鸟debug
|
3月前
|
存储 Java
java数据结构，线性表链式存储（单链表）的实现
文章讲解了单链表的基本概念和Java实现，包括头指针、尾节点和节点结构。提供了实现代码，包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作，如添加、删除、更新和查找元素，并总结了操作的时间复杂度。
杀死一只知更鸟debug
37 1
java数据结构，线性表链式存储（单链表）的实现
努力学习的小廉
|
2月前
|
存储
【数据结构】——单链表实现
【数据结构】——单链表实现
努力学习的小廉
29 2
徐霞客320
|
2月前
|
存储
数据结构2——单链表
数据结构2——单链表
徐霞客320
34 1
是店小二呀
|
2月前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）（一）
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）
是店小二呀
49 1
星霜旅人
|
2月前
|
存储
数据结构（单链表）
数据结构（单链表）
星霜旅人
19 0
平凡程序猿~
|
2月前
|
存储
数据结构--单链表
数据结构--单链表
平凡程序猿~
24 0
小徐在进步
|
3月前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识，涵盖单链表的定义、优点与缺点，并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现，并提供了尾插法和头插法建立单链表的方法，帮助读者深入理解单链表的基本原理与应用技巧。
小徐在进步
635 6