网站导航
> 文档中心 > 单链表碎切详解——数据结构剖析

单链表碎切详解——数据结构剖析

网友: 文档中心 2022-03-24 08:06:47

目录

    • 传统艺能😎
    • 过渡区🤣
  • 什么是链表？🤔
    • 链表的优缺点🤔
    • 链表的分类🤔他们分别是，
    • 单链表👏
    • 尾插🤔
    • 动态申请节点🤔
    • 头插🤔
    • 头删🤔
    • 尾删🤔
    • 销毁链表🤔
    • 任意位置插入🤔
    • 任意位置删除🤔
    • 完整代码：

传统艺能😎

小编是双非本科大一菜鸟不赘述，欢迎大佬指点江山（QQ：1319365055）
此前博客点我！点我！请搜索博主 【知晓天空之蓝】
乔乔的gitee代码库（打灰人 ）欢迎访问，点我！

过渡区🤣

回学校了，这些天没写文章一直在总结之前的错题，没接手新知识今天开始重操旧业开始学习数据结构
在这里插入图片描述

什么是链表？🤔

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

书面解释是很抽象的，说人话就是要多少开多少的非连续单元存储结构

本文是详解链表的基本使用方法，可流畅操作链表，功能上实现了顺序表的增删查改，这里特定位置的插入和删除可做头插尾插的特殊实现。

链表的优缺点🤔

一个实质性的问题就是为啥我们要用链表？

其实相对于我们之前的线性顺序表结构，链表的操作更为复杂，但是由于可以不用按顺序存储，链表在头尾插入时可以达到 O（1）的复杂度。

最主要的就是他可以克服像数组链表一样需要预先知道插入数据的大小才行，链表用多少就开多少，这样就可以使得计算机空间得到充分利用；但是同时他又失去了顺序表随机读取的优点，线性表的链式存储如果要找一个数，必须要从头开始找起，十分麻烦。

链表的分类🤔他们分别是，

链表不是简简单单的一个链表，他有8大结构分别是：

  1. 单链表 or 双链表
  2. 带头 or 不带头
  3. 循环 or 不循环

单链表：
在这里插入图片描述
双链表：

在这里插入图片描述
带头结点单链表：
在这里插入图片描述
带头结点双链表：
在这里插入图片描述
循环单链表：
在这里插入图片描述
循环带头结点双链表：
在这里插入图片描述
带头循环双向链表虽然是链表中最复杂的结构，但它的代码操作却是最简单的，也是现实中实际运用最为广泛的一种。

单链表👏

表中每一个数据都包含两个部分，该元素和下一元素的地址，由下一元素的地址就能链接到各个元素从而形成“ 表 ”的结构，在表尾不需要在寻访下一元素时我们只需放入 NULL 即可。

那么首先我们就要定义一个结构体：

#pragma once typedef int Seqtype;typedef struct Seqlist{ Seqtype data; struct Seqlist* Next;//下一节点的地址}Seqlist;

尾插🤔

为了写起来方便，我把打印功能单独拿出来先定义好：

void print(Seqlist** plist){Seqlist* begin = *plist;while (begin!=NULL){printf("%d->", begin->data);begin = begin->Next;}printf("无内容\n");}

链表的特点就是要多少开多少，根据尾插的逻辑分析一下，那么在尾插之前我们需要先 malloc 一块空间出来，把要插的数据初始化好，再在已有链表结构中寻找尾节点进行插入即可。

