没有头结点的单链表

绝活蛋炒饭

发布于 2024-12-16 07:43:40

5900

代码可运行

文章被收录于专栏：绝活编程学习绝活编程学习

运行总次数：0

代码可运行

0.引言

这段代码定义了一个单链表及其相关操作，主要包括以下功能：

1. 定义单链表的数据类型和结点结构；

2. 动态申请内存创建链表结点；

3. 实现单链表的插入、删除、查找等基本操作；

4. 使用头插和尾插法动态调整链表；

5. 打印单链表；

6. 在指定位置之后插入元素；

7. 删除指定位置之后的元素。

通过这些操作，代码展示了如何使用单链表进行数据存储和操作。在实际应用中，可以根据需求进一步扩展和完善链表的操作功能。

1.节点的定义

typedef int SLTDateType; // 定义单链表的数据类型

typedef struct SListNode // 定义单链表的结点结构
{
	SLTDateType data; // 数据域
	struct SListNode* next; // 指针域，指向下一个结点
}SListNode;

2.动态申请一个结点

// 动态申请一个结点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); // 分配内存空间

	if (newnode == NULL) // 检查内存分配是否成功
	{
		perror("malloc");
	}

	newnode->data = x; // 初始化数据域
	newnode->next = NULL; // 初始化指针域

	return newnode; // 返回新结点的地址
}

3.单链表打印

// 单链表打印
void SListPrint(SListNode* plist)
{
	while (plist != NULL)
	{
		printf("%d->", plist->data); // 打印当前结点的数据
		plist = plist->next; // 移动到下一个结点
	}
	printf("NULL"); // 打印链表结束标志
}

4.单链表尾插

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x); // 创建新结点

	if ((*pplist) == NULL) // 如果链表为空
	{
		*pplist = newnode; // 新结点成为头结点
	}
	else // 如果链表非空
	{
		SListNode* cur = (*pplist);
		while (cur->next) // 找到链表的最后一个结点
		{
			cur = cur->next;
		}
		cur->next = newnode; // 将新结点接在最后一个结点之后
	}
}

5.单链表的头插

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x); // 创建新结点

	if ((*pplist) == NULL) // 如果链表为空
	{
		*pplist = newnode; // 新结点成为头结点
	}
	else // 如果链表非空
	{
		newnode->next = (*pplist); // 将头结点连接在新结点之后
		(*pplist) = newnode; // 新结点成为新的头结点
	}
}

6.单链表的尾删

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(*pplist); // 检查链表非空

	SListNode* cur = *pplist;

	while (((cur->next)->next) != NULL) // 找到倒数第二个结点
	{
		cur = cur->next;
	}

	SListNode* cur1 = cur->next; // 记录最后一个结点的地址
	cur->next = NULL; // 倒数第二个结点的next指针置空
	free(cur1); // 释放最后一个结点的内存
	cur1 = NULL; // 防止产生野指针
}

7.单链表头删

// 单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(*pplist); // 检查链表非空

	SListNode* cur = *pplist; // 保存头结点的地址
	*pplist = cur->next; // 头结点指向下一个结点
	free(cur); // 释放原头结点的内存
	cur = NULL; // 防止产生野指针
}

8.单链表查找

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	while (plist) // 遍历链表
	{
		if (plist->data == x) // 找到目标值
		{
			return plist; // 返回找到的结点的地址
		}
		else // 继续搜索下一个结点
		{
			plist = plist->next;
		}
	}
}

9.单链表在pos位置之后插入x

// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x); // 创建新结点
	newnode->next = pos->next; // 将新结点连接到pos结点之后
	pos->next = newnode; // 将pos结点的next指针指向新结点
}

10.单链表删除pos位置之后的值

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	if (pos->next == NULL) // 判断pos位置之后是否有结点
	{
		printf("pos位置后没有值");
	}
	else // 如果有结点
	{
		SListNode* cur = pos->next; // 保存要删除的结点的地址
		pos->next = cur->next; // 将pos结点的next指针跳过要删除的结点
		free(cur); // 释放要删除的结点的内存
		cur = NULL; // 防止产生野指针
	}
}