网站备案前置审批表格,wordpress 自动提交表单,邢台信息港欢迎您,网站标题前的小图标怎么做文章目录
前言
一、单链表的概念与结构
1.概念
2.结点
3.性质
二、实现单链表
1.结构的定义
2.链表的打印和结点的申请
3.单链表的尾插和头插
4.单链表的尾删和头删
5.单链表的查找
6.指定位置之前插入数据和指定位置之后插入数据
7.删除pos结点和删除pos之后的结…
文章目录
前言
一、单链表的概念与结构
1.概念
2.结点
3.性质
二、实现单链表
1.结构的定义
2.链表的打印和结点的申请
3.单链表的尾插和头插
4.单链表的尾删和头删
5.单链表的查找
6.指定位置之前插入数据和指定位置之后插入数据
7.删除pos结点和删除pos之后的结点
8.单链表的销毁 总结 前言
各位好久不见今天我将给大家更新线性表中的单链表内容较多希望大家能耐心地看完这篇博客。话不多说接下来我详细介绍单链表。 一、单链表的概念与结构
1.概念 概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 就比如在生活中我们坐火车去景点游玩而火车就是一节一节的淡季时车次的车厢会相应减少旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉加上不会影响其他车厢每节车厢都是独立存在的。 在链表里每节“车厢”是什么样的呢
链表大致如图所示链表是由一个一个结点前后相互连接而组成的。前一个节点通过存储后一个节点的地址来找到后一个节点接下来细说结点的内容。 2.结点 定义与顺序表不同的是链表里的每节车厢都是独立申请下来的空间我们称之为“节点/结点”。 结点有两个组成部分1.保存的数据 2.保存下一个结点的地址指针变量 在上图中指针 变量 plist 保存的是第一个结点的地址我们称 plist 此时“指向”第一个结点如果我们希望 plist “指向”第二个结点时只需要修改 plist 保存的内容为 0x0012FFA0 。 链表中每个结点都是独立申请的即需要插入数据时才去申请一块结点的空间我们需要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。 对单链表中一个结点的结构体的定义 typedef int SLTDataType;
//定义链表结点的结构
typedef struct SListNode
{SLTDataType data;//存储的数据struct SListNode* next;//下一个结点的地址
}SLTNode;//结点结构体的名字,起方便的作用 3.性质 1、链式机构在逻辑上是连续的在物理结构上不一定连续 2、结点一般是从堆上申请的 3、从堆上申请来的空间链表的节点是malloc来实现是按照⼀定策略分配出来的每次申请的空间可能连续可能不连续 4、当我们想要保存一个整型数据时实际是向操作系统申请了一块内存这个内存不仅要保存整型数据也需要保存下一结点的地址当下一个结点为空时保存的地址为空。 5、当我们想要从第一个结点走到最后一个结点时只需要在当前结点拿上下一个结点的地址就可以了。 二、实现单链表
1.结构的定义
在上面已介绍单链表中结点的结构定义我们直接实现即可
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;
2.链表的打印和结点的申请
链表的打印
写打印的函数时函数名取为SLTPrint创建一个指针变量pcur让其从链表的头结点开始遍历可避免指针在指向下个一个结点的时候把头结点给丢失。
void SLTPrint(SLTNode* phead)
{SLTNode* pcur phead;while (pcur!NULL){printf(%d -, pcur-data);pcur pcur-next;//指向下一个结点}printf(NULL\n);//表示最后一个结点的下一个结点为NULL
}
结点的申请
在顺序表中空间满就需要进行扩容而在链表中结点的申请也是这种类似的效果。因此我们需要对链表进行一个结点一个结点的增加来进行扩容。
在写结点的申请的函数时函数名取为SLTBuyNode (向操作系统买下来一个结点进行扩容) 在上面单链表的性质中我们可知创建新结点需要用malloc来实现如果新结点NULL 就申请失败就退出反之申请成功就让存储的数据 (node-data) 为x下一个结点的地址(node-next)为NULL最后直接返回node即可。
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node (SLTNode*)malloc(sizeof(SLTNode));if (node NULL){perror(malloc fail!\n);exit(1);}node-data x;node-next NULL;return node;
}
3.单链表的尾插和头插
尾插
尾插是在最后一个结点的后面插入一个有效数据。先在插入数据之前先向空间申请一个结点大小调用SLTBuyNode()即可。再判断链表是否为空为空就直接插入即头结点就是新结点不为空就创建一个变量指针 pcur 从头开始遍历走到尾结点就让尾结点的下一个结点指向新结点(pcur-nextnewnode)。 void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode SLTBuyNode(x);if (*pphead NULL){*pphead newnode;}else {//当链表是非空找尾结点SLTNode* pcur *pphead;while (pcur-next!NULL){pcur pcur-next;}pcur-next newnode;}}
头插
头插是在第一个结点前面插入一个数据使数据指向第一个结点从而变成新的头结点。先操作系统申请一个结点调用SLTBuyNode()即可先让新结点的下一个结点指向原来的头结点这样原来的头结点直接变成新结点所以让新结点变成头结点即可。 void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);//断言一下避免链表为空的情况下进行操作SLTNode* newnode SLTBuyNode(x);newnode-next *pphead;*pphead newnode;
} 4.单链表的尾删和头删
尾删
尾删是在一串结点里把最后一个结点进行删除(释放)并使倒数第二个结点指向NULL。先判断链表有一个结点和多个结点的情况有一个结点时直接对头结点进行释放再置为NULL有多结点时创建两个指针一个 prev 用来保存尾结点的前一个结点一个 ptail 从头开始遍历走到尾结点对尾结点进行释放再置为NULL。 void SLTPopBack(SLTNode** pphead)
{assert(pphead* pphead);//只有一个结点的情况if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else {//多结点的情况SLTNode* prev NULL;SLTNode* ptail *pphead;while (ptail-next){prev ptail;ptail ptail-next;}prev-next NULL;free(ptail);ptail NULL;}
} 头删
头删是在一串结点里把先把第二个结点保存下来再对第一个结点进行释放并置NULL。先创建一个指针next用next对头结点的下一个结点进行保存再对头结点直接释放置为NULL最后让头结点的下一个结点直接变成新的头结点。 void SLTPopFront(SLTNode** pphead)
{assert(pphead* pphead);SLTNode* next (*pphead)-next;free(*pphead);*pphead next;
} 5.单链表的查找
创建指针pcur让pcur从头开始遍历判断pcur指向的数据与查找的数据是否相同如果相同就返回当前的节点如果不相同让pcur指向下一个节点循环结束完成都没找到则返回NULL。
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur phead;while (pcur ! NULL){if (pcur-data x){return pcur;}pcur pcur-next;}//未找到return NULL;
} 6.指定位置之前插入数据和指定位置之后插入数据
指定位置之前插入数据
创建两个指针一个是prev从头开始遍历一个是pos指定的位置先判断头结点是不是指定位置是就调用头删的函数不是就让prev从头开始遍历直到prev-next为pos时就停止遍历再让新节点的next指向pos,避免pos丢失后让prev-next指向新节点。 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead pos);//当pos就是头结点时相当于头插if (pos *pphead){SLTPushFront(pphead, x);//调用头插的函数}else {SLTNode* newnode SLTBuyNode(x);SLTNode* prev *pphead;while (prev-next!pos){prev prev-next;}newnode-next pos;prev-next newnode;}
} 指定位置之后插入数据
在指定位置之后插入数据之前先创建一个指针pos指定位置不需要从头开始遍历直接让新节点的next指向pos的next再让pos的next指向newnode。 void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode SLTBuyNode(x);//是在指定位置之后插入因此是指向pos-nextnewnode-next pos-next;pos-next newnode;
}
7.删除pos结点和删除pos之后的结点
删除pos结点
创建两个指针一个是prev从头遍历一个是pos指定位置先判断头结点是不是指定位置是指定位置就调用头删的函数不是指定位置就再让prev从头开始遍历当prev-next等于pos时停止循环开始对指定位置进行删除再删除之前先对pos-next进行保留避免丢失再对pos进行free后置为NULL。 void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead pos);if (pos *pphead){SLTPopFront(pphead);}else {SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}
删除pos之后的结点
创建一个指针pos直接对pos后面的节点进行销毁。先保存pos-next再对pos进行free后置为NULL。 void SLTEraseAfter(SLTNode* pos)
{assert(pos pos-next);SLTNode* del pos-next;pos-next del-next;free(del);del NULL;
}
8.单链表的销毁
创建两个指针一个是pucr从头开始遍历一个是next用来保存下一个结点。next要走到pcur的前面pcur用来销毁所在位置的next是用来保存pcur-next的。
void SListDestroy(SLTNode** pphead)
{SLTNode* pcur *pphead;while (pcur){SLTNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;//让头结点置为NULL这样才销毁彻底成功
} 总结
非常感谢大家阅读完这篇博客。希望这篇文章能够为您带来一些有价值的信息和启示。如果您有任何问题或建议欢迎在评论区留言我们一起交流学习。
