Eine Datenstruktur mit n Elementen und mit O(1) Operationen?

Hier sehen wir eine Datenstruktur mit n Elementen und O(1)-Operationen. Daher wird die Ausführung des Vorgangs eine konstante Zeit in Anspruch nehmen.

Die Datenstruktur enthält n Elemente (von 0 bis n-1). Die Reihenfolge der Daten ist beliebig. Das Einfügen, Löschen und Suchen dauert O(1) Zeit.

Um dieses Problem zu lösen, verwenden wir ein boolesches Array. Dadurch wird angezeigt, ob das Element am Standort i vorhanden ist. 1, wenn das Element vorhanden ist, andernfalls 0.

Algorithmus

Initialisieren(n)

begin
   fill all elements of the Boolean array as 0
end

Einfügen(i)

begin
   set element at index i as 1(true)
end

Löschen(i)

begin
set element at index i as 0(false)
end

Suchen(i)

begin
   return item at position i
end

Beispiel

//initialization
void init(int n) {
   bool dataStructure[n];
   for (int i = 0; i<n; i++)
      dataStructure[i] = 0;
}
//Insertion
void insert(unsigned i) {
   dataStructure[i] = 1;
}
//Deletion
void delete(unsigned i) {
   dataStructure[i] = 0;
}
//Search
bool search(unsigned i) {
   return dataStructure[i];
}

Das obige ist der detaillierte Inhalt vonEine Datenstruktur mit n Elementen und mit O(1) Operationen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!