C++堆棧數據結構。這段代碼有什麼問題？

所以我目前正試圖通過實現各種數據結構來將我的Java體驗遷移到C++，以便讓它們至少實現一次。C++堆棧數據結構。這段代碼有什麼問題？

你介意給我一些建議嗎？我遇到的問題主要集中在push（int值）和特別是pop（）中的指針。由於推動似乎正常工作，我發現自己努力爭取在彈出的東西時獲得正確的價值。怎麼了？

PS：我也認爲，因爲我手動分配我的數組空間，所以我需要刪除它。我怎麼做？

#ifndef STACK_H 
#define STACK_H 

class Stack 
{ 
private: 
    int *stackArray; 
    int elementsInArray; 
    int allocatedArraySize; 
    int alpha; 
    int beta; 

public: 
    Stack(); 
    void push(int aValue); 
    int pop(); 
    bool isEmpty(); 
    int size() const; 
}; 

#endif

和實現：

#include <iostream> 
#include "Stack.h" 

Stack::Stack() 
{ 
    alpha = 4; 
    beta = 2; 
    elementsInArray = 0; 
    allocatedArraySize = 1; 
    stackArray = new int[1]; 
} 

void Stack::push(int aValue) 
{ 
    if (elementsInArray == allocatedArraySize) 
    { 
     int temporaryArray[allocatedArraySize*beta]; 

     for (int i = 0; i < elementsInArray; i++) 
      temporaryArray[i] = stackArray[i]; 

     stackArray = temporaryArray; 
     allocatedArraySize *= beta; 
    } 

    elementsInArray++; 
    stackArray[elementsInArray] = aValue; 
} 

int Stack::pop() 
{ 
    int result = -INT_MAX; 

    if (elementsInArray == 0) 
     return result; 

    if (elementsInArray > 0) 
    { 
     result = stackArray[elementsInArray-1]; 
     elementsInArray--; 

     if (elementsInArray <= allocatedArraySize/alpha) 
     { 
      int temporaryArray[allocatedArraySize/alpha]; 

      for (int i = 0; i < elementsInArray; i++) 
       temporaryArray[i] = stackArray[i]; 

      stackArray = temporaryArray; 
      allocatedArraySize /= beta; 
     } 
    } 

    return result; 
} 

bool Stack::isEmpty() 
{ 
    if (elementsInArray == 0) 
     return true; 

    return false; 
} 

int Stack::size() const 
{ 
    return allocatedArraySize; 
}

來源

2011-08-22 pkluz

看起來更像C而不是C++。 –

對不起，但你做的都是錯誤的，無論推送還是彈出都無法正常工作。最大的問題是你不懂C++中的內存分配（這有點奇怪，因爲如果你用Java這樣做的話，你會更接近它）。你不能這樣做'int temporaryArray [allocatedArraySize * beta]; ... stackArray = temporaryArray;'。它會編譯，但它肯定不會工作。內存分配在這樣的論壇中是一個太大的話題。你需要**緊急**閱讀一本關於C++的書。 – john

對於初學者來說，你應該交的增加陣列上的指標，所以更改：

elementsInArray++; 
stackArray[elementsInArray] = aValue;

到：

stackArray[elementsInArray++] = aValue;

或：

stackArray[elementsInArray] = aValue; 
elementsInArray++;

其次，當你在if語句中創建新的臨時數組...因此它是一個局部變量並放置在系統上EM堆棧並在退出if語句後丟失。因此，改變

int temporaryArray[allocatedArraySize*beta];

到：

int *temporaryArray = new int[allocatedArraySize*beta];

三，添加在刪除你被複制tempArray的位置之前，從節約的stackArray原指針在談論，然後再執行刪除您之後做了指針複製。

最後，你將不得不作出類似更改您的彈出功能......

來源

2011-08-22 21:22:38

而且OP還需要添加一個析構函數，將構造函數和賦值運算符複製到Stack類。只有這樣他們纔有工作代碼。 – john

非常感謝Gregg，非常感謝！你和ex0du5幫了我很多。約翰，我知道當談到cpp時我有很多東西要學，但是我不是編程中的處女，當你宣佈我的嘗試基本上在三個單獨的評論中毫無希望時，另外三個人設法幫助我更多。儘管如此，謝謝你。 – pkluz

我想我已經被配音爲你解決你的代碼kata了！ ;）下次我只給提示！ –

好吧，我相信你已經知道你已經堆作爲一種通用的（C++稱之爲模板）在STD庫。假設你以代碼kata的身份執行此操作，我將開始將它作爲模板來編寫，因此它不能使用除整數之外的其他對象類型。另外，如果要編寫更多這些低級結構（作爲kata的一部分），請編寫一個瘦類，在此類中委派所有分配，重新分配和分配大小跟蹤，並使用該類代替使用數組的直。

來源

2011-08-22 21:19:33 lurscher

真的這個答案只是錯過了觀點。發佈的代碼有嚴重的錯誤。 – john

「Code-Kata」正是我想要做的。很好地措辭:-) – pkluz

將在這段代碼上工作一段時間，並在稍後遷移到模板時嘗試遵循您的建議。 – pkluz

您正在使用的堆棧上的數組（不是你的籌碼 - 該程序執行堆棧）。在推送功能中，它是一個名爲temporaryArray的人。從該函數返回時，該數組的地址將無效（因爲其他函數將使用堆棧來存放其他數據）。

你想要做的是在堆上分配該數組。只要你需要它，這個記憶就會留在你的程序中。要做到這一點，你會分配你temporaryArray像

int * temporaryArray(new int[allocatedArraySize*beta]);

然後，複製從舊數組中的元素之後，你會用它刪除：

delete [] stackArray;

執行此操作與分配stackArray前temporaryArray。

您的數據結構可能存在其他問題，但是您正在正確地進行基本索引並適當地增加/減少當前索引（儘管我建議在不使用臨時索引時使用preincrement/decrement表單好習慣 - 即。++ elementsInArray/--elementsInArray）。

來源

2011-08-22 21:23:14 ex0du5

非常感謝:)幫助我出去了很多。 – pkluz

C++堆棧數據結構。這段代碼有什麼問題？

回答

相關問題