โครงสร้างข้อมูลสำหรับ n องค์ประกอบและการดำเนินการ O(1)?

ที่นี่เราจะเห็นโครงสร้างข้อมูลหนึ่งโครงสร้างที่มีองค์ประกอบ n รายการและการดำเนินการ O(1) ดังนั้นการดำเนินการจะใช้เวลาคงที่ในการดำเนินการ

โครงสร้างข้อมูลจะเก็บ n องค์ประกอบ (จาก 0 ถึง n-1) ข้อมูลสามารถอยู่ในลำดับใดก็ได้ การแทรก การลบ และการค้นหาจะใช้เวลา O(1)

เพื่อแก้ปัญหานี้ เราจะใช้อาร์เรย์บูลีนหนึ่งอาร์เรย์ สิ่งนี้จะระบุว่ารายการนั้นมีอยู่หรือไม่อยู่ที่ตำแหน่ง i หากมีรายการอยู่ จะถือ 1 มิฉะนั้น 0

อัลกอริทึม

การเริ่มต้น(n)

begin
   fill all elements of the Boolean array as 0
end

insert(i)

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

ลบ(i)

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

ค้นหา(i)

begin
   return item at position i
end

ตัวอย่าง

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