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