单链表和双链表在执行删除操作时的…

发布时间:2016-12-8 4:17:24 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"单链表和双链表在执行删除操作时的…",主要涉及到单链表和双链表在执行删除操作时的…方面的内容,对于单链表和双链表在执行删除操作时的…感兴趣的同学可以参考一下。

写双链表的删除操作时,一开始是采用单链表的方法。在执行的时候,删除非末尾节点还正常,但当删除的节点时最后一个节点时,执行时会返回位置(也就是指针)出错无法执行的情况。调试了好多次,也没找到原因。通过思考,最终找到了两者的区别,以下是两个操作的代码: 单链表删除: Node *delete_element_list(Node *head,int i)   {       Node *p;       p=head;       int j = 0;       if(i>length(head)||i<1)      {           cout<<"error"<<endl;           return NULL;       }       while(p->next&&j<i-1)//删除第i个元素,这个是找到第i个元素      {           p=p->next;           j++;       }     Node *q;       q=p->next;       p->next=q->next;       free(q);       return head;   }   双链表删除: Node *deleteElement(Node *head,int i)   {       if(i>length(head)||i<1)//错误的删除位置       {           cout<<"error!"<<endl;           return NULL;       }       int j = 0;       Node *temp;       temp = head->next;       while(j<i-1&& temp)//这里也是说要依次从j=0-i才能找到第i个元素啊,为什么前面的文章说他是时间复杂度均为O(1),在另一本书上找到前面说的O(1)绝对是已经指向了要删除的节点,其实这样我觉得应该要将双链表的优势放在另一个角度考虑,即双链可以在两个方向进行操作!!单链的构造顺序与输入顺序是相反的,见前面单链文章的动画     {           j++;           temp = temp->next;       }       if(temp->next==NULL)       {           temp->prior->next=NULL;//此步骤是关键,在删除最后一个节点时,需要将其的prior改为尾节点           free(temp);          }       else       {                      temp->prior->next=temp->next;           temp->next->prior=temp->prior;           free(temp);       }       return head;   }   对于单链表,无需判断要删除的节点是否是尾节点。而对于双链表则需要判断。究其原因,单链表的节点直接只有一个next指针,在找到要删除的节点的前一个节点(temp)时直接将其next指向temp->next->next即可,若要删除的节点时尾节点,其指针则直接指向NULL,也就是temp直接变为最后一个节点操作成功。而对于双链表,若删除的节点是尾节点,这种方法显然是不行的。若已找到要删除的节点temp,它是尾节点,在执行temp->next->prior=temp->prior这一操作时显然会出错。因为temp->next的next为空,而NULL是没有prior的。也就是说需要提前判断一下要删除的节点是否是尾节点,若是则直接将temp->prior指向空,free(temp)即可。二者结构的不同决定了相应的操作也有差异。   得到的一点启示就是:写代码的时候要多考虑一些极限情况,对于上面的情况若删除的不是尾节点,则单链表的方法就可以解决两者。但是对于尾节点的情况就不同了。想的和做的差别真的很大,尤其是写代码。只有写的时候调试的时候一些隐藏的错误才会暴露出来。一句话:写代码要多“挑刺”。

上一篇:Oracle&nbsp;Partition&nbsp;分区详细总结
下一篇:解决ajax请求地址含中文参数

相关文章

相关评论