线性表之-单向链表(无头)

目录

什么是单向链表

顺序表和链表的区别和联系

顺序表：

链表：

链表表示(单项)和实现

1.1 链表的概念及结构

1.2单链表(无头)的实现

所用文件

将有以下功能：

链表定义

创建新链表元素

尾插

头插

尾删

头删

查找-给一个节点的指针

改

pos位置之前插入

删除pos位置的值

成品展示

SList.h

SList.c

test.c

什么是单向链表

单向链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含两部分：数据和指向下一个节点的指针。每个节点只能访问它后面的节点，而不能访问前面的节点。

单向链表的特点：

  • 每个节点包含数据和指向下一个节点的指针。
  • 最后一个节点的指针指向空值（NULL），表示链表的结束。
  • 可以动态地添加或删除节点，链表的长度可以根据需要进行扩展或缩小。
  • 可以根据指针迅速插入或删除节点，而不需要移动其他节点。

单向链表相对于数组来说，具有一些优点和缺点：

  • 优点：插入和删除元素的时间复杂度为O(1)，不需要像数组一样进行元素的移动；链表长度可以动态调整，没有固定大小的限制。
  • 缺点：要访问特定位置的元素需要从头开始遍历，时间复杂度为O(n)；相比于数组，在使用额外的指针存储下一个节点的信息，会占用更多的内存空间。

由于单向链表的特点，它常常被用于需要频繁插入和删除元素的场景，或者在事先无法确定数据大小和数量的情况下使用。

顺序表和链表的区别和联系

顺序表：

优点：
空间连续、支持随机访问
缺点：

  1. 中间或前面部分的插入删除时间复杂度O(N)
  2. 2.增容的代价比较大。

链表：

缺点：
以节点为单位存储，不支持随机访问
优点：

  1. 任意位置插入删除时间复杂度为O(1)
  2. 没有增容消耗，按需申请节点空间，不用了直接释放。

链表表示(单项)和实现

1.1 链表的概念及结构

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

1.2单链表(无头)的实现

 

  1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
    构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都
    是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带
    来很多优势，实现反而简单了，后面我们代码实现了就知道了。

所用文件

定义三个文件：

  1. 头文件 SList.h
  2. 函数的实现SList.c
  3. 代码的测试test.c

将有以下功能：

//打印链表
void SListPrint(SLTNode* phead);//创建新链表元素（动态申请一个节点）
SLTNode* BuySListNode(SLTDataType x);//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);//尾删
void SListPopBack(SLTNode** pphead);//头删
void SListPopFront(SLTNode** pphead);//查找->可在查找的基础上进行修改SListAlter
SLTNode* SListFind(SLTNode* phead,SLTDataType x);//改
void SListAlter(SLTNode* phead, SLTDataType x,SLTDataType y);//pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos);

链表定义

定义链表基本结构

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

创建新链表元素

创建新元素用于插入原链表

SLTNode* BuySListNode(SLTDataType x)
{//开辟空间SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));assert(newnode);newnode->data = x;newnode->next = NULL;return newnode;
}

尾插

void SListPushBack(SLTNode** pphead, SLTDataType x)
{//开辟空间SLTNode* newnode = BuySListNode(x);if (*pphead == NULL){//防止开始时节点为空*pphead = newnode;}else{//找尾节点SLTNode* tail = *pphead;//找到链表首元素while (tail->next != NULL){//检索到未节点tail = tail->next;}//插入tail->next = newnode;}
}

头插

void SListPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;//地址传给pphead  //*pphead=&plist/*头插无需检查是否为空*/
}

尾删

