数据结构：单链表

单链表

基本概念

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

链表的分类

根据链表中各个节点之间使用指针的个数，以及首尾节点是否相连，可以将链表细分为如下种类：
1. 单向链表
2. 单向循环链表
3. 双向链表
4. 双向循环链表
这些不同链表的操作都是差不多的，只是指针数目的异同。以最简单的单向链表为例，其基本示意
图如下所示：

上图中，所有的节点均保存一个指针，指向其逻辑上相邻的下一个节点（末尾节点指向空）。另外
注意到，整条链表用一个所谓的头指针 head 来指向，由 head 开始可以找到链表中的任意一个节
点。head 通常被称为头指针。
链表的基本操作，一般包括：
1. 节点设计
2. 初始化空链表
3. 增删节点
4. 链表遍历
5. 销毁链表
下面着重针对这几项常见操作，讲解单向链表的处理。

单链表节点设计   

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

typedef int DATA;
typedef struct Node
{
 DATA data;    // 存储数据---数据域
 struct Node *next;  // 存储下一个节点的地址---指针域
} NODE;

单链表初始化   

首先，空链表有两种常见的形式。一种是带所谓的头结点的，一种是不带头结点的。所谓的头结点
是不存放有效数据的节点，仅仅用来方便操作，如下：

而不带头结点的空链表如下所示：

注意：
头指针 head 是必须的，是链表的入口

头节点是可选的，为了方便某些操作
 
由于头结点是不存放有效数据的，因此如果空链表中带有头结点，那么头指针 head 将永远不变，
这会给以后的链表操作带来些许便捷。
下面以带头结点的链表为例，展示单向链表的初始化的示例代码：

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;
}

单链表增删节点

相对于顺序表需要整片移动数据，链表增删节点只需要修改几个相关指针的指向，动作非常快速。
与顺序表类似，可以对一条链表中的任意节点进行增删操作，示例代码是：

/*
@function:   int slist_addHead(NODE** head,DATA data);
@berif:     向链表头部插入一个节点数据
@argument:   head: 指向头指针变量的地址，用来接收首节点地址
             data: 存储在新节点中的数据
@return :   成功返回 0
失败返回 -1
*/
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;   
}
/*
@function:   int slist_addTail(NODE** head,DATA data);
@berif:     向链表尾部插入一个节点数据
@argument:   head: 指向头指针变量的地址，用来接收首节点地址
             data: 存储在新节点中的数据
@return :   成功返回 0
             失败返回 -1
*/
int slist_addTail(NODE** head,DATA data)
{
    NODE * pNew = (NODE*)malloc(sizeof(NODE));
    if(!pNew)
   {
        return -1;
   }
    pNew -> data = data;
    pNew -> next = NULL;
    NODE* p = *head, *q = NULL;
    if(!p)
   {
        *head = pNew;
        return 0;    
   }
    while(p)
   {
        q  = p;
        p  = p -> next;
   }
    q -> next = pNew;
 return 0;
}
/*
@function:   int slist_insert(NODE** head,DATA pos ,DATA data);
@berif:     向链表节点值为pos的位置插入一个节点数据data
@argument:   head: 指向头指针变量的地址
             pos: 插入节点位置的节点数据
             data: 存储在新节点中的数据
@return :   成功返回 0
             失败返回 -1
*/
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;
    if(!p)
   {
        *head = pNew;
        return 0;
   }
    if(memcmp(&(p -> data),&pos,sizeof(DATA)) == 0)
   {
        pNew -> next = *head;
        *head = pNew;
        return 0;
   }
    while(p)
   {
         if(memcmp(&(p -> data),&pos,sizeof(DATA)) == 0)
         {
               pNew -> next = p;
               q -> next = pNew;
               return 0;
         }
         q  = p;
         p  = p -> next;
   }
    q -> next = pNew;
    return 0;
}
/*
@function:   int slist_update(const NODE* head,DATA old,DATA newdata);
@berif:     更新链表数据old 为 newdata
@argument:   head: 指向头指针变量
             old: 待更新的节点数据
             newdata: 更新后的节点数据
@return :   成功返回 0
             失败返回 -1
*/
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;
}
/*
@function:   int slist_delete(NODE** head,DATA data);
@berif:     删除链表中节点值为data的节点
@argument:   head: 指向头指针变量的地址
             data: 删除节点中的数据
@return :   成功返回 0
             失败返回 -1
*/
int slist_delete(NODE** head,DATA data)
{
    NODE *p = *head, *q = NULL;
    if(!p)
      return -1;
    if(memcmp(&(p -> data),&data,sizeof(DATA)) == 0)
   {
        *head = p -> next;
        free(p);
        return 0;
   }
    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;
}

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

单链表的遍历   

遍历的意思就是逐个访问每一个节点，对于线性表而言，由于路径唯一的选择就是从头走到尾。因
此相当而言比较简单。
下面是单向链表的遍历示例代码，假设遍历每个节点并将其整数数据输出：

/*
@function:   NODE* slist_find(const NODE* head,DATA data);
@berif:     查找链表数据data
@argument:   head: 指向头指针变量
             data: 待查找的数据
@return :   成功返回节点的地址
             失败返回NULL
*/
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;
}
/*
@function:   void slist_showAll(const NODE* head);
@berif:     遍历链表数据
@argument:   head: 指向头指针变量
@return :   无
*/
void slist_showAll(const NODE* head)
{
     const NODE*  p  = head;
    
     while(p)
     {
          printf("%d ",p -> data);
          p = p -> next;
     }
     printf("\n");
}

单链表的销毁   

由于链表中的各个节点被离散地分布在各个随机的内存空间，因此销毁链表必须遍历每一个节点，
释放每一个节点。
注意：
销毁链表时，遍历节点要注意不能弄丢相邻节点的指针

链表优缺点

链式存储中，所有节点的存储位置是随机的，他们之间的逻辑关系用指针来确定，跟物理存储位置
无关，因此从上述示例代码可以很清楚看到，增删数据都非常迅速，不需要移动任何数据。另外，
又由于位置与逻辑关系无关，因此也无法直接访问某一个指定的节点，只能从头到尾按遍历的方式
一个个找到想要的节点。简单讲，链式存储的优缺点跟顺序存储几乎是相对的。
总结其特点如下：
优点
1. 插入、删除时只需要调整几个指针，无需移动任何数据
2. 当数据节点数量较多时，无需一整片较大的连续内存空间，可以灵活利用离散的内存
3. 当数据节点数量变化剧烈时，内存的释放和分配灵活，速度快
缺点
1. 在节点中，需要多余的指针来记录节点之间的关联。
2. 所有数据都是随机存储的，不支持立即访问任意一个随机数据。

原文地址：https://blog.csdn.net/m0_58371281/article/details/145105218

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！