数据结构——单链表

简介: 数据结构——单链表

一、 链表的概念及结构

1.1 链表的概念

概念:链表是⼀种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表

中的指针链接次序实现的 。


链表的结构跟⽕⻋⻋厢相似,淡季时⻋次的⻋厢会相应减少,旺季时⻋次的⻋厢会额外增加⼏节。只 需要将⽕⻋⾥的某节⻋厢去掉/加上,不会影响其他⻋厢,每节⻋厢都是独⽴存在的。


车厢是独⽴存在的,且每节⻋厢都有⻋⻔。想象⼀下这样的场景,假设每节⻋厢的⻋⻔都是锁上的状 态,需要不同的钥匙才能解锁,每次只能携带⼀把钥匙的情况下如何从⻋头⾛到⻋尾?

最简单的做法:每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。


在链表⾥,每节“⻋厢”是什么样的呢?

1fc346c2d4f23f06246087bd1069618b_b4b62243075742dabcb00e0c551c89bc.png

与顺序表不同的是,链表⾥的每节"⻋厢"都是独⽴申请下来的空间,我们称之为“结点/节点”


节点的组成主要有两个部分: 当前节点要保存的数据  和  保存下⼀个节点的地址(指针变量)。

图中指针变量 plist保存的是第⼀个节点的地址,我们称plist此时“指向”第⼀个节点,如果我们希 望plist“指向”第⼆个节点时,只需要修改plist保存的内容为0x0012FFA0.


为什么还需要指针变量来保存下⼀个节点的位置?


链表中每个节点都是独立申请的(即需要插⼊数据时才去申请⼀块节点的空间),我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。


1.2 链表的结构

结合前⾯学到的结构体知识,我们可以给出每个节点对应的结构体代码:


假设当前保存的节点为整型:


struct SListNode
{
 int data; //节点数据
 struct SListNode* next; //指针变量⽤保存下⼀个节点的地址
};


二、单链表的实现

2.1  单链表的尾插和头插

2.1.1  SList.h

#define _CRT_SECURE_NO_WARNINGS
typedef int SListDateType;
typedef struct SListNode
{
    SListDateType val;
    struct SListNode* next;
}SLNode;
//没有初始化,若链表为空,则插入的第一个节点为头节点
//头插和尾插
void SLPushBack(SLNode** pphead,SListDateType x);
void SLPushFront(SLNode** pphead,SListDateType x);

2.1.2   SList.c

尾插:


思路一: 若头节点是NULL,插入的第一个节点为头节点;


判断当前节点的下一节点是否为空,若为空,则为尾节点,在尾节点后面插入新节点


#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
//申请一个节点
SLNode* SLBuyNode(SListDateType x)
{
  SLNode* node = (SLNode*)malloc(sizeof(SLNode));
  if (node == NULL)
  {
    perror("malloc fail:");
      return NULL;
  }
  node->val = x;
  node->next = NULL;
  return node;
}
void SLPushBack(SLNode** pphead, SListDateType x)
{
  assert(pphead);
  SLNode* node = SLBuyNode(x);
  SLNode* pcur = *pphead;
  if ((*pphead) == NULL)
  {
    *pphead = node;
    return 1;
  }
  while (pcur->next != NULL)
  {
    pcur = pcur->next;
  }
  pcur->next = node;
}


尾插:


思路二:若头节点是NULL,插入的第一个节点为头节点;


若第一个节点不是空,说明链表至少一个节点,pcur为当前节点,prve为前一个节点,判断pcur是否为空,若为空,则prve可定位到尾节点插入新节点


void SLPushBack(SLNode** pphead, SListDateType x)
{
  assert(pphead);
  SLNode* node = SLBuyNode(x);
  SLNode* pcur = *pphead;
  SLNode* prev = NULL;
  if ((*pphead) == NULL)
  {
    *pphead = node;
    return 1;
  }
  while (pcur)
  {
    prev = pcur;
    pcur = pcur->next;
  }
  prev->next = node;
}


头插:


注:在这里头指针改变了指向,所以传的二级指针

void SLPushFront(SLNode** pphead,SListDateType x)
{
  assert(pphead);
  SLNode* node = SLBuyNode(x);
  node->next = *pphead;
  *pphead = node;
}

2.2  单链表的头删和尾删

2.2.1  SList.h

//头删和尾删
void SLPopBack(SLNode** pphead);
void  SLPopFront(SLNode** pphead);

2.2.2  SList.c

尾删:


首先保证至少有一个节点


1)若只有一个节点,释放该节点空间,使指向该空间的头节点置为空


2)若有俩个及以上节点,pcur为当前节点,prve为前一个节点,判断pcur的下一个节点是否为空,若为空,则prve可定位到次尾节点,删除尾节点,使次尾节点置为空


void SLPopBack(SLNode** pphead)
{
  assert(pphead && *pphead);//至少有一个节点
  SLNode* del = *pphead;
  SLNode* prev = NULL;
  //若只有一个节点
  if (del->next == NULL)
  {
    free(del);
    del = NULL;
    return 1;
  }
  //不止一个节点
  while (del->next)
  {
    prev = del;
    del = del->next;
  }
  prev->next = NULL;
  free(del);
  del = NULL;
}


头删:

void  SLPopFront(SLNode** pphead)
{
  assert(pphead && *pphead);//至少有一个节点
  SLNode* del = *pphead;
  *pphead = (*pphead)->next;
  free(del);
  del = NULL;
}

2.3   打印链表

2.2.1  SList.h

//打印数据
void SLPrint(SLNode* pphead);

