周立功教授谈迭代器模式设计.doc
《周立功教授谈迭代器模式设计.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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 立功 教授 谈迭代器 模式 设计
链接地址:https://www.31doc.com/p-3406024.html