转载

单链表常见操作图文详解

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

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

无头单链表，也就是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

正文到此结束