链表与内存块

项目原因从来没有接触过链表，今天花了半天的时间研究了下链表，发现用的是二级指针，又研究了下二级指针，编写了几个链表小程序，将收获整理如下。

链表与内存块

链表实际上就是把一块块的内存通过指针连接起来。这些内存有可能是在物理地址上连续的，也有可能是不连续的，不过这不重要，因为在链表中有指针把这些地址连接起来。所以我们可以把链表看成是多个内存块的连接，就如同一根绳上栓了好多蚂蚱，虽然蚂蚱本身没有连接起来，但是通过这个绳子（链表）连接起来，因此，我们可以顺着绳子找到所有的蚂蚱（链表中的节点，也就是一个内存块中的数据）。

链表节点结构体（蚂蚱原型）

下面是我定义的节点结构体，用来存放我需要存放的数据，结构体定义如下：

struct node
{
    U8 index; // 序号索引，第几个蚂蚱
    U8 data; //存放的数据，这个可以根据自己的需要扩展，蚂蚱本身的属性，大小年龄等
    struct node *next;//指向下一个节点（蚂蚱）的指针
};

其中的next指针便是链表的精髓，它将链表中单个互不相关的节点通过next指针相互连接起来，第一个节点指向第二个节点，第二个节点指向第三个节点，依次类推，将所有节点串联起来。

建立好节点后，需要对整个链表上的节点进行操作，一般为增加节点、删除节点、修改节点内容等。

链表操作：增加节点

增加节点的便是把上一个节点的next指针指向本节点，将本节点的next指针指向上一个节点的后一个节点。如原来节点排列为A B C，我们需要在B后面增加节点D，可以这样操作：
B->next = D;
D->next = C;
搞定，是不是很简单。当然，在实际使用时可能会比这两条语句稍微复杂一些，不过思想是一样的。下面是我写的几个增加节点的小程序，亲测可用。

以下程序中定义的head均为需要操作的链表表头地址，item为添加的节点指针，index为需要操作的节点序号。

增加一个节点到链表尾部

/* head -- 已存在的链表 item -- 要增加的节点 */
// 这里为什么要用二级指针定义head呢，因为head本身是一个链表也就是本身是一个指针，它存储的是一个地址，因此，要改变它的内容（也就是它存储的地址的值），需要在此基础上再定义一次指针，也就是二级指针
void NodeAddTail(struct node **head, struct node *item)
{
    struct node *temp;
        
    /* 链表为空时直接添加 */
    if (*head == NULL) //链表头中的地址为空 *取二级指针的值为一级指针（地址）
    {
        *head = item; 
        (*head)->next = NULL;
    }
    else
    {
        temp = *head;
        while(temp)
        {
            if (temp->next == NULL)
            {
                temp->next = item;
                item->next = NULL;
            return;
            }
            temp = temp->next;
        }
    }
    return;
}

增加一个链表到节点头部，使其成为第一个节点

void NodeAddHead(struct node **head, struct node *item)
{
    /* 链表为空 */
    if (*head == NULL)
    {
        *head = item;
        (*head)->next = NULL;
    }
    else
    {
        item->next = (*head); /* 把头部节点指向的第二节点的地址给item */
        (*head) = item;            /*把item给头部节点*/
    }
    return;
}

在指定节点后增加节点

U8 NodeAddIndex(struct node **head, struct node *item,U8 addindex)
{
    struct node *temp;

    //链表为空
    if (*head == NULL)
    {
        *head = item;
        (*head)->next = NULL;
        printf("AddIndex=空\r\n");
        return 0;
    }
    else
    {
        temp = *head;

        while(temp)
        {
            if (temp->index == addindex)//找到指定节点
            {
                item->next = temp->next;
                temp->next = item;
                return 1;
            }
            else
            {
                temp = temp->next;
            }
        }
        printf("AddIndex=没有找到对应节点\r\n");
        return 2;//没有找到对应节点
    }    
}

链表操作：删除节点

