请注意,本文编写于 1424 天前,最后修改于 1424 天前,其中某些信息可能已经过时。
队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它简称为链队列。
队头指针指向队列的头结点,队尾指针指向终端结点。
链队列的结构为:
typedef int QElemType; /* QElemType类型根据实际情况而定,这里假设为int */
typedef struct QNode /* 结点结构 */
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct /* 队列的链表结构 */
{
QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;
整体代码:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
typedef int Status;
typedef int QElemType; /* QElemType类型根据实际情况而定,这里假设为int */
typedef struct QNode /* 结点结构 */
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct /* 队列的链表结构 */
{
QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;
Status InitQueue(LinkQueue *Q);//初始化操作,建立一个空队列
Status Destroy(LinkQueue *Q);//若队列Q存在,则销毁它。
Status ClearQueue(LinkQueue *Q);//将队列Q清空
Status QueueEmpty(LinkQueue Q);//若队列Q为空,返回true,否则返回false
Status GetHead(LinkQueue Q, QNode *e);//若队列Q存在且非空,用e返回队列Q的队头元素。
Status EnQueue(LinkQueue *Q, QElemType e);//若队列Q存在,插入新元素e到队列Q中并成为队尾元素。
Status DeQueue(LinkQueue *Q, QElemType *e);//删除队列Q中队头元素,并用e返回其值
Status QueueLength(LinkQueue Q);//返回队列Q的元素个数
int main() {
LinkQueue* Q = (LinkQueue*)malloc(sizeof(LinkQueue));
QNode* e;
QElemType ee;
int status;
InitQueue(Q);
EnQueue(Q, 111);
EnQueue(Q, 222);
EnQueue(Q, 333);
printf("结点数量:%d \n", QueueLength(*Q));
GetHead(*Q, e);
printf("首元素的值e->data = %d;\n", e->data);
DeQueue(Q, &ee);
printf("被删除的值e->data = %d;\n", ee);
printf("结点数量:%d \n", QueueLength(*Q));
printf("队列为空吗? : %d \n", QueueEmpty(*Q));
GetHead(*Q, e);
printf("首元素的值e->data = %d;\n", e->data);
ClearQueue(Q);
if (GetHead(*Q, e) == 1)
printf("首元素的值e->data = %d;\n", e->data);
printf("结点数量:%d \n", QueueLength(*Q));
printf("队列为空吗? : %d \n", QueueEmpty(*Q));
Destroy(Q);
if (GetHead(*Q, e) == 1)
printf("首元素的值e->data = %d;\n", e->data);
printf("结点数量:%d \n", QueueLength(*Q));
printf("队列为空吗? : %d \n", QueueEmpty(*Q));
printf("执行完成\n");
printf("\n");
return 0;
}
//初始化操作,建立一个空队列
Status InitQueue(LinkQueue *Q)
{
QueuePtr head = (QueuePtr)malloc(sizeof(QNode));
head->data = 0;
head->next=NULL;
Q->front = head; // 首指针指向头结点
printf("Q->front = head;成功\n");
Q->rear = head; // 尾指针指向头结点
printf("Q->rear = head;成功\n");
return OK;
}
//若队列Q存在,则销毁它。
Status Destroy(LinkQueue *Q)
{
if (Q->front)
{
ClearQueue(Q);
QueuePtr q = Q->front;
free(q);//释放头结点
Q->front = NULL;
Q->rear = NULL;
}
return OK;
}
//将队列Q清空
Status ClearQueue(LinkQueue *Q)
{
QueuePtr p,q;
p = Q->front->next; //p指向第一个数据结点
while (p)
{
q = p->next;
free(p);//free释放的是对内存空间的使用权,释放后内存值还在
p = q;
}
Q->front->data = 0;//头结点数据清0
Q->front->next = NULL;
Q->rear = Q->front;
return OK;
}
//若队列Q为空,返回true,否则返回false
Status QueueEmpty(LinkQueue Q)
{
if (!Q.front)
return OVERFLOW;
if (Q.front == Q.rear)
return TRUE;
else
return FALSE;
}
//若队列Q存在且非空,用e返回队列Q的队头元素。
Status GetHead(LinkQueue Q, QNode *e)
{
if (!Q.front)
return OVERFLOW;
if (Q.front == Q.rear)
{
return ERROR;
}
e->data = Q.front->next->data;
e->next = Q.front->next->next;
return OK;
}
// 插入元素e为Q的新的队尾元素
Status EnQueue (LinkQueue *Q, QElemType e)
{
if (!Q)
return OVERFLOW;
QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
if (!s) /* 存储分配失败 */
{
exit(OVERFLOW);
}
s->data=e;
printf("s->data=%d;\n", s->data);
s->next=NULL;
Q->rear->next = s; // 把拥有元素e新结点s赋值给原队尾结点的后继
Q->rear=s; // 把当前的s设置为队尾结点,rear指向s
Q->front->data++;//结点数量加1
return OK;
}
// 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR
Status DeQueue(LinkQueue *Q, QElemType *e)
{
if (!Q)
return OVERFLOW;
QueuePtr p;
if (Q->front == Q->rear)
return ERROR;
p=Q->front->next; //将欲删除的队头结点暂存给p
*e=p->data;//将欲删除的队头结点的值赋值给e
Q->front->next = p->next;//将原队头结点后继p->next赋值给头结点后继
if(Q->rear==p) //若队头是队尾,则删除后将rear指向头结点
Q->rear=Q->front;
free(p);
Q->front->data -= 1;//结点数量减1
return OK;
}
//返回队列Q的元素个数
Status QueueLength(LinkQueue Q)
{
if (Q.front != NULL)
return Q.front->data;
else
return 0;
}
全部评论 (共 1 条评论)