数据结构：链表-C语言实现

golden_hamster 发布于2021-11-17 09:33 / 2793人阅读

摘要：虽然有这么多的链表的结构，但是我们实际中最常用还是这两种结构单向无头不循环链表，双向带头循环链表，下面我们来学习这两种链表。

文章目录

链表

点击下面蓝色字体，越读博主的上一篇文章，数据结构：顺序表-C语言实现
数据结构:顺序表-C语言实现

链表

一. 前言

在学了顺序表之后，我们发现顺序表有一定的缺陷。第一个缺陷，从头部和中间的插入删除，都要移动后面的数据，时间复杂度为O(N)。第二个缺陷，增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。第三个缺陷，增容一般是呈2倍的增长，这会造成一定的空间浪费。比如说当前顺序表数据有1024个，容量也恰好是1024，这时我们只想插入一个数据，但是扩容却要扩大到2048个，这样有1023个空间大小就浪费了。刚刚提到的这些问题，链表就能很好地解决。下面我们就来一起学习一下链表，看看链表是怎么去解决这些问题的，链表又存在什么缺陷？

二. 链表的定义

2.1 概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表的所有节点都是一个一个多带带通过malloc向内存申请的，用的时候再申请。从下图我们可以看出，链表的每个节点都有一个next指针指向下一个节点的地址，从逻辑上每个节点都是链接起来的。从内存的地址上看，每一个节点地址之间的距离大小都是不一样的，所以物理结构上他们不在的空间是不连续的。

2.2 分类

单向和双向
带头和不带头
循环和不循环
实际中链表的结构非常多样，以上情况组合起来就有8种链表结构。虽然有这么多的链表的结构，但是我们实际中最常用还是这两种结构：单向无头不循环链表，双向带头循环链表，下面我们来学习这两种链表。

三. 单向无头不循环链表

3.1 概念和说明

单向无头不循环链表是链表中结构最简单的。如下图所示，每一个节点有一个data和一个next，data是用来存放数据的，next是一个指向下一个节点地址的指针，最后一个节点的next指向NULL。在实现链表上，一个创建了三个文件，分别是SList.h，SList.c，main.c，下面内容我们先定义链表的结构体和实现各个函数接口的代码，最后再把三个文件的代码展示出来。

3.2 定义链表结构体

// 重定义数据类型名typedef int SLTDataType;// 定义链表结构体typedef struct SListNode{	// 定义一个指向下一个节点地址的指针	struct SListNode* next;	// 定义一个存放数据的变量	SLTDataType data;}SListNode;

为什么要重定义数据类型名？因为链表储存的元素类型不单单是int型，后面要存储char型的或者其他类型的数据，需要把代码里面的int都改一遍，非常麻烦。如果我们重新定义了类型名，并且在代码里用重新定义好的名字，下次需要存储其他类型的数据，直接在重定义那里把int改成想存储的类型就好了。

3.3 函数接口

3.3.1 申请节点

// 申请一个节点SListNode* BuySListNode(SLTDataType x){	// 向内存申请一个节点	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));	// 判断申请是否成功	assert(newnode);	// 对节点初始化以及赋值	newnode->next = NULL;	newnode->data = x;	return newnode;}

3.3.2 链表头插

// 头插/*********************** 为什么会用到二级指针 ** 后面3.7会讲到      ***********************/void SListPushFront(SListNode** pplist, SLTDataType x){	// 防止传进来的pplist是空指针	assert(pplist);	// 申请一个新节点	SListNode* newnode = BuySListNode(x);	// 判断链表是否为空	if (*pplist == NULL)	{		*pplist = newnode;	}	else	{		 方法一		  申请一个指针指向当前的头节点		//SListNode* next = *pplist;		//*pplist = newnode;		//newnode->next = next;		// 方法二		newnode->next = *pplist;		*pplist = newnode;	}}// 方法一和方法二的补充// 从上面我们可以看到方法一多定义了一个指针，指向当前头节点的地址//这样做的好处是，在接下来的两条代码的顺序你可以随意变换// 你可以这样写*pplist = newnode;newnode->next = next;// 也可以这样写newnode->next = next;*pplist = newnode;// 如果你像方法二那样没有定义指针的话，你的代码只能写成上面这个顺序// 要是你顺序写反的话，*pplist会直接放弃原来的头节点去指向newnode，而当newnode的next想去指向原来的头节点时，已经找不到地址了。// 所以正确的顺序是上面那样，先让newnode的next先指向原来的头节点，后面*pplist才去指向newnode。// 总结，方法一多定义一个变量更加省心，方法二相对来说要思考得细一点，也便于我们更好地去理解链表结构。

