数据结构与算法-单链表

标签：NODE head 单链 next 链表算法数据结构 data 节点

单链表

链表的介绍

在这里插入图片描述

既然顺序存储中的数据因为挤在一起而导致需要成片移动，那很容易想到的解决方案是将数据离散地存储在不同内存块中，然后在用来指针将它们串起来。这种朴素的思路所形成的链式线性表，就是所谓的链表。

在这里插入图片描述

上图中，所有的节点均保存一个指针，指向其逻辑上相邻的下一个节点（末尾节点指向空）。另外注意到，整条链表用一个所谓的头指针 head 来指向，由 head 开始可以找到链表中的任意一个节点。head 通常被称为头指针。

链表的基本操作，一般包括：

节点设计
初始化空链表
增删节点
链表遍历
销毁链表

单链表的节点设计

单向链表的节点非常简单，节点中除了要保存用户数据之外，只需要增加一个指向本类节点的指针即可，如下所示：

typedef int DATA;

// 创建链表的节点结构体
typedef struct node
{
    DATA         data; // 节点数据
    struct node *next; // 指向下一个同类节点的指针
} NODE;

单链表初始化

空链表有两种常见形式，一种是带头节点的，一种是不带头节点的。所谓的头节点是不存放有效数据的节点，头节点可选，为了方便某些操作。

注：头节点可选，头指针head必须，是链表的入口。


/**
 * 链表的创建
 * @param **head 链表，默认指向头节点
 * @param data 节点数据
 */
int slist_create(NODE **head, DATA data)
{
    // 创建一个新节点
    NODE *p = (NODE *)malloc(sizeof(NODE));
    if (!p)
    {
        return -1;
    }
    // 初始化节点
    p->data = data;
    p->next = NULL;

    // 将创建的节点作为链表的头结点
    *head = p;

    return 0;
}

单链表增加节点

相对于顺序表需要整片移动数据，链表增删节点只需要修改几个相关指针的指向，动作非常快速。此处详细列出了单链表通过头插法、尾插法和任意位置插入的方法。


/**
 * 向链表头部插入一个节点数据（头插法）
 * @param head 指向头指针变量的地址，用来接收首节点地址（头结点）
 * @param data 存储在新节点的数据
 */
int slist_addHead(NODE **head, DATA data)
{
    // 创建一个节点（就是在内存中申请空间）
    NODE *p = (NODE *)malloc(sizeof(NODE));
    if (!p)
        return -1;

    // 初始化节点
    p->data = data;
    p->next = *head;

    // 将当前的新节点作为头结点
    *head = p;

    return 0;
}

/**
 * 向链表尾部插入一个节点数据（尾插法）
 * @param head 指向头指针变量的地址，用来接收首节点地址（头结点）
 * @param data 存储在新节点的数据
 */
int slist_addTail(NODE **head, DATA data)
{
    // 创建一个新节点
    NODE *pNew = (NODE *)malloc(sizeof(NODE));
    if (!pNew)
        return -1;
    // 初始化
    pNew->data = data;
    pNew->next = NULL; // 因为新节点要作为尾结点，所以要指向NULL

    // 通过指针尾随法，实现尾结点的查找
    NODE *p = *head, *q = NULL;
    // 如果*p不存在，也就是空链表
    if (!p)
    {
        // 如果是空链表，就将新节点作为链表的头节点
        *head = pNew;
        return 0;
    }

    // 使用指针尾随找尾结点
    while (p)
    {
        q = p;
        p = p->next;
    }
    // 此时循环结束，p = NULL,q = 尾结点
    // 改变指向，让尾结点的next指向新节点
    q->next = pNew;

    return 0;
}

/**
 * 向链表节点值为pos的位置插入一个节点数据（中间插法）
 * @param head 指向头指针变量的地址，用来接收首节点地址（头结点）
 * @param pos  插入节点（目标节点）的位置的节点数据
 * @param data 存储在新节点的数据
 */
