前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >【海贼王的数据航海】链表—单链表

【海贼王的数据航海】链表—单链表

作者头像
枫叶丹
发布于 2024-06-04 12:20:05
690
发布于 2024-06-04 12:20:05
举报
文章被收录于专栏：C++

1 -> 链表

1.1 -> 链表的概念及结构

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

现实中 数据结构中

注意：

  1. 上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续；
  2. 现实中的结点一般都是从堆上申请出来的；
  3. 从堆上申请的空间，是按照一定策略分配的，两次申请的空间可能连续，也可能不连续。

假设在32位系统上，结点中值域为int类型，则一个节点的大小为8个字节，则也可能有以下链表：

1.2 -> 链表的分类

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

1. 单向或双向

2. 带头或不带头

3. 循环或非循环

虽然有很多链表结构，但最常用的还是这两种：

1. 无头单向非循环链表

2. 带头双向循环链表

1. 无头单向非循环链表：结构简单，一般不会单独用来存储数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

2 -> 无头+单向+非循环链表(单链表)

2.1 -> 接口声明

代码语言：javascript
复制
#pragma once

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

// 无头+单向+非循环链表增删查改实现
typedef int SLTDateType;

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

// 动态申请一个结点
SLTNode* BuySLTNode(SLTDateType x);

// 单链表打印
void SLTPrint(SLTNode* phead);

// 单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x);

// 单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDateType x);

// 单链表的尾删
void SLTPopBack(SLTNode** pphead);

// 单链表头删
void SLTPopFront(SLTNode** pphead);

// 单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDateType x);

// 单链表在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);

// 单链表在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDateType x);

// 单链表删除pos位置的值
void SLTErase(SLTNode** pphead, SLTNode* pos);

// 单链表删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos);

2.2 -> 接口实现

2.2.1 -> 动态申请一个结点
代码语言：javascript
复制
// 动态申请一个结点
SLTNode* BuySLTNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}
2.2.2 -> 单链表的打印
代码语言：javascript
复制
// 单链表的打印
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}

	printf("NULL\n");
}
2.2.3 -> 单链表的尾插
代码语言：javascript
复制
// 单链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL)
	{
		 *pphead = newnode;
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}
代码语言：javascript
复制
// 尾插测试
void SLTTest1()
{
	SLTNode* plist = NULL;

	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);

	SLTPrint(plist);
}
2.2.4 -> 单链表的头插
代码语言：javascript
复制
// 单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);

	newnode->next = *pphead;
	*pphead = newnode;
}
代码语言：javascript
复制
// 头插测试
void SLTTest2()
{
	SLTNode* plist = NULL;

	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);

	SLTPrint(plist);
}
2.2.5 -> 单链表的尾删
代码语言：javascript
复制
// 单链表的尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead); // 暴力检查

	 温柔的检查
	//if (*pphead == NULL)
	//{
	//	return;
	//}

	// 只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	// 有多个节点
	else
	{
		SLTNode* prev = *pphead;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}

		free(tail);
		tail = NULL;

		prev->next = NULL;
	}
}
代码语言：javascript
复制
// 尾删测试
void SLTTest3()
{
	SLTNode* plist = NULL;

	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
}
2.2.6 -> 单链表的头删
代码语言：javascript
复制
// 单链表的头删
void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead);
	SLTNode* tail = *pphead;

	*pphead = (*pphead)->next;
	free(tail);
	tail = NULL;
}
代码语言：javascript
复制
// 头删测试
void SLTTest4()
{
	SLTNode* plist = NULL;

	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
}
2.2.7 -> 单链表的查找
代码语言：javascript
复制
// 单链表的查找
SLTNode* SLTFind(SLTNode* phead, SLTDateType x)
{
	SLTNode* ptr = phead;
	while (ptr->next != NULL)
	{
		if (ptr->data == x)
		{
			return ptr;
		}
		else
		{
			ptr = ptr->next;
		}
	}

	return NULL;
}
代码语言：javascript
复制
// 查找测试
void SLTTest5()
{
	SLTNode* plist = NULL;

	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTNode* ans = SLTFind(plist, 1);
	if (ans)
		ans->data = 10;
	SLTPrint(plist);
}
2.2.8 -> 单链表在pos位置之前插入x
代码语言：javascript
复制
// 单链表在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* newnode = BuySLTNode(x);
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = newnode;
		newnode->next = pos;
	}
}
代码语言：javascript
复制
// 在pos位置之前插入x测试
void SLTTest6()
{
	SLTNode* plist = NULL;

	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTNode* pos = SLTFind(plist, 2);
	if (pos)
		SLTInsert(&plist, pos, 99);
	SLTPrint(plist);
}
2.2.9 -> 单链表在pos位置之后插入x
代码语言：javascript
复制
// 单链表在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	SLTNode* tmp = pos->next;

	pos->next = newnode;
	newnode->next = tmp;
}
代码语言：javascript
复制
// 在pos位置之后插入x测试
void SLTTest7()
{
	SLTNode* plist = NULL;

	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTNode* pos = SLTFind(plist, 2);
	if (pos)
		SLTInsertAfter(pos, 99);
	SLTPrint(plist);
}
2.2.10 -> 单链表删除pos位置的值
代码语言：javascript
复制
// 单链表删除pos位置的值
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		if (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
代码语言：javascript
复制
// 删除pos位置的值测试
void SLTTest8()
{
	SLTNode* plist = NULL;

	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTNode* pos = SLTFind(plist, 2);
	if (pos)
		SLTErase(&plist, pos);
	SLTPrint(plist);
}
2.2.11 -> 单链表删除pos位置之后的值
代码语言：javascript
复制
// 单链表删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* tmp = pos->next->next;

	free(pos->next);
	pos->next = tmp;
}
代码语言：javascript
复制
// 删除pos位置之后的值测试
void SLTTest9()
{
	SLTNode* plist = NULL;

	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTNode* pos = SLTFind(plist, 2);
	if (pos)
		SLTEraseAfter(pos);
	SLTPrint(plist);
}

