数据结构-双向链表-003

2024-03-25 19:14:02
开发
15

1双向链表

1.1链表结点结构体定义

typedef struct student_data
{
    char name[32];
    char sex;
    int age;
}STU_DATA;

typedef struct double_link_node
{
    STU_DATA data;//数据域
    struct double_link_node *ppre;//指向上一个结点的指针
    struct double_link_node *pnext;//指向下一个结点的指针
}DOUB_NODE;

1.2链表头结点结构体定义

typedef struct double_link_head
{
    DOUB_NODE *phead;//指向首结点的指针
    int clen;//记录链表节点数量
}DOUB_HEAD;

1.3双向链表头结点创建

/*=============双向链表创建头结点(创建空表)=========*/
void *create_double_link_list_head_node(void)
{
    DOUB_HEAD *phead=NULL;

    /*创建头结点空间*/
    phead=malloc(sizeof(DOUB_HEAD));
    if(NULL==phead)
    {
        perror("fail to malloc");
        return NULL;
    }

    /*头结点初始化*/
    phead->phead=NULL;
    phead->clen=0;

    return phead;
}

1.4双向链表结点创建

/*=============双向链表创建新结点==============*/
void* create_double_link_list_new_node(STU_DATA data)
{
    DOUB_NODE *pnode=NULL;

    /*创建新结点空间*/
    pnode=malloc(sizeof(DOUB_NODE));
    if(NULL==pnode)
    {
        perror("fail to malloc");
        return NULL;
    }

    /*新结点初始化*/
    pnode->data = data;
    pnode->ppre=NULL;
    pnode->pnext=NULL;

    return pnode;
}

1.5链表非空判断

/*=============双向链表非空判断==============*/
int is_empty_link(DOUB_HEAD *list)
{
    return NULL==list->phead;
}

1.6双向链表结点插入

1.6.1头插法

/*=============双向链表头插法=================*/
int push_head_double_link_list(DOUB_HEAD *list, DOUB_NODE *pnode)
{
    if(NULL==list||NULL==pnode)
    {
        return -1;
    }

    if(is_empty_link(list))
    {
        list->phead=pnode;
    }
    else
    {
        pnode->pnext=list->phead;//初始化新结点的后继为旧的首结点
        list->phead->ppre=pnode;//更新首结点的前驱结点为新结点
        list->phead=pnode;//更新头结点的指向为新结点(因为此时新结点为新的首结点)
    }
    list->clen++;

    return 0;
}

1.6.2尾插法

/*=============双向链表尾插法=================*/
int push_tail_double_link_list(DOUB_HEAD *list,DOUB_NODE *pnode)
{
    DOUB_NODE *ptmp=NULL;

    if(NULL==list||NULL==pnode)
    {
        return -1;
    }


    if(is_empty_link(list))
    {
        list->phead=pnode;
    }

    else
    {
        /*定义一个遍历指针,初始化为指向首结点*/
        ptmp=list->phead;
        while(1)
        {
            if(NULL==ptmp->pnext)
            {
                break;
            }

            ptmp=ptmp->pnext;
        }
        pnode->pnext=ptmp->pnext;//初始化新结点的后继结点为NULL(原来尾结点的指针域)
        ptmp->pnext=pnode;//更新尾结点的后继结点为新结点
        pnode->ppre=ptmp;//初始化新结点的前继结点为尾结点
    }

    list->clen++;

    return 0;
}

1.7双向链表遍历

1.7.1低配版本遍历

/*=============双向链表遍历(原始版)===============*/
int double_list_for_each(DOUB_HEAD *list)
{
    DOUB_NODE *ptmp=NULL;

    /*判断空表*/
    if(is_empty_link(list))
    {
        return 0;
    }

    /*初始化遍历指针为指向首结点*/
    ptmp=list->phead;
    while(1)
    {
        if(NULL==ptmp)//如果是空表，也满足，如果遍历到链表末尾，也满足条件
        {
            break;
        }

        else
        {
            printf("%-10s\t%-10c\t%-10d\n",ptmp->data.name,ptmp->data.sex,ptmp->data.age);
            ptmp=ptmp->pnext;
        }

    }

    return 0;
}

1.7.2指定遍历方法的遍历

/*=============双向链表遍历(改进版)===============*/
int double_list_for_each(DOUB_HEAD *list,int dir,void (*pfun)(DOUB_NODE *))
{
    DOUB_NODE *ptmp=NULL;

    /*判断空表*/
    if(is_empty_link(list))
    {
        return 0;
    }

    /*初始化遍历指针为指向首结点*/
    ptmp=list->phead;
    if(dir)
    {
        while(1)
        {
            if(NULL==ptmp)//如果是空表，也满足，如果遍历到链表末尾，也满足条件
            {
                break;
            }

                pfun(ptmp);
                ptmp=ptmp->pnext;
        }
    }
    else
    {
        /*获取尾结点*/
        while(1)
        {
            if(NULL==ptmp->pnext)
            {
                break;
            }

            ptmp=ptmp->pnext;
        }

        /*以尾结点为遍历起点,通过前继指针进行后序遍历*/
        while(1)
        {
            if(NULL==ptmp)
            {
                break;
            }

            pfun(ptmp);
            ptmp=ptmp->ppre;
        }
    }

    return 0;
}


