LinkedList ปัญหาการพึ่งพาแบบวงกลม

ข้อมูลเบื้องต้นเกี่ยวกับปัญหา: ฉันกำลังสร้างโปรแกรมเพื่อติดตามเส้นทางการบินของสนามบินโดยใช้รายการที่เชื่อมโยง เช่น ถ้าชุดข้อมูลเป็น

(Austin - Dallas, Dallas - Houston)

และคุณพยายามค้นหาเที่ยวบิน

(Austin - Houston)

มันจะคำนวณว่าคุณต้องใช้เส้นทางบิน:

(Austin - Dallas - Houston)

วิธีที่โซลูชันของฉันทำงาน (หากฉันสามารถทราบวิธีการทำเช่นนี้ได้) คือฉันมีรายการลิงก์ภายนอกที่ประกอบด้วย OuterNode ซึ่งแต่ละรายการมีรายการเที่ยวบินที่ลิงก์ภายใน รายการที่เชื่อมโยงภายในประกอบด้วย InnerNode ซึ่งมีตัวชี้ไปยังโหนดด้านนอก (หรือที่เรียกว่าปลายทางของเที่ยวบิน) ตามทฤษฎีแล้ว มันจะทำให้หลายสิ่งหลายอย่างง่ายขึ้นในการวนซ้ำโดยไม่ต้องคัดลอกข้อมูลผ่านสตริงต่อไป ในส่วนหัวของฉัน มีสิ่งต่างๆ มากมายที่ต้องพึ่งพาซึ่งกันและกัน และไม่สามารถนำไปปฏิบัติตามลำดับที่ถูกต้องได้ (ทั้งหมดนี้อยู่ในส่วนหัวของคลาสรายการภายใน)

struct OuterNode {
    InnerList flights;
    int name;
    OuterNode* next;
};

struct InnerNode {
    OuterNode* dest;
    int price;
    InnerNode* next;
};
class InnerList
{
public:
    InnerList();
    ~InnerList();
    void add(InnerNode*);
private:
    InnerNode* innerhead;
};

โดยพื้นฐานแล้ว:

OuterNode – ความต้องการ InnerList (ยังไม่มีคำจำกัดความ)

InnerNode – ความต้องการ OuterNode

InnerList – ความต้องการ InnerNode

และในปัจจุบันข้อผิดพลาดคือไม่มี InnerList เมื่อ OuterNode จำเป็นต้องสร้าง ฉันจะแก้ไขปัญหานี้ได้อย่างไรเพื่อให้ทุกอย่างพบสิ่งที่ต้องการ มีการใช้เทมเพลตอย่างสร้างสรรค์หรืออะไรที่ฉันสามารถใช้เพื่อแก้ไขปัญหานี้ได้หรือไม่


c++ nodes circular-dependency linked-list
person Jd Francis    schedule 10.11.2014    source แหล่งที่มา

คำตอบ (2)


arrow_upward
0
arrow_downward

"มีการใช้เทมเพลตอย่างสร้างสรรค์หรือมีอะไรที่ฉันสามารถใช้เพื่อแก้ไขปัญหานี้ได้หรือไม่"

ไม่จำเป็นต้องใช้เทมเพลต คุณสามารถปรับโครงสร้างโค้ดของคุณใหม่เล็กน้อย และแนะนำการประกาศล่วงหน้าสำหรับ struct InnerNode;

struct InnerNode;  // << forward declaration 

// Declare class InnerList first
class InnerList {
public:
    InnerList();
    ~InnerList();
    void add(InnerNode*);
private:
    InnerNode* innerhead;
};

struct OuterNode {
    InnerList flights;
    int name;
    OuterNode* next;
};

// Finally declare InnerNode completely
struct InnerNode {
    OuterNode* dest;
    int price;
    InnerNode* next;
};

สาธิตสด

โปรดทราบ:

แทนที่จะสร้างโครงสร้างรายการลิงก์ของคุณเอง คุณอาจลองใช้ std::list<InnerNode*> flights; หรือ แม้แต่สมาชิก std::vector<InnerNode*> flights; ใน OuterNode struct ของคุณ
แม้ว่าโซลูชันเหล่านี้จำเป็นต้อง จัดการอินสแตนซ์ของ InnerNode อย่างเหมาะสมโดยใช้การจัดการหน่วยความจำ std::list<std::shared_ptr<InnerNode>> หรือ std::vector<std::shared_ptr<InnerNode>> ดูเหมือนจะมาถูกทางแล้ว

person πάντα ῥεῖ    schedule 10.11.2014

arrow_upward
0
arrow_downward

คุณต้องใช้การประกาศส่งต่อ

เมื่อคอมไพลเลอร์จำเป็นต้องรู้ว่ามีประเภทอยู่ แต่ไม่จำเป็นต้องรู้อะไรเกี่ยวกับคำจำกัดความของมัน (เช่นในกรณีเมื่อคุณประกาศตัวชี้) คุณสามารถใช้การประกาศไปข้างหน้าเพื่อบอกคอมไพเลอร์ 'ประเภทด้วย มีชื่อนี้อยู่':

class InnerNode;
class InnerList
{
public:
    InnerList();
    ~InnerList();
    void add(InnerNode*);
private:
    InnerNode* innerhead;
};

สิ่งนี้จะคอมไพล์ เนื่องจาก InnerList ไม่จำเป็นต้องรู้อะไรเกี่ยวกับ InnerNode; เพียงแต่ต้องรู้ว่ามีประเภทชื่อ InnerNode อยู่

หากคุณมีอินสแตนซ์ประเภทจริงในชั้นเรียนของคุณ เช่นเดียวกับในกรณีของ OuterNode การประกาศส่งต่อจะไม่ทำงาน ชั้นเรียนต้องทราบจำนวนพื้นที่เก็บข้อมูลที่จะจัดสรรให้กับประเภทนี้ ดังนั้นจึงจำเป็นต้องมีคำจำกัดความแบบเต็ม

คุณสามารถใช้การประกาศส่งต่อเพื่อทำการคอมไพล์ InnerList และ InnerNode ได้ แต่คุณจะต้องย้ายคำจำกัดความของ OuterNode ไปอยู่หลัง InnerList เนื่องจากขึ้นอยู่กับการกำหนดไว้

person Collin Dauphinee    schedule 10.11.2014