第11章STL应用

1、第11章 STL应用 n11.1算法的综合应用n11.2在数据结构中的应用n11.3在Visual C+中应用11.1算法的综合应用 11.1.1在多态中的应用在多态中的应用 【例11.1】已知画图基类Shape，多态函数Draw，圆类Circle、正方形类Square都从其派生。创建一个含有Shape指针的vector，指向多个Shape对象，首先画出每个Squre，并按其长度进行升序排序；其次画出每个Circle，并按其半径进行升序排序。n程序代码#include #include #include using namespace std;class Shapepublic:virtual

2、 void Draw()=0;virtual int GetMark() = 0;class Circle:public Shape/圆类定义static int mark;/静态变量, Circle类标识float r;/半径public:float GetR() return r;public:Circle(float r) this-r = r ;virtual Circle() void Draw()cout 这是圆，半径是: r endl;int GetMark() return mark;bool operator(Circle& c) /排序比较用到此函数return r

3、 c.GetR();11.1.2 set,map应用【例11.2】一篇英文文本文件，要求：创建一个集合，保存文件中都出现了哪些单词；创建一个映射，保存单词及该单词在文件中出现的次数。#include #include #include #include #include #include #include #include using namespace std;class CWordstring word;public:CWord(string word)this-word = word;string GetWord()const return word;bool operator(cons

4、t CWord& w) const/用于添加集合用return word w.GetWord();bool operator=(const string& s)const /用于查询用11.1.3 INI文件解析【例11.3】利用STL解析INI文件 INI文件格式示例文件格式示例mydatabaseconnect=jdbc:odbc:mysrcuser=administratorpwd=123456mytabletablename=studenttablefields=studno,studname,age,birthdayn主要有三种元素：section ，key，valu

5、e。key-value也叫键值对，位于等号左右两侧。左侧叫做key，既关键码；右侧叫做值，它们是成对出现的。section是由中括号“”标识的。一个INI文件是由多个section组成的，一个section是由多个key-value键值对组成的。我们的任务就是把INI文件中的信息以一定的方式保存在程序结构中，代码如下所示。 n程序代码#include #include #include #include using namespace std;class MySectionstring section;/一个sectionmap mapKey;/由多个键值对组成public:MySection

6、(string section)this-section = section;bool AddKeyValue(string key, string value)/加key-value键值对函数pair p(key, value);mapKey.insert(p);return true;void Show(ostream& os)/显示section, 做测试用，看是否已保存到相应变量中os section endl;map:iterator it = mapKey.begin();while(it != mapKey.end()os t (*it).first = (*it).se

7、cond endl;it + ;n从语义上来说，一个section由多个key-value键值对组成，一个INI文件由多个section组成。因此前者与基本类MySection相对应，后者与MySection集合类MySectionCollect相对应。而ReadIni是读INI文件类，主要功能是根据INI配置文件填充MySectionCollect对象。【例11.4】已知4个文本文件：学生信息stud.dat，每行信息包括学号、姓名、年龄、性别；课程信息cour.dat，每行信息包括课号、课名；成绩信息grade.dat，每行信息包括学号、课号、成绩。编功能类，可以完成下述的查询功能。根据学

8、号查询，输出学号、姓名、课程名、成绩。哪些学生选了所有课程，输出其学号。查询每门课程的平均成绩，结果按平均成绩升序排列，平均成绩相同时，按课程号降序排列。查询每门课程最好的前两名同学的学号。11.1.4 综合查询11.2.1 全排列应用全排列应用【 例例 1 1 . 5 】 给 定 一 个给 定 一 个 n 个 整 数 的 集 合个 整 数 的 集 合X=x1,x2,xn和整数和整数y，找出和等于，找出和等于y的的X的 子 集的 子 集 Y 。 比 如 说 ： 如 果 ：。 比 如 说 ： 如 果 ：X=10,20,30,40,50,60，y=60。则有三种不。则有三种不同长度的解，它们分别是

9、：同长度的解，它们分别是：10,20,30，20,40，60。11.2在数据结构中的应用 n分析：X有6个元素，相对于3个解，可以用布尔向量表示为：1,1,1,0,0,0，0,1,0,1,0,0，0,0,0,0,01。值为1的部分是解中的元素。换一个说法就是：从6个数据中取1个，是否等于60？从6个数据中取2个数据，之和是否等于60？从6个数据中取6个数据，之和是否等于60？因此转化为从布尔向量0,0,0,0,0,1开始，到1,1,1,1,1,1结束，哪些是符合条件的布尔向量。那么如何变化布尔向量的取值呢？next_permutation就是一个比较好的选择。 【例11.6】八皇后问题。可以陈

10、述如下：如何在 8*8的国际象棋棋盘上安排8个皇后，使得没有两个皇后能互相攻击？如果两个皇后处在同一行、同一列或同一条对角线上，则它们能互相攻击。由此可推广到n皇后问题：有n个皇后和一个n*n棋盘，如何摆放能互相不攻击？ #include #include #include using namespace std;bool ValidOrder(int *start, int *end)int nSize = end - start;for(int i=0; inSize-1; i+)for(int j=i+1; jnSize; j+)if(j-i = abs(*(start+i)- *(st

11、art+j)return false;return true;void main()int a=1,2,3,4,5,6,7,8;don程序代码#include #include #include using namespace std;bool ValidOrder(int *start, int *end, int *s, int total)int nSize = end - start;int sum = 0;for(int i=0; inSize; i+)if(*(start+i)=1)sum += si;return sum = total;void main()int X = 10

