C++|C++ 数据结构超详细讲解单链表 C++数据结构超详细讲解单链表

前言
一、链表是什么

链表的分类

二、链表的实现

总结

(?′?`?) 单链表

前言上篇顺序表结尾了解了顺序表的诸多缺点，链表的特性很好的解决了这些问题，本期我们来认识单链表。

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

文章图片

由图，链式结构在逻辑上是连续的，但是物理上不一定连续
显示中结点一般是从堆上申请出来的
从堆上申请的空间，是按照一定的策略划分的，两次申请的空间，可能连续，可能不连续，见顺序表

文章图片

链表的分类
链表也可以分为很多种
1. 单向或者双向
2. 带头或者不带头
3. 循环或非循环

文章图片

文章图片

我们最常用的还是无头单向非循环链表和带头双向循环链表本篇我们实现无头单向非循环链表增删查改

二、链表的实现基本结点结构

typedef int SLTDateType; typedef struct SListNode{SLTDateType data; struct SListNode* next; }SListNode;

头文件

//llist.h#pragma once#include #include #include #include typedef int SLTDateType; typedef struct SListNode{ SLTDateType data; struct SListNode* next; }SListNode; // 动态申请一个节点SListNode* BuySListNode(SLTDateType x); // 单链表打印void SListPrint(SListNode* plist); // 单链表尾插void SListPushBack(SListNode** pplist, SLTDateType x); // 单链表的头插void SListPushFront(SListNode** pplist, SLTDateType x); // 单链表的尾删void SListPopBack(SListNode** pplist); // 单链表头删void SListPopFront(SListNode** pplist); // 单链表查找SListNode* SListFind(SListNode* plist, SLTDateType x); // 单链表在pos位置之后插入x// 分析思考为什么不在pos位置之前插入？void SListInsertAfter(SListNode* pos, SLTDateType x); // 单链表删除pos位置之后的值// 分析思考为什么不删除pos位置？void SListEraseAfter(SListNode* pos); // 单链表的销毁void SListDestory(SListNode* plist);

动态申请一个节点

文章图片

// 动态申请一个节点SListNode* BuySListNode(SLTDateType x){ SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL)//申请失败 {printf("malloc fail\n"); exit(-1); } else {newnode->data = https://www.it610.com/article/x; newnode->next = NULL; } return newnode; }

单链表打印
链表单个结点中，data存储数据，next存储下一个结点的地址，可以通过next访问下一个结点

文章图片

// 单链表打印void SListPrint(SListNode* plist){ SListNode* cur = plist; while (cur != NULL) {printf("%d->", cur->data); cur = cur->next; //访问下一个结点 } printf("NULL\n"); }

单链表尾插

文章图片

这里传入了头结点的地址的指针，是因为有可能要改变头结点的情况，传址调用幻术，如果只传入*plist，相当于只改变形参，实参不会有实际改变，通过pplist可以解决这个问题

文章图片

// 单链表尾插void SListPushBack(SListNode** pplist, SLTDateType x){ SListNode* newnode = BuySListNode(x); if (*pplist == NULL)//空链表 {*pplist = newnode; } else {SListNode* tail = *pplist; //遍历至最后插入while (tail->next != NULL){tail = tail->next; }tail->next = newnode; }}

单链表的尾删
一前一后遍历，找到空后直接free（tail），将prev->next置空即可

文章图片

// 单链表的尾删void SListPopBack(SListNode** pplist){ assert(pplist); if (*pplist == NULL)//空链表，无需删除 {return; } else {SListNode* prev = NULL; SListNode* tail = *pplist; {while (tail->next != NULL){prev = tail; tail = tail->next; }free(tail); tail = NULL; prev->next = NULL; } }}

单链表的头插

文章图片

有点绕，要多想想

// 单链表的头插void SListPushFront(SListNode** pplist, SLTDateType x){ assert(pplist); SListNode* newnode = BuySListNode(x); newnode->next = *pplist; *pplist = newnode; }

单链表头删

文章图片

比较简单

// 单链表头删void SListPopFront(SListNode** pplist){ assert(pplist); if (*pplist == NULL)//链表为空 {return; } else {SListNode* next = (*pplist)->next; free(*pplist); *pplist = next; }}

// 单链表查找遍历即可SListNode* SListFind(SListNode* plist, SLTDateType x){ SListNode* cur = plist; while (cur != NULL) {if (cur->data = https://www.it610.com/article/x){return cur; }cur = cur->next; } retuen NULL; }

*单链表在pos位置之后插入x
为什么不在pos之前插入，由于我们是单向链表，需要从头遍历查找pos，如果在pos之前插入，找到pos还需找到pos之前的地址，对所传参数不友好，所以我们一般在后插入

文章图片

//单链表在pos位置之后插入xvoid SListInsertAfter(SListNode* pos, SLTDateType x){ assert(pos); SListNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode; }

单链表删除pos位置之后的值为什么不删除pos位置，同上，在逻辑上和传参不友好.

文章图片

// 单链表删除pos位置之后的值void SListEraseAfter(SListNode* pos){ assert(pos); SListNode* next = pos->next; if (next) {pos->next = next->next; free(next); next = NULL; }}

单链表的销毁链表不像顺序表连续删头就可以，由于链表是一个一个分散的结点，需要逐一删除

文章图片

// 单链表的销毁void SListDestory(SListNode** pplist){ assert(*pplist); SListNode* cur = *pplist; while (cur) {SListNode* next = cur->next; free(cur); cur = next; } *pplist = NULL; }

总结链表相比但链表难度提升不少，对c的掌握也变大，不清晰的地方要多想多画图。还请斧正
【C++|C++ 数据结构超详细讲解单链表】到此这篇关于C++ 数据结构超详细讲解单链表的文章就介绍到这了,更多相关C++ 单链表内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！