首页 > 其他分享 >数据结构: 单向链表

数据结构: 单向链表

时间:2024-08-02 16:52:44浏览次数:19  
标签:pphead SLTNode 单向 pos next 链表 new 数据结构 节点

目录

一、链表的概念及结构

二、单链表的实现

2.1 头文件

2.2 各个功能的实现

2.2.1 内存申请

 2.2.2 头插,尾插,头删,尾删

头插

 尾插

 头删

尾删

 2.2.3 查找数据

 2.2.4 指定位置前中后的数据增删

指定位置之前插入数据

指定位置之后插入数据

删除指定位置之后数据

删除指定位置数据

 2.2.5 打印链表

2.2.6 销毁链表


一、链表的概念及结构

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

 

     链表的结构跟火车车厢相似,淡季时车次的车厢会相应减少,旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉或者加上,不会影响其他车厢,每节车厢都是独立存在的,车厢是独立存在的,且每节车厢都有车门,想象⼀下这样的场景,假设每节车厢的车门都是锁上的状 态,需要不同的钥匙才能解锁,每次只能携带⼀把钥匙的情况下如何从车头走到车尾? 最简单的做法:每节车厢里都放⼀把下⼀节车厢的钥匙。

链表里的“车厢”

    与顺序表不同的是,链表里的每节"车厢"都是独立申请下来的空间,我们称之为“节点”, 节点的组成主要有两个部分:当前节点要保存的数据和保存下⼀个节点的地址(指针变量)。 图中指针变量plist保存的是第⼀个节点的地址,我们称plist此时“指向”第⼀个节点,如果我们希望plist“指向”第⼆个节点时,只需要修改plist保存的内容为0x0012FFA0。

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

结合结构体知识,我们可以给出每个节点对应的结构体代码: 假设当前保存的节点为整型:

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

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

当我们想要从第⼀个节点走到最后⼀个节点时,只需要在前⼀个节点拿上下⼀个节点的地址(下⼀个 节点的钥匙)就可以了。

二、单链表的实现

2.1 头文件

    先要创建一个头文件,写入我们需要的函数名以及结构体

typedef int SLTDataType;//方便类型转换
typedef struct SListNode
{
 SLTDataType data; //节点数据 
 struct SListNode* next; //指针保存下⼀个节点的地址 
}SLTNode;

void SLTPrint(SLTNode* phead);

//头部插入删除数据/尾部插入删除数据
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

//查找数据
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除指定位置节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除指定位置之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

2.2 各个功能的实现

2.2.1 内存申请

    单链表是每添加一份数据就申请一次内存空间,虽然这样降低了一点运行效率但是有效的避免了内存空间的浪费。

SLTNode* capacity(SLTDataType x)
{
	SLTNode* new = (SLTNode*)malloc(sizeof(SLTNode));
	if (new == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	new->data = x;
	new->next = NULL; 
	return new;
}

 2.2.2 头插,尾插,头删,尾删

头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* new = capacity(x);
	new->next = *pphead;
	*pphead = new;
}
 尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* new = capacity(x);
	if (*pphead == NULL)
	{
		*pphead = new;
	}
	else
	{
		SLTNode* newnode = *pphead;
		while (newnode->next)
		{
			newnode = newnode->next;
		}
		newnode-> next= new;
	}
}
 头删

    注意free释放指针完,指针一定要有指向(指向空也是可以的),避免造成野指针。

void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead && pphead);
	SLTNode* new = (*pphead)->next;
	free(*pphead);
	*pphead = new;
}
尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead && pphead);
	SLTNode* new = *pphead;
	SLTNode* newnode = *pphead;
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* new = *pphead;
		SLTNode* newnode = *pphead;
		while (new->next)
		{
			newnode = new;
			new = new->next;
		}
		free(new);
		new = NULL;
		newnode->next = NULL;
	}
}

 2.2.3 查找数据

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

 2.2.4 指定位置前中后的数据增删

指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	if (*pphead == pos)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* new = capacity(x);
		SLTNode* newnode = *pphead;
		while (newnode->next != pos)
		{
			newnode = newnode->next;
		}
		new->next = pos;
		newnode->next = new;
	}
}
指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* new = capacity(x);
	SLTNode* newnode = pos->next;
	pos->next = new;
	new->next = newnode;
}
删除指定位置之后数据
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos&&pos->next);
	SLTNode* new = pos->next;
	pos->next = new->next;
	free(new);
	new = NULL;
}
删除指定位置数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(*pphead && *pphead);
	assert(pos);
	SLTNode* new = pos->next;
	while ((*pphead)->next != pos)
	{
		*pphead = (*pphead)->next;
	}
	(*pphead)->next = new;
	free(pos);
	pos = NULL;
}

 2.2.5 打印链表

    给定链表结构中,实现节点从头到尾的打印。

