《使用迭代器如何实现指针前移或后移.doc》由会员分享，可在线阅读，更多相关《使用迭代器如何实现指针前移或后移.doc（5页珍藏版）》请在三一文库上搜索。
1、使用迭代器如何实现指针前移或后移近日周立功教授公开了数年的心血之作程序设计与数据结构，电子版已无偿性分享到电子工程师与高校群体下载，经周立功教授授权，特对本书内容进行连载。1.1.1 算法的接口由于使用迭代器可以轻松地实现指针的前移或后移，因此可以使用迭代器接口实现冒泡排序算法。其函数原型为：void iter_sort(iterator_if_t *p_if, iterator_t begin, iterator_t end, compare_t compare, swap_t swap) ;其中，p_if表示算法使用的迭代器接口。begin与end是一对迭代器，表示算法的操作范围，但不一定
2、是容器的首尾迭代器，因此算法可以处理任何范围的数据。为了判定范围的有效性，习惯采用前闭后开范围表示法，即使用begin和end表示的范围为begin,end)，表示范围涵盖bigen到end（不含end）之间的所有元素。当begin=end时，上述所表现的便是一个空范围。compare同样也是比较函数，但比较的类型发生了变化，用于比较两个迭代器所对应的值。其类型compare_t定义如下：typedef int (*compare_t)(iterator_t it1, iterator_t it2);swap函数用于交换两个迭代器所对应的数据，其类型swap_t定义如下：typedef voi
3、d (*swap_t)(iterator_t it1, iterator_t it2);由此可见，接口中只有迭代器，根本没有容器的踪影，从而做到了容器与冒泡排序算法彻底分离，基于迭代器的冒泡排序算法详见程序清单3.56。程序清单3.56冒泡排序算法函数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，表示指针的内容未交换4 iterator_t it1 = begin; / it1指
4、向数组变量的首元素5 iterator_t it2 = end;67 iterator_t it_next; / pNext指向p1所指向的元素的下一个元素8 if (begin = end) /没有需要算法处理的迭代器9 return;10 11 iterator_prev(p_if, / it2指向需要排序的最后一个元素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为 it1 的下一个元素18
5、 if(compare(it1, it_next) 0)19 swap(it1, it_next); /交换内容20 flag = 0; / flag = 0，表示指针的内容已交换21 22 it1 = it_next; / it1的下一个元素23 24 if(flag) return; /没有交换，表示已经有序，则直接返回25 iterator_prev(p_if, / it2向前移26 27 下面以一个简单的例子来测试验证基于迭代器的冒泡排序算法，详见程序清单3.57。将整数存放到双向链表中，首先将5、4、3、2、1分别加在链表的尾部，接着调用dlist_foreach()遍历链表，看是否
6、符合预期，然后再调用算法库的iter_sort()排序。当排序完毕后链表的元素应该是从小到大排列的，再次调用算法库的dilst_foreach()遍历链表，看是否符合预期。程序清单3.57使用双向链表、算法和迭代器1 #include 2 #include iterator.h34 typedef struct _dlist_int5 dlist_node_t node; /包含链表结点6 int data; / int类型数据7 dlist_int_t;89 int list_node_process(void *p_arg, dlist_node_t *p_node)10 11 print
7、f(%d , (dlist_int_t *)p_node) - data);12 return 0;13 1415 static int _compare(iterator_t it1, iterator_t it2)16 17 return (dlist_int_t *)it1) - data - (dlist_int_t *)it2) - data;18 1920 static void _swap(iterator_t it1, iterator_t it2)21 22 int data = (dlist_int_t *)it2) - data;23 (dlist_int_t *)it2
8、) - data = (dlist_int_t *)it1) - data;24 (dlist_int_t *)it1) - data = data;25 2627 int main(int argc, char *argv)28 29 iterator_if_t iterator_if;30 dlist_head_t head; /定义链表头结点31 dlist_int_t node5; /定义5个结点空间32 int i;3334 dlist_init(3536 for (i = 0; i 2 #include iterator.h34 static int _visit(void *p_
9、arg, iterator_t it)5 6 printf(%d , *(int *)it);7 return 0;8 910 static int _compare(iterator_t it1, iterator_t it2)11 12 return *(int *)it1 - *(int *)it2;13 1415 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 2122 i
10、nt 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(2728 printf(nBefore bubble sort:n);29 iter_foreach(3031 iter_sort(3233 printf(nAfter bubble sort:n);34 iter_foreach(35 return 0;36 由此可见，通过迭代器冒泡排序算法也得到了复用。如果算法库里有几百个函数，那么只要实现迭代器接口的2个函数即可，从而达到复用代码的目的。显然，迭代器是一种更灵活的遍历行为，它可以按任意顺序访问容器中的元素，而且不会暴露容器的内部结构。