C语言数据结构：单向链表的增删操作

2024-04-23 08:59 由你也是流星一条发表于 #后端开发
// 指的是单向链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;

// 构造链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct LinkedList
{
    DataType_t data;         // 结点的数据域
    struct LinkedList *next; // 结点的指针域

} LList_t;

// 创建一个空链表，空链表应该有一个头结点，对链表进行初始化
LList_t *LList_Create(void)
{
    // 1.创建一个头结点并对头结点申请内存
    LList_t *Head = (LList_t *)calloc(1, sizeof(LList_t));
    if (NULL == Head)
    {
        perror("Calloc memory for Head is Failed");
        exit(-1);
    }

    // 2.对头结点进行初始化，头结点是不存储有效内容的！！！
    Head->next = NULL;

    // 3.把头结点的地址返回即可
    return Head;
}

// 创建新的结点，并对新结点进行初始化（数据域 + 指针域）
LList_t *LList_NewNode(DataType_t data)
{
    // 1.创建一个新结点并对新结点申请内存
    LList_t *New = (LList_t *)calloc(1, sizeof(LList_t));
    if (NULL == New)
    {
        perror("Calloc memory for NewNode is Failed");
        return NULL;
    }

    // 2.对新结点的数据域和指针域进行初始化
    New->data = data;
    New->next = NULL;

    return New;
}

// 头插
bool LList_HeadInsert(LList_t *Head, DataType_t data)
{
    // 1.创建新的结点，并对新结点进行初始化
    LList_t *New = LList_NewNode(data);
    if (NULL == New)
    {
        printf("can not insert new node\n");
        return false;
    }

    // 2.判断链表是否为空，如果为空，则直接插入即可
    if (NULL == Head->next)
    {
        Head->next = New;
        return true;
    }

    // 3.如果链表为非空，则把新结点插入到链表的头部
    New->next = Head->next;
    Head->next = New;

    return true;
}

// 尾插
bool LList_TailInsert(LList_t *Head, DataType_t data)
{

    // 1.创建新的结点，并对新结点进行初始化
    LList_t *New = LList_NewNode(data);
    if (NULL == New)
    {
        printf("can not insert new node\n");
        return false;
    }

    // 2.判断链表是否为空，如果为空，则直接插入即可
    if (NULL == Head->next)
    {
        Head->next = New;
        return true;
    }

    // 3.如果链表为非空，则把新结点插入到链表的尾部
    LList_t *Last = Head;
    while (Last->next != NULL)
    {
        Last = Last->next;
    }
    New->next = NULL;
    Last->next = New;

    return true;
}

// 指定插
bool LList_DestInsert(LList_t *Head, DataType_t dest, DataType_t data)
{
    // 1.创建新的结点，并对新结点进行初始化
    LList_t *New = LList_NewNode(data);
    if (NULL == New)
    {
        printf("can not insert new node\n");
        return false;
    }

    // 2.判断链表是否为空，如果为空，则直接插入即可
    if (NULL == Head->next)
    {
        Head->next = New;
        return true;
    }

    // 3.遍历链表，目的是找到目标结点，比较结点的数据域
    LList_t *Dest = Head->next;
    while (Dest->data != dest && Dest != NULL)
    {
        Dest = Dest->next;
    }
    if (NULL == Dest)
    {
        return false;
    }

    // 4.说明找到目标结点，则把新结点插入到目标结点的后面
    New->next = Dest->next;
    Dest->next = New;

    return true;
}

// 头删
bool LList_HeadDel(LList_t *Head, DataType_t data)
{
    // 1.对链表的首结点的地址进行备份
    LList_t *Temp = Head->next;

    // 2.判断链表是否为空，如果为空，则直接退出
    if (NULL == Head->next)
    {
        return false;
    }

    // 3.链表是非空的，则直接删除首结点
    Head->next = Temp->next;
    Temp->next = NULL;
    free(Temp);

    return true;
}

// 尾删
bool LList_TailDel(LList_t *Head, DataType_t data)
{
    LList_t *SecondLast = Head;
    while (SecondLast->next->next != NULL)
    {
        SecondLast = SecondLast->next;
    }
    free(SecondLast->next);
    SecondLast->next = NULL;

    return true;
}

// 指定删
bool LList_DestDel(LList_t *Head, DataType_t dest, DataType_t data)
{
    LList_t *LDest = Head;
    while ((LDest->next)->data != dest)
    {
        LDest = LDest->next;
    }
    LDest->next = LDest->next->next;
    free(LDest->next);
    return true;
}

// 设计一个算法删除单链表L(有头结点)中的一个最小值结点
bool LList_MinDel(LList_t *Head, DataType_t data)
{
    LList_t *LDest = Head;
    LList_t *LMin = LDest;
    while (LDest->next != NULL)
    {
        if ((LDest->next->next)->data < (LMin->next)->data)
        {
            LMin->next = LDest->next->next;
            LMin = LDest->next;
        }
        LDest = LDest->next;
        LDest->next = LDest->next->next;
    }
    LMin->next = LMin->next->next;

    LMin->next->next = NULL;
    free(LMin->next);

    return true;
}

// 遍历
void LList_Print(LList_t *Head)
{
    // 对链表的头文件的地址进行备份
    LList_t *Phead = Head;

    // 首结点
    while (Phead->next)
    {
        // 把头的直接后继作为新的头结点
        Phead = Phead->next;

        // 输出头结点的直接后继的数据域
        printf("data = %d\n", Phead->data);
    }
}

int main(int argc, char const *argv[])
{
    return 0;
}