数据结构初阶——单链表

概念：

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

  • 物理结构
    在这里插入图片描述
    假设这些是一个链表的地址，特点为非连续，非顺序。
  • 逻辑结构
    在这里插入图片描述
    节点一般从堆上申请出来，通过指针首尾相连，将这些节点形成链表。

单链表的实现

还是老样子分三个文件，分别实现函数声明、函数定义与主函数实现。

函数的声明

  • 初始化

在这里插入图片描述
先使用个typedef关键字类型重命名int，方便后续更换存储不同的数据类型。再将结构体类型struct SListNode重命名为SLTNode，其中存放着SLTDataType类型的数据和该结构体类型的指针。

函数的定义

创建节点BuySLTNode

在这里插入图片描述
返回值是一个结构体类型指针。通过malloc动态开辟一个内存为SLTNode结构体大小的空间，该结构体指针newnode指向这块空间。然后判断malloc是否成功，返回值不为空就将其中存放数据位置赋值为目标值，再将存放指针位置置空，方便后续链接。

尾插SLTPushBack

在这里插入图片描述
重点注意：因为要改变传进来指针指向的内容，所以需要二级指针来接收。一般规律是想改变某变量的值，传参时就需要传该变量的地址。

首先断言二级指针pphead不为空，因为它指向一级指针phead的地址，phead地址一定存在，但指向的内容可能为空。
头结点本来为空，第一次插入让push的节点作为头结点，后续插入正常即可。

尾删SLTPopBack

在这里插入图片描述

因为在链表中删除空指针没有意义，所以要进行两次断言。箭头操作符优先级高于*，因为pphead为二级指针，所以要先使用（）解引用。

找尾中新建立tail变量，用它来遍历，防止程序后面还需要找到头指针位置却发现位置改变了，这样更加合理高效。

  • 错误辨析

在这里插入图片描述
在这里插入图片描述
此处tail是局部变量，并没有将前一个节点的next置空，需要用一个结构体指针来，所以这就造成了前一个节点非法访问的问题。

头插SLTPushFront

在这里插入图片描述
在这里插入图片描述
注意最后两句的顺序、传参、断言

头删SLTPopFront

在这里插入图片描述
在这里插入图片描述
通过画图清晰的知道一个节点和多节点情况都符合条件，巧妙创建first指针来进行改变节点指向。

查找具体节点SLTFind

在这里插入图片描述
还是通过创建临时变量cur来遍历寻找存放数据对应相等的节点，并返回该指针

pos位置后插入SLTInsertAfter

在这里插入图片描述
直接创建一个newnode节点，知道pos位置节点就可以直接进行赋值，不需要额外遍历。

  • pos之前插入（对比）

在这里插入图片描述
这种方式传参数量更多，代码量更大，同时运气不好还需要额外创建变量来遍历，找到pos前位置，时间复杂度和空间复杂度都相对于pos后插入低效。不推荐

pos位置后删除SLTEraseAfter

在这里插入图片描述
需注意pos下一个节点不为空，避免非法访问，通过创建del指针来改变节点链接和删除。

  • pos位置删除（对比）

在这里插入图片描述
相对于pos位置后删除，这里传参更多，头指针不等于pos时，需要创建临时变量来遍历得到pos前一个节点，时间复杂度效率更低，不推荐。

打印节点SLTPrint

在这里插入图片描述
不改变头指针位置，通过创建临时变量来遍历打印各节点中数据。

销毁链表SLTDestroy

在这里插入图片描述
free一个节点空间后将指针指向下一个被销毁的节点，当销毁到最后一个节点时，free之后用*pphead置空(cur是临时变量)

整体代码

  • SLlist.h
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

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);
//pos之前插入
void SLTInsert(SLTNode** pphead,SLTNode*pos, SLTDataType x);
//pos位置删除
void SLTErase(SLTNode** pphead,SLTNode*pos);
//pos后面插入
void SLTInsertAfter(SLTNode*pos, SLTDataType x);
//pos位置后面删除
void SLTEraseAfter(SLTNode*pphead);
//销毁链表
void SLTDestroy(SLTNode** pphead);
  • SLlist.c
#include"SLlist.h"

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

//创建节点(独立于链表外，后续链接)
SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	return;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	//链表中只有一个节点情况
	//有多个节点情况
	if ((*pphead)->next == NULL)//注意优先级
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找尾
		SLTNode* tail = *pphead;
		while (tail->next->next!=NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}

//查找具体节点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//pos之前插入
void SLTInsert(SLTNode** pphead,SLTNode*pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	if (*pphead== pos)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		//找到pos前的一个位置
		SLTNode* prev = *pphead;
		while (prev->next!=pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

//pos位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		//找到pos前一个位置
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		//pos=NULL;改变无效，因为形参是实参
		//的一份拷贝，想要改变pos指针要传递pos
		//地址，也就是用二级指针来接收
	}
}

//pos后面插入
void SLTInsertAfter(SLTDataType x, SLTNode* pos)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

//pos位置后删除
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* del = pos->next;
	pos->next=del->next;
	free(del);
	del = NULL;
}

//销毁链表
void SLTDestroy(SLTNode** pphead)
{
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead=NULL;
}
  • test.c
#include"SLlist.h"
void Testlist1()
{
	//尾插
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
}

void Testlist2()
{
	//头插
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);
}

void Testlist3()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	//头删和尾删
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
}

void Testlist4()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	//查找,值为2的节点乘以2
	SLTNode* ret = SLTFind(plist, 2);
	ret->data *= 2;
	SLTPrint(plist);
}

void Testlist5()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	
	SLTNode* ret = SLTFind(plist, 2);
	//利用选择插入接口
	SLTInsert(&plist, ret, 20);
	SLTPrint(plist);
}

void Testlist6()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTNode* ret = SLTFind(plist, 2);
	//利用选择删除接口
	SLTErase(&plist, ret);
	ret = NULL;
	SLTPrint(plist);
	SLTDestroy(&plist);
	SLTPrint(plist);
}

int main()
{
	/*Testlist1();
	Testlist2();
	Testlist3();
	Testlist4();
	Testlist5();*/
	Testlist6();

	return 0;
}

结语

  • 创作不易，感谢大家支持，希望对大家有所帮助。
    请添加图片描述
# 数据结构 # c语言
Logo
乐奇 Rokid 开放社区

更多推荐

cover

AR 智能眼镜并不是简单地在眼前放一块屏幕，而是把**摄像头、传感器、计算机视觉、空间定位、语音交互和云端服务**连接起来

avatar 乐奇 Rokid 开放社区
cover

让界面替我“摇“一次：一个AR祈愿智能体的AIUI实践

avatar 乐奇 Rokid 开放社区
cover

35轮对话，做出一款AI眼镜应用：我的「功德+1」开发实录——用 Rokid AIUI Studio，让一个小小的善意变成真正可用的应用

avatar 乐奇 Rokid 开放社区