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

>>>>1.1.1 算法的接口

由于使用迭代器可以輕松地實(shí)現(xiàn)指針的前移或后移，因此可以使用迭代器接口實(shí)現(xiàn)冒泡排序算法。其函數(shù)原型為：

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

其中，p_if表示算法使用的迭代器接口。begin與end是一對(duì)迭代器，表示算法的操作范圍，但不一定是容器的首尾迭代器，因此算法可以處理任何范圍的數(shù)據(jù)。為了判定范圍的有效性，習(xí)慣采用前閉后開(kāi)范圍表示法，即使用begin和end表示的范圍為[begin,end)，表示范圍涵蓋bigen到end（不含end）之間的所有元素。當(dāng)begin==end時(shí)，上述所表現(xiàn)的便是一個(gè)空范圍。

compare同樣也是比較函數(shù)，但比較的類型發(fā)生了變化，用于比較兩個(gè)迭代器所對(duì)應(yīng)的值。其類型compare_t定義如下：

typedef int (*compare_t)(iterator_t it1, iterator_t it2);

swap函數(shù)用于交換兩個(gè)迭代器所對(duì)應(yīng)的數(shù)據(jù)，其類型swap_t定義如下：

typedef void (*swap_t)(iterator_t it1, iterator_t it2);

由此可見(jiàn)，接口中只有迭代器，根本沒(méi)有容器的蹤影，從而做到了容器與冒泡排序算法徹底分離，基于迭代器的冒泡排序算法詳見(jiàn)程序清單3.56。

程序清單3.56冒泡排序算法函數(shù)

1 void iter_sort(iterator_if_t *p_if, iterator_t begin, iterator_t end, compare_t compare, swap_t swap)

2 {

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

4 iterator_t it1 = begin; // it1指向數(shù)組變量的首元素

5 iterator_t it2 = end;

6

7 iterator_t it_next; // pNext指向p1所指向的元素的下一個(gè)元素

8 if (begin == end) { //沒(méi)有需要算法處理的迭代器

9 return;

10 }

11 iterator_prev(p_if, &it2); // it2指向需要排序的最后一個(gè)元素

12 while (it2 != begin){

13 it1 = begin;

14 flag = 1;

15 while(it1 != it2){

16 it_next = it1; //暫存

17 iterator_next(p_if, &it_next); // it_next為 it1 的下一個(gè)元素

18 if(compare(it1, it_next) > 0){

19 swap(it1, it_next); //交換內(nèi)容

20 flag = 0; // flag = 0，表示指針的內(nèi)容已交換

21 }

22 it1 = it_next; // it1的下一個(gè)元素

23 }

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

25 iterator_prev(p_if, &it2); // it2向前移

26 }

27 }

下面以一個(gè)簡(jiǎn)單的例子來(lái)測(cè)試驗(yàn)證基于迭代器的冒泡排序算法，詳見(jiàn)程序清單3.57。將整數(shù)存放到雙向鏈表中，首先將5、4、3、2、1分別加在鏈表的尾部，接著調(diào)用dlist_foreach()遍歷鏈表，看是否符合預(yù)期，然后再調(diào)用算法庫(kù)的iter_sort()排序。當(dāng)排序完畢后鏈表的元素應(yīng)該是從小到大排列的，再次調(diào)用算法庫(kù)的dilst_foreach()遍歷鏈表，看是否符合預(yù)期。

程序清單3.57使用雙向鏈表、算法和迭代器

1 #include

2 #include "iterator.h"

3

4 typedef struct _dlist_int{

5 dlist_node_t node; //包含鏈表結(jié)點(diǎn)

6 int data; // int類型數(shù)據(jù)

7 }dlist_int_t;

8

9 int list_node_process(void *p_arg, dlist_node_t *p_node)

10 {

11 printf("%d ", ((dlist_int_t *)p_node) -> data);

12 return 0;

13 }

14

15 static int __compare(iterator_t it1, iterator_t it2)

16 {

17 return ((dlist_int_t *)it1) -> data - ((dlist_int_t *)it2) -> data;

18 }

19

20 static void __swap(iterator_t it1, iterator_t it2)

21 {

22 int data = ((dlist_int_t *)it2) -> data;

23 ((dlist_int_t *)it2) -> data = ((dlist_int_t *)it1) -> data;

24 ((dlist_int_t *)it1) -> data = data;

25 }

26

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

28 {

29 iterator_if_t iterator_if;

30 dlist_head_t head; //定義鏈表頭結(jié)點(diǎn)

31 dlist_int_t node[5]; //定義5個(gè)結(jié)點(diǎn)空間

32 int i;

33

34 dlist_init(&head);

35

36 for (i = 0; i < 5; i++) {? ???????????????????????? //?將5個(gè)結(jié)點(diǎn)添加至鏈表尾部

37 node[i].data = 5 - i; //使值的順序?yàn)?5 ~ 1

38 dlist_add_tail(&head, &(node[i].node));

39 }

40 dlist_iterator_if_get(&iterator_if);

41

42 printf("\nBefore bubble sort:\n");

43 dlist_foreach (&head, list_node_process, NULL); //打印排序前的情況

44

45 iter_sort(&iterator_if, dlist_begin_get(&head), dlist_end_get(&head),__compare, __swap);

46

47 printf("\nAfter bubble sort:\n");

48 dlist_foreach (&head, list_node_process, NULL); //打印排序后的情況

49 return 0;

50 }

