【数据结构】单向链表的增删查改以及指定pos位置的插入删除

news/2024/11/26 7:19:24/

目录

 单向链表的概念及结构

 尾插

头插

尾删

​编辑

 头删

 查找

 在pos位置前插

 在pos位置后插

 删除pos位置

 删除pos的后一个位置

总结

代码 

 单向链表的概念及结构

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

 单向链表的结构：

注意:

  1. 从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续。
  2. 现实中的结点一般都是从堆上申请出来的。
  3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。 
  •  无头单向非循环链表:结构简单, 一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

 尾插

尾插分为两种情况：

  1. 一开始没有链表：当开始没有链表，直接将newnode赋给*pphead，通过二级指针改变plist。
  2. 一开始有链表：当开始有链表，创建一个结构体指针tail，来找到最后一个节点，再将newnode赋给最后一个节点的next。

头插

头插分为两种情况，开始有链表和开始没有链表，但是两种情况不需要分类考虑，先将*pphead即plist赋给newnode->next，再将newnode连上*pphead。

尾删

 尾删分两种情况考虑：

  1. 只有一个节点：给*pphead赋空值
  2. 一个以上节点：确定尾节点tail后，通过tail的前一个节点tailprev，进行tailprev->next=NULL赋空值或者直接通过tail->next->next找倒数第二个节点，再给tail->next赋空值。

 头删

 头删不需要分情况，直接将第一个节点的next即第二个节点的地址通过newnode的中转赋给*pphead。

 查找

创建一个结构体指针cur，链表中遍历查找cur->data==x的节点，找到后返回cur，方便后面的修改功能。

 （不需要修改，所以传入函数的是一级指针）

 在pos位置前插

 分两种情况考虑：

  1. 当pos为第一个节点，相当于头插，调用头插函数即可。
  2. 当pos不为第一个节点，通过pos的前一个节点prev，将newnode插入pos前面。 

​​​​​​

 在pos位置后插

在pos位置后插，先将pos->next赋给newnode->next，把newnode和d3连上，再将newnode赋给pos->next,连上d2。

注意：在两个语句不能换位置，不然成环，循环打印

 删除pos位置

 分两种情况：

  1. pos在第一个节点位置，直接调用头删函数即可。
  2. pos不在第一个节点位置，通过pos的前一个节点prev，将pos->next赋给prev->next，达到将pos节点删除的效果。

 

 删除pos的后一个位置

删除pos的后一个位置，需要先检测pos->next是否为空值，为空值就直接返回，若pos->next不为空赋给posNext，再将posNext->next赋给pos->next达到删除posNext节点，后面可以free(posNext)释放posNext节点，再posNext=NULL给它赋空值。

 

无头删除pos位置

 不给头节点的情况下，可以先通过pos->data=posNext->data的方式交换内容，再删除pos的下一节点posNext，将pos替换为posNext，达到和删除pos一样的效果。

但是这种方法的缺点是当pos本身为尾节点时，不能通过下一节点posNext来使用替换法。

 

代码

总结

 在上面众多单向链表的实现中，很多并不实用，当需要大量的头插头删时，使用单向链表会更高效。

代码 

 SList.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//typedef struct SListNode SLTNode;//打印
