C语言详解无头单向非循环链表各种操作方法
链表引入
问:上次我们看了顺序表,那么顺序表有些什么优缺点呢?
优点:
顺序表是连续的物理空间,方便下标的随机访问。
缺点:
1.增容需要申请新空间,拷贝数据,释放旧的空间。会有一定消耗。
2.头部或者中间位置插入或者删除数据,需要挪动数据,效率较低。
3.可能存在一定空间占用,浪费空间,不能按需申请和释放空间。
为了解决上诉问题,我们引入了链表。首先我们先来看看单链表。
链表介绍
链表是一种物理存储结构上非连续、非顺序的存储结构、数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个节点包含两部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
实际上,链表的结构多样,如下:
1.单向或者双向
2.带头或者不带头
3.循环或者非循环
创建链表
链表是由结点链接而成的,所以创建链表需要创建一个结点类型。该类型由指针域和数据域组成。
typedef int SLTDataType; typedef struct SListNode { SLTDataType data;//用来存放该结点的数据 struct SListNode* next;//用来存放下一个结点的地址 }SListNode;
打印链表
从头指针指向的位置开始,依次向后打印,知道cur访问到NULL就结束循环。
void SListPrint(SListNode* phead); void SListPrint(SListNode* phead) { SListNode* cur = phead;//我们一般不会改变头指针,所以我们把头指针赋值给cur while (cur)//链表结束条件 { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n");//表示数据已经打印完毕 }
创建结点
每当我们需要插入一个数据,我们就需要申请一个结点,如果每次都重新申请就会很麻烦,所以我们将创建一个新结点封装为一个函数。
SListNode* BuySListNode(SLTDataType x) { SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL) { printf("BuySListNode::%s\n", strerror(errno));//若申请失败,则打印错误信息 exit(-1); } else { newnode->data = x;//将数据赋值到新点的数据域 newnode->next = NULL;//新结点指针域置为空指针 } return newnode;//返回新结点的地址 }
单链表尾插
我们需要将尾插分为两种情况:
情况一: 链表为空,我们直接让头指针指向新的结点即可。
情况二: 链表已经有多个结点,我们需要找到链表的最后一个结点,然后让最后一个结点指向新的结点。
void SListPushBack(SListNode** pphead, SLTDataType x); void SListPushBack(SListNode** pphead, SLTDataType x) { assert(pphead); SListNode* newnode = BuySListNode(x); //链表为空 if (*pphead == NULL) { *pphead = newnode;//头指针指向新的结点 } //链表不为空 else { SListNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } }
注意: 链表头插函数的参数我们应该传头指针的地址,而不是头指针本身。如果为传值调用,那么形参是实参的一份临时拷贝,对形参的改变不会影响实参。
单链表头插
单链表头插时,我们申请一个新的结点,然后让新结点的指针域指向之前的第一个结点,然后让头指针指向新结点。
注意:这两步操作的顺序不可以颠倒,如果先让头指针指向了新结点,那么将不可能找到第一个结点的位置了。也不可能在找到后面的数据了。
void SListPushFront(SListNode** pphead, SLTDataType x); void SListPushFront(SListNode** pphead, SLTDataType x) { assert(pphead); SListNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; }
单链表尾删
演示一种错误的写法:
对于单链表的尾删,我们需要考虑三种情况:
1.链表为空时,不做任何处理。
2.链表只有一个结点时,释放该结点,然后将头指针置为空。
3.链表有多个结点时,有两种处理方法,详见一下代码。
代码一: 找到最后一个结点的前一个结点,释放最后一个结点。将前一个结点的指针域置为空指针。
void SListPopBack(SListNode** pphead); void SListPopBack(SListNode** pphead) { assert(pphead); if (*pphead == NULL) return; else if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SListNode* prev = NULL; SListNode* tail = *pphead; while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); tail = NULL; prev->next = NULL; } }
代码二: 找到最后一个结点的前一个结点,将后一个结点释放掉,然后在置为空就可以了。
void SListPopBack(SListNode** pphead); void SListPopBack(SListNode** pphead) { assert(pphead); if (*pphead == NULL) return; else if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SListNode* tail = *pphead; while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
单链表头删
若链表为空,则不处理。若链表不为空,让头指针指向第二个结点,释放掉第一个结点。
void SListPopFront(SListNode** pphead); void SListPopFront(SListNode** pphead) { assert(pphead); if (*pphead == NULL)//链表为空 return; else { SListNode* head = *pphead; *pphead = head->next;//让头指针指针域中的地址指向头指针 free(head);//释放第一个结点 head = NULL; } }
在pos位置之前插入数据
若pos是第一个结点,我们直接调用之前写的头插。若pos不是第一个结点,我们找到pos位置的前一个结点,让新的结点指向地址为pos的结点,然后让前一个结点指向新结点。
void SListInsertBefore(SListNode** pphead, SListNode* pos, SLTDataType x); void SListInsertBefore(SListNode** pphead, SListNode* pos, SLTDataType x) { assert(pphead); assert(pos); if (*pphead == pos) { SListPushFront(pphead,x);//头插函数 } else { SListNode* prev = *pphead; while (prev->next != pos)//找到pos的前一个结点 { prev = prev->next; } SListNode* newnode = BuySListNode(x); newnode->next = prev->next;//让新结点指向pos结点 prev->next = newnode;//让前一个结点指向新结点 } }
在pos位置之后插入数据
让新结点指向该位置的下一个位置,然后让该位置的结点指向新结点。
void SListInsertAfter(SListNode** pphead, SListNode* pos, SLTDataType x); void SListInsertAfter(SListNode** pphead, SListNode* pos, SLTDataType x) { assert(pphead); SListNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode; }
删除pos位置结点
void SListErase(SListNode** pphead, SListNode* pos); void SListErase(SListNode** pphead, SListNode* pos) { assert(pphead); assert(pos); if (*pphead == pos) { SListPopFront(pphead); } else { SListNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } }
删除pos位置之后的结点
void SListEraseAfter(SListNode* pos); void SListEraseAfter(SListNode* pos) { assert(pos); SListNode* next = pos->next; if (next)//如果next不为空,则条件为真 { pos->next = next->next;//让pos指向要删除位置的后一个结点 free(next);//释放pos的下一个结点 next = NULL; } }
销毁链表
在销毁链表时。首先我们将头指针赋值给一个新的指针,用该指针依次遍历链表,先把该结点的下一个结点的地址保存,然后在释放该结点,最后将头指针置为空。
注意: 一定要在释放该指针之前保存该指针的下一个结点的地址,否则就找不到下一个结点了。
void SListDestroy(SListNode** pphead); void SListDestroy(SListNode** pphead) { assert(pphead); SListNode* cur = *pphead; while (cur) { SListNode* next = cur->next;//存放下一个结点地址 free(cur);//释放当前结点 cur = NULL; } *pphead = NULL;//将头指针置为空 }
链表查找
SListNode* SListFind(SListNode* phead, SLTDataType x); SListNode* SListFind(SListNode* phead, SLTDataType x) { SListNode* cur = phead; while (cur != NULL) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
提示:我们在写链表的时候,尽量画图分析,帮助我们理清思路。
到此这篇关于C语言详解无头单向非循环链表各种操作方法的文章就介绍到这了,更多相关C语言无头单向非循环链表内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
原文出处:https://blog.csdn.net/qq_61939403/article/details/123601114
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
C语言正则表达式详解 regcomp() regexec() regfree()用法详解
C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror(),这里就为大家介绍一下,需要的朋友可以参考一下啊...2020-04-25- 这篇文章主要介绍了c语言实现找最大值最小值位置查找,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-04