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