首页 > 其他分享 >【数据结构】—— 单链表(single linked list)

【数据结构】—— 单链表(single linked list)

时间：2024-07-08 20:02:03浏览次数：17  
标签：pphead list pos 节点 single SLNode plist next linked

文章目录

1、单链表的定义

单链表（Singly LinkedList）是一种链式存储的数据结构，它由一系列节点组成，每个节点包含两部分：数据部分（存储数据元素）和指针部分（指向下一个节点的指针）。

在这里插入图片描述

优点和缺点

优点：简单易实现，插入和删除操作只需调整指针，时间复杂度为 O(1)。
缺点：不支持随机访问，访问某个节点的时间复杂度为 O(n)，并且需要额外的空间来存储指针。

单链表的构成

单链表由一系列节点构成，每个节点存储当前节点的数据和指向下一个节点的指针。

typedef struct SListNode
{
	SLDateType date;//存储当前节点的数据
	struct SListNode* next;//存储下一个节点的地址
	//struct SLNode* next;为什么这里不能用SLNode替换，因为程序运行到这个位置还没有成功typedef，因此提前使用会报错
}SLNode;

2、单链表的创建

初始化：

通过定义头节点来管理链表，头指针指向单链表的第一个节点，头节点内通常不存储数据，因此对头指针悬空即可。

SLNode* plist = (SLNode*)malloc(sizeof(SLNode));//动态分配内存
plist->next=NULL;//头指针悬空

Q:为什么使用malloc

1）动态分配内存: malloc 允许在程序运行时动态分配内存，我们可以动态地创建新的节点，而不必预先知道节点的数量或者大小。
2）避免静态内存限制：可以在运行时根据需要分配内存，灵活性更高。
3）内存生命周期管理:malloc分配的内存块无需free函数释放，避免内存泄漏问题，即程序运行过程中持续占用未使用的内存。

3、单链表的接口实现

打印

创建节点pcur从头节点开始遍历链表，直到pcur为空为止

void SLPrint(SLNode* headList)
{
	SLNode* pcur = headList;//头节点
	while (pcur)
	{
		printf("%d->", pcur->date);//打印当前节点的数据
		pcur = pcur->next;//指向下一个节点
	}
	printf("NULL\n");
}

申请节点函数
对申请节点功能进行封装，方便调用。

SLNode* SLBuyNode(SLDateType x)//封装
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));//创建新节点:malloc默认返回void*类执政，这里强制转换为SLNode*指针类型
	if (newnode == NULL)//如果malloc申请失败直接退出
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->date = x;
	newnode->next = NULL;
	return newnode;
}

尾插

从头节点开始遍历，直到节点的next指向NULL后进行尾插。
Q:为什么使用二级指针

为了能够修改函数外部传入的单链表头指针的值,传入的是&plist,如果使用SLNode*phead会导致函数内部无法修改函数外部传入的头指针。因此这里应该采用传址调用而不是传值调用，用二级指针SLNode**pphead接收传入头节点的地址。
在这里插入图片描述

在这里插入图片描述

void SLPushBack(SLNode** pphead, SLDateType x){
	assert(pphead);
	SLNode* newnode=SLBuyNode(x);//调用申请节点函数
	//链表为空，新节点作为head
	if (*pphead == NULL) {//解引用一次，即为第一个节点的地址
		*pphead = newnode; 
		newnode->next = NULL; //新节点指向NULL
		return;
	}
	//链表不为空，找到尾节点
	SLNode* TailList = *pphead;//解引用一次，即为第一个节点的地址
	while (TailList->next)//当下一个节点不为NULL时继续循环
	{
		TailList = TailList->next;
	}
	//结束while后TailList即为尾节点,使尾节点指向新节点(更新尾节点)
	TailList->next = newnode;
	newnode->next = NULL;
}

头插

传入头节点直接插入即可

void SLPushFront(SLNode** pphead, SLDateType x)
{
	SLNode* newnode = SLBuyNode(x);//调用申请节点函数
	newnode->next = *pphead;
	*pphead = newnode;
}

尾删

分两种情况，当链表只有一个节点，直接删除头节点即可。否则遍历链表找到尾节点并删除。

