探索数据结构:单链表的实践和应用

简介: 探索数据结构:单链表的实践和应用

一、前言

前面我们学习了数据结构中的顺序表,知道了顺序表的空间是连续存储的,这与数组非常类似,为我们随机访问数据提供了便利的条件,但顺序表也有着一些不足之处:


  1. 尾部插入删除效率还不错,中部或者头部插入删除需要挪动数据,效率低下。
  2. 顺序表满了以后需要扩容,扩容本身也有一定的消耗。
  3. 扩容存在空间浪费:一次扩的多了容易造成浪费,一次扩的少了可能要频繁扩容。


这些大大增加我们的时间与空间成本。为了解决这个问题,就要学习我们今天要讲解的链表

二、什么是链表

2.1 链表的概念

链表是一种物理存储结构上非连续、非顺序存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。与顺序表不同,链表的存储数据在内存是随机分布的。

链表是由一个个结点组成的,结点如下图所示:

注意:链表中的最后一个结点的next指向空,next=NULL,一个个结点串成了链表:


2.2 链表的分类

链表的种类多种多样,它们大致可以分为三类:

2.2.1 单向或双向

2.2.2 带不带头结点

2.2.3 循环不循环


三、单链表的基本操作

单链表的基本操作包括单链表的初始化判断空链表销毁清空以及求表长这些较为简单的操作,还有更为重要的单链表的取值、按值查找返回元素所在地址、按值查找返回元素所对应序号、结点插入和删除以及头插法和尾插法建立单链表。目前只实现了这些操作,并进行的测试。


3.1 单链表的初始化

单链表的结点定义方式与我们以往定义的方式都不同,它是一个结构体中包含两个成员。一个是存储数值,一个存放下一个结点的地址。

typedef int SLTDataType;
 
typedef  struct SList
{
  SLTDataType val;
  struct SList* next;//下一个结点的地址
}SLT;


3.2 创建一个新结点

后面我们要在单链表中进行头插和尾插,此时插入的不再是像顺序表一样简单的SLDateType数据了,而是一个结点,这个结点是包括SLTDateType数据以及SLTDateType*的指针,因此,为了方便和减少代码的重复度,我们另写一个函数用来专门创建新结点

SLT* CreateNode(SLTDataType x)
{
  SLT* newnode = (SLT*)malloc(sizeof(SLT));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->val = x;
  //原本指向下一个结点的指针放在插入的结点的里面
  //尾插是newnode->next = NULL
  //尾插中经过while循环,tail->next == NULL
  newnode->next = NULL;
  return newnode;
}


3.3 打印单链表

注意:链表和顺序不同的是,顺序表传过来的指针是肯定不会为空的,而链表传过来的指针是可能为空的,比如说当链表中没有元素时,头指针所指向的就是NULL,如果在第一行写上断言就会有问题。

void SLTPrint(SLT* phead)//初位置的指针
{
  SLT* tail = phead;//指向链表的第一个结点(结构体)
  //遍历链表
  while (tail != NULL)//尾结点的next为空,tail指向尾结点
  {
    printf("%d->", tail->val);
    tail = tail->next;
  }
  printf("NULL\n");
}


3.4 单链表尾插

注意:在创建结点时,已经让 结点.next=NULL,所以不需要在插入完结点后,再让新结点的next指针为NULL。

有人可能会有疑问,为什么之前打印链表的时候不用断言指针,而在尾插时就要断言指针,以及为什么函数的形参是二级指针,而不使用一级指针


因为,尾插分为两种情况:


  1. 当链表为空时,头指针phead指向NULL,尾插相当于头插,此时要改变phead的指向,让phead指向这个新结点,此时就需要二级指针来改变一级指针的值(如果我们用一级指针做形参,形参的改变不会影响实参,那么一级指针phead就不会被改变)。
  2. 至于这个什么时候要断言指针,什么时候不用断言指针:
  1. 一级指针也就是phead,当链表为空的时候,phead就是为NULL,phead存在为空的可能。
  2. 而二级指针永远指向phead,phead的地址是永远存在的,那么pphead就一定不可能为空,所以需要断言pphead。
