1. Toy模板网首页
  2. > Toy博客

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

9月前 作者：你小子别偷懒了 分类：Toy博客 阅读(23) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构--＞线性表--＞单链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

 

链表的定义

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

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

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

链表的节点（结点）

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

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

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->2
	SLPopBack(&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->1
	SLPrint(plist);
	SLDestroy(&plist);

	return 0;
}

运行test函数：

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

 数据结构--＞线性表--＞单链表,数据结构文章来源地址https://www.toymoban.com/news/detail-825683.html

到了这里，关于数据结构--＞线性表--＞单链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】线性表之单链表（讲解实现——带动图理解）

    【数据结构】线性表之单链表（讲解实现——带动图理解）

    单链表的优点 1.头部和中间插入或删除数据效率高，无需挪动。 2.按照需求申请释放空间，无需担心空间不够用。 单链表的缺点 1.不可以进行下标随机访问。 2.复杂度是O(n) 3.反向遍历困难 单链表是线性表的一种，单链表是链式存储的线性表，不同于单链表， 链表在内存空间

    2024年02月06日
    浏览(46)

  • 数据结构--线性表（顺序表、单链表、双链表、循环链表、静态链表）

    前言  学习所记录，如果能对你有帮助，那就泰裤辣。 目录 1.线性表概念 定义 基本操作 2.顺序表 定义 顺序表的实现--静态分配 动态分配 顺序表的特点 顺序表的插入和删除 顺序表的查找 按位查找  按值查找 3.单链表 定义 单链表的初始化 不带头节点的单链表 带头节点的单

    2024年02月11日
    浏览(61)
  • 数据结构三：线性表之单链表(带头结点单向)的设计与实现

    数据结构三：线性表之单链表(带头结点单向)的设计与实现

            线性表的链式存储结构正是所谓的单链表，何谓单链表？通过地址将每一个数据元素串起来，进行使用，这可以弥补顺序表在进行任意位置的插入和删除需要进行大量的数据元素移动的缺点，只需要修改指针的指向即可；单链表的种类又可划分为很多种，本篇博客详

    2024年02月19日
    浏览(59)
  • 【玩转408数据结构】线性表——单链表的定义以及增删改查（线性表的链式表示 上）

    【玩转408数据结构】线性表——单链表的定义以及增删改查（线性表的链式表示 上）

            到这里我们已经了解到线性表是具有 相同数据类型 的 有限个数据元素 序列，而线性表的顺序存储也就是顺序表，顺序表的存储形式十分直观，我们在实现时使用数组进行实现，但顺序表在插入或者删除元素时需要移动大量元素，那么怎么样才能在插入删除元素时不

    2024年02月21日
    浏览(52)
  • 【软考中级-软件设计师】day4：数据结构-线性表、单链表、栈和队列、串

    【软考中级-软件设计师】day4：数据结构-线性表、单链表、栈和队列、串

    真题 真题

    2024年01月21日
    浏览(44)
  • 【数据结构】数据结构小试牛刀之单链表

    【数据结构】数据结构小试牛刀之单链表

    不讲虚的啦，直接肝！ 单链表所要实现的功能罗列如下： 初始化工作我们先初始化一个节点类型，类型中包括了数据域和指针域，数据与中保存着该节点要保存的数据，指针域则保存着链表下一个节点的地址： 然后我们在创建一个函数，用于创建一个新的节点，因为后面我

    2023年04月24日
    浏览(59)
  • 数据结构·单链表

    数据结构·单链表

            不可否认的是，前几节我们讲解的顺序表存在一下几点问题：         1. 中间、头部的插入和删除，需要移动一整串数据，时间复杂度O(N)         2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗         3. 增容一般是2倍的增长，这势

    2024年01月25日
    浏览(75)
  • 数据结构--单链表

    数据结构--单链表

    目录 1.单链表的定义： 单链表基本操作的实现： 2.单链表的初始化（构造带头结点的空表） 2.将头结点的指针域置空 3.链表是否为空： 4.单链表的销毁： 5.单链表的清空: 6.求单链表的表长： 7.   取值  取单链表第i个元素： 8按值查找 根据指定数据查找指定数据所在位置序

    2024年02月15日
    浏览(39)
  • 【数据结构】单链表（超全）

    【数据结构】单链表（超全）

    前言：  上一次我们分享了线性表中的一种结构顺序表，它存在着一些其缺点，比如：在中间位置或者头部进行元素插入或者删除的时候时间复杂度是 O ( N ) O(N) O ( N ) 效率比较低，并且顺序表在扩容的时候也存在时间和空间上的消耗，由于我们每次都是按照二倍来扩的，那

    2024年02月11日
    浏览(39)
  • 数据结构——单链表（下）

    数据结构——单链表（下）

    🌇个人主页：_麦麦_ 📚今日名言：年轻时候的我以为坚持是永不动摇，到这个年纪明白了坚持就是犹疑着，退缩着，心猿意马着，一步三停着，还在往前走。——《十二月历》 目录 一、引言  二、单链表剩余功能的实现         1.单链表的查找         2. 单链表指定位

    2024年01月17日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包