【C语言】双链表（可记录遍历点，根据记录继续遍历）

短命女 2022-06-10 03:06 113阅读 0赞

text1-1.h
    /* * 链表演示 * */
    #ifndef __TEXT1_1_H__
    #define __TEXT1_1_H__
    typedef struct node {
        int num;
        struct node *p_next;
        struct node *p_pre;
    } node;
    
    typedef struct {
        node head;
        node tail;
        node *p_cur; //记录遍历过程中上一个被处理的节点
    } link;
    ?
    //链表的初始化函数
    void link_init(link *);
    //清理函数
    void link_deinit(link *); 
    //计算有效数字个数
    int link_size(const link *); 
    //判断链表是否为空
    int link_empty(const link *);
    //判断是否为满
    int link_full(const link *);
    //在链表前面加入新节点
    void link_add_head(link *, int);
    //在原有节点最后加入新节点
    void link_append(link *, int);
    //按顺序插入
    void link_insert(link *, int);
    //删除最前面的有效数字
    int link_remove_head(link *);
    //删除最后一个有效节点
    int link_remove_tail(link *);
    //删除某个数字所在节点
    int link_remove(link *, int);
    //获得链表最前面的数字
    int link_get_head(const link *, int *);
    //获得最后面的有效数字
    int link_get_tail(const link *, int *);
    //根据编号获得数字
    int link_get(const link *, int, int *);
    //将遍历位置指针设置为开始从前往后遍历状态
    void link_begin(link *);
    //遍历过程中处理下一个节点
    int link_next(link *,int *);
    //将遍历位置记录与尾捆绑，从后向前遍历
    void link_rbegin(link *);
    //在从后向前的遍历过程中处理下一个节点
    int link_pre(link *, int *);
    #endif //__TEXT1_1_H
    
    
    --------------------------------------------------------------------------------
    text1.c
    /* * 链表演示 * 双向 ，记录遍历位置 * 记录遍历的位置需要再增加一个独立的节点link，这个节点用来记录当前遍历的位置和值， * 要注意在增加和删除节点的时候是需要将记录点赋值为空的，否则容易删除该节点，产生野指针 * */
    #include <stdlib.h>
    #include "text1-1.h"
    
    //链表的初始化函数
    void link_init(link *p_link) {
        p_link->head.p_next = &(p_link->tail);
        p_link->tail.p_next = NULL;
        //下面是另一个方向的，从尾指向头
        p_link->tail.p_pre = &(p_link->head);
        p_link->head.p_pre = NULL;
    
        p_link->p_cur = NULL;//该点为空代表此时没有开始遍历
    }
    
    //链表的清理函数
    void link_deinit(link *p_link) {
        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;//清理正向
    
            p_last->p_pre = p_first;//清理反向，就的指针的方向反了一下
    
            free(p_mid);
            p_mid = NULL;
        }
        p_link->p_cur = NULL;// 清空记录点
    }
    
    //计算有效数字个数的函数，正反一样，要修改可以让p_first,p_mid,p_last,从后面开始来
    int link_size(const link *p_link) {
        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) {
        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_tmp->p_pre = NULL;//反向指针
    
        p_first = &(p_link->head);
        p_mid = p_first->p_next;
        p_last = p_mid->p_next;
    
        p_first->p_next = p_tmp;
        p_tmp->p_pre = p_first;//反向
        p_tmp->p_next = p_mid;
        p_mid->p_pre = p_tmp;//反向
    
        p_link->p_cur = NULL;
    }
    
    //在原有节点最后加入新节点的函数
    void link_append(link *p_link, int val) {
        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_tmp->p_pre = NULL;//反向
    
        p_first = p_link->tail.p_pre;//反向添加最后一个节点就是这里不同，原来是first指向头，现在是指向尾，相当于反着来了
        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_pre = p_first;//反
        p_tmp->p_next = p_mid;//正
        p_mid->p_pre = p_tmp;//反
    
        p_link->p_cur = NULL;
    }
    /*void link_append(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; p_tmp->p_pre = 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_pre = p_first; p_tmp->p_next = p_mid; p_mid->p_pre = p_tmp; 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;
    
        p_tmp->p_pre = 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_pre = p_first;//反向
                p_tmp->p_next = p_mid;
                p_mid->p_pre = p_tmp;//反向
    
                break;
            }
        }
    
        p_link->p_cur = NULL;
    }
    
    //删除最前面有效数字的函数
    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_first->p_next = p_last;//正
    
        p_last->p_pre = p_first;//反
    
        free(p_mid);
        p_mid = NULL;
    
        p_link->p_cur = NULL;//记录当前遍历位置
        return 1;
    }
    
    //删除最后一个有效节点的函数
    int link_remove_tail(link *p_link) {
        node *p_first = NULL, *p_mid = NULL, *p_last = NULL;
        if (link_empty(p_link)) {
            return 0;
        }
    
        p_first = p_link->tail.p_pre->p_pre;//尾节点->最后一个有效节点->倒数第二个有效节点
        p_mid = p_first->p_next;//最后一个有效节点
        p_last = p_mid->p_next;
        //把p_mid指针捆绑的节点从链表里
        //摘出来
    
        p_first->p_next = p_last;
    
        p_last->p_pre = p_first;
    
        free(p_mid);
        p_mid = NULL;
    
        p_link->p_cur = 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; if (p_last == &(p_link->tail)) { p_first->p_next = p_last; p_last->p_pre = p_first; free(p_mid); p_mid = NULL; break; } } return 1; }*/
    
    //删除某个数字所在节点的函数
    int link_remove(link *p_link, int val) {
        node *p_node = NULL;
    
        p_link->p_cur = 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;//正
    
                p_last->p_pre = p_first;//反
    
                free(p_mid);
                p_mid = NULL;
                return 1;
            }
        }
        return 0;
    }
    
    //获得链表最前面数字的函数
    int link_get_head(const link *p_link, int *p_num) {
        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) {
        if (link_empty(p_link)) {
            return 0;
        }
        *p_num = p_link->tail.p_pre->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;
    }
    
    //将遍历位置指针设置为开始从前往后遍历状态
    void link_begin(link *p_link) {
        p_link->p_cur = &(p_link->head);//将记录指针与头捆绑，下一个要处理的就是第一个有效节点
    }
    
    //遍历过程中处理下一个节点
    int link_next(link *p_link, int *p_num) {
       //因为不确定是否可以成功的获得，所以需要有返回来确定状态
        if(!(p_link->p_cur)) {
       //如果不处于遍历状态，也就是记录指针为0时
            return 0;
        }
        p_link->p_cur = p_link->p_cur->p_next;//找到这次要处理的节点并记录到p_cur指针里面
        if(p_link->p_cur == &(p_link->tail)) {
            p_link->p_cur = NULL;
            return 0;
        }
        else {
            *p_num = p_link->p_cur->num;
            return 1;
        }
    }
    
    //将遍历位置记录与尾捆绑，从后向前遍历
    void link_rbegin(link *p_link) {
        p_link->p_cur = &(p_link->tail);
    }
    
    //在从后向前的遍历过程中处理下一个节点
    int link_pre(link *p_link, int *p_num) {
        if(!(p_link->p_cur)) {
            return 0;
        }
    
        p_link->p_cur = p_link->p_cur->p_pre;
    
        if(p_link->p_cur == &(p_link->head)) {
            p_link->p_cur = NULL;
            return 0;
        }
        else {
            *p_num = p_link->p_cur->num;
            return 1;
        }
    }
    
    --------------------------------------------------------------------------------
    text2.c:
    /* * 链表测试 * */
    #include <stdio.h>
    #include "text1-1.h"
    int main() {
        int size = 0;
        int num = 0, val = 0;
        link lnk = {
       0};
    
        link_init(&lnk);
        link_deinit(&lnk);
    
        link_add_head(&lnk, 30);
        link_add_head(&lnk, 10);
    
        link_append(&lnk, 80);
        link_append(&lnk, 100);
    
    
        link_insert(&lnk, 20);
        link_insert(&lnk, 90);
        link_insert(&lnk, 50);
        link_insert(&lnk, 60);
        link_insert(&lnk, 40);
        link_insert(&lnk, 70);
    
        link_remove_head(&lnk);
        link_remove_tail(&lnk);
    
        link_remove(&lnk, 70);
    
        size = link_size(&lnk);
        printf("数字个数是：%d\n", size);
    /* for(num = 0; num < size -1; num++){ link_get(&lnk, num, &val); printf("%d ", val); }*/
    
        link_begin(&lnk);
        while(1) {
            if(!link_next(&lnk, &val)){
       //如果返回值是零就停止
                break;
            }
            printf("%d ", val);
        }
        printf("\n");
        link_rbegin(&lnk);
        while(1) {
            if(!link_pre(&lnk, &val)) {
                break;
            }
            printf("%d ", val);
        }
        printf("\n");
        link_deinit(&lnk);
        return 0;
    }