Czy istnieje możliwość powiązania listy różnych typów danych?

Question

To kolejne pytanie do wywiadu.

Czy możemy mieć połączoną listę różnych typów danych, tj. Każdy element na połączonej liście może mieć inną strukturę lub elementy złączne? Jeśli to możliwe, czy możesz wyjaśnić na przykładzie?

Answer 1

Możesz mieć każdy węzeł na liście połączonej ma pustkę *, która wskazuje Twoje dane. Od Ciebie zależy, w jaki sposób określisz typ danych wskazywanych przez wskaźnik.

Answer 2

Zastosowanie unia stworzyć typ danych

union u_tag{ 
    char ch; 
    int d; 
    double dl; 
}; 

struct node { 
    char type; 
    union u_tag u; 
    struct node *next; 
}; 

węzeł Zastosowanie struct do stworzenia połączonej listy. typ decyduje o typie danych.

Harsha T, Bangalore

Answer 3

Dobrze w połączonej listy nie trzeba powiązać jak dla podobnych strukturach razem. Dopóki mają odpowiednie wskaźniki do przodu i/lub do tyłu, jesteś w porządku. Na przykład:

struct BaseLink 
{ 
    BaseLink* pNext; 
    BaseLink* pPrev; 
    int  typeId; 
}; 

struct StringLink 
{ 
    BaseLink baseLink; 
    char* pString; 
}; 

struct IntLink 
{ 
    BaseLink baseLink; 
    int nInt; 
}; 

W ten sposób będziesz mieć połączoną listę, która przechodzi od BaseLink do BaseLink. Dodatkowe dane nie stanowią problemu. Chcesz go zobaczyć jako StringLink? Następnie odrzuć BaseLink do StringLink.

Po prostu pamiętaj, że potrzebujesz jakiejś formy typu, abyś wiedział, do czego ją przesłać po dotarciu na miejsce.

Answer 4

Tak jak powiedziałeś, możesz mieć węzeł to pytanie z pustką *. Proponuję za pomocą coś wiedzieć o swoim rodzaju:

typedef struct 
{ 
    /* linked list stuff here */  

    char m_type; 
    void* m_data; 
} 
Node; 

Zobacz this question.

Answer 5

W rzeczywistości nie trzeba umieszczać wskaźnika w strukturze, można go umieścić w dowolnym miejscu, a następnie znaleźć początek dla struktury za pomocą makra containerof(). Jądro Linuksa robi to z powiązanymi listami.

http://isis.poly.edu/kulesh/stuff/src/klist/

Answer 6

Po prostu FYI, W języku C# można użyć Object jako członka danych.

class Node 
{ 
    Node next; 
    Object Data; 
} 

Użytkownik może następnie użyć czegoś takiego, aby dowiedzieć się, które Object z Node Sklepy:

if (obj.GetType() == this.GetType()) // 
{ 

} 

Answer 7

można użyć Union Typ:

enum type_tag {INT_TYPE, DOUBLE_TYPE, STRING_TYPE, R1_TYPE, R2_TYPE, ...}; 
struct node { 
    union { 
    int ival; 
    double dval; 
    char *sval; 
    struct recordType1 r1val; 
    struct recordType2 r2val; 
    ... 
    } data; 
    enum type_tag dataType; 
    struct node *prev; 
    struct node *next; 
}; 

Innym sposobem mam zbadane należy użyć pustej przestrzeni * dla danych i dołączyć wskaźniki do funkcji, które obsługują elementy świadome typów:

/** 
* Define a key type for indexing and searching 
*/ 
typedef ... key_t;     

/** 
* Define the list node type 
*/ 
struct node { 
    void *data; 
    struct node *prev; 
    struct node *next; 
    void *(*cpy)(void *);   // make a deep copy of the data 
    void (*del)(void *);    // delete the data 
    char *(*dpy)(void *);   // format the data for display as a string 
    int (*match)(void *, key_t);  // match against a key value 
}; 

/** 
* Define functions for handling a specific data type 
*/ 
void *copyARecordType(void *data) 
{ 
    struct aRecordType v = *(struct aRecordType *) data; 
    struct aRecordType *new = malloc(sizeof *new); 
    if (new) 
    { 
    // copy elements of v to new 
    } 
    return new; 
} 

void deleteARecordType(void *data) {...} 
char *displayARecordType(void *data) {...} 
int matchARecordType(void *data, key_t key) {...} 

/** 
* Define functions for handling a different type 
*/ 
void *copyADifferentRecordType(void *data) {...} 
void deleteADifferentRecordType(void *data) {...} 
char *displayADifferentRecordType(void *data) {...} 
int matchADifferentRecordType(void *data, key_t key) {...} 

/** 
* Function for creating new list nodes 
*/ 
struct node *createNode(void *data, void *(*cpy)(void *), void (*del)(void *), 
    char *(*dpy)(void *), int (*match)(void *, key_t)) 
{ 
    struct node *new = malloc(sizeof *new); 
    if (new) 
    { 
    new->cpy = cpy; 
    new->del = del; 
    new->dpy = dpy; 
    new->match = match; 
    new->data = new->cpy(data); 
    new->prev = new->next = NULL; 
    } 
    return new; 
} 

/** 
* Function for deleting list nodes 
*/ 
void deleteNode(struct node *p) 
{ 
    if (p) 
    p->del(p->data); 
    free(p); 
} 

/** 
* Add new node to the list; for this example, we just add to the end 
* as in a FIFO queue. 
*/ 
void addNode(struct node *head, void *data, void *(*cpy)(void*), 
    void (*del)(void *), char *(*dpy)(void *), int (*match)(void*, key_t)) 
{ 
    struct node *new = createNode(data, cpy, del, dpy, match); 
    if (!head->next) 
    head->next = new; 
    else 
    { 
    struct node *cur = head->next; 
    while (cur->next != NULL) 
     cur = cur->next; 
    cur->next = new; 
    new->prev = cur; 
    } 
} 