2.3.2 SList.c

 void SLPrint(SLNode* pphead)
{
    assert(pphead);
    SLNode* pcur = pphead;
    while(pcur)
    {
        printf("%d->", pcur->val);
        pcur = pcur->next;
    }
    printf("NULL\n");
}

2.4   在指定位置之前插入数据和指定位置之后插入数据

2.4.1  SList.h

//在指定位置之前插入数据和指定位置之后插入数据
void SLInsertFront(SLNode** pphead, SLNode* pos, SListDateType x);
void SLInsertAfter(SLNode** pphead, SLNode* pos, SListDateType x);

2.4.2 SList.c

void SLInsertFront(SLNode** pphead, SLNode* pos, SListDateType x)
{
  assert(pphead && *pphead && pos);
  //若pos为第一个节点或者链表只有一个节点,->头插
  SLNode* node = SLBuyNode(x);
  SLNode* prev =*pphead;
  if (pos == *pphead)
  {
    node->next = *pphead;
    *pphead = node;
  }
  else//pose为第2,3,4...节点
  {
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    node->next = pos;
    prev->next = node;
  }
}
void SLInsertAfter(SLNode** pphead, SLNode* pos, SListDateType x)
{
  assert(pphead&&pos&&*pphead);
  SLNode* node = SLBuyNode(x);
  node->next = pos->next;
  pos->next = node;
}


2.5  在指定位置删除数据和指定位置之后删除数据

2.5.1 List.h

//在指定位置删除数据和指定位置之后删除数据
void SLErase(SLNode** pphead, SLNode* pos);
void SLEraseAfter(SLNode** pphead, SLNode* pos);

2.5.1 List.c

void SLErase(SLNode** pphead, SLNode* pos)
{
  assert(pphead && *pphead && pos);
  SLNode* prev = *pphead;
  //pos为第一个节点或者链表只有一个节点
  if (pos == *pphead)
  {
    *pphead=(*pphead)->next;
    free(pos);
    pos = NULL;
  }
  else//为第2,3,4....个节点
  {
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    pos = NULL;
  }
}
void SLEraseAfter(SLNode** pphead, SLNode* pos)
{
  assert(pphead && *pphead && pos);
  assert((*pphead)->next);
  assert(pos->next);
  SLNode* del = pos->next;
  pos->next = del->next;
  free(del);
  del = NULL;
}


2.6  查找数据

2.6.1  List.h

//查找数据
SLNode* SLFind(SLNode** pphed, SListDateType x);

2.6.2  List.c

SLNode* SLFind(SLNode** pphead,SListDateType x)
{
  assert(pphead);
  SLNode* pcur = *pphead;
  while (pcur)
  {
    if (pcur->val == x)
    {
      return pcur;
    }
    pcur = pcur->next;
  }
     return NULL;
}

2.7    销毁

思路:销毁时,会使链表断裂,所以在销毁当前节点时,需要提前保存好下一个节点


2.7.1  SList.h

//销毁
void SLDestroy(SLNode** pphead);

2.7.2  SList.c

void SLDestroy(SLNode** pphead)
{
        assert(pphead&&*pphead);
  SLNode* pcur = *pphead;
  SLNode* next = (*pphead)->next;
  while(pcur)
  {
    free(pcur);
    pcur = next;
    if (next)
    {
      next = next->next;
    }
  }
  *pphead = NULL;
}


2.8   测试代码

2.8.1  text.c

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"
#include<stdlib.h>
int main()
{
  SLNode* s = NULL;
  SLPushBack(&s,1);
  SLPushBack(&s, 2);
  SLPushBack(&s, 3);
  SLPushBack(&s, 4);
  SLPrint(s);
  SLNode*node= SLFind(&s, 2);
    SLInsertFront(&s,node, 77);
  SLPrint(s);
   node = SLFind(&s, 4);
  SLInsertAfter(&s, node, 55);
  SLPrint(s);
  //在指定位置删除数据和指定位置之后删除数据
  SLErase(&s, node);
  SLPrint(s);
  node = SLFind(&s, 1);
  SLEraseAfter(&s, node);
  SLPrint(s);
  //查找数据
//
//     SLPushFront(&s, 5);
//   SLPrint(s);
//
//  //头删和尾删
//  SLPopBack(&s);
//  SLPrint(s);
//
//  SLPopFront(&s);
//SLPrint(s);
  return 0;
}


测试结果:

相关文章
|
4月前
【数据结构】单链表(长期维护)(1)
【数据结构】单链表(长期维护)(1)
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
39 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
2月前
|
存储
[数据结构] -- 单链表
[数据结构] -- 单链表
26 1
|
3月前
|
存储 Java
java数据结构,线性表链式存储(单链表)的实现
文章讲解了单链表的基本概念和Java实现,包括头指针、尾节点和节点结构。提供了实现代码,包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作,如添加、删除、更新和查找元素,并总结了操作的时间复杂度。
java数据结构,线性表链式存储(单链表)的实现
|
2月前
|
存储
【数据结构】——单链表实现
【数据结构】——单链表实现
|
2月前
|
存储
数据结构2——单链表
数据结构2——单链表
34 1
|
2月前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(一)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
2月前
|
存储
数据结构(单链表)
数据结构(单链表)
18 0
|
2月前
|
存储
数据结构--单链表
数据结构--单链表
|
3月前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识,涵盖单链表的定义、优点与缺点,并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现,并提供了尾插法和头插法建立单链表的方法,帮助读者深入理解单链表的基本原理与应用技巧。
628 6