五、功能的实现 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置空,防止销毁链表后对链表误操作而导致的野指针问题。 |
|