ROOT
ROOT

链式队列的定义与操作

不解释,看代码,注释

/*************************************************************************
    > File Name: queue.c
    > Author: Netcan
    > Mail: 1469709759@qq.com
    > Created Time: 2014/12/21 20:10:02
 ************************************************************************/

#include<stdio.h>
#include<malloc.h>

struct Node { // 定义节点 
    int data;
    Node * pNext;
};
struct Queue { // 定义队列,这里的 pHead 是头指针,不是首指针,指向无效节点 
    Node * pHead;
    Node * pTail;
};

void init_Queue(Queue *Q); // 初始化队列 
bool in_Queue(Queue *Q,int val); // 入队 
bool out_Queue(Queue *Q); // 出队 
bool is_empty_Queue(Queue *Q); // 判断队列是否为空 
int length_Queue(Queue *Q); // 队列长度 
void traverse_Queue(Queue *Q); // 遍历队列 = = 检测队列用的 
void clear_Queue(Queue *Q); // 清空队列 


int main() {
    Queue Q; // 声明队列 
    init_Queue(&Q); // 初始化 
    in_Queue(&Q,0); // 入队 
    in_Queue(&Q,1);
    in_Queue(&Q,2);
    in_Queue(&Q,3);
    in_Queue(&Q,4);
    in_Queue(&Q,5);
    in_Queue(&Q,6);
    in_Queue(&Q,7);
    in_Queue(&Q,8);
    in_Queue(&Q,9);
    traverse_Queue(&Q); // 遍历队列 
    printf("Queue length: %d\n", length_Queue(&Q)); // 输出当前队列长度 
    out_Queue(&Q); // 出队 
    out_Queue(&Q);
    traverse_Queue(&Q);
    printf("Queue length: %d\n", length_Queue(&Q));

    puts("Clear Queue");
    clear_Queue(&Q); // 清空队列 
    printf("Queue length: %d\n", length_Queue(&Q));
    traverse_Queue(&Q);

    return 0;
}

void init_Queue(Queue *Q)
{
    Q->pTail = (Node *)malloc(sizeof(Node)); // 使尾指针指向新节点 
    Q->pTail->pNext = NULL; // 尾指针指向下一个空节点 
    Q->pHead = Q->pTail; // 当前头指针指向尾指针 
    return;
}

bool is_empty_Queue(Queue *Q)
{
    if(Q->pHead == Q->pTail) // 只要头指针指向尾指针就为空 
        return true;
    else
        return false;
}

int length_Queue(Queue *Q)
{
    if( is_empty_Queue(Q) )
        return 0;
    int len;
    Node * p = Q->pHead->pNext;  // p 指向第一个有效节点 
    for(len = 1; p != Q->pTail; len++, p = p->pNext); // 计数,当队列不为空长度当然大于等于 1
    return len;
}

bool in_Queue(Queue *Q,int val)
{
    Node * pNew = (Node *)malloc(sizeof(Node)); // 分配新节点 
    if( NULL == pNew )
        return false;
    pNew->data = val; // 新节点的值为入队的值 
    pNew->pNext = NULL; // 新节点从尾部插入则指向下一个空节点 
    Q->pTail->pNext = pNew; // 当前尾指针后一个节点指向新节点 
    Q->pTail = pNew; // 更新尾指针 
    return true;
}

bool out_Queue(Queue *Q)
{
    if(is_empty_Queue(Q))
        return false;
    Node * p = Q->pHead; // 使 p 指向头指针 
    Q->pHead = p->pNext;  // 更新头指针,头指针下移 
    free(p); // 释放 p
    return true;
}

void traverse_Queue(Queue *Q)
{
    if(is_empty_Queue(Q))
        return;
    Node *p = Q->pHead->pNext; // 使 p 指向第一个有效节点 
    while( p != Q->pTail->pNext ) { // 如果 p 没到队列最后一个节点就输出 
        printf("%3d",p->data);
        p = p->pNext;
    }
    puts("");
    return;
}

void clear_Queue(Queue *Q)
{
    if(is_empty_Queue(Q))
        return;
    Node *p = Q->pHead->pNext; // 使 p 指向第一个有效节点 
    Node *q = p->pNext; // q 指向 p 指向的下一个节点 
    while( q != Q->pTail->pNext ) { // 遍历节点,并清空 
        free(p);
        p=q;
        q = p->pNext;
    }
    free(p); // 尾节点清空 
    Q->pTail = Q->pHead; // 重置尾指针 
}
支持一下
扫一扫,支持Netcan
  • 微信扫一扫
  • 支付宝扫一扫