/** 
* Examples of how all of this would be used. 
*/ 
int main(void) 
{ 
    struct aRecordType r1 = {...}; 
    struct aDifferentRecordType r2 = {...}; 

    struct node list, *p; 
    addNode(&list, &r1, copyARecordType, deleteARecordType, displayARecordType, 
    matchARecordType); 
    addNode(&list, &r2, copyADifferentRecordType, deleteADifferentRecordType, 
    displayADifferentRecordType, matchADifferentRecordType); 
    p = list.next; 
    while (p) 
    { 
    printf("Data at node %p: %s\n", (void*) p, p->dpy(p->data)); 
    p = p->next; 
    } 
    return 0; 
} 

Oczywiście, w tym przykładzie pominięto kod sprawdzania i obsługi błędów i nie wątpię, że jest z nim wiele problemów, ale powinno być to ilustracja.

Answer 8

Używam tych makr, które napisałem, aby tworzyć ogólne listy.Po prostu utwórz własną strukturę i użyj makra list_link gdzieś jako członka struktury. Podaj makro jeden argument nazwany struct (bez słowa kluczowego struct). To implementuje podwójnie połączoną listę bez węzła fikcyjnego (na przykład ostatni węzeł łączy się z powrotem do pierwszego węzła). Zakotwiczenie jest wskaźnikiem do pierwszego węzła, który rozpoczyna się od zainicjowania przez list_init(anchor) przez nadanie mu wartości l (wskazanie odwołanego do niej jest l-wartością). Następnie możesz użyć innych makr w nagłówku. Przeczytaj źródło komentarzy do każdej dostępnej funkcji makra. Jest to zaimplementowane w 100% w makrach.

http://phil.ipal.org/pre-release/list-0.0.5.tar.bz2

Answer 9

Jeśli nie chcesz mieć, aby określić typ każdego węzła na liście poprzez rozwiązania unii zawsze można po prostu przechowywać dane w char * i wziąć typu specyficzne wskaźniki funkcyjne jak parametry do operacji wrażliwych na typ, takich jak drukowanie lub sortowanie listy. W ten sposób nie musisz się martwić, jaki węzeł jest typu i możesz po prostu przesyłać dane według własnego uznania.

/* data types */ 

typedef struct list_node list_node; 
struct list_node { 
    char *data; 
    list_node *next; 
    list_node *prev; 
}; 

typedef struct list list; 
struct list { 
    list_node *head; 
    list_node *tail; 
    size_t size; 
}; 

/* type sensitive functions */ 

int list_sort(list *l, int (*compar)(const void*, const void*)); 
int list_print(list *l, void (*print)(char *data)); 

Answer 10

Tak, robię to poprzez zdefiniowanie wartości listy za elementu jako void wskaźnikvoid*. Aby poznać typ zapisany w każdym elemencie listy, mam tam również pole .type, dzięki czemu wiem, jak wyłuskać wskazanie wskaźnika dla każdego elementu.

struct node { 
    struct node* next; 
    int type; 
    void* value; 
}; 

Oto pełna przykładem:

//                                               
// An exercise to play with a struct that stores anything using a void* field.                            
//                                               

#include <stdio.h> 

#define TRUE 1 

int TYPE_INT = 0; 
int TYPE_STRING = 1; 
int TYPE_BOOLEAN = 2; 
int TYPE_PERSON = 3; 

struct node { 
    struct node* next; 
    int type; 
    void* value; 
}; 

struct person { 
    char* name; 
    int age; 
}; 

int main(int args, char **argv) { 

    struct person aPerson; 
    aPerson.name = "Angel"; 
    aPerson.age = 35; 

    // Define a linked list of objects.                                      
    // We use that .type field to know what we're dealing                                  
    // with on every iteration. On .value we store our values.                                 
    struct node nodes[] = { 
    { .next = &nodes[1], .type = TYPE_INT , .value=1     }, 
    { .next = &nodes[2], .type = TYPE_STRING , .value="anyfing, anyfing!" }, 
    { .next = &nodes[3], .type = TYPE_PERSON , .value=&aPerson   }, 
    { .next = NULL  , .type = TYPE_BOOLEAN, .value=TRUE    } 
    }; 

    // We iterate through the list                                        
    for (struct node *currentNode = &nodes[0]; currentNode; currentNode = currentNode->next) { 
    int currentType = (*currentNode).type; 
    if (currentType == TYPE_INT) { 
     printf("%s: %d\n", "- INTEGER", (*currentNode).value); // just playing with syntax, same as currentNode->value                   
    } else if (currentType == TYPE_STRING) { 
     printf("%s: %s\n", "- STRING", currentNode->value); 
    } else if (currentType == TYPE_BOOLEAN) { 
     printf("%s: %d\n", "- BOOLEAN (true:1, false:0)", currentNode->value); 
    } else if (currentType == TYPE_PERSON) { 
     // since we're using void*, we end up with a pointer to struct person, which we *dereference                       
     // into a struct in the stack.                                      
     struct person currentPerson = *(struct person*) currentNode->value; 
     printf("%s: %s (%d)\n","- TYPE_PERSON", currentPerson.name, currentPerson.age); 
     } 
    } 

    return 0; 
} 

oczekiwany wynik:

- INTEGER: 1 
- STRING: anyfing, anyfing! 
- TYPE_PERSON: Angel (35) 
- BOOLEAN (true:1, false:0): 1