void SLTpushback(SLT** pphead, SLTDataType x)
{
  assert(pphead);
  SLT* newnode = CreateNode(x);//新结点的地址
  if (*pphead == NULL)//改变结构体的指针(二级指针)
  {
    *pphead = newnode; 
  }
  else
  {
    SLT* tail = *pphead;
    while (tail->next != NULL)//tail->next,当链表为空会解引用空指针
    {
      tail = tail->next;
    }
    //下一个结构体的指针被存放在结构体成员里面
    //可以使用一级指针访问结构体的成员来间接访问下一个结构体的指针
    //第一个结点的结构体的指针没有存放,所以要用二级指针
    tail->next = newnode;//修改结构体的内容(一级指针)
  }
}

3.5 单链表头插

头插没什么好说的,记住要断言*pphead,保证链表内容不为空,头删也同理。

void SLTpushfront(SLT** pphead, SLTDataType x)
{
  assert(pphead);
  SLT* newnode = CreateNode(x);
  newnode->next  = *pphead;
  *pphead = newnode;
}


3.6 单链表尾删

要想删除链表中的元素,就必须保证原链表就有元素,因此要断言assert(*pphead)

尾删需要分情况去讨论:

void SLTpopback(SLT** pphead)
{
  assert(pphead);
  assert(*pphead);
  SLT* tail = *pphead;
  if (tail->next == NULL)//只有一个结点
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    while (tail->next->next != NULL)//tail指向的结点后面第二个不为空
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}


3.7 单链表头删

void SLTpopfront(SLT** pphead)
{
  assert(pphead);
  assert(*pphead);
  SLT* tail= *pphead;
  *pphead = tail->next;
  free(tail);
  tail = NULL;
}


3.8 单链表的查找

这个函数返回值不再是void,而是SListNode*,把找到的结点的地址返回去,这个函数一般会跟结点插入删除之类的函数一起使用。

SLT* SLTfind(SLT* phead, SLTDataType x)
{
  SLT* cur = phead;
  while (cur)
  {
    if (cur->val == x)
    {
      return cur;
    }
    else
    {
      cur = cur->next;
    }
  }
  return NULL;
}


3.9 单链表任意位置插入

void SLTInsert(SLT** pphead, SLT* pos, SLTDataType x)
{
  assert(pphead);
  //pphead 是二级指针,不会为空
  //*pphead == NULL 链表为空
  //要么都为空,要么都不为空
  assert((pos && *pphead)||(!pos && !(*pphead)));
 
  if (*pphead == NULL)
  {
    SLTpushfront(pphead, x);
  }
  else
  {
    SLT* prve = *pphead;
    while (prve->next != pos)
    {
      prve = prve->next;
    }
    SLT* newnode = CreateNode(x);
    prve->next = newnode;
    newnode->next = pos;
  }
}

3.10 单链表任意位置删除

这里我要提醒一下,千万不要忘记判断pos是否正确,不要只单单断言pos是否为NULL,还要判断能不能在链表中找到pos这个地址。

void SLTErase(SLT** pphead, SLT* pos)
{
  assert(pphead);
  assert(*pphead);
  assert(pos);
 
  if (*pphead == pos)
  {
    SLTpopfront(pphead);
  }
  else
  {
    SLT* prve = *pphead;
    while (prve->next != pos)
    {
      prve = prve->next;
    }
    prve->next = pos->next;
    free(pos);
  }
}


3.11 单链表的销毁

销毁链表这一块,咱可不敢直接free(phead),因为链表在物理结构上是不连续存储的,销毁链表必须要一个结点一个结点去销毁!!!!最后不要忘记把phead置为NULL

