数据结构之 “单链表“

2024-08-29 05:52
文章标签 数据结构 单链

本文主要是介绍数据结构之 “单链表“，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

（1）在顺表表中，如果是头插/删的时间复杂度是O(1)；尾插/删的时间复杂度是O(N)
（2）增容一般是呈2倍的增长，势必会有一定的空间浪费。比如：申请了50个空间，只用了两个？(链表可以解决空间浪费的问题)

这一章节的内容是关于单链表。

文章目录

  • 1. 链表
  • 2. 单链表
    • 1. 单链表的概念
    • 2. 单链表的实现
      • 2.1 尾插
      • 2.2 头插
      • 2.3 尾删
      • 2.4 头删
      • 2.5 查找
      • 2.3 特定位置（之前/之后）插入
      • 2.6删除特定位置pos处的结点
      • 2.7 删除pos之后的结点
      • 2.8 销毁链表

1. 链表

链表也是线性表的一种。我们仍然从物理结构和线性结构来分析
(1)物理结构(真实)：不是线性
(2)线性结构(想象)：线性

重点：链表是由一个一个的结点连接起来的。每次创建一个结点，不存在浪费的情况。
一个结点里面存储的是：数据+下一个结点的地址。

链表里的结点，它们的地址不是连续的，而是靠(存储的地址)连接起来的。
在这里插入图片描述

在这里插入图片描述

(3)在链表中，没有增容的概念。如果要增加数据，直接再申请一个结点大小的空间即可。

2. 单链表

1. 单链表的概念

单链表的全称是”不带头,单向,不循环链表“。

  1. 单链表的定义：在.h里

在这里插入图片描述
（1）创建链表—>在test.c里

这个方法只是示范一下，平常创建链表并不会像这么麻烦。
在初始情况下，链表是空链表，只有一个结点，指向NULL，之后尾插即可达到申请结点的结果。

//这个是写在test.c的内容#include"SLTNode.h"
//创建链表
void creatListNode()
{//使用malloc记得写头文件stdlibSLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));node2->data = 2;SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));node3->data = 3;node1->next = node2;node2->next = node3;node3->next = NULL;
}int main()
{creatListNode();return 0;
}

在这里插入图片描述
（2）打印链表出来看看
在这里插入图片描述

2. 单链表的实现

2.1 尾插

不管是头插还是尾插，都需要再申请一个结点大小的空间，所以可以将它封装为一个函数，之后调用即可。

尾插比较简单，有两种可能。

1.链表不为空。最后一个结点的next指向NULL，我们只需将 (最后一个结点的next) 指向 (想插入的结点的地址newnode) 即可。

2.链表为空，就不用找结点了。在刚开始时，我们创建了链表struct SLTNode，这是空链表，只有一个头结点(phead)指向NULL，我们将phead->next指向newnode即可

注意在尾插时传过去的是地址，这样形参的改变可以改掉实参。

//SLTNode.h里的内容#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义链表的结点
typedef int SLTDataType;
typedef struct SLTNode
{SLTDataType data;struct SLTNode* next;
}SLTNode;//申请新结点
SLTNode* SLTBuyNode(SLTDataType x);//尾插
void SLTPushBack(SLTNode** pphead,SLTDataType x);//打印链表
void SLTPrint(SLTNode* phead);
//SLTNode.c里面的内容#include"SLTNode.h"
//用于打印链表的函数的定义
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d(地址:%p) -> ",pcur->data, pcur->next);pcur = pcur->next;}printf("NULL");
}//用于申请新结点的函数的定义
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));//判断一下是否申请成功if (node == NULL){perror("malloc");return 1;}node->next = NULL;node->data = x;return node;
}//尾插函数的定义         pphead是第一个结点指针的地址（地址的地址）
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{//先申请新结点SLTNode* newnode = SLTBuyNode(x);//链表为空if (*pphead == NULL)        //*pphead是第一个结点的指针{*pphead = newnode;}else  //链表不为空{//接下来将尾结点->next指向newnode//找尾结点不能用phead直接遍历找到尾结点，因为这样的话就找不到第一个结点了(单链表只能往后)我们需要重新申请一个来存放第一个结点的地址)SLTNode* pcur = *pphead;while (pcur->next)         //不为NULL时可进入循环{pcur = pcur->next;     //将指针pcur里存放成下一个结点的地址}//出循环表示pcur是尾结点地址，将它的next修改pcur->next = newnode;}}  

//test.c的内容#include"SLTNode.h"
void SLTtest01()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPrint(plist);SLTPushBack(&plist, 2);SLTPrint(plist);SLTPushBack(&plist, 3);SLTPrint(plist);
}int main()
{SLTtest01();return 0;
}

2.2 头插