删除节点的思想也很简单，例如原来链表顺序为 A B C D ，我们需要删除第二号节点也就是B节点，只需要找到B节点，然后使
A->next = C;
即可。关于如何找到节点B，这需要根据自己定义的数据内容来判断，如我是根据节点结构体红的index变量来查找。
下面是程序例子

U8 NodeDelIndex(struct node **head, U8 delindex)
{
    struct node *temp1;
    struct node *temp2;

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

        if (temp1->index == delindex)
        {
            *head = temp1->next;
            return 1;
        }

        while(temp1->next)
        {
            temp2 = temp1;
            temp1 = temp1->next;

            if (temp1->index == delindex) /*类比节点B*/
            {
                temp2->next = temp1->next; //类比A->next = C
                return 1;
            }
        }
    }
    printf("DelIndex=没有找到对应节点\r\n");
    return 2;
}

链表操作：修改节点数据

修改数据其实更为简单，找到需要修改的节点，然后修改即可。

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

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

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

链表操作：获取节点个数

//获取单向链表的节点个数
U16 GetNodeNum(struct node **head)
{
    U16 num = 0;
    struct node *temp;

    if (*head == NULL)
    {
        return num;
    }
    else
    {
        temp = *head;
        num++;
        while(temp)
        {
            if (temp->next == NULL)
            {
                return num;
            }
            temp = temp->next;
            num++;
        }
    }
   return num;
}

链表打印

void NodeListPrint(struct node **head)
{
    struct node *temp;

    if (*head == NULL)
    {
        printf("空\r\n");
        return 0;
    }
    else
    {
        temp = *head;
        
        while(temp)
        {
            printf("index=0x%02x",temp->index);
            printf("  data=0x%02x\r\n",temp->data);
            
            temp = temp->next;
        }
    }
}

以上是根据链表特性编写的几个小函数，测试后均可以实现特定的功能。

下面是主函数。

void main()
{
    struct node *NewNodeList = NULL; /*定义链表表头*/
    struct node Node1,Node2,Node3,Nodeadd;/*定义几个操作的节点*/
    U8 datamodify = 0xAB;/* 将原来的数据修改为0XAB */  
    U8 num=0;/* 链表节点个数 */
 
    /* 赋初值 */
    Node1.index = 0x1;
    Node1.data = 0x11;
    Node1.next = NULL;

    Node2.index = 0x2;
    Node2.data = 0x22;
    Node2.next = NULL;

    Node3.index = 0x3;
    Node3.data = 0x33;
    Node3.next = NULL;

    Nodeadd.index = 0x4;
    Nodeadd.data= 0x44;
    Nodeadd.next = NULL;    
    

    //1. 分别把Node1,2,3 加入链表
    NodeAddTail(&NewNodeList,&Node1);
    NodeAddTail(&NewNodeList,&Node2);
    NodeAddTail(&NewNodeList,&Node3);
    
    //2. 在链表头部增加元素
    NodeAddHead(&NewNodeList,&Nodeadd);
    NodeListPrint(&NewNodeList);

    //3. 在指定节点后增加元素
    NodeAddIndex(&NewNodeList,&Nodeadd,4);
    NodeListPrint(&NewNodeList);

    //4. 在指定节点删除元素
    NodeDelIndex(&NewNodeList,1);
    NodeDelIndex(&NewNodeList,2);
    NodeDelIndex(&NewNodeList,3);
    NodeDelIndex(&NewNodeList,4);
    NodeListPrint(&NewNodeList);
    
    //5. 修改某个节点元素的值
    NodeModifyIndex(&NewNodeList,&datamodify,0);
    NodeListPrint(&NewNodeList);
    
    //6. 获取链表节点个数
    num = GetNodeNum(&NewNodeList);
    printf("个数为%2d\r\n",num);

    //7. 打印节点结构体大小
    printf("\r\n%2d",sizeof(U8));
    printf("\r\n%2d",sizeof(struct node));
}