是否有任何結構的通用鏈表功能-有解無憂

假設我的代碼中有兩個結構，如下所示：

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，然后食物編號 2next指向下一個食物，然后......

問題是當我想為鏈表撰寫函式時，我必須為每個作業撰寫 2 個函式。例如，我想要一個函式來獲取串列的頭部和一個新元素，然后將新元素添加到串列中。因為這兩個鏈表的型別不同，所以我想不出一種只為兩者寫一個函式的方法。有沒有辦法這樣做？

例如，我想讓這個函式適用于所有型別：

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

uj5u.com熱心網友回復：

首先，您將每個條目的域資料與管理資料分開。

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

uj5u.com熱心網友回復：

一個可能的技巧是利用以下事實：將指向結構的指標轉換為指向其初始成員的指標是合法的，并且從任何指標型別轉換為 void * 并回傳也是合法的。因此，提供next了第一個成員，許多函式可以獨立于實際類，如果它們void *為第一個元素是next指標的任何結構獲取引數。當然，應該提供能夠處理真實物件的輔助功能......

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

uj5u.com熱心網友回復：

您可以使用宏：

來自我的個人專案之一

#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*);

uj5u.com熱心網友回復：

我認為我在 C 中發現的最好的方法（即，沒有模板）是：

制作一個SinglyLinkedNode剛剛擁有的課程SinglyLinkedNode *next
基于這個類撰寫你的串列函式——每個串列都是一個串列 SinglyLinkedNode
將SinglyLinkedNode node欄位添加到Food和Coupon，并使用它將它們鏈接在一起。
另外提供函式或宏以從指標中獲取包含Food或指標，例如CouponSinglyLinkedNodeCoupon *couponFromNode(Node *p);

請注意，我實際上永遠不會對單鏈表執行此操作，因為單鏈表操作非常容易撰寫，以至于您實際上不需要串列方法。這種技術開始對雙向鏈表或更復雜的內省容器有用。

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/417152.html

標籤：

上一篇：OpenSSLAES_ecb_encrypt填充選項？

下一篇：__declspec(dllimport)extern"C"和extern"C"__declspec(dllimport)有什么區別