链表与内存--头节点和链表分割

上篇写到了链表，后来发现自己对链表的理解还有些偏差，重新做了下链表测试，优化了相关代码。
主要改动的地方是：之前理解的链表为一个节点一个节点串联起来，后来查看资料，发现如果给链表增加一个空节点，使用起来会更加方便。也就是说，链表表头的第一个节点只有地址，没有实际数据，当然我们也可以给他填充上一些数据比如链表长度等。从第二个节点开始节点有了地址和数据，我们称第二个节点为头指针。很显然，头节点不一定是头指针，头节点可以没有，但头指针必须有。
[头节点] -> [头指针]->[ ] -> NULL
那么加入头节点之后，代码瞬间就变得统一起来，而且也更加好理解。
如增加一个节点到链表，可以如下定义，可对比之前的文章中的添加节点代码。
下面是增加头节点后的代码，敬请参考。

增加元素到链表

/* 增加一个元素到链表中 
*     head -- 链表头节点
*     item -- 要增加的加点
*    Opr  -- 0(增加到头指针) -1(增加到尾指针) >0 增加到对应节点之后
*/
U8 NodeAdd(struct node **head, struct node *item, S8 Oper)
{
    struct node *temp;
        
    /* 头节点为空,链表未分配地址 */
    if (*head == NULL)
    {
        return 0;
    }

    /* 添加到头指针 */
    if (Oper == 0)
    {
        item->next = (*head)->next;
        (*head)->next = item;
        (*head)->data++;
        return 1;
    }
    else if (Oper == -1) /* 添加到尾指针 */
    {
        temp = (*head)->next; /* 获取链表头指针 */
            while(temp)
        {
            if (temp->next == NULL)
            {
                item->next = *head;
                //item->next = NULL;         /* 先续尾 */
                temp->next = item;        /* 再接头 */
                (*head)->data++;
                return 1;
            }
            temp = temp->next;
        }
    }
    else
    {
        temp = (*head)->next; /* 获取链表头指针 */
        while(temp)
        {
            if (temp->index == Oper)
            {
                item->next = temp->next;     /* 先续尾 */
                temp->next = item;            /* 再接头 */
                (*head)->data++;
                return 1;
            }
            temp = temp->next;
        }
    }
    return 2;//节点索引错误
}

删除链表中节点

/* 在链表中删除指定节点 */
U8 NodeDel(struct node **head, U8 DelIndex)
{
    struct node *nodeforward; /* 查询节点指针 */
    struct node *nodetemp;        /* 暂存节点指针 */

    /* 头节点空 */
    if (*head == NULL)
    {
        return 0;
    }

    nodeforward = (*head); /* 查询指针指向头节点 */

    while(nodeforward->next)
    {
        nodetemp = nodeforward; 
        nodeforward = nodeforward->next;

        if (nodeforward->index == DelIndex)
        {
            nodetemp->next = nodeforward->next;
            (*head)->data--;
            return 1;
        }
    }
    return 2;
}

修改指定节点的值

//修改指定节点中的值
U8 NodeModifyIndex(struct node **head, U8 *data,U8 modifyindex)
{
    struct node *temp;

    if (*head == NULL)
    {
        return 0;
    }

    temp = *head;

    while(temp)
    {
        if (temp->index == modifyindex)//找到指定节点
        {
            memcpy(&temp->data,data,sizeof(temp->data));
            return 1;
        }
        temp = temp->next;
    }
    return 2;//没有找到对应节点
}

将一个链表按顺序分割

/*
*     将一个链表按照给定值val排序，大于等于val的放在后面，小于val的放在前面
*    链表带头结点: [头结点] -> [头指针] -> [] -> []
*    头结点存放结点个数，索引为0
*/
U8 NodeCut2Parts(struct node **head,U8 val)
{
    struct node *temp = NULL;
    struct node *small = NULL;
    struct node *big = NULL;
    struct node *ptrsmall = NULL; /* 指向small链表各结点的指针 */
    struct node *ptrbig = NULL;    

    small = (struct node *)malloc(sizeof(struct node));
    big = (struct node *)malloc(sizeof(struct node));

    ptrsmall = small;
    ptrbig = big;

    if (*head == NULL)/* 链表为空,头节点 */
    {
        free(small);
        free(big);
        return 0;
    }
    else
    {
        temp = (*head)->next;/* 头指针赋值 */
        
        while(temp)
        {
            if (temp->index < val)
            {
                ptrsmall->next = temp;
                ptrsmall = ptrsmall->next; /* small链表节点指针后移 */
            }
            else
            {
                ptrbig->next = temp;
                ptrbig = ptrbig->next;    /* big链表节点指针后移 */
            }
            temp = temp->next; /* 原链表节点指针后移 */
        }
        /* 将大小链表的最后节点指向NULL */
        ptrsmall->next = NULL; 
        ptrbig->next = NULL;

        ptrsmall->next = big->next; /* 大小链表合并 */
        (*head)->next = small->next;/* 合并后赋值给原链表 */
        free(small);
        free(big);
    }
}

主程序可以用来测试功能

void main()
{
    U8 datamodify = 0xAB;
    struct node *NewNodeList;
    struct node Node[10];


    NewNodeList->data = 0;
    NewNodeList->index = 0;
    NewNodeList->next = NULL;

    /* 给10个节点赋值 */
    for (i=0;i<10;i++)
    {
        Node[i].index = i+1;
        Node[i].data = (U8)(((i+1)&0x0F)|(((i+1)<<4)&0xF0));
        Node[i].next = NULL;
    }

    //1. 分别把Node1,2,3 加入链表
    NodeAdd(&NewNodeList,&Node[0],0);
    NodeAdd(&NewNodeList,&Node[5],0);
    NodeAdd(&NewNodeList,&Node[3],0);
    NodeAdd(&NewNodeList,&Node[8],0);
    NodeAdd(&NewNodeList,&Node[1],-1);

    //GetNodeNum(&NewNodeList);
    
    NodeAdd(&NewNodeList,&Node[6],-1);
    NodeAdd(&NewNodeList,&Node[2],-1);
    NodeAdd(&NewNodeList,&Node[7],-1);
    NodeAdd(&NewNodeList,&Node[4],6);
    NodeAdd(&NewNodeList,&Node[9],1);

    //4. 删除指定节点
    NodeDel(&NewNodeList,2);

    //5. 修改某个节点的值
    NodeModifyIndex(&NewNodeList,&datamodify,1);

    NodeCut2Parts(&NewNodeList,5);
}