void pushback( Seqlist** plist, Seqtype x){Seqlist* node = (Seqlist*)malloc(sizeof(Seqlist));node->data = x;node->Next = NULL;Seqlist* tail = *plist;if (tail == NULL){tail = node;}//处理为空的特殊情况else{while (tail->Next != NULL){tail = tail->Next;}//寻找尾结点tail->Next = node;//插入数据}}

但是注意，一上来就去找尾结点的话，因为在 test.c 里面 plist 已经被初始化成 NULL，那为了避免 tail 一上来就没了这种尬尴的情况，我们加入一个判断：

if(*plist == NULL){*plist = node;}else{……//上面的pushback}

动态申请节点🤔

因为考虑到要时常进行 malloc 开辟空间，所以我们单独拎出来写成一个函数方便调用：

Seqlist* newmalloc(Seqtype x){Seqlist* node = (Seqlist*)malloc(sizeof(Seqlist));node->data = x;node->Next = NULL;return node;}

头插🤔

尾插一但明了了，其他的接口就是信手拈来，头插不需要挪数据，直接开辟空间就行。

void pushfront(Seqlist** plist, Seqtype x){    assert(*plist);Seqlist* node = (Seqlist*)malloc(sizeof(Seqlist));node->data = x;node->Next = *plist;*plist = node;}

因为头插会对首元素地址做出修改，plist 会因此更改，因此这里采用传址调用。

头删🤔

头删思路就是把打头的元素 free 掉，再把指向下一个元素地址的指针放入即可：

void popfront(Seqlist** plist){Seqlist* node = (*plist)->Next;;free(*plist);*plist = node;}

尾删🤔

尾删思路同头删一个道理，遍历找到尾结点，将其free掉，但是这里需要一个处理：

我们在 free 掉最后一个元素后，其地址就不能访问，那么前一个节点存放的寻址指针就是一个野指针，所以需要双指针维护一个 NULL 的 Next 参数。其次还需注意当前链表是否为空或者只有一个元素。

void popback(Seqlist** plist){    assert(*plist);if (*plist == NULL){return;}else{Seqlist* pre = NULL;//跟进 tail 防止free后产生野指针Seqlist* tail = *plist;while (tail->Next != NULL){pre = tail;tail = tail->Next;}free(tail);pre->Next = NULL;}}

销毁链表🤔

结束时不要忘了销毁链表

void destroy(Seqlist** plist){assert(*plist);Seqlist* node = *plist;Seqlist* pre = *plist;while (node->Next == NULL){if (pre->Next != NULL){pre = pre->Next;}else{free(node);node = NULL;node = *plist;}}free(pre);pre = NULL;}

任意位置插入🤔

void insert(Seqlist** plist, Seqtype x, Seqtype pos){assert(*plist);if (pos == *plist){pushfront(plist,x);}else{Seqlist* node = newmalloc(x);Seqlist* pre = *plist;while (pre->Next != pos){pre = pre->Next;}pre->Next = node;node->Next = pos;}}

任意位置删除🤔

void erase(Seqlist** plist, Seqlist* pos){assert(*plist);if (*plist == pos){popfront(plist);}else{Seqlist* pre = *plist;while (pre->Next != pos){pre = pre->Next;}pre->Next = pos->Next;free(pos);pos = NULL;}}

完整代码：

test.c：

# define _CRT_SECURE_NO_WARNINGS #include"Slist.h"void test(){Seqlist* plist = NULL;//增删查改自行组合}int main(){test();return 0;}

Slist.h：

#pragma once#include#includetypedef int Seqtype;typedef struct Seqlist{Seqtype data;struct Seqlist* Next;//下一节点的地址}Seqlist;void pushback(Seqlist* plist, Seqtype x);//尾插void pushfront(Seqlist** plist, Seqtype x);//头插void print(Seqlist** plist);//打印链表void destroy(Seqlist** plist);//销毁链表void popfront(Seqlist** plist);//头删void popback(Seqlist** plist);//尾删void insert(Seqlist** plist, Seqtype x, Seqtype pos);//pos位置插入void erase(Seqlist** plist, Seqtype pos);//pos位置删除Seqlist* newmalloc(Seqtype);//开辟新节点

Slist.c：

# define _CRT_SECURE_NO_WARNINGS #include"Slist.h"void print(Seqlist** plist){Seqlist* begin = *plist;while (begin!=NULL){printf("%d->", begin->data);begin = begin->Next;}printf("无内容\n");}void pushback( Seqlist** plist, Seqtype x){Seqlist* node = (Seqlist*)malloc(sizeof(Seqlist));node->data = x;node->Next = NULL;Seqlist* tail = *plist;if (tail == NULL){tail = node;}else{while (tail->Next != NULL){tail = tail->Next;}tail->Next = node;}}void pushfront(Seqlist** plist, Seqtype x){Seqlist* node = (Seqlist*)malloc(sizeof(Seqlist));node->data = x;node->Next = *plist;*plist = node;}void popfront(Seqlist** plist){Seqlist* node = (*plist)->Next;;free(*plist);*plist = node;}void popback(Seqlist** plist){if (*plist == NULL){return;}else{Seqlist* pre = NULL;Seqlist* tail = *plist;while (tail->Next != NULL){pre = tail;tail = tail->Next;}free(tail);pre->Next = NULL;}}Seqlist* newmalloc(Seqtype x){Seqlist* node = (Seqlist*)malloc(sizeof(Seqlist));node->data = x;node->Next = NULL;return node;}void destroy(Seqlist** plist){assert(*plist);Seqlist* node = *plist;Seqlist* pre = *plist;while (node->Next == NULL){if (pre->Next != NULL){pre = pre->Next;}else{free(node);node = NULL;node = *plist;}}free(pre);pre = NULL;}void insert(Seqlist** plist, Seqtype x, Seqlist* pos){assert(*plist);if (pos == *plist){pushfront(plist,x);}else{Seqlist* node = newmalloc(x);Seqlist* pre = *plist;while (pre->Next != pos){pre = pre->Next;}pre->Next = node;node->Next = pos;}}void erase(Seqlist** plist, Seqlist* pos){assert(*plist);if (*plist == pos){popfront(plist);}else{Seqlist* pre = *plist;while (pre->Next != pos){pre = pre->Next;}pre->Next = pos->Next;free(pos);pos = NULL;}}

今天就到这里吧，摸了家人们。

网络标签：

相关问题