一键生成论文的网站,长春公司做网站,wordpress 标签下的文章,山东免费网站建设数据结构 | 单链表专题【详解】 文章目录 数据结构 | 单链表专题【详解】链表的概念及结构单链表的实现头文件打印尾插头插尾删头删查找在指定位置之前插入数据在指定位置之后插入数据删除pos节点删除pos之后的节点销毁链表 顺序表遗留下来的问题 中间/头部的插⼊删除#xff…数据结构 | 单链表专题【详解】 文章目录 数据结构 | 单链表专题【详解】链表的概念及结构单链表的实现头文件打印尾插头插尾删头删查找在指定位置之前插入数据在指定位置之后插入数据删除pos节点删除pos之后的节点销毁链表 顺序表遗留下来的问题 中间/头部的插⼊删除时间复杂度为O(N)增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。增容⼀般是呈2倍的增长势必会有⼀定的空间浪费。例如当前容量为100满了以后增容到 200我们再继续插入了5个数据后⾯没有数据插入了那么就浪费了95个数据空间。 那么如何解决以上问题呢 那这个时候我们就要开始我们的链表专题了~~ 链表的概念及结构 概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。 链表的结构跟火车车厢相似淡季时车次的车厢会相应减少旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上不会影响其他车厢每节车厢都是独立存在的。 车厢是独立存在的且每节车厢都有车门。想象一下这样的场景假设每节车厢的车门都是锁上的状态需要不同的钥匙才能解锁每次只能携带一把钥匙的情况下如何从车头走到车尾 最简单的做法每节车厢里都放一把下一节车厢的钥匙。
在链表里每节“车厢”是什么样的呢我们来看下面 与顺序表不同的是链表里的每节车厢都是独立申请下来的空间我们称之为“结点/节点” 节点的组成主要有两个部分当前节点要保存的数据和保存下一个节点的地址指针变量。 图中指针变量 plist保存的是第一个节点的地址我们称plist此时“指向”第一个节点如果我们希望plist“指向”第二个节点时只需要修改plist保存的内容为0x0012FFA0。 为什么还需要指针变量来保存下一个节点的位置 链表中每个节点都是独立申请的即需要插入数据时才去申请一块节点的空间我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。
结合前面学到的结构体知识我们可以给出每个节点对应的结构体代码
假设当前保存的节点为整型
struct SListNode
{int val;struct SListNode* next;
}当我们想要保存一个整型数据时实际是向操作系统申请了一块内存这个内存不仅要保存整型数据也需要保存下一个节点的地址当下一个节点为空时保存的地址为空。 当我们想要从第一个节点走到最后一个节点时只需要在前一个节点拿上下一个节点的地址下一个节点的钥匙就可以了。 给定的链表结构中如何实现节点从头到尾的打印 思考当我们想保存的数据类型为字符型、浮点型或者其他自定义的类型时该如何修改 补充说明 1、链式机构在逻辑上是连续的在物理结构上不一定连续 2、节点一般是从堆上申请的 3、从堆上申请来的空间是按照一定策略分配出来的每次申请的空间可能连续可能不连续
单链表的实现
我们老样子先来定义结构体要用的头文件引入~~
头文件
SList
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int SLNDataType;typedef struct SListNode
{SLNDataType val;struct SListNode* next;
}SLNode;我们要实现哪些功能呢
//打印
void SLTPrint(SLNode* phead);//尾插
void SLTPushBack(SLNode** pphead, SLNDataType x);//头插
void SLTPushFront(SLNode** pphead, SLNDataType x);//尾删
void SLTPopBack(SLNode** pphead);//头删
void SLTPopFront(SLNode** pphead);//查找
SLNode* SListFind(SLNode** phead, SLNDataType x);//在指定位置之前插入数据
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x);//删除pos节点
void SLTErase(SLNode** pphead, SLNode* pos);//在指定位置之后插入数据
void SLTInsertAfter(SLNode* pos, SLNDataType x);//删除pos之后的节点
void SLTEraseAfter(SLNode* pos);//销毁链表
void SListDesTroy(SLNode** pphead);好接下来我们开始实现~~ SList.c
打印
这个很好实现
void SLTPrint(SLNode* phead)
{//将头节点的地址保存到cur中SLNode* cur phead;while (cur ! NULL){printf(%d- , cur-val);//cur是保存下一个节点的地址cur cur-next;}printf(NULL\n);
}我们来测试一下这里链表中什么都没有我们可以自己手动创造几个数据
slttest1()
{//测试打印SLNode* node1 (SLNode*)malloc(sizeof(SLNode));node1-val 1;SLNode* node2 (SLNode*)malloc(sizeof(SLNode));node2-val 2;SLNode* node3 (SLNode*)malloc(sizeof(SLNode));node3-val 3;SLNode* node4 (SLNode*)malloc(sizeof(SLNode));node4-val 4;node1-next node2;node2-next node3;node3-next node4;node4-next NULL;SLNode* plist node1;SLTPrint(plist);
}可以看到是可以打印出来的~~ 尾插
这里的尾插是不是需要先申请空间然后再将申请出来的空间赋值还需要先判断链表为不为如果是空就将新开辟的空间赋给头
下面是代码
扩容我们后面可能还要用所以我们就给他分装成一个函数
//开辟空间
SLNode* CreateNode(SLNDataType x)
{//malloc一个新的空间SLNode* newnode (SLNode*)malloc(sizeof(SLNode));if (newnode NULL){perror(malloc fail);exit(-1);}//申请出来的空间直接赋值newnode-val x;//下一个next赋值为空newnode-next NULL;//返回一个新的空间return newnode;
} void SLTPushBack(SLNode** pphead, SLNDataType x)
{//这里申请空间SLNode* newnode CreateNode(x);//判断头是否为空如果为空就将新开辟的空间赋给头if (*pphead NULL){*pphead newnode;}else{//将头指向变量尾SLNode* tail *pphead;//找尾while (tail-next ! NULL){//找到了尾然后继续tail tail-next;}//把那个返回的空间赋值给尾的nexttail-next newnode;}
}头插
这里先申请节点然后让新的节点和头节点连接起来最后再让新的节点成为头节点这里如果链表为空也是可以完成任务的~~
void SLTPushFront(SLNode** pphead, SLNDataType x)
{//申请节点SLNode* newnode CreateNode(x);//让新节点跟头节点连接起来newnode-next *pphead;//让新的节点成为头节点*pphead newnode;
}可以看到头插~~ 尾删
首先找尾然而找尾就要找到前一个节点掷为空然后再进行free链表为空的时候不能尾删
void SLTPopBack(SLNode** pphead)
{assert(pphead);assert(*pphead);//当前链表只有一个节点的时候if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{//定义一个快慢指针SLNode* ptail *pphead;SLNode* prev NULL;//ptail的next不等于NULL就一直找while (ptail-next ! NULL){//将ptail的地址赋给慢指针prevprev ptail;//ptail继续往下找ptail ptail-next;}free(ptail);prev-next NULL;}
}头删
使用临时节点指向头节点然后将头节点指向新的头把临时指针指向的节点释放掉
void SLTPopFront(SLNode** pphead)
{assert(pphead);assert(*pphead);//定义一个临时指针将第二个节点赋值给临时指针SLNode* next (*pphead)-next;//释放头节点free(*pphead);//将临时节点变成头节点*pphead next;
}查找
这里我们传地址就是要保持接口的一致性所以我们这里写二级指针这里很简单不再介绍
SLNode* SListFind(SLNode** phead, SLNDataType x)
{assert(phead);SLNode* pcur *phead;while (pcur ! NULL){if (pcur-val x){return pcur;}pcur pcur-next;}return NULL;
}
在指定位置之前插入数据
在插入前我们要向申请一块空间先找到要插入的地方前一个节点处理前一个和后一个的连接关系~~链表不能为空pos也不能为空还要处理只有一个节点和只有一个节点的情况下直接将新申请下来的节点赋给头
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{assert(pphead);//链表不能为空pos也不能为空assert(pos);assert(*pphead);SLNode* node CreateNode(x);//处理只有一个节点和只有一个节点的情况下直接将新申请下来的节点赋给头if ((*pphead)-next NULL || pos *pphead){node-next *pphead;*pphead node;return;}SLNode* prev *pphead;//找pos的前一个节点while (prev-next ! pos){prev prev-next;}//连接node-next pos;prev-next node;
}在指定位置之后插入数据
这里可以直接申请空间后赋值然后直接连接~~
void SLTInsertAfter(SLNode* pos, SLNDataType x)
{assert(pos);SLNode* node CreateNode(x);//连接node-next pos-next;pos-next node;
}删除pos节点
首先找到前一个节点将next的指针指向下一个再把pos的节点删除~~当也要判断pos是不是头
void SLTErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//判断pos是不是头if (pos *pphead){*pphead (*pphead)-next;free(pos);return;}//找pos的前一个节点SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;
}删除pos之后的节点
首先要将pos的节点保存下来然后改变pos的指向最后释放
void SLTEraseAfter(SLNode* pos)
{assert(pos pos-next);SLNode* del pos-next;pos-next del-next;free(del);del NULL;
}销毁链表
销毁节点之前要把下一个节点保存起来然后找下一个free句许循环
void SListDesTroy(SLNode** pphead)
{assert(pphead);SLNode* pcur *pphead;while (pcur ! NULL){SLNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
} 好了以上就是单链表的所有内容了如果问题欢迎在评论区指正一起交流~~ 感谢大家的收看希望我的文章可以帮助到正在阅读的你