在这里插入图片描述
注意：不能传入空地址

void SLPopBack(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);//链表不能为空(*pphead指向第一个节点的地址)
	//两种情况： 
	// 1）当链表只有一个节点 
	if ((*pphead)->next == NULL)
	{
		//释放动态分配的内存,提高系统的资源利用率和性能
		free(*pphead);
		*pphead = NULL;
		return;
	}
	// 2）链表有多个节点
	SLNode* ptail = *pphead;
	SLNode* newLnode = NULL;
	while (ptail->next)
	{
		newLnode = ptail;
		ptail = ptail->next;
	}
	//跳出后newLnode更新为最后一个节点
	newLnode->next = NULL;
	//销毁尾节点
	free(ptail);//释放内存
	ptail = NULL;
}

头删

创建节点保存要删除的节点，更新头节点，最后删除已经保存的节点

void SLPopFront(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);//链表不为空
	SLNode* head = *pphead;//保存要删除的节点
	*pphead = (*pphead)->next;//->的优先级高于*
	free(head);
	head = NULL;
}

查找

从头节点遍历链表，找到返回节点，否则返回-1

SLNode* SLFind(SLNode** pphead, SLDateType x)
{
	assert(pphead);//不能传NULL

	//遍历链表
	SLNode* pcur = *pphead;
	while (pcur!=NULL)
	{
		if (pcur->date == x) {//找到了返回节点
			return pcur;
		}
		pcur = pcur->next;
	}
	//没找到
	return NULL;
}

在指定位置之前插入

分两种情况，指定位置为头节点直接插入即可，否则从头节点开始遍历找到指定位置前一个结点prev，(修改对应指针连接)重新连接prev（指定位置前一个结点）,newnode（插入的节点），pos（指定的位置）
在这里插入图片描述

void SLInsert(SLNode** pphead, SLNode* pos, SLDateType x){
	assert(pphead);
	assert(pos);//pos是链表中某一个有效节点
	//要加上链表不能为空
	assert(*pphead);

	SLNode* newnode = SLBuyNode(x);//申请节点
	//pos刚好是头节点
	if (pos == *pphead) {
		SLPushFront(*pphead, x);
		return;
	}

	//找pos的前驱节点
	SLNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//重新连接 prev->newnode->pos
	prev->next = newnode;
	newnode->next = pos;
}

在指定位置之后插入

申请节点后直接插入即可（注意传入的节点不能是NULL）

void SLInsertAfter(SLNode* pos, SLDateType x) {
	assert(pos);

	SLNode* newnode = SLBuyNode(x);//申请新节点

	//pos->newnode->(pos->next)
	//先将newnode指向下一个节点
	newnode->next = pos->next;
	pos->next = newnode;
}

删除指定位置的节点

分两种情况：如果pos为头节点，直接调用SLPopFront()进行删除，否则遍历链表找到指定节点后进行删除。

void SLErase(SLNode** pphead, SLNode* pos) {
	assert(pphead);
	assert(*pphead);//头节点不为NULL
	assert(pos);

	//pos刚好是头节点
	if (*pphead == pos) {
		SLPopFront(pphead);
		return;
	}

	SLNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = pos->next;
	free(pos);//释放空间
}

删除指定位置之后的节点

删除后释放空间即可

