当前位置：首页 > news >正文

单链表的学习与基础运用p

news 来源：原创 2024/9/20 3:48:30

当我们在实际做项目，或者是自主开发一点小东西的时候，往往会储存一些数据，有时候我们需要添加这些数据，有时候需要删除，而有时候，仅仅只需要查找到就行。链表中的每一个节点都是一个独立开辟的空间，就像一个个的小箱子。那我们要如何将这些箱子串联起来呢？这时候，链表就发挥了作用。一个最基本的节点，应当如下图组成

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，已证明已经删除完成。