分鐘堆棧中的最小值

-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

分鐘堆棧中的最小值

回答

相關問題