单链表的实现

单链表的实现

  • 单链表的链表的概念及结构
    • 概念
    • 结构
      • 链表结构的分类
      • 链表常用的结构
  • 无头单向不循环链表
    • 头文件 SList.h
        • 结构体 struct SListNode
    • 源文件 SList.c
        • 创建结点 SLNode* SLBuyNode(SLDataType x)
        • 初始化链表 void SLInit(SLNode** pphead)
        • 链表尾部插入 void SLPushBack(SLNode** pphead,SLDataType x)
        • 链表头部插入 void SLPushFront(SLNode** pphead, SLDataType x)
        • 打印链表 void SLPrint(SLNode* phead)
        • 链表尾部删除 void SLPopBack(SLNode** pphead)
        • 链表头部删除 void SLPopFront(SLNode** pphead)
        • 销毁单链表 void SLDesTroy(SLNode** pphead)
      • 测试插入数据与删除数据 test.c
        • 查找链表元素 SLNode* SLFind(SLNode** pphead, SLDataType x)
        • 在指定位置之前添加数据 void SLInsert(SLNode** pphead,SLNode* pos ,SLDataType x)
        • 在指定位置之后添加数据 void SLInsertAfter(SLNode** pphead,SLNode* pos ,SLDataType x)
      • 测试指定位置插入数据
        • 删除指定结点 void SLErase(SLNode** pphead, SLNode* pos)
        • 删除指定结点的下一结点 void SLEraseAfter(SLNode* pos)
      • 测试指定位置删除数据
    • 结语

单链表的链表的概念及结构

概念

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

结构

在这里插入图片描述

  • 在链表中,我们将带有需要存储的变量data与该结构体指针变量next的结构体设为一个结点,再将多个结点通过该结构体的成员next进行链接,就如上图所形成的数据结构,其中1为头节点,4为节点。
  • 链表的结构在逻辑上是连续的,但在物理内存上不一定连续
  • 现实中的节点一般都是从堆区申请得来的
  • 从堆区申请的空间,按照一定的策略来分配,两次申请的空间可能连续,也可能不连续

链表结构的分类

下面以32位环境下,结点存储信息位int类型为例来介绍链表的不同结构:

  1. 带头链表与不带头链表
    在这里插入图片描述

这里的带有链表的头结点仅为向导作用,他的next指向真正的头结点,存储的值可以是任意的。

  1. 单向链表与双向链表
    在这里插入图片描述

双向链表与单向链表不同的是他的结构体多了一个指向上一个结点的成员prev,这样的链表在进行特定点插入的时候,就会变得很方便了。

  1. 循环链表与不循环链表
    在这里插入图片描述

循环链表顾名思义,就是将未结点的next指向我们的头节点,从而使链表进行闭环。

以上就是链表的三种基本结构,但是我们可以根据这三种基本结构推出其他的复合状态的结构。

链表常用的结构

在日常生活中,我们常有的链表有下面两种:

  1. 无头单向不循环链表
    在这里插入图片描述
    常用的原因:结构简单,⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构,如哈希桶、图的邻接表等等,另外这种结构在笔试⾯试中出现很多,这种链表就是我们本次要讲的链表。

  2. 带头双向循环链表
    在这里插入图片描述
    常用的原因:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,而实现它反而较为简单。

以上,就是两种常用的链表,下面让我们来看看本篇主要讲的无头单向不循环链表。

无头单向不循环链表

头文件 SList.h

#pragma once#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLDataType;typedef struct SListNode
{SLDataType data;struct SListNode* next;
}SLNode;SLNode* SLBuyNode(SLDataType x);//创建结点 void SLInit(SLNode** pphead);//初始化链表
void SLPrint(SLNode* phead);//打印void SLPushBack(SLNode** pphead,SLDataType x);//尾插
void SLPushFront(SLNode** pphead, SLDataType x);//头插void SLPopBack(SLNode** pphead);//尾删
void SLPopFront(SLNode** pphead);//头删SLNode* SLFind(SLNode** pphead, SLDataType x);//查找void SLInsert(SLNode** pphead,SLNode* pos ,SLDataType x);//在该地址之前添加
void SLInsertAfter( SLNode* pos, SLDataType x);//在该地址之后添加void SLErase(SLNode** pphead, SLNode* pos);//删除该单元
void SLEraseAfter(SLNode* pos);//删除该单元的下一单元void SLDesTroy(SLNode** pphead);//销毁单链表
结构体 struct SListNode
typedef int SLDataType;typedef struct SListNode
{SLDataType data;struct SListNode* next;
}SLNode;

