欢迎光临散文网 会员登陆 & 注册

《数据结构(C语言版)》循环队列的实现

2022-04-01 12:16 作者:回到唐朝当少爷  | 我要投稿

清华大学计算机系列教材   累计发行超400万册

严蔚敏 吴伟民 编著

数据结构(C语言版)

以下是本人对该紫皮书第三章栈和队列中循环队列的代码实现,即课本3.4.3节队列的顺序表示和实现,本人使用少用一个元素空间的方式区分队满与队空,并处理了非法输入字母等问题。

(貌似专栏把我缩进吃了,懒得加了,另外建议用visual studio编译) 

代码实现如下

/*

课本P63页倒数第二段,由于C语言中中仅凭等式Q.front==Q.rear无法判断队列空间是“空”还是“满”

可以采取两种处理方法:

1.另设一个标志位以区别队列是“空”还是“满”

2.少用一个元素空间,约定以队列头指针在队列尾指针的下一位置作为队列成“满”状态的标志

下列代码中采取处理方法2

队空标志:front==rear

队满标志:(rear+1)%MAXQSIZE==front

*/

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#include <stdlib.h>

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

#define MAXQSIZE 6

typedef int Status;

typedef int QElemType;

typedef struct

{

QElemType* base;

int front;

int rear;

}SqQueue;

Status InitQueue(SqQueue& Q);//队列的初始化

int QueueLength(SqQueue Q);//返回Q的元素个数,即队列的长度

Status EnQueue(SqQueue& Q, QElemType e);//入队

Status DeQueue(SqQueue& Q, QElemType& e);//出队

Status GetHead(SqQueue Q, QElemType& e);//用e返回队头元素,若队空返回ERROR

void Menu()

{

printf("***************************\n");

printf("********0:退出系统********\n");

printf("********1:元素入队********\n");

printf("********2:元素出队********\n");

printf("********3:求队列长********\n");

printf("********4:求队头值********\n");

printf("***************************\n");

}

int main()

{

int option;

int value;

SqQueue MyQueue;

InitQueue(MyQueue);

Menu();

printf("请输入你想使用的功能:");

while (scanf("%d", &option) != EOF)

{

while (getchar() != '\n');

switch (option)

{

case 1:

printf("请输入你想入队的元素:");

while (scanf("%d", &value) != 1)

{

while (getchar() != '\n');

printf("非法输入,请重试\n");

}

if (EnQueue(MyQueue, value))

{

printf("入队成功!\n");

}

else

{

printf("队列的最大长度为%d,队列已满!\n", MAXQSIZE - 1);

}

break;

case 2:

if (DeQueue(MyQueue, value))

{

printf("元素%d出队成功!\n", value);

}

else

{

printf("队空,无元素可出队\n");

}

break;

case 3:

printf("队列长度为%d\n", QueueLength(MyQueue));

break;

case 4:

if (GetHead(MyQueue, value))

{

printf("队头元素为%d\n", value);

}

else

{

printf("队空,无队头元素\n");

}

break;

case 0:

printf("感谢使用!\n");

exit(0);

default:

printf("非法输入,请重试\n");

}

Menu();

printf("请输入你想使用的功能:");

}

return 0;

}

Status InitQueue(SqQueue& Q)//队列的初始化

//构造一个空队列

{

Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));

if (!Q.base)

{

exit(OVERFLOW);

}

Q.front = Q.rear = 0;

return OK;

}

int QueueLength(SqQueue Q)//返回Q的元素个数,即队列的长度

{

return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;

}

Status EnQueue(SqQueue& Q, QElemType e)//入队

//插入元素e为Q的新的队尾元素

{

if ((Q.rear + 1) % MAXQSIZE == Q.front)

{

return ERROR;//队列满

}

Q.base[Q.rear] = e;

Q.rear = (Q.rear + 1) % MAXQSIZE;//队尾指针+1

return OK;

}

Status DeQueue(SqQueue& Q, QElemType& e)//出队

//若队列不空,则删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR

{

if (Q.front == Q.rear)//如果队空

{

return ERROR;

}

e = Q.base[Q.front];

Q.front = (Q.front + 1) % MAXQSIZE;

return OK;

}

Status GetHead(SqQueue Q, QElemType& e)//用e返回队头元素,若队空返回ERROR

{

if (Q.front != Q.rear)

{

e = Q.base[Q.front];//返回对头指针元素,对头指针不变

return OK;

}

return ERROR;

}


《数据结构(C语言版)》循环队列的实现的评论 (共 条)

分享到微博请遵守国家法律