/*==========遍历方式==========*/
void show_data(DOUB_NODE *pnode)
{
    printf("%-10s\t%-10c\t%-10d\n",pnode->data.name,pnode->data.sex,pnode->data.age);
}

1.8双向链表结点删除

1.8.1头删法

/*==========双向链表头删法==========*/
int pop_head_double_link_list(DOUB_HEAD *list)
{
    DOUB_NODE *ptmp=NULL;

    if(is_empty_link(list))
    {
        return 0;
    }

    ptmp=list->phead;//初始化结点类型的中间指针变量为指向首结点

    list->phead=ptmp->pnext;//更新头结点的指向为首结点的后继结点
    ptmp->pnext->ppre=ptmp->ppre;//新的首结点的前继指针继承旧的首结点的前继指针
    
    free(ptmp);
    list->clen--;

    return 0;
}

1.8.2尾删法

/*==========双向链表尾删法==========*/
int pop_tail_double_link_list(DOUB_HEAD *list)
{
    DOUB_NODE *ptmp=NULL;

    if(is_empty_link(list))
    {
        return 0;
    }

    ptmp=list->phead;
    while(1)
    {
        if(NULL==ptmp->pnext)
        {
            break;
        }

        ptmp=ptmp->pnext;
    }

    if(ptmp->ppre!=NULL)
    {
        ptmp->ppre->pnext=NULL;
    }
    else
    {
        list->phead=NULL;
    }
    free(ptmp);

    list->clen--;

    return 0;
}

1.9双向链表查找

/*==========查找结点==========*/
DOUB_NODE *search_double_link_list_node(DOUB_HEAD *list,int (*pfun)(DOUB_NODE *,void *),void *t)
{
    DOUB_NODE *ptmp=NULL;

    if(NULL==list||NULL==pfun||NULL==t)
    {
        return NULL;
    }

    ptmp=list->phead;
    while(1)
    {
        if(ptmp==NULL)
        {
            break;
        }

        if(pfun(ptmp,t))
        {
            return ptmp;
        }
        ptmp=ptmp->pnext;
    }

    return NULL;
}

/*==========查找方式==========*/
int search_by_name(DOUB_NODE *pnode,void *t)
{
    if(strcmp((char *)t,pnode->data.name)==0)
    {
        return 1;
    }

    return 0;
}

int search_by_sex(DOUB_NODE *pnode,void *t)
{
    if(*((char *)t)==pnode->data.sex)
    {
        return 1;
    }

    return 0;
}

int search_by_age(DOUB_NODE *pnode,void *t)
{
    if(*((int *)t)==pnode->data.age)
    {
        return 1;
    }

    return 0;
}

1.10双向链表修改

通过调用双向链表的查找函数接口进行修改

1.11双向链表销毁

/*==========双向链表销毁==========*/
void destroy_double_link_list(DOUB_HEAD *list)
{
    while(1)
    {
        if(is_empty_link(list))
        {
            break;
        }
        else
        {
            pop_head_double_link_list(list);
//            pop_tail_double_link_list(list);
        }

        free(list);
    }
}

1.12双向链表的其它操作

1.12.1双向链表逆序

/*==========双向链表逆序==========*/
void reverse_double_link_list(DOUB_HEAD *list)
{
    DOUB_NODE *ptmp=NULL;
    DOUB_NODE *pinsert=NULL;

    if(is_empty_link(list))
    {
        return ;
    }

    ptmp=list->phead;//初始化遍历指针为指向首结点
    list->phead=NULL;
    list->clen=0;//头结点与首结点断开，此时clen置0
    while(1)
    {
        if(NULL==ptmp)
        {
            break;
        }

        pinsert=ptmp;//获取当前结点为待插入结点
        ptmp=ptmp->pnext;

        pinsert->pnext=NULL;
        pinsert->ppre=NULL;
        push_head_double_link_list(list,pinsert);//用头插法将待插入结点插入
    }
}

1.12.2双向链表查找中间结点

1.12.3双向链表查找倒数第k个结点

1.12.4双向链表删除指定结点

1.12.4.1单结点删除

/*==========双向链表删除指定结点==========*/
int pop_appointed_node(DOUB_HEAD *list,int (*pfun)(DOUB_NODE *,void *),void *t)
{
    DOUB_NODE *pnode=NULL;

    if(NULL==list||NULL==pfun||NULL==t)
    {
        return -1;
    }

    pnode=search_double_link_list_node(list,pfun,t);
    if(NULL==pnode)
    {
        return -1;
    }

    if(NULL==pnode->ppre)
    {
        pop_head_double_link_list(list);
    }
    else if(NULL==pnode->pnext)
    {
        pop_tail_double_link_list(list);
    }
    else
    {
        pnode->ppre->pnext=pnode->pnext;
        pnode->pnext->ppre=pnode->ppre;
        free(pnode);
        list->clen--;
    }

    return 0;
}

1.12.4.2多结点删除

用于多个结点值相同的情况

原文地址:https://blog.csdn.net/qq_63713157/article/details/136869526 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1772220391805292544.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部