《周立功教授谈迭代器模式设计.doc》由会员分享，可在线阅读，更多相关《周立功教授谈迭代器模式设计.doc（6页珍藏版）》请在三一文库上搜索。
1、周立功教授谈迭代器模式设计近日周立功教授公开了数年的心血之作程序设计与数据结构，电子版已无偿性分享到电子工程师与高校群体下载，经周立功教授授权，特对本书内容进行连载。1.1 迭代器模式1.1.1 迭代器与容器1.1.2 迭代器接口为什么一定要考虑引入Iterator这种复杂的设计模式呢？如果是数组，直接使用for循环语句进行遍历处理不就可以了吗？为什么要在集合之外引入Iterator这个角色呢？一个重要的理由是，引入Iterator后可以将遍历与实现分离。实际上无论是单向链表还是双向链表，其查找算法与遍历算法的实现没有多少差别，基本上都是重复劳动。如果代码中有bug，则需要修改所有相关的代码。
2、为什么会出现这样的情况呢？主要是接口设计不合理所造成的，其最大的问题就是将容器和算法放在了一起，且算法的实现又依赖于容器的实现，因而必须为每一个容器开发一套与之匹配的算法。假设要在2种容器（双向链表、动态数组）中分别实现6种算法（交换、排序、求最大值、求最小值、遍历、查找），显然需要26=12个接口函数才能实现目标。随着算法数量的不断增多，势必导致函数的数量成倍增加，重复劳动的工作量也越大。如果将容器和算法单独设计，则只需要实现6个算法函数就行了。即算法不依赖容器的特定实现，算法不会直接在容器中进行操作。比如，排序算法无需关心元素是存放在数组或线性表中。在正式引入迭代器之前，不妨分析一下如程序
3、清单3.49所示的冒泡排序算法。程序清单3.49冒泡排序算法1 #include2 #include swap.h34 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所指向的元素的下一个元素1011 while(p2 != begin)12 p1 = begin;13 flag = 1;14 while(p1 != p2)
4、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 2728 int main(int argc, char *argv)29 30 int a=5, 3, 2, 4, 1;31 int i = 0;3233 bubbleSort(a, a+4);34 fo
5、r(i = 0; i *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指向a3。经过一轮循环之后，直到p1 = p2，此时整数4移到a3所在的位置，剩余的排序详见图 3.22。当p1
6、与p2重合在数组首元素所在的位置时，表示排序结束（图 3.22（d）。图 3.22 外部循环执行过程示意图由此可见，冒泡排序算法的核心是指针的操作，其主要行为如下：比较指针所指向的值的大小；交换指针所指向的内容；指针后移，即指针指向下一个元素；指针前移，即指针指向前面一个元素。由于这里是以int类型数据为例实现冒泡排序的，因此用户知道如何比较数据和如何交换指针所指向的内容，以及指针的前后移动。当使用支持任意类型数据的void *时，虽然算法程序不知道传入什么类型的数据，但调用者知道，因此在调用排序算法函数时，可以由用户传递参数通过回调函数实现。修改后的冒泡排序函数原型如下：void iter_
7、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实现指针的移动。虽然使用这种
8、方式可以实现指针的移动，但始终要求数据必须以数组的形式存储，一旦离开了这个特定的容器，则无法确定指针的行为。如果将算法与链表结合起来使用，显然代码中的p1+和p2-不适合链表。基于此，“不妨对指针进行抽象，让它针对不同的容器有不同的实现，而算法只关心它的指针接口”。显然，需要容器提供相应的接口函数，才能实现指针前移和后移，通常将这样的指针称为“迭代器”。从某种意义上来说，迭代器作为算法的接口是广义指针，而指针满足所有迭代器的要求。其优势在于对任何种类的容器都可以用同样的方法顺序遍历容器中的元素，而又不暴露容器的内部细节，迭代器接口的声明详见程序清单3.50。程序清单3.50 迭代器接口的声明1
9、 typedef void *iterator_t; /定义迭代器类型2 typedef void (*iterator_next_t)(iterator_t *p_iter);3 typedef void (*iterator_prev_t)(iterator_t *p_iter);45 /迭代器接口（if表示interface，由具体容器实现，比如，链表、数组等）6 typedef struct _iterator_if7 iterator_next_t pfn_next; /迭代器后移函数，相当于p1+8 iterator_prev_t pfn_prev; /迭代器前移函数，相当于p2-
10、9 iterator_if_t;其中，p_iter指向的内容是由容器决定的，它既可以指向结点，也可以指向数据。无论是链表还是其它容器实现的pfn_next函数，其意义是一样的，其它函数同理。如果将迭代器理解为指向数据的指针变量，则pfn_next函数让迭代器指向容器的下一个数据，pfn_prev函数让迭代器指向容器的上一个数据。此时，应该针对接口编写一些获取或设置数值的方法。用于读取变量的方法通常称为“获取方法（getter）”，用于写入变量的方法通常称为“设置方法（setter）”。下面以双向链表为例，使用结构体指针作为dlist_iterator_if_get()的返回值，详见程序清单3.
11、51。程序清单3.51获取双向链表的迭代器接口（1）1 static void _dlist_iterator_next(iterator_t *p_iter) /让迭代器指向容器的下一个数据2 3 *p_iter = (dlist_node_t *)*p_iter) - p_next;4 56 static void _dlist_iterator_prev(iterator_t *p_iter) /让迭代器指向容器的上一个数据7 8 *p_iter = (dlist_node_t *)*p_iter) - p_prev;9 1011 iterator_if_t *dlist_iterato
12、r_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 /返回结构体变量地址 / 获得链表的迭代器接口，即p_if = 4 p_if - pfn_prev = _dlist_iterator_prev;5 其调用形式如下：iterator_if_t iterator_if;dlist_iterator_if_get(由于iterator_
13、if_t类型的结构体中只有两个函数指针，因此对函数指针的访问仅包含设置和调用，详见程序清单 3.53。程序清单3.53迭代器接口（iterator.h）1 #pragma once;23 typedef void *iterator_t;4 typedef void(*iterator_next_t)(iterator_t *p_iter);5 typedef void(*iterator_prev_t)(iterator_t *p_iter);67 typedef struct _iterator_if8 iterator_next_t pfn_next; /调用迭代器后移的函数指针，相当于
14、p1+9 iterator_prev_t pfn_prev; /调用迭代器前移的函数指针，相当于p2-10 iterator_if_t;1112 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); /迭代器后移函数，相当于+14 void iterator_prev(iterator_if_t *p_if, iterator_t *
15、p_iter); /迭代器前移函数，相当于-这些函数的具体实现详见程序清单3.54。程序清单3.54迭代器接口的实现1 #include iterator.h23 void iterator_if_init(iterator_if_t *p_if, iterator_next_t pfn_next, iterator_prev_t pfn_prev)4 5 p_if - pfn_next = pfn_next;6 p_if - pfn_prev = pfn_prev;7 89 void iterator_next(iterator_if_t *p_if, iterator_t *p_iter)
16、10 11 p_if - pfn_next(p_iter);12 1314 void iterator_prev(iterator_if_t *p_if, iterator_t *p_iter)15 16 p_if - pfn_prev(p_iter);17 现在可以直接调用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);4