数据结构-单链队列相关操作算法

时间:2022-05-06 19:06:22

程序代码如下:

#include <stdio.h>
#include <stdlib.h>

#define OVERFLOW -2
#define OK 1
#define ERROR 0

typedef int QElemType;
typedef struct QNode {
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct {
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

int InitQueue(LinkQueue *Q);//初始化队列
int DestoryQueue(LinkQueue *Q);//销毁队列
int EmptyQueue(LinkQueue *Q);//判断队列是否为空
int EnQueue(LinkQueue *Q,QElemType e);//插入元素e为Q的新的队尾元素
int DeQueue(LinkQueue *Q,QElemType *e);//删除非空队列的队头元素,并用e返回删除元素的值
int ClearQueue(LinkQueue *Q);//清空队列
int QueueLength(LinkQueue *Q);//取得队列的长度
int GetHead(LinkQueue *Q,QElemType *e);//取得队头元素
void visit(QElemType e);//自定义visit函数,表示输出元素的值
void QueueTraverse(LinkQueue *Q,void *visit(QElemType));//从队头到队尾依次对队列Q中每个元素调用visit函数

//初始化队列
int InitQueue(LinkQueue *Q) {
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q->front) exit(OVERFLOW);
    Q->front->next = NULL;
    Q->rear->next = NULL;
    return OK;
}

//销毁队列
int DestoryQueue(LinkQueue *Q) {
    while(Q->front) {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
    return OK;
}

//判断队列是否为空,为空返回1,不为空返回0
int EmptyQueue(LinkQueue *Q) {
    if(Q->front == Q->rear) {
        return OK;
    } else {
        return ERROR;
    }
}

//插入元素e为Q的新的队尾元素
int EnQueue(LinkQueue *Q,QElemType e) {
    QueuePtr p;
    p = (QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(OVERFLOW);
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
    return OK;
}

//删除非空队列的队头元素,并用e返回删除元素的值
int DeQueue(LinkQueue *Q,QElemType *e) {
    QueuePtr p;
    if(Q->front == Q->rear) return ERROR;
    p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if(Q->rear == p) {
        Q->rear = Q->front;
        Q->front->next = NULL;
    }
    free(p);
    return OK;
}

//清空队列
int ClearQueue(LinkQueue *Q) {
    QueuePtr p,q;
    if(!EmptyQueue(Q)) {
        p = Q->front->next;
        while(p!=Q->rear) {
            q = p;
            Q->front->next = p->next;
            p = p->next;
            free(q);
        }
        Q->rear = Q->front;
        free(p);
        Q->front->next = NULL;
        Q->rear->next = NULL;
        return OK;
    } else {
        return ERROR;
    }

}

//取得队列的长度
int QueueLength(LinkQueue *Q) {
    QueuePtr p;
    int i=0;
    p = Q->front;
    while(p!=Q->rear) {
        ++i;
        p = p->next;
    }
    return i;
}

//取得队头元素
int GetHead(LinkQueue *Q,QElemType *e) {
    if(!EmptyQueue(Q)) {
        *e = Q->front->next->data;
        return OK;
    } else {
        return ERROR;
    }
}

//自定义visit函数,表示输出元素的值
void visit(QElemType e) {
     printf("%d ",e);
 }

//从队头到队尾依次对队列Q中每个元素调用visit函数
void QueueTraverse(LinkQueue *Q,void *visit(QElemType)) {
    QueuePtr p;
    p = Q->front->next;
    printf("队列中的元素为:");
    while(p) {
        visit(p->data);
        p= p->next;
    }
    printf("\n");
}

int main()
{
    LinkQueue link;
    int f1,f2,f3,f4,f5,f6,e,i,a,len,n;
    //队列初始化
    f1 = InitQueue(&link);
    if(f1) printf("队列初始化成功!\n");
    else printf("队列初始化失败!\n");

    //入队
    printf("请输入队列中元素的个数:");
    scanf("%d",&n);
    printf("请输入队列中元素的值:");
    for(i=0; i<n; i++) {
        scanf("%d",&a);
        EnQueue(&link,a);
    }

    //获取队列长度
    len = QueueLength(&link);
    printf("队列的长度为:%d\n",len);

    //判断队列是否为空
    f2 = EmptyQueue(&link);
    if(f2) printf("队列为空!\n");
    else printf("队列不为空!\n");

    //遍历队列
    QueueTraverse(&link,&visit);

    //出队
    f3 = DeQueue(&link,&e);
    if(f3) printf("删除的队头元素为:%d\n",e);
    else printf("队列为空!无法删除队头元素!\n");

    //取得队头元素
    f4 = GetHead(&link,&e);
    if(f4) printf("队头元素为:%d\n",e);
    else printf("队列为空!");

    //清空队列
    f6 = ClearQueue(&link);
    if(f6) printf("清空队列成功!\n");
    else printf("清空队列失败!\n");

    //销毁队列
    f5 = DestoryQueue(&link);
    if(f5) printf("销毁队列成功!\n");
    else printf("销毁队列失败!\n");

    return 0;
}