文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

C语言数据结构超详细讲解单向链表

2024-04-02 19:55

关注

1.链表概况

1.1 链表的概念及结构

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

1.2 链表的分类

实际中链表的结构非常多样,以下情况组合起来就有8种链表结构

单向或者双向

带头或者不带头

循环或者非循环

虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构

2. 单向链表的实现

单向链表结构

2.1 SList.h(头文件的汇总,函数的声明)

#pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;

typedef struct SListNode
{
	int data;//数据
	struct SListNode* next;//下一个节点的地址
}SListNode;

void SListPrint(SListNode* phead);//打印

SListNode* BuySListNode(SLTDataType x);//搞出一个新节点

void SListPushBack(SListNode** pphead, SLTDataType x);//尾插
void SListPushFront(SListNode** pphead, SLTDataType x);//头插

void SListPopBack(SListNode** pphead);//尾删
void SListPopFront(SListNode** pphead);//头删

SListNode* SListFind(SListNode* phead, SLTDataType x);//查找

void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);//在pos位置之前插入
void SListInsertAfter(SListNode* pos, SLTDataType x);//在pos位置之后插入

void SListErase(SListNode** pphead, SListNode* pos);//删除pos位置
void SListEraseAfter(SListNode* pos);//删除pos之后位置

void SListDestroy(SListNode** pphead);//销毁

2.2 SList.c(函数的具体实现逻辑)

2.2.1 打印链表

//打印
void SListPrint(SListNode* phead)
{
	//assert(phead);//没必要断言,空链表也能打印
	SListNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
//test.c
void TestSList1()
{
	SListNode* slist;//结构体指针,用于存节点的地址
	SListNode* n1 = (SListNode *)malloc(sizeof(SListNode));
	SListNode* n2 = (SListNode*)malloc(sizeof(SListNode));
	SListNode* n3 = (SListNode*)malloc(sizeof(SListNode));
	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n1->next = n2;
	n2->next = n3;
	n3->next = NULL;
	slist = n1;

	SListPrint(slist);
}

2.2.2 搞出一个新节点(为其他函数服务)

//搞出一个新节点
SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}

	return newnode;
}

2.2.3 链表尾插

//尾插
void SListPushBack(SListNode** pphead,SLTDataType x)//会改变实参slist,要传二级指针
{
	assert(pphead);//就算链表是空,它的二级指针也不为空
	SListNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//遍历找尾
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
void TestSList2()
{
	SListNode* slist = NULL;
	for (int i = 0; i < 6; i++)
	{
		SListPushBack(&slist,i);
	}
	SListPrint(slist);
}

2.2.4 链表头插

//头插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
	assert(pphead);//就算链表是空,它的二级指针也不为空

	SListNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void TestSList2()
{
	SListNode* slist = NULL;
	for (int i = 0; i < 6; i++)
	{
		SListPushFront(&slist,i);
	}
	SListPrint(slist);
}

2.2.5 链表尾删

方法1(用两个指针,分别找最后一个和倒数第二个):

方法2(直接找倒数第二个):

//尾删
void SListPopBack(SListNode** pphead)//如果只有一个节点但还要尾删,就会改变实参slist,建议传二级指针
{
	assert(pphead);//就算链表是空,它的二级指针也不为空
	//三种情况:
	//1.空
	//2.一个节点
	//3.多个节点
	if (*pphead == NULL)
	{
		return;
	}

	else if ((*pphead)->next == NULL)//优先级,记得加括号
	{
		free(*pphead);
		*pphead = NULL;
	}

	//第一种写法(用两个指针,分别找最后一个和倒数第二个)
	else
	{
		SListNode* prev = NULL;//找倒数第二个元素,用于将它指向NULL
		SListNode* tail = *pphead;//找尾
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;//习惯性free掉就将其置空

		prev->next = NULL;
	}

	//方法二(直接找倒数第二个)
	//else
	//{
		//SListNode* tail = *pphead;//找尾
		//while (tail->next->next != NULL)
		//{
		//	tail = tail->next;
		//}
		//free(tail->next);
		//tail->next = NULL;
	//}
}

2.2.6 链表头删

//头删
void SListPopFront(SListNode** pphead)
{
	assert(pphead);
	//1.空
	//2.非空
	if (*pphead == NULL)
	{
		return;
	}
	else
	{
		SListNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}

2.2.7 查找节点

//查找
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
	SListNode* cur = phead;
	while (phead != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

2.2.8 在pos位置之前插入

//在pos位置之前插入(一般跟find配合使用)
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);//间接检测链表是否为空,因为空链表找不到pos
	//1.pos是第一个节点(头插)
	//2.pos不是第一个节点
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SListNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

2.2.9 在pos位置之后插入

方法1:两个指针,先连接pos和newnode还是先连接newnode和next都行

方法2:只有一个指针,一定要先通过pos连接newnode和下一个,再连接pos和newnode,否则会找不到下一个的地址。

//在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	SListNode* next = pos->next;
	newnode->next = next;//顺序无所谓
	pos->next = newnode;
	//或者不定义next
	//newnode->next = pos->next;
	//pos->next = newnode;//顺序要定好,否则会找不到
}

2.2.10 删除pos位置

//删除pos位置
void SListErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(pos);

	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;//好习惯
	}
}

2.2.11 删除pos之后位置

//删除pos之后位置
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	SListNode* next = pos->next;
	if (next)//防止pos是最后一个元素
	{
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}

2.2.12 链表销毁

一个个找,一个个销毁,最终将slist置空。

//销毁
void SListDestroy(SListNode** pphead)
{
	assert(pphead);

	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

总结:单链表结构,适合头插头删。尾部或者中间某个位置插入删除不适合。如果要使用链表单独存储数据,那我们之后会学的双向链表更合适。单链表学习的意义:

链表系列有很多重点内容,我会花不少时间来跟大家讲解链表,相信大家跟着练习的话编程严谨性会大大提升,加油哦!

到此这篇关于C语言数据结构超详细讲解单向链表的文章就介绍到这了,更多相关C语言 单向链表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