void SLTDestory(SLT** pphead)
{
  assert(pphead);
  SLT* cur = *pphead;
  while (cur)
  {
    //方法一:
    //cur = cur->next;
    //free(*pphead);//释放掉了phead的空间
    //*pphead = cur;
 
    SLT* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}


四、完整代码

4.1 SLT.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int SLTDataType;
 
typedef  struct SList
{
  int val;
  struct SList* next;//下一个结点的地址
}SLT;
 
void SLTPrint(SLT* phead);//打印链表
 
SLT* CreateNode(SLTDataType x, SLT* tail);//创建一个新结点
 
void SLTpushback(SLT** pphead, SLTDataType x);//尾插
void SLTpushfront(SLT** pphead, SLTDataType x);//头插
void SLTpopback(SLT** pphead);
void SLTpopfront(SLT** phead);
 
SLT* SLTfind(SLT* phead, SLTDataType x);
 
//与find函数结合使用
//在pos前面插入
void SLTInsert(SLT** pphead, SLT* pos, SLTDataType x);
//删除pos位置
void SLTErase(SLT** pphead, SLT* pos);
 
void SLTDestory(SLT** pphead);//销毁

4.2 SLT.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
 
SLT* CreateNode(SLTDataType x)
{
  SLT* newnode = (SLT*)malloc(sizeof(SLT));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->val = x;
  //原本指向下一个结点的指针放在插入的结点的里面
  //尾插是newnode->next = NULL
  //尾插中经过while循环,tail->next == NULL
  newnode->next = NULL;
  return newnode;
}
 
void SLTPrint(SLT* phead)//初位置的指针
{
  SLT* tail = phead;//指向链表的第一个结点(结构体)
  //遍历链表
  while (tail != NULL)//尾结点的next为空,tail指向尾结点
  {
    printf("%d->", tail->val);
    tail = tail->next;
  }
  printf("NULL\n");
}
 
 
void SLTpushback(SLT** pphead, SLTDataType x)
{
  assert(pphead);
  SLT* newnode = CreateNode(x);//新结点的地址
  if (*pphead == NULL)//改变结构体的指针(二级指针)
  {
    *pphead = newnode; 
  }
  else
  {
    SLT* tail = *pphead;
    while (tail->next != NULL)//tail->next,当链表为空会解引用空指针
    {
      tail = tail->next;
    }
    //下一个结构体的指针被存放在结构体成员里面
    //可以使用一级指针访问结构体的成员来间接访问下一个结构体的指针
    //第一个结点的结构体的指针没有存放,所以要用二级指针
    tail->next = newnode;//修改结构体的内容(一级指针)
  }
}
 
void SLTpushfront(SLT** pphead, SLTDataType x)
{
  assert(pphead);
  SLT* newnode = CreateNode(x);
  newnode->next  = *pphead;
  *pphead = newnode;
}
 
void SLTpopback(SLT** pphead)
{
  assert(pphead);
  assert(*pphead);
  SLT* tail = *pphead;
  if (tail->next == NULL)//只有一个结点
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    while (tail->next->next != NULL)//tail指向的结点后面第二个不为空
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}
 
void SLTpopfront(SLT** pphead)
{
  assert(pphead);
  assert(*pphead);
  SLT* tail= *pphead;
  *pphead = tail->next;
  free(tail);
  tail = NULL;
}
 
SLT* SLTfind(SLT* phead, SLTDataType x)
{
  SLT* cur = phead;
  while (cur)
  {
    if (cur->val == x)
    {
      return cur;
    }
    else
    {
      cur = cur->next;
    }
  }
  return NULL;
}
 
void SLTInsert(SLT** pphead, SLT* pos, SLTDataType x)
{
  assert(pphead);
  //pphead 是二级指针,不会为空
  //*pphead == NULL 链表为空
  //要么都为空,要么都不为空
  assert((pos && *pphead)||(!pos && !(*pphead)));
 
  if (*pphead == NULL)
  {
    SLTpushfront(pphead, x);
  }
  else
  {
    SLT* prve = *pphead;
    while (prve->next != pos)
    {
      prve = prve->next;
    }
    SLT* newnode = CreateNode(x);
    prve->next = newnode;
    newnode->next = pos;
  }
}
 
void SLTErase(SLT** pphead, SLT* pos)
{
  assert(pphead);
  assert(*pphead);
  assert(pos);
 
  if (*pphead == pos)
  {
    SLTpopfront(pphead);
  }
  else
  {
    SLT* prve = *pphead;
    while (prve->next != pos)
    {
      prve = prve->next;
    }
    prve->next = pos->next;
    free(pos);
  }
}
 
void SLTDestory(SLT** pphead)
{
  assert(pphead);
  SLT* cur = *pphead;
  while (cur)
  {
    //方法一:
    //cur = cur->next;
    //free(*pphead);//释放掉了phead的空间
    //*pphead = cur;
 
    SLT* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}
相关文章
|
22天前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
51 4
|
15天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
37 5
|
13天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
37 1
|
23天前
|
缓存 NoSQL PHP
Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出
本文深入探讨了Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出。文章还介绍了Redis在页面缓存、数据缓存和会话缓存等应用场景中的使用,并强调了缓存数据一致性、过期时间设置、容量控制和安全问题的重要性。
36 5
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
62 4
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
22天前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
40 0
|
1月前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
43 0
|
6月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表