assert是一个断言函数，程序运行的时候，当括号里面的结果为假时，就会停止运行并且报错。报错显示的信息包括断言的内容和断言的位置，还有一个错误框，如下图所示。断言能够快速地帮我们定位程序的错误，在实际开发中可以减少很多不必要的麻烦，所以建议大家在写代码的时候也尽量在需要的时候加上断言。
温馨提示在使用assert函数时，记得包含一下assert.h这个头文件。

3.3.3 链表尾插

// 尾插void SListPushBack(SListNode** pplist, SLTDataType x){	assert(pplist);	// 申请一个新节点	SListNode* newnode = BuySListNode(x);	// 分两种情况，链表为空和非空	if (*pplist == NULL)	{		*pplist = newnode;	}	else	{		// 定义一个指针，去遍历寻找尾节点		SListNode* tail = *pplist;		while (tail->next)		{			tail = tail->next;		}		// 插入节点		tail->next = newnode;	}}

3.3.4 在pos节点之后插入

// 在pos之后插入一个节点void SListInsertAfter(SListNode* pos, SLTDataType x){	assert(pos);	// 申请一个新节点	SListNode* newnode = BuySListNode(x);		 这里也是有两个方法，跟之前头插的差不多	 方法一	 定义一个指针指向pos的next	//SListNode* posNext = pos->next;	//newnode->next = posNext;	//pos->next = newnode;	// 方法二	newnode->next = pos->next;	pos->next = newnode;}

3.3.5 在pos节点之前插入

// 在pos之前插入一个节点void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x){	assert(pplist);	assert(pos);	// 申请一个新节点	SListNode* newnode = BuySListNode(x);	// 判断pos是否为第一个节点	if (*pplist == pos)	{		newnode->next = pos;  		*pplist = newnode;	}	else	{		// 先找到pos之前的一个节点		SListNode* prev = *pplist;		while (prev->next != pos)		{			prev = prev->next;		}				// 插入新节点		newnode->next = pos;  		prev->next = newnode;	}}

3.3.6 链表头删

// 头删void SListPopFront(SListNode** pplist){	// 防止pplist指针为空	assert(pplist);	// 防止pplist指向的地址为空，即链表为空	assert(*pplist);	// 定义一个指针指向第一个节点的地址，后面释放空间需要用到	SListNode* temp = *pplist;	// 让*pplist直接指向它的下一个节点	*pplist = (*pplist)->next;	// 释放被删节点空间,并把temp指针置空	free(temp);	temp = NULL;}

3.3.7 链表尾删

// 尾删void SListPopBack(SListNode** pplist){	assert(pplist);	assert(*pplist);	// 分两种情况，链表只有一个节点，和有一个以上节点	if ((*pplist)->next == NULL)	{		free(*pplist);		*pplist = NULL;	}	else	{		// 找到尾节点之前的一个节点		SListNode* tail = *pplist;		while (tail->next->next)		{			tail = tail->next;		}		SListNode* temp = tail->next;		tail->next = NULL;		free(temp);		temp = NULL;	}}

3.3.8 删去pos节点

// 删去pos节点void SListErase(SListNode** pplist, SListNode* pos){	assert(pplist);	assert(*pplist);	// 分两种情况，pos为第一个节点和不是第一个节点	if (*pplist == pos)	{		free(*pplist);		*pplist = NULL;	}	else	{		// 找到pos之前的节点		SListNode* posPrev = *pplist;		while (posPrev->next != pos)		{			posPrev = posPrev->next;		}		posPrev->next = pos->next;		free(pos);		pos = NULL;	}}

3.3.9 链表查找

// 查找SListNode* SListFind(SListNode* plist, SLTDataType x){	// 当链表为空，返回NULL	if (plist == NULL)	{		return NULL;	}		// 链表不为空，遍历链表	SListNode* find = plist;	while (find)	{		// 判断是否为所找节点，是则返回节点地址		if (find->data == x)		{			return find;		}		// 继续迭代		find = find->next;	}	// 没有找到，返回NULL	return NULL;}

3.3.10 链表修改

// 修改void SListModify(SListNode* pos, SLTDataType x){	assert(pos);	pos->data = x;}

3.3.11销毁链表

// 销毁void SListDestroy(SListNode** pplist){	assert(pplist);	SListNode* temp = NULL;        // 头删，依次释放空间	while (*pplist)	{		temp = *pplist;		*pplist = (*pplist)->next;		free(temp);	}	temp = NULL;}

