1. AI技术聚合首页
  2. IT

数据结构之单链表及其实现！

青葱年少 • • IT • 阅读 80

目录

                                            悟已往之不谏，知来者犹可追  

创作不易，宝子们！如果这篇文章对你们有帮助的话，别忘了给个免费的赞哟

1.  顺序表的问题及思考

问题：

1. 中间/头部的插入删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？下面给出了链表的结构来看看。

2.链表的概念结构和分类

2.1 概念及结构

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

2.2 分类

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

1. 单项或者双向

 2. 带头或者不带头

 3. 循环或者非循环

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

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

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

下面我就来实现一下无头单向非循环链表~

3. 单链表的实现

这里我就具体实现一下接口~（SList.h)

#define _CRT_SECURE_NO_WARNINGS
#pragma once//避免头文件被多次引用
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SListDataType;//便于改变数据类型

//定义一个结构体类型的节点
typedef struct SListNode
{
	SListDataType data;
	struct SListNode* next;//存储下一个节点的地址
}SListNode;

//1. 新节点的创建
SListNode* SListCreatNode(SListDataType x);

//2. 打印单链表
void PrintSList(SListNode* phead);

//3. 头插
void SListPushFront(SListNode** phead, SListDataType x);

//4. 头删
void  SListPopFront(SListNode** phead);

//5. 尾差
void SListPushBack(SListNode** phead, SListDataType x);

//6. 尾删
void  SListPopBack(SListNode** phead);

//7. 查找元素X
SListNode* SListFind(SListNode* phead, SListDataType x);

//8. 在pos位置修改
void SListModify(SListNode* pos, SListDataType x);

//9. 在任意位置之前插入
void SListInsert(SListNode** phead, SListNode* pos, SListDataType x);

//10. 在任意位置删除
void SListErase(SListNode** phead, SListNode* pos);

//11. 销毁单链表
void SListDestroy(SListNode** phead);

3.1 新节点的创建

(1)代码实现

//1. 新节点的创建
SListNode*  SListCreatNode(SListDataType x)
{
	SListNode* NewNode= (SListNode*)malloc(sizeof(SListNode));//开辟空间
	if (NewNode == NULL)//判断空间是否开辟成功
	{
		perror("malloc fail");
		return NULL;
	}
	NewNode->data = x;//赋值
	NewNode->next = NULL;//置空
	return NewNode;
}

3.2 打印单链表

(1)代码实现

