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

数据结构2——单链表

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

在数据结构1——顺序表（C语言版）中，我们已经了解了顺序表的使用和实现，总结一下顺序表的优点：

①尾插尾删效率足够快；

②下标的随机访问和修改也足够方便。

可除此之外顺序表也确实存在着不足：

①头部和中部的插入删除效率都不高（时间复杂度为O(N)）；

②扩容需要申请新空间，拷贝数据，释放旧空间，有一定的消耗；

③扩容可能存在空间浪费（我们的扩容函数是2倍增长，比如：当前容量是100，我需要再插入3个数据，按照我的2倍扩容机制就会扩容到200，这时就会浪费了97个数据的空间）。

了解了顺序表的不足，下面我们就来学习一下链表，看一看链表能不能解决顺序表的不足。


1.链表

为了避免像顺序表那样插入数据时造成扩容浪费，那我就边插入边扩容行不行呢？只要插入一个新数据我就开一块空间存一个。那么问题来了，如果这么搞，这些数据就不连续了啊，那还怎么像顺序表那样成为一个表结构呢？~~~~~~对！不要忘了指针，我们可以用指针把这写不连续的空间串起来啊！

1.1链表的概念及结构

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

也就是说，链表并不像顺序表那样在物理空间上是连续存储的，链表的每一个单位里存的不仅仅有数据域，还存的有指针域，我们把每一个这样的单位称为节点。

如图：

1.2 链表的分类

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

①单向或者双向

②带头或者不带头

③循环或者非循环

④最常用的两个

1.无头单向非循环链表

结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构。

2.带头双向循环链表

结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。

2.无头单链表的实现

1. 节点

经过上面的分析我们得知，链表的主要结构为节点，所以我们先用结构体定义节点：

//定义节点
typedef int SLTDataType;//typedef节点的数据域
 
typedef struct SListNode
{
  SLTDataType data;//定义节点的数据域
  struct SListNode* next;//定义指向下一个节点的指针
}SLTNode;

2.遍历链表

//遍历链表函数实现
void SLTPrint(SLTNode* phead)
{
  SLTNode* cur = phead;//定义当前节点
  //while (cur != NULL)//等于空就结束
  while (cur)
  {
    printf("%d->", cur->data);
    cur = cur->next;//将下一个节点的地址（指针）赋值给当前节点
  }
 
  printf("NULL\n");
}

3.动态增加新节点

//增加新节点函数实现
SLTNode* BuySListNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);//malloc为空直接退出
  }
 
  newnode->data = x;
  newnode->next = NULL;
 
  return newnode;
}

4.查找（修改）

//查找下标pos函数实现
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
 
    cur = cur->next;
  }
 
  return NULL;
}

5.插入

5.1 尾插

//尾插函数实现
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  
 
  SLTNode* newnode = BuySListNode(x);
 
  if (*pphead == NULL)
  {
    //改变结构体的指针，所以要用到指针的指针
    *pphead = newnode;
  }
  else
  {
    SLTNode* tail = *pphead;//定义尾节点
    while (tail->next != NULL)//只有尾节点的next指针为空
    {
      tail = tail->next;
    }
    //改变结构体，只需用到结构体的指针即可
    tail->next = newnode;
  }
}

5.2 头插

//头插函数实现
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = BuySListNode(x);
 
  newnode->next = *pphead;
  *pphead = newnode;
}

5.3 在pos之前插入x

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

5.4 在pos之后插入x

//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
 
  SLTNode* newnode = BuySListNode(x);
  pos->next = newnode;
  newnode->next = pos->next;
}

6.删除

6.1 尾删

//尾删
void SLTPopBack(SLTNode** pphead)
{
  assert(pphead);
  //1、空
  assert(*pphead);
  //2、一个节点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else//3、一个以上节点   找尾
  {
    SLTNode* tailPrev = NULL;//将要尾删的前一个节点的指针域置空
    SLTNode* tail = *pphead;
    while (tail->next)
    {
      tailPrev = tail;
      tail = tail->next;
    }
    free(tail);
    tailPrev->next = NULL;
  }
}

6.2 头删

//头删函数实现
void SLTPopFront(SLTNode** pphead)
{
  assert(pphead);
 
  //空
  assert(*pphead);
  //非空
  SLTNode* newhead = (*pphead)->next;
  free(*pphead);
  *pphead = newhead;
}

6.3 删除pos位置

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

6.4 删除pos的后一个位置

//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{
  assert(pos);
 
  //检查pos是否为尾节点
  assert(pos->next);
 
  SLTNode* posNext = pos->next;
 
  pos->next = posNext->next;
  free(posNext);
  posNext = NULL;
}

7.测试（仅测试一个）

int main() 
{
  SLTNode* plist = NULL;
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPrint(plist);
  return 0;
}

*源代码

SList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
//定义节点
typedef int SLTDataType;//typedef节点的数据域
 
typedef struct SListNode
{
  SLTDataType data;//定义节点的数据域
  struct SListNode* next;//定义指向下一个节点的指针
}SLTNode;
 
//遍历链表函数声明
void SLTPrint(SLTNode* phead);
 
//增加新节点函数声明
SLTNode* BuySListNode(SLTDataType x);
 
