【C语言】单链表常用函数

朴灿烈づ我的快乐病毒、 2022-06-10 01:50 286阅读 0赞

/* * 链表演示 * 单向 * */
    #include <stdlib.h>
    #include "03link.h"
    
    //链表的初始化函数
    void link_init(link *p_link) {
        p_link->head.p_next = &(p_link->tail);//单向链表的初始化也就是让头指针指向尾，尾节点指向空
        p_link->tail.p_next = NULL;
    }
    
    //链表的清理函数
    void link_deinit(link *p_link) { //因为链表的增加需要分配动态内存，所以链表的清空不仅需要断开有效数据，还需要将所分配的内存释放，释放需要用循环一个一个释放，释放过程为：先将头指针指向下一个节点（p_first直接指向p_last,此时的p_mid指向的就是要删除的），然后用free（）释放
        while (p_link->head.p_next != &(p_link->tail)) {
            node *p_first = &(p_link->head);
            node *p_mid = p_first->p_next;
            node *p_last = p_mid->p_next;
            p_first->p_next = p_last;
            free(p_mid);
            p_mid = NULL;
        }
    }
    
    //计算有效数字个数的函数
    int link_size(const link *p_link) { //统计有效个数统计p_mid除了指向尾节点的就可以
        int cnt = 0;
        const node *p_node = NULL;
        for (p_node = &(p_link->head);p_node != &(p_link->tail);p_node = p_node->p_next) {
            const node *p_first = p_node;
            const node *p_mid = p_first->p_next;
            const node *p_last = p_mid->p_next;
            if (p_mid != &(p_link->tail)) {
                cnt++;
            }
        }
        return cnt;
    }
    
    //判断链表是否空的函数
    int link_empty(const link *p_link) {
       //空的时候头和尾在一起
        return p_link->head.p_next == &(p_link->tail);
    }
    //判断链表是否满的函数
    int link_full(const link *p_link) {
       //链表不会满
        return 0;
    }
    //在链表前边加入新节点的函数
    void link_add_head(link *p_link, int val) { //起始的时候p_mid就是指向第一个有效节点的，将新店插入到p_first和p_mid间就可以
        node *p_first = NULL, *p_mid = NULL, *p_last = NULL;
        node *p_tmp = (node *)malloc(sizeof(node));//加入新点要增加内存
        if (!p_tmp) {
            return ;
        }
        //分配成功之后将要增加的新点赋值给新的内存中，指针先设置为空
        p_tmp->num = val;
        p_tmp->p_next = NULL;
        //辅助变量链接
        p_first = &(p_link->head);
        p_mid = p_first->p_next;
        p_last = p_mid->p_next;
        //p_first指向新点，新点指向p_mid
        p_first->p_next = p_tmp;
        p_tmp->p_next = p_mid;
    }
    
    //在原有节点最后加入新节点的函数
    void link_append(link *p_link, int val) {
       //在最后面添加，p_mid指向尾节点
        node *p_tmp = (node *)malloc(sizeof(node));
        node *p_node = NULL;//要指向尾需要循环
        if (!p_tmp) {
            return ;
        }
    
        p_tmp->num = val;
        p_tmp->p_next = NULL;
    
        for (p_node = &(p_link->head);p_node != &(p_link->tail);p_node = p_node->p_next) {
            node *p_first = p_node;
            node *p_mid = p_first->p_next;
            node *p_last = p_mid->p_next;
    
            if (p_mid == &(p_link->tail)) {
                p_first->p_next = p_tmp;
                p_tmp->p_next = p_mid;
                break;
            }
        }
    }
    
    //按顺序插入函数
    void link_insert(link *p_link, int val) {
        node *p_tmp = (node *)malloc(sizeof(node));
        node *p_node = NULL;
        if (!p_tmp) {
            return ;
        }
        p_tmp->num = val;
        p_tmp->p_next = NULL;
    
        for (p_node = &(p_link->head);p_node != &(p_link->tail);p_node = p_node->p_next) {
    
            node *p_first = p_node;
            node *p_mid = p_first->p_next;
            node *p_last = p_mid->p_next;
    
            if (p_mid == &(p_link->tail) || p_mid->num > val) {
       //按顺序插入是从小到大的排列，在找到第一个比新点大的就插在前面，注意特殊情况
                p_first->p_next = p_tmp;
                p_tmp->p_next = p_mid;
                break;
            }
        }
    }
    
    //删除最前面有效数字的函数
    int link_remove_head(link *p_link) {
        node *p_first = NULL, *p_mid = NULL, *p_last = NULL;
        if (link_empty(p_link)) {
            return 0;
        }
    
        p_first = &(p_link->head);
        p_mid = p_first->p_next;
        p_last = p_mid->p_next;
        //删除最前面就是在初始时p_mid指向第一位，让p_first跳过p_mid就可以，然后释放节点
        p_first->p_next = p_last;
    
        free(p_mid);
        p_mid = NULL;
        return 1;
    }
    
    //删除最后一个有效节点的函数
    int link_remove_tail(link *p_link) {
        node *p_node = NULL;
        if (link_empty(p_link)) {
            return 0;
        }
        for (p_node = &(p_link->head);p_node != &(p_link->tail);p_node = p_node->p_next) {
    
            node *p_first = p_node;
            node *p_mid = p_first->p_next;
            node *p_last = p_mid->p_next;
            //删除最后节点就是让p_mid指向最后一个，也就是p_last指向尾
            if (p_last == &(p_link->tail)) {
    
                p_first->p_next = p_last;
    
                free(p_mid);
                p_mid = NULL;
                break;
            }
        }
        return 1;
    }
    
    //删除某个数字所在节点的函数
    int link_remove(link *p_link, int val) {
        node *p_node = NULL;
        for (p_node = &(p_link->head);p_node != &(p_link->tail);p_node = p_node->p_next) {
    
            node *p_first = p_node;
            node *p_mid = p_first->p_next;
            node *p_last = p_mid->p_next;
    
            if (p_mid != &(p_link->tail) && p_mid->num == val) {
       //判断是否是要删除的，注意尾，如果尾里面的随机值正好是要删的就错了
    
                p_first->p_next = p_last;
    
                free(p_mid);
                p_mid = NULL;
                return 1;
            }
        }
        return 0;
    }
    
    //获得链表最前面数字的函数
    int link_get_head(const link *p_link, int *p_num) {
       //获得一个数就是将p_mid指向的数赋值给变量
        const node *p_first = NULL, *p_mid = NULL, *p_last = NULL;
        if (link_empty(p_link)) {
            return 0;
        }
    
        p_first = &(p_link->head);
        p_mid = p_first->p_next;
        p_last = p_mid->p_next;
    
        *p_num = p_mid->num;
        return 1;
    }
    
    //获得最后有效数字的函数
    int link_get_tail(const link *p_link, int *p_num) {
        const node *p_node = NULL;
        if (link_empty(p_link)) {
            return 0;
        }
        for (p_node = &(p_link->head);p_node != &(p_link->tail);p_node = p_node->p_next) {
    
            const node *p_first = p_node;
            const node *p_mid = p_first->p_next;
            const node *p_last = p_mid->p_next;
    
            if (p_last == &(p_link->tail)) {
    
                *p_num = p_mid->num;
                break;
            }
        }
        return 1;
    }
    
    //根据编号获得数字的函数
    int link_get(const link *p_link, int num, int *p_num) {
       //删除某位置的一个数需要用一个数来计数，用于判断当前位置
        int cnt = 0;
        const node *p_node = NULL;
        for (p_node = &(p_link->head);p_node != &(p_link->tail);p_node = p_node->p_next) {
    
            const node *p_first = p_node;
            const node *p_mid = p_first->p_next;
            const node *p_last = p_mid->p_next;
    
            if (p_mid != &(p_link->tail) && num == cnt) {
    
                *p_num = p_mid->num;
                return 1;
            }
            cnt++;
        }
        return 0;
    }