当前位置： 首页 > news >正文

数据结构与算法系列之单链表

news 2025/8/5 4:42:57

在这里插入图片描述

💗 💗 博客:小怡同学
💗 💗 个人简介:编程小萌新
💗 💗 如果博客对大家有用的话，请点赞关注再收藏 🌞

这里写目录标题

  • test.h
  • SList.h
  • 注意事项
    • 一级指针与二级指针的使用
    • assert的使用
    • 空链表与顺序表的区别及优缺点
  • 详解各接口函数的功能

test.h

#include "SList.h"
void Test()
{SLTNode* plist = NULL;SLPrint(plist);SLPushBack(&plist, 7);SLPushBack(&plist, 8);SLPushBack(&plist, 9);SLPushBack(&plist, 10);SLPrint(plist);//SLTNode* ret = SListFind(plist, 8);//SLPrint(plist);//SLisTEraseAfter(ret);//SLPrint(plist);//SListInsert(&plist, ret, 3);//SListInsertAfter(ret, 4);//SlistErase(&plist , ret);//SLisTEraseAfter(ret);//SLPrint(plist);
}int main()
{Test();
}

SList.h


```c
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SList* next;
}SLTNode;void SLPrint(SLTNode* phead);//打印
void SLPushBack(SLTNode** pphead, SLTDataType x);//尾插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//头插
void SLTPopBack(SLTNode** pphead);//尾删
void SLTPopFront(SLTNode** pphead);//头删
SLTNode* BuySLTode(SLTDataType x);//开辟一个节点
SLTNode* SListFind(SLTNode* phead, SLTDataType x);//找到x这个节点
void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x);//在pos之前增加data为x这个节点
void SListInsertAfter(SLTNode* pos, SLTDataType x);//在pos之后增加data为x这个节点
void SlistErase(SLTNode** pphead, SLTNode* pos);//删除在pos之前，删除这个节点
void SLisTEraseAfter(SLTNode* pos);//删除pos之后的节点


#  SList.c```c
#include "SList.h"
SLTNode* BuySLTode(SLTDataType x)
{SLTNode* newnode =  (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;return newnode;
}void SLPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->",cur->data);cur = cur->next;}printf("NULL\n");
}void SLPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode*  newnode = BuySLTode(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)
{assert(pphead);SLTNode* newnode = BuySLTode(x);if (*pphead == NULL){*pphead = newnode;}else{newnode->next = *pphead;*pphead = newnode;}
}void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);if ( (*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;SLTNode* prev = NULL;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}
}void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* cur = *pphead;*pphead = (*pphead)->next;free(cur);cur = NULL;}SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur =  phead;while (cur){if (cur->data == x)return  cur;cur = cur->next;}return NULL;
}void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (*pphead == pos){SLTPushFront(pphead, x);}else{SLTNode* cur = pphead;while (cur->next != pos){cur = cur->next;}SLTNode* newnode = BuySLTode(x);cur->next  = newnode;newnode->next = pos;}}void SListInsertAfter(SLTNode* pos, SLTDataType x) 
{assert(pos);SLTNode* newnode = BuySLTode(x);newnode->next = pos->next;pos->next = newnode;
}void SlistErase(SLTNode**pphead, SLTNode* pos)
{assert(pphead);assert(pos);//assert(*pphead);if (*pphead == pos){SLTPopFront(pphead);}else{SLTNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}cur->next= pos->next;free(pos);}}void SLisTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* cur = pos->next;pos->next = pos->next->next;free(cur);cur = NULL;
}

注意事项

一级指针与二级指针的使用

可以看得出来，接口函数传参时有的需要而二级指针，有的需要一级指针
总结为一句话，改变结构体地址需要二级指针，改变结构体（SLTNode）成员需要一级指针。
解析如下

1.根据c语言，实参传址调用与传值调用知识我们可以知道，改变元素大小需要传入地址。而改变地址，则需要传入地址的地址。因为形参只是实参的拷贝 函数销毁之后形参将不存在

在这里插入图片描述

2.改变结构体的地址，具体是如何改变呢
通过头指针的地址（pphead这个是二级指针），再解引用得到头指针（headnoe），就可以使用且改变了。

在这里插入图片描述

3.通过结构体（headnode），headnode->next可以得到下一个结构体node1

assert的使用

从SList.c可以看出 有时assert(pphead（二级指针）)，有时assert（*pphead（一级指针）），
1.当有二级指针传入时，必须使用assert(pphead)断言因为 pphead是头指针的地址 ，虽然头指针 为NULL但是，头指针的地址是真实存在的（也就是地址中的地址）。
2.assert（*pphead）是当链表中已经没有节点存在了，不能进行删除结点的行为。
在这里插入图片描述

空链表与顺序表的区别及优缺点

区别

1.顺序表为空时 因为结构体不为NULL，只是 size ==0 链表 phead 为空时，没有节点则头指针为NULL。
2，为什么链表不能和顺序表一样直接size++就可以存入数据呢
因为链表每个节点的地址位置都是malloc函数开辟，每个起点位置可能都不一样。而顺序表相当是开辟一段连续内存空间。

优缺点

一.顺序表存储
优点：顺序表存储是将数据元素放到一块连续的内存存储空间，通过下标 访问高效，直接存储与删除
缺点：1.插入和删除比较慢，需要移动大量元素，
2.开辟空间是不可减少的，不可以动态增加长度，容易造成内存浪费
二 .链表存储
原理：没有空间限制，不会溢出，节省空间内存
优点：插入和删除速度快，只需要改变指针指向即可
缺点：不可通过下标访问，需要遍历节点

