当我们在实际做项目,或者是自主开发一点小东西的时候,往往会储存一些数据,有时候我们需要添加这些数据,有时候需要删除,而有时候,仅仅只需要查找到就行。链表中的每一个节点都是一个独立开辟的空间,就像一个个的小箱子。那我们要如何将这些箱子串联起来呢?这时候,链表就发挥了作用。一个最基本的节点,应当如下图组成
typedef char x;
typedef struct SlistNote SlistNote;
struct SlistNote
{
x data;
SlistNote* next;
};
因为我们可能需要不断的改变数据的类型,所以在最初我们利用typedef来进行重定义。并且因为结构体指针每次创建名都太长,索性直接将名字进行替换
而上图最重要的,其实是结构体中的内容:1.数据。在这个节点中存放着相应的数据 2.指向下一个节点的地址。如上图的next,便是指向下一个节点的地址。
因此,当我们想使用一个链表的时候,我们其实只要找到第一个节点的地址就可以了。
那么,我们要如何实现链表的初始化,前插后插,前删后删,查询,定点操作呢?让我们一个一个来。
初始化
SListNote* SltBuyNote(SLT_type x)
{
SListNote* newnote = (SListNote*)malloc(sizeof(SListNote));
assert(newnote);
newnote->data = x;
newnote->next = NULL;
return newnote;
}
我们想要实现尾插和头插,需要先把要插入的节点准备好。以上代码,便是数据的初始化过程。先开辟出一片空间,并将这个空间的地址赋值给newnote这个指针。接着进行assert,避免前面的开辟空间失败进而导致后续的一系列错误。接着将数据进行赋值,暂时先把next指针定义为空指针,防止变成野指针,接着将刚刚创建的这个指针给return了。
尾插
void BackInsert(SListNote** pphead, SLT_type x)
{
SListNote* newnote = SltBuyNote(x);
if (*pphead == NULL)
{
*pphead = newnote;
}
else
{
SListNote* ppend = *pphead;
while (ppend->next)
{
ppend = ppend->next;
}
ppend->next = newnote;
}
}
当我们知道如何初始化节点以后,我们便可以开始一些基本的操作,比如尾插。在最开始,我们先创建出一个节点newnote,这个节点内部的数据就是我们要插入的数据。接着,我们判断一下被插入的节点的是否为空,若为空,则直接将newnote设置为初始节点,若不为空,那便先通过while循环找到ppend,也就是该结构体的末端。接着让结构体末端的next指针指向newnote,那便完成了尾插。
头插
void FrontInsert(SListNote** pphead, SLT_type x)
{
SListNote* newnote = SltBuyNote(x);
if (*pphead == NULL)
{
*pphead = newnote;
}
else
{
newnote->next = *pphead;
*pphead = newnote;
}
}
头插相比较于尾插要更简单一些,前面基本相似,在else这边,我们只需要把新节点的next指针指向*pphead,那其实就已经插上了。但是这样有一些错误,因为此时链表的头部已经发生改变,变成了newnote,因此,我们需要手动把节点地址改为newnote地址。
头删
void FrontDel(SListNote** pphead)
{
assert(pphead && *pphead);
SListNote* pcur = *pphead;
if (pcur->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
SListNote* pcur = *pphead;
*pphead = pcur->next;
free(pcur);
}
头删也是比较简单的,在头删函数中,我们首先需要先判断到底有没有数据,利用assert函数完成,如果有,再判断有几个数据,如果只有一个,那便是将头地址给删除,如果多于一个,那就将原先的头地址赋给一个值做备份,接着将头地址改变为下一个节点地址,再释放掉之前的头地址,即可完成头删。
尾删
void BackDel(SListNote** pphead)
{
assert(pphead && *pphead);
SListNote* pcur = *pphead;
if (pcur->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
while (pcur->next->next)
{
pcur = pcur->next;
}
free(pcur->next);
pcur->next->next = NULL;
pcur->next = NULL;
}
尾删前面几部类似于头删,如果已经确定有大于1个的数据,那就利用while精确定位到最后一个数据处,接着释放掉最后一个数据的地址并赋NULL值。
指定位置删除
void PosDel(SListNote** pphead, int pos)
{
int count = 0;
SListNote* pcur = *pphead;
assert(pphead && *pphead);
if (pos == 0)
{
FrontDel(pphead);
}
else
{
while (pcur)
{
pcur = pcur->next;
count++;
}
pcur = *pphead;
count = 0;
while (count < pos - 1)
{
pcur = pcur->next;
count++;
}
SListNote* ppos = pcur->next;
pcur->next = pcur->next->next;
free(ppos);
ppos = NULL;
}
}
我们先断言待删链表不是空链表,接着看待删位置是不是首节点,如果是首节点,那么直接执行头删,如果不是,则接着进行下一步。通过while循环找到pos位置处的节点,接着将这个节点的上一个节点的next指针连接到pos位置的下一个节点,接着删除pos位置处的节点,将其free掉。
指定位置插入
指定位置插入分为前插和后插,不同的插入方式需要不同的代码来实现
前插:
void FrontPosInsert(SListNote** pphead, int pos, SLT_type x)
{
SListNote* newnote = SltBuyNote(x);
if (*pphead == NULL)
{
*pphead = newnote;
}
else
{
if (pos == 0)
{
FrontInsert(pphead, x);
}
else
{
SListNote* pcur = *pphead;
int count = 0;
while (count != pos-1)
{
pcur = pcur->next;
count++;
if (pcur == NULL)
{
printf("不在可执行范围内!");
return 0;
}
}
SListNote* ppos = pcur->next;
pcur->next = newnote;
newnote->next = ppos;
}
}
}
先创建一个节点newnote,接着判断链条是否为空链条,若是空链条,则将*pphead直接赋一个newnote,若不是,则开始判断pos的数值,若pos为0的话,那么就执行前插函数,若pos不为0,则在进行下一步。先找到pos所代表的节点的前一个节点,接着继续判断,若该节点已经超过已有的节点,则进行提醒并直接返回,当然,你也可以选择进行一次后插。若该pos符合以上规则,则开始进行插入。
后插
void BackPosInsert(SListNote** pphead, int pos, SLT_type x)
{
SListNote* newnote = SltBuyNote(x);
if (*pphead == NULL)
{
*pphead = newnote;
}
else
{
SListNote* pcur = *pphead;
int count = 0;
while (count != pos)
{
pcur = pcur->next;
count++;
if (pcur == NULL)
{
printf("不在可执行范围内!");
return 0;
}
}
SListNote* ppos = pcur->next;
pcur->next = newnote;
newnote->next = ppos;
}
}
尾插与头插大体相似,在一些细节处略微改动,例如在后续找pos位置时,我们找到的是pos的位置,而之前是找到pos前面一个节点,这方面略有不同。其他大体相同。
查找节点
void Finding(SListNote** pphead, SLT_type x)
{
assert(pphead && *pphead);
SListNote* pcur = *pphead;
int count = 0;
while (pcur)
{
if (pcur->data == x)
{
printf("找到了!在%d处\n", count);
return;
}
count++;
pcur = pcur->next;
}
printf("没找到");
}
查找节点并不难,用到的方法和之前许多代码相似,可大致看看上图。
摧毁链表
void Sli_destory(SListNote** pphead)
{
assert(pphead && *pphead);
SListNote* pcur = *pphead;
while (pcur)
{
SListNote* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
首先我们也还是先断言一下节点地址的存在性,接着从头到尾一个节点一个节点的去删除,为了方便显示,我在最后又让首节点显示了个NULL,已证明已经删除完成。