Sunhuiquan_ 2020-02-26 14:58 采纳率: 0%
浏览 592

求大家帮我看看这个队列问题,我要崩了啊啊啊啊

本人大一小白,今天做pta的一道队列问题,我真是崩溃了啊啊啊,求大神救救孩子吧!!!
双端队列(deque,即double-ended queue的缩写)是一种具有队列和栈性质的数据结构,即可以(也只能)在线性表的两端进行插入和删除。若以顺序存储方式实现双端队列,请编写例程实现下列操作:

Push(X,D):将元素X插入到双端队列D的头;
Pop(D):删除双端队列D的头元素,并返回;
Inject(X,D):将元素X插入到双端队列D的尾部;
Eject(D):删除双端队列D的尾部元素,并返回。

https://pintia.cn/problem-sets/434/problems/6096网站

下面是我写的两个答案,第一个答案错误,头指针指向头一个元素的前一个位置;第二个答案全对,尾指针指向最后一个元素的后一个位置,我感觉第一个答案没问题啊,已经有点崩溃了

第一个错误的//头指针指向头一个元素的前一个
bool Push(ElementType X, Deque D)
{
if ((D->Rear + 1) % D->MaxSize == D->Front)
return false;

D->Data[D->Front] = X;
D->Front = (D->Front + D->MaxSize - 1) % D->MaxSize; //避免出现负数

return true;

}

ElementType Pop(Deque D)
{
if (D->Rear == D->Front)
return ERROR;

D->Front = (D->Front + 1) % D->MaxSize;
return D->Data[D->Front];

}

bool Inject(ElementType X, Deque D)
{
if ((D->Rear + 1) % D->MaxSize == D->Front)
return false;

D->Rear = (D->Rear + 1) % D->MaxSize;
D->Data[D->Rear] = X;
return true;

}

ElementType Eject(Deque D)
{
if (D->Rear == D->Front)
return ERROR;

ElementType temp = D->Data[D->Rear];

D->Rear = (D->Rear + D->MaxSize - 1) % D->MaxSize; //避免出现负数
return temp;

}

第二个正确的
//尾指针指向最后一个元素的后一个

bool Push(ElementType X, Deque D)
{
if ((D->Rear + 1) % D->MaxSize == D->Front)
return false;

D->Front = (D->Front - 1 + D->MaxSize) % D->MaxSize;
D->Data[D->Front] = X;

return true;

}

ElementType Pop(Deque D)
{
if (D->Rear == D->Front)
return ERROR;

ElementType a = D->Data[D->Front];
D->Front = (D->Front + 1) % D->MaxSize;
return a;

}

bool Inject(ElementType X, Deque D)
{
if ((D->Rear + 1) % D->MaxSize == D->Front)
return false;

D->Data[D->Rear] = X;
D->Rear = (D->Rear + 1) % D->MaxSize;
return true;

}

ElementType Eject(Deque D)
{
if (D->Rear == D->Front)
return ERROR;

D->Rear = (D->Rear - 1 + D->MaxSize) % D->MaxSize;
ElementType a = D->Data[D->Rear];
return a;

}

下面是题干
#include
#include

#define ERROR -1
typedef int ElementType;
typedef enum { push, pop, inject, eject, end } Operation;
typedef enum { false, true } bool;
typedef int Position;
typedef struct QNode PtrToQNode;
struct QNode {
ElementType *Data; /
存储元素的数组 /
Position Front, Rear; /
队列的头、尾指针 /
int MaxSize; /
队列最大容量 */
};
typedef PtrToQNode Deque;

Deque CreateDeque( int MaxSize )
{ /* 注意:为区分空队列和满队列,需要多开辟一个空间 */
Deque D = (Deque)malloc(sizeof(struct QNode));
MaxSize++;
D->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
D->Front = D->Rear = 0;
D->MaxSize = MaxSize;
return D;
}

bool Push( ElementType X, Deque D );
ElementType Pop( Deque D );
bool Inject( ElementType X, Deque D );
ElementType Eject( Deque D );

Operation GetOp(); /* 裁判实现,细节不表 /
void PrintDeque( Deque D ); /
裁判实现,细节不表 */

int main()
{
ElementType X;
Deque D;
int N, done = 0;

scanf("%d", &N);
D = CreateDeque(N);
while (!done) {
    switch(GetOp()) {
    case push: 
        scanf("%d", &X);
        if (!Push(X, D)) printf("Deque is Full!\n");
        break;
    case pop:
        X = Pop(D);
        if ( X==ERROR ) printf("Deque is Empty!\n");
        else printf("%d is out\n", X);
        break;
    case inject: 
        scanf("%d", &X);
        if (!Inject(X, D)) printf("Deque is Full!\n");
        break;
    case eject:
        X = Eject(D);
        if ( X==ERROR ) printf("Deque is Empty!\n");
        else printf("%d is out\n", X);
        break;
    case end:
        PrintDeque(D);
        done = 1;
        break;
    }
}
return 0;

}

/* 你的代码将被嵌在这里 */

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 乘性高斯噪声在深度学习网络中的应用
    • ¥15 运筹学排序问题中的在线排序
    • ¥15 关于docker部署flink集成hadoop的yarn,请教个问题 flink启动yarn-session.sh连不上hadoop,这个整了好几天一直不行,求帮忙看一下怎么解决
    • ¥30 求一段fortran代码用IVF编译运行的结果
    • ¥15 深度学习根据CNN网络模型,搭建BP模型并训练MNIST数据集
    • ¥15 C++ 头文件/宏冲突问题解决
    • ¥15 用comsol模拟大气湍流通过底部加热(温度不同)的腔体
    • ¥50 安卓adb backup备份子用户应用数据失败
    • ¥20 有人能用聚类分析帮我分析一下文本内容嘛
    • ¥30 python代码,帮调试,帮帮忙吧