C语言数据结构超详细讲解单向链表
1.链表概况
1.1 链表的概念及结构
概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
1.2 链表的分类
实际中链表的结构非常多样,以下情况组合起来就有8种链表结构
单向或者双向
带头或者不带头
循环或者非循环
虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构
- 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了
2. 单向链表的实现
单向链表结构
2.1 SList.h(头文件的汇总,函数的声明)
#pragma once #include<stdio.h> #include<string.h> #include<stdlib.h> #include<assert.h> typedef int SLTDataType; typedef struct SListNode { int data;//数据 struct SListNode* next;//下一个节点的地址 }SListNode; void SListPrint(SListNode* phead);//打印 SListNode* BuySListNode(SLTDataType x);//搞出一个新节点 void SListPushBack(SListNode** pphead, SLTDataType x);//尾插 void SListPushFront(SListNode** pphead, SLTDataType x);//头插 void SListPopBack(SListNode** pphead);//尾删 void SListPopFront(SListNode** pphead);//头删 SListNode* SListFind(SListNode* phead, SLTDataType x);//查找 void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);//在pos位置之前插入 void SListInsertAfter(SListNode* pos, SLTDataType x);//在pos位置之后插入 void SListErase(SListNode** pphead, SListNode* pos);//删除pos位置 void SListEraseAfter(SListNode* pos);//删除pos之后位置 void SListDestroy(SListNode** pphead);//销毁
2.2 SList.c(函数的具体实现逻辑)
2.2.1 打印链表
//打印 void SListPrint(SListNode* phead) { //assert(phead);//没必要断言,空链表也能打印 SListNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
//test.c void TestSList1() { SListNode* slist;//结构体指针,用于存节点的地址 SListNode* n1 = (SListNode *)malloc(sizeof(SListNode)); SListNode* n2 = (SListNode*)malloc(sizeof(SListNode)); SListNode* n3 = (SListNode*)malloc(sizeof(SListNode)); n1->data = 1; n2->data = 2; n3->data = 3; n1->next = n2; n2->next = n3; n3->next = NULL; slist = n1; SListPrint(slist); }
2.2.2 搞出一个新节点(为其他函数服务)
//搞出一个新节点 SListNode* BuySListNode(SLTDataType x) { SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } else { newnode->data = x; newnode->next = NULL; } return newnode; }
2.2.3 链表尾插
//尾插 void SListPushBack(SListNode** pphead,SLTDataType x)//会改变实参slist,要传二级指针 { 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 TestSList2() { SListNode* slist = NULL; for (int i = 0; i < 6; i++) { SListPushBack(&slist,i); } SListPrint(slist); }
2.2.4 链表头插
//头插 void SListPushFront(SListNode** pphead, SLTDataType x) { assert(pphead);//就算链表是空,它的二级指针也不为空 SListNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; }
void TestSList2() { SListNode* slist = NULL; for (int i = 0; i < 6; i++) { SListPushFront(&slist,i); } SListPrint(slist); }
2.2.5 链表尾删
方法1(用两个指针,分别找最后一个和倒数第二个):
方法2(直接找倒数第二个):
//尾删 void SListPopBack(SListNode** pphead)//如果只有一个节点但还要尾删,就会改变实参slist,建议传二级指针 { assert(pphead);//就算链表是空,它的二级指针也不为空 //三种情况: //1.空 //2.一个节点 //3.多个节点 if (*pphead == NULL) { return; } else if ((*pphead)->next == NULL)//优先级,记得加括号 { free(*pphead); *pphead = NULL; } //第一种写法(用两个指针,分别找最后一个和倒数第二个) else { SListNode* prev = NULL;//找倒数第二个元素,用于将它指向NULL SListNode* tail = *pphead;//找尾 while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); tail = NULL;//习惯性free掉就将其置空 prev->next = NULL; } //方法二(直接找倒数第二个) //else //{ //SListNode* tail = *pphead;//找尾 //while (tail->next->next != NULL) //{ // tail = tail->next; //} //free(tail->next); //tail->next = NULL; //} }
2.2.6 链表头删
//头删 void SListPopFront(SListNode** pphead) { assert(pphead); //1.空 //2.非空 if (*pphead == NULL) { return; } else { SListNode* next = (*pphead)->next; free(*pphead); *pphead = next; } }
2.2.7 查找节点
//查找 SListNode* SListFind(SListNode* phead, SLTDataType x) { SListNode* cur = phead; while (phead != NULL) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
2.2.8 在pos位置之前插入
//在pos位置之前插入(一般跟find配合使用) void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x) { assert(pphead); assert(pos);//间接检测链表是否为空,因为空链表找不到pos //1.pos是第一个节点(头插) //2.pos不是第一个节点 if (pos == *pphead) { SListPushFront(pphead, x); } else { SListNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } SListNode* newnode = BuySListNode(x); prev->next = newnode; newnode->next = pos; } }
2.2.9 在pos位置之后插入
方法1:两个指针,先连接pos和newnode还是先连接newnode和next都行
方法2:只有一个指针,一定要先通过pos连接newnode和下一个,再连接pos和newnode,否则会找不到下一个的地址。
//在pos位置之后插入 void SListInsertAfter(SListNode* pos, SLTDataType x) { assert(pos); SListNode* newnode = BuySListNode(x); SListNode* next = pos->next; newnode->next = next;//顺序无所谓 pos->next = newnode; //或者不定义next //newnode->next = pos->next; //pos->next = newnode;//顺序要定好,否则会找不到 }
2.2.10 删除pos位置
//删除pos位置 void SListErase(SListNode** pphead, SListNode* pos) { assert(pphead); assert(pos); if (pos == *pphead) { SListPopFront(pphead); } else { SListNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL;//好习惯 } }
2.2.11 删除pos之后位置
//删除pos之后位置 void SListEraseAfter(SListNode* pos) { assert(pos); SListNode* next = pos->next; if (next)//防止pos是最后一个元素 { pos->next = next->next; free(next); next = NULL; } }
2.2.12 链表销毁
一个个找,一个个销毁,最终将slist置空。
//销毁 void SListDestroy(SListNode** pphead) { assert(pphead); SListNode* cur = *pphead; while (cur) { SListNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
总结:单链表结构,适合头插头删。尾部或者中间某个位置插入删除不适合。如果要使用链表单独存储数据,那我们之后会学的双向链表更合适。单链表学习的意义:
- 单链表会作为我们之后学习复杂数据结构的子结构(图的邻接表、哈希桶)
- 单链表会出很多经典的练习题。
链表系列有很多重点内容,我会花不少时间来跟大家讲解链表,相信大家跟着练习的话编程严谨性会大大提升,加油哦!
到此这篇关于C语言数据结构超详细讲解单向链表的文章就介绍到这了,更多相关C语言 单向链表内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
原文出处:https://blog.csdn.net/qq_47882731/article/details/123411413
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- 这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-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#常用数据结构和算法,这里我们总结了一些知识点,可以帮助大家理解这些概念。...2020-06-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