网站建设前景,国内做网站比较好的公司有哪些,辽宁省住房和城乡建设厅网站进不去,阿里云主机如何搭建wordpress目录
什么是单向链表
顺序表和链表的区别和联系
顺序表#xff1a;
链表#xff1a;
链表表示(单项)和实现
1.1 链表的概念及结构
1.2单链表(无头)的实现
所用文件
将有以下功能#xff1a;
链表定义
创建新链表元素
尾插
头插
尾删
头删
查找-给一个节点的…目录
什么是单向链表
顺序表和链表的区别和联系
顺序表
链表
链表表示(单项)和实现
1.1 链表的概念及结构
1.2单链表(无头)的实现
所用文件
将有以下功能
链表定义
创建新链表元素
尾插
头插
尾删
头删
查找-给一个节点的指针
改
pos位置之前插入
删除pos位置的值
成品展示
SList.h
SList.c
test.c 什么是单向链表
单向链表是一种常见的线性数据结构它由一系列节点组成每个节点包含两部分数据和指向下一个节点的指针。每个节点只能访问它后面的节点而不能访问前面的节点。
单向链表的特点
每个节点包含数据和指向下一个节点的指针。最后一个节点的指针指向空值NULL表示链表的结束。可以动态地添加或删除节点链表的长度可以根据需要进行扩展或缩小。可以根据指针迅速插入或删除节点而不需要移动其他节点。
单向链表相对于数组来说具有一些优点和缺点
优点插入和删除元素的时间复杂度为O(1)不需要像数组一样进行元素的移动链表长度可以动态调整没有固定大小的限制。缺点要访问特定位置的元素需要从头开始遍历时间复杂度为O(n)相比于数组在使用额外的指针存储下一个节点的信息会占用更多的内存空间。
由于单向链表的特点它常常被用于需要频繁插入和删除元素的场景或者在事先无法确定数据大小和数量的情况下使用。
顺序表和链表的区别和联系
顺序表
优点 空间连续、支持随机访问 缺点
中间或前面部分的插入删除时间复杂度O(N)2.增容的代价比较大。
链表
缺点 以节点为单位存储不支持随机访问 优点
任意位置插入删除时间复杂度为O(1)没有增容消耗按需申请节点空间不用了直接释放。
链表表示(单项)和实现
1.1 链表的概念及结构
概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表 中的指针链接次序实现的
1.2单链表(无头)的实现 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都 是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带 来很多优势实现反而简单了后面我们代码实现了就知道了。 所用文件
定义三个文件
头文件 SList.h函数的实现SList.c代码的测试test.c
将有以下功能
//打印链表
void SListPrint(SLTNode* phead);//创建新链表元素动态申请一个节点
SLTNode* BuySListNode(SLTDataType x);//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);//尾删
void SListPopBack(SLTNode** pphead);//头删
void SListPopFront(SLTNode** pphead);//查找-可在查找的基础上进行修改SListAlter
SLTNode* SListFind(SLTNode* phead,SLTDataType x);//改
void SListAlter(SLTNode* phead, SLTDataType x,SLTDataType y);//pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos);链表定义
定义链表基本结构
typedef struct SListNode
{int data;struct SListNode* next;
}SLTNode;创建新链表元素
创建新元素用于插入原链表
SLTNode* BuySListNode(SLTDataType x)
{//开辟空间SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));assert(newnode);newnode-data x;newnode-next NULL;return newnode;
}尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{//开辟空间SLTNode* newnode BuySListNode(x);if (*pphead NULL){//防止开始时节点为空*pphead newnode;}else{//找尾节点SLTNode* tail *pphead;//找到链表首元素while (tail-next ! NULL){//检索到未节点tail tail-next;}//插入tail-next newnode;}
}头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;//地址传给pphead //*ppheadplist/*头插无需检查是否为空*/
}尾删
void SListPopBack(SLTNode** pphead)
{assert(*pphead);if ((*pphead)-nextNULL){//1只有一个节点free(*pphead);*pphead NULL;}else{//2有多个节点//将前一个链元素中存放的地址换为NULL防止野指针/* 写法一 */SLTNode* tailPrev NULL;SLTNode* tail *pphead;while (tail-next!NULL){tailPrev tail;//tail的地址tail tail-next;}free(tail);tailPrev-next NULL;/* //写法二* //tail寻找的是倒数第二个元素while (tail-next-next!NULL){tail tail-next;}free(tail-next);tail-next NULL;*/}
}头删
void SListPopFront(SLTNode** pphead)
{ //防止被删空assert(*pphead);//找到首位链表元素SLTNode* next (*pphead)-next;//存储首元素存放下一个元素的地址free(*pphead);//释放首元素*pphead next;//将第二位元素改为首元素
}查找-给一个节点的指针
//无需更改元素故传一级指针
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead;while (cur){if (cur-datax)return cur;cur cur-next;}//未找到指定元素返回NULLreturn NULL;
}改
改元素是建立再查找基础之上进行更改
void SListAlter(SLTNode* phead, SLTDataType x, SLTDataType y)
{printf(修改成功:\n);//先找到相应元素再进行更改SLTNode* ret SListFind(phead, y);ret-data x;
}pos位置之前插入
任意位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//头插if (pos *pphead)SListPushFront(pphead, x);else{ //任意位置之前插入SLTNode* prev *pphead;while (prev-next!pos)//找到pos的位置{prev prev-next;//prev存放pos的地址}//找到位置SLTNode* newnode BuySListNode(x);//创建新链表元素并赋值prev-next newnode;//给前一个元素赋上下一元素地址newnode-next pos;//给插入元素存放下一个元素的地址}
}删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead pos)SListPopFront(pphead);//头删else{SLTNode* prev *pphead;while (prev-next ! pos)//找到pos的位置{prev prev-next;//prev存放pos的地址//移到pos前一位next存放的是pos的地址}//将prev存放的地址改为pos后一个元素的地址prev-next pos-next;//释放posfree(pos);pos NULL;}
}成品展示
SList.h
#pragma once#include stdlib.h
#include stdio.h
#include assert.htypedef int SLTDataType;typedef struct SListNode
{int data;struct SListNode* next;
}SLTNode;//打印链表
void SListPrint(SLTNode* phead);//创建新链表元素动态申请一个节点
SLTNode* BuySListNode(SLTDataType x);//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);//尾删
void SListPopBack(SLTNode** pphead);//头删
void SListPopFront(SLTNode** pphead);//查找-可在查找的基础上进行修改SListAlter
SLTNode* SListFind(SLTNode* phead,SLTDataType x);void SListAlter(SLTNode* phead, SLTDataType x,SLTDataType y);//pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos);SList.c
#include SList.h//打印
void SListPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur!NULL){printf(%d-, cur-data);cur cur-next;//存放下一个元素的地址}printf(NULL\n);
}//创建新链表元素
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));assert(newnode);newnode-data x;newnode-next NULL;return newnode;
}//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode BuySListNode(x);//dataif (*pphead NULL){//防止开始时节点为空*pphead newnode;}else{//找尾节点SLTNode* tail *pphead;while (tail-next ! NULL){//存放新节点地址tail tail-next;}tail-next newnode;}
}//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;//地址传给pphead //*ppheadplist/*头插无需检查是否为空*/
}//尾删
void SListPopBack(SLTNode** pphead)
{assert(*pphead);if ((*pphead)-nextNULL){//1只有一个节点free(*pphead);*pphead NULL;}else{//2有多个节点//将前一个链元素中存放的地址换为NULL防止野指针/* 写法一 */SLTNode* tailPrev NULL;SLTNode* tail *pphead;while (tail-next!NULL){tailPrev tail;//tail的地址tail tail-next;}free(tail);tailPrev-next NULL;/* //写法二* //tail寻找的是倒数第二个元素while (tail-next-next!NULL){tail tail-next;}free(tail-next);tail-next NULL;*/}
}//头删
void SListPopFront(SLTNode** pphead)
{ //防止被删空assert(*pphead);SLTNode* next (*pphead)-next;free(*pphead);*pphead next;
}//查找-给一个节点的指针
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead;while (cur){if (cur-datax)return cur;cur cur-next;}return NULL;
}//改
void SListAlter(SLTNode* phead, SLTDataType x, SLTDataType y)
{assert(phead);printf(修改成功:\n);SLTNode* ret SListFind(phead, y);ret-data x;
}
//pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//头插if (pos *pphead)SListPushFront(pphead, x);else{ SLTNode* prev *pphead;while (prev-next!pos)//找到pos的位置{prev prev-next;//prev存放pos的地址}//找到位置SLTNode* newnode BuySListNode(x);//创建新链表元素并赋值prev-next newnode;//给前一个元素赋上下一元素地址newnode-next pos;//给插入元素存放下一个元素的地址}
}//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead pos)SListPopFront(pphead);//头删else{SLTNode* prev *pphead;while (prev-next ! pos)//找到pos的位置{prev prev-next;//prev存放pos的地址//移到pos前一位next存放的是pos的地址}//将prev存放的地址改为pos后一个元素的地址prev-next pos-next;//释放posfree(pos);pos NULL;}
}test.c
test.c仅仅是用于测试代码本文以弄懂单向链表为主故不进行菜单制作 但改测试中也包含了对部分链表结构即原理进行了讲解请耐心看完
#include SList.h
void TestSList1()
{ SLTNode* n1 (SLTNode*)malloc(sizeof(SLTNode));assert(n1);SLTNode* n2 (SLTNode*)malloc(sizeof(SLTNode));assert(n2);SLTNode* n3 (SLTNode*)malloc(sizeof(SLTNode));assert(n3);SLTNode* n4 (SLTNode*)malloc(sizeof(SLTNode));assert(n4);n1-data1;n2-data2;n3-data3;n4-data4;n1-next n2;n2-next n3;n3-next n4;n4-next NULL;SListPrint(n1);
}void TestSList2()
{SLTNode* plist NULL;//传的是plist指针的地址//如果直接传plist将导致SLTNode* phead中//phead为临时拷贝不影响实参SListPushBack(plist, 1);SListPushBack(plist, 2);SListPushBack(plist, 3);SListPushBack(plist, 4);SListPrint(plist);//不改变无需传二级指针SListPushFront(plist,0);SListPrint(plist);SListPopFront(plist);SListPrint(plist);SListPopBack(plist);/*SListPrint(plist);SListPopBack(plist);SListPrint(plist);SListPopBack(plist);SListPrint(plist);SListPopBack(plist);SListPrint(plist);*//*SListPopBack(plist);SListPrint(plist);*/
}void TestSList3()
{SLTNode* plist NULL;//传的是plist指针的地址//如果直接传plist将导致SLTNode* phead中//phead为临时拷贝不影响实参SListPushBack(plist, 1);SListPushBack(plist, 2);SListPushBack(plist, 3);SListPushBack(plist, 4);SListPrint(plist);//不改变无需传二级指针//查找SLTNode* ret SListFind(plist, 3);if (ret){//返回值不为空则为找到printf(找到了\n);}SListPrint(plist);修改//SListAlter(plist, 20, 2);//SListPrint(plist);//插入SLTNode* pos SListFind(plist, 3);//先要找到再进行更改if (pos){SListInsert(plist, pos, 40);}SListPrint(plist);//删除pos SListFind(plist, 2);//先要找到再进行删除if (pos){SListErase(plist, pos);}SListPrint(plist);
}int main()
{TestSList3();return 0;
}单向链表讲解完毕啦创作不易如果喜欢请留下个赞吧感激不尽