12、,20,30,40,50,60;int y = 60;int n= sizeof(X)/sizeof(int);vector v(6);for(int k=0; k=0)fill(v.begin(), v.begin()+n-k-2,0);11.2.2 频度问题频度问题n【例11.7】求整形集合中各元素出现频度算法如下：1.设置整形数组A中元素, 获得元素个数N2.sort(A)3.初始化查询起始指针，firstA, lastNULL, 查询值find_value *first4.do5. lastupper_bound(first, A+nSize, find_value)6. 根据发fir

13、st, last查询起始指针显示查询元素及出现频度7. firstlast8. if first!= A+nSize then find_value*first9.while first!= A+nSize#include #include using namespace std;void main()int A = 1,3,2,3,4,3,6,3;int nSize = sizeof(A)/sizeof(int);sort(A, A+nSize);int *first = A;int *last = NULL;int find_value = A0;dolast = upper_bound(

14、first, A+nSize, find_value);cout find_value= find_value t频度: (float)(last-first)/nSize endl;first = last;if(first != A+nSize)find_value = *first;while(first != A+nSize);11.2.3 最长公共子序列问题最长公共子序列问题【例11.8】最长公共子序列问题即分别给出两个长度为n和m的字符串 A和B，确定在 A和B中最长公共子序列的长度及该串内容。例如A=“zxyxyz”，B=“xyyzx”，那么xyy同时是A和B的长度为3的子序列。

15、然而，它不是A和B最长的公共子序列，因为字符串xyyz也是A和B的公共子序列，长度是4。由于没有比4更唱的公共子序列，因此，A和B最长的公共子序列长度是4。解决这类问题很好的方法叫做动态规划方法。 11.2.4 大整形数加法、乘法类大整形数加法、乘法类#include #include #include #include #include using namespace std;class MyBigNumdeque v; /用deque容器表示大整数public:MyBigNum()MyBigNum(string strNum)/通过字符串建立大整数copy(strNum.begin(),

