分享一篇由C语言实现《数据结构》无头无循环单链表

03-11 4215阅读 0评论

三月，你好，各位csdn uu们好

分享一篇由C语言实现《数据结构》无头无循环单链表 第1张

文章目录

  • 前言
  • 一、何为单链表
  • 二、单链表基本操作（增，删，查，改，销毁，遍历）
    • 1.查找与修改、销毁与遍历
    • 2.链表插入与删除操作
    • 三、单链表 VS 顺序表 且 全部 源码(SLNode.h ) (SLNode.c) ( test.c)

      前言

      由于上一篇博客顺序表的相关实现其基本操作中，它的查找效率很快，通过下标可以快速存取表中任意一个位置的元素，但是其插入和删除操作因为要移动大量的元素，造成效率极低，时间复杂度达到O（n)，那么能用上面结构来存储可以使其效率提高呢？因此在这里引入单链表，单链表的基本操作插入和删除效率喝高很高时间复杂度为O(n)，在以查找到节点的前提下.分享一篇由C语言实现《数据结构》无头无循环单链表 第2张

      一、何为单链表

      链表 是一种在物理上非连续、 非顺序的数据结构， 由若干 节点 所组成，一个节点连着一个节点。

      单链表顾名思义是链表的每一个节点又包含两部分， 一部分是存放数据的变量data， 另一部分是指向下一个节点的指针next。一个节点连着一个节点，每一个节点之间可以想象成有一条绳子拴起来，其实是上一个节点的next指针指向下一个节点，然后下一个的next指针又指向下一个。

      线性表的单链表存储结构

      typedef int SLDataType;
typedef struct SLNode
{
	SLDataType data;
	struct SLNode* next;
}SLNode;

      从这个结构中，可以知道节点由存放数据元素的数据域(data)和存放下一个节点地址的指针域(next)组成,假设phead是指向链表中第一个节点的指针，那么该节点的数据域可以用phead->data表示，该节点的指针域用phead->next表示，链表与顺序表按照下标来随机寻找元素不同，

      对于链表的其中一个节点A， 只能根据节点A的next指针来找到该节点的下一个节点B， 再根据节点 B的next指针找到下一个节点C……

      而链表中的第一个节点被称为头节点， 最后1个节点被称为尾节点， 尾节点的 next指针指向空。后文不用带哨兵位的头节点，哨兵位的头节点数据域里是没有元素。这里的头节点数据域里是有元素的，与哨兵位头节点不同，这里用phead这一结构体指针指向链表第一个节点，phead->next是指向头节点的下一个节点，其实是phead->next存着它下一个节点的地址，可以想象成第一个节点拿着一根绳子把第二个节点拴起来了。

      单链表找下一个容易但是它找他的前一个十分困难，需要再回溯一遍，在数据结构中还有一中双向链表可以快速找到前一个元素，但是本文重点描述单链表实现

      链表在内存中如何存储的？

      接下来我们看一看链表的存储方式。 如果说顺在内存中的存储方式是顺序存储（一个挨着一个的存储）， 而链表在内存中的存储 方式则是随机存储（链表在内存中每一个节点存储在不同内存块中，而通过节点next指针链接下一个节点地址，依靠next指针这样连使每一个节点存在联系，使这些零星的空间链接起来）红色为顺序表顺序存储，绿色为链表随机存储

      分享一篇由C语言实现《数据结构》无头无循环单链表 第3张

      链表物理结构和逻辑结构

      物理结构是在内存中真是存在的内存块，结构体指针phead指向第一个节点，然后第一个节点的next指针指向下一个节点地址。其实就是前一个节点的next存着下一个节点地址，这样下去直到链表为空分享一篇由C语言实现《数据结构》无头无循环单链表 第4张

      逻辑结构是想象中有一根线连着两个节点，箭头表示next指针

      分享一篇由C语言实现《数据结构》无头无循环单链表 第5张

      与顺序表一样，链表同样有增删查改基本操作，并且插入和删除同样有头、尾、任意位置操作。且还有销毁操作

      二、单链表基本操作（增，删，查，改，销毁，遍历）

      1.查找与修改、销毁与遍历

      查找

      在查找元素时， 链表不像数组那样可以通过下标快速进行定位， 只能从 头节点开始向后一个一个节点逐一查找，查找到就返回改节点，找不到则返回空，如pos为3,从以phead指针指向第一个节点，第一个节点数据域不为3，通过第一个节点next指针指向第二个，然后第三个，找到为止。链表中的数据只能按顺序进行访问， 最坏的时间复杂度是O(n) 。

      分享一篇由C语言实现《数据结构》无头无循环单链表 第6张

      //查找
