看到這個標題，你可能非常驚訝，C語言也能實現泛型鏈表?我們知道鏈表是我們非常常用的數據結構，但是在C中卻沒有像C++中的STL那樣有一個list的模板類，那么我們是否可以用C語言實現一個像STL中的list那樣的泛型鏈表呢?答案是肯定的。下面就以本人的一個用C語言設計的鏈表為例子，來分析說明一下本人的設計和實現要點，希望能給你一點有用的幫助。
 
 　　一、所用的鏈表類型的選擇
 
 　　我們知道，鏈表也有非常多的類型，包括單鏈表、單循環鏈表、雙鏈表、雙向循環鏈表等。在我的設計中，我的鏈表使用的類型是雙向循環鏈表，并帶一個不保存真實數據的頭結點。其原因如下：
 
 　　1)單鏈表由于不能從后繼定位到前驅，在操作時較為不方便
 
 　　2)雙鏈表雖然能方便找到前驅，但是如果總是在其尾部插入或刪除結點，為了定位的方便和操作的統一(所有的刪除和插入操作，都跟在中間插入刪除結點的操作一樣)，還要為其增加一個尾結點，并且程序還要保存一個指向這個尾結點的指針，并管理這個指針，從而增加程序的復雜性。而使用帶頭結點的循環雙向鏈表，就能方便的定位(其上一個元素為鏈表的最后一個元素，其下一個元素為鏈表的第0個元素)，并使所有的插入和刪除的操作統一，因為頭結點也是尾結點。注：結點的下標從0開始，頭結點不算入下標值。
 
 　　3)接口的使用與C++中stl中list和泛型算法的使用大致相同。
 
 　　二、list類型的定義
 
 　　為了讓大家一睹為快，下面就給出這個用C語言實現的“泛型”的定義，再來說明，我這樣設計的原因及要點，其定義如下：
 
 　　其定義在文件list_v2.c中
 
 　　typedef struct node
 
 　　{
 
 　　//循環雙鏈表的結點結構
 
 　　void* data;//數據域指針
 
 　　struct node *next;//指向當前結點的下一結點
 
 　　struct node *last;//指向當前結點的上一結點
 
 　　}Node;
 
 　　struct list
 
 　　{
 
 　　struct node *head;//頭指針，指向頭結點
 
 　　int data_size;//鏈表對應的數據所占內存的大小
 
 　　int length;//鏈表list的長度
 
 　　};
 
 　　其聲明在文件list_v2.h中
 
 　　//泛型循環雙鏈表，帶頭結點，結點下標從0開始，頭結點不計入下標值
 
 　　//定義結點指針Node*為List類型的迭代器
 
 　　typedef struct node* Iterator;
 
 　　//List類型的定義
 
 　　typedef struct list* List;
 
 　　//初始化鏈表,數據域所占內存的大小由data_size給出
 
 　　int InitList(List *list, int data_size);
 
 　　//把data的內容插入到鏈表list的末尾
 
 　　//assign指定數據data間的賦值方法
 
 　　Iterator Append(List list, void *data,
 
 　　void (*assign)(void*, const void*));
 
 　　//把data的內容插入到鏈表的迭代器it_before的前面
 
 　　//assign指定數據data間的賦值方法
 
 　　Iterator Insert(List list, void *data, Iterator it_before,
 
 　　void (*assign)(void*, const void*));
 
 　　//把鏈表A中迭代器it_a指向的結點移動到鏈表B中迭代器it_b_befroe的前面
 
 　　Iterator MoveFromAtoB(List A, Iterator it_a,
 
 　　List B, Iterator it_b_before);
 
 　　//刪除鏈表list中迭代器it指向的結點
 
 　　int Remove(List list, Iterator it);
 
 　　//刪除鏈表list的第0個結點，下標從0開始
 
 　　int RemoveFirst(List list);
 
 　　//刪除鏈表list的最后一個結點
 
 　　int RemoveLast(List list);
 
 　　//返回list中第index個數據的指針
 
 　　void* At(List list, int index);
 
 　　//在begin和end之間查找符合condition的第一個元素，
 
 　　//比較函數由condition指向,比較的值由data指向
 
 　　//當第一個參數的值小于第二個參數的值時，返回1，否則返回0
 
 　　//根據condition函數的不同，可以查找第一個相等、大于或小于data的值
 
 　　Iterator FindFirst(Iterator begin, Iterator end, void *data,
 
 　　int (*condition)(const void*, const void*));
 
 　　//查找list中第一個與data相等的元素的下標，
 
 　　//equal函數，當第一個參數與第二個參數的值相等時，返回1，否則返回0
 
 　　int IndexOf(List list, void *data,
 
 　　int (*equal)(const void*,const void*));
 
 　　//查找在begin和end之間的最小值，比較函數由less指向
 
 　　//當第一個參數的值小于第二個參數的值時，返回1，否則返回0
 
 　　Iterator GetMin(Iterator begin, Iterator end,
 
 　　int (*less)(const void*, const void*));
 
 　　//查找在begin和end之間的最大值，比較函數由large指向
 
 　　//當第一個參數的值大于第二個參數的值時，返回1，否則返回0
 
 　　Iterator GetMax(Iterator begin, Iterator end,
 
 　　int (*large)(const void*, const void*));
 
 　　//獲取list的長度
 
 　　int GetLength(List list);
 
 　　//若list為空鏈表，則返回1，否則返回0
 
 　　int IsEmpty(List list);
 
 　　//銷毀list
 
 　　void DestroyList(List *list);
 
 　　//獲得list的首迭代器
 
 　　Iterator Begin(List list);
 
 　　//獲得list的尾迭代器，指向最后一個元素的下一個位置
 
 　　Iterator End(List list);
 
 　　//使it指向下一個位置，并返回指向下一個位置后的迭代器
 
 　　Iterator Next(Iterator *it);
 
 　　//使it指向上一個位置，并返回指向上一個位置后的迭代器
 
 　　Iterator Last(Iterator *it);
 
 　　//通過迭代器it獲得數據，相當于*p
 
 　　void* GetData(Iterator it);
 
 　　//獲取當前迭代器的下一個迭代器，注意，并不改變當前迭代器
 
 　　Iterator GetNext(Iterator it);
 
 　　//獲取當前迭代器的上一個迭代器，注意，并不改變當前迭代器
 
 　　Iterator GetLast(Iterator it);
 
 　　為了更加清楚地表達這個鏈表的結構，下圖所示的，就是該鏈表的結構：
 
 　　調用InitList函數后，
 
 
 　　當向鏈表中插入一定數量的結點后，
 
 
 　　三、如何實現隱藏鏈表的成員變量(即封裝)
 
 　　首先，我們為什么需要封裝呢?我覺得封裝主要有三大好處。
 
 　　1)隔離變化，在程序中需要封裝的通常是程序中最容易發生變化的地方，例如成員變量等，我們可以把它們封裝起來，從而讓它們的變化不會影響到系統的其他部分，也就是說，封裝的是變化。
 
 　　2)降低復雜度，因為我們把一個對象是如何實現的等細節封裝起來，只留給用戶一個最小依賴的接口，從而讓系統變量簡單明了，在一定程度降低了系統的復雜性，方便了用戶的使用。
 
 　　3)讓用戶只能按照我們設計好的接口來操作一個對象或類型，而不能自己直接對一個對象進行操作，從而減少了用戶的誤操作，提高了系統的穩定性。
 
 　　在面向對象的設計中，如果我們想要隱藏一個類的成員變量，我們可以把這些成員變量聲明為私有的，而在C語言中，我們可以怎么實現呢?其實其實現是很簡單的，我們在C語言中，當我們要使用一個自己定義的類型或函數時，我們會把聲明它的頭文件包含(include)過來，只要我們在文件中只聲明其類型是一個結構體，而把它的實現寫在.c文件中即可。
 
 　　在本例子中，我把struct list和struct node定義在.c文件中，而在頭文件中，只聲明其指針類型，即typedef struct node* Iterator和typedef struct list* List;當我們要使用該類型時，只需要在所在的文件中，include該頭文件即可。因為在編譯時，編譯器只要知道List和Iterator是一個指針類型就能知道其所占的內存大小，也就能為其分配內存，所以能夠編譯成功。而又因為該頭文件中并沒有該類型(struct list和struct node)的定義，所以我們在使用該類型時，只能通過我們提供的接口來操作對象。例如，我們并不能使用List list; list->data等等的操作，而只能通過已定義的接口GetData來獲得。
 
 　　四、如何實現泛型
 
 　　泛型，第一時間想起的可能是模板，但是在C語言中卻沒有這個東西。但是C語言中卻有一個可以指向任何類型，在使用時，再根據具體的指針類型進行類型轉換的指針類型，它就是void*。
 
 　　為什么void*可以指向任何類型的數據?這還得從C語言對于數據類型的處理方式來說明。在C語言中，我們使用malloc等函數來申請內存，而從內存的角度來看，數據是沒有類型的，它們都是一串的0或1，而程序則根據不同的類型來解釋這個內存單元中的數據的意義，例如對于內存中的數據，FFFFFFFF，如果它是一個有符號整型數據，它代表的是-1，而如果它是一個無符號整型數據，它代表的則是2^32-1。進一步說，如果你用一個int的指針變量p指向該內存，則*p就是-1，如果你用unsigned int的指針p指向該內存，則*p = 2^32-1。
 
 　　而我們使用malloc等函數時，也只需要說明申請的內存的大小即可，也不用說明申請的內存空間所存放的數據的類型，例如，我們申請一塊內存空間來存放一個整型數據，則只需要malloc(sizeof(int))，即可，當然你完全可以把它當作一個具有4個單位的char數組來使用。所以我們可以使用void指針來指向我們申請的內存，申請內存的大小由鏈表中的成員data_size定義，它也是真正的data所占的內存大小。
 
 　　五、為什么需要賦值函數指針assign
 
 　　這里來說明一下，該鏈表的數據的插入方式，我們的插入方式是，新建一個結點，把data指向的數據復制到結點中，并把該結點插入到鏈表中。插入的函數定義如下：
 
 　　Iterator Insert(List list, void *data, Iterator it_before,
 
 　　void (*assign)(void*, const void*));
 
 　　從上面的解說中，我們可以看到鏈表中的成員data_size指示了鏈表中的數據所占的內存大小，那我們們就可以使用函數memcpy把data指向的數據復制到新建的結點的data所指向的內存即可。為什么還需要一個函數指針assign，來指向一個定義數據之間如何賦值的函數呢?其實這和面向對象語言中常說到的深復制和淺復制有關。
 
 　　注：memcpy函數的原型為： void * memcpy ( void * destination, const void * source, size_t num );
 
 　　試想一下，假如你的鏈表的數據類型不是int型等基本類型，也不是不含有指針的結構體，而是一個這樣的結構體，例如：
 
 　　struct student
 
 　　{
 
 　　char *name;
 
 　　char *no;
 
 　　int age;
 
 　　};
 
 　　學生的姓名和學號都是能過動態分配內存而來的，并由student結構體中的name和no指針指向，那么當我們使用memcpy時，只能復制其指針，而不能復制其指向的數據，這樣在很多情況下都會帶來一定的問題。這個跟在C++中什么時候需要自己定義復制構造函數的情況類似。因為這種情況下，默認的復制構造函數并不能滿足我們的需要，只能自己定義復制構造函數。
 
 　　所以在插入一個結點時，需要assign函數指針的原理與C++中自己定義復制構造函數的原理一樣。它用于定義如何根據一個已有的對象生成一個該對象的拷貝對象。當然，可能在大多數的情況下，我們需要用到的數據類型都沒有包含指針，所以在Insert函數的實現中，其實我也是有用到memcpy函數的，就是當assign為NULL時，就使用memcpy函數進行數據對象間的賦值，它其實就相當于C++中的默認復制構造函數。assign為NULL表示使用默認的逐位復制方式。
 
 　　六、為什么不用typedef
 
 　　對于這個問題，其實很好回答。很多人實現一個通用鏈表是這樣實現的，它們把node結構的實現如下：
 
 　　typedef struct node
 
 　　{
 
 　　//循環雙鏈表的結點結構
 
 　　DataType data;//數據域指針
 
 　　struct node *next;//指向當前結點的下一結點
 
 　　struct node *last;//指向當前結點的上一結點
 
 　　}Node;
 
 　　然后，當需要使用整型的鏈表時，就把DataType用typedef為int。其實這樣做的一個最大的缺陷就是一個程序中只能存在著一個數據類型的鏈表，例如，如果我需要一個int型的鏈表和一個float型的鏈表，那么該把DataType定義為int呢還是float呢?所以這種看似可行的方式，其實只是虛有其表，在現象中是行不能的，雖然不少的數據結構的書都是這樣實現的，但是它卻沒有什么實用價值。
 
 　　而其本質的原因是把結點的數據域的數據類型與某一種特定的數據類型DataType綁定在一起，從而讓鏈表不能獨立地變化。
 
 　　七、為什么只把結點的指針定義為Iterator
 
 　　在C++中iterator是一個類，為什么在這里，我只把結點的指針聲明為一個Iterator呢?其實受STL的影響，我在一開始時，也是把Iterator實現為一個結構體，它只有一個數據成員，就是一個指向Node的指針。但在后來的實踐中，發現其實并沒有必要。在C++中為什么把iterator定義為一個類，是為了重載*，->等運行符，讓iterator使用起來跟普通的指針一樣。但是在C語言中，并沒有重載運行符的做法，所以直接把Ierator聲明為一個Node的指針最為方便、直接和好用，所有的比較運算都可以直接進行，而無需要借助函數。而把它聲明為一個結構體反而麻煩、累贅。
 
 　　八、為什么查找需要兩個Iterator
 
 　　其實這是參考了STL中的泛型算法的思想。而且本人覺得這是一種比較好的實現。為什么FindFirst的函數原型不是托福改分
 
 　　Iterator FindFirst(List list, int (*condition)(const void*, const void*));
 
 　　而是
 
 　　Iterator FindFirst(Iterator begin, Iterator end, void *data,
 
 　　int (*condition)(const void*, const void*));
 
 　　我們可以試想一下，這個鏈表的為char鏈表，鏈表的元素為ABCBCBC，我們要在鏈表中找出所有的B，如果查找算法是使用第一種定義的話，它只能找出第一個B，而后面的兩個B就無能為力了，而第二種定義，則可以通過循環改變其始末迭代器來在不同的序列段間查找目標字符B的位置。 www.lefeng123.com