代做网站排名,小型企业网站开发价格,北京网站开发需要多少钱,手机网站开发人员工具前言 #x1f4da;作者简介#xff1a;爱编程的小马#xff0c;正在学习C/C#xff0c;Linux及MySQL。 #x1f4da;本文收录于初阶数据结构系列#xff0c;本专栏主要是针对时间、空间复杂度#xff0c;顺序表和链表、栈和队列、二叉树以及各类排序算法#xff0c;持…
前言 作者简介爱编程的小马正在学习C/CLinux及MySQL。 本文收录于初阶数据结构系列本专栏主要是针对时间、空间复杂度顺序表和链表、栈和队列、二叉树以及各类排序算法持续更新 相关专栏C及Linux正在发展敬请期待 目录 前言 1. 链表 1.1 链表的定义 1.2 链表与顺序表相比的好处 1.3 链表的结构表示 1.3.1 链表的结构形式 1.3.2 链表的结构性质 1.4 单链表的实现 1.4.1 单链表的创建 1.4.2 单链表的打印 1.4.3 单链表的动态内存申请 1.4.4 单链表的头插 1.4.5 单链表的尾插 1.4.6 单链表的头删 1.4.7 单链表的尾删 1.4.8 单链表的查找 1.4.9 单链表的任意位置插入的前插 1.4.10 单链表任意位置的删除 2.单链表的完整代码 2.1 test.c测试函数代码 2.2 SList.h函数声明代码 2.3 SList.c函数实现代码 总结 1. 链表
1.1 链表的定义
概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序所决定的
本文只介绍最简单的链表结构单链表
1.2 链表与顺序表相比的好处
1、顺序表从中间插入/头部插入时间复杂度是O(N)因为要一次往后挪动但是单链表是O(1),大大节省了程序运行时间。
2、 顺序表每次需要增容到后期增容很大的时候需要拷贝数据、开辟新空间、释放旧空间。会有不小的损耗。链表直接开辟一个结构体大小的空间即可。
3、增容一般是两倍但是我就想多插入几个仅此而已会造成空间的大规模浪费。链表同样更加简单且占用空间小。
1.3 链表的结构表示
首先要给大家介绍一下就是链表中的结点是一个结构体结点中一个变量是存储数据的另一个变量是存储结构体地址的上一个结点存下一个结点的地址从而链接起来。
1.3.1 链表的结构形式 1.3.2 链表的结构性质
1、从上图可以看出链表在逻辑上是连续的在物理地址上是不连续的
2、现实的结点是动态内存在堆区申请出来的
3、堆上申请的空间是按照一定的规律来的有些可能相同有些可能不同。
1.4 单链表的实现
1.4.1 单链表的创建
上文我们提到了结点是一个结构体第一个结构体变量是存储数据的第二个是存储下一个链表的地址的
typedef int SListDataType;typedef struct SListNode
{SListDataType data;struct SListNode* next;
}SLTNode; 1.4.2 单链表的打印
void PrintSList(SLTNode* phead)
{SLTNode* cur phead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL);
}为什么是这样子打印的给大家说一下思想
1、单链表定义了最后一个链表的地址为空指针所以我们就定义了一个cur来遍历整个链表
2、每找到一个数据我们就打印然后遍历链表指针cur就往后走一步 怎么走是不是next中存放了下一个结点的地址那么把cur管理的结构体中next的地址赋值给cur是不是相当于向后走了一步。
1.4.3 单链表的动态内存申请
SLTNode* BuySLTNode(SListDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-data x;newnode-next NULL;return newnode;
} 比方说我想申请一块动态内存空间里面存储x的值那么这个时候就通过malloc在堆上申请一块空间交给newnode管理这时候把newnode中data的值赋值为xnewnode中next的值赋值为NULL后返回这块空间的地址。这是不是就很好的开辟了一个结点。如果开辟失败了就返回空指针。
1.4.4 单链表的头插
void SListPushFront(SLTNode** pphead, SListDataType x)
{SLTNode* newnode BuySLTNode(x);assert(newnode);newnode-next *pphead;*pphead newnode;
}
这里我们用newnode来管理开辟的新结点如果开辟了失败了就不用往下了开辟成功了往下走我画个图来帮助大家理解上面代码的意思 1.4.5 单链表的尾插
我先给大家介绍一下尾插有两种情况第一种空链表第二种非空链表
先分析第一种情况如果是空链表是不是直接把newnode的地址给pphead是不是就可以了
第二种情况我给大家画个图一起来分析
void SListPushBack(SLTNode** pphead, SListDataType x)
{SLTNode* newnode BuySLTNode(x);//空链表if (*pphead NULL){*pphead newnode;return;}//非空链表SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;
}
第二种情况首先我们要尾插是不是要先找尾部在哪里尾部在哪里是不是说tail-next是空指针这个就是链表中最后一个元素了找到了之后就把tail-next存newnode的地址就可以。 1.4.6 单链表的头删
给大家说一下啊如何删除单链表中的数是不是只需要让上个结点存下下个结点的地址就好了。
那么头删就是让*pphead指向下下个结点然后释放第一个结点就好了。
那么应该这么做看代码
void SListPopFront(SLTNode** pphead)
{assert(*pphead);//链表只有一个值SLTNode* cur *pphead;*pphead cur-next;free(cur);cur NULL;
}
画个图给大家理解一下 1.4.7 单链表的尾删
尾删就更简单了还是第一步找尾第二部释放空间即可。
void SListPopBack(SLTNode** pphead)
{assert(*pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLTNode* cur *pphead;while (cur-next-next ! NULL){cur cur-next;}free(cur-next);cur-next NULL;}
}
1.4.8 单链表的查找
在单链表中查找一个数找到了就返回这个结点的地址没找到就返回空指针。
SLTNode* SListFind(SLTNode* pphead, SListDataType x)
{assert(pphead);SLTNode* cur pphead;while (cur){if (cur-data x)return cur;elsecur cur-next;}return NULL;
}
1.4.9 单链表的任意位置插入的前插
void SListInsertbefore(SLTNode** pphead, SLTNode* pos, SListDataType x)
{if (*pphead NULL){SListPushFront(pphead, x);}//在pos前插入else{SLTNode* newnode BuySLTNode(x);SLTNode* cur *pphead;while (cur-next ! pos){cur cur-next;}cur-next newnode;newnode-next pos;}
}
首先啊如果pphead没有值那么就相当于头插如果链表中有值画个图给大家理解 1.4.10 单链表任意位置的删除
void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(*pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLTNode* cur *pphead;while (cur-next ! pos){cur cur-next;}cur-next pos-next;free(pos);pos NULL;}
}
2.单链表的完整代码
2.1 test.c测试函数代码
#include SList.h
SLTNode* Phead NULL;
void Test1()
{//该函数测试头插和尾插SListPushFront(Phead, 1);SListPushFront(Phead, 2);SListPushFront(Phead, 3);SListPushFront(Phead, 4);SListPushFront(Phead, 5);SListPushBack(Phead, 2);SListPushBack(Phead, 3);SListPushBack(Phead, 4);PrintSList(Phead);
}void Test2()
{//该函数测试头删和尾删SListPushFront(Phead, 1);SListPopBack(Phead);PrintSList(Phead);
}
void Test3()
{//查找SListPushFront(Phead, 1);SListPushFront(Phead, 2);SListPushFront(Phead, 3);SListPushFront(Phead, 4);SLTNode* find SListFind(Phead, 3);if (find)find-data 30;PrintSList(Phead);
}
void Test4()
{//任意位置插入前插SListPushFront(Phead, 1);SListPushFront(Phead, 2);SListPushFront(Phead, 3);SListPushFront(Phead, 4);SLTNode* find1 SListFind(Phead, 3);SLTNode* find2 SListFind(Phead, 4);if (find1){SListInsertbefore(Phead, find1, 40);SListEraseafter(find2);SListEraseafter(find1);}PrintSList(Phead);
}
int main()
{Test1();//Test2();//Test3();//Test4();return 0;
}
2.2 SList.h函数声明代码
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.htypedef int SListDataType;typedef struct SListNode
{SListDataType data;struct SListNode* next;
}SLTNode;void PrintSList(SLTNode* phead);
//头插
void SListPushFront(SLTNode** pphead, SListDataType x);
//尾插
void SListPushBack(SLTNode** pphead, SListDataType x);
//头删
void SListPopFront(SLTNode** pphead);
//尾删
void SListPopBack(SLTNode** pphead);
//查找
SLTNode* SListFind(SLTNode* pphead, SListDataType x);
//在pos之后插入x
void SListInsertbefore(SLTNode** pphead,SLTNode* pos, SListDataType x);
//在pos之后插入x
void SListInsertafter(SLTNode* pos, SListDataType x);
//删除pos位置上的值
void SListErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的位置
void SListEraseafter(SLTNode* pos);2.3 SList.c函数实现代码
#include SList.h
void PrintSList(SLTNode* phead)
{SLTNode* cur phead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL);
}SLTNode* BuySLTNode(SListDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-data x;newnode-next NULL;return newnode;
}
void SListPushFront(SLTNode** pphead, SListDataType x)
{SLTNode* newnode BuySLTNode(x);assert(newnode);newnode-next *pphead;*pphead newnode;
} void SListPushBack(SLTNode** pphead, SListDataType x)
{SLTNode* newnode BuySLTNode(x);//空链表if (*pphead NULL){*pphead newnode;return;}//非空链表SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;
}void SListPopFront(SLTNode** pphead)
{assert(*pphead);//链表只有一个值SLTNode* cur *pphead;*pphead cur-next;free(cur);cur NULL;
}void SListPopBack(SLTNode** pphead)
{assert(*pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLTNode* cur *pphead;while (cur-next-next ! NULL){cur cur-next;}free(cur-next);cur-next NULL;}
}SLTNode* SListFind(SLTNode* pphead, SListDataType x)
{assert(pphead);SLTNode* cur pphead;while (cur){if (cur-data x)return cur;elsecur cur-next;}return NULL;
}
void SListInsertbefore(SLTNode** pphead, SLTNode* pos, SListDataType x)
{if (*pphead NULL){SListPushFront(pphead, x);}//在pos前插入else{SLTNode* newnode BuySLTNode(x);SLTNode* cur *pphead;while (cur-next ! pos){cur cur-next;}cur-next newnode;newnode-next pos;}
}void SListInsertafter(SLTNode* pos, SListDataType x)
{assert(pos);//只有一个SLTNode* newnode BuySLTNode(x);newnode-next pos-next;pos-next newnode;
}void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(*pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLTNode* cur *pphead;while (cur-next ! pos){cur cur-next;}cur-next pos-next;free(pos);pos NULL;}
}void SListEraseafter(SLTNode* pos)
{assert(pos);assert(pos-next);SLTNode* cur pos-next;pos-next cur-next;free(cur);cur NULL;
}总结
1、单链表其实不难大家一定要搞清楚指针和结构体
2、一定要动手实践一下
3、其实数据结构就是围绕着数据的增删查改显示这几个点所以一定要搞清楚每一个代码实现的逻辑。 如果这份博客对大家有帮助希望各位给小马一个大大的点赞鼓励一下如果喜欢请收藏一下谢谢大家 制作不易如果大家有什么疑问或给小马的意见欢迎评论区留言。