详解各接口函数的功能

void SLPrint(SLTNode* phead)

void SLPrint(SLTNode* phead)
{
//不改变结构体地址，只是循环打印数据所以传一级指针SLTNode* cur = phead;while (cur != NULL){printf("%d->",cur->data);cur = cur->next;}printf("NULL\n");
}

void SLPushBack(SLTNode** pphead, SLTDataType x)

	assert(pphead);//因为二级指针，肯定存在，所以需要断言SLTNode*  newnode = BuySLTode(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)

	assert(pphead);//因为头插改变了头节点，所以传二级指针SLTNode* newnode = BuySLTode(x);//当没有节点时，增加节点if (*pphead == NULL){*pphead = newnode;}else{newnode->next = *pphead;//增加首节点*pphead = newnode;}

void SLTPopBack(SLTNode** pphead)

	assert(pphead);//二级指针必须断言assert(*pphead);//因为当头节点为空时，不能删除//当只有一个节点时，释放头节点的空间if ( (*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//当有两个或两个以上的节点时else{SLTNode* tail = *pphead;SLTNode* prev = NULL;while (tail->next != NULL)//找到最后一个元素，以及倒数第二个，所以定义了两个指针，因为只找到最后一个并释放后需要把倒数第二个节点（的next）设为NULL{prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}

void SLTPopFront(SLTNode** pphead)

	assert(pphead);//二级指针必定不为空assert(*pphead);//因为链表必须有节点才可以删除，所以需要断言SLTNode* cur = *pphead;*pphead = (*pphead)->next;free(cur);cur = NULL;

SLTNode* BuySLTode(SLTDataType x)

	SLTNode* newnode =  (SLTNode*)malloc(sizeof(SLTNode));//开辟一个新节点if (newnode == NULL){perror("malloc fail");return NULL;}//初始化newnode->data = x;newnode->next = NULL;return newnode;

SLTNode* SListFind(SLTNode* phead, SLTDataType x)

SLTNode* cur =  phead;while (cur){if (cur->data == x)return  cur;//找到返回此节点坐标cur = cur->next;}return NULL;//找不到返回NULL

void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)

	assert(pphead);//二级指针必不为空assert(pos);//判断pos是否为有效地址//判断头节点是否可以插入if (*pphead == pos){SLTPushFront(pphead, x);}else{SLTNode* cur = pphead;while (cur->next != pos)//找到pos之前的位置{cur = cur->next;}SLTNode* newnode = BuySLTode(x);cur->next  = newnode;//链接新的节点newnode->next = pos;}

void SListInsertAfter(SLTNode* pos, SLTDataType x)

	assert(pos);//判断pos位置SLTNode* newnode = BuySLTode(x);//链接新的节点newnode->next = pos->next;pos->next = newnode;

void SlistErase(SLTNode** pphead, SLTNode* pos)

	assert(pphead);//二级指针必不为空assert(pos);//pos位置是否合理assert(*pphead);/删除一个节点，所以链表必不为空//改变了头指针，地址改变需要二级指针if (*pphead == pos){SLTPopFront(pphead);}else{SLTNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}cur->next= pos->next;free(pos);}

void SLisTEraseAfter(SLTNode* pos)

    assert(pos);//判断pos位置是否合理assert(pos->next);//因为要删除pos的下一个位置的节点，所以只有一个节点不能删除SLTNode* cur = pos->next;pos->next = pos->next->next;free(cur);cur = NULL;

在这里插入图片描述

http://www.lryc.cn/news/28489.html

相关文章：

  • MySQL基础
  • 面试热点题：环形链表及环形链表寻找环入口结点问题
  • 【算法】DFS与BFS
  • 湖州银行冲刺A股上市：计划募资约24亿元，资产质量水平较高
  • 高性能网络I/O框架-netmap源码分析
  • SpringBoot监听机制-以及使用
  • 若依学习——定时任务代码逻辑 详细梳理（springboot整合Quartz）
  • C++---最长上升子序列模型---拦截导弹（每日一道算法2023.3.4）
  • 【机器学习面试】百面机器学习笔记和问题总结+扩展面试题
  • 【2021.12.28】ctf逆向中的迷宫问题（含exe及wp）
  • WSL2使用Nvidia-Docker实现深度学习环境自由部署
  • SpringBoot入门 - 配置热部署devtools工具
  • CANFDNET-200U-UDP配置与数据收发控制
  • 嵌入式中backtrace的使用
  • CV学习笔记-Faster-RCNN
  • 大型三甲医院云HIS系统源码 强大的电子病历+完整文档
  • 如何使用Spring Cloud搭建高可用的Elasticsearch集群？详解Elasticsearch的安装与配置及Spring Boot集成的实现
  • phpinfo包含临时文件Getshell全过程及源码
  • ubuntu22.04 Desktop 服务器安装
  • Halcon——关于halcon中的一些语法
  • Java 循环语句
  • Python 基础语法
  • Kubernetes:通过 kubectl 插件 ketall 查看所有APi对象资源
  • Zookeeper3.5.7版本——选举机制（非第一次启动）
  • Python | Leetcode刷题日寄Part05
  • SpringCloud学习笔记（一）
  • 【C语言指针练习题】你真的学会指针了吗？
  • java实现UDP及TCP通信
  • 深度学习-第T1周——实现mnist手写数字识别
  • 质量保障（QA）和质量控制（QC）