Ist es möglich, eine verknüpfte Liste verschiedener Datentypen zu haben?

Question

Dies ist nur eine weitere Interviewfrage.

Können wir eine verknüpfte Liste verschiedener Datentypen haben, d. H. Jedes Element in einer verknüpften Liste kann verschiedene Struktur- oder Vereinigungselemente haben? Wenn es möglich ist, können Sie das bitte mit einem Beispiel erklären?

Answer 1

Sie können für jeden Knoten in einer verknüpften Liste ein void * angeben, das auf Ihre Daten verweist. Es hängt von Ihnen ab, wie Sie bestimmen, auf welche Art von Daten der Zeiger zeigt.

Answer 2

Verwenden Vereinigung der Datentyp

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

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

Verwenden struct Knoten erstellen verknüpfte Liste zu erstellen. Typ entscheidet, was der Datentyp der Daten ist.

Harsha T, Bangalore

Answer 3

Well in einer verknüpften Liste Sie haben nicht wie zusammen wie structs zu verknüpfen. Solange sie die entsprechenden Vorwärts- und/oder Rückwärtszeiger haben, geht es Ihnen gut. Zum Beispiel:

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

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

struct IntLink 
{ 
    BaseLink baseLink; 
    int nInt; 
}; 

Auf diese Weise würden Sie eine verkettete Liste, die von BaseLink zu BaseLink geht. Die zusätzlichen Daten sind kein Problem. Sie möchten es als StringLink sehen? Dann werfen Sie den BaseLink auf einen StringLink.

Denken Sie nur daran, dass Sie eine Form von Typid benötigen, damit Sie wissen, worauf Sie es bei Ihrer Ankunft anwenden müssen.

Answer 4

Wie gesagt, Sie können einen Knoten diese Frage mit einem void * haben. Ich schlage vor, mit etwas über Ihre Art wissen:

typedef struct 
{ 
    /* linked list stuff here */  

    char m_type; 
    void* m_data; 
} 
Node; 

this question See.

Answer 5

Eigentlich müssen Sie den Zeiger nicht zuerst in die Struktur einfügen, Sie können ihn irgendwo platzieren und dann den Anfang der Struktur mit einem containerof() - Makro finden. Der Linux-Kernel tut dies mit seinen verknüpften Listen.

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

Answer 6

Nur ein FYI, In C# können Sie Object als Datenelement verwenden.

class Node 
{ 
    Node next; 
    Object Data; 
} 

Der Benutzer kann dann so etwas wie diese verwenden, um herauszufinden, welche Object die Node Läden:

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

} 

Answer 7

Sie können eine Vereinigung Typ verwenden:

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

Eine andere Methode, die ich untersucht habe ist, ein void * für die Daten zu verwenden und Zeiger an Funktionen anzuhängen, die das typbewusste Zeug verarbeiten:

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

Offensichtlich habe ich einige Fehlerprüfung und Handhabung von Code aus diesem Beispiel weggelassen, und ich bezweifle nicht, dass es eine Menge Probleme gibt, aber es sollte illustrativ sein.

Answer 8

Ich benutze diese Makros, die ich schrieb, um allgemeine verkettete Listen zu machen.Sie erstellen einfach Ihre eigene Struktur und verwenden das Makro list_link irgendwo als Mitglied der Struktur. Geben Sie diesem Makro ein Argument mit der Struktur (ohne das Schlüsselwort struct). Dies implementiert eine doppelt verknüpfte Liste ohne einen Dummy-Knoten (z. B. der letzte Knoten verbindet sich zurück mit dem ersten Knoten). Der Anker ist ein Zeiger auf den ersten Knoten, der mit list_init(anchor) initialisiert wird, indem er ihm den Wert lvalue gibt (ein dereferenzierter Zeiger darauf ist ein lvalue). Dann können Sie die anderen Makros in der Kopfzeile verwenden. Lesen Sie die Quelle für Kommentare zu den verfügbaren Makrofunktionen. Dies ist zu 100% in Makros implementiert.

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

Answer 9

Wenn Sie wollen nicht die Art von jedem Knoten in der Liste über die Vereinigung Lösung müssen angeben, können Sie immer nur speichern die Daten in einem char * und nehmen typspezifische Funktionszeiger als Parameter für typensensitive Operationen wie Drucken oder Sortieren der Liste. Auf diese Weise brauchen Sie sich keine Gedanken darüber zu machen, welcher Knoten welcher Typ ist, und können die Daten einfach so darstellen, wie Sie möchten.

/* 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

Ja, ich tue dies, indem die Liste des Elements Wert als void-Zeigervoid* definieren. Um den Typ zu kennen, der in jedem Element der Liste gespeichert ist, habe ich auch ein .type Feld, so dass ich weiß, wie dereferenziert wird, worauf der Zeiger für jedes Element zeigt.

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

Hier ist ein vollständiges Beispiel dafür:

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

Erwartete Ausgabe:

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