素材搜集网站,中文网址的作用,在线设计平台代理,淘客软件自动做网站【数据结构篇】~链表 链表前言链表的实现1.头文件2.源文件 链表前言
链表是一种物理存储结构上非连续、非顺序的存储结构#xff0c;数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 1、链式机构在逻辑上是连续的#xff0c;在物理结构上不一定连续 2、结点一般是从… 【数据结构篇】~链表 链表前言链表的实现1.头文件2.源文件 链表前言
链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 1、链式机构在逻辑上是连续的在物理结构上不一定连续 2、结点一般是从堆上申请的 3、从堆上申请来的空间是按照一定策略分配出来的每次申请的空间可能连续可能不连续当我们想要保存一个整型数据时实际是向操作系统申请了一块内存这个内存不仅要保存整型数据也需要保存下一个结点的地址当下一个结点为空时保存的地址为空。 当我们想要从第一个结点走到最后一个结点时只需要在当前结点拿上下一个结点的地址就可以了。 如图 既然链表是有一个个节点组成的那我们就可以把它看成一个小火车
链表的实现
1.头文件
#pragma once
#include stdio.h
#includeassert.h
#includestdlib.h
typedef int sldatatype;//因为不知道要保存什么类型的数据
//定义节点的结构体
typedef struct slistnode {sldatatype data;//保存的数据struct slistnode* next;//指向下一个结构体的指针
}slnode;
void slprint(slnode* phead);
//打印链表(这里要传链表头的地址以确保能找到链表)
//phead的作用就和火车头差不多
slnode* slbuynode(sldatatype);//申请新节点
void slpushback(slnode** pphead, sldatatype x);
//尾插因为要通过函数改变数据所以就要传‘址’调用不能‘传值’
//所以这里是‘二级’指针
void slpushfornt(slnode** pphead, sldatatype x);//头插
void slpopback(slnode** pphead);//尾删
void slpopfornt(slnode** pphead);//头删
//查找
slnode* slfind(slnode* phead, sldatatype x);
//在指定位置之前插入数据
void slinsert(slnode** pphead, slnode* pos, sldatatype x);
//删除pos结点
void slerase(slnode** pphead, slnode* pos);
//在指定位置之后插入数据
void slinsertAfter(slnode* pos, sldatatype x);
//删除pos之后的结点
void sleraseAfter(slnode* pos);
//销毁链表
void sldestroy(slnode** pphead);2.源文件
#includeslist.h
//断言pphead的目的是不能对空地址进行解引用
void slprint(slnode* phead)//打印链表
{slnode* pcur phead;while(pcur){printf(%d-, pcur-data);//打印数据pcur pcur-next;//改变purc的指向让它指向下一个节点}printf(NULL\n);
}
slnode* slbuynode(sldatatype x)//申请新节点
{slnode* newnode (slnode*)malloc(sizeof(slnode));//一开辟空间就要检查是否开辟成功if (newnodeNULL){perror(malloc fail);}newnode-data x;newnode-next NULL;return newnode;
}
void slpushback(slnode** pphead,sldatatype x)//尾插(ppheadplist)
{ slnode* pcur *pphead;//既然要插入数据那么就要开辟新空间新节点slnode* newnode slbuynode(x);assert(pphead);if (*ppheadNULL)//如果是空链表plistnull{*pphead newnode;newnode-data x;}else//不是空链表{ while (pcur-next){pcur pcur-next;}newnode-data x;pcur-next newnode; }
}
void slpushfornt(slnode** pphead, sldatatype x)//头插
{//既然要插入数据那么就要开辟新空间新节点slnode* newnode slbuynode(x);assert(pphead);newnode-next *pphead;//为了把新结点和原来的链表连起来*pphead newnode;
}
void slpopback(slnode** pphead)//尾删
{//删除时pphead不能对null进行解引用和头节点不然没意义了都不能为空assert(pphead*pphead);if ((*pphead)-nextNULL)//只有一个节点{free(*pphead);(*pphead)-next NULL;}else{ slnode* ptail *pphead;slnode* prev NULL;while (ptail-next)//跳出循环时ptail就是最后一个节点{ prev ptail;ptail ptail-next;}prev-next NULL;free(ptail);ptail NULL;}
}
void slpopfornt(slnode**pphead)//头删
{//删除时pphead不能对null进行解引用和头节点不然没意义了都不能为空assert(pphead *pphead);slnode* node (*pphead)-next;//(-)的优先级大于*解引用所以要用free(*pphead);*pphead NULL;*pphead node;
}
//查找
//因为查找数据不需要改变链表内容所以这里传一级指针
slnode* slfind(slnode* phead, sldatatype x)
{assert(phead);//不能在空链表中查找数据slnode* node phead;while (node){if (x node-data){return node;}node node-next;}return NULL;
}
//在指定位置之前插入数据要改变的指针有pos的前驱节点和pos
void slinsert(slnode** pphead, slnode* pos, sldatatype x)
{assert(pphead);assert(pos);slnode* newnode slbuynode(x);if (pos *pphead)//pos是头节点就调用’头插‘{slpushfornt(pphead,x);}else//pos不是头节点{ slnode* prev *pphead;//定义pos的前一个节点以便连接while (prev-next!pos){prev prev-next;}//出循环就代表pos的前驱节点已找到newnode-next pos;prev-next newnode;}
}
//在指定位置之后插入数据
//在pos后插入数据要改变的指针有pos、pos-next
void slinsertAfter(slnode* pos, sldatatype x)
{assert(pos);slnode* newnode slbuynode(x);slnode* next pos-next;newnode-next pos-next;pos-next newnode;
}
//删除pos结点
//删除pos后改变的指针有pos的前驱节点和pos的next指针
void slerase(slnode** pphead, slnode* pos)
{assert(pphead pos);//不能删除空节点if (pos *pphead)//如果pos是头节点就进行头删{ slpopfornt(pphead);}else//不是头节点{slnode* prev *pphead;slnode* next pos-next;while(prev-next!pos){prev prev-next;}//出循环后找到了pos的前驱节点prev-next next;free(pos);pos NULL;}}//删除pos之后的结点
//删除pos之后的结点要改变的指针有pos和pos-next
void sleraseAfter(slnode* pos)
{assert(pos);slnode* del pos-next;pos-next pos-next-next;free(del);del NULL;
}
//销毁链表
void sldestroy(slnode** pphead)
{assert(pphead*pphead);//不能销毁空链表slnode* purc *pphead;while (purc){slnode* next purc-next ;free(purc);purc next; }//头节点还没销毁*pphead NULL;
}详解都在注释中哦
