C++算法设计基础(5).ppt

《C++算法设计基础(5).ppt》由会员分享，可在线阅读，更多相关《C++算法设计基础(5).ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2章章 C+算法设计基础（算法设计基础（5）石志国石志国大纲大纲 C+程序结构初步，使用程序结构初步，使用C+语言编写简语言编写简单代码单代码 C+面向对象基础、构造与析构函数、面向对象基础、构造与析构函数、this指针以及指针以及const修饰符等修饰符等 C+模板的基本概念、函数模型和类模板模板的基本概念、函数模型和类模板 泛型算法的基本概念泛型算法的基本概念2.11 泛型算法初步泛型算法初步在进行程序设计的时候，一些常用的算法经常在进行程序设计的时候，一些常用的算法经常用到。用到。n比如：取最大值比如：取最大值（max()）、取最小值、取最小值（min()）、查扎查扎（find()）

2、和排序和排序（sort()）在调用这些算法的时候，希望算法并不局限于在调用这些算法的时候，希望算法并不局限于某一种数据类型，比如不管是某一种数据类型，比如不管是vector、list还是还是内置的数组类型都可以使用。内置的数组类型都可以使用。2.11.1 泛型算法的必要性泛型算法的必要性为了实现这些需要，需要引入为了实现这些需要，需要引入“泛型算法泛型算法”，所谓，所谓“泛型泛型”是它们的操作是建立多种容器上的是它们的操作是建立多种容器上的所谓所谓“算法算法”是因为实现的是公共操作，比如：是因为实现的是公共操作，比如：min()、max()和和sort()等等。使用等等。使用“泛型算法泛型算法

3、”可以大可以大大提高代码的开发效率。大提高代码的开发效率。Std(标准模板库标准模板库)是是C中的中的STL中的。中的。STL是是C独有的一套库，内容很丰富，功能很强大，但独有的一套库，内容很丰富，功能很强大，但是学习的难度也比较大。是学习的难度也比较大。在在vector中查找一个数中查找一个数#include#include using namespace std;void main()int iSearchValue=47;int ia 6 =27,210,12,47,109,83;vector ivec(ia,ia+6);vector:iterator iter=ivec.begin()

4、;for(;iter!=ivec.end();+iter)if(*iter=iSearchValue)cout 找到要查找的字符了！找到要查找的字符了！endl;2.11.2 泛型算法的基本概念泛型算法的基本概念希望每个泛型算法的实现都独立于单独的容器希望每个泛型算法的实现都独立于单独的容器类型。类型。因为已经消除了算法的类型依赖性，所以单个因为已经消除了算法的类型依赖性，所以单个的算法可以操作在各种容器以及内置数组类型的算法可以操作在各种容器以及内置数组类型上。上。1 泛型算法的组成泛型算法的组成对于对于find()算法，一般性步骤是：算法，一般性步骤是：n1、顺次检查每个元素、顺次检查每个

5、元素n2、如果当前元素等于被检查的值，那么返回该元素在、如果当前元素等于被检查的值，那么返回该元素在集合中的位置。集合中的位置。n3、否则，检查下一个元素，重复步骤、否则，检查下一个元素，重复步骤2，直到找到一个，直到找到一个元素，或者检查完所有元素。元素，或者检查完所有元素。n4、如果已经到了集合的末尾，而且没有找到该值，则、如果已经到了集合的末尾，而且没有找到该值，则返回该值在这个集合中不存在。返回该值在这个集合中不存在。泛型算法提供一个泛型算法提供一个“iterator”来遍历每个元素。来遍历每个元素。算法遍历的范围用一对算法遍历的范围用一对iterator标记：一个标记：一个first

6、 iterator指向操作的首元素，一个指向操作的首元素，一个last iterator标记标记指向操作的尾元素。如果找到了该值，返回该位指向操作的尾元素。如果找到了该值，返回该位置的置的iterator。iterator使用泛型算法，元素的访问和遍历都通过使用泛型算法，元素的访问和遍历都通过iterator实现。实际的容器类型可能是一个内实现。实际的容器类型可能是一个内置的数组，也可以能是一种容器类。为了支置的数组，也可以能是一种容器类。为了支持内置数组类型，普通指针以及持内置数组类型，普通指针以及iterator都可都可以被传递给泛型算法。以被传递给泛型算法。比如对普通的数组类型使用泛型算

7、法，泛型比如对普通的数组类型使用泛型算法，泛型算法中的算法中的find()函数定义在头文件函数定义在头文件“algorithm”中，因此需要引入该头文件。中，因此需要引入该头文件。在普通数组中使用泛型算法在普通数组中使用泛型算法#include#include#include using namespace std;void main()int search_value;int ia 6 =27,210,12,47,109,83;search_value=12;vector:iterator presult;presult=find(&ia0,&ia6,search_value);cout T

