近日周立功教授公開(kāi)了數(shù)年的心血之作《程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)》，電子版已無(wú)償性分享到電子工程師與高校群體下載，經(jīng)周立功教授授權(quán)，特對(duì)本書(shū)內(nèi)容進(jìn)行連載。

>>>>1.1 迭代器模式

>>>1.1.1 迭代器與容器

在初始化數(shù)組中的元素時(shí)，通常使用下面這樣的for循環(huán)語(yǔ)句遍歷數(shù)組：

int i, a[10];

for(i = 0; i < 10; i++)?

a[i] = i;

這段代碼中的循環(huán)變量i，該變量的初始值為0，然后遞增為1、2、3、...，程序在每次i遞增后都將值賦給a[i]。數(shù)組中保存了許多元素，通過(guò)指定數(shù)組下標(biāo)，即可從中選擇任意一個(gè)元素。for語(yǔ)句中的i++的作用是讓i的值在每次循環(huán)后自增1，這樣就可以訪問(wèn)數(shù)組中的下一個(gè)元素，從而實(shí)現(xiàn)了從頭到尾逐一遍歷數(shù)組元素的功能。

由此可見(jiàn)，常用的循環(huán)結(jié)構(gòu)就是一種迭代操作，在每一次迭代操作中，對(duì)迭代器的修改即等價(jià)于修改循環(huán)控制的標(biāo)志或計(jì)數(shù)器。而容器是一種保存值的集合的數(shù)據(jù)結(jié)構(gòu)，C有兩種內(nèi)建的容器：數(shù)組和結(jié)構(gòu)體。雖然C沒(méi)有提供更多的容器，但用戶(hù)可以按需編寫(xiě)自己的容器，比如，鏈表、哈希表等。

將i的作用抽象化、通用化后形成的模式，在設(shè)計(jì)模式中i稱(chēng)為迭代器（Iterator）模式，Iterate的字面意思是重復(fù)、反復(fù)聲明，其實(shí)就是重復(fù)做某件事，Iterator模式用于遍歷數(shù)組中的元素。迭代器的基本思想是迭代器變量存儲(chǔ)了容器的某個(gè)元素的位置，因此能夠遍歷該位置的元素。通過(guò)迭代器提供的方法，可以繼續(xù)遍歷容器的下一個(gè)元素。

顯而易見(jiàn)，迭代器是一種抽象的設(shè)計(jì)概念，因?yàn)樵诔绦蛟O(shè)計(jì)語(yǔ)言中并沒(méi)有直接對(duì)應(yīng)于這個(gè)概念的實(shí)物?！对O(shè)計(jì)模式》一書(shū)提供了23種設(shè)計(jì)模式的完整描述，其中iterator模式的定義為：在遍歷一個(gè)容器對(duì)象時(shí)，提供一種方法順序訪問(wèn)一個(gè)容器對(duì)象中的各個(gè)元素，而又不暴露該對(duì)象的內(nèi)部表示方式。其中心思想是將數(shù)據(jù)容器和算法分開(kāi)且彼此獨(dú)立，最后再用黏合劑將它們撮合在一起。

>>>1.1.2 迭代器接口

為什么一定要考慮引入Iterator這種復(fù)雜的設(shè)計(jì)模式呢？如果是數(shù)組，直接使用for循環(huán)語(yǔ)句進(jìn)行遍歷處理不就可以了嗎？為什么要在集合之外引入Iterator這個(gè)角色呢？一個(gè)重要的理由是，引入Iterator后可以將遍歷與實(shí)現(xiàn)分離。

實(shí)際上無(wú)論是單向鏈表還是雙向鏈表，其查找算法與遍歷算法的實(shí)現(xiàn)沒(méi)有多少差別，基本上都是重復(fù)勞動(dòng)。如果代碼中有bug，則需要修改所有相關(guān)的代碼。為什么會(huì)出現(xiàn)這樣的情況呢？主要是接口設(shè)計(jì)不合理所造成的，其最大的問(wèn)題就是將容器和算法放在了一起，且算法的實(shí)現(xiàn)又依賴(lài)于容器的實(shí)現(xiàn)，因而必須為每一個(gè)容器開(kāi)發(fā)一套與之匹配的算法。