2.3 -> 完整代码

2.3.1 -> SList.h
代码语言：javascript
复制
#pragma once

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

// 无头+单向+非循环链表增删查改实现
typedef int SLTDateType;

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

// 动态申请一个结点
SLTNode* BuySLTNode(SLTDateType x);

// 单链表打印
void SLTPrint(SLTNode* phead);

// 单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x);

// 单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDateType x);

// 单链表的尾删
void SLTPopBack(SLTNode** pphead);

// 单链表头删
void SLTPopFront(SLTNode** pphead);

// 单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDateType x);

// 单链表在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);

// 单链表在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDateType x);

// 单链表删除pos位置的值
void SLTErase(SLTNode** pphead, SLTNode* pos);

// 单链表删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos);
2.3.2 -> SList.c
代码语言：javascript
复制
#include "SList.h"

// 动态申请一个结点
SLTNode* BuySLTNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

// 单链表的打印
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}

	printf("NULL\n");
}

// 单链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL)
	{
		 *pphead = newnode;
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}

// 单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);

	newnode->next = *pphead;
	*pphead = newnode;
}

// 单链表的尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead); // 暴力检查

	 温柔的检查
	//if (*pphead == NULL)
	//{
	//	return;
	//}

	// 只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	// 有多个节点
	else
	{
		SLTNode* prev = *pphead;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}

		free(tail);
		tail = NULL;

		prev->next = NULL;
	}
}

// 单链表的头删
void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead);
	SLTNode* tail = *pphead;

	*pphead = (*pphead)->next;
	free(tail);
	tail = NULL;
}

// 单链表的查找
SLTNode* SLTFind(SLTNode* phead, SLTDateType x)
{
	SLTNode* ptr = phead;
	while (ptr->next != NULL)
	{
		if (ptr->data == x)
		{
			return ptr;
		}
		else
		{
			ptr = ptr->next;
		}
	}

	return NULL;
}

// 单链表在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* newnode = BuySLTNode(x);
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = newnode;
		newnode->next = pos;
	}
}

