数据结构之单链表
线性表
线性表的顺序存储结构,有着较大的缺陷
- 插入和删除操作需要移动大量元素。会耗费很多时间
- 增容需要申请空间,拷贝数据,释放旧空间。会有不小的消耗
- 即使是使用合理的增容策略,实际上还会浪费许多用不上的空间。如我只需要101个空间存放数据,而100进行2倍增容后有200个空间,这样实际上浪费了99块空间。
线性表的链式存储结构就可以解决这些问题,首先链式存储结构并不需要增容,而是使用多少数据申请多少空间,这一点就避免了时间和空间的浪费。
顺序存储结构和链式存储结构
存储方式
- 顺序存储结构,使用一段连续的空间依次存储数据
- 链式存储结构,使用一个个存储单元存放数据
时间性能
插入和删除
顺序存储结构,O(N)
链式存储结构,O(1)
空间性能
- 顺序存储结构,需要预分配空间,给小了不够用,给打了浪费
- 链式存储结构,不需要预分配空间,只要有新的元素插入才会开辟内存单元
使用场景
具体在什么场景使用不同的线性表存储结构呢?
若线性表需要频繁的查找,很少进行插入和删除操作时,可以采用顺序存储结构。
若线性表中的元素个数变化较大或不知道有多大时,可以采用链式存储结构。
- 单链表在插入和删除不需要移动元素,只需改变指针的指向即可。
单链表
概念:单链表是在物理存储结构上不连续,逻辑结构上连续的线性表。它是通过指针链接,就像火车的一节一节车厢一样通过挂钩链接在一起,车厢就是单链表的一个一个节点,里面用来存放数据。
而在单链表里“车厢”内有些什么的呢?单链表是一种数据结构“车厢”里肯定存放在数据,而单链表又是通过指针链接在以起,就像车厢的钩子一样链接,它在物理存储结构上不是连续的,所以“车厢”里还有一个指针变量用来存放下一节“车厢”的地址。
typedef int SLNodeDatatpye;
struct SListNode
{
SLNodeDatatpye data;//存放数据
struct SListNode* next;//存放单链表类型的指针
};
存放的数据类型:单链表不会只用来存放整形数据,这里只是以整形举例,所以需要对类型重命名,方便对后面的类型进行修改,需要修改数据类型的只需要动动 typedef int SLNodeDatatpye;
,这串代码。
功能实现
typedef int SLNodeDatatpye;
struct SListNode
{
SLNodeDatatpye data;
struct SListNode* next;
};
typedef struct SListNode SL;
//创建节点
SL* SLBuyNode(SLNodeDatatpye x);
//打印
void SLPrint(SL** pphead);
//头插
void SLPushFront(SL** pphead, SLNodeDatatpye x);
//尾插
void SLPushBack(SL** pphead, SLNodeDatatpye x);
//头删
void SLPopFront(SL** pphead);
//尾删
void SLPopBack(SL** pphead);
//查找,返回地址
SL* SLFind(SL** pphead, SLNodeDatatpye x);
//指定位置插入(之前)
void SLInsert(SL** pphead, SLNodeDatatpye x, SL* pos);
//删除pos之后的节点
void SLEraseBack(SL* pos);
//删除pos节点
void SLErase(SL** pphead, SL* pos);
//销毁链表
void SLDestory(SL** pphead);
创建节点和打印
实现单链表的功能第一步需要为它创建节点以用来存放数据。实现打印功能,将链表的数据打印出来方便更好的观查链表存储数据的情况,配合着调试功能可以更加完善的查找,观测在实现完一个功能,它执行的结果是否与预期相符合,若发生错误,又可以借助调试功能更好、更快的查找bug。
//创建节点
SL* SLBuyNode(SLNodeDatatpye x)
{
SL* newnode = (SL*)malloc(sizeof(SL));
if (newnode == NULL)
{
perror("malloc");
return;
}
newnode->data = x;
newnode->next = NULL;
return newnode;//忘记返回newnode的地址了
}
//打印
void SLPrint(SL** phead)
{
//assert(phead);
SL* pcur = phead;
while (pcur)//pcur != NULL
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
创建节点很容易理解,一个单链表的节点用来存放数据和下一个节点的地址,在创建节点时使用malloc函数开辟一个内存单元,然后判断开辟空间是否成功,接着将传递过来的参数放在 newnode->data = x;
里。
newnode->next = NULL;
置为空即可,这只是一个节点没有与其余节点有任何关联,借助插入函数来实现像火车一样一节一节车厢链接在一起的效果。
打印单链表时应注意:
循环体,单链表的循环通过next指针来实现,结束条件是最后一个节点的next指针为空。
pcur = pcur->next;
,通过 pcur->next
,赋值给 pcur
,来来遍历每一个节点。重述:将pcur的下一个节点的地址赋给pcur,此时pcur就等于下一个节点,直达循环到最后一个节点,在最后一个节点data == 4 ,pcur = pcur->next;
,为空指针将其赋给 pcur
,此时它为空指针,跳出循环。
查找数据
查找数据,为什么传递二级指针,这里是为了保持函数接口的一致性,后续实现的插入、删除、销毁操作都需要传递二级指针,同时也是减少对函数的混淆,当函数量较多时,这个函数传一级指针,另一个函数传递二级指针,四处分散,容易让使用者看了傻眼~。
//查找,返回地址
SL* SLFind(SL** pphead, SLNodeDatatpye x)
{
assert(*pphead && pphead);
SL* pcur = *pphead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
查找数据的基本的逻辑与打印类似,都需要使用循环遍历链表, 循环内增加了一个条件判断,用于判断这个节点的数据是否等于形参x,相等就说明找到了 “找到了”,将当前节点的地址返回即可,若跳出循环后还是没有找到对应的节点,将返回NULL,空指针。
assert断言是防止,传递过来的链表的节点是空指针,在函数内对进行解引用导致程序报错。
插入数据
在插入数据时需要考虑,插入的数据会对影响那些节点
特别注意的一点,插入数据会对单链表进行改变,在传递参数的时候需要对取pliat的地址,而plist又是一个指针变量,所以函数需要使用二级指针来接收。
节点 | 函数参数 |
---|---|
*plist(第一个节点) | **pphead |
plist(指向第一个节点的指针) | *pphead |
&plist(指向第一个节点的指针的地址) | pphead |
void test()
{
SL* plist = NULL;
SLPushFront(&plist, 1);
SLPushFront(&plist, 2);
}
//头插
void SLPushFront(SL** pphead, SLNodeDatatpye x)
{
assert(pphead);
SL* newnode = SLBuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//尾插
void SLPushBack(SL** pphead, SLNodeDatatpye x)
{
assert(pphead);
if (*pphead == NULL)
{
*pphead = SLBuyNode(x);
}
else
{
SL* pcur = *pphead;
while (pcur->next)
{
pcur = pcur->next;
}
pcur->next = SLBuyNode(x);
}
}
需要对头插、尾插分两种场景,一是没有节点,传递过来的是空链表,二是有节点,传递的不是空链表。
实现头插、尾插先认为传递的不是一个空链表,基于此来实现,然后对空链表的情况做出判断和处理。这样做会更容易上手,先实现最主要的功能,然后再检擦其完整性。
assert断言是防止,传递过来的链表的节点是空指针,在函数内对进行解引用导致程序报错。
头插:
- 需要创建一个节点,
SL* newnode = SLBuyNode(x);
,使用上述的函数创建一个新节点 - 将其放在链表的第一个位置,
newnode->next = *pphead;
,
- 将新插入的节点置为新的头(让*pphead指向新的节点),
*pphead = newnode;
。
千万别忘了,需要将*pphead置为新的头,否则此时,它指向的是下一个节点的位置,会影响到后续对链表的操作。
**最后取特殊情况:**当链表为空时,上述头插是否支持。很明显,我们将 *pphead == NULL
的情况带入头插函数,SL* newnode = SLBuyNode(x);
,第一步正常创建节点;newnode->next = *pphead;
,第二步正常,由于只有一个节点所以 newnode->next == NULL
,没有问题;*pphead = newnode;
,第三步将*pphead置为新的头,这步没有问题,也不存在对空指针解引用的情况。
最后通过运行代码观测:
尾插:
尾插同理,也是将链表默认不为空的情况实现。
- 想要进行尾插首先得有一个指针指向最后一个节点,然后将创建的新节点插入。
- 定义一个指针pcur,使用循环遍历到最后一个节点。
- 跳出循环,完成最后一步尾插代码~,
pcur->next = SLBuyNode(x);
。
当链表为空时,这不就是头插吗?!,这样我们使用一个if语句判断*pphead是否为空,为空就调用头插函数,不为空就循环到最后一个节点,然后插入~
指定位置插入:
指定位置插入实际上与尾插代码差别不大,就改变了跳出while循环的的条件。
//指定位置插入(之前)
void SLInsert(SL** pphead, SLNodeDatatpye x, SL* pos)
{
assert(pphead);
assert(pos);
SL* newnode = SLBuyNode(x);
SL* pcur = *pphead;
if (*pphead == pos)//这不就是头插吗?
{
newnode->next = pos;
*pphead = newnode;
}
else
{
while (pcur->next != pos)
{
pcur = pcur->next;
}
pcur->next = newnode;
newnode->next = pos;
}
}
首先想要实现指定位置插入,传入的链表和pos不可能为空使用一个assert断言进行判断。
同样,将指定位置插入分为两种情况,一是 *pphead == pos
,二是 *pphead != pos
这里可以将pos看似空指针(NULL),那指定位置插入(之前)不就是尾插吗?细节上不就是在 pos这个指针上,处理它也很简单。
在指针pos之前插入数据会影响到的节点:pcur pos
,在pcur和pos之前插入newnode,pcur newnode pos
这里需要将pcur和pos之间的”线“断开,然后使 newnode->next = pos;
,newnode->next = pos;
这不就完成了插入操作。
删除数据
在删除数据时需要考虑,删除这个节点会影响到那些节点
删除数据需要注意的是 *pphead 和 pphead不能为空,删除数据也不可能删除空,函数里对空指针解引用也会报错。
头删:
头删的逻辑简单:一,保存*pphead之后的节点 SL* pcur = (*pphead)->next;
,二、然后释放第一个节点 free(*pphead);
,三、最后将 pcur 赋给 *pphead,更新头节点的位置。
尾删:
尾删,需要考虑最后一个节点,和最后一个节点之前的节点,所以需要使用pdst指针指向倒数第二个节点,以及pcur指针指向最后一个节点。在循环时以 pcur->next != NULL
为结束条件,在循环体内要保证 pdst指针在pcur指针后,这种做法保证了,pdst指针在pcur指针后,而pcur指针指向的也是最后一个节点。
SL* pdst = *pphead;
SL* pcur = pdst->next;
//头删
void SLPopFront(SL** pphead)
{
assert(*pphead && pphead);
SL* pcur = (*pphead)->next;
free(*pphead);
*pphead = pcur;
}
//尾删
void SLPopBack(SL** pphead)
{
assert(*pphead && pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SL* pdst = *pphead;
SL* pcur = pdst->next;
while (pcur->next)
{
pcur = pcur->next;
pdst = pdst->next;
}
pdst->next = NULL;
free(pcur);
pcur = NULL;
}
}
指定位置删除数据:
指定位置删除数据与指定位置插入数据类似,与尾删也比较类似。首先想要指定位置删除数据, *pphead和pphead以及pos都不可能为空,否则这还删什么?传递过来的东西都是空的。
删除指定位置的数据时需要从它会影响那些节点,pos会影响到 pcur pos pos->next
。
*pphead 刚好等于pos 的情况,和 *pphead != pos的情况。当 *pphead != pos时:
需要使用循环将定义的pcur指针指向pos之前的节点,所以结束条件是
pcur->next != pos
当跳出循环时开始销毁,在销毁前需要将
pos->next;
赋给pcur->next
,否则直接删除pos节点,无法将pso的后继节点与它前驱节点链接,链表断开了~讲pcur与pos->next链接上后,释放pos即可。
当*pphead == pos时,pos指向的时第一个节点的位置,此时不就是头删吗,这是直接调用头删函数就完成了。
//指定位置删除
void SLErase(SL** pphead, SL* pos)
{
assert(*pphead && pphead);
assert(pos);
SL* pcur = *pphead;
if (*pphead == pos)//头删
{
//free(*pphead);
//*pphead = NULL;
SLPopFront(pphead);
}
else
{
while (pcur->next != pos)
{
pcur = pcur->next;
}
pcur->next = pos->next;
free(pos);
pos = NULL;
}
}
//删除pos之后的节点
void SLEraseBack(SL* pos)
{
assert(pos->next && pos);
// pos pos->next pos->next-->next
SL* del = pos->next;
// pos del del->next
pos->next = del->next;
free(del);
del = NULL;
}
删除pos之后的节点逻辑简单与删除pos节点类似。第一步同样是需要考虑,删除pos之后·的节点会影响到那些节点。
删除pos之后的节点会影响 :pos pos->next pos->next-->next
,这三个节点,所以传递过来的 pos 和 pos->next不能为空否则就是对空指针解引用,导致程序异常。
在删除时,需要注意删除和将pos 与 pos->next–>next链接的顺序, 先链接,在删除
- 将pos->next保存,赋给del指针
- 将pos与 del->next链接
- 释放del指针
销毁链表
销毁链表需要使用free对每一个节点进行释放。
//销毁链表
void SLDestory(SL** pphead)
{
//循环销毁所有节点
assert(*pphead && pphead);
SL* pcur = *pphead;
while (pcur)
{
SL* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
销毁链表,需要对每一个节点进行释放,而只使用一个指针pcur,释放当前的节点就找不到下一个节点了,这里需要使用两个指针。
一个指针用来释放(pcur),一个指针用来指向待释放之后的节点(next)。
当释放完pcur节点后,更新pcur的位置 pcur = next;
,用来释放下一个节点,next指针也需要更新用来指向下一个节点 next = pcur->next;
,用来对pcur进行更新。直到pcur指向空指针时释放完所有节点,跳出循环。而 *pphead,还没有置为空,这时候时野指针,最后一步 *pphead = NULL;
。
源码
SListNode.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLNodeDatatpye;
struct SListNode
{
SLNodeDatatpye data;
struct SListNode* next;
};
typedef struct SListNode SL;
//创建节点
SL* SLBuyNode(SLNodeDatatpye x);
//打印
void SLPrint(SL* phead);
//头插
void SLPushFront(SL** pphead, SLNodeDatatpye x);
//尾插
void SLPushBack(SL** pphead, SLNodeDatatpye x);
//头删
void SLPopFront(SL** pphead);
//尾删
void SLPopBack(SL** pphead);
//查找,返回地址
SL* SLFind(SL** pphead, SLNodeDatatpye x);//不需要二级指针,保证接口一直,所以传递二级
//指定位置插入(之前)
void SLInsert(SL** pphead, SLNodeDatatpye x, SL* pos);
//删除pos之后的节点
void SLEraseBack(SL* pos);
//删除pos节点
void SLErase(SL** pphead, SL* pos);
//销毁链表
void SLDestory(SL** pphead);
SListNode.c
#define _CRT_SECURE_NO_WARNINGS
#include "SListNode.h"
//创建节点
SL* SLBuyNode(SLNodeDatatpye x)
{
SL* newnode = (SL*)malloc(sizeof(SL));
if (newnode == NULL)
{
perror("malloc");
return;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//打印
void SLPrint(SL* phead)
{
//assert(phead);
SL* pcur = phead;
while (pcur)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
//头插
void SLPushFront(SL** pphead, SLNodeDatatpye x)
{
assert(pphead);
SL* newnode = SLBuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//尾插
void SLPushBack(SL** pphead, SLNodeDatatpye x)
{
assert(pphead);
if (*pphead == NULL)
{
*pphead = SLBuyNode(x);
}
else
{
SL* pcur = *pphead;
while (pcur->next)
{
pcur = pcur->next;
}
pcur->next = SLBuyNode(x);
}
}
//头删
void SLPopFront(SL** pphead)
{
assert(*pphead && pphead);
SL* pcur = (*pphead)->next;
free(*pphead);
*pphead = pcur;
}
//尾删
void SLPopBack(SL** pphead)
{
assert(*pphead && pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SL* pdst = *pphead;
SL* pcur = pdst->next;
while (pcur->next)
{
pcur = pcur->next;
pdst = pdst->next;
}
pdst->next = NULL;
free(pcur);
pcur = NULL;
}
}
//查找,返回地址
SL* SLFind(SL** pphead, SLNodeDatatpye x)
{
assert(*pphead && pphead);
SL* pcur = *pphead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
//指定位置插入(之前)
void SLInsert(SL** pphead, SLNodeDatatpye x, SL* pos)
{
assert(pphead);
assert(pos);
SL* newnode = SLBuyNode(x);
SL* pcur = *pphead;
if (*pphead == pos)
{
newnode->next = pos;
*pphead = newnode;
}
else
{
while (pcur->next != pos)
{
pcur = pcur->next;
}
pcur->next = newnode;
newnode->next = pos;
}
}
//指定位置删除
void SLErase(SL** pphead, SL* pos)
{
assert(*pphead && pphead);
assert(pos);
if (*pphead == pos)//头删
{
//free(*pphead);
//*pphead = NULL;
SLPopFront(pphead);
}
else
{
SL* pcur = *pphead;
while (pcur->next != pos)
{
pcur = pcur->next;
}
pcur->next = pos->next;
free(pos);
pos = NULL;
}
}
//删除pos之后的节点
void SLEraseBack(SL* pos)
{
assert(pos->next && pos);
// pos pos->next pos->next-->next
SL* del = pos->next;
// pos del del->next
pos->next = del->next;
free(del);
del = NULL;
}
//销毁链表
void SLDestory(SL** pphead)
{
assert(*pphead && pphead);
SL* pcur = *pphead;
while (pcur)
{
SL* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}