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

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

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

 

链表的定义

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

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

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

链表的节点(结点)

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

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

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日
    浏览(50)
  • 数据结构三:线性表之单链表(带头结点单向)的设计与实现

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

    2024年02月19日
    浏览(62)
  • 数据结构--线性表(顺序表、单链表、双链表、循环链表、静态链表)

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

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

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

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

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

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

    我们需要在程序中存储一系列的数据,这些数据不是一成不变的,需要满足随时的动态增删查改。 顺序表,虽然能满足这些要求,可是顺序表在头插或者中间插入数据时,需要将数据一个一个挪动,效率较低;而且需要频繁的扩容,扩容也是需要付出一定的代价。 为有效解

    2023年04月17日
    浏览(54)
  • 数据结构之单链表

    目录 1.什么是链表。 2.链表的优点 3.单链表的实现 1.单链表的结构体 2.节点的创建 3.参数的调用 4.头插  5.尾插 7.头删 8.尾删 8.在pos节点前插入x 9.在pos节点前插入x 10.删除pos位置节点  对于顺序表我们发现,在此基础上仍存在了些许不足: 1.中间或头部的插入时间复杂度为O

    2024年02月05日
    浏览(41)
  • 数据结构·单链表

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

    2024年01月25日
    浏览(76)
  • 【数据结构】单链表详解

    当我们学完顺序表的时候,我们发现了好多问题如下: 中间/头部的插入删除,时间复杂度为O(N) 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们 再继续插入了

    2024年02月09日
    浏览(35)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包