รายการทั่วไป (Generalized Lists) ในโครงสร้างข้อมูล

รายการทั่วไป (Generalized Lists) คืออะไร

รายการทั่วไป (Generalized List) สามารถนิยามได้ดังนี้: รายการทั่วไป L คือลำดับจำกัดของ n องค์ประกอบ (n ≥ 0) องค์ประกอบแต่ละตัว (ei) จะเป็นอะตอม (องค์ประกอบเดี่ยว) หรือรายการทั่วไปอีกชุดหนึ่ง องค์ประกอบที่ไม่ใช่อะตอมจะกลายเป็นรายการย่อย (sub-list) ของ L

ตัวอย่าง

สมมติ L = ((A, B, C), ((D, E), F), G) รายการ L นี้มี 3 องค์ประกอบ ได้แก่ รายการย่อย (A, B, C) รายการย่อย ((D, E), F) และอะตอม G อีกครั้ง รายการย่อย ((D, E), F) มี 2 องค์ประกอบ คือรายการย่อย (D, E) และอะตอม F

การนิยามโครงสร้างใน C++

class GeneralizedListNode {
private:
    GeneralizedListNode *next;
    bool tag;
    union {
        char data;
        GeneralizedListNode *down;
    };
};

การทำงานของโครงสร้าง

• tag = true: โหนดแทนรายการย่อย (sub-list) ตัวชี้ down จะชี้ไปยังโหนดแรกของรายการย่อย
• tag = false: โหนดแทนอะตอม (atom) ตัวชี้ next จะชี้ไปยังองค์ประกอบถัดไปในรายการ

โครงสร้างหน่วยความจำจะมีลักษณะดังรูปประกอบ