异质链表入门

参考文章 最简单的异质链表---链表中存放不同类型的对象/结点

前言

最近C++实验课要求做一个图书馆, 里面有多种类型的物品需要使用链表来存储, 然后便想要知道如何使用链表存储不同类型的数据, 于是上网搜索, 就看到了上面的文章, 从而了解到了异质链表这个概念.

简介

异质链表主要是在普通链表的基础上, 添加了一个类型信息和一个指向对应类型地址的指针, 从而实现一个链表可以存储多种类型的数据

C语言版

#include <stdio.h>

struct Type1 {
    int x;
};
struct Type2 {
    int x;
    int y;
};
struct Type3 {
    int x;
    int y;
    int z;
};
typedef enum {
    ErrorID = -1,
    Type1 = 1,
    Type2,
    Type3
}ObjectID;
typedef struct Node {
    ObjectID id;
    void* p;
    struct Node* next;
}Node;
int main(void)
{
    struct Type1 t11, t12;
    t11.x = 11;
    t12.x = 12;
    struct Type2 t21, t22;
    t21.x = 21;
    t21.y = 210;
    t22.x = 22;
    t22.y = 220;
    struct Type3 t31, t32;
    t31.x = 31;
    t31.y = 310;
    t31.z = 311;
    t32.x = 32;
    t32.y = 320;
    t32.z = 321;
    Node n;
    Node *head = &n;
    head->id = ErrorID;
    head->p = NULL;
    head->next = NULL;
    Node node1, node2, node3;
    node1.id = Type1;
    node1.p = &t11;
    node2.id = Type2;
    node2.p = &t21;
    node3.id = Type3;
    node3.p = &t31;
    head->next = &node1;
    node1.next = &node2;
    node2.next = &node3;
    node3.next = NULL;
    
    struct Type1 *p1 = NULL;
    struct Type2 *p2 = NULL;
    struct Type3 *p3 = NULL;
    
    Node* ptr;
    for (ptr = head; ptr != NULL; ptr = ptr->next)
    {
        switch(ptr->id)
        {
            case Type1:
                p1 = (struct Type1 *) ptr->p;
                printf("x = %d\n", p1->x);
                break;
            case Type2:
                p2 = (struct Type2 *) ptr->p;
                printf("x = %d, y = %d\n", p2->x, p2->y);
                break;
            case Type3:
                p3 = (struct Type3 *) ptr->p;
                printf("x = %d, y = %d, z = %d\n", p3->x, p3->y, p3->z);
                break;
            default:
                break;
        }
    }
    printf("1");
}

C++版

#include <iostream>
#include <string>

using namespace std;

class Phone {
    public:
        Phone(string brand = "OPPO") {this->brand = brand;}
        void display() {cout << "Phone brand : " << brand << endl;}
    private:
        string brand;
};
class Book {
    public:
        Book(string name = "English") {this->name = name;}
        void display() {cout << "Book name : " << name << endl;}
    private:
        string name;
};
typedef enum {
    ErrorID = -1,
    PhoneID = 1,
    BookID = 2
}ClassID;
class Node {
    public: 
        ClassID id;
        void *p;
        Node* next;
};

int main() {
    Phone phone1("vivo");
    Book book1("Chinese");
    Node node1, node2, node3;
    
    Node *head = &node1;
    head->id = ErrorID;
    head->p = NULL;
    head->next = &node2;
    node2.id = PhoneID;
    node2.p = &phone1;
    node2.next = &node3;
    node3.id = BookID;
    node3.p = &book1;
    node3.next = NULL;
    
    Phone* ptrPhone = NULL;
    Book* ptrBook = NULL;
    Node* ptr = NULL;
    for (ptr = head; ptr != NULL; ptr = ptr->next)
    {
        switch (ptr->id)
        {
            case PhoneID:
                ptrPhone = (Phone *) ptr->p;
                ptrPhone->display();
                break;
            case BookID:
                ptrBook = (Book *) ptr->p;
                ptrBook->display();
                break;
            default:
                break;
        }
    }
    cout << 1 << endl;
}