β

单链表常见操作图文详解

Harries Blog™ 3 阅读

单链表的最大特点是可以将物理地址上不连续的 数据 连接起来,通过指针来对物理地址进行操作,实现增删改查等功能。

单链表分为两种:有头链表和无头链表。

无头单链表,也就是phead一只是一个指针,指向链表的第一个节点。

单链表常见操作图文详解

带头节点的单链表:只不过头结点的data不保存信息。

单链表常见操作图文详解

//构建一个节点

typedef struct Node
{
    DataType data;
    struct Node *next;

}Node,*PHead;
//1.初始化单链表
void InitListNode(PNode *pHead)
{
    assert(pHead);
    *pHead = NULL;
}
//2.构建一个结点
 PNode BuyNode(DataType _data)
{
    PNode node = (PNode)malloc(sizeof(Node));
    if (node)
    {
         node->data = _data;
         node->next = NULL;
    }
    return node;
}
/*3.尾插 考虑因素:链表为空时,直接让phead指向新节点即可。 链表不空时,遍历一遍链表,找到最后一个链表,连接在最后一个链表的后面即可。 */
void PushBack(PNode *pHead,DataType _data)
{
    assert(pHead);
    PNode newNode = BuyNode(_data);
    if (NULL == (*pHead))
    {
        *pHead = newNode;
        return ;
    }
    PNode pCur = *pHead;
    while (pCur->next)
    {
        pCur = pCur->next;
    }
    pCur->next = newNode;
}

尾插图解:

单链表常见操作图文详解

/*4.尾删 考虑因素:链表为空时,直接返回 
链表中只有一个结点时,free这个节点,并将phead置空 链表中有多个节点时,遍历一遍链表,找到最后一个节点(pCur->next == NULL),并且保存最后一个节点的前一个节点的信息 */
void PopBack(PNode *pHead)
{
    assert(pHead);
    if (NULL == (*pHead))
    {
        return ;
    }
    else if (NULL == (*pHead)->next)
    {
        free(*pHead);
        *pHead = NULL;
    }
    else
    {
        PNode pCur = *pHead;
        PNode prev = pCur;
        while (pCur->next)
        {
            prev = pCur;
            pCur = pCur->next;
        }
        free(pCur);
        prev ->next = NULL;
    }
}

尾删图解:

单链表常见操作图文详解

/*5.头插 考虑因素: 链表为空时:直接让phead指向新的节点即可。 当链表有一个节点或者多个节点时: 如图示:*/
void PushFront(PNode *pHead,DataType _data)
{
    assert(pHead);
    PNode newNode = BuyNode(_data);
    if (NULL == (*pHead))
    {
        *pHead = newNode;
    }
    else
    {
        if (newNode)
        {
            newNode->next = *pHead;
            *pHead = newNode;
        }
    }
}

头插示意:

单链表常见操作图文详解

/*6.头删 考虑因素: 链表为空时:直接返回,不需要删除 链表不为空时:当只有一个节点时:free掉这个节点,并将phead置空。 当有多个节点时:如图示 分析可知:有一个节点和有多个节点可以使用相同的逻辑*/
void PopFront(PNode *pHead)
{
    assert(pHead);
    if (NULL == (*pHead))
    {
        return ;
    }
    PNode pDel = *pHead;
    *pHead = (*pHead)->next;
    free(pDel);
}

头删图解:

单链表常见操作图文详解

/*7.逆序打印单链表(递归): */
void printFromTailToFront(PNode pHead)
{
    if (pHead)
    {
        printFromTailToFront(pHead->next);
        printf("%d->",pHead->data);
    }
}
/*8.查找一个值为data的节点,如果存在,返回所在位置,否则,返回NULL 
只需要遍历一遍链表即可。 */
PNode Find(PNode pHead, DataType _data)
{
    if (NULL == pHead)
    {
        return NULL;
    }
    PNode pCur = pHead;
    while (pCur)
    {
        if (pCur->data == _data)
        {
            return pCur;
        }
        pCur = pCur->next;
    }
    return NULL;
}
//插入一个节点
void InsertNode(PNode pos,DataType _data)
{
    if (pos)
    {
        PNode newNode = BuyNode(_data);
        if (newNode)
        {
            newNode->next = pos->next;
            pos->next = newNode;
        }
    }
}
/*9.插入一个节点(由于是单链表,所以只能插在pos位置的后面) 需考虑的因素: ①检查参数(链表是否存在,pos位置是否为空) ②当pos位置不空时:如图示*/
void InsertNode(PNode pos,DataType _data)
{
    if (pos)
    {
        PNode newNode = BuyNode(_data);
        if (newNode)
        {
            newNode->next = pos->next;
            pos->next = newNode;
        }
    }
}

插入一个节点图解:

单链表常见操作图文详解

*10.删除pos位置上的一个节点: 需要考虑的因素: ①链表为空和pos为空,直接返回 
②pos不为空且pos为1时,这时就可以转化为删除第一个节点,操作步骤同上面的头删 
③当pos不是第一个节点时,分析如图示:*/
void Erase(PNode* pHead, PNode pos)
{
    assert(pHead);
    if ((NULL == (*pHead)) && (NULL == pos))
    {
        return ;
    }
    if((*pHead) == pos)
    {
        *pHead = pos->next;
        free(pos);
    }
    else
    {
        PNode pCur = *pHead;
        while (pCur ->next != pos)
        {
            pCur = pCur->next;
        }
        pCur->next = pos->next;
        free(pos);
    }
}

删除pos位置结点图解:

单链表常见操作图文详解

/*11.删除单链表中值为_data的节点*/
void Remove(PNode* pHead, DataType _data)
{
    assert(pHead);
    Erase(pHead, Find(*pHead,_data));
}
/*12.删除单链表中所有值为_data的节点: 
需考虑: ①第一个节点的值是_data,因为删除第一个节点需要修改phead的值,所以需要单独处理第一个节点的值是_data的时候。 
删除第一个节点就是上面所说的头删。 
②如果第一个节点的值不是_data,直接处理即可。 下面处理第一个值不是_data(这里的_data为2)的情况:*/
void RemoveAll(PNode *pHead, DataType _data)
{
    assert(pHead);
    if (NULL == (*pHead))
    {
        return ;
    }
    PNode pDel = *pHead;
    if ((*pHead)->data == _data)
    {
        *pHead = (*pHead)->next;
        free(pDel);
    }
    PNode pCur = *pHead;
    PNode prev = pCur;
    while (pCur)
    {
        if (pCur->data == _data)
        {
            prev->next = pCur->next;
            free(pCur);
            pCur = prev->next;
        }
        else
        {
            prev = pCur;
            pCur = pCur->next;
        }
    }    
}

删除单链表中所有值为_data的结点图解:

单链表常见操作图文详解

/*13.打印单链表:*/
void printList(PNode phead)
{
    PNode pCur = phead;
    while (pCur)
    {
        printf("%d ",pCur->data);
        pCur = pCur->next;
    }
    printf("/n");
}
/*14.得到单链表中节点的个数: */
size_t Size(PNode pHead)
{
    size_t count = 0;
    while (pHead)
    {
        pHead = pHead->next;
        count++;
    }
    return count;
}

原文

http ://blog.csdn.net/fanyun_01/article/details/79831877

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。 PS:如果您想和业内技术大牛交流的话,请加qq群(474807195)或者关注微信公众号(AskHarries),谢谢!

转载请注明原文出处: Harries Blog™ » 单链表常见操作图文详解

作者:Harries Blog™
追心中的海,逐世界的梦
原文地址:单链表常见操作图文详解, 感谢原作者分享。

发表评论