C中的模塊化數據結構，帶動態數據類型

Question

對於即將到來的大學C項目，我被要求擁有模塊化代碼，因爲C允許它。基本上，我會.c文件和一些數據結構的相應的.h文件中，就像一個鏈表，二叉樹，哈希表，無論...

使用鏈表作爲一個例子，我有這樣的：

typedef struct sLinkedList { 
    int value; 
    struct sLinkedList *next; 
} List; 

但是，這迫使value是int類型和使用該鏈表庫的用戶將被迫直接更改庫的源代碼。我想避免這種情況，我想避免需要更改庫，使代碼儘可能模塊化。

我的項目可能需要使用一個鏈表整數列表，或者一些結構的列表。但我不打算複製庫文件/代碼並相應地更改代碼。

我該如何解決這個問題？

Answer 1

不幸的是，沒有簡單的方法來解決這個問題。對於這種情況，最常見的純粹的C方法是使用void*，並將該值複製到您分配的內存中以存入指針。儘管如此，這使得使用非常棘手，而且非常容易出錯。

Answer 2

由於這是一個大學項目，我們不能只給你答案。相反，我會請你冥想兩個C特性：空指針（你可能遇到過），和token pasting operator（你可能沒有）。

Answer 3

您可以通過定義值void* value;避免這種情況。您可以通過這種方式爲任何類型的數據指定一個指針，但調用代碼需要將指針轉換爲正確類型並將其解引用。跟蹤這種情況的一種方法是將一個簡短的char數組添加到struct以記錄類型名稱。

Answer 4

這個問題正是爲什麼模板是爲C++開發的原因。我在C中使用過一次或兩次的方法是將值字段設置爲void *，並在插入時將值轉換並將其重新轉換爲檢索。當然，這遠不是類型安全的。爲了獲得額外的模塊性，我可能爲每個使用此類型的類型編寫insert_int（），get_mystruct（）等函數，並在那裏進行投射。

Answer 5

您可以使用Void *而不是int。這允許數據是任何類型的。但用戶應該知道數據的類型。

爲此，您可以選擇另一個表示Type的成員。這是枚舉{INT，CHAR，float ...}

Answer 6

另一個沒有人提到的替代方案可以在Linux內核的list.h通用鏈表實現中找到。其原理是這樣的：

/* generic definition */ 
struct list { 
    strict list *next, *prev; 
}; 

// some more code 

/* specific version */ 
struct intlist { 
    struct list list; 
    int i; 
}; 

如果您struct intlist*指針，他們可以放心地投（C語言）來struct list*指針，從而使您可以編寫在struct list*操作，不管有沒有數據類型的他們的工作泛型化功能。

list.h實現使用一些宏觀技巧來支持struct list在您的特定列表中的任意位置，但我更願意依靠自己的struct-cast-to-first-member技巧。它使調用代碼更容易閱讀。當然，它禁用「多重繼承」（假設你認爲這是某種繼承），但next(mylist)看起來比next(mylist, list)好看。另外，如果你可以避免深入研究offsetof，你可能會變得更好。

Answer 7

與C++不同的是，可以使用template,void *是事實上的C解決方案。

此外，您還可以把鏈表的元素在一個單獨的結構，e.g：

typedef struct sLinkedListElem { 
    int value; /* or "void * value" */ 
} ListElem; 

typedef struct sLinkedList { 
    ListElem data; 
    struct sLinkedList *next; 
} List; 

，這樣的元素可以在不影響鏈接-ING代碼進行更改。

Answer 8

這裏是鏈表公用事業C中的例子：

struct Single_List_Node 
{ 
    struct Single_List * p_next; 
    void *    p_data; 
}; 

struct Double_List_Node 
{ 
    struct Double_List * p_next; 
    struct Double_List * p_prev; // pointer to previous node 
    void *     p_data; 
}; 

struct Single_List_Data_Type 
{ 
    size_t       size; // Number of elements in list 
    struct Single_List_Node *  p_first_node; 
    struct Single_List_Node *  p_last_node; // To make appending faster. 
}; 

一些通用的功能：

void Single_List_Create(struct Single_List_Data_Type * p_list) 
{ 
    if (p_list) 
    { 
     p_list->size = 0; 
     p_list->first_node = 0; 
     p_list->last_node = p_list->first_node; 
    } 
    return; 
} 


void Single_List_Append(struct Single_List_Data_Type * p_list, 
          void *       p_data) 
{ 
    if (p_list) 
    { 
     struct Single_List_Node * p_new_node = malloc(sizeof(struct Single_List_Node)); 
     if (p_new_node) 
     { 
      p_new_node->p_data = p_data; 
      p_new_node->p_next = 0; 
      if (p_list->last_node) 
      { 
       p_list->last_node->p_next = p_new_node; 
      } 
      else 
      { 
       if (p_list->first_node == 0) 
       { 
        p_list->first_node = p_new_node; 
        p_list->last_node = p_new_node; 
       } 
       else 
       { 
        struct Single_List_Node * p_last_node = 0; 
        p_last_node = p_list->first_node; 
        while (p_last_node->p_next) 
        { 
         p_last_node = p_last_node->p_next; 
        } 
        p_list->last_node->p_next = p_new_node; 
        p_list->last_node = p_new_node; 
       } 
      } 
      ++(p_list->size); 
     } 
    } 
    return; 
} 

你可以把所有這些功能集成到一個單一的源文件和函數聲明成頭文件。這將允許您使用其他程序的功能，而不必一直重新編譯。指向數據的指針void *將允許您使用具有許多不同數據類型的列表。

（上面的代碼來作爲 - 是尚未與任何編譯器進行測試。bug修復的責任是高達的例子用戶）。