void SListPopBack(SLTNode** pphead)
{assert(*pphead);if ((*pphead)->next==NULL){//1，只有一个节点free(*pphead);*pphead = NULL;}else{//2，有多个节点//将前一个链元素中存放的地址换为NULL，防止野指针/* 写法一 */SLTNode* tailPrev = NULL;SLTNode* tail = *pphead;while (tail->next!=NULL){tailPrev = tail;//tail的地址tail = tail->next;}free(tail);tailPrev->next = NULL;/* //写法二* //tail寻找的是倒数第二个元素while (tail->next->next!=NULL){tail = tail->next;}free(tail->next);tail->next = NULL;*/}
}

头删

void SListPopFront(SLTNode** pphead)
{ //防止被删空assert(*pphead);//找到首位链表元素SLTNode* next = (*pphead)->next;//存储首元素存放下一个元素的地址free(*pphead);//释放首元素*pphead = next;//将第二位元素改为首元素
}

查找-给一个节点的指针

//无需更改元素，故传一级指针
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data==x)return cur;cur = cur->next;}//未找到指定元素，返回NULLreturn NULL;
}

改

改元素是建立再查找基础之上进行更改

void SListAlter(SLTNode* phead, SLTDataType x, SLTDataType y)
{printf("修改成功:\n");//先找到相应元素，再进行更改SLTNode* ret = SListFind(phead, y);ret->data = x;
}

pos位置之前插入

任意位置之前插入

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//头插if (pos == *pphead)SListPushFront(pphead, x);else{ //任意位置之前插入SLTNode* prev = *pphead;while (prev->next!=pos)//找到pos的位置{prev = prev->next;//prev存放pos的地址}//找到位置SLTNode* newnode = BuySListNode(x);//创建新链表元素，并赋值prev->next = newnode;//给前一个元素赋上下一元素地址newnode->next = pos;//给插入元素存放下一个元素的地址}
}

删除pos位置的值

void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead == pos)SListPopFront(pphead);//头删else{SLTNode* prev = *pphead;while (prev->next != pos)//找到pos的位置{prev = prev->next;//prev存放pos的地址//移到pos前一位，next存放的是pos的地址}//将prev存放的地址改为pos后一个元素的地址prev->next = pos->next;//释放posfree(pos);pos = NULL;}
}

成品展示

SList.h

#pragma once#include <stdlib.h>
#include <stdio.h>
#include <assert.h>typedef int SLTDataType;typedef struct SListNode
{int data;struct SListNode* next;
}SLTNode;//打印链表
void SListPrint(SLTNode* phead);//创建新链表元素（动态申请一个节点）
SLTNode* BuySListNode(SLTDataType x);//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);//尾删
void SListPopBack(SLTNode** pphead);//头删
void SListPopFront(SLTNode** pphead);//查找->可在查找的基础上进行修改SListAlter
SLTNode* SListFind(SLTNode* phead,SLTDataType x);void SListAlter(SLTNode* phead, SLTDataType x,SLTDataType y);//pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos);

SList.c

#include "SList.h"//打印
void SListPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur!=NULL){printf("%d->", cur->data);cur = cur->next;//存放下一个元素的地址}printf("NULL\n");
}//创建新链表元素
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));assert(newnode);newnode->data = x;newnode->next = NULL;return newnode;
}//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);//dataif (*pphead == NULL){//防止开始时节点为空*pphead = newnode;}else{//找尾节点SLTNode* tail = *pphead;while (tail->next != NULL){//存放新节点地址tail = tail->next;}tail->next = newnode;}
}//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;//地址传给pphead  //*pphead=&plist/*头插无需检查是否为空*/
}//尾删
void SListPopBack(SLTNode** pphead)
{assert(*pphead);if ((*pphead)->next==NULL){//1，只有一个节点free(*pphead);*pphead = NULL;}else{//2，有多个节点//将前一个链元素中存放的地址换为NULL，防止野指针/* 写法一 */SLTNode* tailPrev = NULL;SLTNode* tail = *pphead;while (tail->next!=NULL){tailPrev = tail;//tail的地址tail = tail->next;}free(tail);tailPrev->next = NULL;/* //写法二* //tail寻找的是倒数第二个元素while (tail->next->next!=NULL){tail = tail->next;}free(tail->next);tail->next = NULL;*/}
}//头删
void SListPopFront(SLTNode** pphead)
{ //防止被删空assert(*pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//查找-给一个节点的指针
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data==x)return cur;cur = cur->next;}return NULL;
}//改
void SListAlter(SLTNode* phead, SLTDataType x, SLTDataType y)
{assert(phead);printf("修改成功:\n");SLTNode* ret = SListFind(phead, y);ret->data = x;
}
//pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//头插if (pos == *pphead)SListPushFront(pphead, x);else{ SLTNode* prev = *pphead;while (prev->next!=pos)//找到pos的位置{prev = prev->next;//prev存放pos的地址}//找到位置SLTNode* newnode = BuySListNode(x);//创建新链表元素，并赋值prev->next = newnode;//给前一个元素赋上下一元素地址newnode->next = pos;//给插入元素存放下一个元素的地址}
}//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead == pos)SListPopFront(pphead);//头删else{SLTNode* prev = *pphead;while (prev->next != pos)//找到pos的位置{prev = prev->next;//prev存放pos的地址//移到pos前一位，next存放的是pos的地址}//将prev存放的地址改为pos后一个元素的地址prev->next = pos->next;//释放posfree(pos);pos = NULL;}
}