void SLEraseAfter(SLNode* pos) {
	assert(pos);
	assert(pos->next);
	SLNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

销毁链表

通过遍历删除所有节点

void SListDesTroy(SLNode** pphead) {
	assert(pphead);
	assert(*pphead);

	SLNode* pcur = *pphead;
	while (pcur)
	{
		SLNode* next = pcur->next;
		free(pcur);//删除节点
		pcur = next;
	}
	*pphead = NULL;
}

4、源代码

.h文件

#pragma once//防止头文件被二次引用
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDateType;
//链表由节点组成
typedef struct SListNode
{
	SLDateType date;//存储当前节点的数据
	struct SListNode* next;//存储下一个节点的地址
	//struct SLNode* next;为什么这里不能用SLNode替换，因为程序运行到这个位置还没有成功typedef，因此提前使用会报错
}SLNode;
//打印链表
void SLPrint(SLNode* phead);

//二级指针接受一级指针
void SLPushBack(SLNode** pphead,SLDateType x);//尾插
void SLPushFront(SLNode** pphead, SLDateType x);//头插

void SLPopBack(SLNode** pphead);//尾删
void SLPopFront(SLNode** pphead);//头删

//查找
SLNode* SLFind(SLNode** pphead, SLDateType x);

//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDateType x);

//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDateType x);

//删除指定位置的节点
void SLErase(SLNode** pphead, SLNode* pos);

//删除指定位置之后的节点
void SLEraseAfter(SLNode* pos);

//销毁链表
void SListDesTroy(SLNode** pphead);

**

.c文件

**

#include "SList.h"

void SLPrint(SLNode* headList)
{
	SLNode* pcur = headList;//头节点
	while (pcur)
	{
		printf("%d->", pcur->date);//打印当前节点的数据
		pcur = pcur->next;//指向下一个节点
	}
	printf("NULL\n");
}
//申请节点的函数
SLNode* SLBuyNode(SLDateType x)//封装
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));//创建新节点:malloc默认返回void*类执政，这里强制转换为SLNode*指针类型
	if (newnode == NULL)//如果malloc申请失败直接退出
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->date = x;
	newnode->next = NULL;
	return newnode;
}
//尾插
void SLPushBack(SLNode** pphead, SLDateType x){
	assert(pphead);
	SLNode* newnode=SLBuyNode(x);//调用申请节点函数
	//链表为空，新节点作为head
	if (*pphead == NULL) {//解引用一次，即为第一个节点的地址
		*pphead = newnode; 
		newnode->next = NULL; //新节点指向NULL
		return;
	}
	//链表不为空，找到尾节点
	SLNode* TailList = *pphead;//解引用一次，即为第一个节点的地址
	while (TailList->next)//当下一个节点不为NULL时继续循环
	{
		TailList = TailList->next;
	}
	//结束while后TailList即为尾节点,使尾节点指向新节点(更新尾节点)
	TailList->next = newnode;
	newnode->next = NULL;
}
//头插
void SLPushFront(SLNode** pphead, SLDateType x)
{
	SLNode* newnode = SLBuyNode(x);//调用申请节点函数
	newnode->next = *pphead;
	*pphead = newnode;
}

void SLPopBack(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);//链表不能为空(*pphead指向第一个节点的地址)
	//两种情况： 
	// 1）当链表只有一个节点 
	if ((*pphead)->next == NULL)
	{
		//释放动态分配的内存,提高系统的资源利用率和性能
		free(*pphead);
		*pphead = NULL;
		return;
	}
	// 2）链表有多个节点
	SLNode* ptail = *pphead;
	SLNode* newLnode = NULL;
	while (ptail->next)
	{
		newLnode = ptail;
		ptail = ptail->next;
	}
	//跳出后newLnode更新为最后一个节点
	newLnode->next = NULL;
	//销毁尾节点
	free(ptail);
	ptail = NULL;
}


void SLPopFront(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);//链表不为空
	SLNode* head = *pphead;//保存要删除的节点
	*pphead = (*pphead)->next;//->的优先级高于*
	free(head);
	head = NULL;
}

SLNode* SLFind(SLNode** pphead, SLDateType x)
{
	assert(pphead);//不能传NULL

	//遍历链表
	SLNode* pcur = *pphead;
	while (pcur!=NULL)
	{
		if (pcur->date == x) {//找到了返回节点
			return pcur;
		}
		pcur = pcur->next;
	}
	//没找到
	return NULL;
}

void SLInsert(SLNode** pphead, SLNode* pos, SLDateType x){
	assert(pphead);
	assert(pos);//pos是链表中某一个有效节点
	//要加上链表不能为空
	assert(*pphead);

	SLNode* newnode = SLBuyNode(x);//申请节点
	//pos刚好是头节点
	if (pos == *pphead) {
		SLPushFront(*pphead, x);
		return;
	}

	//找pos的前驱节点
	SLNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//重新连接 prev->newnode->pos
	prev->next = newnode;
	newnode->next = pos;
}

