是否有任何结构的通用链表功能

Question

假设我的代码中有两个这样的结构：

typedef struct Food {
    char* name;
    int food_id;
    int price;
    int capacity;
    int hall_id;
    int day;
    int reserved;
    int profit;
    Food* next;
} Food;

typedef struct Coupon {
    int id;
    int percentage;
    int capacity;
    Coupon* next;
} Coupon;

而且我想用他们实现一个链表数据结构。例如，我有一个 Food* 变量，它指向食物编号 1，然后 next 中的食物编号 2 指向下一个食物，然后...

问题是当我想为链表编写函数时，我必须为每个作业编写 2 个函数。例如，我想要一个函数来获取列表的头部和一个新元素，然后将新元素添加到列表中。因为这两个链表的类型不一样，所以我想不出一个办法，都只写一个函数。有办法吗？

例如，我想让这个函数适用于所有类型：

void add_front(Coupon* head, Coupon* new_el){
    while (head->next != NULL){
        head = head->next;
    }
    head->next = new_el;
    new_el->next = NULL;
}

Answer 1

你可以使用宏:

来自我的个人项目之一

#if !defined(CIRCULAR_DOUBLE_LINKED_LIST_H)
#define CIRCULAR_DOUBLE_LINKED_LIST_H

//T must include ->prev and ->next member
#define DECLARE_NAMED_CIRCULAR_DOUBLE_LINKED_LIST(T, name)  \
  static inline T* name ## _add_after(T* source, T* item) { \
    T* last_next = source->next;                            \
    source->next = item;                                    \
    item->prev = source;                                    \
    item->next = last_next;                                 \
    last_next->prev = item;                                 \
    return source;                                          \
  }                                                         \
  static inline T* name ## _add_before(T* source, T* item) {\
    T* last_prev = source->prev;                            \
    source->prev = item;                                    \
    item->next = source;                                    \
    item->prev = last_prev;                                 \
    last_prev->next = item;                                 \
    return source;                                          \
  }                                                         \
  static inline T*  name ## _remove(T* item) {              \
    T* next = item->next;                                   \
    item->prev->next = item->next;                          \
    item->next->prev = item->prev;                          \
    return next == item ? NULL : next;                      \
  }

#define DECLARE_CIRCULAR_DOUBLE_LINKED_LIST(T) DECLARE_NAMED_CIRCULAR_DOUBLE_LINKED_LIST(T, list_ ## T)

#endif // CIRCULAR_DOUBLE_LINKED_LIST_H

typedef struct Food {
    Food* next;
    Food* prev;
    char* name;
    int food_id;
    int price;
    int capacity;
    int hall_id;
    int day;
    int reserved;
    int profit;
} Food;

DECLARE_CIRCULAR_DOUBLE_LINKED_LIST(Food)

list_Food_add_after(Food*, Food*);
list_Food_add_before(Food*, Food*);
list_Food_remove(Food*);

Answer 2

首先，您将每个条目的域数据与管理数据分开。

typedef struct {
    char* name;
    int food_id;
    int price;
    int capacity;
    int hall_id;
    int day;
    int reserved;
    int profit;
} Food;

typedef struct {
    int id;
    int percentage;
    int capacity;
} Coupon;

然后您可以使用带有指针的联合指向条目结构中的域数据。每个条目的大小相同。

typedef struct Entry {
    struct Entry* next;
    union {
        Food* food;
        Coupon* coupon;
    } data;
} Entry;

您甚至可以将域数据直接放在联合中，但如果只存储小尺寸的值，这将浪费内存。

typedef struct Entry {
    struct Entry* next;
    union {
        Food food;
        Coupon coupon;
    } data;
} Entry;

现在您可以使用通用函数添加不同数据的新条目。

void add_front(Entry* head, Entry* new_el) {
    while (head->next != NULL){
        head = head->next;
    }
    head->next = new_el;
    new_el->next = NULL;
}

Answer 3

一个可能的技巧是利用以下事实：将指向结构的指针转换为指向其初始成员的指针是合法的，并且从任何指针类型转换为 void * 并返回都是合法的。因此，如果 next 是第一个成员，许多函数可以独立于实际的 class，如果它们为第一个元素是 [=12] 的任何结构采用 void * 参数=] 指针。当然，应该提供能够处理真实对象的辅助函数...

这是一个示例代码，显示了 add_before、add_after、list_remove（remove 在 stdio.h 中定义）和 display 并显示了与 Coupon 对象一起使用的示例：

#include <stdio.h>

typedef struct Food {
    struct Food* next;
    char* name;
    int food_id;
    int price;
    int capacity;
    int hall_id;
    int day;
    int reserved;
    int profit;
} Food;

typedef struct Coupon {
    struct Coupon* next;
    int id;
    int percentage;
    int capacity;
} Coupon;

void* add_before(void* list, void* elem) {
    *(void **)elem = list;
    return elem;
}

void* add_after(void* list, void* elem) {
    if (NULL == list) return elem;
    void** last = list;
    while (*last != NULL) {
        last = *last;
    }
    *last = elem;
    return list;
}

// eltdisplay is a pointer to a function able to display an element
void display(void* list, void (*eltdisplay)(void*, FILE *), FILE *out) {
    while (NULL != list) {
        eltdisplay(list, out);
        if (NULL != *(void **)list) {
            fprintf(out, " -> ");
        }
        list = *(void **)list;
    }
    fprintf(out, "\n");
}

void* list_remove(void* list, void* elem, int(*comp)(void* elt1, void* elt2)) {
    if (list == NULL) return NULL;
    void** cur = list, **old = NULL;
    while (cur != NULL) {
        if (0 == comp(cur, elem)) {
            if (old == NULL) return *cur;
            *old = *cur;
            break;
        }
        old = cur;
        cur = *cur;
    }
    return list;
}

int couponcomp(void* elt1, void* elt2) {
    return ((Coupon*)elt1)->id != ((Coupon*)elt2)->id;
}

void coupondisplay(void* elt, FILE *out) {
    Coupon* coupon = elt;
    fprintf(out, "%d", coupon->id);

}
int main() {
    Coupon data[3] = { {NULL, 1}, {NULL, 2}, {NULL, 3} };
    Coupon* list = NULL;
    for (int i = 0; i < sizeof(data) / sizeof(*data); i++) {
        list = addLast(list, data+i);
    }
    display(list, coupondisplay, stdout);
    Coupon data2 = { NULL, 2 };
    list = list_remove(list, &data2, couponcomp);
    display(list, coupondisplay, stdout);
    return 0;
}

它在没有警告的情况下编译并按预期显示：

1 -> 2 -> 3
1 -> 3

Answer 4

我认为我在 C 中找到的最好的方法（即没有模板）是：

制作一个 SinglyLinkedNode class 刚好有 SinglyLinkedNode *next
根据这个 class 编写列表函数 -- 每个列表都是 SinglyLinkedNode
将 SinglyLinkedNode node 字段添加到 Food 和 Coupon，并将其用于 link 它们。
另外提供函数或宏来从 SinglyLinkedNode 指针获取包含 Food 或 Coupon 的指针，例如 Coupon *couponFromNode(Node *p);

请注意，我永远不会对单linked 列表执行此操作，因为单linked 列表操作很容易编写，您实际上不需要列表方法。这种技术开始对双重 linked 列表或更复杂的内省容器有用。

是否有任何结构的通用链表功能

Is there a generic linked list functionality for any structure

c

algorithm

data-structures