数据结构--＞线性表--＞单链表

2024-02-10 13:12
文章标签 数据结构 单链 线性表

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

 

链表的定义

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

与顺序表不同的是，链表里的每节都是独立申请下来的空间，我们称之为“节点、结点”。

节点的组成主要由两个部分：当前节点要保存的数据和保存下一个节点的地址（指针变量）。

链表的节点（结点）

链表中的每个节点都是独立申请的（需要插入数据时才去申请一块节点的空间），我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。

给出每个节点对应的结构体代码：以保存的节点是整形为例：

struct SListNode
{int data; //节点数据struct SListNode* next; //指针变量⽤保存下⼀个节点的地址
};

当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数据，也需要保存下一个节点的地址（当下一个节点为空时保存的地址为空）。

链式结构在逻辑上是连续的，在物理结构上不一定连续

节点一般是从堆上申请的

从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续。

链表的分类 

对于链表的分类来说：一共有8种

最常用的两种链表结构 

虽然链表结构很多，但最常用的只有两种结构
单链表：也叫无头单向非循环链表，结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。这个链表虽然结构复杂，但是使用代码实现以后会发现法结构会带来更多优势。
 

首先我们给出我们要实现的单链表的头文件：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
typedef struct SList
{SLDataType data;struct SList* next;
}SL;
//打印
void SLPrint(SL* phead);
//销毁
void SLDestroy(SL** pphead);
//开辟新链表节点
SL* Buynode(SLDataType x);
//链表头插
void SLPushFront(SL** pphead,SLDataType x);
//链表尾插
void SLPushBack(SL** pphead,SLDataType x);
//链表头删
void SLPopFront(SL** pphead); 
//链表尾删
void SLPopBack(SL** pphead);
//链表对节点的查找
SL* SLFind(SL** pphead,SLDataType x);
//对指定位置之前插入数据
void SLInsert(SL** pphead,SL* pos,SLDataType x);
//在指定位置之后插入数据
void SLInsertafter(SL* pos, SLDataType x);
//删除pos节点
void SLErase(SL** pphead,SL* pos);
//删除pos之后的节点
void SLEraseafter(SL* pos);

对单链表打印


这里直接进行遍历就ok

//打印
void SLPrint(SL* phead)
{SL* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL");
}

销毁单链表 

逐个销毁，销毁某一个节点时，保存他的下一个节点的地址。

//销毁
void SLDestroy(SL** pphead)
{assert(pphead);assert(*pphead);SL* pcur = *pphead;while (pcur){SL* next = (*pphead)->next;free(pcur);pcur = next;}*pphead = NULL;
}

 开辟节点空间

为新的数据开辟空间

//开辟节点空间
SL* Buynode(SLDataType x)
{SL* newnode = (SL*)malloc(sizeof(SL));if (newnode == NULL){perror("malloc fail\n");return;}newnode->data = x;newnode->next = NULL;return newnode;
}

 单链表头插

记得先后顺序，个人感觉容易犯错

//链表头插
void SLPushFront(SL** pphead, SLDataType x)
{assert(pphead);SL* new = Buynode(x);//个人觉得易错new->next = *pphead;*pphead = new;
}

单链表尾插

如果头结点为空，则相当于头插

如果头结点不为空，就正常找尾节点然后插入。

//链表尾插
void SLPushBack(SL** pphead, SLDataType x)
{assert(pphead);SL* new = Buynode(x);if (*pphead == NULL){*pphead = new;return;}SL* pcur = *pphead;while (pcur->next){pcur = pcur->next;}pcur->next = new;
}

 单链表头删

 对于删除来说，需要断言pphead和*pphead，pphead是存放*pphead的地址不能为NULL，

*pphead是为了判断单链表不能为NULL

//链表头删
void SLPopFront(SL** pphead)
{assert(pphead);assert(*pphead);SL* next = (*pphead)->next;free(*pphead);*pphead = next;
}

 单链表尾删

如果只有一个元素，就相当于头删，否则就相当于尾删

//链表尾删
void SLPopBack(SL** pphead)
{assert(pphead);assert(*pphead);if (((*pphead)->next) == NULL){free(*pphead);*pphead = NULL;}SL* prev = NULL;SL* pcur = *pphead;while (pcur->next){prev = pcur;pcur = pcur->next;}free(pcur);pcur = NULL;prev->next = NULL;
}

单链表对节点的查找

遍历查找与目标值相同的，然后返回存储该值的地址

//链表对节点的查找
SL* SLFind(SL** pphead, SLDataType x)
{assert(pphead);SL* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

对指定位置插入数据

1.pos在*pphead，相当于头插

2.pos不在*pphead，就正常插入

//对指定位置之前插入数据
void SLInsert(SL** pphead, SL* pos, SLDataType x)
{assert(pphead);assert(pos);assert(*pphead);SL* new = Buynode(x);if (pos == *pphead){SLPushFront(pphead, x);return;}SL* pcur = *pphead;while (pcur->next!=pos){pcur = pcur->next;}pcur->next = new;new->next = pos;
}

 在指定位置后插入

没什么好说的，直接找到指定位置，然后插入即可

//在指定位置之后插入数据
void SLInsertafter(SL* pos, SLDataType x)
{assert(pos);SL* new = Buynode(x);new->next = pos->next;pos->next = new;
}

 删除pos节点的值

如果pos为*pphead就头删，否则就正常删除pos节点的值

//删除pos节点
void SLErase(SL** pphead, SL* pos)
{assert(pphead);assert(*pphead);assert(pos);if (*pphead == pos){SLPopFront(pphead);return;}SL* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}SL* next = pos->next;pcur->next = next;free(pos);pos=NULL;
}

 删除pos节点之后的值