void SLInsertAfter(SLNode* pos, SLDateType x) {
	assert(pos);

	SLNode* newnode = SLBuyNode(x);//申请新节点

	//pos->newnode->(pos->next)
	//先将newnode指向下一个节点
	newnode->next = pos->next;
	pos->next = newnode;
}

void SLErase(SLNode** pphead, SLNode* pos) {
	assert(pphead);
	assert(*pphead);//头节点不为NULL
	assert(pos);

	//pos刚好是头节点
	if (*pphead == pos) {
		SLPopFront(pphead);
		return;
	}

	SLNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = pos->next;
	free(pos);
}

void SLEraseAfter(SLNode* pos) {
	assert(pos);
	assert(pos->next);
	SLNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

void SListDesTroy(SLNode** pphead) {
	assert(pphead);
	assert(*pphead);

	SLNode* pcur = *pphead;
	while (pcur)
	{
		SLNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

**

测试文件

**

#include "SList.h"

void SListTest01() 
{
	//新建节点
	/*Q:为什么使用malloc
	1）动态分配内存: malloc 允许在程序运行时动态分配内存，我们可以动态地创建新的节点，而不必预先知道节点的数量或者大小。
	2）避免静态内存限制：可以在运行时根据需要分配内存，灵活性更高。
	3）内存生命周期管理:malloc分配的内存块无需free函数释放，避免内存泄漏问题，即程序运行过程中持续占用未使用的内存。
	创建链表，方便展示链表打印*/
	SLNode* node1 = (SLNode*)malloc(sizeof(SLNode));//malloc默认返回void*类执政，这里强制转换为SLNode*指针类型
	node1->date = 1;//存储node1的数据
	SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));
	node2->date = 2;
	SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));
	node3->date = 3;
	SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));
	node4->date = 4;
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;
	SLNode* headList = node1;
	SListPrint(headList);
}

//测试尾插
void SListTest02()
{
	SLNode* plist = NULL;
	SLPushBack(&plist, 1);///plist本身是一级指针
	//现在对一级指针取地址，此时为二级指针，且必须用二级指针接受一级指针的地址
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 2);
	SLPrint(plist);
	//SLPushBack(NULL, 1);
	//SLPrint(NULL);
	//说明传入地址不能为空
}

void SListTest03() {
	SLNode* plist = NULL;
	SLPushFront(&plist, 1);
	SLPrint(plist);
	SLPushFront(&plist,3);
	SLPushFront(&plist,5);
	SLPrint(plist);
}

void SListTest04() {
	SLNode* plist = NULL;
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 5);
	SLPopBack(&plist);
	SLPrint(plist);//为什么打印就不用传地址
}

void SListTest05() {
	SLNode* plist = NULL;
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 5);
	SLPopFront(&plist);
	SLPrint(plist);//为什么打印就不用传地址
}

void SListTest06() {
	SLNode* plist = NULL;
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 5);
	SLPrint(plist);//为什么打印就不用传地址
    SLNode* node1=SLFind(&plist,3);
	if (node1) printf("找到了\n");
	else printf("未找到\n");
	SLNode* node2 = SLFind(&plist,4);
	if (node2) printf("找到了\n");
	else printf("未找到\n");
}

void SListTest07() {
	SLNode* plist = NULL;
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 5);
	SLPrint(plist);
	SLNode* FindRet = SLFind(&plist, 3);//返回链表中3的节点
	SLInsert(&plist, FindRet, 999);
	SLPrint(plist);
}

void SListTest08() {
	SLNode* plist = NULL;
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 5);
	SLPrint(plist);
	SLNode* FindRet = SLFind(&plist, 3);//返回链表中3的节点
	SLInsertAfter(FindRet, 999);
	SLPrint(plist);
}

void SListTest09() {
	SLNode* plist = NULL;
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 5);
	SLPrint(plist);
	SLNode* FindRet = SLFind(&plist, 3);//返回链表中3的节点
	SLErase(&plist, FindRet);
	SLPrint(plist);
}

