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

数据结构---单链表

news 2024/12/14 0:54:56

目录

一、概念

二、分类

1. 单向或者双向

2. 带头或者不带头  

3. 循环或者非循环  

三、接口实现

1.定义结构

 2、申请节点

3、尾插 

4、头插

 5、尾删

6、头删

7.查找，也可以充当修改

8、在pos之前插入x 

9、在pos之后插入x 

​编辑 10、删除pos位置

 11、删除pos之后位置

 四、完整代码

一、概念

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

二、分类

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

1. 单向或者双向

2. 带头或者不带头  

3. 循环或者非循环  

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

这里我们只介绍无头单向非循环链表： 

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构。

三、接口实现

1.定义结构

//定义一下结构
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;

这里为了方便我们测试代码的正确性，我们顺手实现一个Print，以方便我们检查。

void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;//cur向后走}printf("NULL\n");
}

 2、申请节点

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;
}

3、尾插 

下面这样写对吗？

//尾插
void SLTPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);SLTNode* tail = phead;while (tail != NULL){tail = tail->next;}tail = newnode;
}

改正：

//尾插
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* phead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);if (phead = NULL){phead = newnode;}else{SLTNode* tail = phead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}}

 

 从结果来看好像并没有插进去啊，这是怎么回事呢？

 我们要改变plist就要传plist的地址过去，所以代码应该这么写：

//正确代码
//尾插
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;}}

4、头插

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;}

 5、尾删

下面这样写对吗？ 

void SLTPopBack(SLTNode** pphead)
{//1、空assert(*pphead);//2、一个节点//3、一个以上节点if ((*pphead)->next = NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;while (tail->next){tail = tail->next;}free(tail);tail = NULL;}
}

正确代码：

//尾删
void SLTPopBack(SLTNode** pphead)
{//1、空assert(*pphead);//2、一个节点//3、一个以上节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//方法一：SLTNode* tailPrev = NULL;SLTNode* tail = *pphead;while (tail->next){tailPrev = tail;tail = tail->next;}free(tail);tailPrev->next = NULL;//方法二：//SLTNode* tail = *pphead;//while (tail->next->next)//{//	tail = tail->next;//}//free(tail->next);//tail->next = NULL;}
}

6、头删

 

//头删
void SLTPopFront(SLTNode** pphead)
{//空assert(*pphead);//非空SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;
}

7.查找，也可以充当修改

//查找,也可以充当修改
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

8、在pos之前插入x 

 

//在pos之前插入x
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;}
}

9、在pos之后插入x 

//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}

注意： 

 10、删除pos位置

//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}

 11、删除pos之后位置

//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//检查pos是不是尾节点assert(pos->next);SLTNode* posNext = pos->next;pos->next = posNext->next;fress(posNext);posNext = NULL;
}

 四、完整代码

//SList.h#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//无头+单向+非循环链表//定义一下结构
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;
//打印
void SLTPrint(SLTNode* phead);//申请节点
SLTNode* BuySListNode(SLTDataType x);//头插
void SLTPushFront(SLTNode** phead, SLTDataType x);//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);//头删
void SLTPopFront(SLTNode** pphead);//尾删
void SLTPopBack(SLTNode** pphead);//查找,也可以充当修改
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){printf("%d->", cur->data);cur = cur->next;//cur向后走}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;
}//尾插
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){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、一个节点//3、一个以上节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tailPrev = NULL;SLTNode* tail = *pphead;while (tail->next){tailPrev = tail;tail = tail->next;}free(tail);tailPrev->next = NULL;//SLTNode* tail = *pphead;//while (tail->next->next)//{//	tail = tail->next;//}//free(tail->next);//tail->next = NULL;}
}//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//空assert(*pphead);//非空SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;
}//查找,也可以充当修改
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);newnode->next = pos->next;pos->next = newnode;
}//删除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的后一个位置
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//检查pos是不是尾节点assert(pos->next);SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);posNext = NULL;
}


http://www.mrgr.cn/news/79429.html

相关文章：

  • JSON语法、序列化/反序列化、(JS、JSON、Java对象间转换)、fastjson库、JS内置对象JSON
  • 设置笔记本同时连接内外网
  • 高级java每日一道面试题-2024年12月12日-Tomcat篇-请解释什么是Tomcat Coyote ?
  • [Collection与数据结构] 位图与布隆过滤器
  • mp4影像和m4a音频无损合成视频方法
  • 单元测试
  • Dockerfile容器镜像构建技术
  • [C++]友元函数和友元类
  • ACM:均分纸牌
  • 人脸识别Adaface之libpytorch部署
  • 红日靶场vulnstark 4靶机的测试报告[细节]（二）
  • golang实现简单的redis服务
  • [C++]构造函数和析构函数
  • 第1章：CSS简介 --[CSS零基础入门]
  • nginx代理rabbitmq和配置 Nginx 代理达梦数据库
  • ubuntu下Qt5自动编译配置QtMqtt环境（10）
  • D91【python 接口自动化学习】- pytest基础用法
  • 残差网络连接，使得输入与输出的尺寸一样
  • 十九(GIT2)、token、黑马就业数据平台(页面访问控制(token)、首页统计数据、登录状态失效)、axios请求及响应拦截器、Git远程仓库
  • 海选女主角
  • Day7 苍穹外卖项目 缓存菜品、SpringCache框架、缓存套餐、添加购物车、查看购物车、清空购物车
  • TTC模型（1D和2D）理论推导及python实现
  • 不同系统查看软件占用端口的方式
  • MySQL-DDL之数据库操作
  • vue异步更新，$nextTick
  • 嵌入式系统与移动设备开发