C удваивают связанный список с абстрактным типом данных

Есть несколько подходов, которые вы можете использовать, один из которых предполагает сохранение void * в вашем ADT.

Я всегда считал, что это немного неудобно для связанного списка, поскольку вам нужно управлять его распределением отдельно от самого списка. Другими словами, чтобы выделить узел, вам необходимо выделить как узел, так и его полезную нагрузку отдельно (и не забудьте также очистить их при удалении).

Один из подходов, который я использовал в прошлом, - иметь структуру «переменного размера», например:

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    char payload[1];
} tNode;

Теперь это не выглядит переменным размером, но давайте разместим структуру таким образом:

typedef struct {
    char Name[30];
    char Addr[50];
    char Phone[20];
} tPerson;
tNode *node = malloc (sizeof (tNode) - 1 + sizeof (tPerson));

Теперь у вас есть узел, который для всех целей и задач выглядит так:

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    char Name[30];
    char Addr[50];
    char Phone[20];
} tNode;

или, в графической форме (где [n] означает n байт):

+------------+
| prev[4]    |
+------------+
| next[4]    |
+------------+ +-----------+
| payload[1] | | Name[30]  | <- overlap
+------------+ +-----------+
               | Addr[50]  |
               +-----------+
               | Phone[20] |
               +-----------+

То есть, если вы знаете, как правильно адресовать полезную нагрузку. Это можно сделать следующим образом:

node->prev = NULL;
node->next = NULL;
tPerson *person = &(node->payload); // cast for easy changes to payload.
strcpy (person->Name, "Richard Cranium");
strcpy (person->Addr, "10 Smith St");
strcpy (person->Phone, "555-5555");

Эта строка преобразования просто преобразует адрес символа полезной нагрузки (в типе tNode ) в адрес фактического tPerson тип полезной нагрузки.

Используя этот метод, вы можете переносить любой тип полезной нагрузки в узле, даже разные типы полезной нагрузки в каждом узле , если вы сделаете структуру более похожей на:

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    int payloadType;       // Allows different payload type at each node.
    char payload[1];
} tNode;

и используете payloadType для хранения индикатора фактической полезной нагрузки.

У этого есть преимущество перед объединением в том, что он не тратит впустую пространство, что можно увидеть из следующего:

union {
    int fourBytes;
    char oneHundredBytes[100];
} u;

где 96 байт тратятся впустую каждый раз, когда вы сохраняете целочисленный тип в списке (для 4- байт целое).

Тип полезной нагрузки в tNode позволяет вам легко определять, какой тип полезной нагрузки несет этот узел, поэтому ваш код может решить, как ее обрабатывать. Вы можете использовать что-то вроде:

#define PAYLOAD_UNKNOWN     0
#define PAYLOAD_MANAGER     1
#define PAYLOAD_EMPLOYEE    2
#define PAYLOAD_CONTRACTOR  3

или (возможно, лучше):

typedef enum {
    PAYLOAD_UNKNOWN,
    PAYLOAD_MANAGER,
    PAYLOAD_EMPLOYEE,
    PAYLOAD_CONTRACTOR
} tPayLoad;

Единственное, на что вам нужно обратить внимание, это убедиться, что выравнивание полезной нагрузки правильное. Поскольку и мой заполнитель полезной нагрузки, и полезная нагрузка относятся к типам char , это не проблема. Однако, если ваша полезная нагрузка состоит из типов с более строгими требованиями к выравниванию (например, что-то более строгое, чем указатели, вам может потребоваться отрегулировать это).

Хотя я никогда не видел среды с более строгим выравниванием, чем указатели, это возможно в соответствии со стандартом ISO C.

Обычно вы можете получить требуемое выравнивание, просто используя тип данных для заполнителя полезной нагрузки, который имеет самые строгие требования к выравниванию, такие как:

long payload;

Оглядываясь назад, мне кажется, что вам, вероятно, не нужен массив как заполнитель полезной нагрузки. Достаточно просто иметь что-то, адрес которого можно взять. Я подозреваю, что эта конкретная моя идиома восходит к тем временам, когда я просто хранил массив символов (а не структуру) и напрямую ссылался на них. В этом случае вы можете использовать payload [] отдельно без преобразования к другому типу.