数据结构2——单链表

在数据结构1——顺序表（C语言版）中，我们已经了解了顺序表的使用和实现，总结一下顺序表的优点：

①尾插尾删效率足够快；

②下标的随机访问和修改也足够方便。

可除此之外顺序表也确实存在着不足：

①头部和中部的插入删除效率都不高（时间复杂度为O(N)）；

②扩容需要申请新空间，拷贝数据，释放旧空间，有一定的消耗；

③扩容可能存在空间浪费（我们的扩容函数是2倍增长，比如：当前容量是100，我需要再插入3个数据，按照我的2倍扩容机制就会扩容到200，这时就会浪费了97个数据的空间）。

了解了顺序表的不足，下面我们就来学习一下链表，看一看链表能不能解决顺序表的不足。

1.链表

为了避免像顺序表那样插入数据时造成扩容浪费，那我就边插入边扩容行不行呢？只要插入一个新数据我就开一块空间存一个。那么问题来了，如果这么搞，这些数据就不连续了啊，那还怎么像顺序表那样成为一个表结构呢？~~~~~~对！不要忘了指针，我们可以用指针把这写不连续的空间串起来啊！

1.1链表的概念及结构

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

也就是说，链表并不像顺序表那样在物理空间上是连续存储的，链表的每一个单位里存的不仅仅有数据域，还存的有指针域，我们把每一个这样的单位称为节点。

如图：

1.2 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

①单向或者双向

②带头或者不带头

③循环或者非循环

④最常用的两个

1.无头单向非循环链表

结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构。

2.带头双向循环链表

结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。

2.无头单链表的实现

1. 节点

经过上面的分析我们得知，链表的主要结构为节点，所以我们先用结构体定义节点：

//定义节点
typedef int SLTDataType;//typedef节点的数据域

typedef struct SListNode
{
SLTDataType data;//定义节点的数据域
struct SListNode* next;//定义指向下一个节点的指针
}SLTNode;

2.遍历链表

//遍历链表函数实现
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;//定义当前节点
//while (cur != NULL)//等于空就结束
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;//将下一个节点的地址（指针）赋值给当前节点
}

printf("NULL\n");
}

3.动态增加新节点

//增加新节点函数实现
SLTNode* BuySListNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);//malloc为空直接退出
}

newnode->data = x;
newnode->next = NULL;

return newnode;
}

4.查找（修改）

//查找下标pos函数实现
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}

cur = cur->next;
}

return NULL;
}

5.插入

5.1 尾插

//尾插函数实现
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);


SLTNode* newnode = BuySListNode(x);

if (*pphead == NULL)
{
//改变结构体的指针，所以要用到指针的指针
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;//定义尾节点
while (tail->next != NULL)//只有尾节点的next指针为空
{
tail = tail->next;
}
//改变结构体，只需用到结构体的指针即可
tail->next = newnode;
}
}

5.2 头插

//头插函数实现
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySListNode(x);

newnode->next = *pphead;
*pphead = newnode;
}

5.3 在pos之前插入x

//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);

if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}

SLTNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}

5.4 在pos之后插入x

//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);

SLTNode* newnode = BuySListNode(x);
pos->next = newnode;
newnode->next = pos->next;
}

6.删除

6.1 尾删

//尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
//1、空
assert(*pphead);
//2、一个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else//3、一个以上节点   找尾
{
SLTNode* tailPrev = NULL;//将要尾删的前一个节点的指针域置空
SLTNode* tail = *pphead;
while (tail->next)
{
tailPrev = tail;
tail = tail->next;
}
free(tail);
tailPrev->next = NULL;
}
}

6.2 头删

//头删函数实现
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);

//空
assert(*pphead);
//非空
SLTNode* newhead = (*pphead)->next;
free(*pphead);
*pphead = newhead;
}

6.3 删除pos位置

//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);

if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}

prev->next = pos->next;
free(pos);
pos = NULL;
}
}

6.4 删除pos的后一个位置

//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);

//检查pos是否为尾节点
assert(pos->next);

SLTNode* posNext = pos->next;

pos->next = posNext->next;
free(posNext);
posNext = NULL;
}

7.测试（仅测试一个）

int main() 
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
return 0;
}

源代码

SList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//定义节点
typedef int SLTDataType;//typedef节点的数据域

typedef struct SListNode
{
SLTDataType data;//定义节点的数据域
struct SListNode* next;//定义指向下一个节点的指针
}SLTNode;

//遍历链表函数声明
void SLTPrint(SLTNode* phead);

//增加新节点函数声明
SLTNode* BuySListNode(SLTDataType x);

//尾插函数声明
void SLTPushBack(SLTNode** phead, SLTDataType x);
//头插函数声明
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//尾删函数声明
void SLTPopBack(SLTNode** pphead);
//头删函数声明
void SLTPopFront(SLTNode** pphead);