void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

2.2.6 销毁链表

void SListDesTroy(SLTNode** pphead)
{
	assert(*pphead && pphead);
	SLTNode* new=*pphead;
	while (new)
	{
		SLTNode* newnode =new->next;
		free(new);
		new = newnode;
	}
	*pphead= NULL;
}

    各个功能实现后,不要忘了测试,看看写的代码是否有误。


    本篇内容就到这里了,希望对各位有帮助,如果有错误欢迎指出。

标签:pphead,SLTNode,单向,pos,next,链表,new,数据结构,节点
From: https://blog.csdn.net/2401_86551514/article/details/140870820

相关文章

  • 双向链表的实现
    1、双向链表示意图 2、双向链表实现(1)结构体定义typedefintLTDataType;typedefstructListNode{ LTDataTypedata; structListNode*prev; structListNode*next; }LTNode;(2)初始化/****************初始化*****************/LTNode*ListInit(LTNode*phead......
  • 数据结构与算法-二分搜索树节点的查找
    ......
  • 创建一个简单的双链表
    1.ListNode.h头文件#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<string.h>typedefintLTDataType;typedefstructListNode{ structListNode*next; structListNode*prev; LTDataTypedata;}LN;//初始化......
  • c语言数据结构-单链表
    typedefstructLNode{   Elemtypedata;   structLNode*next;}LNode,*Linklist;//初始化单链表(不带头节点)boolInitList(LinkList&L){   L=NULL;   returntrue;}插入boolListInsert(LinkList&L,inti,Elemtypee){   if(i<1)  ......
  • 基于Java的数据结构课程网站的设计与实现/线上学习系统/在线教学管理系统/Web、SSM、v
    需要源码的联系方式请查看文章末尾数据结构课程网站的设计与实现摘 要计算机网络与信息化管理相配合,可以有效地提高管理人员的工作效能和改进工作的质量。良好的数据结构课程网站可以使管理员工作得到更好的实施和应用,并有助于管理员更好地管理数据结构课程,解决人力管理......
  • 数据结构:二叉树(链式结构)
    文章目录1.二叉树的链式结构2.二叉树的创建和实现相关功能2.1创建二叉树2.2二叉树的前,中,后序遍历2.2.1前序遍历2.2.2中序遍历2.2.3后序遍历2.3二叉树节点个数2.4二叉树叶子结点个数2.5二叉树第k层结点个数2.6二叉树的深度/高度2.7二叉树查找值为x的结点2.8......
  • 数据结构C语言---文件的加密和解密
    本篇的主要目的是利用所学的数据结构的知识对一个任意文件进行加密和解密。在文件加密过程中,常用的数据结构包括哈希表、树结构(如二叉搜索树、哈夫曼树)、堆、链表等。选择合适的数据结构取决于加密算法的需求和特性。选择合适的加密算法和数据结构对保障数据安全至关重要。常......
  • 数据结构实验----邻接表和拓扑排序
    一.实验目的1.理解拓扑排序的特性和算法;2.通过构造图的邻接表,掌握拓扑排序算法。二.实验内容1.建立邻接表存储的图;2.对图进行拓扑排序;3.输出拓扑排序序列。三.代码#include<stdio.h>#include<string.h>#include<stdlib.h>#defineMAXSIZE10#defineOK1#......
  • 数据结构实验---散列表
    一.实验目的1.理解散列表的存储结构;2.掌握常用散列函数构造方法和处理冲突方法;3.在散列表上实现查找的算法。二.实验内容为小于n个关键字设计一个散列表,使得查找成功时平均查找长度<2.0,要求完成相应的散列表建立和查找。假设关键字为整型数据,散列函数用除留余数法,采用开放......
  • 【数据结构】排序
    目录1.前言2.排序的概念及引用2.1排序的概念2.2常见的排序算法 3.常见排序算法的实现3.1插入排序3.1.1基本思想 3.1.2直接插入排序 3.1.3希尔排序(缩小增量排序)3.2选择排序3.2.1基本思想3.2.2直接选择排序3.2.3堆排序3.3交换排序3.3.1基本思想3.3.2冒泡排......