【数据结构】单链表-->详细讲解,后赋源码

欢迎来到我的Blog,点击关注哦💕

前面已经介绍顺序表,顺序表存在一定的局限性,空间管理上存在一定的缺陷,今天介绍新的存储结构单链表。

前言:

单链表是一种基本的数据结构,它由一系列节点组成,每个节点包含数据部分和一个指向下一个节点的指针。在单链表中,每个节点的地址不一定是连续的,而是通过指针相互链接起来。单链表的特点是存储灵活,可以动态地添加或删除节点,不需要预先分配固定大小的存储空间。

一、单链表基本介绍

单链表创建

1.定义节点结构体:首先需要定义一个结构体来表示链表的节点,通常包括数据域和指针域。
2.动态创建节点:使用malloc函数为每个节点分配内存空间,并初始化数据域和指针域。
3.插入节点:根据需要将新节点插入到链表的适当位置。插入操作可以是头插法或尾插法。
4.遍历链表:通过遍历链表,可以访问链表中的每个节点,通常用于打印或搜索特定数据。

单链表的操作

单链表的常见操作包括插入删除查找遍历。这些操作通常涉及到对链表节点的指针进行操作,以实现数据的动态管理。

单链表的理解

链表同名字一样,像一个链子一样,有一个一个节点相连接。

A
B
C
D
E
....

二、单链表的实现

2.1 单链表的功能

分装成函数,有助于我们一一管理。

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 在pos的前面插入
void SLTInsert(SListNode** pplist, SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos); 
// 删除pos位置
void SLTErase(SListNode** pplist, SListNode* pos);
///删除pos前面的值
void SListEraseFront(SListNode* pos);
//单链表的销毁
void SLTDestory(SListNode** pphead);

2.2 定义节点结构体

数域 和 指针域

typedef int SLTDateType;

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

2.3 动态创建节点

SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newcode = (SLTDateType*)malloc(sizeof(SListNode));
	if (newcode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newcode->data = x;
	newcode->next = NULL;

	return newcode;
}

2.3 单链表便历

注意:链表和顺序表的区别顺序表内存是连续的,链表是由一个一个节点连接的,‘cur’ 指向的下一个节点赋值给‘cur’cur = cur->next;

void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

2.4 单链表的尾插

断言 pplist 避免传参时候造成不必要的麻烦

//单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newcode = BuySListNode(x);

	if (*pplist == NULL)
	{
		*pplist = newcode;
	}
	else
	{
		//找尾
		SListNode* tail = *pplist;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newcode;
	}
}

2.5 单链表的尾删除

//单链表尾删
void SListPopBack(SListNode** pplist)
{
	//节点断言
	assert(pplist);
	assert(*pplist);
	//存在节点 1.存在一个节点 2.存在两个节点
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		//找尾

		//SListNode* tail = *pplist;
		//while (tail->next->next != NULL)
		//{
		//	tail = tail->next;
		//}
		//free(tail->next);
		//tail->next = NULL;

		SListNode* prv = NULL;
		SListNode* tail = *pplist;
		while (tail->next != NULL)
		{
			prv = tail;
			tail = tail->next;
		}

		free(tail);
		prv->next = NULL;
	}
}

2.6 单链表的头插

这个相对简单

//单链表头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* newcode = BuySListNode(x);
	newcode->next = *pplist;
	*pplist = newcode;
}

2.6 单链表的头删

//单链表头删
void SListPopFront(SListNode** pplist)
{
	//节点断言
	assert(*pplist);

	SListNode* first = *pplist;
	*pplist = first->next;
	free(first);
	first = NULL;
}

2.7 单链表的查找

//单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

2.8 单链表在指定位置(pos)的插入

2.8.1 在pos后面
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newcode = BuySListNode(x);
	newcode->next = pos->next;
	pos->next = newcode;
}
2.8.2 在pos前面插入
// 在pos的前面插入
void SLTInsert(SListNode** pplist, SListNode* pos, SLTDateType x)
{
	assert(pplist);
	assert(*pplist);

	SListNode* newcode = BuySListNode(x);
	if (pos == *pplist)
	{
		SListPushFront(pplist,x);
	}
	else
	{
		SListNode* cur = *pplist;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		newcode->next = pos;
		cur->next = newcode;
	}
}
2.8.3 在pos后面插入
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newcode = BuySListNode(x);
	newcode->next = pos->next;
	pos->next = newcode;
}

2.9 在指定位置(pos)删除

2.9.1 删除在pos位置前面
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	SListNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}
2.9.2 删除 pos 本位上的值
// 删除pos位置
void SLTErase(SListNode** pplist, SListNode* pos)
{
	assert(pplist);
	assert(*pplist);

	SListNode* tail = *pplist;
	while (tail->next != pos)
	{
		tail = tail->next;
	}
	tail->next = pos->next;
	free(pos);
	pos = NULL;
}
2.9.3 删除pos位置后面的值
//删除pos前面的值
void SListEraseFront(SListNode** pplist,SListNode* pos)
{
	assert(pplist);
	assert(*pplist);

	SListNode* tail = *pplist;
	while (tail->next->next != pos)
	{
		tail = tail->next;
	}
	SListNode* del = tail->next;
	tail->next = pos;
	free(del);
	del = NULL;
}

2.10 单链表的销毁

不可以直接销毁*pplist,内存存贮不是连续的需要一个一个销毁。