1.头插仍然是将pphead（地址）传过去
2.头插是将申请的结点的next指向第一个结点的地址。即 newnode->next =* pphead
3.记得最后将*pphead移到新结点处

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);   //已经头插了，那传过来的参数指定不能为空SLTNode* newnode=SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;}

2.3 尾删

尾删：链表不可以为空。

在尾删时，不能直接将最后一个结点释放再置为空，因为我们还需要找到倒数第二个结点，将它的next改为NULL。

还有可能遇见只有一个结点的情况，我们直接把它释放置为空即可。

方法：
（1）创建一个ptail，遍历，使之成为倒数第二个结点，即ptail->next->next=NULL;,将ptail->next指向空。再将ptail往后走成为最后一个结点，将其释放。

void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);  //传过来的参数不能为空，链表不能为空if((*pphead)->next==NULL){free(*pphead);*pphead=NULL;}else{SLTNode* ptail = *pphead;while (ptail->next->next){ptail = ptail->next;}  ptail->next = NULL;ptail = ptail->next;free(ptail);ptail = NULL;} 
}

（2）将prev一直是ptail的前一个

void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);  //传过来的参数不能为空，链表不能为空if((*pphead)->next==NULL){free(*pphead);*pphead=NULL;}else{SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;            //第一次时，prev=*ppheadptail = ptail->next;     //第一次循环时，ptail=第二个结点的指针}                            //当ptail->next=NULL时，ptail最后一个，prev是倒数第二个prev->next = NULL;free(ptail);ptail = NULL;}
}

2.4 头删

头删同样需要断言。

要是删除第一个结点，那么第二个结点等一下就找不到了，我们应该先将第二个结点存起来。再将*pphead释放，再将 * pphead指向第二个结点

void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* tmp = (*pphead)->next;free(*pphead);*pphead = tmp;
}

2.5 查找

不用传地址过去，并不希望在查找时不小心将内容修改

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}

在这里插入图片描述

2.3 特定位置（之前/之后）插入

  1. 在特定位置之前插入，那插入这个数据会影响谁呢？（需要第一个结点）

在这里插入图片描述
由图可知：prev->next 将会被影响。

但是如何可以找到prev呢?单链表只能从前往后找，并不能从pos往前找。

我们可以采用循环，直到 xxxx->next == pos为止。当满足这个条件时，xxxx就是prev。

注意：在插入时，链表phead可以为空，但参数pphead不能为空。pos也不能为空

prev->next = newnode;
newnode->next = pos;

//SLTNode.h里的内容
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)；

//SLTNode.c里的内容
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//如果pos是第一个结点，那么这就变成头插了if (pos == *pphead){SLTPushFront(*pphead, x);}else{SLTNode* newnode = SLTBuyNode(x);  //新结点SLTNode* prev = *pphead;           //先让prev是第一个结点的指针while (prev->next!=pos)            //循环让prev=pos前一个结点指针{prev = prev->next;}prev->next = newnode;             //让prev的下一个是新结点newnode->next = pos;}
}

//test.c里的内容//通过x找到pos
SLTNode* find = SLTFind(plist, 2);
SLTInsert(&plist, find, 9);
  1. 在特定位置之后插入（不需要第一个结点）
    在这里插入图片描述

在“特定位置之后插入”的函数的参数中，并没有第一个结点的地址，为什么呢？

我们已经知道了pos这个地址，可以直接找到它的下一个结点的地址，并不需要通过头结点一个一个往后找。

void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead&&pos);//如果是空链表if (*pphead == NULL){SLTPushBack(*pphead, x);}//不是空链表else{SLTNode* newnode = SLTBuyNode(x);  //新结点SLTNode* Next = pos->next;  //pos的下一个结点pos->next = newnode;newnode->next = Next;}
}

2.6删除特定位置pos处的结点

需要修改pos前一个结点 (prev) 的next
在这里插入图片描述

//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);//头删if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}
}

2.7 删除pos之后的结点

//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);//pos pos->next pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}

2.8 销毁链表

//销毁链表
void SListDestroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

这篇关于数据结构之 “单链表“的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1117022。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
Go语言构建单链表

Go语言构建单链表

package mainimport "fmt"type ListNode struct {Val intNext *ListNode}func main() {list := []int{2,4,3}head := &ListNode{Val:list[0]}tail := head //需要头尾两个指针for i:=1;i<len(list);i++ {//方法一 数组直接构建链表tai
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...
【数据结构入门】排序算法之交换排序与归并排序

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客，我们学习了排序算法中的插入排序和选择排序，接下来我们将继续探索交换排序与归并排序，这两个排序都是重头戏，让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换，让较大的元素逐渐向右移动，从而将最大的元素移动到最右边。 动画演示： 1.1.2 具体步
阅读更多...
数据结构：线性表的顺序存储

数据结构：线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2