1. Toy模板网首页
  2. > Toy博客

【数据结构初阶】单链表（附全部码源）

8月前 作者：hallelujah... 分类：Toy博客 阅读(31) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构初阶】单链表（附全部码源）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1，单链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
【数据结构初阶】单链表（附全部码源）,数据结构,链表,数据结构,算法,c语言
【数据结构初阶】单链表（附全部码源）,数据结构,链表,数据结构,算法,c语言
现实中 数据结构中
【数据结构初阶】单链表（附全部码源）,数据结构,链表,数据结构,算法,c语言

2，单链表的实现

2.1初始化内容（所需文件，接口）

所需文件

头文件->SLTNode.h
源文件->test.c
源文件->SLTNode.c

接口（SList.h中）

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

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType date;
	struct SListNode* next;
}SLTNode;

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

//创造结点
SLTNode* BuySListNode(SLTDateType x);

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

//头插
void SLTPushFront(SLTNode** pphead, SLTDateType x);

//尾删
void SLTPopBack(SLTNode** pphead);

//头删
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* FindSLTNode(SLTNode* phead, SLTNode* pos);

//pos位置插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);

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

//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);

//删除pos位置下一个
void SLTEraseAfter(SLTNode* pos);

//销毁单链表
void SLTDestroy(SLTNode* phead);

2.2申请结点

//创造结点
SLTNode* BuySListNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->date = x;
	newnode->next = NULL;
	return newnode;
}

2.3打印单链表

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

2.4尾插

//尾插
//尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
	SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while(tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

2.5头插

头插显然是要改变头指针存放的地址，因此形参也需要传递二级指针。头插无需单独考虑空链表的情况
【数据结构初阶】单链表（附全部码源）,数据结构,链表,数据结构,算法,c语言

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

2.6尾删

尾删先要遍历一遍链表找到最后一个节点将其释放掉，还要找到倒数第二个节点将它的指针域中存的地址改为NULL。所以定义两个指针让他们同时去遍历链表，一个找尾，另一个找倒数第二个节点。需要注意的是空链表和只有一个节点的链表的情况，空链表无法进行尾删，而只有一个节点的链表在尾删后会变成一个空链表，这意味着要改变头指针里面存放的地址，所以尾删形参也要传递二级指针。
【数据结构初阶】单链表（附全部码源）,数据结构,链表,数据结构,算法,c语言

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);

	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tailPrev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tailPrev = tail;
			tail = tail->next;
		}
		free(tail);
		tailPrev->next = NULL;
		/*SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;*/
	}
}

2.7头删

头删很明显需要改变头指针中存放的地址，所以形参仍然需要传递二级指针。头删只需要注意链表是否为空，空链表无法进行删除。此外在进行头删的时候记得将原来的头节点释放掉，因此在改变头节点之前需要先保留原来头结点的地址，否则在更换完新的头节点后就找不到原来的头节点了。
【数据结构初阶】单链表（附全部码源）,数据结构,链表,数据结构,算法,c语言

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);

	assert(*pphead);

	SLTNode* newnode = (*pphead)->next;
	free(*pphead);
	*pphead = newnode;
}

2.8查找

其实就是遍历一遍链表，但是只能返回第一次出现的地址。查找可以当修改来使用，我们查找到节点的地址后就可以通过地址去修改数据域中存储的数据。

//查找
SLTNode* FindSLTNode(SLTNode* phead, SLTDateType x)
{
	
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->date == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

2.9在pos位置之后插入

先让newnode的指针域存储pos后一个节点的地址，再让pos的指针域存newnode的地址

【数据结构初阶】单链表（附全部码源）,数据结构,链表,数据结构,算法,c语言

//在pos位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;

	//err 死循环
	//pos->next = newnode;
	//newnode->next = pos->next;
}

2.10在pos位置前面插入

和尾插类似，但此时只需要遍历链表找到pos位置的前一个节点即可，同样需要注意pos是头结点的情况，此时就成头插了，需要改变头指针中存的地址，因此函数的形参需要传二级指针。
【数据结构初阶】单链表（附全部码源）,数据结构,链表,数据结构,算法,c语言