//2. 打印单链表
void PrintSList(SListNode* phead)
{
	if (phead == NULL)
	{
		printf("NULL");//如果链表没有元素就打印NULL
		return;
	}
	SListNode* cur = phead;
	//循环单链表打印
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

(2) 复杂度分析

  • 时间复杂度：因为需要遍历整个链表，显然时间复杂度为O(N)。
  • 空间复杂度：打印链表不需要格外的空间，所以空间复杂度为O(1).

3.3 头插

(1)代码实现

//3. 头插
void SListPushFront(SListNode** phead, SListDataType x)
{
	assert(phead);
	SListNode* newnode =SListCreatNode(x);//创建一个新节点
	newnode->next =*phead;
	*phead = newnode;
}

(2) 复杂度分析

  • 时间复杂度：不需要额外时间的消耗，时间复杂度为O(1)。
  • 空间复杂度：固定创造一个节点，空间复杂度为O(1)。

3.4 头删

(1)代码实现

//4. 头删
void  SListPopFront(SListNode** phead)
{
	assert(phead);
	assert(*phead);//如果没有数据就不用头删，并报错
	SListNode* cur = (*phead)->next;
	free(*phead);
	*phead = cur;
}

(2) 复杂度分析

  • 时间复杂度：不需要额外时间的消耗，时间复杂度为O(1)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.5 尾插

(1)代码实现

//5. 尾插
void SListPushBack(SListNode** phead, SListDataType x)
{
	assert(phead);
	if (*phead == NULL)
	{
		*phead = SListCreatNode(x);//创建新节点并插入
	}
	else
	{
		SListNode* tail = *phead;
		while (tail->next != NULL)//找到尾节点
		{
			tail = tail->next;
		}
		tail->next = SListCreatNode(x);//创建新节点并插入
	}
}

(2) 复杂度分析

  • 时间复杂度：需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：固定创造一个节点，空间复杂度为O(1)。

3.6 尾删

(1)代码实现

//6. 尾删
void  SListPopBack(SListNode** phead)
{
	assert(phead);
	assert(*phead);//链表为空就不进行尾删
	SListNode* tail = *phead;
	if (tail->next == NULL)//如果链表就只有一个元素就进行头删
	{
		SListPopFront(phead);
	}
	else
	{
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

(2) 复杂度分析

  • 时间复杂度：需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.7 查找元素X

(1)代码实现

//7. 查找元素X
SListNode* SListFind(SListNode* phead, SListDataType x)
{
	assert(phead);
	while (phead->next!=NULL)//注意最后一个节点是没有查找的
	{
		if (phead->data == x)
			return phead;
			phead = phead->next;
	}
	if (phead->data == x)
		return phead;//最后一个节点没有查找
	else
	return NULL;//没找到
}

(2) 时间复杂度

  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.8 在pos位置修改

(1)代码实现


//8. 在pos位置修改
void SListModify( SListNode* pos, SListDataType x)
{
	assert(pos);
	pos->data = x;
}

(2) 时间复杂度

  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.9 在任意位置之前插入

(1)代码实现

//9. 在任意位置之前插入
void SListInsert(SListNode** phead, SListNode* pos, SListDataType x)
{
	assert(phead);
	assert(*phead);
	if (pos==*phead)//如果pos位置刚好是第一个节点就进行头插
	{
		SListPushFront( phead,x);
	}
	else
	{
		SListNode* newnode = SListCreatNode(x);
		SListNode* cur = *phead;
		while (cur->next != pos)//找到pos前一个节点
		{
			cur = cur->next;
		}
		cur->next = newnode;
		newnode->next  = pos;
	}
}

(2) 复杂度分析

  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.10 在任意位置删除

(1)代码实现

//10. 在任意位置删除
void SListErase(SListNode** phead, SListNode* pos)
{
	assert(phead && *phead && pos);
	if (pos==*phead)//如果pos位置就是第一个节点就进行头删
	{
		SListPopFront(phead);
	}
	else
	{
		SListNode* cur = *phead;
		while (cur->next != pos)//找到pos前一个节点
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
	}
}

(2) 复杂度分析

  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.11 单链表的销毁

(1)代码实现

//11. 销毁单链表
void SListDestroy(SListNode** phead)
{
	assert(*phead && phead);
	SListNode* cur = *phead;
	while (cur!= NULL)
	{
		SListNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	*phead = NULL;
}

(2) 复杂度分析

  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

4. 完整代码

SList.c

#define _CRT_SECURE_NO_WARNINGS

#include"SList.h"

//1. 新节点的创建
SListNode*  SListCreatNode(SListDataType x)
{
	SListNode* NewNode= (SListNode*)malloc(sizeof(SListNode));//开辟空间
	if (NewNode == NULL)//判断空间是否开辟成功
	{
		perror("malloc fail");
		return NULL;
	}
	NewNode->data = x;//赋值
	NewNode->next = NULL;//置空
	return NewNode;
}

//2. 打印单链表
void PrintSList(SListNode* phead)
{
	if (phead == NULL)
	{
		printf("NULL");//如果链表没有元素就打印NULL
		return;
	}
	SListNode* cur = phead;
	//循环单链表打印
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

//3. 头插
void SListPushFront(SListNode** phead, SListDataType x)
{
	assert(phead);
	SListNode* newnode =SListCreatNode(x);//创建一个新节点
	newnode->next =*phead;
	*phead = newnode;
}

//4. 头删
void  SListPopFront(SListNode** phead)
{
	assert(phead);
	assert(*phead);//如果没有数据就不用头删，并报错
	SListNode* cur = (*phead)->next;
	free(*phead);
	*phead = cur;
}

//5. 尾插
void SListPushBack(SListNode** phead, SListDataType x)
{
	assert(phead);
	if (*phead == NULL)
	{
		*phead = SListCreatNode(x);//创建新节点并插入
	}
	else
	{
		SListNode* tail = *phead;
		while (tail->next != NULL)//找到尾节点
		{
			tail = tail->next;
		}
		tail->next = SListCreatNode(x);//创建新节点并插入
	}
}

//6. 尾删
void  SListPopBack(SListNode** phead)
{
	assert(phead);
	assert(*phead);//链表为空就不进行尾删
	SListNode* tail = *phead;
	if (tail->next == NULL)//如果链表就只有一个元素就进行头删
	{
		SListPopFront(phead);
	}
	else
	{
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

//7. 查找元素X
SListNode* SListFind(SListNode* phead, SListDataType x)
{
	assert(phead);
	while (phead->next!=NULL)//注意最后一个节点是没有查找的
	{
		if (phead->data == x)
			return phead;
			phead = phead->next;
	}
	if (phead->data == x)
		return phead;//最后一个节点没有查找
	else
	return NULL;//没找到
}

//8. 在pos位置修改
void SListModify( SListNode* pos, SListDataType x)
{
	assert(pos);
	pos->data = x;
}

//9. 在任意位置之前插入
void SListInsert(SListNode** phead, SListNode* pos, SListDataType x)
{
	assert(phead);
	assert(*phead);
	if (pos==*phead)//如果pos位置刚好是第一个节点就进行头插
	{
		SListPushFront( phead,x);
	}
	else
	{
		SListNode* newnode = SListCreatNode(x);
		SListNode* cur = *phead;
		while (cur->next != pos)//找到pos前一个节点
		{
			cur = cur->next;
		}
		cur->next = newnode;
		newnode->next  = pos;
	}
}

//10. 在任意位置删除
void SListErase(SListNode** phead, SListNode* pos)
{
	assert(phead && *phead && pos);
	if (pos==*phead)//如果pos位置就是第一个节点就进行头删
	{
		SListPopFront(phead);
	}
	else
	{
		SListNode* cur = *phead;
		while (cur->next != pos)//找到pos前一个节点
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
	}
}

//11. 销毁单链表
void SListDestroy(SListNode** phead)
{
	assert(*phead && phead);
	SListNode* cur = *phead;
	while (cur!= NULL)
	{
		SListNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	*phead = NULL;
}

5. 完结散花

好了，这期的分享到这里就结束了~

如果这篇博客对你有帮助的话，可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话，可以点点关注，避免找不到我了呢~

我们下期不见不散~~

版权声明：本文为博主作者：秋风起，再归来～原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/2301_80221228/article/details/136599893

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
青葱年少的头像青葱年少普通用户
0
上一篇 2024年4月1日
下一篇 2024年4月1日

相关推荐

此站出售，如需请站内私信或者邮箱！