假設(shè)要在2種容器（雙向鏈表、動(dòng)態(tài)數(shù)組）中分別實(shí)現(xiàn)6種算法（交換、排序、求最大值、求最小值、遍歷、查找），顯然需要2×6=12個(gè)接口函數(shù)才能實(shí)現(xiàn)目標(biāo)。隨著算法數(shù)量的不斷增多，勢(shì)必導(dǎo)致函數(shù)的數(shù)量成倍增加，重復(fù)勞動(dòng)的工作量也越大。如果將容器和算法單獨(dú)設(shè)計(jì)，則只需要實(shí)現(xiàn)6個(gè)算法函數(shù)就行了。即算法不依賴(lài)容器的特定實(shí)現(xiàn)，算法不會(huì)直接在容器中進(jìn)行操作。比如，排序算法無(wú)需關(guān)心元素是存放在數(shù)組或線性表中。

在正式引入迭代器之前，不妨分析一下如程序清單3.49所示的冒泡排序算法。

程序清單3.49冒泡排序算法

1 #include

2 #include "swap.h"

3

4 void bubbleSort(int *begin, int *end)

5 {

6 int flag = 1; // flag = 1，表示指針的內(nèi)容未交換

7 int *p1 = begin; // p1指向數(shù)組的首元素

8 int *p2 = end; // p2指向數(shù)組的尾元素

9 int *pNext; // pNext指向p1所指向的元素的下一個(gè)元素

10

11 while(p2 != begin){

12 p1 = begin;

13 flag = 1;

14 while(p1 != p2){

15 pNext = p1+1;

16 if(*p1>*pNext) //比較指針?biāo)赶虻闹档拇笮?/span>

17 {

18 swap(p1, pNext); //交換2個(gè)指針的內(nèi)容

19 flag = 0; // flag = 0，表示2個(gè)指針的內(nèi)容交換

20 }

21 p1++; // p1指針后移

22 }

23 if(flag) return; // 沒(méi)有交換，表示已經(jīng)有序，則直接返回

24 p2--; // p2指針前移

25 }

26 }

27

28 int main(int argc, char *argv[])

29 {

30 int a[]={5, 3, 2, 4, 1};

31 int i = 0;

34 for(i = 0; i < sizeof(a) / sizeof(a[0]); i++){

35 printf("%d ", a[i]);

36 }

37 return 0;

如果任何一次遍歷沒(méi)有執(zhí)行任何交換，則說(shuō)明記錄是有序的且終止排序。其中，p1指向數(shù)組的首元素，pNext指向p1所指向的元素的下一個(gè)元素，p2指向數(shù)組的尾元素（圖 3.21（a））。如果*p1>*pNext，則交換指針?biāo)赶虻膬?nèi)容，p1與pNext后移（圖 3.21（b）），反之指針?biāo)赶虻膬?nèi)容不變，p1與pNext后移，經(jīng)過(guò)一輪排序之后，直到p1 = p2為止，最大元素移到數(shù)組尾部。

圖 3.21 內(nèi)部循環(huán)執(zhí)行過(guò)程示意圖

當(dāng)最大元素移到數(shù)組的尾部時(shí)，則退出內(nèi)部循環(huán)。p2前移后程序跳轉(zhuǎn)到程序清單3.49（15），p1再次指向數(shù)組的首元素，pNext指向p1所指向的元素的下一個(gè)元素（圖 3.22（a））。此時(shí)，圖 3.22（a）與圖 3.21（a）的差別在于p2指向a[3]。經(jīng)過(guò)一輪循環(huán)之后，直到p1 = p2，此時(shí)整數(shù)4移到a[3]所在的位置，剩余的排序詳見(jiàn)圖 3.22。當(dāng)p1與p2重合在數(shù)組首元素所在的位置時(shí)，表示排序結(jié)束（圖 3.22（d））。

圖 3.22 外部循環(huán)執(zhí)行過(guò)程示意圖

由此可見(jiàn)，冒泡排序算法的核心是指針的操作，其主要行為如下：

●比較指針?biāo)赶虻闹档拇笮。?/span>

●交換指針?biāo)赶虻膬?nèi)容；

●指針后移，即指針指向下一個(gè)元素；

●指針前移，即指針指向前面一個(gè)元素。