// 单链表在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	SLTNode* tmp = pos->next;

	pos->next = newnode;
	newnode->next = tmp;
}

// 单链表删除pos位置的值
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		if (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

// 单链表删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* tmp = pos->next->next;

	free(pos->next);
	pos->next = tmp;
}
2.3.3 -> Test.c
代码语言：javascript
复制
#include "SList.h"

// 尾插测试
void SLTTest1()
{
	SLTNode* plist = NULL;

	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);

	SLTPrint(plist);
}

// 头插测试
void SLTTest2()
{
	SLTNode* plist = NULL;

	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);

	SLTPrint(plist);
}

// 尾删测试
void SLTTest3()
{
	SLTNode* plist = NULL;

	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
}

// 头删测试
void SLTTest4()
{
	SLTNode* plist = NULL;

	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
}

// 查找测试
void SLTTest5()
{
	SLTNode* plist = NULL;

	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTNode* ans = SLTFind(plist, 1);
	if (ans)
		ans->data = 10;
	SLTPrint(plist);
}

// 在pos位置之前插入x测试
void SLTTest6()
{
	SLTNode* plist = NULL;

	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTNode* pos = SLTFind(plist, 2);
	if (pos)
		SLTInsert(&plist, pos, 99);
	SLTPrint(plist);
}

// 在pos位置之后插入x测试
void SLTTest7()
{
	SLTNode* plist = NULL;

	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTNode* pos = SLTFind(plist, 2);
	if (pos)
		SLTInsertAfter(pos, 99);
	SLTPrint(plist);
}

// 删除pos位置的值测试
void SLTTest8()
{
	SLTNode* plist = NULL;

	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTNode* pos = SLTFind(plist, 2);
	if (pos)
		SLTErase(&plist, pos);
	SLTPrint(plist);
}

// 删除pos位置之后的值测试
void SLTTest9()
{
	SLTNode* plist = NULL;

	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTNode* pos = SLTFind(plist, 2);
	if (pos)
		SLTEraseAfter(pos);
	SLTPrint(plist);
}

int main()
{



	return 0;
}

感谢大佬们的支持！！！

互三啦！！！

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-03-13，如有侵权请联系 cloudcommunity@tencent.com 删除
void
测试
链表
数据
plist

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

void
测试
链表
数据
plist
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 1 -> 链表
    • 1.1 -> 链表的概念及结构
      • 1.2 -> 链表的分类
      • 2 -> 无头+单向+非循环链表(单链表)
        • 2.1 -> 接口声明
          • 2.2 -> 接口实现
            • 2.2.1 -> 动态申请一个结点
            • 2.2.2 -> 单链表的打印
            • 2.2.3 -> 单链表的尾插
            • 2.2.4 -> 单链表的头插
            • 2.2.5 -> 单链表的尾删
            • 2.2.6 -> 单链表的头删
            • 2.2.7 -> 单链表的查找
            • 2.2.8 -> 单链表在pos位置之前插入x
            • 2.2.9 -> 单链表在pos位置之后插入x
            • 2.2.10 -> 单链表删除pos位置的值
            • 2.2.11 -> 单链表删除pos位置之后的值
          • 2.3 -> 完整代码
            • 2.3.1 -> SList.h
            • 2.3.2 -> SList.c
            • 2.3.3 -> Test.c
        相关产品与服务
        腾讯云服务器利旧
        云服务器（Cloud Virtual Machine，CVM）提供安全可靠的弹性计算服务。 您可以实时扩展或缩减计算资源，适应变化的业务需求，并只需按实际使用的资源计费。使用 CVM 可以极大降低您的软硬件采购成本，简化 IT 运维工作。
        产品介绍
        11.11 上云拼团GO
        领券

        腾讯云开发者

        扫码关注腾讯云开发者

        扫码关注腾讯云开发者

        领取腾讯云代金券

        热门产品

        热门推荐

        更多推荐

        Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

        深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

        腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

        Copyright © 2013 - 2024 Tencent Cloud.

        All Rights Reserved. 腾讯云 版权所有

        登录 后参与评论