void SLTPrint(SLTNode* phead);SLTNode* BuySListNode(SLTDataType x);//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);//尾删
void SLTPopBack(SLTNode** pphead);//头插
void SLTPushBack(SLTNode** pphead, SLTDataType);//头删
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在pos位置前插
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在pos位置后插
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);}newnode->data = x;newnode->next = NULL;return newnode;}尾插  phead是plist的形参   //开始就有链表
//void SLTPushBack(SLTNode* phead, SLTDataType x)
//{
//	SLTNode* newnode = BuySListNode(x);
//	SLTNode* tail = phead;
//	while (tail->next != NULL)
//	{
//		tail = tail->next;
//	}
//	tail->next = newnode;
//}//尾插  //包括一开始没有链表
void SLTPushBack(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 SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}//尾删
void SLTPopBack(SLTNode** pphead)
{//1.空assert(*pphead);//2、一个节点//3、一个以上节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//方法1.SLTNode* tailPrev = NULL;SLTNode* tail = *pphead;while (tail->next){tailPrev = tail;tail = tail->next;}free(tail);tailPrev->next = NULL;方法2.//SLTNode* tail = *pphead;//while (tail->next->next)//{//	tail = tail->next;//}//free(tail->next);//tail->next = NULL;}}//头删
void SLTPopFront(SLTNode** pphead)
{//空assert(*pphead);//非空SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;
}//查找是否有x这个数,找到返回指向该数的指针
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}//在pos位置前插
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{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位置后插
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySListNode(x);//下面两句不能交换位置，否则会成环newnode->next = pos->next;pos->next = newnode;
}//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);if (*pphead == pos){SLTPopFront(pphead);}//else if (pos->next == NULL)//{//	SLTPopBack(pphead);//}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}		//free(prev->next);//不要free，不然这个节点后面全没了prev->next = pos->next;		}
}//删除pos后一个位置
void SLTEraseAfter(SLTNode* pos)
{//assert(pos);//检测pos是否是尾节点//assert(pos->next);//暴力检测if (pos->next == NULL)//温和检测{return NULL;}SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);posNext = NULL;}

 Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"void TestSList1()
{int n;printf("请输入链表的长度：");scanf("%d", &n);printf("\n请依次输入每个节点的值：");SLTNode* plist = NULL;for (size_t i = 0; i < n; i++){int val;scanf("%d", &val);SLTNode* newnode = BuySListNode(val);//头插newnode->next = plist;plist = newnode;}SLTPrint(plist);SLTPushBack(&plist, 1000);SLTPrint(plist);}void TestSList2()
{SLTNode* plist = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);//头插SLTPushFront(&plist, 10);SLTPushFront(&plist, 20);SLTPushFront(&plist, 30);SLTPushFront(&plist, 40);SLTPrint(plist);
}void TestSList3()
{SLTNode* plist = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);头插//SLTPushFront(&plist, 10);//SLTPushFront(&plist, 20);//SLTPushFront(&plist, 30);//SLTPushFront(&plist, 40);//SLTPrint(plist);//尾删SLTPopBack(&plist);//SLTPopBack(&plist);//SLTPopBack(&plist);//SLTPopBack(&plist);//SLTPopBack(&plist);SLTPrint(plist);}void TestSList4()
{SLTNode* plist = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);//头插SLTPushFront(&plist, 10);SLTPushFront(&plist, 20);SLTPushFront(&plist, 30);SLTPushFront(&plist, 40);SLTPrint(plist);//头删SLTPopFront(&plist);SLTPrint(plist);
}void TestSList5()
{SLTNode* plist = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);//头插SLTPushFront(&plist, 10);SLTPushFront(&plist, 20);SLTPushFront(&plist, 30);SLTPushFront(&plist, 40);SLTPrint(plist);//查找SLTNode* pos = SLTFind(plist, 40);if (pos){pos->data *= 10;}SLTPrint(plist);
}void TestSList6()
{SLTNode* plist = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);//头插SLTPushFront(&plist, 10);SLTPushFront(&plist, 20);SLTPushFront(&plist, 30);SLTPushFront(&plist, 40);SLTPrint(plist);//在pos位置前插int x;scanf("%d", &x);SLTNode* pos = SLTFind(plist, x);if (pos){SLTInsert(&plist, pos, x * 10);}SLTPrint(plist);
}void TestSList7()
{SLTNode* plist = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);//头插SLTPushFront(&plist, 10);SLTPushFront(&plist, 20);SLTPushFront(&plist, 30);SLTPushFront(&plist, 40);SLTPrint(plist);//在pos位置后插int x;scanf("%d", &x);SLTNode* pos = SLTFind(plist, x);if (pos){SLTInsertAfter(pos, x * 10);}SLTPrint(plist);
}void TestSList8()
{SLTNode* plist = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);//头插SLTPushFront(&plist, 10);SLTPushFront(&plist, 20);SLTPushFront(&plist, 30);SLTPushFront(&plist, 40);SLTPrint(plist);//删除pos位置int x;scanf("%d", &x);SLTNode* pos = SLTFind(plist, x);if (pos){SLTErase(&plist, pos);pos = NULL;}SLTPrint(plist);
}void TestSList9()
{SLTNode* plist = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);//头插SLTPushFront(&plist, 10);SLTPushFront(&plist, 20);SLTPushFront(&plist, 30);SLTPushFront(&plist, 40);SLTPrint(plist);//删除pos后一个位置int x;scanf("%d", &x);SLTNode* pos = SLTFind(plist, x);if (pos){SLTEraseAfter(pos);pos = NULL;}SLTPrint(plist);
}void PrintSList(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}int main()
{//TestSList1();// 头插 尾插//TestSList2();// 尾删//TestSList3();// 头删//TestSList4();// 查找//TestSList5();// pos位置前插//TestSList7();// pos位置后插//TestSList8();// 删除pos位置TestSList9();//删除pos的后一个位置//TestSList10();return 0;
}