本篇文章使用int来演示链表结构体所存储的数据,所以利用#defineSLDataType重命名。
再定义一种结构体,结构体中放置SLDataType与自身结构体指针struct SListNode*两种成员变量。

源文件 SList.c

创建结点 SLNode* SLBuyNode(SLDataType x)
SLNode* SLBuyNode(SLDataType x)
{SLNode* node = (SLNode*)malloc(sizeof(SLNode));assert(node);node->data = x;node->next = NULL;return node;
}
#include<stdlib.h>
void* malloc (size_t size);//malloc()  分配大小为字节的内存块,返回指向块开头的指针。

利用malloc函数进行空间的申请,申请一个结点的空间,为防止申请失败返回空指针我们这里再用assert函数进行断言。若成功申请到空间,则分别对该结构体内的成员变量进行赋值即可,这里我们暂且不知道next的值,所以将next置空,最后再返回这个结点的指针即可。

初始化链表 void SLInit(SLNode** pphead)
void SLInit(SLNode** pphead)
{*pphead = NULL;
}

初始化链表顾名思义就是将链表置为空NULL ,这也是为了避免使用者在定义结构体指针的时候,没有初始化造成使用野指针的情况。

链表尾部插入 void SLPushBack(SLNode** pphead,SLDataType x)
void SLPushBack(SLNode** pphead,SLDataType x)
{assert(pphead);SLNode* node = SLBuyNode(x);if (!*pphead){*pphead = node;return;}SLNode* pcur = *pphead;while (pcur->next != NULL){pcur = pcur->next;}pcur->next = node;
}

SLPushBack函数接受二级指针也就是链表首结点的地址,这里我们必须要断言一下,检查指针是否正确传参。
再接着我们利用if语句判断链表的首结点是否为空NULL,若为空我们就进行特殊处理,将SLBuyNode函数返回的结点设为首结点;否则就初始化一个新变量pcur指向头结点,利用while循环使pcur走到未结点,然后将未结点的next指向SLBuyNode函数返回的新节点即可。

链表头部插入 void SLPushFront(SLNode** pphead, SLDataType x)
void SLPushFront(SLNode** pphead, SLDataType x)
{assert(pphead);SLNode* node = SLBuyNode(x);if (!*pphead){*pphead = node;return ;}SLNode* pcur = *pphead;node->next = pcur;*pphead = node;
}

这里依旧是先对pphead进行断言,再开始向下执行语句。
利用if语句判断链表头结点是否为空,头结点为空就将 SLBuyNode函数返回的结点赋值给*pphead。
若不为空,就新命名一个指向*pphead的变量pcur,再将node->next指向刚刚新命名头结点pcur,最后将指向头结点的指针指向新的头结点node即可,流程如下图所示:
在这里插入图片描述