在這里，使用了dlist_foreach()遍歷函數(shù)，既然通過(guò)迭代器能夠?qū)崿F(xiàn)冒泡排序，那么也能通過(guò)迭代器實(shí)現(xiàn)簡(jiǎn)單的遍歷算法，此時(shí)遍歷算法與具體容器無(wú)關(guān)。遍歷函數(shù)的原型如下：

void iter_foreach(iterator_if_t *p_if, iterator_t begin, iterator_t end, visit_t visit, void *p_arg);

其中，p_if表示算法使用的迭代器接口，begin與end表示算法需要處理的迭代器范圍，visit是用戶自定義的遍歷迭代器的函數(shù)。其類型visit_t定義如下：

typedef int (*visit_t)(void *p_arg, iterator_t it);

visit_t的參數(shù)是p_arg指針和it迭代器，其返回值為int類型的函數(shù)指針。每遍歷一個(gè)結(jié)點(diǎn)均會(huì)調(diào)用visit指向的函數(shù)，傳遞給p_arg的值即為用戶參數(shù)，其值為iter_foreach()函數(shù)的p_arg參數(shù)，p_arg的值完全是由用戶決定的，傳遞給it迭代器的值即為指向當(dāng)前遍歷的迭代器，iter_foreach()函數(shù)的實(shí)現(xiàn)詳見(jiàn)程序清單3.58。

程序清單3.58遍歷算法函數(shù)

1 void iter_foreach(iterator_if_t *p_if, iterator_t begin, iterator_t end, visit_t visit, void *p_arg)

2 {

3 iterator_t it = begin;

4 while(it != end){

5 if (visit(p_arg, it) < 0) {???? ?????????????????? //?若返回值為負(fù)值，表明用戶終止了遍歷

6 return;

7 }

8 iterator_next(p_if, &it); //讓迭代器向后移動(dòng)

9 }

10 }

現(xiàn)在可以將程序清單3.57中的第43行和第48行中的dlist_foreach()函數(shù)修改為使用iter_foreach()函數(shù)，看能否得到相同的效果？

如果將數(shù)據(jù)保存在數(shù)組變量中，那么將如何使用已有的冒泡排序算法呢？由于數(shù)組也是容器，因此只要實(shí)現(xiàn)基于數(shù)組的迭代器即可，詳見(jiàn)程序清單3.59。

程序清單3.59使用數(shù)組實(shí)現(xiàn)迭代器接口

1 typedef int element_type_t;

2

3 static void __array_iterator_next(iterator_t *p_iter)

4 {

5 (*(element_type_t **)(p_iter))++; //讓迭代器指向下一個(gè)數(shù)據(jù)

6 }

7

8 static void __array_iterator_prev(iterator_t *p_iter)

9 {

10 (*(element_type_t **)(p_iter))--; //讓迭代器指向前一個(gè)數(shù)據(jù)

11 }

12

13 void array_iterator_if_get(iterator_if_t *p_if)

14 {

15 iterator_if_init(p_if, __array_iterator_next, __array_iterator_prev);

16 }

基于新的迭代器，同樣可以直接使用冒泡排序算法實(shí)現(xiàn)排序，詳見(jiàn)程序清單3.60。

程序清單3.60使用數(shù)組、算法和迭代器

1 #include

2 #include "iterator.h"

3

4 static int __visit(void *p_arg, iterator_t it)

5 {

6 printf("%d ", *(int *)it);

7 return 0;

8 }

9

10 static int __compare(iterator_t it1, iterator_t it2)

11 {

12 return *(int *)it1 - *(int *)it2;

13 }

14

15 static void __swap(iterator_t it1, iterator_t it2)

16 {

17 int data = *(int *)it2;

18 *(int *)it2 = *(int *)it1;

19 *(int *)it1 = data;

20 }

21

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

23 {

24 iterator_if_t iterator_if;

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

26 array_iterator_if_get(&iterator_if);

27

28 printf("\nBefore bubble sort:\n");

29 iter_foreach(&iterator_if, a, a + 5, __visit, NULL);

30

31 iter_sort(&iterator_if, a, a + 5, __compare, __swap);

32

33 printf("\nAfter bubble sort:\n");

34 iter_foreach(&iterator_if, a, a + 5, __visit, NULL);

35 return 0;

36 }

由此可見(jiàn)，通過(guò)迭代器冒泡排序算法也得到了復(fù)用。如果算法庫(kù)里有幾百個(gè)函數(shù)，那么只要實(shí)現(xiàn)迭代器接口的2個(gè)函數(shù)即可，從而達(dá)到復(fù)用代碼的目的。顯然，迭代器是一種更靈活的遍歷行為，它可以按任意順序訪問(wèn)容器中的元素，而且不會(huì)暴露容器的內(nèi)部結(jié)構(gòu)。