不知道大家是否记得上次顺序表的销毁是一次性把整块给销毁的，而这次的链表则要一个一个多带带释放。因为顺序表我们是向内存申请一整块连续的空间，而链表这边是一个一个多带带申请的，且他们一般情况下是不连续的，所以释放得多带带释放。

3.4 SList.h文件代码

#pragma once  // 防止头文件被重复包含// 包含头文件#include#include#include// 重新定义数据类型名typedef int SLTDataType;// 定义链表结构体typedef struct SListNode{	// 定义一个指向下一个节点地址的指针	struct SListNode* next;	// 定义一个存放数据的变量	SLTDataType data;}SListNode;// 函数接口// 打印void SListPrint(SListNode* plist);// 申请一个节点SListNode* BuySListNode(SLTDataType x);// 头插void SListPushFront(SListNode** pplist, SLTDataType x);// 尾插void SListPushBack(SListNode** pplist, SLTDataType x);// 在pos之前插入一个节点void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x);// 在pos之后插入一个节点void SListInsertAfter(SListNode* pos, SLTDataType x);// 头删void SListPopfront(SListNode** pplist);// 尾删void SListPopBack(SListNode** pplist);// 删去pos节点void SListErase(SListNode** pplist, SListNode* pos);// 查找SListNode* SListFind(SListNode* plist, SLTDataType x);// 修改void SListModify(SListNode* pos, SLTDataType x);// 销毁void SListDestroy(SListNode** pplist)

3.5SList.c文件代码

#define _CRT_SECURE_NO_WARNINGS  // 这句是我的VS2019用scanf报错才加的，大家可以不用理#include"SList.h"// 打印void SListPrint(SListNode* plist){	while (plist)	{		printf("%d", plist->data);		printf("-->");		plist = plist->next;	}	printf("NULL");}// 申请一个节点SListNode* BuySListNode(SLTDataType x){	// 向内存申请一个节点	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));	// 判断申请是否成功	assert(newnode);	// 对节点初始化以及赋值	newnode->next = NULL;	newnode->data = x;	return newnode;}// 头插void SListPushFront(SListNode** pplist, SLTDataType x){	// 防止传进来的pplist是空指针	assert(pplist);	// 申请一个新节点	SListNode* newnode = BuySListNode(x);	// 判断链表是否为空	if (*pplist == NULL)	{		*pplist = newnode;	}	else	{		 方法一		  申请一个指针指向当前的头节点		//SListNode* next = *pplist;		//*pplist = newnode;		//newnode->next = next;		// 方法二		newnode->next = *pplist;		*pplist = newnode;	}}// 尾插void SListPushBack(SListNode** pplist, SLTDataType x){	assert(pplist);	// 申请一个新节点	SListNode* newnode = BuySListNode(x);	// 分两种情况，链表为空和非空	if (*pplist == NULL)	{		*pplist = newnode;	}	else	{		// 定义一个指针，去遍历寻找尾节点		SListNode* tail = *pplist;		while (tail->next)		{			tail = tail->next;		}		// 插入节点		tail->next = newnode;	}}// 在pos之前插入一个节点void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x){	assert(pplist);	assert(pos);	// 申请一个新节点	SListNode* newnode = BuySListNode(x);	// 判断pos是否为第一个节点	if (*pplist == pos)	{		newnode->next = pos;  		*pplist = newnode;	}	else	{		// 先找到pos之前的一个节点		SListNode* prev = *pplist;		while (prev->next != pos)		{			prev = prev->next;		}				// 插入新节点		newnode->next = pos;  		prev->next = newnode;	}}// 在pos之后插入一个节点void SListInsertAfter(SListNode* pos, SLTDataType x){	assert(pos);	// 申请一个新节点	SListNode* newnode = BuySListNode(x);		 这里也是有两个方法，跟之前头插的差不多	 方法一	 定义一个指针指向pos的next	//SListNode* posNext = pos->next;	//newnode->next = posNext;	//pos->next = newnode;	// 方法二	newnode->next = pos->next;	pos->next = newnode;}// 头删void SListPopFront(SListNode** pplist){	// 防止pplist指针为空	assert(pplist);	// 防止pplist指向的地址为空，即链表为空	assert(*pplist);	// 定义一个指针指向第一个节点的地址，后面释放空间需要用到	SListNode* temp = *pplist;	// 让*pplist直接指向它的下一个节点	*pplist = (*pplist)->next;	// 释放被删节点空间，并把temp指针置空	free(temp);	temp = NULL;}// 尾删void SListPopBack(SListNode** pplist){	assert(pplist);	assert(*pplist);	// 分两种情况，链表只有一个节点，和有一个以上节点	if ((*pplist)->next == NULL)	{		free(*pplist);		*pplist = NULL;	}	else	{		// 找到尾节点之前的一个节点		SListNode* tail = *pplist;		while (tail->next->next)		{			tail = tail->next;		}		SListNode* temp = tail->next;		tail->next = NULL;		free(temp);		temp = NULL;	}}// 删去pos节点void SListErase(SListNode** pplist, SListNode* pos){	assert(pplist);	assert(*pplist);	// 分两种情况，pos为第一个节点和不是第一个节点	if (*pplist == pos)	{		*pplist = pos->next;		free(pos);	}	else	{		// 找到pos之前的节点		SListNode* posPrev = *pplist;		while (posPrev->next != pos)		
            
                     
                 
                                                                                                                    
                         GPU云服务器
                                             
                         云服务器
                                                                                                                                                 
                                      
                     
                    
                                                                                               多链表c语言实现
                                                                                                           遍历c语言实现链表
                                                                                                           用链表实现队列c语言
                                                                                                           结构体链表c语言
                                                         
                 
               
              
             
               
                    文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
                 
                   转载请注明本文地址：https://www.ucloud.cn/yun/123619.html
               
                      
               
                 
                                  上一篇：深入理解取整、取余与取模问题  
                                                
                                       下一篇：八种常见排序算法细讲


              
                相关文章
                
                             
                                                                    
                                                
                          不要认为学PHP就不需要学C语言
                                                     摘要：之所以这样说不要认为学就不需要学语言，是因为一味的只学而没有语言等这些基础语言的支撑，是很难深入理解的很多东西的。

