无头链表二级指针方式实现(C语言描述)

无头链表二级指针方式实现

#include <stdio.h>
#include <stdlib.h>

//定义链表结构
typedef struct Node {
    int data;
    struct Node* next;
}NODE,*LPNODE;

//创建节点
LPNODE createNode(int data) {
    LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
    if (NULL == newNode) {
        printf("数据节点内存申请失败!\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

//头插
void insertByHead(LPNODE* headNode, int data) {
    LPNODE newNode = createNode(data);
    if (*headNode == NULL) {
        *headNode = newNode;
    }
    else {
        newNode->next = *headNode;
        *headNode = newNode;
    }
}

//尾插
void insertByTail(LPNODE* headNode, int data) {
    LPNODE newNode = createNode(data);
    if (*headNode == NULL) {
        *headNode = newNode;   //插入节点就是头节点
    }
    else {
        LPNODE curNode = *headNode;
        while (curNode->next != NULL) {
            curNode = curNode->next;
        }
        curNode->next = newNode;
    }
}

//指定位置插入
void insertAppoint(LPNODE* headNode, int data, int pos) {
    LPNODE newNode = createNode(data);
    LPNODE curNode = *headNode;
    if (*headNode == NULL) {
        *headNode = newNode;
    }
    else {
        while (curNode->next != NULL && --pos) {
            curNode = curNode->next;
        }
        newNode->next = curNode->next;
        curNode->next = newNode;
    }
}

//头删
void deleteByHead(LPNODE* headNode) {
    if (*headNode == NULL) {
        printf("链表为空,没有节点可以删除!\n");
        return;
    }
    else {
        LPNODE delNode = *headNode;
        *headNode = delNode->next;
        free(delNode);
        delNode = NULL;
    }
}

//尾删
void deleteByTail(LPNODE* headNode) {
    if (*headNode == NULL) {
        printf("链表为空,没有节点可以删除!\n");
        return;
    }
    else {
        LPNODE delNode = *headNode;
        LPNODE preNode = *headNode; //删除节点的前一个节点
        while (delNode->next != NULL) {
            preNode = delNode;
            delNode = delNode->next;
        }
        preNode->next = NULL;
        free(delNode);
        delNode = NULL;
    }
}

//指定数据删除
void deleteByAppointData(LPNODE* headNode, int posData) {
    if (*headNode == NULL) {
        printf("链表为空,没有节点可以删除!\n");
        return;
    }
    if ((*headNode)->next == NULL) {   //一个节点
        if ((*headNode)->data == posData)
            deleteByHead(headNode);
        else
            printf("未找到指定节点数据!\n");
    }
    else {
        LPNODE delNode = (*headNode)->next;
        LPNODE preNode = *headNode;
        while (delNode->next != NULL && delNode->data != posData) {
            preNode = delNode;
            delNode = delNode->next;
        }
        preNode->next = delNode->next;
        free(delNode);
        delNode = NULL;
    }
}

//查找
LPNODE searchNode(LPNODE headNode, int posData) {
    LPNODE curNode = headNode;
    while (curNode != NULL && curNode->data != posData) {
        curNode = curNode->next;
    }
    return curNode;
}

//删除全部指定数据
void deleteAllPosdata(LPNODE* headNode, int posData) {
    while (searchNode(*headNode, posData) != NULL) {
        deleteByAppointData(headNode, posData);
    }
}

//销毁链表
void destroyList(LPNODE* headNode) {
    while ((*headNode)->next != NULL) {
        deleteByHead(headNode);
    }
    free(*headNode);
    *headNode = NULL;
}

//打印链表
void printList(LPNODE headNode) {
    while (headNode != NULL) {
        printf("%d\t", headNode->data);
        headNode = headNode->next;
    }
    printf("\n");
}

int main()
{
    LPNODE list = NULL;

    //头插
    insertByHead(&list, 1002);
    insertByHead(&list, 1001);
    printList(list);

    //尾插
    for (int i = 0; i < 3; i++)
    {
        insertByTail(&list, 520 + i);
        insertByTail(&list, 520 + i);
    }
    printList(list);

    //指定位置插入
    insertAppoint(&list, 1314, 2);
    printList(list);

    //头删
    deleteByHead(&list);
    printList(list);

    //尾删
    deleteByTail(&list);
    printList(list);

    //指定数据删除
    deleteByAppointData(&list, 1314);
    printList(list);

    //删除所有指定数据
    deleteAllPosdata(&list, 521);
    printList(list);

    if (list != NULL)
        printf("链表未销毁!\n");

    //销毁链表
    destroyList(&list);

    if (list == NULL)
        printf("链表已销毁!\n");

    system("pause");
    return 0;
}