//销毁链表
void SLTDestory(SListNode** pplist)
{
	assert(pphead);
	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;

源码

SLT.h

#pragma once


#include <stdio.h>
#include <assert.h>
#include <stdlib.h>


typedef int SLTDateType;

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 在pos的前面插入
void SLTInsert(SListNode** pplist, SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos); 
// 删除pos位置
void SLTErase(SListNode** pplist, SListNode* pos);
///删除pos前面的值
void SListEraseFront(SListNode* pos);
//单链表的销毁
void SLTDestory(SListNode** pplist);

SLT.c

#define _CRT_SECURE_NO_WARNINGS
#include"SLT.h"


//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newcode = (SLTDateType*)malloc(sizeof(SListNode));
	if (newcode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newcode->data = x;
	newcode->next = NULL;

	return newcode;
}

//打印单链表
void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

//单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	SListNode* newcode = BuySListNode(x);

	if (*pplist == NULL)
	{
		*pplist = newcode;
	}
	else
	{
		//找尾
		SListNode* tail = *pplist;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newcode;
	}
}


//单链表尾删
void SListPopBack(SListNode** pplist)
{
	//节点断言
	assert(*pplist);
	//if((*pplist)==NULL)
	// return ;

	//存在节点 1.存在一个节点 2.存在两个节点
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		//找尾

		//SListNode* tail = *pplist;
		//while (tail->next->next != NULL)
		//{
		//	tail = tail->next;
		//}
		//free(tail->next);
		//tail->next = NULL;

		SListNode* prv = NULL;
		SListNode* tail = *pplist;
		while (tail->next != NULL)
		{
			prv = tail;
			tail = tail->next;
		}

		free(tail);
		prv->next = NULL;
	}
}


//单链表头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* newcode = BuySListNode(x);
	newcode->next = *pplist;
	*pplist = newcode;
}

//单链表头删
void SListPopFront(SListNode** pplist)
{
	//节点断言
	assert(*pplist);

	SListNode* first = *pplist;
	*pplist = first->next;
	free(first);
	first = NULL;
}

//单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newcode = BuySListNode(x);
	newcode->next = pos->next;
	pos->next = newcode;
}

// 在pos的前面插入
void SLTInsert(SListNode** pplist, SListNode* pos, SLTDateType x)
{
	assert(pplist);
	assert(*pplist);

	SListNode* newcode = BuySListNode(x);
	if (pos == *pplist)
	{
		SListPushFront(pplist,x);
	}
	else
	{
		SListNode* cur = *pplist;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		newcode->next = pos;
		cur->next = newcode;
	}
}

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	SListNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}

// 删除pos位置
void SLTErase(SListNode** pplist, SListNode* pos)
{
	assert(pplist);
	assert(*pplist);

	SListNode* tail = *pplist;
	while (tail->next != pos)
	{
		tail = tail->next;
	}
	tail->next = pos->next;
	free(pos);
	pos = NULL;
}

//删除pos前面的值
void SListEraseFront(SListNode** pplist,SListNode* pos)
{
	assert(pplist);
	assert(*pplist);

	SListNode* tail = *pplist;
	while (tail->next->next != pos)
	{
		tail = tail->next;
	}
	SListNode* del = tail->next;
	tail->next = pos;
	free(del);
	del = NULL;
}


//销毁链表
void SLTDestory(SListNode** pplist)
{
	assert(pplist);
	SListNode* cur = *pplist;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pplist = NULL;

Test.c

#define _CRT_SECURE_NO_WARNINGS


#include "SLT.h"

void testSList1()
{
	SListNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);

	SListNode* ret = SListFind(plist, 2);
	//ret->data = (ret->data) * 3;

	//SListInsertAfter(ret, 66);

	SLTInsert(&plist, ret, 77);

	//SListEraseAfter(ret);

	//SLTErase(&plist, ret);

	SListEraseFront(&plist, ret);

	SListPrint(plist);

}

void testSList2()
{
	SListNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);


	SListPopFront(&plist);
	SListPopFront(&plist);

	SListPrint(plist);



}

int main()
{

	testSList1();
	//testSList2();


	return 0;
}

相关推荐

  1. 数据结构-->详细讲解

    2024-06-08 21:24:01       8 阅读

最近更新

  1. 国际化项目开发中关于时间的问题二

    2024-06-08 21:24:01       0 阅读
  2. Linux知识汇总

    2024-06-08 21:24:01       0 阅读
  3. Flink集群运行模式

    2024-06-08 21:24:01       0 阅读
  4. 617作业

    617作业

    2024-06-08 21:24:01      0 阅读
  5. k8s_DaemonSet和Deployment区别

    2024-06-08 21:24:01       0 阅读
  6. 细说MCU定时器中断的实现方法

    2024-06-08 21:24:01       0 阅读
  7. webpack之HMR

    2024-06-08 21:24:01       0 阅读

热门阅读

  1. android 异屏同显二.

    2024-06-08 21:24:01       5 阅读
  2. 2014年上海高考作文题目(ChatGPT版)

    2024-06-08 21:24:01       3 阅读
  3. golang定时器使用示例

    2024-06-08 21:24:01       6 阅读
  4. 前端常见的加密方式

    2024-06-08 21:24:01       6 阅读
  5. input输入框设置样式

    2024-06-08 21:24:01       6 阅读
  6. Ansible——fetch模块

    2024-06-08 21:24:01       5 阅读
  7. Mybatis06-动态SQL

    2024-06-08 21:24:01       6 阅读
  8. 微信小程序动画和Canvas笔记

    2024-06-08 21:24:01       5 阅读