Struktur data dengan n elemen dan dengan operasi O(1)?

Di sini kita akan melihat struktur data dengan n elemen dan operasi O(1). Oleh itu, operasi akan mengambil masa yang berterusan untuk dilaksanakan.

Struktur data akan memegang n elemen (dari 0 hingga n-1). Data boleh dalam sebarang susunan. Sisipan, pemadaman dan carian akan mengambil masa O(1).

Untuk menyelesaikan masalah ini kita akan menggunakan tatasusunan boolean. Ini akan menunjukkan sama ada item itu wujud di lokasi i. 1 jika item itu wujud, 0 sebaliknya.

Algoritma

Initialize(n)

begin
   fill all elements of the Boolean array as 0
end

Insert(i)

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

Delete(i)

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

Cari(i)

begin
   return item at position i
end

Contoh

//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];
}

Atas ialah kandungan terperinci Struktur data dengan n elemen dan dengan operasi O(1)?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!