欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C语言数据结构之链队列的基本操作

程序员文章站 2022-03-12 14:55:37
目录1.队列的定义2.队列的表示和实现(1) 初始化操作(2)销毁队列(3) 入队操作(4) 出队操作附录完整代码:总结1.队列的定义队列 (queue)是另一种限定性的线性表,它只允许在表的一端插入...

1.队列的定义

队列 (queue)是另一种限定性的线性表,它只允许在表的一端插入元素,而在另一端删除元素,所以队列具有先进先出(fist in fist out,缩写为fifo)的特性。在队列中,允许插入的一端叫做队尾(rear),允许删除的一端则称为队头(front)。 假设队列为q=(a1,a2,…,an),那么a1就是队头元素,an则是队尾元素。队列中的元素是按照a1、a2、…、an的顺序进入的, 退出队列也必须按照同样的次序依次出队,也就是说,只有在a1、a2、…、an-1都离开队列之后,an才能退出队列。

2.队列的表示和实现

C语言数据结构之链队列的基本操作

链队列可以定义如下:

#define  true    1
#define  false  0
typedef struct qnode{
        qelemtype  data;
        struct qnode *next;
}qnode, *queueptr;
typedef struct{
        queueptr  front;
        queueptr  rear;
}linkqueue;

(1) 初始化操作

status initqueue(linkqueue &q)
{ 
       q.front = q.rear = (queueptr) malloc(sizeof(qnode));
       if(!q.front) exit ( overflow);
       q.front ->next = null;
       return ok;
} 

(2)销毁队列

status destroyqueue(linkqueue &q)
{ 
        while(q.front) {
	q.rear = q.front->next;
	free (q.front);
	q.front = q.rear;
        }
        return ok;
}

(3) 入队操作

status enqueue (linkqueue &q, qelemtype e)
{ 
        p= (queueptr) malloc(sizeof(qnode));
        if (!p) exit ( overflow);
        p->data = e;  p->next = null;
        q.rear -> next =p;
        q.rear = p;
        return ok;
}

(4) 出队操作

status dequeue (linkqueue &q, qelemtype &e)
{
        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;
        free(p);
        return ok;
}

附录完整代码:

#include<iostream>
using namespace std;
#define ok 1
#define false 0

typedef int qelemtype;
typedef int status;

typedef struct qnode{
    qelemtype data;
    struct qnode *next;
}qnode,*queueptr;
typedef struct{
    queueptr font;
    queueptr near;
}linkqueue;

status initqueue(linkqueue &q)
{
    q.font=(queueptr)malloc(sizeof(qnode));
    if(!q.font) exit(false);
    q.font->next=null;
    q.near=q.font;
    return ok;
}
status queueempty(linkqueue q)
{
    if(q.font->next) return ok;
    return false;
}
status enqueue(linkqueue &q,qelemtype e)
{
    queueptr p=(queueptr)malloc(sizeof(qnode));
    p->data=e;
    q.near->next = p;
    q.near = q.near->next;
    p->next = null;
    return ok;
}
status dequeue(linkqueue &q,qelemtype &e)
{
    if(!q.font->next) return false;
    queueptr p;
    p=q.font->next;
    e=p->data;
    q.font->next=p->next;
    if(q.near==p) q.near=q.font;   //当是最后一个元素时,q.font=null,q.near=q.font
    free(p);
    return ok;
}
status clearqueue(linkqueue &q)
{
    queueptr p;
    p=q.font->next;
    queueptr q;
    while(p)
    {
        q=p;
        p=p->next;
        q.font->next=p;
        free(q);
    }
    q.near=q.font;
    return ok;
}
void menu()
{
    cout<<"初始化队列:1"<<endl;
    cout<<"入队:2"<<endl;
    cout<<"出队:3"<<endl;
    cout<<"清空队列:4"<<endl;
    cout<<"退出:5"<<endl;
}
int main()
{
    linkqueue q;
    while(true)
    {
        int n;
        menu();
        scanf("%d",&n);
        int e=-1;
        switch(n)
        {
            case 1:
                initqueue(q);
                continue;
            case 2:
                printf("请输入一个元素");
                scanf("%d",&e);
                enqueue(q,e);
                continue;
            case 3:
                dequeue(q,e);
                printf("\n出队元素%d\n",e);
                continue;
            case 4:
                clearqueue(q);
                printf("清空成功\n");
                continue;
            default:
                break;
        }
        if(n==5)break;
    }

}

总结

本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注的更多内容!