由于這里是以int類(lèi)型數(shù)據(jù)為例實(shí)現(xiàn)冒泡排序的，因此用戶(hù)知道如何比較數(shù)據(jù)和如何交換指針?biāo)赶虻膬?nèi)容，以及指針的前后移動(dòng)。當(dāng)使用支持任意類(lèi)型數(shù)據(jù)的void *時(shí)，雖然算法程序不知道傳入什么類(lèi)型的數(shù)據(jù)，但調(diào)用者知道，因此在調(diào)用排序算法函數(shù)時(shí)，可以由用戶(hù)傳遞參數(shù)通過(guò)回調(diào)函數(shù)實(shí)現(xiàn)。修改后的冒泡排序函數(shù)原型如下：

void iter_sort (void *begin, void *end, compare_t compare, swap_t swap);

其中，compare用于比較兩個(gè)指針?biāo)赶虻闹档拇笮?/span>，compare_t類(lèi)型定義如下：

typedef int (*compare_t) (void *p1, void *p2);

swap函數(shù)用于交換兩個(gè)指針指向的內(nèi)容，swap_t類(lèi)型定義如下：

typedef void (*swap_t) (void *p1, void *p2);

顯然無(wú)法通過(guò)++或--移動(dòng)指針，因?yàn)椴恢纻魅氲氖鞘裁搭?lèi)型的數(shù)據(jù)。如果知道數(shù)據(jù)占用4個(gè)字節(jié)，則可以通過(guò)指針的值加4或減4實(shí)現(xiàn)指針的移動(dòng)。雖然使用這種方式可以實(shí)現(xiàn)指針的移動(dòng)，但始終要求數(shù)據(jù)必須以數(shù)組的形式存儲(chǔ)，一旦離開(kāi)了這個(gè)特定的容器，則無(wú)法確定指針的行為。如果將算法與鏈表結(jié)合起來(lái)使用，顯然代碼中的p1++和p2--不適合鏈表。

基于此，“不妨對(duì)指針進(jìn)行抽象，讓它針對(duì)不同的容器有不同的實(shí)現(xiàn)，而算法只關(guān)心它的指針接口”。顯然，需要容器提供相應(yīng)的接口函數(shù)，才能實(shí)現(xiàn)指針前移和后移，通常將這樣的指針?lè)Q為“迭代器”。從某種意義上來(lái)說(shuō)，迭代器作為算法的接口是廣義指針，而指針滿(mǎn)足所有迭代器的要求。其優(yōu)勢(shì)在于對(duì)任何種類(lèi)的容器都可以用同樣的方法順序遍歷容器中的元素，而又不暴露容器的內(nèi)部細(xì)節(jié)，迭代器接口的聲明詳見(jiàn)程序清單3.50。

程序清單3.50 迭代器接口的聲明

1 typedef void *iterator_t; //定義迭代器類(lèi)型

2 typedef void (*iterator_next_t)(iterator_t *p_iter);

4

5 //迭代器接口（if表示interface，由具體容器實(shí)現(xiàn)，比如，鏈表、數(shù)組等）

