LinkedList Masalah Ketergantungan Melingkar

Pengantar masalah: Saya membuat program untuk melacak jalur penerbangan bandara menggunakan daftar tertaut. Misalnya jika kumpulan datanya adalah

(Austin - Dallas, Dallas - Houston)

dan Anda mencoba mencari penerbangan

(Austin - Houston)

itu akan menghitung bahwa Anda perlu mengambil jalur penerbangan:

(Austin - Dallas - Houston)

Cara kerja solusi saya (jika saya tahu cara melakukan ini) adalah saya memiliki daftar tertaut luar yang terdiri dari OuterNode yang masing-masing berisi daftar penerbangan tertaut dalam. Daftar tertaut bagian dalam terdiri dari InnerNode yang berisi penunjuk ke node luar (alias tujuan penerbangan). Secara teori, ini akan membuat banyak hal lebih mudah untuk diulangi tanpa harus terus menyalin data melalui string. Di header saya, terlalu banyak hal yang memerlukan satu sama lain dan implementasinya tidak dapat dilakukan dalam urutan yang benar. (ini semua ada di header kelas innerlist)

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

Jadi pada dasarnya:

OuterNode – membutuhkan InnerList (belum ada definisi)

InnerNode – kebutuhan OuterNode

InnerList – kebutuhan InnerNode

Dan saat ini kesalahannya adalah InnerList tidak ada padahal OuterNode perlu membuatnya. Bagaimana cara memperbaikinya sehingga semuanya sesuai kebutuhan? Apakah ada penggunaan templat secara kreatif atau sesuatu yang dapat saya gunakan untuk memperbaikinya?


c++ nodes circular-dependency linked-list
person Jd Francis    schedule 10.11.2014    source sumber

Jawaban (2)


arrow_upward
0
arrow_downward

"Apakah ada penggunaan template secara kreatif atau sesuatu yang dapat saya gunakan untuk memperbaikinya?"

Tidak perlu menggunakan templat, Anda cukup menyusun ulang kode Anda sedikit, dan memperkenalkan deklarasi penerusan untuk 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;
};

DEMO LANGSUNG

HARAP DICATAT:

Daripada membuat struktur daftar tertaut sendiri, Anda juga dapat mempertimbangkan untuk menggunakan std::list<InnerNode*> flights; atau bahkan anggota std::vector<InnerNode*> flights; di OuterNode struct Anda.
Meskipun solusi ini perlu menangani instance InnerNode dengan benar, melalui manajemen memori, std::list<std::shared_ptr<InnerNode>> atau std::vector<std::shared_ptr<InnerNode>> sepertinya merupakan cara yang tepat.

person πάντα ῥεῖ    schedule 10.11.2014

arrow_upward
0
arrow_downward

Anda perlu menggunakan deklarasi maju.

Ketika kompiler hanya perlu mengetahui bahwa suatu tipe ada, tetapi tidak perlu mengetahui apa pun tentang definisinya (seperti ketika Anda mendeklarasikan sebuah pointer), Anda dapat menggunakan deklarasi penerusan untuk memberi tahu kompiler 'suatu tipe dengan nama ini ada':

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

Ini akan dikompilasi, karena InnerList tidak perlu mengetahui apa pun tentang InnerNode; ia hanya perlu mengetahui bahwa tipe bernama InnerNode ada.

Jika Anda memiliki instance sebenarnya dari suatu tipe di kelas Anda, seperti halnya OuterNode, deklarasi penerusan tidak akan berfungsi. Kelas harus mengetahui berapa banyak penyimpanan yang akan dialokasikan untuk tipe tersebut, sehingga memerlukan definisi lengkap.

Anda dapat menggunakan deklarasi penerusan untuk mengkompilasi InnerList dan InnerNode, tetapi Anda harus memindahkan definisi OuterNode ke setelah InnerList, karena definisi tersebut bergantung pada definisinya.

person Collin Dauphinee    schedule 10.11.2014