test.c

test.c仅仅是用于测试代码，本文以弄懂单向链表为主，故不进行菜单制作
但改测试中也包含了对部分链表结构即原理进行了讲解，请耐心看完

#include "SList.h"
void TestSList1()
{	SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));assert(n1);SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));assert(n2);SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));assert(n3);SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode));assert(n4);n1->data=1;n2->data=2;n3->data=3;n4->data=4;n1->next = n2;n2->next = n3;n3->next = n4;n4->next = NULL;SListPrint(n1);
}void TestSList2()
{SLTNode* plist = NULL;//传的是plist指针的地址//如果直接传plist，将导致SLTNode* phead中//phead为临时拷贝，不影响实参SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushBack(&plist, 3);SListPushBack(&plist, 4);SListPrint(plist);//不改变无需传二级指针SListPushFront(&plist,0);SListPrint(plist);SListPopFront(&plist);SListPrint(plist);SListPopBack(&plist);/*SListPrint(plist);SListPopBack(&plist);SListPrint(plist);SListPopBack(&plist);SListPrint(plist);SListPopBack(&plist);SListPrint(plist);*//*SListPopBack(&plist);SListPrint(plist);*/
}void TestSList3()
{SLTNode* plist = NULL;//传的是plist指针的地址//如果直接传plist，将导致SLTNode* phead中//phead为临时拷贝，不影响实参SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushBack(&plist, 3);SListPushBack(&plist, 4);SListPrint(plist);//不改变无需传二级指针//查找SLTNode* ret = SListFind(plist, 3);if (ret){//返回值不为空则为找到printf("找到了\n");}SListPrint(plist);修改//SListAlter(plist, 20, 2);//SListPrint(plist);//插入SLTNode* pos = SListFind(plist, 3);//先要找到再进行更改if (pos){SListInsert(&plist, pos, 40);}SListPrint(plist);//删除pos = SListFind(plist, 2);//先要找到再进行删除if (pos){SListErase(&plist, pos);}SListPrint(plist);
}int main()
{TestSList3();return 0;
}

单向链表讲解完毕啦！创作不易，如果喜欢请留下个赞吧，感激不尽😊

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/121225.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

快速学会git版本管理——上传gitee仓库

快速学会git版本管理——上传gitee仓库

