欢迎来到尧图网

客户服务 关于我们

您的位置：首页 > 房产 > 建筑 > 数据结构--单链表（图文）

数据结构--单链表（图文）

2024/10/24 15:13:31 来源：https://blog.csdn.net/SouTY_C/article/details/139809130  浏览:  次   关键词：数据结构--单链表（图文）

单链表的概念

在单链表中，每个元素（称为节点）包含两部分：一部分是存储数据的数据域，另一部分是存储下一个节点地址的指针域。这里的“单”指的是每个节点只有一个指向下一个节点的指针。
在这里插入图片描述

  1. 节点：链表中的基本单元，通常由数据域和指针域组成。数据域用于存储实际的数据，而指针域用于指向链表中的下一个节点。

  2. 链：通过节点中的指针链接形成的序列。在单链表中，这种链接是单向的，即只能从一个节点指向下一个节点。

  3. 头节点：链表的第一个节点，用于标识链表的开始。有时，头节点仅作为链表的头部标识，不存储实际数据。

  4. 尾节点：链表的最后一个节点，其指针域通常为空（NULL），表示链表的结束。

  5. 非连续性：与数组不同，单链表的节点在内存中不必连续存储。每个节点的位置由其前一个节点的指针决定。

  6. 动态性：单链表的大小是动态的，可以在运行时通过增加或删除节点来改变链表的长度。

单链表的主要特点是其灵活性和动态性，它可以有效地进行插入和删除操作，尤其是在不知道数据数量的情况下，或者当数据量变化较大时。但是，由于需要通过指针进行遍历，单链表在访问特定元素时可能不如数组高效。以下是其在各种操作中的优势：

  • 插入和删除：在单链表中插入或删除节点只需要O(1)的时间，前提是已经有了指向要操作节点的指针。
  • 空间利用：单链表不需要预分配固定的存储空间，它可以根据需要动态地分配内存。

单链表的实现

首先创建三个文件：

  • SList.h —— 用于声明函数的头文件
  • SList.c —— 单链表主要函数的实现
  • test.c——测试单链表。

创建单链表

typedef int SLTDataType;//方便后续使用更改类型//创建一个节点
typedef struct SListNode
{SLTDataType data;//该节点储存的数据struct SListNode* next;//指向下一个节点的指针
}SListNode;

销毁链表

从前向后依次释放节点，最后将头节点置为NULL 。