8、he value search_value(presult=&ia6?is not present:is present)endl;程序中，如果返回的指针等于程序中，如果返回的指针等于ia6的地址（即的地址（即ia末元素的下一位置），则查找失末元素的下一位置），则查找失败；否则，相应的值就被查到。败；否则，相应的值就被查到。泛型算法传递指针泛型算法传递指针通常，向泛型算法传递指针的时候，可以写通常，向泛型算法传递指针的时候，可以写成成nint*presult=find(&ia0,&ia6,search_value);或者不太明确地写成：或者不太明确地写成：nint*presult=find(i

9、a,ia+6,search_value);如果希望传递一个子范围，只需要修改传递如果希望传递一个子范围，只需要修改传递给算法的地址索引。给算法的地址索引。在在vector中使用泛型算法中使用泛型算法 例如，在例如，在find()的调用中，只查找第二个和第三个元素，注意元素从的调用中，只查找第二个和第三个元素，注意元素从0开始计数。开始计数。#include#include#include using namespace std;void main()int search_value;int ia 6 =27,210,12,47,109,83;vector vec(ia,ia+6);search

10、_value=20;vector:iterator presult;presult=find(vec.begin(),vec.end(),search_value);cout The value search_value(presult=vec.end()?is not present:is present)endl;在在list中使用泛型算法中使用泛型算法#include#include#include using namespace std;void main()int search_value;int ia 6 =27,210,12,47,109,83;list ilist(ia,ia+

11、6);search_value=20;list:iterator presult;presult=find(ilist.begin(),ilist.end(),search_value);cout The value search_value(presult=ilist.end()?is not present:is present)endl;2 几种常用的几种常用的iterator除了上面介绍的除了上面介绍的iterator，还有，还有n反向反向iteratorniostream_iteratornistream_iteratornostream_iterator。1、反向、反向iterat

12、or反向反向iterator的遍历方式同前向的遍历方式同前向iterator一样。不同一样。不同的是对于前向的是对于前向iterator，+操作访问容器中的下一操作访问容器中的下一个元素，对于反向个元素，对于反向iterator，它访问的是前面的元素。，它访问的是前面的元素。例如，反向遍历一个例如，反向遍历一个vector，可以这样编写。，可以这样编写。nvector :reverse_iterator r_iternfor(r_iter=vec.rbegin();/将将r_iter绑定到末元素绑定到末元素nr_iter!=vec.rend();/不等于首元素下一元素不等于首元素下一元素n r

13、_iter+)/递减递减iterator一个元素一个元素使用反向使用反向iterator#include#include#include using namespace std;void main()int ia 6 =27,210,12,47,109,83;vector vec(ia,ia+6);vector:reverse_iterator r_iter;for(r_iter=vec.rbegin();r_iter!=vec.rend();r_iter+)cout *r_iter endl;sort泛型算法泛型算法可以看出，程序将数组的元素倒序输出。如可以看出，程序将数组的元素倒序输出。如

14、果为了降序排列果为了降序排列vector，只需要简单地向，只需要简单地向sort()传递一对反向传递一对反向iterator，其中，其中sort也是泛型也是泛型定义的算法。定义的算法。nsort(vec.begin(),vec.end()/以升序排列以升序排列vectornsort(vec.rbegin,vec.rend()/以降序排列以降序排列vector使用反向使用反向iterator#include#include#include using namespace std;void main()int ia 6 =27,210,12,47,109,83;vector vec(ia,ia+6

15、);vector:iterator iter1;sort(vec.begin(),vec.end();cout 正序排列：正序排列：endl;for(iter1=vec.begin();iter1!=vec.end();iter1+)cout *iter1 ;sort(vec.rbegin(),vec.rend();cout endl 倒序排列：倒序排列：endl;vector:iterator iter2;for(iter2=vec.begin();iter2!=vec.end();iter2+)cout *iter2 ;cout endl;2、istream_iterator和和ostre

16、am_iterator标准库为输入和输出标准库为输入和输出iostream的的iterator提供了提供了支持，它们可以与标准库容器类型和泛型算法支持，它们可以与标准库容器类型和泛型算法结合起来工作。结合起来工作。分为两种分为两种iterator，一种是，一种是istream_iterator，另一种是另一种是ostream_iterator，为了使用这两种，为了使用这两种iterator，必须使用头文件，必须使用头文件“#include”。使用使用istream_iterator和和ostream_iterator#include#include#include#include using

17、namespace std;void main()istream_iterator input(cin);istream_iterator end_of_stream;vector vec;copy(input,end_of_stream,inserter(vec,vec.begin();sort(vec.begin(),vec.end();ostream_iterator output(cout,);unique_copy(vec.begin(),vec.end(),output);执行程序的时候，输入一些有重复的整数，要停止输入就输入一个字母，程序降排序执行程序的时候，输入一些有重复的整数，要停止输入就输入一个字母，程序降排序的结果显示出来，使用了的结果显示出来，使用了unique_copy所以将重复的数字全部去掉了所以将重复的数字全部去掉了 小结小结 C+程序结构初步，使用程序结构初步，使用C+语言编写语言编写简单代码简单代码 C+面向对象基础、构造与析构函数、面向对象基础、构造与析构函数、this指针以及指针以及const修饰符等修饰符等 C+模板的基本概念、函数模型和类模模板的基本概念、函数模型和类模板板 泛型算法的基本概念泛型算法的基本概念