http://www.ppmy.cn/news/1192421.html

相关文章

美观且可以很方便自定义的MATLAB绘图颜色

美观且可以很方便自定义的MATLAB绘图颜色

函数介绍 主函数是draw_test&#xff0c;用于测试函数。 draw_h是函数&#xff0c;用于给Matlab提供美观且可以很方便自定义的绘图颜色。 draw_h函数介绍 这是一个带输入输出的函数&#xff0c;输入1/2/3&#xff0c;输出下面三种颜色库的配色&#xff0c;每种库均有五种颜色…
阅读更多...
2023年国赛如何运行脚本文件

2023年国赛如何运行脚本文件

1、设备脚本文件运行&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1xqLvO0k7LIJVLkzcL0KohQ?pwdwgzj 提取码&#xff1a;wgzj 二维码 2、linux虚拟机脚本文件运行 链接&#xff1a;https://pan.baidu.com/s/1vzRt01AT4u77ynel1KWCaw?pwdwgzj 提取码&#xff1…
阅读更多...
计算机毕业设计选题推荐-校园失物招领微信小程序/安卓APP-项目实战

计算机毕业设计选题推荐-校园失物招领微信小程序/安卓APP-项目实战

✨作者主页&#xff1a;IT毕设梦工厂✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…
阅读更多...
利用C++实现RANSAC拟合多条直线并提出符合要求的直线，标准库和手写（不使用任何库、链表方式）两种方法

利用C++实现RANSAC拟合多条直线并提出符合要求的直线，标准库和手写（不使用任何库、链表方式）两种方法

**背景&#xff1a;**2D/3D激光雷达扫描的点云数据&#xff0c;拟合直线做分析&#xff0c;实现总共有三种方法&#xff1a; &#xff08;1&#xff09;PCL点云库实现 &#xff08;2&#xff09;利用标准库手写 &#xff08;3&#xff09;不使用任何库&#xff0c;链表方式实现…
阅读更多...
ChatGLM3-6B详细安装过程记录（Linux）

ChatGLM3-6B详细安装过程记录（Linux）

先附上GitHub官方地址： https://github.com/THUDM/ChatGLM3https://github.com/THUDM/ChatGLM3 一、预览 咱们可以先看看完成之后的界面： 1. 基于 Gradio 的网页版 demo 运行以下命令即可打开界面： python web_demo.py 运行界面如下： 2. 基于 Streamlit 的网页版 de…
阅读更多...
航空领袖《波音公司》被攻击勒索

航空领袖《波音公司》被攻击勒索

全球航空航天业的领袖公司-波音竟然被黑客攻击勒索了&#xff1f;相比很多小伙伴对波音并不熟悉&#xff0c;波音公司是世界上最大的民用和军用飞机制造商之一。其客户分布在全球90多个国家&#xff0c;像国内很多民航都用的是波音。那就有小伙伴担心了那我做飞机不是就很危险了…
阅读更多...
多测师肖sir_高级金牌讲师_性能指标

多测师肖sir_高级金牌讲师_性能指标

性能指标 一、性能测试指标 性能测试是通过测试工具模拟多种正常、峰值及异常负载条件来对系统的各项性能指标进行测试。 目的&#xff1a;验证软件系统是否能够达到用户提出的性能指标&#xff0c;发现系统中存在的性能瓶颈并加以优化。 二、指标分为两大类&#xff1a; 软件…
阅读更多...
UniPro自定义个人专属工作台 大幅提升工作效率

UniPro自定义个人专属工作台 大幅提升工作效率

很多研发团队在开完每日站会后&#xff0c;工程师的工作习惯便是打开研发管理系统&#xff0c;先看看自己的待办事项&#xff0c;或是查看同事的需求、评论&#xff0c;亦或是查看今日份工作的高优先级项等等。 如何方便工程师能够快速查看和了解一天的工作究竟从哪开始呢&…
阅读更多...
最新文章

Copyright @ 2022~2023