//在pos位置插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(*pphead);
	assert(pos);

	if (*pphead == pos)
	{
		//头插
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

2.11删除pos之后的值

注意不能写成后面这样：pos->next = pos->next->next。这样写虽然把pos位置后面的节点从链表中剔除出去了，但并没有真正意义上的实现删除，因为每一个节点都是通过malloc在堆上申请的，不使用的时候要主动的去释放掉，也就是free掉，把这块空间归还给操作系统，否则会导致内存泄漏。而上面那样写，就会导致pos后面的节点丢失，无法进行释放，正确的做法是在执行这条语句之前把pos后边节点的地址先保存起来。
 【数据结构初阶】单链表（附全部码源）,数据结构,链表,数据结构,算法,c语言

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	//检查pos是不是尾结点
	assert(pos->next);

	SLTNode* posNext = pos->next;

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

2.12删除pos位置的值

pos可能是头结点的地址，因此形参要用二级指针。
【数据结构初阶】单链表（附全部码源）,数据结构,链表,数据结构,算法,c语言

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);

	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

2.13销毁链表

void SListDestroy(SLTNode* plist)
{
	assert(plist);
	SLTNode* cur = plist;
	while (cur)
	{
		SLTNode* pur = cur;
		cur = cur->next;
		free(pur);
	}
}

3.全部码源

SLTNode.c

#include"SLTNode.h"

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

//创造结点
SLTNode* BuySListNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->date = x;
	newnode->next = NULL;
	return newnode;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
	SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while(tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

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

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);

	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tailPrev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tailPrev = tail;
			tail = tail->next;
		}
		free(tail);
		tailPrev->next = NULL;
		/*SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;*/
	}
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);

	assert(*pphead);

	SLTNode* newnode = (*pphead)->next;
	free(*pphead);
	*pphead = newnode;
}

//查找
SLTNode* FindSLTNode(SLTNode* phead, SLTDateType x)
{
	
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->date == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

//在pos位置插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(*pphead);
	assert(pos);

	if (*pphead == pos)
	{
		//头插
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

//在pos位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;

	//err 死循环
	//pos->next = newnode;
	//newnode->next = pos->next;
}

//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(*pphead);
	assert(pos);

	if (pos == *pphead)
	{
		SLTPopFront(*pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		//pos
	}
}

//删除pos下一个位置
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);

	//检查pos是不是尾结点
	assert(pos->next);

	SLTNode* posNext = pos->next;
	pos->next = posNext->next;
	free(posNext);
	posNext = NULL;
}

//销毁单链表
void SLTDestroy(SLTNode* phead)
{
	assert(phead);
	SLTNode* cur = phead;
	while (cur)
	{
		SLTNode* pur = cur;
		cur = cur->next;
		free(pur);
	}
}

SLTNode.h

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

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType date;
	struct SListNode* next;
}SLTNode;

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

//创造结点
SLTNode* BuySListNode(SLTDateType x);

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

//头插
void SLTPushFront(SLTNode** pphead, SLTDateType x);

//尾删
void SLTPopBack(SLTNode** pphead);

//头删
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* FindSLTNode(SLTNode* phead, SLTNode* pos);

//pos位置插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);

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

//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);

//删除pos位置下一个
void SLTEraseAfter(SLTNode* pos);

//销毁单链表
void SLTDestroy(SLTNode* phead);

test.c

#include"SLTNode.h"

void SLTNodeTest1()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPrint(plist);
	SLTPushBack(&plist, 2);
	SLTPrint(plist);
	SLTPushBack(&plist, 3);
	SLTPrint(plist);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	SLTPushBack(&plist, 5);
	SLTPrint(plist);
	SLTPushBack(&plist, 6);
	SLTPrint(plist);
}

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

	SLTPushFront(&plist, 200);
	SLTPrint(plist);
}

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

	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);

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

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

	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);

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

	SLTNode* pos = FindSLTNode(plist, 3);
	SLTInsert(&plist, pos, 30);

	SLTPrint(plist);
}

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

	SLTNode* pos = FindSLTNode(plist, 3);
	SLTInsertAfter(pos, 30);

	SLTPrint(plist);
}

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

	SLTNode* pos = FindSLTNode(plist, 3);
	SLTErase(&plist, pos);

	SLTPrint(plist);
}

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

	SLTNode* pos = FindSLTNode(plist, 3);
	SLTEraseAfter(pos);

	SLTPrint(plist);
}


int main()
{
	SLTNodeTest8();
	return 0;
}

💘不知不觉，【数据结构初阶】单链表以告一段落。通读全文的你肯定收获满满，让我们继续为数据结构学习共同奋进!!!文章来源地址https://www.toymoban.com/news/detail-755139.html

