C與抽象數據類型的雙重鏈接列表

Question

我需要C中的雙鏈表，但它必須針對不同的類型。在C++中，我們使用模板。我在哪裏可以找到C中的例子與抽象類型項目的雙鏈表。

謝謝

Answer 1

您可以採取幾種方法，其中之一涉及在您的ADT中存儲void*。

我一直髮現這在鏈表中有點痛苦，因爲你必須將它的分配單獨管理到列表本身。換句話說，爲了分配一個節點，你需要分別分配節點和它的有效載荷（並且記得在刪除時也清理它們）。我已經在過去使用

一種方法是有一個像「可變大小的」結構：

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[]而不用轉換爲其他類型。

Answer 2

用C處理任意的數據通常是通過使用指針完成的 - 在大多數情況下，特別是void *。

Answer 3

C語言中最接近於「對象」基類或模板類型的指針是void指針。 A void *表示一個指向某個東西的指針，但它沒有指定正在指向什麼類型的數據。如果你想訪問數據，你需要使用一個強制轉換。

雙向鏈表節點可以是這樣的：

struct DoubleLinkedListNode { 
    struct DoubleLinkedListNode *previous, *next; 
    void *data; 
}; 

要分配節點的字符串，例如，你可以這樣做：

char myString[80] = "hello, world"; 
struct DoubleLinkedListNode myNode; 
myNode.data = myString; 

從節點獲取字符串返回，您使用演員表：

char *string = (char *)myNode.data; 
puts(string); 

要存儲非指針，您需要從數據中創建一個指針。對於結構體來說，如果它的生命週期足夠長，就可以簡單地解引用實例（類似於上面的例子）。如果不是，或者您正在處理的是原始類型（例如int或float），則需要malloc一些空間。只要確保在完成後釋放內存。

Answer 4

你可以使用宏演示here（這個特殊的例子實現了通用的散列表）。

Answer 5

顯然，linux內核在內核本身和許多設備驅動模塊中的許多地方使用鏈表。幾乎所有這些都是使用與linux/list.h中定義的相同的一組宏來實現的。

請參見http://isis.poly.edu/kulesh/stuff/src/klist/或http://kernelnewbies.org/FAQ/LinkedLists以獲得很好的解釋。

這些宏起初看起來有點奇怪，但很容易使用，並很快成爲第二性質。它們可以適用於用戶空間（請參閱list.h）。