int slist_insert(NODE **head, DATA pos, DATA data)
{
    // 创建一个新节点
    NODE *pNew = (NODE *)malloc(sizeof(NODE));
    if (!pNew)
        return -1;
    // 初始化
    pNew->data = data;
    pNew->next = NULL;

    // 找位置，永远的指针尾随法
    NODE *p = *head, *q = NULL;
    // 情景1：如果是空链表
    if (!p)
    {
        *head = pNew;
        return 0;
    }

    // 情景2：如果链表中只有一个头结点
    if (memcmp(&(p->data), &pos, sizeof(DATA)) == 0) // 此时等价于 p->data == pos
    {
        // 插入到目标节点前面（头插法）
        pNew->next = *head;
        *head = pNew;

        // 插入到目标节点后面
        // p->next = pNew;
        return 0;
    }

    // 情景3：如果链表中有两个或以上节点
    while (p)
    {
        if (memcmp(&(p->data), &pos, sizeof(DATA)) == 0) // 此时等价于 p->data == pos
        {
            // 插入到目标节点前面
            pNew->next = p;
            q->next = pNew;
            return 0;
        }
        q = p;
        p = p->next;
    }
    
    // 情景4：找不到目标节点的位置（就执行尾插法）
    q->next = pNew;

    return 0;
}

单链表删除节点


/**
 * 删除链表中节点值为data的节点
 * @param head 指向头指针变量的地址，用来接收首节点地址（头结点）
 * @param data 待删除节点数据
 */
int slist_delete(NODE **head,DATA data)
{
    NODE *p = *head,*q = NULL;
    // 情景1：空链表
    if(!p)
        return -1;
    // 情景2；只有一个节点
    if(memcmp(&(p->data),&data,sizeof(DATA))==0)
    {
        *head = p->next; // p -> next = NULL;
        free(p);
        return 0;
    }
    // 情景3：超过两个节点的链表
    while(p)
    {
         if(memcmp(&(p->data),&data,sizeof(DATA))==0)
         {
             q->next = p->next;
             free(p);
             return 0;
         }
         q = p;
         p = p->next;
    }
    return -1;
}

注意：删除链表的节点并不意味着释放其内存，而是将其剔除出链表

链表节点数据的修改

修改链表中的数据（不改变链表结构，只修改节点中的数据）


/**
 * 根据数据查询节点（一般给修改用）
 * @param head 指向头指针变量的地址，用来接收首节点地址（头结点）
 * @param data 需要查询节点的数据
 * 
 * @return 返回查询到的节点
 */
NODE* slist_find(const NODE* head,DATA data)
{
    const NODE* p = head;

    while (p)
    {
        if(memcmp(&(p->data),&data,sizeof(DATA))== 0)
        {
            return (NODE*)p;
        }
        p = p->next;
    }
    
    return NULL;  
}


/**
 * 更新链表节点数据old位newdata
 * @param head 指向头指针变量的地址，用来接收首节点地址（头结点）
 * @param old 旧数据
 * @param newdata 新数据
 */
int slist_update(const NODE* head,DATA old,DATA newdata)
{
    NODE* p = NULL;

    if(!(p = slist_find(head,old)))
        return -1;
    // 更新数据
    p->data = newdata;

    return 0;
}

单链表的遍历

遍历的意思就是逐个访问每一个节点，对于线性表而言，由于路径唯一的选择就是从头走到尾。


/**
 * 遍历链表数据
 * @param head 指向头指针变量的地址，用来接收首节点地址（头结点）
 */
void slist_showAll(const NODE *head)
{
    // 首先使用一个变量来接收参数
    const NODE* p = head;

    while(p)
    {
        printf("%d\t",p->data);
        p = p->next; // 循环的最后一次：p = p->next = NULL
    }
    printf("\n");
}

单链表的销毁

由于链表中的各个节点被离散地分布在各个随机的内存空间，因此销毁链表必须遍历每一个节点，释放每一个节点。


/**
 * 回收链表
 * @param head 指向头指针变量的地址，用来接收首节点地址（头结点）
 */
void slist_destroy(NODE **head)
{
    NODE *p = *head,*q = NULL;
    while (p)
    {
        q = p;
        p = p->next;
        free(q);
    }
    *head = NULL;
}

标签：NODE,head,单链,next,链表,算法,数据结构,data,节点
From： https://blog.csdn.net/Are_pro_bald/article/details/144991496