SLNode* SLNodeFind(SLNode* phead, SLDataType x)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data != x)
		{
			cur = cur->next;
		}
		else
		{
			return cur;
		}
	}
	return NULL;
}

      不考虑查找节点的过程， 链表的更新过程会像数组那样简单， 直接 把旧数据替换成新数据即可。修改就是将找到的这一节点的数据域修改即可

      代码如下

      if (ret)
	{
		//修改ret节点的值
		ret->data *= 2;
	}

      链表销毁

      销毁时注意释放上一个节点时要找到下一个节点地址，同时将该节点置空

      代码实现如下

      //销毁
void SLNodeDestory(SLNode** pphead)
{
	assert(*pphead);
	SLNode* cur = *pphead;
	SLNode* next = NULL;
	while (cur->next != NULL)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
		free(cur);
		cur = NULL;
		/*free(next);
		next = NULL;*/
		*pphead = NULL;
}

      链表遍历

      直接上代码

      //遍历
void SLNodeprint(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

      2.链表插入与删除操作

      插入三种情况

      1、尾部插入 2、头部插入 3、中间插入

      在插入之前先创建一个要插入的节点，开创新节点之后返回该节点地址，新节点数据域为x，指针域为空

      代码如下

      //创建一个新节点
SLNode* BuyNewnode(SLDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;//1
	newnode->next = NULL;
	return newnode;
}

      尾插

      尾部插入， 是最简单的情况， 把最后一个节点的next指针指向新插入的 节点即可。

      分享一篇由C语言实现《数据结构》无头无循环单链表 第7张

      代码如下

      //尾插
void SLNodePushBack(SLNode** pphead, SLDataType x)
{
	assert(pphead);
	SLNode* newnode = BuyNewnode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;//1
	}
	else
	{
		SLNode* tail = *pphead;
		while (tail->next != NULL)//如果将判断改为cur != NULL,那么到最后一个节点时将NULL给cur，后面插入的时候就不能找到下一个节点，直接为空了
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

      头插

      头部插入， 可以分成两步。

      1、 把新节点的next指针指向原先的头节点。

      2 、把新节点变为链表的头节点。

      分享一篇由C语言实现《数据结构》无头无循环单链表 第8张

      代码如下

      //头插
void SLNodePushFront(SLNode** pphead, SLDataType x)
{
	assert(pphead);
	SLNode* newnode = BuyNewnode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

      任意位置（pos)插入

      任意位置插入， 同样分为两步。

      1、 新节点的next指针， 指向插入位置的节点。

      2、 插入位置前置节点的next指针， 指向新节点。

      分享一篇由C语言实现《数据结构》无头无循环单链表 第9张

      代码 如下

      //pos前面插入
void SLNodeInsert(SLNode** pphead, SLNode*pos,SLDataType x)
{
	assert(pphead);
	SLNode* newnode = BuyNewnode(x);
	SLNode* prev = *pphead;
	if (pos == *pphead)
	{
		SLNodePushFront(pphead, x);//复用头插
	}
	else
	{
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}

      链表插入只要内存空间允许， 能够插入链表的元素是无穷无尽的， 不需要像数组 那样考虑扩容的问题。

      链表删除操作同样分为尾删、头删、任意位置(pos)删除

      尾删

      尾部删除， 是最简单的情况， 把倒数第2个节点的next指针指向空。

      分享一篇由C语言实现《数据结构》无头无循环单链表 第10张

      代码如下

      //尾删
void SLNodePopBack(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* tail = *pphead;
		SLNode* prev = NULL;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}

      头删

      头部删除， 把链表的头节点设为原先头节点的next指针即 可。

      分享一篇由C语言实现《数据结构》无头无循环单链表 第11张

      代码如下

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

      任意位置删除

      任意位置删除，把要删除节点的前置节点的next指针 指向要 删除元素的下一个节点即可。分享一篇由C语言实现《数据结构》无头无循环单链表 第12张

      代码如下

      //删除pos位置节点
void SLNodeErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	if (*pphead == pos)
	{
		*pphead = pos->next;
		free(pos);
		pos = NULL;//这里置空无意义，形参改变不会影响实参，在外面调用它的那个函数置空
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next!=pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

      删除注意两点

      1、链表删空

      2、被删除的节点需要释放且置空

      链表的插入和删除时间复杂度是多少嘞？

      如果不考虑插入、 删除操作之前 查找元素的过程， 只考虑纯粹的插入和删除操作， 时间复杂度都 是O(1)

      三、单链表 VS 顺序表 且 全部 源码(SLNode.h ) (SLNode.c) ( test.c)

      那么思考一下顺序表和 链表都属于线性的数据结构， 用哪一个更好呢？ 顺序表和链表没有绝对的好与坏，顺序和 链表各有千秋。

      对比一下顺序表和链表相关操作的性能。

      分享一篇由C语言实现《数据结构》无头无循环单链表 第13张

      从表格可以看出， 顺序表的优势在于能

      够快速定位元素，就这一优势就特别如在有序且数据个数范围特别大时，用二分效率高。而链表的优势在于能够灵活地进行插入和删除操作。

      SLNode.h

      #include
#include
#include
typedef int SLDataType;
typedef struct SLNode
{
	SLDataType data;
	struct SLNode* next;
}SLNode;
//遍历打印
void SLNodeprint(SLNode* phead);
//尾插
void SLNodePushBack(SLNode** pphead, SLDataType x);
//尾删
void SLNodePopBack(SLNode** pphead);
//头插
void SLNodePushFront(SLNode** pphead, SLDataType x);
//头删
void SLNodePopFront(SLNode** pphead);
//销毁
void SLNodeDestory(SLNode** pphead);
//查找
SLNode* SLNodeFind(SLNode* phead, SLDataType x);
//在pos位置前插入
void SLNodeInsert(SLNode** pphead, SLNode* pos, SLDataType x);
//在pos位置后插入
void SLNodeInsertAfter(SLNode** pphead, SLNode* pos, SLDataType x);
//删除pos节点
void SLNodeErase(SLNode** pphead, SLNode* pos);
//节点pos后一个节点
void SLNodePopAfter(SLNode** pphead, SLNode* pos);

      SLNode.c

      #include"SLNode.h"
//遍历
void SLNodeprint(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
//创建一个新节点
SLNode* BuyNewnode(SLDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;//1
	newnode->next = NULL;
	return newnode;
}
//尾插
void SLNodePushBack(SLNode** pphead, SLDataType x)
{
	assert(pphead);
	SLNode* newnode = BuyNewnode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;//1
	}
	else
	{
		SLNode* tail = *pphead;
		while (tail->next != NULL)//如果将判断改为cur != NULL,那么到最后一个节点时将NULL给cur，后面插入的时候就不能找到下一个节点，直接为空了
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
//尾删
void SLNodePopBack(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* tail = *pphead;
		SLNode* prev = NULL;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}
//头插
void SLNodePushFront(SLNode** pphead, SLDataType x)
{
	assert(pphead);
	SLNode* newnode = BuyNewnode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
//头删
void SLNodePopFront(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	
	SLNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}
//销毁
void SLNodeDestory(SLNode** pphead)
{
	assert(*pphead);
	SLNode* cur = *pphead;
	SLNode* next = NULL;
	while (cur->next != NULL)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
		free(cur);
		cur = NULL;
		/*free(next);
		next = NULL;*/
		*pphead = NULL;
}
//查找
SLNode* SLNodeFind(SLNode* phead, SLDataType x)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data != x)
		{
			cur = cur->next;
		}
		else
		{
			return cur;
		}
	}
	return NULL;
}
//pos前面插入
void SLNodeInsert(SLNode** pphead, SLNode*pos,SLDataType x)
{
	assert(pphead);
	SLNode* newnode = BuyNewnode(x);
	SLNode* prev = *pphead;
	if (pos == *pphead)
	{
		SLNodePushFront(pphead, x);
	}
	else
	{
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}
//在pos位置后面插入x
void SLNodeInsertAfter(SLNode** pphead, SLNode* pos, SLDataType x)
{
	SLNode* newnode = BuyNewnode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
//删除pos位置节点
void SLNodeErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	if (*pphead == pos)
	{
		*pphead = pos->next;
		free(pos);
		pos = NULL;//这里置空无意义，形参改变不会影响实参，在外面调用它的那个函数置空
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next!=pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}
//在pos位置之后删除
void SLNodePopAfter(SLNode** pphead, SLNode* pos)
{
	assert(pos->next);
	SLNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

      test.c

      #include"SLNode.h"
void test()
{
	SLNode* plist = NULL;
	//尾插
	SLNodePushBack(&plist, 1);
	SLNodePushBack(&plist, 2);
	SLNodePushBack(&plist, 3);
	SLNodePushBack(&plist, 4);
	SLNodeprint(plist);
	//头插
	SLNodePushFront(&plist, 10);
	SLNodeprint(plist);
	SLNodeDestory(&plist);
}
void test1()
{
	SLNode* plist = NULL;
	SLNodePushBack(&plist, 1);
	SLNodePushBack(&plist, 2);
	SLNodePushBack(&plist, 3);
	SLNodePushBack(&plist, 4);
	SLNodePushFront(&plist, 10);
	SLNodeprint(plist);
	//尾删
	SLNodePopBack(&plist);
	SLNodeprint(plist);
	SLNodePopBack(&plist);
	SLNodePopBack(&plist);
	/*SLNodePopBack(&plist);*/
	//SLNodePopBack(&plist);
	SLNodeprint(plist);
	//头删
	SLNodePopFront(&plist);
	SLNodeprint(plist);
	SLNodePopFront(&plist);
	SLNodeprint(plist);
	SLNodePopFront(&plist);
	SLNodeprint(plist);
	SLNodeDestory(&plist);
}
void test2()
{
	SLNode* plist = NULL;
	SLNodePushBack(&plist, 1);
	SLNodePushBack(&plist, 2);
	SLNodePushBack(&plist, 3);
	SLNodePushBack(&plist, 4);
	SLNodePushFront(&plist, 10);
	SLNodeprint(plist);
	//查找
	SLNode* ret = SLNodeFind(plist, 4);
	if (ret)
	{
		//在ret位置前插入30
		SLNodeInsert(&plist, ret, 30);
	}
	SLNodeprint(plist);
	if (ret)
	{
		//修改ret节点的值
		ret->data *= 2;
	}
	SLNodeprint(plist);
	if (ret)
	{
		//在ret节点后面插入一个值为节点
		SLNodeInsertAfter(&plist, ret, 999);
	}
	SLNodeprint(plist);
	//if (ret)
	//{
	// //删除ret节点
	//	SLNodeErase(&plist, ret);
	//	//ret = NULL;
	//}
	//SLNodeprint(plist);
	if (ret)
	{
		//删除ret节点后面的那个节点
		SLNodePopAfter(&plist, ret);
	}
	SLNodeprint(plist);
}
int main()
{
	//test();
	//test1();
	test2();
	return 0;
}

      注意:这篇文章是由c语言实现的，而从上文很多接口实现时可以发现，有**pphead，*phead，*plist为结构体指针初始化为空，后面在向链表中插入节点时，由于要改变链表内容，那么就需要将链表的地址传过去，在插入接口以二级指针指向链表地址，通过解引用就可以改变链表。这里插入一点传参问题，值传递：改变形参不可改变实参，地址传递：，改变形参可以改变实参。而断言assert(pphead)则是因为在插入时需要有链表才可以对链表进行操作，如果在SLNodePushBack()这个接口函数test()在传参时，传的是空地址，该接口就无法对链表进行操作。而在删除时同样如此，还需要断言链表内容是否为空，链表中是否有节点assert(*pphead)，链表为空就不能再删除了。如果不用断言判断，用if判断链表是否为空的话，如果代码太多，一时间看不出哪里出的问题，还需要通过调试才能发现，而用断言则能给你报一些基础的错误，这时会发觉断言真好用。

      迎来了三月


相关阅读：

1、YOLOv8目标检测中数据集各部分的作用

2、目标检测任务中常用的数据集格式(voc、coco、yolo)

3、【基于Ubuntu下pointnet++激光点云目标检测】保姆级教程 | 环境配置 | 数据集下载 | 修改配置 | 训练以及测试 | 全过程图文by.Akaxi

4、目标检测——摩托车头盔检测数据集

5、【C语言】文件操作（1）

免责声明
1、本网站属于个人的非赢利性网站，转载的文章遵循原作者的版权声明。
2、本网站转载文章仅为传播更多信息之目的，凡在本网站出现的信息，均仅供参考。本网站将尽力确保所
提供信息的准确性及可靠性，但不保证信息的正确性和完整性，且不对因信息的不正确或遗漏导致的任何
损失或损害承担责任。
3、任何透过本网站网页而链接及得到的资讯、产品及服务，本网站概不负责，亦不负任何法律责任。
4、本网站所刊发、转载的文章，其版权均归原作者所有，如其他媒体、网站或个人从本网下载使用，请在
转载有关文章时务必尊重该文章的著作权，保留本网注明的“稿件来源”，并白负版权等法律责任。

手机扫描二维码访问

文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。

相关阅读

发表评论

快捷回复： 表情：
评论列表 （暂无评论，4215人围观）

还没有评论，来说两句吧...

目录[+]