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