打印链表 void SLPrint(SLNode* phead)
void SLPrint(SLNode* phead)
{SLNode* pcur = phead;while (pcur!=NULL){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

这里只是对链表进行范围而非增添新的结点,所以在这里传的是一级指针。
我们先新命名一个指向头结点的指针pcur,再利用while循环遍历链表同时对链表中的元素进行打印即可,因为最后的结点的next指向空NULL或者该链表本身就为空,所以我们在最后打印一个NULL

链表尾部删除 void SLPopBack(SLNode** pphead)
void SLPopBack(SLNode** pphead)
{assert(pphead && *pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return ;}SLNode* pcur = *pphead;while (pcur->next->next!= NULL){pcur = pcur->next;}free(pcur->next);pcur->next = NULL;
}

对链表进行删除,首先我们要判断该链表的地址是否正确和该链表是否为空。
通过断言之后,利用if语句判断该链表是否只有一个结点,若只有一个结点我们就需要进行特殊处理,将唯一的结点释放掉在置为空即可,因为在单链表在删除过程中需要知道要删除结点的前一个结点。若为正常处理,我们就需新命名一个指针变量pcur,再用while循环找到next指向删除结点的上一个结点pcur,利用上一个结点pcurnext指向删除结点的next,这样就可以让删除结点从链表中脱离出来,再用free对其进行释放即可,就如下图所示:
在这里插入图片描述

链表头部删除 void SLPopFront(SLNode** pphead)
void SLPopFront(SLNode** pphead)
{assert(pphead && *pphead);SLNode* del = *pphead;*pphead = (*pphead)->next;free(del);del = NULL;
}

老规矩先断言。
通过断言后,新命名一个指向头结点的指针del,再让头结点等于其自身的next,再然后将del释放掉即可。

销毁单链表 void SLDesTroy(SLNode** pphead)
void SLDesTroy(SLNode** pphead)
{assert(pphead);SLNode* pret = *pphead;while (*pphead){pret = (*pphead)->next;free(*pphead);*pphead = pret;}
}

先断言,再新命名一个指向头结点的指针变量pret让头结点依次随着next走动,在*pphead走向next之后,利用pret释放掉`*pphead的上一个结点,如此循环直到*pphead为空时,循环结束。

测试插入数据与删除数据 test.c

#include"SList.h"
int main()
{SLNode* phead;SLInit(&phead);SLPushBack(&phead, 2);SLPushBack(&phead, 3);SLPrint(phead);//2->3->NULLSLPushFront(&phead, 1);SLPushFront(&phead, 0);SLPrint(phead);//0->1->2->3->NULLSLPopBack(&phead);SLPrint(phead);//0->1->2->NULLSLPopFront(&phead);SLPrint(phead);//1->2->NULLreturn 0 ;
}

测试环节:

  1. 先依次尾插2和3,打印结果理应为2->3->NULL;
  2. 依次头插1和0,打印结果理应为0->1->2->3->NULL;
  3. 对链表进行未删,打印结果理应为0->1->2->NULL;
  4. 对链表进行头删,打印结果理应为1->2->NULL;

以上测试运行结果如下图所示:
在这里插入图片描述

查找链表元素 SLNode* SLFind(SLNode** pphead, SLDataType x)
SLNode* SLFind(SLNode** pphead, SLDataType x)
{assert(pphead && *pphead);SLNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

先断言保证程序可正常运行
新命名一个指向头结点的指针pcur,利用while循环遍历链表,当满足pcur->data == x时返回该结点pcur;如果pcur跳出while循环,说明链表中没有要查找的元素,就返回NULL

在指定位置之前添加数据 void SLInsert(SLNode** pphead,SLNode* pos ,SLDataType x)
void SLInsert(SLNode** pphead,SLNode* pos ,SLDataType x)
{assert(pphead && *pphead);assert(pos);SLNode* node = SLBuyNode(x);if (pos == *pphead){node->next = *pphead;*pphead = node;return;}SLNode* pret = *pphead;while (pret->next != pos){pret = pret->next;}node->next = pos;pret->next = node;
}

先断言保证程序可正常运行。
利用SLBuyNode函数得到一个储存元素为x的结点,再利用if语句判断特例pos == *pphead,若为真就进行头插即可;若不为真,就新命名一个指向头结点的指针pret,依旧是遍历链表找到pret->next == pos的位置,再在pret后面插入数据即可。这里的插入,先将node->next指向pos,再将pret>next指向node即可,如下图所示:
在这里插入图片描述

在指定位置之后添加数据 void SLInsertAfter(SLNode** pphead,SLNode* pos ,SLDataType x)
void SLInsertAfter( SLNode* pos, SLDataType x)
{assert(pos);SLNode* node = SLBuyNode(x);node->next = pos->next;pos->next = node;
}

先断言保证程序可正常运行,再正常向后插入即可。

测试指定位置插入数据

#include"SList.h"int main()
{SLNode* phead;SLInit(&phead);SLPushBack(&phead, 1);SLPushBack(&phead, 2);SLPushBack(&phead, 3);SLPrint(phead);//1->2->3->NULLSLInsert(&phead, SLFind(&phead, 1), 0);SLPrint(phead);//0->1->2->3->NULLSLInsert(&phead, SLFind(&phead, 3), 4);SLPrint(phead);//0->1->2->4->3->NULLSLInsertAfter(&phead, SLFind(&phead, 1), 9);SLPrint(phead);//0->1->9->2->4->3->NULLSLInsertAfter(&phead, SLFind(&phead, 3), 5);SLPrint(phead);//0->1->9->2->4->3->5->NULLreturn 0 ;
}

测试环节:

  1. 先依次尾插1,2和3,打印结果理应为1->2->3->NULL;
  2. 向结点为1的位置之前插入0,打印结果理应为0->1->2->3->NULL;
  3. 向结点为3的位置之前插入4,打印结果理应为0->1->2->4->3->NULL;
  4. 向结点为1的位置之后插入9,打印结果理应为0->1->9->2->4->3->NULL;
  5. 向结点为3的位置之后插入5,打印结果理应为0->1->9->2->4->3->5->NULL;

以上测试运行结果如下图所示:
在这里插入图片描述

删除指定结点 void SLErase(SLNode** pphead, SLNode* pos)
void SLErase(SLNode** pphead, SLNode* pos)
{assert(pphead && *pphead);assert(pos);SLNode* pret = *pphead;if (pret == pos){SLPopFront(pphead);return;}while (pret->next!=pos){pret = pret->next;}pret->next = pos->next;free(pos);pos = NULL;
}

先断言保证程序可正常运行,再判断特例。
若不为特例,就while循环遍历,找到pos上一个结点,再进行删除即可。

删除指定结点的下一结点 void SLEraseAfter(SLNode* pos)
void SLEraseAfter(SLNode** pphead,SLNode* pos)
{assert(pphead && *pphead);assert(pos);if (!pos->next){return;}SLNode* pcur = *pphead;while (pos != pcur){cur = cur->next;}SLNode* del = pcur->next;pcur->next = del->next;free(del);del = NULL;
}

先断言保证程序可正常运行,如果pos->next为空就说明要删除的为空,我们直接返回即可。
pos->next不为空,就新命名一个指向头结点的指针变量pcur,遍历链表当pos==pcur的时候跳出while循环,再命名一个指针指向pcur->next,再将pcur->next 指向del->next,最后释放掉del即可。

测试指定位置删除数据

#include"SList.h"int main()
{SLNode* phead;SLInit(&phead);SLPushBack(&phead, 1);SLPushBack(&phead, 2);SLPushBack(&phead, 3);SLPushBack(&phead, 4);SLPushBack(&phead, 5);SLPushBack(&phead, 6);SLPrint(phead);//1->2->3->4->5->6->NULLSLErase(&phead, SLFind(&phead, 1));SLPrint(phead);//2->3->4->5->6->NULLSLErase(&phead, SLFind(&phead, 6));SLPrint(phead);//2->3->4->5->NULLSLEraseAfter(&phead,SLFind(&phead, 5));SLPrint(phead);//2->3->4->5->NULLSLEraseAfter(&phead,SLFind(&phead, 2));SLPrint(phead);//3->4->5->NULLreturn 0 ;
}

测试环节:

  1. 先依次尾插1,2,3,4,5,6,打印结果理应为1->2->3->4->5->6->NULL;
  2. 指定删除1,打印结果理应为2->3->4->5->6->NULL;
  3. 指定删除6,打印结果理应为2->3->4->5->NULL;
  4. 指定删除5之后的结点,打印结果理应为2->3->4->5->NULL;
  5. 指定删除2之后的结点,打印结果理应为2->4->5->NULL

以上测试运行结果如下图所示:
在这里插入图片描述

结语

本期的内容到这里就结束了,谢谢各位的支持!
下期小编将为大家带来基于本期的单链表所实现的贪吃蛇小游戏。
那么,喜欢请多多关照吧!!!

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

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

相关文章

C语言:计算 1! + 2! + 3! + ... + n!

题目&#xff1a; 从键盘输入一个值n&#xff0c;计算 1的阶乘 至 n的阶乘 的和&#xff0c; 如&#xff1a;输入10&#xff0c;计算 1的阶乘 至 n的阶乘 的和 --> 计算&#xff1a;1! 2! 3! ... 10! 思路一&#xff1a; 效率比较低&#xff0c;会重复计算之前计算过的…

Leetcode-234 回文链表

我的解法&#xff1a;使用栈&#xff0c;定义了len略微复杂&#xff0c;拿链表的后半部分和前半部分比较即可&#xff0c;没必要全部比较 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* List…

如何在在线Excel文档中规范单元格输入

在日常的工作中&#xff0c;我们常常需要处理大量的数据。为了确保数据的准确性和可靠性。我们需要对输入的数据进行规范化和验证。其中一个重要的方面是规范单元格输入。而数据验证作为Excel中一种非常实用的功能&#xff0c;它可以帮助用户规范单元格的输入&#xff0c;从而提…

Java用log4j写日志

日志可以方便追踪和调试问题&#xff0c;以前用log4net写日志&#xff0c;换Java了改用log4j写日志&#xff0c;用法和log4net差不多。 到apache包下载下载log4j的包&#xff0c;解压后把下图两个jar包引入工程 先到网站根下加一个log4j2.xml的配置文件来配置日志的格式和参…

matlab中的iddata函数的初步理解和使用程序举例

matlab中的iddata函数的初步理解和程序举例 一、iddata函数功能 iddata函数常用于系统识别分析领域数据分析方面。该函数在时域或频域中&#xff0c;将用于系统识别的输入输出数据及其特性数据的生成对象数据类型。即&#xff0c;可以使用iddata函数封装要标识的系统的输入和…

Mysql数据库 8.SQL语言 外键约束

一、外键约束 外键约束——将一个列添加外键约束与另一张表的主键&#xff08;唯一列&#xff09;进行关联之后&#xff0c;这个外键约束的列添加的数据必须要在关联的主键字段中存在 案例 创建原则&#xff1a;先创建不含外键的表也就是班级表 添加外键的方式 一般使用第一…

HCIE-CCE

1、创建集群 svc网络&#xff0c;10.247 pod网络&#xff0c;10.244 节点网络&#xff0c;192.168.66&#xff08;master和node一致&#xff09; 2、创建节点 上面集群选择了最新版本1.27&#xff0c;CCE从1.27版本开始不再支持docker容器引擎&#xff0c;仅支持containered&…

git笔记

git常见命令 git init :初始化本地仓库&#xff0c;会生成一个.git文件&#xff0c;该文件用于管理和追踪该本地仓库&#xff0c;只有在git仓库下的文件才能被管理! git config user. name "用户名” git config user. email " 邮箱” git config -1 :列出当前git仓库…

python接口自动化测试 —— unittest框架suite、runner详细使用

test suite 测试套件&#xff0c;理解成测试用例集一系列的测试用例&#xff0c;或测试套件&#xff0c;理解成测试用例的集合和测试套件的集合当运行测试套件时&#xff0c;则运行里面添加的所有测试用例 test runner 测试运行器用于执行和输出结果的组件 test suite、tes…

Flask(Jinja2) 服务端模板注入漏洞(SSTI)

Flask&#xff08;Jinja2&#xff09; 服务端模板注入漏洞(SSTI) 参考 https://www.freebuf.com/articles/web/260504.html 验证漏洞存在 ?name{{7*7}} 回显49说明漏洞存在 vulhub给出的payload: {% for c in [].__class__.__base__.__subclasses__() %} {% if c.__name__…

【uniapp小程序下载】调用uni.uploadfile方法在调试工具里是没有问题的,但是线上版本和体验版就调用不成功,真机调试也没问题

把你的下载地址前缀添加到合法域名就解决了 在调试工具里成功了是因为勾选了下面这项 下面是我的下载并打开函数 methods: {// 下载downloadFileFn(data) {if (this.detailsObj.currentUserBuy) {uni.downloadFile({// data是路径url: https:// data,success(res) {//保存到本…

未来已来,“码”上见证---通义灵码

为了撰写一份关于通义灵码的产品测评&#xff0c;我将构建一个基于提供的产品介绍和评测内容要求的框架给大家介绍这款产品。 功能使用维度 代码智能生成 使用场景&#xff1a;开发中遇到需要编写新功能、单元测试、或对现有代码进行注释时。 使用效果&#xff1a;预期通义灵…

7.5 SpringBoot 拦截器Interceptor实战 统一角色权限校验

前言 在【7.1】管理员图书录入和修改API,当时预告过:并没有写【校验是否是管理员】的逻辑,因为是通用逻辑,会单写一篇来细讲,那么今天就来安排! 角色权限校验,是保证接口安全必备的能力:有权限才可以操作!所以,一般对于这种通用逻辑,推荐不与主业务逻辑耦合,那么…

二叉树的前序、中序、后序、层序遍历

参考内容&#xff1a; 五分钟让你彻底理解二叉树的非递归遍历 Python实现二叉树的非递归遍历 二叉树遍历——深度优先&#xff08;前中后序&#xff09;广度优先&#xff08;层序遍历&#xff09; 构造二叉树 定义二叉树结构如下 struct node {int data;node *left;node *rig…

C++前缀和算法的应用:统计上升四元组

C前缀和算法的应用&#xff1a;统计上升四元组 本文涉及的基础知识点 C算法&#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 题目 给你一个长度为 n 下标从 0 开始的整数数组 nums &#xff0c;它包含 1 到 n 的所有数字&#xff0c;请你返回上…

关于网站安全的一些讨论

互联网的普及和发展为企业和个人提供了巨大的机会&#xff0c;但同时也伴随着网络安全威胁的增加。网站被攻击是一个常见的问题&#xff0c;可能导致数据泄露、服务中断和声誉受损。在本文中&#xff0c;我们将探讨与网络安全紧密相关的因素&#xff0c;分析为什么网站容易受到…

Si4010 一款带有MCU SoC RF发射机芯片 无线遥控器

Si4010是一款完全集成的SoC RF发射机&#xff0c;带有嵌入式CIP-51 8051 MCU&#xff0c;专为1GHz以下ISM频带设计。该芯片针对电池供电的应用进行了优化&#xff0c;工作电压为1.8至3.6 V&#xff0c;待机电流小于10 nA的超低电流消耗。高功率放大器可提供高达10 dBm的输出功率…

Linux Crontab 定时任务

crond 服务 Linux 通过 crond 服务来支持 crontab。 查看 crond 服务是否已经安装 输入下面命令确认 crond 服务是否已安装。 systemctl list-unit-files | grep crond 如果为 enabled&#xff0c;表示服务正运行。 crontab 文件 crontab 要执行的定时任务都被保存在 /etc…

seata1.8安装部署

1.在nacos里面创建命名空间 2.下载seata安装包 3.将下载的seata解压&#xff0c;找到seata/script/server/db目录下对应数据库的sql脚本&#xff0c;创建数据库 undo_log.sql CREATE TABLE undo_log (branch_id bigint(20) NOT NULL COMMENT branch transaction id,xid varcha…

3线SPI驱动 HX8347 TFT屏

老五家2.8寸屏&#xff0c;3线SPI驱动 前言 要知道屏幕的驱动芯片都小的惊人&#xff0c;想必是不会打上丝印的。从几百个引脚中判断哪个是哪个&#xff0c;想想就晕。 大佬们都太厉害了&#xff0c;看看PFC就知道屏幕的接线定义。一直好奇这种神技是怎么练成的。也尝试自己来…