之所以这样说不要认为学PHP就不需要学C语言，是因为一味的只学PHP而没有C语言等这些基础语言的支撑，是很难深入理解PHP的很多东西的。
这样的例子其实很多，这里我就举这个例子吧：PHP的数组和C语言的数组的区别和联系。
学过C语言的朋友当然知道C语言里有数组；
PHP里...
                                                   
                          
                                
                                    KoreyLee
                                    2019-06-27 16:27
                                    评论0 
                                    收藏0 
                                
                          
                      
                     
                                                                                                           
                
              
              
               
                  
                  发表评论
                   
                                      
                      
                        登陆后可评论
                      
                   
               
              
                
                  0条评论


           
               
                
                    
                    golden_hamster
                    男|高级讲师
                    
                     
                                                                      我要关注
      
                                                                                        我要私信
                     
                                            
                    
                    
                          TA的文章
                          阅读更多
                    
                      
                                                  tensorflow
                            阅读 1854·2023-04-25 14:28
                                                       模拟信号|隔离器放大器|隔离变送器|4-20mA|0-5V|0-10V隔离|常见问题解答
                            阅读 1890·2021-11-19 09:40
                                                       数据结构：链表-C语言实现
                            阅读 2794·2021-11-17 09:33
                                                       OBHost：万圣节优惠，新加坡vps/美国vps等，大硬盘VPS/游戏服务器/站群VPS七折，最低
                            阅读 1382·2021-11-02 14:48
                                                       Vue.js 移动端适配之 vw 解决方案
                            阅读 1708·2019-08-29 16:36
                                                       Bootstrap 4重大更新，亮点解读
                            阅读 3330·2019-08-29 16:09
                                                       关于响应式设计的一些关键点
                            阅读 2915·2019-08-29 14:17
                                                       Web前端面试题目汇总
                            阅读 2375·2019-08-29 14:07
                                                
                      
                

                   
              
  
                  最新活动

资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

数据结构：链表-C语言实现

文章目录

链表

一. 前言

二. 链表的定义

2.1 概念

2.2 分类

三. 单向无头不循环链表

3.1 概念和说明

3.2 定义链表结构体

3.3 函数接口

3.3.1 申请节点

3.3.2 链表头插

3.3.3 链表尾插

3.3.4 在pos节点之后插入

3.3.5 在pos节点之前插入

3.3.6 链表头删

3.3.7 链表尾删

3.3.8 删去pos节点

3.3.9 链表查找

3.3.10 链表修改

3.3.11销毁链表

3.4 SList.h文件代码

3.5SList.c文件代码

相关文章

发表评论

0条评论

男|高级讲师

TA的文章

最新活动