C双链表的插入与删除操作

4890阅读　0评论2013-04-09　tansijie
分类：C/C++

今天面试出来一道题，要求对双链表进行插入与删除操作，好久都没写过链表的操作了，觉得有意思，晚上将内容贴出来。
双链表结构如下，它不是一般的双链表，有前驱和后继，这个链表有个指向下一个节点的指针和指向下一个节点的下个节点指针。

  1. typedef struct tagNode{
  2.     struct tagNode* pnext ;//指向下一个节点
  3.     struct tagNode* ppnext ;//指向下一个节点的下一个节点
  4. }Node;

  6. typedef Node* LList ;

下面提供如何创建链表，毁灭链表等函数。

  1. /************************************************************************/
  2. /* 创建链表 */
  3. /************************************************************************/
  4. LList create_list()
  5. {
  6.     Node* p = new Node ;
  7.     p->pnext = NULL;
  8.     p->ppnext = NULL;
  9.     return p ;
  10. }
  11. /************************************************************************/
  12. /* 创建新节点 */
  13. /************************************************************************/
  14. Node* create_new_node()
  15. {
  16.     Node* p = new Node ;
  17.     p->pnext = NULL;
  18.     p->ppnext = NULL;
  19.     return p ;
  20. }
  1. /************************************************************************/
  2. /* 在链表尾端插入新节点 */
  3. /************************************************************************/
  4. void insert_node(LList head,Node* pNode)
  5. {
  6.     Node* pb=head->pnext;
  7.     Node* pbb=head;
  8.     Node* ps= head->ppnext;
  9.     while(ps)
  10.     {
  11.         pbb = pb ;
  12.         pb = ps;
  13.         ps = ps->pnext;
  14.     }
  15.     if(pb) //如果父节点不为NULL
  16.     {
  17.         pbb->ppnext = pNode;
  18.         pb->pnext = pNode;
  19.         pb->ppnext = NULL;
  20.     }else//父节点为NULL
  21.     {
  22.         pbb->pnext = pNode;
  23.         pbb->ppnext =NULL;
  24.     }
  25.     
  26. }
  1. /************************************************************************/
  2. /* 毁灭（删除）链表 */
  3. /************************************************************************/
  4. void destroy_list(LList head)
  5. {
  6.     Node* p = head ;
  7.     Node* q;
  8.     while(p)
  9.     {
  10.         q=p ;
  11.         p=p->pnext;
  12.         delete q ;
  13.     }
  14. }
  15. /************************************************************************/
  16. /* 遍历链表 */
  17. /************************************************************************/
  18. void visit_list(LList list)
  19. {
  20.     Node* p = list ;
  21.     while(p)
  22.     {
  23.         printf("current_addr=[%p] son_addr=[%p] son_son_addr=[%p] \n",p,p->pnext,p->ppnext);
  24.         p=p->pnext;
  25.     }
  26. }

  1. /************************************************************************/
  2. /* 删除链表的指定节点，但是不能删除头节点，删除头节点有问题 */
  3. /************************************************************************/
  4. void delete_node(LList list,Node* pNode)
  5. {
  6.     if(list == pNode || pNode == NULL)
  7.     {
  8.         return ;
  9.     }

  11.     Node* pb=list;//指向当前节点的父节点
  12.     Node* pbb=list;//指向当前节点爷爷节点
  13.     Node* pc= list;//指向当前节点
  14.     while(pc && pc != pNode)
  15.     {
  16.         pbb = pb ;
  17.         pb = pc;
  18.         pc = pc->pnext;
  19.     }
  20.     if(pc)//说明找到了pc==pNode的节点，否则pc==NULL
  21.     {
  22.         pb->pnext = pc->pnext;
  23.         pb->ppnext = pc->ppnext;
  24.         pbb->ppnext = pc->ppnext;
  25.     }
  26. }







  1. /************************************************************************/
  2. /* 创建新节点 */
  3. /************************************************************************/
  4. Node* create_new_node()
  5. {
  6.     Node* p = new Node ;
  7.     p->pnext = NULL;
  8.     p->ppnext = NULL;
  9.     return p ;
  10. }
上一篇：C 字符串删除指定字符，比如删除字符串中的空格
下一篇：mmap文件内存映射