6 typedef struct _iterator_if{

7 iterator_next_t pfn_next; //迭代器后移函數(shù)，相當(dāng)于p1++

8 iterator_prev_t pfn_prev; //迭代器前移函數(shù)，相當(dāng)于p2--

其中，p_iter指向的內(nèi)容是由容器決定的，它既可以指向結(jié)點(diǎn)，也可以指向數(shù)據(jù)。無(wú)論是鏈表還是其它容器實(shí)現(xiàn)的pfn_next函數(shù)，其意義是一樣的，其它函數(shù)同理。如果將迭代器理解為指向數(shù)據(jù)的指針變量，則pfn_next函數(shù)讓迭代器指向容器的下一個(gè)數(shù)據(jù)，pfn_prev函數(shù)讓迭代器指向容器的上一個(gè)數(shù)據(jù)。

此時(shí)，應(yīng)該針對(duì)接口編寫(xiě)一些獲取或設(shè)置數(shù)值的方法。用于讀取變量的方法通常稱(chēng)為“獲取方法（getter）”，用于寫(xiě)入變量的方法通常稱(chēng)為“設(shè)置方法（setter）”。下面以雙向鏈表為例，使用結(jié)構(gòu)體指針作為dlist_iterator_if_get()的返回值，詳見(jiàn)程序清單3.51。

程序清單3.51獲取雙向鏈表的迭代器接口（1）

1 static void __dlist_iterator_next(iterator_t *p_iter) //讓迭代器指向容器的下一個(gè)數(shù)據(jù)

2 {

4 }

5

6 static void __dlist_iterator_prev(iterator_t *p_iter) //讓迭代器指向容器的上一個(gè)數(shù)據(jù)

7 {

8 *p_iter = ((dlist_node_t *)*p_iter) -> p_prev;

9 }

11 iterator_if_t *dlist_iterator_if_get (void)

12 {

13 static iterator_if_t iterator_if;

14 iterator_if.pfn_next = __dlist_iterator_next;

15 iterator_if.pfn_prev = __dlist_iterator_prev;

16 return &iterator_if; //返回結(jié)構(gòu)體變量地址&iterator_if

其調(diào)用形式如下：

iterator_if_t *p_if = dlist_iterator_if_get(); // 獲得鏈表的迭代器接口，即p_if = &iterator_if

注意，如果省略static，則iterator_if就成了一個(gè)局部變量。由于它將在函數(shù)執(zhí)行完后失效，因此返回它的地址毫無(wú)意義。這里采用了直接訪問(wèn)結(jié)構(gòu)體成員的方式對(duì)iterator_if_t類(lèi)型的結(jié)構(gòu)體賦值，顯然不同模塊之間應(yīng)該盡可能避免這種方式，取而代之的是提供相應(yīng)的接口，詳見(jiàn)程序清單 3.52。

程序清單3.52獲取雙向鏈表的迭代器接口（2）

1 void dlist_iterator_if_get(iterator_if_t *p_if)

2 {

3 p_if -> pfn_next = __dlist_iterator_next;

4 p_if -> pfn_prev = __dlist_iterator_prev;

其調(diào)用形式如下：

iterator_if_t iterator_if;

由于iterator_if_t類(lèi)型的結(jié)構(gòu)體中只有兩個(gè)函數(shù)指針，因此對(duì)函數(shù)指針的訪問(wèn)僅包含設(shè)置和調(diào)用，詳見(jiàn)程序清單 3.53。

程序清單3.53迭代器接口（iterator.h）

1 #pragma once;

2

3 typedef void *iterator_t;

4 typedef void(*iterator_next_t)(iterator_t *p_iter);

6

7 typedef struct _iterator_if{

8 iterator_next_t pfn_next; //調(diào)用迭代器后移的函數(shù)指針，相當(dāng)于p1++

9 iterator_prev_t pfn_prev; //調(diào)用迭代器前移的函數(shù)指針，相當(dāng)于p2--

10 }iterator_if_t;

12 void iterator_if_init(iterator_if_t *p_if, iterator_next_t pfn_next, iterator_prev_t pfn_prev);

13 void iterator_next(iterator_if_t *p_if, iterator_t *p_iter); //迭代器后移函數(shù)，相當(dāng)于++

這些函數(shù)的具體實(shí)現(xiàn)詳見(jiàn)程序清單3.54。

程序清單3.54迭代器接口的實(shí)現(xiàn)

1 #include "iterator.h"

2

3 void iterator_if_init(iterator_if_t *p_if, iterator_next_t pfn_next, iterator_prev_t pfn_prev)

5 p_if -> pfn_next = pfn_next;

6 p_if -> pfn_prev = pfn_prev;

7 }

8

9 void iterator_next(iterator_if_t *p_if, iterator_t *p_iter)

10 {

11 p_if -> pfn_next(p_iter);

12 }

14 void iterator_prev(iterator_if_t *p_if, iterator_t *p_iter)

15 {

16 p_if -> pfn_prev(p_iter);

現(xiàn)在可以直接調(diào)用iterator_if_init()實(shí)現(xiàn)dlist_iterator_if_get()，詳見(jiàn)程序清單 3.55。

程序清單3.55獲取雙向鏈表的迭代器接口（3）

1 void dlist_iterator_if_get(iterator_if_t *p_if)

2 {

3 iterator_if_init(p_if, __dlist_iterator_next, __dlist_iterator_prev);