找到pos节点，当然联系pos和pos->next->next的值

//删除pos之后的节点
void SLEraseafter(SL* pos)
{assert(pos);assert(pos->next);SL* pcur = pos->next;pos->next = pos->next->next;free(pcur);pcur = NULL;
}

 最终代码

SList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
typedef struct SList
{SLDataType data;struct SList* next;
}SL;
//打印
void SLPrint(SL* phead);
//销毁
void SLDestroy(SL** pphead);
//开辟新链表节点
SL* Buynode(SLDataType x);
//链表头插
void SLPushFront(SL** pphead,SLDataType x);
//链表尾插
void SLPushBack(SL** pphead,SLDataType x);
//链表头删
void SLPopFront(SL** pphead); 
//链表尾删
void SLPopBack(SL** pphead);
//链表对节点的查找
SL* SLFind(SL** pphead,SLDataType x);
//对指定位置之前插入数据
void SLInsert(SL** pphead,SL* pos,SLDataType x);
//在指定位置之后插入数据
void SLInsertafter(SL* pos, SLDataType x);
//删除pos节点
void SLErase(SL** pphead,SL* pos);
//删除pos之后的节点
void SLEraseafter(SL* pos);

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
//打印
void SLPrint(SL* phead)
{SL* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL");
}
//销毁
void SLDestroy(SL** pphead)
{assert(pphead);assert(*pphead);SL* pcur = *pphead;while (pcur){SL* next = (*pphead)->next;free(pcur);pcur = next;}*pphead = NULL;
}
//开辟节点空间
SL* Buynode(SLDataType x)
{SL* newnode = (SL*)malloc(sizeof(SL));if (newnode == NULL){perror("malloc fail\n");return;}newnode->data = x;newnode->next = NULL;return newnode;
}
//链表头插
void SLPushFront(SL** pphead, SLDataType x)
{assert(pphead);SL* new = Buynode(x);//个人觉得易错new->next = *pphead;*pphead = new;
}
//链表尾插
void SLPushBack(SL** pphead, SLDataType x)
{assert(pphead);SL* new = Buynode(x);if (*pphead == NULL){*pphead = new;return;}SL* pcur = *pphead;while (pcur->next){pcur = pcur->next;}pcur->next = new;
}
//链表头删
void SLPopFront(SL** pphead)
{assert(pphead);assert(*pphead);SL* next = (*pphead)->next;free(*pphead);*pphead = next;
}
//链表尾删
void SLPopBack(SL** pphead)
{assert(pphead);assert(*pphead);if (((*pphead)->next) == NULL){free(*pphead);*pphead = NULL;}SL* prev = NULL;SL* pcur = *pphead;while (pcur->next){prev = pcur;pcur = pcur->next;}free(pcur);pcur = NULL;prev->next = NULL;
}
//链表对节点的查找
SL* SLFind(SL** pphead, SLDataType x)
{assert(pphead);SL* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
//对指定位置之前插入数据
void SLInsert(SL** pphead, SL* pos, SLDataType x)
{assert(pphead);assert(pos);assert(*pphead);SL* new = Buynode(x);if (pos == *pphead){SLPushFront(pphead, x);return;}SL* pcur = *pphead;while (pcur->next!=pos){pcur = pcur->next;}pcur->next = new;new->next = pos;
}
//在指定位置之后插入数据
void SLInsertafter(SL* pos, SLDataType x)
{assert(pos);SL* new = Buynode(x);new->next = pos->next;pos->next = new;
}
//删除pos节点
void SLErase(SL** pphead, SL* pos)
{assert(pphead);assert(*pphead);assert(pos);if (*pphead == pos){SLPopFront(pphead);return;}SL* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}SL* next = pos->next;pcur->next = next;free(pos);pos=NULL;
}
//删除pos之后的节点
void SLEraseafter(SL* pos)
{assert(pos);assert(pos->next);SL* pcur = pos->next;pos->next = pos->next->next;free(pcur);pcur = NULL;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
int main()
{SL* plist = NULL;SLPushBack(&plist, 1);SLPushBack(&plist, 2);//1->2//SLPrint(plist);SLPushFront(&plist, 3);//3->1->2//SLPrint(plist);SLPushFront(&plist, 4);//SLPrint(plist);//4->3->1->2SLPopBack(&plist);//4->3->1//SLPrint(plist);SLPopFront(&plist);//3->1//SLPrint(plist);SL* new=SLFind(&plist, 3);SLInsert(&plist,new,4);//4->3->1//SLPrint(plist);SLInsertafter(new, 5);//4->3->5->1//SLPrint(plist);SLErase(&plist, new);//4->5->1SLPrint(plist);SLDestroy(&plist);return 0;
}

运行test函数：

以及测试过了，每个接口函数都没啥问题

 

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


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

相关文章

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

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

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 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