舞蹈《我的头我的肩》:一步一步写算法(之双向链表)

来源:百度文库 编辑:偶看新闻 时间:2024/03/29 06:48:55

一步一步写算法(之双向链表)

分类: 数据结构和算法 2011-10-07 20:03 677人阅读 评论(4) 收藏 举报

【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】


    前面的博客我们介绍了单向链表。那么我们今天介绍的双向链表,顾名思义,就是数据本身具备了左边和右边的双向指针。双向链表相比较单向链表,主要有下面几个特点:

    (1)在数据结构中具有双向指针

    (2)插入数据的时候需要考虑前后的方向的操作

    (3)同样,删除数据的是有也需要考虑前后方向的操作

    那么,一个非循环的双向链表操作应该是怎么样的呢?我们可以自己尝试一下:

    (1)定义双向链表的基本结构

view plaincopy to clipboardprint?

  1. typedef struct _DOUBLE_LINK_NODE  
  2. {  
  3.     int data;  
  4.     struct _DOUBLE_LINK_NODE* prev;  
  5.     struct _DOUBLE_LINK_NODE* next;  
  6. }DOUBLE_LINK_NODE;  
    (2)创建双向链表节点 view plaincopy to clipboardprint?
  1. DOUBLE_LINK_NODE* create_double_link_node(int value)  
  2. {  
  3.     DOUBLE_LINK_NODE* pDLinkNode = NULL;  
  4.     pDLinkNode = (DOUBLE_LINK_NODE*)malloc(sizeof(DOUBLE_LINK_NODE));  
  5.     assert(NULL != pDLinkNode);  
  6.   
  7.     memset(pDLinkNode, 0, sizeof(DOUBLE_LINK_NODE));  
  8.     pDLinkNode->data = value;  
  9.     return pDLinkNode;  
  10. }  
    (3)删除双向链表

view plaincopy to clipboardprint?

  1. void delete_all_double_link_node(DOUBLE_LINK_NODE** pDLinkNode)  
  2. {  
  3.     DOUBLE_LINK_NODE* pNode;  
  4.     if(NULL == *pDLinkNode)  
  5.         return ;  
  6.   
  7.     pNode = *pDLinkNode;  
  8.     *pDLinkNode = pNode->next;  
  9.     free(pNode);  
  10.     delete_all_double_link_node(pDLinkNode);  
  11. }  
    (4)在双向链表中查找数据

view plaincopy to clipboardprint?

  1. DOUBLE_LINK_NODE* find_data_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode, int data)  
  2. {  
  3.     DOUBLE_LINK_NODE* pNode = NULL;  
  4.     if(NULL == pDLinkNode)  
  5.         return NULL;  
  6.   
  7.     pNode = (DOUBLE_LINK_NODE*)pDLinkNode;  
  8.     while(NULL != pNode){  
  9.         if(data == pNode->data)  
  10.             return pNode;  
  11.         pNode = pNode ->next;  
  12.     }  
  13.       
  14.     return NULL;  
  15. }  
    (5)双向链表中插入数据

view plaincopy to clipboardprint?

  1. STATUS insert_data_into_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data)  
  2. {  
  3.     DOUBLE_LINK_NODE* pNode;  
  4.     DOUBLE_LINK_NODE* pIndex;  
  5.   
  6.     if(NULL == ppDLinkNode)  
  7.         return FALSE;  
  8.   
  9.     if(NULL == *ppDLinkNode){  
  10.         pNode = create_double_link_node(data);  
  11.         assert(NULL != pNode);  
  12.         *ppDLinkNode = pNode;  
  13.         (*ppDLinkNode)->prev = (*ppDLinkNode)->next = NULL;  
  14.         return TRUE;  
  15.     }  
  16.   
  17.     if(NULL != find_data_in_double_link(*ppDLinkNode, data))  
  18.         return FALSE;  
  19.   
  20.     pNode = create_double_link_node(data);  
  21.     assert(NULL != pNode);  
  22.   
  23.     pIndex = *ppDLinkNode;  
  24.     while(NULL != pIndex->next)  
  25.         pIndex = pIndex->next;  
  26.   
  27.     pNode->prev = pIndex;  
  28.     pNode->next = pIndex->next;  
  29.     pIndex->next = pNode;  
  30.     return TRUE;  
  31. }  
    (6)双向链表中删除数据

view plaincopy to clipboardprint?

  1. STATUS delete_data_from_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data)  
  2. {  
  3.     DOUBLE_LINK_NODE* pNode;  
  4.     if(NULL == ppDLinkNode || NULL == *ppDLinkNode)  
  5.         return FALSE;  
  6.   
  7.     pNode = find_data_in_double_link(*ppDLinkNode, data);  
  8.     if(NULL == pNode)  
  9.         return FALSE;  
  10.   
  11.     if(pNode == *ppDLinkNode){  
  12.         if(NULL == (*ppDLinkNode)->next){  
  13.             *ppDLinkNode = NULL;  
  14.         }else{  
  15.             *ppDLinkNode = pNode->next;  
  16.             (*ppDLinkNode)->prev = NULL;  
  17.         }  
  18.   
  19.     }else{  
  20.         if(pNode->next)  
  21.             pNode->next->prev = pNode->prev;  
  22.         pNode->prev->next = pNode->next;  
  23.     }  
  24.   
  25.     free(pNode);  
  26.     return TRUE;  
  27. }  
    (7)统计双向链表中数据的个数

view plaincopy to clipboardprint?

  1. int count_number_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode)  
  2. {  
  3.     int count = 0;  
  4.     DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;  
  5.   
  6.     while(NULL != pNode){  
  7.         count ++;  
  8.         pNode = pNode->next;  
  9.     }  
  10.     return count;  
  11. }  
    (8)打印双向链表中数据

view plaincopy to clipboardprint?

  1. void print_double_link_node(const DOUBLE_LINK_NODE* pDLinkNode)  
  2. {  
  3.     DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;  
  4.   
  5.     while(NULL != pNode){  
  6.         printf("%d\n", pNode->data);  
  7.         pNode = pNode ->next;  
  8.     }  
  9. }  
    注意:

        今天我们讨论的双向链表是非循环的,大家可以考虑一下如果改成循环双向链表,应该怎么写?如果是有序的循环双向链表,又该怎么写?


【预告: 下面我们讨论的是循环单向链表】


分享到: