分钟堆栈中的最小值

-1

我试图让StackMin，Pop和Push中的最小值都是Θ(1)。我的代码不能正常工作......这是我的尝试：分钟堆栈中的最小值

typedef struct{ 
    int top; 
    int entry[1000]; 
    int small; 
} Stack; 

void Pop(int *e,Stack *ps){ 
    *e=ps->entry[--ps->top]; 
} 

void Push(int e,Stack *ps){ 
    ps->entry[ps->top++]=e; 
} 

int StackMin(Stack *ps){ 
    ps->small=ps->entry[ps->top]; 
    while(!StackEmpty(ps)){ 
     int *e; 
     *e=ps->entry[--ps->top]; 
     if(ps->small >= *e){ 
      ps->small = *e; 
     } 
    } 
    return ps->small; 
}

来源

2012-10-24 mike memo

什么不行？编译器会给你错误吗？你必须提供比这更多的信息。 –

“小”访问未初始化的内存，你关了一个。 –

推，流行音乐和民不能都是'Theta（1）'，除非你正在谈论一个历史分钟。如果你存储一个最小值，你可以在push和StackMin上得到'O（1）'，但是如果你弹出一个等于min的值，你将不得不重新计算min - 一个线性操作。你可以存储排序的数组，使Min计算为'O（1）'，但是推送和弹出'O（n）' - 你可以将它存储为排序的，但是有一个引用数组值的栈，和min都显示为'O（1）'，但由于push和pop违反了排序后的存储，所以在修复损坏时，它们实际上就是'O（n）'。 – FrankieTheKneeMan

你需要有两个叠做到这一点。一个堆栈可以有顺序的最小值，并且每次调用最小值时都会更新此堆栈。尝试找出你自己的算法。

来源

2012-10-24 21:39:39 noMAD

你并不需要在这些行的指针：

int *e; 
*e=ps->entry[--ps->top]; 
if(ps->small >= *e){ 
    ps->small = *e; 
}

他们更改为：

int e = ps->entry[--ps->top]; 
if(ps->small >= e){ 
    ps->small = e; 
}

来源

2012-10-24 21:41:52 user1610015

达到1000！投给我的人，让我到2000年:) – user1610015

“不工作”是不是有帮助的说明。但是在任何情况下，这看起来有问题的：

int *e; 
*e=ps->entry[--ps->top]; 
if(ps->small >= *e){ 
    ps->small = *e; 
}

时，你已经声明了一个指针（目前指着什么事情 - 这是联合国初始化），然后向它指向的（无效）位置写入一个值。

如果偶然代码不会崩溃，并且您的问题是关于算法，另一个用户发布了有关该问题的答案。

来源

2012-10-24 21:42:46 paddy

分钟堆栈中的最小值

回答

相关问题