void SListTest10() {
	SLNode* plist = NULL;
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 5);
	SLPrint(plist);
	SLNode* FindRet = SLFind(&plist, 3);//返回链表中3的节点
	SLEraseAfter(FindRet);
	SLPrint(plist);
}

void SListTest11() {
	SLNode* plist = NULL;
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 5);
	SLPrint(plist);
	SListDesTroy(&plist);
	SLPrint(plist);
}

int main()
{
	//SListTest01();//测试打印
	//SListTest02();//尾插
	//SListTest03();//头插
	//SListTest04();//尾删
	//SListTest05();//头删
	//SListTest06();//查找
	//SListTest07();//指定位置前插入节点
	//SListTest08();//指定位置后插入节点
	//SListTest09();//删除指定位置的节点
	//SListTest10();//删除指定位置之后的节点
	SListTest11();//销毁链表
	return 0;
}

标签：pphead,list,pos,节点,single,SLNode,plist,next,linked
From： https://blog.csdn.net/xasdf338/article/details/140177122

相关文章

  • List 转 Page
    packagecom.leo.boot.jpa.stream;importorg.apache.commons.collections4.CollectionUtils;importorg.apache.commons.collections4.IterableUtils;importorg.springframework.beans.BeanUtils;importorg.springframework.data.domain.Page;importorg.springfram......
  • List 按照指定大小分片的几种方式
    如果有一个list<string>里面可能有1000份或者更多数据,如果需要进行入库等操作,需要拆分成指定大小每份进行处理,这种需求很常见,那么应该怎么做呢?首先我们需要将List<String> 转为多份后进行逐个处理, 处理批量事务注意事务哦 那么怎么将list转为多份呢? 下面介绍2......
  • WPF single instance via mutex
    usingSystem;usingSystem.Collections.Generic;usingSystem.Configuration;usingSystem.Data;usingSystem.Diagnostics.Eventing.Reader;usingSystem.Linq;usingSystem.Runtime.InteropServices;usingSystem.Threading;usingSystem.Threading.Tasks;usingS......
  • python数据容器（一）列表list
    思维导图代码1.数据容器入门2.数据容器：list（列表）name_list=['itheima','itcast','python']print(name_list)print(type(name_list))运行结果： name_list=['itheima',666,True]print(name_list)print(type(name_list))运行结果： name_l......
  • python: list
     #去重A=['geovindu','刘杰','江山','河水','刘杰','geovindu','张三','李五']B=[]foriinA:ifinotinB:B.append(i)print(B)C=set(A)......
  • HashTable，ArrayList，queue等常用方法
    HashTable，ArrayList，queue等常用方法HashMap是Java中非常常用的集合类，它存储键值对，并提供了一系列方便的方法来操作这些数据。以下是一些HashMap的常用方法：1.添加和获取元素:put(key,value):将指定的键值对添加到HashMap中。如果键已存在，则更新对应的值。get(ke......
  • C++list的模拟实现
    链表节点 template<classT> structListNode { ListNode(constT&data=T()) : _data(data) { } ListNode<T>*_prev=nullptr; ListNode<T>*_next=nullptr; T_data; };因为之后要访问这个类的成员变量函数和结构体，所以在这里将class直接改为struct......
  • set_source_files_properties QT_QML_SINGLETON_TYPE
    目录前言QT_QML_SINGLETON_TYPE 属性基本用法示例1.创建一个基本的CMake项目2.编辑 CMakeLists.txt3.创建 main.cpp4.创建 MySingleton.qml5.创建 qml.qrc6.创建 main.qml构建和运行项目结论前言在使用Qt和CMake构建项目时，有时你可能需要将......
  • 3-List
    ListList继承于CollectionList常用方法/*List接口中常用方法：增加:add(intindex,Eelement)删除:remove(intindex)remove(Objecto)修改:set(intindex,Eelement)查看:get(intindex)判断:......
  • java List集合排序方式
    javaList集合排序方式1.使用直接上代码packagecom.demo;importcn.hutool.core.date.DateTime;importlombok.AllArgsConstructor;importlombok.Data;importjava.util.*;importjava.util.stream.Collectors;publicclassDemoCollectionsSortMain{public......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99