//查找下标pos函数声明
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos之后插入x
void SLTInsertAfter( SLTNode* pos, SLTDataType x);

//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);

SList.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "SList.h"

//遍历链表函数实现
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;//定义当前节点
//while (cur != NULL)//等于空就结束
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;//将下一个节点的地址（指针）赋值给当前节点
}

printf("NULL\n");
}

//增加新节点函数实现
SLTNode* BuySListNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);//malloc为空直接退出
}

newnode->data = x;
newnode->next = NULL;

return newnode;
}

//尾插函数实现
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);


SLTNode* newnode = BuySListNode(x);

if (*pphead == NULL)
{
//改变结构体的指针，所以要用到指针的指针
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;//定义尾节点
while (tail->next != NULL)//只有尾节点的next指针为空
{
tail = tail->next;
}
//改变结构体，只需用到结构体的指针即可
tail->next = newnode;
}
}
//头插函数实现
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySListNode(x);

newnode->next = *pphead;
*pphead = newnode;
}

//尾删函数声明
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
//1、空
assert(*pphead);
//2、一个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else//3、一个以上节点   找尾
{
SLTNode* tailPrev = NULL;//将要尾删的前一个节点的指针域置空
SLTNode* tail = *pphead;
while (tail->next)
{
tailPrev = tail;
tail = tail->next;
}
free(tail);
tailPrev->next = NULL;
}
}
//头删函数实现
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);

//空
assert(*pphead);
//非空
SLTNode* newhead = (*pphead)->next;
free(*pphead);
*pphead = newhead;
}

//查找下标pos函数实现
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}

cur = cur->next;
}

return NULL;
}

//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);

if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}

SLTNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}

//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);

SLTNode* newnode = BuySListNode(x);
pos->next = newnode;
newnode->next = pos->next;
}

//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);

if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}

prev->next = pos->next;
free(pos);
pos = NULL;
}
}

//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);

//检查pos是否为尾节点
assert(pos->next);

SLTNode* posNext = pos->next;

pos->next = posNext->next;
free(posNext);
posNext = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "SList.h"

int main() 
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
return 0;
}

原文地址：https://blog.csdn.net/weixin_73629886/article/details/142453461

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：3D 模型GLTF、GLB格式文件介绍使用
下一篇：设计模式六大原则：面向对象设计的核心

systemctl centos7 LTS
systemctl centos7 LTSsudo systemctl daemon-reloadsudo systemctl start nginxsudo systemctl enable ngi
阅读更多2024-09-25
一对一视频通话软件Call-Me
Call-Me：你即时视频通话的首选！
阅读更多2024-09-25
【论文阅读】RISE: 3D Perception Makes Real-World Robot Imitation Simple and Effective
这种算子节省了计算量，并继承了传统卷积的核心优势。稀疏3D编码器采用浅ResNet架构[17]。它由一个初始卷积层、四个残差块和一个最终卷积层组成，每两个分量之间有五个2×稀疏池化层。层数可以自由增加
阅读更多2024-09-25
论文阅读【时间序列】ModerTCN (ICLR2024)
ModerTCN简介，梳理CNN分组设计结构。
阅读更多2024-09-25
Q必达任务脚本
小程序或APP任务的用户。通过定时执行脚本，用户可以自动完成签到、广告任务等操作，并将积分转换为余额，帮助节省手动操作的时间。该脚本适用于那些想要自动完成。该脚本的主要作用是用于。
阅读更多2024-09-25
【openwrt】 libubox组件——ustream
在C/C++中经常会提到流，可能有很多同学对流这个概念不是特别理解，实际上，流只是不同设备间传输的一系列数据的抽象，简单的说，流就是一串数据。如果是这串数据需要对外输出，那么就称这个流为输出流，反之则
阅读更多2024-09-25
基于Python实现一个庆祝国庆节的小程序
这个国庆祝福生成器是一个简单而有趣的项目，可以根据需要进行扩展和修改。
阅读更多2024-09-25
Qt窗口——对话框
Qt对话框：对话框内存泄漏、对话框分类（模态、非模态）、消息对话框QMessageBox、颜色对话框QColorDialog、文件对话框QFileDialog、字体对话框QFontDialog、输入对
阅读更多2024-09-25
Oracle数据库高级技术解析与实战案例
Oracle数据库作为企业级数据库市场的领导者，凭借其强大的数据处理能力、高可用性、可扩展性以及安全性，在各行各业得到了广泛应用。本文将深入探讨Oracle数据库的高级技术特性，并通过实际代码案例展示
阅读更多2024-09-25
Linux常用命令（部分学习待继续补充）
前面三个是当前所有者的权限中间三个同一个group（这里的group就是staff）用户的权限后三个是其他用户的权限。head readme.md 查看文件开头的内容（head --lines=2
阅读更多2024-09-25