16、strNum.end(), back_inserter(v);transform(v.begin(),v.end(),v.begin(), bind2nd(minus(), 0);/字符1变成整数1要减去0deque:iterator begin()/迭代始指针return v.begin();deque:iterator end()/迭代止指针return v.end();int size()/容器大小return v.size();11.2.5 矩阵问题矩阵问题#include #include #include #include #include #include using names

17、pace std;templateclass MyMatrixpublic:vectorvector matrix;/二维矩阵向量public:MyMatrix(int m, int n):matrix(m, vector(n)MyMatrix(string s, int m, int n):matrix(m, vector(n)istringstream out(s); /解析字符串至矩阵向量char ch;/形如1 2 3, 4 5 6, 7 8 9for(int i=0; im; i+)for(int j=0; jmatrixij;out ch; 【例11.11】迷宫问题求迷宫中从入口到

18、出口的路径是一个经典的程序设计问题。即从入口出发，顺某一方向向前搜索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先处的栈结构来保存从入口到当前位置的路径。 11.2.6 回溯问题回溯问题n程序代码#include #include #include #include #include using namespace std;struct PathUnit /三元组结构int x;/坐标xint y;/坐标yint direct;/方位特征值。0东,1南,2西,3北;class MyMaze

19、vectorvector vecMaze;/迷宫描述矩阵vectorvector vecMark;/迷宫标志矩阵public:MyMaze(int m, int n):vecMaze(m+2, vector(n+2),vecMark(m+2, vector(n+2)for(int i=0; im+2; i+)fill(vecMazei.begin(), vecMazei.end(), 1);void InitMaze(string strMaze)/根据字符串建立迷宫矩阵n程序代码#include #include #include #include #include using namesp

20、ace std;class MyMaxCommonStringstring a;/字符串1string b;/字符串2vectorvector L;/两字符串二维动态规划表矩阵public:MyMaxCommonString(string s1, string s2):a(s1),b(s2),L(s1.length()+1, vector(s2.length()+1,0)int GetMaxLength()int row = L.size();int col = L0.size();return Lrow-1col-1; /L矩阵最后一个元素值是最大公共序列长度值string GetMaxCo

21、mmonString()string s = ;【例11.12】编一个功能类，能实现字符串表达式求值。表达式求值是程序设计语言中很重要的一个问题，它的实现是栈应用的典型例子，即“算符优先算法”。算术四则运算的规则是：先乘除，后加减；从左算到右；先括号内，后括号外。任何一个表达式都是由操作数、运算符和界限符组成的。本示例中为了简便起见，操作数采用符点常数，运算符限于+、-、*、/，界限符限于左右括号。11.2.7 字符串表达式字符串表达式字符串表达式头文件:class MyExpressstring m_strChars;/算符字符vectorvector m_vComp;/优先级比较矩阵pub

22、lic:MyExpress(string m_strChars,string strComps);bool GetUnit(string strExpress, int& pos, string& dest, bool& bOper);/返回每个操作符或操作数char CompareProc(char chStack, char ch);/优先级比较函数float Calc(float value1, float value2, char oper); /操作数运算函数float Process(string strExpress);/表达式处理函数;n程序代码#inc

23、lude #include #include #include #include using namespace std;class MyExpressstring m_strChars;/算符字符vectorvector m_vComp;/优先级比较矩阵public:MyExpress(string m_strChars,string strComps);bool GetUnit(string strExpress, int& pos, string& dest, bool& bOper);/返回每个操作符或操作数char CompareProc(char chSta

24、ck, char ch);/优先级比较函数float Calc(float value1, float value2, char oper);/操作数运算函数float Process(string strExpress);/表达式处理函数;MyExpress:MyExpress(string m_strChars,string strComps):m_vComp(m_strChars.length()-1, vector(m_strChars.length()this-m_strChars = m_strChars;/根据字符串创建比较矩阵istringstream in(strComps)

25、;for(int i=0; im_vComp.size()-1; i+)for(int j=0; jv = v, this-strDiscript = strDiscript;string GetNodeDiscript();/获得结点描述return strDiscript; ;n(2)边类template/DistType: 权重类型class MyEdge/边类int head, tail; /head: 边起始结点号，tail: 边结束结点号DistType weight;/权重public:MyEdge(int head, int tail, DistType weight)this

26、-head = head, this-tail = tail;this-weight = weight;int GetHead() return head;int GetTail() return tail;DistType GetWeight() return weight;bool operator = (int node)/为了stl find函数起作用return tail = node;bool operator(MyEdge& m)/为了sort排序起作用return weight m.GetWeight();n(3)一元函数类template class NodeComp

27、are /一元函数int value;public:NodeCompare(int value)this-value = value;bool operator()(MyEdge& m)return m.GetHead() = value;n(4)最小生成树类template class MyMinSpanTree/最小生成树类int vertices; /表明是多少点的最小生成树vectorMyEdge vec_Edge;public:MyMinSpanTree(int n) vertices = n;bool IsCircuit(int from, int to ); /判定回路b

28、ool Insert(MyEdge& e);p/插入最小边函数void Show()/显示最小生成树结果for(int i=0; ivec_Edge.size(); i+)cout vec_Edgei.GetHead() t vec_Edgei.GetTail() t vec_Edgei.GetWeight() endl;n(5)图功能类template class MyGraph /图功能类private:vector vec_vertices;/顶点集合vectorvector vec_matrix; /邻接矩阵 public:MyGraph(string strNodes, st

29、ring strMatrix,int nSize);bool GraphEmpty()return vec_vertices.empty();int NumberOfVertices()return vec_vertices.size();DistType GetWeigth(int v1, int v2)/得出v1-v2边权值return vec_matrixv1v2;int GetFirstNeighbour(int v); /给出v的第1个邻接顶点的位置int GetNextNeighbour(int v1, int v2);/给出v1的某邻接顶点v2的下一个邻接顶点void DFS(i

30、nt start);/从某点开始进行深度优先搜索void DFS(int v, vector& visit);void BFS(int v);/广度优先搜索void Kruskal(MyMinSpanTree& t);/克鲁斯卡尔最小生成树算法void Show()/显示图的邻接矩阵for(int i=0; ivec_matrix.size(); i+)copy(vec_matrixi.begin(), vec_matrixi.end(), ostream_iterator(cout, t);cout endl;n程序代码#include #include #include #

31、include using namespace std;class MyNode/结点类int v;/结点号,关键字,不重复string strDiscript;/结点描述public:MyNode(int v, string strDiscript)/构造函数this-v = v, this-strDiscript = strDiscript;string GetNodeDiscript()/获得结点描述return strDiscript; ;template/DistType: 权重类型class MyEdge/边类int head, tail; /head: 边起始结点号，tail:

32、边结束结点号DistType weight;/权重public:MyEdge(int head, int tail, DistType weight)this-head = head, this-tail = tail;this-weight = weight;nVisual C+提供了强大的功能，深受编程者喜爱。但其庞大而复杂的类库也使学多人望而却步，那么如果在Visual C+中运用STL，就能少学许多MFC类库，具体体现在：11.3在Visual C+中应用 n(1)STL string类可代替 MFC CString: 对每种程序开发包而言，字符串编程都是最重要的功能，不同字符串类库尽

33、管功能是非常相似的，但是熟悉函数名写法及参数类型，都是一项长期的工作。如果你熟悉了STL string类，那么就省去了这份工作。而且STL中还有关于字符串流的操作，功能更强大。n(2)STL 文件操作ifstream、ofstream、fstream可以代替关于文件的 CFile类。n(3)STL基本序列容器(vector,list,queue,stack)及关联容器（set,map）可代替MFC中有关容器的模板类。MFC中容器模板类有：CArray, CList, CMap, CTypedPtrAarray, CTypedPtrList,CtypedPtrMap。n(4)当然 STL还能代替

34、许多其它的MFC非模板类，如CByteArray、CDWordArray、CPtrList等，总之那些与GUI无关的类都可能由STL代替。n(5)如果在MFC中应用了STL, 那么就可以应用强大的STL算法。n【例11.14】MFC Scribble程序Scribble程序是MSDN中一个著名的MFC例子，是一个小绘图应用程序,它允许用鼠标绘制徒手画并将图像保存在文件中， 11.3.1 Scribble绘图程序绘图程序n分析:关键问题有两点：n（1）用鼠标写了“三”字，应该用3笔写完，那么在程序中如何标识一笔呢？我们规定：当鼠标左键按下时，是一笔开始，鼠标左键抬起时是一笔的结束，中间拖动过程完

35、成绘制过程，因此应该响应视图类的WM_LBUTTONDOWN、WM_LBUTTONUP、WM_MOUSEMOVE；n（2）完成一笔绘制应该是多个点的集合，应该有一个基础类能体现出语义“一笔有多个点”，假设类名是CStroke, Stroke汉语是“一笔、一划”意思，内部应该有一个vector成员变量，CPoint是VC提供的一个系统类，成员变量有x,y,因此可表示一个点的坐标。主要头文件（程序源码见chap11/myscribble）n(1)CStroke“笔”类class CStroke public:CStroke();virtual CStroke();public:vector m_p

36、ointArray; /一笔有多个点public:void NewPoint(CPoint pt);/新加一个点void DrawStroke(CDC *pDC);/划这“一笔”void LoadStroke(CArchive& ar);/从文件中读“一笔”void SaveStroke(CArchive& ar);/向文件中存“一笔”;n（2）文档类#include Stroke.hclass CMyScribbleDoc : public CDocumentprotected: / create from serialization onlyCMyScribbleDoc()

37、;DECLARE_DYNCREATE(CMyScribbleDoc)public:vector m_strokeList; /一文档由多一文档由多“笔笔”组成组成public:void NewStroke();/往当前往当前“笔笔”中新增一个结点中新增一个结点CStroke* GetNewStroke();/获得当前获得当前“笔笔”对象对象void DrawStrokes(CDC *pDC);/画文件中所有画文件中所有“笔笔”void LoadStrokes(CArchive& ar);/读文件中所有读文件中所有“笔笔”void SaveStrokes(CArchive& ar

38、);/存文件中所有存文件中所有“笔笔”/ ClassWizard generated virtual function overrides/AFX_VIRTUAL(CMyScribbleDoc)public:virtual BOOL OnNewDocument();virtual void Serialize(CArchive& ar);virtual void DeleteContents();/删除容器指针元素删除容器指针元素/AFX_VIRTUAL/ Implementationpublic:virtual CMyScribbleDoc();#ifdef _DEBUGvirtua

39、l void AssertValid() const;virtual void Dump(CDumpContext& dc) const;#endifprotected:/ Generated message map functionsprotected:DECLARE_MESSAGE_MAP();【例11.15】数据库表解析程序11.3.2 数据库操作程序数据库操作程序完成功能是：初始化时左侧列表框显示某数据库的所有表名。当用鼠标双击该列表框某表名时，右侧列表控件在表头处显示该表各字段的属性名称，在数据区显示该表的所有记录信息。 n为了简化起见，建立一个ACCESS数据库，在库中建立

40、几个表，并在控制面板ODBC数据源管理器进行注册（可把chap11/db1.mdb注册），假设名称为mysrc。n程序源码见chap22/MyDB 【例11.16】文本文件数据排序、查询程序所用文本文件是关于学生基本信息的，包括学号、姓名、年龄、性别四项，一行代表一个学生记录，记录中各项间以空格隔开 。11.3.3 文本文件排序、查询程序文本文件排序、查询程序n完成功能是：当按打开文件按钮，弹出CfileDialog文件选择对话框，当选择完本件后，按确定按钮后出现图10-1界面；排序功能。当按图10-1中listctrl控件表头中某项时，例如若按姓名时，则表中数据显示按姓名升序排列；查询功能。可按学号查询，当按此按钮后，出现学号查询对话框，在编辑框中输入查询的学号。有两种输入方式，对应两种查询类型。一种是如“1001，1003，1005”，一种是如“1001-1003”。前者表明查询1001，1003，1005学号的学生信息，后者表明是范围查询，查询学号从1001到1003所有学号的学生信息。n本例展示如何在MFC中应用STL排序，查询算法。n本例源码见chap11/MyInfo11