小菜坤日常上传gitee代码:https://gitee.com/qi-dunyan(所有的原码都放在了我上面的gitee仓库里) 数据结构知识点存放在专栏【数据结构】后续会持续更新 ❤❤❤ 个人简介:双一流非科班的一名小白,期待与各位大佬一起努力! 推荐数据结构书籍:《大话数据结构》
回顾之前的顺序表,我们发现就算是动态扩容,我们也都是成倍的括,也可能存在空间浪费,并且顺序表的头插头删还十分麻烦,需要挪动数据。 而链表的存在就解决了头插头删以及空间浪费这一问题,提到链表,我们脑海中就会浮现出一个链条把东西都链接起来。
链表
链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。这里所谓的逻辑结构,其实就是为了方便理解,然后加上箭头用来表示关系的,但实际上并不存在箭头。
我们发现,链式结构其实就是在该节点存放下一个节点的地址,然后通过地址便可以访问到该节点的下一个节点。而上图中的箭头,只是为了方便理解,一个一个连接起来,但实际上是并不存在的。(逻辑结构)
因此,链式结构在逻辑上是连续的(如上图通过箭头链接起来),但在物理地址上却不一定连续。因为每一个节点都是在堆上开辟空间,开辟空间的地址有可能连续,又可能不连续。
链表种类
链表主要分为以下几类:单向与双向、带头与不带头、循环与非循环,而通过这三类的组合,又分为八种形式的链表:带头单向循环链表、带头单向不循环…
而我们本次章节研究的就是不带头单向非循环链表。把这一个连接后,后面的其它种类的链表就很好理解与实现了
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;//数据
struct SListNode* next;//指向下一个结构体的指针
}SListNode;
动态申请节点其实就是在堆上malloc出一块空间,并把数据data存放在该节点中。由于后面的插入操作都需要进行开辟新空间,所以这里单独给写了出来,后面用到的时候直接调用即可
//动态申请节点
SListNode* BuySListNode(SLTDateType x)
{
SListNode*newnode=(SListNode*)malloc(sizeof(SListNode));//malloc空间
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;//将数据放在该节点的data
newnode->next = NULL;//next置为空(避免野指针)
return newnode;//返回新节点
}
尾插 还是需要进行画图,这样才能更好的理解
但是这里假如传来的是个空指针,即假如是一个空的链表,那尾插时这个新节点就作为头节点来使用。(特殊情况)
//尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
//动态申请一个新节点
SListNode* newnode = BuySListNode(x);
//空表
if (*pplist == NULL)
{
//这里改变List,传址调用、形参是实参的临时拷贝,形参的修改不会影响实参,所以传List的地址,即用二级指针变量来接收一级指针的地址,这时解引用后就会影响到List
*pplist = newnode;
}
else
{ //找尾巴
SListNode* ptail = *pplist;
//这里修改的是结构体成员变量,所以不用二级指针
while (ptail->next != NULL)
{
ptail = ptail->next;
}
//将节点接在尾巴上
ptail->next = newnode;
}
}
这里需要注意的是,我是在外面定义的是一个结构体指针,要对此进行修改,必须传址调用,因为传值调用形参的改变不会影响实参。而进行修改后(空表情况下进行尾插),后面的再次尾插其实改变的就不是该变量了,而是该变量的结构体成员next,以及next节点指向的data
尾删 画图解决一切。
这里需要注意的就是,假如只有一个节点的情况下,该节点的next就是空指针,然后再next就形成了空指针的解引用操作(NULL->next)这是错误的,所以我们要考虑到只剩一个节点的特殊情况,另外,还要注意空表状态是不可删除的。
//尾删
void SListPopBack(SListNode** pplist)
{
//空表不可进行删除,所以加个断言
assert(*pplist);
//只有一个数据时直接把该节点释放,然后置空即可
if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
SListNode* ptail = *pplist;//本意即SListNode*ptail=list
//找到最后一个的前一个
while (ptail->next->next!=NULL)
{
ptail = ptail->next;
}
//释放最后一个节点
free(ptail->next);
//并把指向最后一个节点的next置空(不置空就是野指针了,因为虽然释放了那块空间,但是它的前一个节点的next依然指向它)
ptail->next = NULL;
}
}
这里我们写一个打印的接口,方便我们观察。也很简单,遍历整个链表即可。
//单链表打印
void SListPrint(SListNode* phead)
{
SListNode* cur = phead;
//注意这里是cur!=NULL,因为假如是cur->next !=NULL的话,最后一个节点的数据不会被打印
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL");
}
这里我们来测试一下前面的尾插与尾删操作。
void SListTest2()
{
SListNode* list = NULL;
//传址调用,解引用后形参的修改会影响实参
SListPushBack(&list, 0);
//SListPrint(list);//0->NULL
SListPushBack(&list, 1);
SListPushBack(&list, 2);
SListPushBack(&list, 3);
SListPushBack(&list, 4);
//打印
//SListPrint(list);//0->1->2->3->4->NULL
//尾删
SListPopBack(&list);
//SListPrint(list);//0->1->2->3->NULL
SListPopBack(&list);
SListPopBack(&list);
SListPopBack(&list);
SListPopBack(&list);
SListPrint(list);//NULL
//空表进行删除
SListPopBack(&list);//报错 error
}
通过测试我们发现一切都在掌控之中,并没有什么问题。接下来实现头插与头删。
头插
单链表的头插最为简单,时间复杂度达到了O(1),还是通过画图从而更好的理解。这里只需要将新节点的next指向目前的头指针,然后头指针再更新为新节点即可。
//头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
//注意这里形参是二级指针,因为这里改变的是list,并不是改变list指向的结构体成员,所以传地址,而一级指针的地址,就要用二级指针pplist接收
SListNode* newnode = BuySListNode(x);
newnode->next =*pplist;
*pplist = newnode;
}
我们假定是个空链表,我们发现头插也是适用的。因此就以上代码就够了。 头删
这里我们需要注意的就是,空表不可进行删除,然后其余的画个图就一目了然,需要注意的是,这里依然是改变的list,所以还是用二级指针。
//头删
void SListPopFront(SListNode** pplist)
{
assert(*pplist);
//先保存
SListNode* next = (*pplist)->next;
free(*pplist);
*pplist = next;
}
测试
//头插头删
void SListTest3()
{
//头插
SListNode* list = NULL;
SListPushFront(&list,1);
//SListPrint(list);//1->NULL
SListPushFront(&list, 2);
SListPushFront(&list, 3);
SListPushFront(&list, 4);
//SListPrint(list);//4->3->2->1->NULL
//头删
SListPopFront(&list);
//SListPrint(list);//3->2->1->NULL
SListPopFront(&list);
SListPopFront(&list);
SListPopFront(&list);
SListPrint(list);//NULL
//SListPopFront(&list);//error(空表不可删除)
}
这里我们通过测试,进行观察发现没有什么问题,接下来是单链表的查找。
查找操作也很简单,无非就是遍历整个链表,然后找到data时返回该节点指针即可,找不到就返回空指针。其实也可以这样来实现:
//单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
SListNode* cur = plist;
//while (cur)
//{
// if (cur->data == x)
// {
// return cur;
// }
// cur = cur->next;
//}
//return NULL;
//简化版本
while (cur && cur->data != x)
{
cur = cur->next;
}
//结束循环的条件,要么就是cur== NULL,说明找不到,或者就是cur->data==x,找到了,这里直接返回cur就行。
return cur;
}
pos位置进行插入 思路都在图纸当中,画图会更加容易理解!
//在pos位置插入
void SListInsert(SListNode** pplist, SListNode* pos, SLTDateType x)
{
if (*pplist == pos)
{
//头插
SListPushFront(pplist, x);
}
else
{
SListNode* cur = *pplist;
//找到pos节点之前的一个
while (cur->next != pos)
{
cur = cur->next;
}
//将新节点插入在此
SListNode* newnode = BuySListNode(x);
//找到了pos位置之前的了
cur->next = newnode;
newnode->next = pos;
}
}
pos位置进行删除
//删除pos位置
void SListErase(SListNode** pplist, SListNode* pos)
{
assert(pos);
//假如pos指向list
if (pos == *pplist)
{
SListPopFront(pplist);
}
else
{
SListNode* cur = *pplist;
//找到pos位置之前的
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = pos->next;
free(pos);
}
}
最后便是单链表的销毁,因为我们知道,malloc、realloc、calloc这几个函数都是与free成对出现的。不然会造成内存泄漏。 这里我们也是需要进行遍历每一个节点,然后进行删除,不过需要注意的是在删除该节点之前。要先记住下一个节点。
//单链表销毁
void SListDestroy(SListNode** pplist)
{
SListNode* cur = *pplist;
while(cur != NULL)
{
SListNode* next = cur->next;
free(cur);
cur = next;
}
*pplist = NULL;//一定要置空,不然后面打印就是野指针的访问
}
在这里,一定要多画图,根据图形来理清思路,然后再进行写代码,同时一定要考虑考虑特殊情况,比如空表状态下能不能删除,比如free的时候会不会存在野指针, 并且还建议大家边写边调试,不要一口气从尾插写完,要逐步进行,慢即是快!
end 生活原本沉闷,但跑起来就会有风!❤