数据结构--单向链表

如果对于顺序表的结构已经大致了解，那么对单向链表的学习就会轻松一些。

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

顺序表和链表在内存在的基本样态如下图所示

根据链表中各个节点之间使用指针的个数，以及首尾节点是否相连，可以将链表分为如下种类：

1. 单向链表 （只有一个指针（一个方向），指向下一个数据的入口地址）
2. 单向循环链表（只有一个指针，最后一个数据的指针存储的是第一个数据的入口地址）
3. 双向循环链表 （有两个指针，分别指向下一个数据，以及上一个数据，并首尾节点是相互指向的）
4. 内核链表 （由系统的头文件提供了所有关于指针的操作，对与指针的操作更为安全）

这些不同链表的操作都是差不多的，只是指针数目的异同。以最简单的单向链表为例，其基本示意图如下所示：

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

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

1. 节点设计

2. 初始化空链表

• 无头节点的链表

// 无头节点的初始化P_Node head = NULL ;

• 有头节点的链表

// 初始化有头结点的链表P_Node head = NewNode( NULL );
// 创建一个新节点作为头节点，但是头结点不需要有数据
// 参数给NULL 表示不需要对数据域进行操作

3. 增删节点

P_Node GetNewNode( DataType * NewData ){    if ( NewData == NULL )    {        printf("请传递正确的数据地址..\n");        return NULL ;    }

    // 申请一个新的节点 （堆内存）
    P_Node NewNode = calloc(  1 , sizeof(Node) );
    if (NewNode == NULL)
    {
        perror("calloc NewNode error") ;
        return NULL ;
    }
    

    // 对该新节点进行初始化 （数据域， 指针域）
    memcpy( &NewNode->Data , NewData , sizeof(DataType));

    NewNode->Next = NULL ;
    
    return NewNode ;
}

P_Node Add2List( P_Node head , P_Node NewNode  )
{
    // 让新节点的后继指针，指向头指针所指向的节点（指定第一个有效数据）
    NewNode->Next = head ;

    // 让头指针指向新节点
    head = NewNode ;

    return head;
}

void Add2List( P_Node head , P_Node New )
{  
// 让新节点的后继指针， 指向第一个有效数据  
New->Next =  head->Next ;  
// 让头节点的后继指针 ， 指向新节点 
head->Next = New ;
}

4. 链表遍历

// 无头节点遍历链表void DisplayList( P_Node head ){    if (head == NULL)    {        printf("当前链表为空....\n");        return  ;    }
    
    // 通过临时指针tmp遍历整个链表 ，只要tmp 不指向NULL 就说明链表还没遍历结束
    for (P_Node tmp = head ; tmp != NULL ; tmp = tmp->Next )
    {
        printf("TMP:%d\n" , tmp->Data );
    }
    
    return ;
}


// 有头节点遍历链表
void DisplayList( P_Node head)
{

    if (head->Next == NULL)
    {
        printf("当前链表为空..\n");
        return ;
    }
    
    //   让 tmp 指向第一个有效数据
    for (P_Node tmp = head->Next ; tmp != NULL ; tmp = tmp->Next )
    {
        printf("tmp:%d\n" , tmp->Data );
    }
}

5. 销毁链表

销毁的方式可以有多种，比如循环进行销毁，或者递归实现。

递归思路：

通过递归不断往链表末尾移动，当递归到链表的末尾节点时进行释放以及返回。

递进时不断往末尾移动，回归时从末尾不断释放节点。

P_Node DestroyList( P_Node ptr ){    // 检查当前指针ptr 是否指向最后一个节点    if (ptr->Next == NULL )    {        printf("Name:%s:%d\n" , ptr->Data.Name , ptr->Data.Num );        free(ptr);        return NULL ;
    }
    // 如果当前节点不是末尾节点，则递进向链表末尾
    DestroyList( ptr->Next );
    printf("Name:%s:%d\n" , ptr->Data.Name , ptr->Data.Num );

    free(ptr);

    return NULL ;
}

链表插入的变形：

循环链表：

初始化循环链表：

P_Node NewNode( DataType * NewData )
{
    // 为新节点申请堆内存
    P_Node New = calloc(1, sizeof(Node) );

    
    // 判断是否需要初始化数据域
    if ( NewData )
    {
        memcpy( &New->Data , NewData );
    }
    
    // 初始化指针域
    New->Next = New ;

    return New ;
}

到此，单向链表的知识点分布就结束了，如下为样例代码

//因为单项链表可写为无头、有头、循环，太多就不放代码了