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

实践Linux的理论

文章存档

2015年(1)

2014年(60)

我的朋友

分类: C/C++

2014-04-29 11:51:44

前面的博客中,我们曾经有一篇专门讲到单向链表的内容。那么今天讨论的链表和上次讨论的链表有什么不同呢?重点就在这个"循环"上面。有了循环,意味着我们可以从任何一个链表节点开始工作,可以把root定在任何链表节点上面,可以从任意一个链表节点访问数据,这就是循环的优势。
    那么在实现过程中,循环单向链表有什么不同?
    1)打印链表数据
[cpp] view plaincopy
void print_data(const LINK_NODE* pLinkNode)  
{  
    LINK_NODE* pIndex = NULL;  
    if(NULL == pLinkNode)  
        return;  
  
    printf("%d\n", pLinkNode->data);  
    pIndex = pLinkNode->next;  
    while(pLinkNode != pIndex){  
        printf("%d\n", pIndex->data);  
        pIndex = pIndex ->next;  
    }  
}  
    以往,我们发现打印数据的结束都是判断指针是否为NULL,这里因为是循环链表所以发生了变化。原来的条件(NULL != pLinkNode)也修改成了这里的(pLinkNode != pIndex)。同样需要修改的函数还有find函数、count统计函数。


    2)插入数据
[cpp] view plaincopy
STATUS insert_data(LINK_NODE** ppLinkNode, int data)  
{  
    LINK_NODE* pNode;  
    if(NULL == ppLinkNode)  
        return FALSE;  
  
    if(NULL == *ppLinkNode){  
        pNode = create_link_node(data);  
        assert(NULL != pNode);  
  
        pNode->next = pNode;  
        *ppLinkNode = pNode;  
        return TRUE;  
    }  
  
    if(NULL != find_data(*ppLinkNode, data))  
        return FALSE;  
  
    pNode = create_link_node(data);  
    assert(NULL != pNode);  
  
    pNode->next = (*ppLinkNode)->next;  
    (*ppLinkNode)->next = pNode;  
    return TRUE;  
}  
这里的insert函数在两个地方发生了变化:
    a)如果原来链表中没有节点,那么链表节点需要自己指向自己
    b)如果链表节点原来存在,那么只需要在当前的链表节点后面添加一个数据,同时修改两个方向的指针即可


    3) 删除数据
[cpp] view plaincopy
STATUS delete_data(LINK_NODE** ppLinkNode, int data)  
{  
    LINK_NODE* pIndex = NULL;  
    LINK_NODE* prev = NULL;  
    if(NULL == ppLinkNode || NULL == *ppLinkNode)  
        return FALSE;  
  
    pIndex = find_data(*ppLinkNode, data);  
    if(NULL == pIndex)  
        return FALSE;  
  
    if(pIndex == *ppLinkNode){  
        if(pIndex == pIndex->next){  
            *ppLinkNode = NULL;  
        }else{  
            prev = pIndex->next;  
            while(pIndex != prev->next)  
                prev = prev->next;  
  
            prev->next = pIndex->next;  
            *ppLinkNode = pIndex->next;  
        }  
    }else{  
        prev = pIndex->next;  
        while(pIndex != prev->next)  
            prev = prev->next;  
        prev->next = pIndex->next;  
    }  
  
    free(pIndex);  
    return TRUE;  
}  
和添加数据一样,删除数据也要在两个方面做出改变:
    a)如果当前链表节点中只剩下一个数据的时候,删除后需要设置为NULL
    b)删除数据的时候首先需要当前数据的前一个数据,这个时候就可以从当前删除的数据开始进行遍历
    c) 删除的时候需要重点判断删除的数据是不是链表的头结点数据
阅读(789) | 评论(0) | 转发(0) |
0

上一篇:双向链表

下一篇:链表逆转

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