//尾插函数声明
void SLTPushBack(SLTNode** phead, SLTDataType x);
//头插函数声明
void SLTPushFront(SLTNode** pphead, SLTDataType x);
 
//尾删函数声明
void SLTPopBack(SLTNode** pphead);
//头删函数声明
void SLTPopFront(SLTNode** pphead);
 
//查找下标pos函数声明
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
 
//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos之后插入x
void SLTInsertAfter( SLTNode* pos, SLTDataType x);
 
//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
 
#include "SList.h"
 
//遍历链表函数实现
void SLTPrint(SLTNode* phead)
{
  SLTNode* cur = phead;//定义当前节点
  //while (cur != NULL)//等于空就结束
  while (cur)
  {
    printf("%d->", cur->data);
    cur = cur->next;//将下一个节点的地址（指针）赋值给当前节点
  }
 
  printf("NULL\n");
}
 
//增加新节点函数实现
SLTNode* BuySListNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);//malloc为空直接退出
  }
 
  newnode->data = x;
  newnode->next = NULL;
 
  return newnode;
}
 
//尾插函数实现
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  
 
  SLTNode* newnode = BuySListNode(x);
 
  if (*pphead == NULL)
  {
    //改变结构体的指针，所以要用到指针的指针
    *pphead = newnode;
  }
  else
  {
    SLTNode* tail = *pphead;//定义尾节点
    while (tail->next != NULL)//只有尾节点的next指针为空
    {
      tail = tail->next;
    }
    //改变结构体，只需用到结构体的指针即可
    tail->next = newnode;
  }
}
//头插函数实现
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = BuySListNode(x);
 
  newnode->next = *pphead;
  *pphead = newnode;
}
 
//尾删函数声明
void SLTPopBack(SLTNode** pphead)
{
  assert(pphead);
  //1、空
  assert(*pphead);
  //2、一个节点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else//3、一个以上节点   找尾
  {
    SLTNode* tailPrev = NULL;//将要尾删的前一个节点的指针域置空
    SLTNode* tail = *pphead;
    while (tail->next)
    {
      tailPrev = tail;
      tail = tail->next;
    }
    free(tail);
    tailPrev->next = NULL;
  }
}
//头删函数实现
void SLTPopFront(SLTNode** pphead)
{
  assert(pphead);
 
  //空
  assert(*pphead);
  //非空
  SLTNode* newhead = (*pphead)->next;
  free(*pphead);
  *pphead = newhead;
}
 
//查找下标pos函数实现
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
 
    cur = cur->next;
  }
 
  return NULL;
}
 
//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pphead);
  assert(pos);
 
  if (pos == *pphead)
  {
    SLTPushFront(pphead, x);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
 
    SLTNode* newnode = BuySListNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}
 
//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
 
  SLTNode* newnode = BuySListNode(x);
  pos->next = newnode;
  newnode->next = pos->next;
}
 
//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(pos);
 
  if (pos == *pphead)
  {
    SLTPopFront(pphead);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
 
    prev->next = pos->next;
    free(pos);
    pos = NULL;
  }
}
 
//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{
  assert(pos);
 
  //检查pos是否为尾节点
  assert(pos->next);
 
  SLTNode* posNext = pos->next;
 
  pos->next = posNext->next;
  free(posNext);
  posNext = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
 
#include "SList.h"
 
int main() 
{
  SLTNode* plist = NULL;
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPrint(plist);
  return 0;
}
文章标签：
存储
关键词：
数据结构单链表
徐霞客320
目录
相关文章
睡觉待开机
|
3月前
【数据结构】单链表(长期维护)（1）
【数据结构】单链表(长期维护)（1）
睡觉待开机
30 0
java冯坚持
|
1月前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
33 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
白子寰
|
1月前
|
存储
[数据结构] -- 单链表
[数据结构] -- 单链表
白子寰
26 1
杀死一只知更鸟debug
|
2月前
|
存储 Java
java数据结构，线性表链式存储（单链表）的实现
文章讲解了单链表的基本概念和Java实现，包括头指针、尾节点和节点结构。提供了实现代码，包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作，如添加、删除、更新和查找元素，并总结了操作的时间复杂度。
杀死一只知更鸟debug
33 1
java数据结构，线性表链式存储（单链表）的实现
努力学习的小廉
|
1月前
|
存储
【数据结构】——单链表实现
【数据结构】——单链表实现
努力学习的小廉
28 2
是店小二呀
|
1月前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）（一）
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）
是店小二呀
45 1
星霜旅人
|
1月前
|
存储
数据结构（单链表）
数据结构（单链表）
星霜旅人
17 0
平凡程序猿~
|
1月前
|
存储
数据结构--单链表
数据结构--单链表
平凡程序猿~
23 0
是店小二呀
|
1月前
|
存储 缓存
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）（二）
【初阶数据结构】深入解析单链表:探索底层逻辑（无头单向非循环链表）
是店小二呀
46 0
小徐在进步
|
2月前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识，涵盖单链表的定义、优点与缺点，并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现，并提供了尾插法和头插法建立单链表的方法，帮助读者深入理解单链表的基本原理与应用技巧。
小徐在进步
556 6