分享

UC头条:<数据结构> 链表

 cnzrp 2023-06-17 发布于山西

五、功能的实现

1)打印单链表

//打印单链表voidSLTPrint(SLTNode*phead);

voidSLTPrint(SLTNode*phead){SLTNode*cur=phead;//(1)while(cur!=NULL)//(2){printf('%d->',cur->data);cur=cur->next;//(3)}printf('NULL\n');}

(1)这里也可以直接用phead进行循环,但是像这样创建一个“当前节点”(cur源自单词current)会比较“美观”。(But如果这个函数内部后面还需要用头节点的话就不能直接用phead,否则会找不到头)

(2)控制结束的条件

(3)遍历

2)创建新节点

链表的结点:按需分配,随用随创

链表的头插、尾插(只要是插入)都需要创建一个新节点,然后插到对应位置。所以我们可以直接把“创建新节点”封装成一个函数,以便后面直接调用:

SLTNode*BuySLTNode(SLTDataTypex){SLTNode*newnode=(SLTNode*)malloc(sizeof(SLTNode));//(1)if(newnode==NULL)//(2){perror('mallocnewnodefail:');return;}//(3)给新节点赋值newnode->x;newnode->next=NULL;returnnewnode;//别忘了返回newnode}

(1)动态开辟一个新节点,.h头文件里要包含

(2)判断开辟是否成功,如果不成功则输出错误并返回

(3)给新节点的数据域赋值,指针域赋为空:NULL,这样做的好处是:不需要最后对链表尾结点的指针域置空。

3)尾插

在链表尾部插入一个节点

先看这段代码:

voidSLTPushBack(SLTNode**pphead,SLTDataTypex);{SLTNode*newnode=BuySLTNode(x);SLTNode*tail=*pphead;while(tail->next!=NULL){tail=tail->next;}tail->next=newnode;}

上面这段代码的前提是,我们已经假定这个链表有>=1个节点,但是如果*pphead为空呢?

如果为空,则只执行:

SLTNode*newnode=BuySLTNode(x);SLTNode*tail=*pphead;

初始化:SLTNode*phead=NULL;

传参:SLTPushBack(&phead,x);)

当phead为NULL时,也就不存在tail->next了

所以切记要先判断*pphead是否为空:

voidSLTPushBack(SLTNode**pphead,SLTDataTypex){SLTNode*newnode=BuySLTNode(x);if(*pphead==NULL){*pphead=newnode;}else{SLTNode*tail=*pphead;//找原链表的尾结点while(tail->next!=NULL){tail=tail->next;}tail->next=newnode;}}

点击加载图片

4)尾删

尾删比较麻烦,因为要判断链表是否为空以及分情况讨论结点个数。

先看这段代码:

voidSLTPopBack(SLTNode**pphead){assert(pphead&&*pphead);//(1)SLTNode*tail,*tailpre;//(2)tail=*pphead->next;tailpre=*pphead;while(tail->next){tail=tail->next;tailpre=tailpre->next;}free(tail);//(3)tailpre->next=NULL;//(4)}

(1)pphead(二级指针)和*pphead绝对不可以为空,最好断言一下

(2)定义tail和tail前一个结点tailpre,目的是释放tail后,直接得到新的尾结点,方便置空

(3)没必要再把tail置空:tail=NULL;因为tail是局部变量,函数结束就自动销毁了

(4)释放后,新的尾结点的next置空

看似没什么毛病·······

但是,上面没有考虑只有一个结点的情况!!

⚡如果只有一个结点,tail=*pphead->next;后,tail为NULL,下面的执行就出大问题了

解决办法是判断一下:

voidSLTPopBack(SLTNode**pphead){assert(pphead&&*pphead);if((*pphead)->next==NULL)//只有一个结点{free(*pphead);*pphead=NULL;}else//>=2个结点{SLTNode*tail,*tailpre;tail=*pphead->next;tailpre=*pphead;while(tail->next){tail=tail->next;tailpre=tailpre->next;}free(tail);tailpre->next=NULL;}}

5)头插

按照尾插的路子,可能会这样写:

voidSLTPushFront(SLTNode**pphead,SLTDataTypex){assert(pphead);SLTNode*newnode=BuySLTNode(x);if(*pphead==NULL){*pphead=newnode;}else{newnode->next=*pphead;*pphead=newnode;}}

当然没有错,但是仔细想一想,其实没有必要判断*pphead是否为空,因为即使*pphead为空,执行else部分依然没毛病!

化简为:

voidSLTPushFront(SLTNode**pphead,SLTDataTypex){assert(pphead);SLTNode*newnode=BuySLTNode(x);newnode->next=*pphead;*pphead=newnode;}

6)头删

头删相比较尾删很简单,因为不需要像尾删一样找tail前一个结点。

头删可以直接删:

voidSLPopFront(SLTNode**pphead){assert(pphead&&*pphead);SLTNode*next=(*pphead)->next;//临时存一下第二个元素的结点free(*pphead);*pphead=next;}

7)查找

查找链表中的某个元素,只需遍历一遍链表。返回data==要查找的元素第一次出现的节点的地址;如果链表中没有要查找的元素,返回NULL。

<注意,空链表也可以查找,返回NULL即可>↓

SLTNode*SLFind(SLTNode*phead,SLDataTypex){SLTNode*cur=phead;while(cur){if(cur->data==x)returncur;cur=cur->next;}returnNULL;}

8)删除

分两种情况:链表只有一个节点、链表有多个节点。

1、只有一个节点:如果*pphead==pos,相当于头删,直接调用前面的函数即可。

2、有多个节点:遍历链表,直到找到地址为pos的结点,按照尾删的思路,删除即可。

voidSLErase(SLTNode**pphead,SLTNode*pos){assert(pphead&&*pphead&&pos);//都不能为空if(*pphead==pos){SLPopFront(pphead);}else{SLTNode*cur=*pphead;while(cur->next!=pos){cur=cur->next;}SLTNode*next=cur->next->next;cur->next=next;free(pos);//一定要free}}

9)插入结点

在pos前插入:

voidSLInsert(SLTNode**pphead,SLTNode*pos,SLDataTypex){assert(pphead&&pos);if(pos==*pphead){SLPushFront(pphead,x);}else{SLTNode*cur=*pphead;while(cur->next!=pos){cur=cur->next;}SLTNode*insnode=BuyNode(x);cur->next=insnode;insnode->next=pos;}}

10)销毁

对于销毁链表,如果只free掉*pphead行么?

当然不行!!

因为单链表由一个一个的结点连接起来的。如果只free(*pphead),头结点是释放了,但是后面的节点没被释放,还占用着空间但是已经找不到他们的地址了。

所以应该逐个释放

voidSLDestroy(ListNode**pphead){ListNode*cur=*pphead;while(cur){ListNode*next=cur->next;free(cur);cur=next;}*pphead=NULL;//最后别忘了置空}

销毁完后最好把*pphead置空,防止销毁链表后对链表误操作而导致的野指针问题。

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多