void SListDesTroy(SListNode** pphead)//销毁链表
{assert(pphead && *pphead);SListNode* pcur = *pphead;while (pcur){SListNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

打印节点数据

遍历依次打印即可。

void SLTPrint(SListNode* phead)//打印节点数据
{assert(phead);SListNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

申请一块节点

在进行插入节点时，我们需要先申请一块节点来进行插入，所以我们将申请节点单独封装成一个函数。

SListNode* SLTBuyNode(SLTDataType x)//增加节点(空间)
{//开辟一个节点空间SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){perror("malloc");exit(1);}//设置数据并返回该节点地址newnode->data = x;newnode->next = NULL;return newnode;
}

尾插数据

两种情况

  • 情况一：链表为空直接申请新节点给头节点；
  • 情况二：链表不为空，遍历找到尾节点，再将新节点接入即可。

在这里插入图片描述

void SLTPushBack(SListNode** pphead, SLTDataType x)//尾插数据
{assert(pphead);//不能为空，否则就会对空指针解引用if (*pphead == NULL)//指向头节点的指针为空，也就是链表为空{*pphead = SLTBuyNode(x);}else{SListNode* newnode = *pphead;while (newnode->next){newnode = newnode->next;}newnode->next = SLTBuyNode(x);}
}

头插数据

两种情况

  • 情况一：链表为空直接申请新节点给头节点。
  • 情况二：链表不为空，先将pphead（头节点）保存起来，然后让pphead指向新插入的节点，在让*pphead->next指向刚才保存好的原本的头节点。
    在这里插入图片描述
void SLTPushFront(SListNode** pphead, SLTDataType x)//头插数据
{assert(pphead);if (*pphead == NULL){*pphead = SLTBuyNode(x);}else{SListNode* pcur = *pphead;*pphead = SLTBuyNode(x);(*pphead)->next = pcur;}
}

尾删数据

两种情况

  • 情况一：链表只有一个数据，直接释放该节点并将头节点置为空。
  • 情况二：链表有多个数据节点，遍历找到尾节点的前一个节点，释放该节点的next节点，再将该节点的next置为空。
    在这里插入图片描述
void SLTPopBack(SListNode** pphead)//尾删数据
{assert(pphead && *pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SListNode* pcur = *pphead;while (pcur->next->next){pcur = pcur->next;}free(pcur->next);pcur->next = NULL;}
}

头删数据

两种情况

  • 情况一：链表只有一个数据，直接释放该节点并将头节点置为空。
  • 情况二：链表有多个数据节点，先将pphead（头节点）保存起来，然后让pphead指向*pphead->next（新的头节点），然后释放刚才保存的节点（原头节点）。
    在这里插入图片描述
void SLTPopFront(SListNode** pphead)//头删数据
{assert(pphead && *pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SListNode* pcur = (*pphead);*pphead = (*pphead)->next;free(pcur);}
}

查找数据

从前向后遍历整个链表，如果 plist->data == x，就说明找到了，返回 plist 此时的值，如果plist = NULL了，就说明这个链表中没有该数据，则返回空。

SListNode* SLTFind(SListNode* phead, SLTDataType x)//查找数据
{assert(phead);SListNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

有了查找函数，就可以实现任意位置的增加数据和删除数据的操作了。

在指定位置之前插入数据

两种情况

  • 情况一：指定位置为头节点则直接头插。
  • 情况二：指定位置为其他节点，遍历找到指定节点的前一个节点，在该节点后插入新数据。
    在这里插入图片描述
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x)//在指定位置之前插入数据
{assert(pphead&&*pphead);if (*pphead == pos){SLTPushFront(pphead,x);}else{SListNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}SListNode* newnode = SLTBuyNode(x);pcur->next = newnode;newnode->next = pos;}
}

在指定位置之后插入数据

在指定位置后直接插入即可。

void SLTInsertAfter(SListNode* pos, SLTDataType x)//在指定位置之后插入数据
{assert(pos);SListNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

删除指定位置节点

两种情况

  • 情况一：指定位置为头节点则直接头删。
  • 情况二：指定位置为其他节点，遍历找到指定位置的前一个节点，先将该节点的next指针指向指定位置的next位置，然后再释放指定位置。（不能改变顺序，否则找不到指定位置的下一个节点了）
    在这里插入图片描述
void SLTErase(SListNode** pphead, SListNode* pos)//删除pos节点
{assert(*pphead && pphead);assert(pos);if (*pphead == pos){SLTPopFront(pphead);}else{SListNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;}
}

删除指定位置之后的数据

先将指定位置的的下一个位置保存起来，让指定位置的next指针指向保存位置的下一个位置，然后释放掉保存的位置也就是指定位置之后的数据。
在这里插入图片描述

void SLTEraseAfter(SListNode* pos)//删除pos之后的节点
{assert(pos && pos->next);SListNode* pcur = pos->next;pos->next = pos->next->next;free(pcur);pcur = NULL;	
}

单链表源码

SList.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>typedef int SLTDataType;//创建一个节点
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SListNode;SListNode* SLTBuyNode(SLTDataType x);//增加节点(空间)void SLTPrint(SListNode* phead);//打印节点数据void SListDesTroy(SListNode** pphead);//销毁链表void SLTPushBack(SListNode** pphead, SLTDataType x);//尾插数据void SLTPushFront(SListNode** pphead, SLTDataType x);//头插数据SListNode* SLTFind(SListNode* phead, SLTDataType x) ;//查找数据void SLTPopBack(SListNode** pphead);//尾删数据void SLTPopFront(SListNode** pphead);//头删数据void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x);//在指定位置之前插入数据void SLTInsertAfter(SListNode* pos, SLTDataType x);//在指定位置之后插入数据void SLTErase(SListNode** pphead, SListNode* pos);//删除pos节点void SLTEraseAfter(SListNode* pos);//删除pos之后的节点

SList.c

#include"SList.h"SListNode* SLTBuyNode(SLTDataType x)//增加节点(空间)
{//开辟一个节点空间SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){perror("malloc");exit(1);}//设置数据并返回该节点地址newnode->data = x;newnode->next = NULL;return newnode;
}
void SLTPrint(SListNode* phead)//打印节点数据
{assert(phead);SListNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
void SListDesTroy(SListNode** pphead)//销毁链表
{assert(pphead && *pphead);SListNode* pcur = *pphead;while (pcur){SListNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}void SLTPushBack(SListNode** pphead, SLTDataType x)//尾插数据
{assert(pphead);if (*pphead == NULL){*pphead = SLTBuyNode(x);}else{SListNode* newnode = *pphead;while (newnode->next){newnode = newnode->next;}newnode->next = SLTBuyNode(x);}
}void SLTPushFront(SListNode** pphead, SLTDataType x)//头插数据
{assert(pphead);if (*pphead == NULL){*pphead = SLTBuyNode(x);}else{SListNode* pcur = *pphead;*pphead = SLTBuyNode(x);(*pphead)->next = pcur;}
}SListNode* SLTFind(SListNode* phead, SLTDataType x)//查找数据
{assert(phead);SListNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}void SLTPopBack(SListNode** pphead)//尾删数据
{assert(pphead && *pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SListNode* pcur = *pphead;while (pcur->next->next){pcur = pcur->next;}free(pcur->next);pcur->next = NULL;}
}void SLTPopFront(SListNode** pphead)//头删数据
{assert(pphead && *pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SListNode* pcur = (*pphead);*pphead = (*pphead)->next;free(pcur);}
}void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x)//在指定位置之前插入数据
{assert(pphead&&*pphead);if (*pphead == pos){SLTPushFront(pphead,x);}else{SListNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}SListNode* newnode = SLTBuyNode(x);pcur->next = newnode;newnode->next = pos;}
}void SLTInsertAfter(SListNode* pos, SLTDataType x)//在指定位置之后插入数据
{assert(pos);SListNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}void SLTErase(SListNode** pphead, SListNode* pos)//删除pos节点
{assert(*pphead && pphead);assert(pos);if (*pphead == pos){SLTPopFront(pphead);}else{SListNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;}
}void SLTEraseAfter(SListNode* pos)//删除pos之后的节点
{assert(pos && pos->next);SListNode* pcur = pos->next;pos->next = pos->next->next;free(pcur);pcur = NULL;	
}

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

相关资讯

热文排行

最新新闻

推荐新闻

热搜词

开源文生图霸主归来！Stable Diffusion 3.5发布全家桶,可以创建更逼真的图像。 牛客周赛 Round 64（A~E） 2024 睿抗机器人开发者大赛（RAICOM)-【网络安全】CTF 部分WP 数据结构修炼——常见的排序算法：插入/希尔/选择/堆排/冒泡/快排/归并/计数 AFSim仿真系统 --- 系统简解_13 武器 L0G1000 Linux 基础知识