近日周立功教授公開了數年的心血之作《程序設計與數據結構》，電子版已無償性分享到電子工程師與高校群體下載，經周立功教授授權，特對本書內容進行連載。

>>>>1.1 迭代器模式

>>>1.1.1 迭代器與容器

在初始化數組中的元素時，通常使用下面這樣的for循環語句遍歷數組：

int i, a[10];

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

a[i] = i;

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

由此可見，常用的循環結構就是一種迭代操作，在每一次迭代操作中，對迭代器的修改即等價于修改循環控制的標志或計數器。而容器是一種保存值的集合的數據結構，C有兩種內建的容器：數組和結構體。雖然C沒有提供更多的容器，但用戶可以按需編寫自己的容器，比如，鏈表、哈希表等。

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

顯而易見，迭代器是一種抽象的設計概念，因為在程序設計語言中并沒有直接對應于這個概念的實物。《設計模式》一書提供了23種設計模式的完整描述，其中iterator模式的定義為：在遍歷一個容器對象時，提供一種方法順序訪問一個容器對象中的各個元素，而又不暴露該對象的內部表示方式。其中心思想是將數據容器和算法分開且彼此獨立，最后再用黏合劑將它們撮合在一起。

>>>1.1.2 迭代器接口

為什么一定要考慮引入Iterator這種復雜的設計模式呢？如果是數組，直接使用for循環語句進行遍歷處理不就可以了嗎？為什么要在集合之外引入Iterator這個角色呢？一個重要的理由是，引入Iterator后可以將遍歷與實現分離。

實際上無論是單向鏈表還是雙向鏈表，其查找算法與遍歷算法的實現沒有多少差別，基本上都是重復勞動。如果代碼中有bug，則需要修改所有相關的代碼。為什么會出現這樣的情況呢？主要是接口設計不合理所造成的，其最大的問題就是將容器和算法放在了一起，且算法的實現又依賴于容器的實現，因而必須為每一個容器開發一套與之匹配的算法。

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

在正式引入迭代器之前，不妨分析一下如程序清單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，表示指針的內容未交換

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

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

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

10

11 while(p2 != begin){

12 p1 = begin;

13 flag = 1;

14 while(p1 != p2){

15 pNext = p1+1;

16 if(*p1>*pNext) //比較指針所指向的值的大小

17 {

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

19 flag = 0; // flag = 0，表示2個指針的內容交換

20 }

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

22 }

23 if(flag) return; // 沒有交換，表示已經有序，則直接返回

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;

如果任何一次遍歷沒有執行任何交換，則說明記錄是有序的且終止排序。其中，p1指向數組的首元素，pNext指向p1所指向的元素的下一個元素，p2指向數組的尾元素（圖 3.21（a））。如果*p1>*pNext，則交換指針所指向的內容，p1與pNext后移（圖 3.21（b）），反之指針所指向的內容不變，p1與pNext后移，經過一輪排序之后，直到p1 = p2為止，最大元素移到數組尾部。

圖 3.21 內部循環執行過程示意圖

當最大元素移到數組的尾部時，則退出內部循環。p2前移后程序跳轉到程序清單3.49（15），p1再次指向數組的首元素，pNext指向p1所指向的元素的下一個元素（圖 3.22（a））。此時，圖 3.22（a）與圖 3.21（a）的差別在于p2指向a[3]。經過一輪循環之后，直到p1 = p2，此時整數4移到a[3]所在的位置，剩余的排序詳見圖 3.22。當p1與p2重合在數組首元素所在的位置時，表示排序結束（圖 3.22（d））。

圖 3.22 外部循環執行過程示意圖

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

●比較指針所指向的值的大小；

●交換指針所指向的內容；

●指針后移，即指針指向下一個元素；

●指針前移，即指針指向前面一個元素。

由于這里是以int類型數據為例實現冒泡排序的，因此用戶知道如何比較數據和如何交換指針所指向的內容，以及指針的前后移動。當使用支持任意類型數據的void *時，雖然算法程序不知道傳入什么類型的數據，但調用者知道，因此在調用排序算法函數時，可以由用戶傳遞參數通過回調函數實現。修改后的冒泡排序函數原型如下：

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

其中，compare用于比較兩個指針所指向的值的大小，compare_t類型定義如下：

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

swap函數用于交換兩個指針指向的內容，swap_t類型定義如下：

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

顯然無法通過++或--移動指針，因為不知道傳入的是什么類型的數據。如果知道數據占用4個字節，則可以通過指針的值加4或減4實現指針的移動。雖然使用這種方式可以實現指針的移動，但始終要求數據必須以數組的形式存儲，一旦離開了這個特定的容器，則無法確定指針的行為。如果將算法與鏈表結合起來使用，顯然代碼中的p1++和p2--不適合鏈表。

基于此，“不妨對指針進行抽象，讓它針對不同的容器有不同的實現，而算法只關心它的指針接口”。顯然，需要容器提供相應的接口函數，才能實現指針前移和后移，通常將這樣的指針稱為“迭代器”。從某種意義上來說，迭代器作為算法的接口是廣義指針，而指針滿足所有迭代器的要求。其優勢在于對任何種類的容器都可以用同樣的方法順序遍歷容器中的元素，而又不暴露容器的內部細節，迭代器接口的聲明詳見程序清單3.50。

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

1 typedef void *iterator_t; //定義迭代器類型

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

4

5 //迭代器接口（if表示interface，由具體容器實現，比如，鏈表、數組等）

6 typedef struct _iterator_if{

7 iterator_next_t pfn_next; //迭代器后移函數，相當于p1++

8 iterator_prev_t pfn_prev; //迭代器前移函數，相當于p2--

其中，p_iter指向的內容是由容器決定的，它既可以指向結點，也可以指向數據。無論是鏈表還是其它容器實現的pfn_next函數，其意義是一樣的，其它函數同理。如果將迭代器理解為指向數據的指針變量，則pfn_next函數讓迭代器指向容器的下一個數據，pfn_prev函數讓迭代器指向容器的上一個數據。

此時，應該針對接口編寫一些獲取或設置數值的方法。用于讀取變量的方法通常稱為“獲取方法（getter）”，用于寫入變量的方法通常稱為“設置方法（setter）”。下面以雙向鏈表為例，使用結構體指針作為dlist_iterator_if_get()的返回值，詳見程序清單3.51。

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

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

2 {

4 }

5

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

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; //返回結構體變量地址&iterator_if

其調用形式如下：

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

注意，如果省略static，則iterator_if就成了一個局部變量。由于它將在函數執行完后失效，因此返回它的地址毫無意義。這里采用了直接訪問結構體成員的方式對iterator_if_t類型的結構體賦值，顯然不同模塊之間應該盡可能避免這種方式，取而代之的是提供相應的接口，詳見程序清單 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;

其調用形式如下：

iterator_if_t iterator_if;

由于iterator_if_t類型的結構體中只有兩個函數指針，因此對函數指針的訪問僅包含設置和調用，詳見程序清單 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; //調用迭代器后移的函數指針，相當于p1++

9 iterator_prev_t pfn_prev; //調用迭代器前移的函數指針，相當于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); //迭代器后移函數，相當于++

這些函數的具體實現詳見程序清單3.54。

程序清單3.54迭代器接口的實現

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);

現在可以直接調用iterator_if_init()實現dlist_iterator_if_get()，詳見程序清單 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);