数据结构-队列-005

1链式队列

运行结果如下：

1.1链式队列结点定义

/*自定义一个数据类型*/
typedef struct student
{
    char name[32];
    char sex;
    int age;
}DATA_TYPE;

/*定义一个链式队列结点*/
typedef struct link_queue_node
{
    DATA_TYPE data;//数据域
    struct link_queue_node *pnext;//指针域
}LINK_QUEUE_NODE;

1.2链式队列队头结点定义

/*定义一个链式队列头*/
typedef struct link_queue_head
{
    LINK_QUEUE_NODE *pfront;
    LINK_QUEUE_NODE *prear;
    int clen;
}LINK_QUEUE_HEAD;

1.3创建链式队列的队头

/*==========创建一个链队队头==========*/
LINK_QUEUE_HEAD *create_link_queue_head(void)
{
    LINK_QUEUE_HEAD *phead=NULL;

    /*创建一个链式队列的队头空间*/
    phead=malloc(sizeof(LINK_QUEUE_HEAD));
    if(NULL==phead)
    {
        perror("fail to malloc");
        return NULL;
    }

    /*初始化链式队列的队头*/
    phead->pfront=NULL;
    phead->prear=NULL;
    phead->clen=0;

    return phead;
}

1.4创建链式队列结点

/*==========创建一个链队结点==========*/
LINK_QUEUE_NODE *create_link_queue_node(DATA_TYPE data)
{
    LINK_QUEUE_NODE *pnode=NULL;

    /*创建一个链队结点空间*/
    pnode=malloc(sizeof(LINK_QUEUE_NODE));
    if(NULL==pnode)
    {
        perror("fail to malloc");
        return NULL;
    }

    /*初始化链队结点*/
    pnode->data=data;
    pnode->pnext=NULL;

    return pnode;
}

1.5判断非空链式队列

/*==========判断非空链队==========*/
int is_empty_link_queue(LINK_QUEUE_HEAD *link_queue)
{
    return NULL==link_queue->pfront;
}

1.6入队

/*==========链式队列入队-尾插法==========*/
int push_link_queue(LINK_QUEUE_HEAD *link_queue,LINK_QUEUE_NODE *pnode)
{
    if(is_empty_link_queue(link_queue))
    {
        link_queue->prear=pnode;//更新链式队头尾指针
        link_queue->pfront=pnode;//更新链式队头头指针
    }
    else
    {
        link_queue->prear->pnext=pnode;//更新尾结点指针为指向新结点
        link_queue->prear=pnode;//更新链式队头尾指针
    }
    link_queue->clen++;

    return 0;
}

1.7出队

/*==========链式队列出队-头删法*/
int pop_link_queue(LINK_QUEUE_HEAD *link_queue,DATA_TYPE *data)
{
    LINK_QUEUE_NODE *pnode=NULL;

    if(is_empty_link_queue(link_queue))
    {
        return -1;
    }

    pnode=link_queue->pfront;//备份待出队的队首结点
    link_queue->pfront=pnode->pnext;//更新链式队列指向队首的指针
    if(NULL==link_queue->pfront)
    {
        link_queue->prear=NULL;
    }
    if(data!=NULL)
    {
        *data=pnode->data;
    }
    free(pnode);
    link_queue->clen--;

    return 0;
}

1.8遍历链式队列

/*==========链式队列的遍历==========*/
void link_queue_for_each(LINK_QUEUE_HEAD *link_queue,void (*pfun)(LINK_QUEUE_NODE *))
{
    LINK_QUEUE_NODE *ptmp=NULL;

    ptmp=link_queue->pfront;//初始化链式队列结点类型的中间指针变量为队首
    while(1)
    {
        if(NULL==ptmp)
        {
            break;
        }

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

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

1.9清空链式队列

/*==========清空链式队列==========*/
void clear_link_queue(LINK_QUEUE_HEAD *link_queue)
{
    while(1)
    {
        if(is_empty_link_queue(link_queue))
        {
            break;
        }

        pop_link_queue(link_queue,NULL);
    }
}

1.10销毁链式队列

/*==========销毁链式队列==========*/
void destroy_queue(LINK_QUEUE_HEAD *link_queue)
{
    clear_link_queue(link_queue);
    free(link_queue);
}