首先在gitee右上角有一个新建仓库 创建之后打开自己想要上传的文件 右键打开 Git Bash Here 接下来会弹出git的窗口 首先先初始化仓库 用git命令 git init 然后用git add . 上传所有文件上传到暂存区(上一篇文章说过add是单个文件&#xff0c;add . 是所有文件) 没有显示错误 …
阅读更多...
almaLinux 8 安装 xxdiff 5.1

almaLinux 8 安装 xxdiff 5.1

almaLinux 安装 xxdiff XXdiff——比较和合并工具下载安装安装qt5 XXdiff——比较和合并工具 XXdiff是一款免费、强大的文件和目录比较及合并工具&#xff0c;可以在类似Unix的操作系统上运行&#xff0c;比如Linux、Solaris、HP/UX、IRIX和DEC Tru64。XXdiff的一大局限就是不…
阅读更多...
【枚举区间+线段树】CF Ehu 152 E

【枚举区间+线段树】CF Ehu 152 E

Problem - E - Codeforces 题意&#xff1a; 思路&#xff1a; 感觉是个套路题 对区间计数&#xff0c;按照CF惯用套路&#xff0c;枚举其中一个端点&#xff0c;对另一个端点计数 对于这道题&#xff0c;枚举右端点&#xff0c;对左端点计数 Code&#xff1a; #include &…
阅读更多...
无涯教程-Android Online Test函数

无涯教程-Android Online Test函数

Android在线测试模拟了真正的在线认证考试。您将看到基于 Android概念的多项选择题(MCQ),将为您提供四个options。您将为该问题选择最合适的答案,然后继续进行下一个问题,而不会浪费时间。完成完整的考试后,您将获得在线考试分数。 总问题数-20 最长时间-20分钟 Start Test …
阅读更多...
楼兰图腾——树状数组

楼兰图腾——树状数组

在完成了分配任务之后&#xff0c;西部 314 来到了楼兰古城的西部。 相传很久以前这片土地上(比楼兰古城还早)生活着两个部落&#xff0c;一个部落崇拜尖刀(V)&#xff0c;一个部落崇拜铁锹(∧)&#xff0c;他们分别用 V 和 ∧ 的形状来代表各自部落的图腾。 西部 314 在楼兰古…
阅读更多...
【leetcode 力扣刷题】数学题之除法：哈希表解决商的循环节➕快速乘求解商

【leetcode 力扣刷题】数学题之除法：哈希表解决商的循环节➕快速乘求解商

两道和除法相关的力扣题目 166. 分数到小数29. 两数相除快速乘解法一&#xff1a;快速乘变种解法二&#xff1a; 二分查找 快速乘 166. 分数到小数 题目链接&#xff1a;166. 分数到小数 题目内容&#xff1a; 题目是要我们把一个分数变成一个小数&#xff0c;并以字符串的形…
阅读更多...
uni-app 之 v-on:click点击事件

uni-app 之 v-on:click点击事件

uni-app 之 v-on:click点击事件 image.png <template><!-- vue2的<template>里必须要有一个盒子&#xff0c;不能有两个&#xff0c;这里的盒子就是 view--><view>--- v-on:click点击事件 ---<view v-on:click"onclick">{{title}}<…
阅读更多...
周赛361（模拟、枚举、记忆化搜索、统计子数组数目（前缀和+哈希）、LCA应用题）

周赛361（模拟、枚举、记忆化搜索、统计子数组数目（前缀和+哈希）、LCA应用题）

文章目录 周赛361[2843. 统计对称整数的数目](https://leetcode.cn/problems/count-symmetric-integers/)模拟 [2844. 生成特殊数字的最少操作](https://leetcode.cn/problems/minimum-operations-to-make-a-special-number/)记忆化搜索枚举 [2845. 统计趣味子数组的数目](http…
阅读更多...
港陆证券：五日线破位怎么看？

港陆证券：五日线破位怎么看？

在股票交易中&#xff0c;五日线是个重要的技术指标之一&#xff0c;它能够反映出最近的商场趋势。假如五日线破位&#xff0c;这意味着商场呈现了趋势反转&#xff0c;出资者需求注重趋势改动&#xff0c;并采取相应的出资战略。 首先&#xff0c;咱们来看看五日线破位的原因…
阅读更多...
2022年09月 C/C++（八级）真题解析#中国电子学会#全国青少年软件编程等级考试

2022年09月 C/C++（八级）真题解析#中国电子学会#全国青少年软件编程等级考试

C/C编程&#xff08;1~8级&#xff09;全部真题・点这里 第1题&#xff1a;道路 N个以 1 … N 标号的城市通过单向的道路相连:。每条道路包含两个参数&#xff1a;道路的长度和需要为该路付的通行费&#xff08;以金币的数目来表示&#xff09; Bob and Alice 过去住在城市 1.…
阅读更多...
每日一题——旋转图像

每日一题——旋转图像

旋转图像 题目链接 方法一&#xff1a;利用辅助数组 通过对示例的观察和分析&#xff0c;我们可以得到这样的结论&#xff1a; 对于原数组的下标为i行元素&#xff0c;顺时针旋转九十度后&#xff0c;都变成了下标为&#xff08;n-1-i&#xff09;列元素。如图所示&#xff…
阅读更多...
es倒排索引深入解读

es倒排索引深入解读

文章目录 一. Lucene二.倒排索引算法2.1 Posting List压缩算法2.1.1 FOR2.1.2 RoaringBitmap压缩 2.3 FST压缩算法2.3.1 trie前缀树原理2.3.2 FST构建过程NFADFAFSMFSAFST:有限状态转换机构建原理FST在lucene中实现原理 1.什么是搜索引擎? 全文搜索引擎: 自然语言处理(NLP)、爬…
阅读更多...
关于git约定式提交IDEA

关于git约定式提交IDEA

背景 因为git提交的消息不规范导致被乱喷&#xff0c;所以领导统一规定了约定式提交 官话 约定式提交官网地址 约定式提交规范是一种基于提交信息的轻量级约定。 它提供了一组简单规则来创建清晰的提交历史&#xff1b; 这更有利于编写自动化工具。 通过在提交信息中描述功能…
阅读更多...
docker使用（一）生成，启动，更新(容器暂停，删除，再生成)

docker使用（一）生成，启动，更新(容器暂停，删除，再生成)

docker使用&#xff08;一&#xff09; 编写一个 Dockerfile构建镜像构建失败构建成功 运行镜像运行成功 修改代码后再次构建请不要直接进行构建&#xff0c;要将原有的旧容器删除或暂停停止成功删除成功再次构建且构建成功&#xff01; 要创建一个镜像&#xff0c;你可以按照以…
阅读更多...
stable diffusion实践操作-hypernetworks

stable diffusion实践操作-hypernetworks

系列文章目录 本文专门开一节写hypernetworks的内容&#xff0c;在看之前&#xff0c;可以同步关注&#xff1a; stable diffusion实践操作 提示&#xff1a;写完文章后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 系列文章目录前言一、h…
阅读更多...
CSS中如何实现元素的旋转和缩放效果？

CSS中如何实现元素的旋转和缩放效果？

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 元素的旋转和缩放效果⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅&#xff01;这个专栏是为那些对Web开发感兴趣、刚刚踏…
阅读更多...
【Unity3D】UI Toolkit元素

【Unity3D】UI Toolkit元素

1 前言 UI Toolkit简介 中介绍了 UI Builder、样式属性、UQuery、Debugger&#xff0c;UI Toolkit容器 中介绍了 VisualElement、ScrollView、ListView、GroupBox 等容器&#xff0c;UI Toolkit样式选择器 中介绍了简单选择器、复杂选择器、伪类选择器等样式选择器&#xff0c;…
阅读更多...
韩老师java教程

韩老师java教程

基础知识 进制 进制首位表示方式二进制0B十进制无八进制0十六进制0X 进制转换 x进制转十进制 正常&#xff0c;没什么问题 十进制转x进制 将该数不断除以x&#xff0c;直到商为0为止&#xff0c;然后将每一步得到的余数倒过来&#xff0c;就是对应的x进制 二进制转八进…
阅读更多...
酷开科技丨酷开系统，把电影院给你搬回家

酷开科技丨酷开系统，把电影院给你搬回家

在繁忙、混乱的快节奏工作中&#xff0c;人们总是渴望在下班后&#xff0c;逃离工作的桎梏找到一丝慰藉&#xff0c;看电影&#xff0c;则成为了很多人宣泄情感、放松心情的一种方式。但是&#xff0c;电影院的时间和地点总是那么不受控制&#xff0c;要么地点太远、要么场次不…
阅读更多...
OS | 第5章 插叙：进程API

OS | 第5章 插叙：进程API

OS | 第5章 插叙&#xff1a;进程API 文章目录 OS | 第5章 插叙&#xff1a;进程API5.1 fork()系统调用代码过程分析 5.2 wait()系统调用5.3 exec() 系统调用执行过程 为什么这样设计API&#xff1f;shell执行过程shell 重定向pipe()>>>>> 欢迎关注公众号【三戒…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发