链表¶

//链表数据的打印（遍历链表）
void SLTPrint(SLTNode* phead);
//头部插⼊删除/尾部插⼊删除 
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
//查找链表中的数据 
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插⼊数据 
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点 
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插⼊数据 
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点 
void SLTEraseAfter(SLTNode* pos);
//销毁链表 
void SListDesTroy(SLTNode** pphead);

//链表数据的打印（遍历链表）
void SLNPrint(SLN* phead)
{
    SLN* pstart = phead;//定义一个临时结构体指针变量，直接使用phead遍历会使最后找不到链表的开始处
    //使用while循环遍历
    //结束条件是pstart不为空指针，因为pstart在遍历的过程中会被更新为当前结构体的下一个结构体地址
    //一旦pstart存储为最后一个节点中存储地址的部分的NULL值则退出循环
    while (pstart)
    {
        printf("%d->", pstart->data);
        pstart = pstart->next;
    }
    printf("NULL\n");
}

//开辟新空间，用于存储需要插入的新数据
SLN* applySpace(SListDataType x)
{
    SLN* phead = (SLN*)malloc(sizeof(SLN));
    assert(phead);
    phead->data = x;
    //开辟的新空间中，存储下一个节点地址的部分要置为空，防止野指针
    phead->next = NULL;

    return phead;
}

//链表的头部插入
void SLNPushFront(SLN** pphead, SListDataType x)
{
    assert(pphead);
    SLN* newnode = applySpace(x);

    //将形参指向的链表的第一个节点的地址给新开辟的节点中的存储下一个节点地址部分
    newnode->next = *pphead;
    *pphead = newnode;//将初始的第一个节点中存储下一个节点的部分存储新开辟的节点的地址
}

void SLNPushBack(SLN** pphead, SListDataType x)
{
    assert(pphead);

    //开辟新空间
    SLN* newnode = applySpace(x);
    //如果新开辟的空间为链表的第一个节点，则将新节点作为首节点
    if (*pphead == NULL)
    {
        *pphead = newnode;
        return;
    }
    //尾部插入的前提是先找到最后一个节点
    //因为最后一个节点中存储下一个节点地址的部分为NULL，故可以遍历链表直到找到该部分为NULL为止
    SLN* pmove = *pphead;//防止丢失链表的第一个节点
    //使用next作为终止条件，而不是pmove为终止条件，当pmove为终止条件时，即pmove = NULL，
    while (pmove->next)
    {
        pmove = pmove->next;
    }

    pmove->next = newnode;
}

//链表的头部删除
void SLNPopFront(SLN** pphead)
{
    assert(pphead);

    //判断链表是否为空链表
    //如果为空链表则不执行删除操作
    if (*pphead == NULL)
    {
        return;
    }

    SLN* BlocktoFree = *pphead;
    //如果链表不为空时，执行删除操作

    //释放完空间后首节点需要改变
    *pphead = (*pphead)->next;
    //删除节点需要释放开辟的内存空间
    free(BlocktoFree);
}

//链表的尾部删除void SLNPopBack(SLN** pphead)
{
    assert(pphead);

    //删除之前需要判断链表是不是空链表
    //如果是空链表则不执行删除操作
    if (*pphead == NULL)
    {
        return;
    }

    //如果链表只有一个节点时
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
        return;
    }

    //如果链表不为空且有多个节点时，执行删除操作
    //先找到尾结点
    SLN* p_end = *pphead;
    SLN* pprev = p_end;
    while (p_end->next)
    {
        pprev = p_end;
        p_end = p_end->next;
    }
    //将倒数第二个节点的存储下一个节点地址的部分置为空
    pprev->next = NULL;
    //释放尾结点的空间
    free(p_end);
    p_end = NULL;
}

//查找链表中的数据
SLN* SLNFind(SLN* phead, SListDataType x)
{
    SLN* pcur = phead;
    //遍历链表数据
    while (pcur)
    {
        //找到数据返回数据所在节点的地址
        if (pcur->data == x)
        {
            return pcur;
        }
        pcur = pcur->next;
    }
    //未找到数据返回空指针
    return NULL;
}

//在指定位置之前（在指定位置）插入数据
void SLNInsert(SLN** pphead, SLN* pos, SListDataType x)
{
    assert(pphead);
    //插入的位置不可以为空，否则插入无效
    assert(pos);
    //插入的链表不能为空，否则不存在pos所指向的位置
    assert(*pphead);

    //开辟空间
    //在指定位置之前插入数据时，需要考虑该位置是不是头结点
    //如果需要插入的位置为头结点的位置，则相当于是头部插入操作
    if (pos == *pphead)
    {
        SLNPushFront(pphead, x);
        return;
    }
    //如果需要插入的位置不是头结点位置，则进行后续插入操作
    SLN* newnode = applySpace(x);
    SLN* pprev = *pphead;
    //遍历链表找到pos指向的位置
    while (pprev->next != pos)
    {
        pprev = pprev->next;
    }
    //更改前一节点指针的存储下一节点位置部分的地址为新节点的地址
    pprev->next = newnode;
    //更改新节点的存储下一节点部分的地址为pos
    newnode->next = pos;
    //上述两步可以交换执行顺序
}

//在指定位置之后插⼊数据 
void SLNInsertAfter(SLN* pos, SListDataType x)
{
    assert(pos);

    //指定位置之后插入数据时注意节点连接顺序
    SLN* newnode = applySpace(x);

    //将新节点中的存储下一节点地址的部分赋值为pos后一节点的地址
    newnode->next = pos->next;
    //将pos节点中的存储下一节点地址的部分赋值为新节点的地址
    pos->next = newnode;
    //上述两步不可以交换执行顺序
}

//删除指定位置的节点
void SLNEraseAfter(SLN* pos)
{
    assert(pos);

    //如果pos之后的节点为空，则不执行删除操作
    if (pos->next == NULL)
    {
        return;
    }

    SLN* BlockToFree = pos->next;
    //如果pos之后的节点不为空，执行删除操作
    //将pos节点的存储下一个节点地址的部分更改为待删除节点的后一个节点地址
    pos->next = pos->next->next;
    free(BlockToFree);
    BlockToFree = NULL;
}

//销毁链表 
void SLNDesTroy(SLN** pphead)
{
    assert(pphead);

    SLN* pcur = *pphead;
    //循环销毁链表
    while (pcur)
    {
        SLN* BlockToFree = pcur;
        pcur = pcur->next;
        free(BlockToFree);
    }
    *pphead = NULL;
}

//双向链表初始化
//由于要对双向链表中的头结点的地址进行修改并且也需要改变头结点的内容，故传入二级指针
void DLNInit(DLN** pphead)
{
    *pphead = (DLN*)malloc(sizeof(DLN));
    assert(*pphead);
    //将头结点的数据置为任意值
    (*pphead)->data = -1;//亦可以写成(**pphead).data = -1;
    //将头结点的指针域改为置为指向自己的地址
    (*pphead)->pprev = (*pphead)->next = *pphead;
}
//或者写成带有返回类型的形式
DLN* DLNInit_1()
{
    DLN* phead = (DLN*)malloc(sizeof(DLN));
    assert(phead);
    phead->data = -1;
    phead->pprev = phead->next = phead;

    return phead;
}

//双向链表的打印
void DLNPrint(DLN* phead)
{
    assert(phead);

    //循环打印双向链表中的值
    //循环条件为指针下一次的位置不为头结点的位置，防止打印头结点中的无效数据
    DLN* pcur = phead->next;
    while (pcur != phead)
    {
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }
    printf("|\n");
}