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

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

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

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

อัลกอริทึม

initialization(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

search(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]; }