淘宝联盟的网站怎么做,牡丹江到林口火车时刻表,wordpress积分与奖励,wordpress情侣主题快乐的流畅#xff1a;个人主页 个人专栏#xff1a;《算法神殿》《数据结构世界》《进击的C》 远方有一堆篝火#xff0c;在为久候之人燃烧#xff01; 文章目录 引言一、顺序表的问题二、链表的概念三、单链表的模拟实现3.1 定义3.2 打印3.3 创建新节点3.4 头插3.5 尾插3… 快乐的流畅个人主页 个人专栏《算法神殿》《数据结构世界》《进击的C》 远方有一堆篝火在为久候之人燃烧 文章目录 引言一、顺序表的问题二、链表的概念三、单链表的模拟实现3.1 定义3.2 打印3.3 创建新节点3.4 头插3.5 尾插3.6 头删3.7 尾删3.8 查找与修改3.9 指针断言3.10 指定插入3.11 指定删除3.12 销毁 引言
数据结构世界——单链表Single Linked List
一、顺序表的问题
让我们回顾一下顺序表
中间/头部的插入删除时间复杂度为O(N)增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。
那么如何解决以上问题呢
二、链表的概念
链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 链表的结构跟火车车厢相似将火车里的某节车厢去掉/加上不会影响其他车厢每节车厢都是独立存在的。车厢是独立存在的且每节车厢都有车门。想象一下这样的场景假设每节车厢的车门都是锁上的状态需要不同的钥匙才能解锁每次只能携带一把钥匙的情况下如何从车头走到车尾最简单的做法每节车厢里都放一把下一节车厢的钥匙。 在链表里每节“车厢”是怎样的呢 与顺序表不同的是链表的每节车厢都是独立申请下来的空间我们称之为结点/节点。节点的组成主要有两个部分当前节点要保存的数据和保存下一个节点的地址指针变量。
图中指针变量 plist保存的是第一个节点的地址我们称plist此时“指向”第一个节点如果我们希望plist“指向”第二个节点时只需要修改plist保存的内容为0x0012FFA0。 为什么还需要指针变量来保存下一个节点的位置
链表中每个节点都是独立申请的即需要插入数据时才去申请一块节点的空间我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。
三、单链表的模拟实现
3.1 定义
//单链表
typedef int SLDataType;
typedef struct SListNode
{SLDataType data;struct SListNode* next;
}SLNode;在结构体内嵌套结构体一定要表明struct而不能直接使用typedef后的名称
3.2 打印
先来看看怎么实现链表的打印这样更有助于我们理解它的结果。
void SLPrint(SLNode* phead)
{SLNode* cur phead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}先用cur指针接受头部地址当cur不为NULL时则打印当前节点的数据并将该节点存储的下一节点的地址赋值给cur这样cur指针就能一直访问整个链表直到最后一个节点该节点存储地址为NULL 3.3 创建新节点
每次插入要生成新节点申请空间……一系列操作 所以我们可以把它该过程写成一个函数以增强函数的复用性。
SLNode* BuySLNode(SLDataType x)
{SLNode* newnode (SLNode*)malloc(sizeof(SLNode));if (newnode NULL){perror(malloc fail);return;}newnode-data x;newnode-next NULL;return newnode;
}malloc动态开辟内存生成一个新节点再将数据放入新节点中初始地址为NULL
3.4 头插
void SLPushFront(SLNode** pphead, SLDataType x)
{assert(pphead);SLNode* newnode BuySLNode(x);newnode-next *pphead;*pphead newnode;
}先创建新节点再将新节点链接在链表头部更新链表指针 可能很多人有疑惑为什么要用二级指针呢请看接下来的测试 与顺序表不同的是我们不再创建结构体而是创建结构体指针初始指向NULL。那么我们要在函数内改变外部指针指向的地址就要使用二级指针。
3.5 尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{assert(pphead);//1.空链表//2.非空链表SLNode* newnode BuySLNode(x);if (*pphead NULL){*pphead newnode;}else{SLNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}如果为空链表则直接将新节点的地址传给外部的链表指针如果为非空链表先申请新节点再用循环一直向后访问找到最后一个节点的地址将新节点链接在最后
3.6 头删
void SLPopFront(SLNode** pphead)
{assert(pphead);assert(*pphead);SLNode* cur *pphead;*pphead (*pphead)-next;free(cur);
}将链表指针的地址改成第二个节点的并将第一个节点的空间释放
3.7 尾删
void SLPopBack(SLNode** pphead)
{assert(pphead);assert(*pphead);//一个节点//多个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLNode* tail *pphead;while (tail-next-next){tail tail-next;}free(tail-next);tail-next NULL;
}如果为一个节点直接释放空间并赋值为NULL如果有多个节点找到倒数第二个节点解引用将其next指针指向的空间最后一个节点释放再赋值为NULL
3.8 查找与修改
SLNode* SLFind(SLNode* phead, SLDataType x)
{SLNode* cur phead;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;
}找到返回对应节点的地址找不到返回NULL能查找也意味着能修改因为我们获取了该节点的地址自然能在外部解引用修改数据这样一个函数就有两个功能 ——查找和修改
3.9 指针断言
这里说一下关于assert断言的情况 并不是所有函数参数的指针都需要断言而是要根据实际情况分析而定。 //打印
void SLPrint(SLNode* phead);
//查找
SLNode* SLFind(SLNode* phead, SLDataType x);打印与查找则不需要断言因为空链表也可以打印也可以查找就比如你的银行账户没有钱就不能显示出来看看不能查询吗 //头插
void SLPushFront(SLNode** pphead, SLDataType x);
//尾插
void SLPushBack(SLNode** pphead, SLDataType x);头插与尾插对于其二级指针需要断言一级指针不用因为pphead指向链表指针plist所以不能为空而链表指针可为空即为空链表。 //头删
void SLPopFront(SLNode** pphead);
//尾删
void SLPopBack(SLNode** pphead);头删与尾删其二级指针与一级指针都要断言除了pphead不能为空*pphead也不能为空因为空链表就不能进行删除操作。
3.10 指定插入
这里有两种插入方式在pos前插入和在pos后插入 。
在pos前插入
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{assert(pphead);assert(pos);if (pos *pphead){SLPushFront(pphead, x);}else{SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLNode* newnode BuySLNode(x);newnode-next pos;prev-next newnode;}
}如果pos为头部地址时即为头插可复用头插函数如果pos不为头部地址时再找到pos前一个节点的地址然后创建新节点最后将它们链接起来 在pos后插入
void SLInsertAfter(SLNode* pos, SLDataType x)
{assert(pos);SLNode* newnode BuySLNode(x);newnode-next pos-next;pos-next newnode;
}相比于在pos前插入单链表其实更适合在pos后插入直接创建新节点进行链接即可
ps链接的过程有顺序问题不能写反了要不然会环状链接。
3.11 指定删除
这里也有两种删除方式在pos删除和在pos后删除。
在pos删除
void SLErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(pos);if (pos *pphead){SLPopFront(pphead);}else{SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);}
}如果pos为头部地址时即为头删可复用头删函数如果pos不为头部地址时再找到pos前一个节点的地址链接pos后一个节点再释放pos节点空间 在pos后删除
void SLEraseAfter(SLNode* pos)
{assert(pos);assert(pos-next);SLNode* next pos-next;pos-next pos-next-next;free(next);
}相比于在pos位置删除单链表其实更适合在pos后删除这里用一个next指针保存pos下一个节点的地址在pos链接往后第二个节点后再对next节点空间释放
3.12 销毁
void SLDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur *pphead;while (cur){SLNode* next cur-next;free(cur);cur next;}*pphead NULL;
}在每次循环内临时创建一个新指针next记录下一个节点的地址让cur释放所指空间后还可以找到下一个节点最后把链表指针解引用置空 当然这里你也可以传一级指针不在函数内部把外部的链表指针置为NULL而在外部手动置空跟free函数的用法一样实现半自动。
void SLDestroy(SLNode* phead)
{SLNode* cur phead;while (cur){SLNode* next cur-next;free(cur);cur next;}
}真诚点赞手有余香