到了这里，关于【数据结构初阶】单链表（附全部码源）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】- 链表之单链表(下)

    【数据结构】- 链表之单链表(下)

    未来藏在迷雾中 叫人看来胆怯 带你踏足其中 就会云开雾散 本章是关于数据结构中的链表之单链表(下) 提示：以下是本篇文章正文内容，下面案例可供参考 1.2.1 在pos位置插入(也就是pos位置之前) 流程图 多个节点 一个节点 1.2.2 在pos位置之后插入 流程图： 注意： 下面这种写

    2023年04月23日
    浏览(45)
  • [数据结构]链表之单链表（详解）

    [数据结构]链表之单链表（详解）

    在学习 链表 之前，我们已经学习了 顺序表 了 根据 顺序表 的特点，我们可以发现 顺序表 有优点，也有一些缺陷。 所以根据 顺序表 的缺点，链表就横空出世啦~ **概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次

    2023年04月08日
    浏览(39)
  • Leetcode刷题---C语言实现初阶数据结构---单链表

    Leetcode刷题---C语言实现初阶数据结构---单链表

    删除链表中等于给定值 val 的所有节点 给你一个链表的头节点head和一个整数val，请你删除链表中所有满足Node.val==val的节点，并返回新的头节点 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5] 示例 2： 输入：head = [ ], val = 1 输出：[ ] 示例 3： 输入：head = [7,7,7,7], val = 7 输出：

    2024年02月15日
    浏览(32)
  • ＜数据结构＞ 链表 - 单链表（c语言实现）

    ＜数据结构＞ 链表 - 单链表（c语言实现）

    哨兵位结点也叫哑节点。哨兵位结点 也是头结点 。该节点 不存储有效数据，只是为了方便操作 （如尾插时用带哨兵位的头结点很爽，不需要判空）。 有哨兵位结点的链表，第一个元素应该是链表第二个节点（head - next，head为哨兵位结点）对应的元素。 有哨兵位结点的链表

    2023年04月11日
    浏览(29)
  • 数据结构入门 — 链表详解_单链表

    数据结构入门 — 链表详解_单链表

    数据结构入门 — 单链表详解 * 博客主页链接：https://blog.csdn.net/m0_74014525 关注博主，后期持续更新系列文章 文章末尾有源码 *****感谢观看，希望对你有所帮助***** 第一篇：数据结构入门 — 链表详解_单链表 第二篇：数据结构入门 — 链表详解_双向链表 第三篇：数据结构入门

    2024年02月11日
    浏览(38)
  • 【数据结构】-- 单链表 vs 双向链表

    【数据结构】-- 单链表 vs 双向链表

    🌈 个人主页： 白子寰 🔥 分类专栏： python从入门到精通，魔法指针，进阶C++，C语言，C语言题集，C语言实现游戏 👈 希望得到您的订阅和支持~ 💡 坚持创作博文(平均质量分82+)，分享更多关于深度学习、C/C++，python领域的优质内容！（希望得到您的关注~）  目录  单链表和

    2024年04月17日
    浏览(28)
  • 初阶数据结构：链表

    初阶数据结构：链表

    经过学习与练习，已经掌握了顺序表的相关知识并且能够自我实现。在这一过程中，通过对其结构的实现，发现顺序表的尾部插入删除数据效率很高，可是，在 头部与随机插入的场景下效率低下 而且 存在扩容消耗 等一些问题。而有这样一种数据结构可以很好的解决顺序表存

    2024年01月20日
    浏览(30)
  • 【数据结构】反转链表、链表的中间节点、链表的回文结构（单链表OJ题）

    【数据结构】反转链表、链表的中间节点、链表的回文结构（单链表OJ题）

    正如标题所说，本文会图文详细解析三道单链表OJ题，分别为：  反转链表 （简单）  链表的中间节点 （简单）  链表的回文结构 （较难） 把他们放在一起讲的原因是：  反转链表 和  链表的中间节点 是  链表的回文结构 的基础 为什么这样说？请往下看： 目录 1. 反转链

    2024年02月13日
    浏览(39)
  • 初阶数据结构（三）链表

    初阶数据结构（三）链表

    💓博主csdn个人主页：小小unicorn💓 ⏩专栏分类：c++ 🚚代码仓库：小小unicorn的学习足迹🚚 🌹🌹🌹关注我带你学习编程知识 前面我们讲的线性表的 顺序存储结构 。它是有缺点的，最大的缺点就是插入和删除时需要移动大量元素，这显然就需要 耗费时间 ，那能不能想办法

    2024年02月09日
    浏览(41)
  • 【数据结构初阶】链表OJ

    【数据结构初阶】链表OJ

    OJ 方案一： 题目解析： 方案二： 题目解析：把原链表遍历一遍，插入新链表 OJ 题目解析： OJ 题目解析： OJ 题目解析： OJ 题目解析： OJ 题目解析： OJ 题目解析： OJ 题目解析： 定义快慢指针，使快指针先走与慢指针同步。然后同时走看是否相交 OJ 题目解析： OJ 题目解析：

    2024年02月05日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包