Chinaunix首页 | 论坛 | 博客
  • 博客访问: 119041
  • 博文数量: 61
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 230
  • 用 户 组: 普通用户
  • 注册时间: 2014-04-26 11:35
个人简介

实践Linux的理论

文章存档

2015年(1)

2014年(60)

我的朋友

分类: C/C++

2014-04-29 11:50:42

前面的博客我们介绍了单向链表。那么我们今天介绍的双向链表,顾名思义,就是数据本身具备了左边和右边的双向指针。双向链表相比较单向链表,主要有下面几个特点:
    (1)在数据结构中具有双向指针
    (2)插入数据的时候需要考虑前后的方向的操作
    (3)同样,删除数据的是有也需要考虑前后方向的操作
    那么,一个非循环的双向链表操作应该是怎么样的呢?我们可以自己尝试一下:
    (1)定义双向链表的基本结构
[cpp] view plaincopy
typedef struct _DOUBLE_LINK_NODE  
{  
    int data;  
    struct _DOUBLE_LINK_NODE* prev;  
    struct _DOUBLE_LINK_NODE* next;  
}DOUBLE_LINK_NODE;  
    (2)创建双向链表节点
[cpp] view plaincopy
DOUBLE_LINK_NODE* create_double_link_node(int value)  
{  
    DOUBLE_LINK_NODE* pDLinkNode = NULL;  
    pDLinkNode = (DOUBLE_LINK_NODE*)malloc(sizeof(DOUBLE_LINK_NODE));  
    assert(NULL != pDLinkNode);  
  
    memset(pDLinkNode, 0, sizeof(DOUBLE_LINK_NODE));  
    pDLinkNode->data = value;  
    return pDLinkNode;  
}  
    (3)删除双向链表
[cpp] view plaincopy
void delete_all_double_link_node(DOUBLE_LINK_NODE** pDLinkNode)  
{  
    DOUBLE_LINK_NODE* pNode;  
    if(NULL == *pDLinkNode)  
        return ;  
  
    pNode = *pDLinkNode;  
    *pDLinkNode = pNode->next;  
    free(pNode);  
    delete_all_double_link_node(pDLinkNode);  
}  
    (4)在双向链表中查找数据
[cpp] view plaincopy
DOUBLE_LINK_NODE* find_data_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode, int data)  
{  
    DOUBLE_LINK_NODE* pNode = NULL;  
    if(NULL == pDLinkNode)  
        return NULL;  
  
    pNode = (DOUBLE_LINK_NODE*)pDLinkNode;  
    while(NULL != pNode){  
        if(data == pNode->data)  
            return pNode;  
        pNode = pNode ->next;  
    }  
      
    return NULL;  
}  
    (5)双向链表中插入数据
[cpp] view plaincopy
STATUS insert_data_into_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data)  
{  
    DOUBLE_LINK_NODE* pNode;  
    DOUBLE_LINK_NODE* pIndex;  
  
    if(NULL == ppDLinkNode)  
        return FALSE;  
  
    if(NULL == *ppDLinkNode){  
        pNode = create_double_link_node(data);  
        assert(NULL != pNode);  
        *ppDLinkNode = pNode;  
        (*ppDLinkNode)->prev = (*ppDLinkNode)->next = NULL;  
        return TRUE;  
    }  
  
    if(NULL != find_data_in_double_link(*ppDLinkNode, data))  
        return FALSE;  
  
    pNode = create_double_link_node(data);  
    assert(NULL != pNode);  
  
    pIndex = *ppDLinkNode;  
    while(NULL != pIndex->next)  
        pIndex = pIndex->next;  
  
    pNode->prev = pIndex;  
    pNode->next = pIndex->next;  
    pIndex->next = pNode;  
    return TRUE;  
}  
    (6)双向链表中删除数据
[cpp] view plaincopy
STATUS delete_data_from_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data)  
{  
    DOUBLE_LINK_NODE* pNode;  
    if(NULL == ppDLinkNode || NULL == *ppDLinkNode)  
        return FALSE;  
  
    pNode = find_data_in_double_link(*ppDLinkNode, data);  
    if(NULL == pNode)  
        return FALSE;  
  
    if(pNode == *ppDLinkNode){  
        if(NULL == (*ppDLinkNode)->next){  
            *ppDLinkNode = NULL;  
        }else{  
            *ppDLinkNode = pNode->next;  
            (*ppDLinkNode)->prev = NULL;  
        }  
  
    }else{  
        if(pNode->next)  
            pNode->next->prev = pNode->prev;  
        pNode->prev->next = pNode->next;  
    }  
  
    free(pNode);  
    return TRUE;  
}  
    (7)统计双向链表中数据的个数
[cpp] view plaincopy
int count_number_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode)  
{  
    int count = 0;  
    DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;  
  
    while(NULL != pNode){  
        count ++;  
        pNode = pNode->next;  
    }  
    return count;  
}  
    (8)打印双向链表中数据
[cpp] view plaincopy
void print_double_link_node(const DOUBLE_LINK_NODE* pDLinkNode)  
{  
    DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;  
  
    while(NULL != pNode){  
        printf("%d\n", pNode->data);  
        pNode = pNode ->next;  
    }  
}  
    注意:
        今天我们讨论的双向链表是非循环的,大家可以考虑一下如果改成循环双向链表,应该怎么写?如果是有序的循环双向链表,又该怎么写?
阅读(677) | 评论(0) | 转发(0) |
0

上一篇:单向链表

下一篇:循环单链表

给主人留下些什么吧!~~