🎉🎉🎉哈喽!!!大家好,这里是禾子日月
🎆欢迎各位小伙伴关注➕点赞➕留言➕收藏
🎆我坚信努力奔跑才能与幸运不期而遇。
目录
1、为什么要学链表
2.链表的定义
3、链表的插入
①尾插
②头插
③其他位置插入
4、链表的删除
①尾删
②头删
③其他位置删除
5、打印链表
6、销毁链表
写在最后
🎇🎇🎇上篇文章我们用顺序表写了一个目录,通过写目录我们又巩固了顺序表的相关知识,如果你对这个感兴趣可以点击下方的链接哦。
👇👇👇
http://t.csdn.cn/HSkor
🎉🎉🎉废话不多说,我们开始今天的内容。
1、为什么要学链表
在回答这个问题之前,我们先引入一个例子:
首先我们想到的是用数组存储,但是用数组有些不便之处。因为事先我们并不知道文件1.txt中数据的个数,因此数组的大小不易确定。数组定义的太小,不能容纳所有数据;定义的太大,造成内存空间的浪费。——该问题用动态数组可以解决。
数组需要占用连续的内存空间,当没有所需大小的连续空间时,程序不能运行。——该问题用链表可以解决。
2.链表的定义
链表分为单向链表和双向链表。链表的每个元素称为一个节点。每个节点包含两部分:
第一部分 data;第二部分 next。 data时用户需要的数据(可以是一个成员,或多个成员),称为链表的数据领域;next为下一个节点的地址,或称为指向下一个节点的指针,它也被称为链表的指针域。看到这里你可能似懂非懂,接下来上图🎈🎈🎈
链表的尾部是链表的最后一个节点,即指针域为NULL的节点。链表的长度不是固定的,随时可以添加,如果添加到链表的尾部,则新的节点将成为链表的结尾。所以任何一个需要添加到链表尾部的新节点,其指针域必须是NULL,并使原来链表的结尾指针域指向新的节点。
接下来我们创建一个链表
- typedef struct SLinkNode
- {
- int data;
- struct SLinkNode *next;
- }SLTNode;
※※注意:我们在定义链表的时候可以使用typedf关键字起一个别名,这样在后面的操作中会省下不少事。SLTNode 等价于 struct SLinkNode。
main函数中代码
- int main()
- {
- SLTNode *plist=NULL;
- return 0;
- }
3、链表的插入
①尾插
尾插示意图:
尾插后原链表最后一个节点的指针域不再为NULL而是指向新节点。接下来我们用代码来实现一下。
- void SListPushBack(SLTNode **pphead,int x)
- {
- SLTNode *newnode=(SLTNode*)malloc(sizeof(SLTNode));
- newnode->data = x;
- newnode->next = NULL;
- if(*pphead==NULL)
- {
- *pphead=newnode;
- }
- else
- {
- SLTNode *tail = *pphead;
- while(tail->next !=NULL)
- {
- tail=tail->next;
- }
- tail->next=newnode;
- }
- }
②头插
头插示意图:
头插时我们只需要将新节点的指针域指向头节点即可。
代码如下:
- void SListPushFront(SLTNode **pphead,SLTDataType x)
- {
- SLTNode *newnode=(SLTNode*)malloc(sizeof(SLTNode));
- newnode->data = x;
- newnode->next = *pphead;
- *pphead=newnode;
- }
③其他位置插入
其他位置插入示意图:
从其他插入我们需要先断开两个节点之间的联系。
- //在pos位置插入一个节点
- void SListInsert(SLTNode **pphead,SLTNode *pos,SLTDataType x)
- {
- SLTNode *newnode=(SLTNode*)malloc(sizeof(SLTNode));
- newnode->data = x;
- if(*pphead==pos)
- {
- newnode->next =*pphead;
- *pphead=newnode;
- }
- else
- {
- //找到pos的前一个位置
- SLTNode *posPrev = *pphead;
- while(posPrev->next != pos)
- {
- posPrev=posPrev->next;
- }
- posPrev->next = newnode;
- newnode->next =pos;
- }
- }
4、链表的删除
①尾删
尾删示意图:
尾删时,我们只需要将最后一个节点前面的节点的指针域变成NULL即可。
代码如下:
- void SListPopBack(SLTNode **pphead)
- {
-
- if(*pphead==NULL)//判断链表是否为空
- {
- return;
- }
- SLTNode *tail=*pphead;
- while(tail->next->next ){
- tail=tail->next;
- }
- free(tail->next);
- tail->next =NULL;
- }
②头删
头删示意图:
代码如下:
- void SListPopFront(SLTNode **pphead)
- {
- assert(pphead);
- if(*pphead==NULL)//判断链表是否为空
- return;
- SLTNode *q=(*pphead)->next;
- free(*pphead);
- *pphead=q;
- }
③其他位置删除
其他位置删除示意图:
代码如下:
- void SListErase(SLTNode **pphead,SLTNode *pos)
- {
- if(*pphead==pos)
- {
- SListPopFront(pphead);//如果要删除的是头节点,我们偷个懒直接调用
- }
- else
- {
- SLTNode *prev=*pphead;
- while(prev->next !=pos)
- {
- prev=prev->next ;
- }
- prev->next =pos->next ;
- free(pos);
- }
- }
5、打印链表
打印链表比较简单,我们只需要遍历一次链表就可以了。
- void SListPrint(SLTNode *phead)
- {
- SLTNode *cur=phead;
- while(cur!=NULL)
- {
- printf("%d->",cur->data);
- cur = cur->next;
- }
- printf("NULL");
- }
6、销毁链表
链表的节点都是我们在内存中申请的,使用完后要销毁掉。
- void SListDestory(SLTNode **pphead)
- {
- assert(pphead);
- SLTNode *cur= *pphead;
- while(cur)
- {
- SLTNode *next=cur->next ;
- free(cur);
- }
- *pphead=NULL;
- }
写在最后
🎉🎉🎉以上就是本篇文章全部内容,作者知识水平有限,若有什么错误或者需改进之处希望大家指出,若是你有更好的代码希望能给博主留言,博主希望能在CSDN与各位一起进步,感谢大家观看!