Implementieren von List-Klasse mit der Verwendung von Stack-Klasse

Question

Ich versuche, eine interpretierte Programmiersprache wie Python zu schreiben, also brauche ich eine List-Klasse zum Speichern von 'Adresse von' Funktionen und Variablen. Ich bin für die Umsetzung List-Klasse Stack-Klasse implementiert:

typedef unsigned int UIntegerP; //This type for storing addresses 
#define Free 0x0 

template <typename T> class Stack{ 
    public: 
     unsigned long UsedBSize; // You can use that like End Of Stack (EOS) 

     Stack(void){ 
      this->BSize = 0; this->UsedBSize = 0; 
      this->Buffer = new T;   
     } 
     ~Stack(void){ 
      delete this->Buffer; 
     } 

     inline void Push(T Variable){ 
      if(this->UsedBSize == this->BSize){ 
       this->BSize++; 
      } this->Buffer[this->UsedBSize] = Variable; this->UsedBSize++; 
     }  
     inline T Pop(bool IsProtected = false){ 
      if(IsProtected){ 
       return this->Buffer[this->UsedBSize]; 
      }else{ 
       this->UsedBSize--; T Element = this->Buffer[this->UsedBSize]; this->Buffer[this->UsedBSize] = Free; 
       return Element; 
      } 
     } 
    private: 
     T *Buffer; 
     unsigned long BSize; 

}; 

Und das ist die Klasse i implementieren möchten:

class List{ 
    private: 
     Stack<UIntegerP> *stack = new Stack<UIntegerP>; //A stack for storing variable addresses 

    public: 
     ~List(void){ 
      delete this->stack; 
     } 

     List(Stack<UIntegerP> Elements){ 
      while(Elements.UsedBSize != 0){ 
       this->stack->Push(Elements.Pop()); 
      } 
     } 

     List(Stack<UIntegerP> *Elements){ 
      while(Elements->UsedBSize != 0){ 
       this->stack->Push(Elements->Pop()); 
      } 
     } 

     UIntegerP Get(unsigned long Size); //Get Address with Index number 
     UIntegerP Set(unsigned long Size, UIntegerP Address); //Set Address with Index number 
}; 

Ich werde diese List-Klasse verwenden, um wie Wörterbücher Python implementiert. UIntegerP-Typ ist für die Variablenklasse erforderlich. Wie kann ich diese zwei Funktionen implementieren?

Answer 1

Angenommen, Ihr Stack stellt nur die Funktionen Push und Pop zur Verfügung, dann können Sie die Liste mit Indizierung nicht effizient implementieren.

Wenn Sie im normalen C++ - Stil programmieren, wäre die grundlegende Datenstruktur ein dynamic array oder ein linked list. Sie können dann einen Stapel darüber erstellen. Beachten Sie jedoch, dass die Indizierung in einer verknüpften Liste langsam ist (lineare Zeitkomplexität).

Wenn Sie in einem funktionalen Stil programmieren, dann ist die Grundstruktur "Liste", die eine unveränderliche einfach verknüpfte Liste ist und es ist praktisch das gleiche wie unveränderlichen Stapel. Aber auch hier wird die Indexierung langsam sein.

---

Beachten Sie auch, dass Ihr Stack falsch implementiert wird: Sie Zuweisung Speicher für einen einzelnen T, aber dann übernehmen Sie, dass für eine unbegrenzte Anzahl von T s nutzen können. Sie müssen entweder die Route der verknüpften Liste wählen: Weisen Sie jedem Element einen neuen Knoten zu und verbinden Sie die Knoten mit Zeigern; oder Sie müssen die dynamische Array-Route gehen: Ordnen Sie ein Array mit einer bestimmten Größe zu, und wenn es zu klein wird, weisen Sie es neu zu.