C++程序设计案例实训教程第14章

时间:2022-08-31 19:05:03

14章  标准模板库

(本资料qq讨论群112133686)

C++语言提供的标准模板库(Standard Template Library,STL)是面向对象程序设计与泛型程序设计(Generic Programming)思想相结合的一个良好典范。C++标准库中容器类可以方便地存储和操作群体数据,用好C++标准库可以大大提高程序的开发效率。本章介绍了与C++标准库有关的几个基本术语:容器、容器适配器、迭代器、迭代器适配器、通用算法、函数对象和函数适配器,详细介绍了几种可以用于处理线性群体的容器:向量、双端队伍、 和适配器、标准栈、标准队伍和优先队伍。详细介绍4种通用算法以及迭代器和函数对象的应用,并给出了相应的实例。

标准库中给出了很多的算法,为了使读者能够很好地了解和应用这些算法,本章给出了通用算法的函数功能说明。学会使用这些算法可以有效地缩短程序的开发周期,提高程序的效率。本章重点讲解了这些模板库的使用,于初学者在以后编程中经常遇到,反复多实践,使用好这些模板库可事半功倍提供编程效率,缩短开发周期。

14.1 理解STL编码时的防错

STL程序设计中,容器(container)就是通用的数据结构。容器用来承载不同类型的数据对象,就如同现实生活中,人们使用容器用来装载各种物品一样。但C++中的容器还存在一定的“数据加工能力”,如同一个对数据对象进行加工的模具,可以把不同类型的数据放到这个模具中进行加工处理,形成具有一定共同特性的数据结构。

案例14-1  使用STL库创建容器

【案例描述】

例如将int型、char型或者float型放到队列容器中,就分别生成int型队列、char型队列或者float型队列,它们都是队列具有队列的基本特性,但是具体的数据类型是不一样的。本例效果如图14-1所示。

 

14-1  使用STL库创建容器

【实现过程】

程序定义list容器list1,把字符数组x[7]的值赋给list1,反转链表list1,遍历list1,输出list1每个元素的值。代码实现如下:

#include <iostream>

#include <cassert>

#include <list>

#include <algorithm>   //reverse函数头文件

using namespace std;

int main()

{

  char x[7] = {'a', 'b', 'c', 'd', 'e','f','g'};

  list<char> list1(&x[0], &x[7]);//list对象的声明构造

  reverse(list1.begin(), list1.end()); //reverse()反转链表

  list<char>::iterator i;

  cout.precision(10); //设置精度

  for (i = list1.begin(); i != list1.end(); ++i) //begin返回第一个元素的指针,end返回最后一个元素的下一位置的指针(list为空时end()=begin())

  cout << *i << endl; //打印容器元素

  cout << endl;

  system("pause");

  return 0;

}

【案例分析】

1)上述代码用list创建一个列表list1。在STL程序设计中,容器就是通用的数据结构。STL容器主要包括向量(vector)、列表(list)、队列(deque)、集合(set/ multiset)和映射(map/multimap)等。在STL中容器大致可以分为两类:顺序容器和关联容器。

2STL中的所有容器都是类模板,是一个已经建立完成的抽象的数据结构。

 

提示:可以使用容器来存储任何类型的数据,甚至是自己定义的类,而无需自己再定义数据结构。例如利用deque容器,就很容易建立一个队列。

案例14-2  裁员计划——获取、、删除和清空容器

【案例描述】

STL通过采用C++模板机制实现了算法与数据类型的无关性。目的是为了支持通用程序设计,STL实现了算法与容器(数据结构)的分离。本实例定义容器,实现数据类型和算法如移除等分离。本例效果如图14-2所示。

 

14-2  裁员计划——获取、删除和清空容器

【实现过程】

定义容器vec_A,填充8个数据元素'A',从第3个元素用4'B'代替,统计数据元素;移除数据元素'A';移除所有元素,清空容器vec_A。代码实现如下:

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

template<class T>

void print(T &con) //输出容器中所有元素

{

  if(con.empty())

         cout<<"Container is empty!"<<endl;

  else

  {

  T::iterator it; //设置迭代器

  for(it=con.begin(); it!=con.end();it++) //遍历容器

  {

cout<<*it<<" "; //显示容器元素的值

      }

  cout<<endl;

  }}

int main()

{

  int num;

  vector<char> vec_A(8);          //定义容器vec_A

  cout<<"Fill vec_A with 'A':"<<endl;  

  fill(vec_A.begin(),vec_A.end(),'A');            //填充数据元素

  char array_B[]={'B','B','B','B',};

  vector<char> vec_B(array_B,array_B+4);        //定义容器vec_A,并初始化

  copy(vec_B.begin(),vec_B.end(),vec_A.begin()+2);//复制数据元素

  print(vec_A);     //输出容器中所有元素

  cout<<"Copy element of vector to vec_A:"<<endl;

  num=count(vec_A.begin(),vec_A.end(),'B');      //统计数据元素

  cout<<"Counting the number of 'B' in vec_A:"<<endl;

  cout<<num<<endl;

  vector<char>::iterator it;

  it=remove(vec_A.begin(),vec_A.end(),'A');     //移除数据元素

  vec_A.erase(it,vec_A.end());                  //删除数据元素

  print(vec_A);     //输出容器中所有元素

  vec_A.clear();     //移除所有元素,清空容器

  print(vec_A);     //输出容器中所有元素

  system("pause");

  return 0;

}

【案例分析】

1)算法(algorithm)就是指一些常用的数据处理方法,如向容器中插入、删除容器中的元素、查找容器中的元素、对容器中的元素排序、复制容器中的元素等,这些数据处理方法都是以函数模板的形式实现的。

2)算法之美就在于不仅独立于底层元素的类型,而且也独立于所操作的容器。利用这些已经定义的算法和迭代器,程序员可以方便灵活地存取容器中存储的各种数据元素。 在STL中,算法的神奇之处在于:算法并非容器的一部分,而是工作在迭代器基础之上,通过迭代器这个“中间人”存取容器中的元素,算法并没有和特定的容器进行绑定。

 

提示:在传统的软件开发方法中,算法与数据类型、数据结构是紧密耦合的,缺乏通用性。而STL倡导泛型编程风格,即以通用的方式来编写程序。

案例14-3  图书印刷——复制元素并自动输出

【案例描述】

有容器ab,分别存有元素,如何把容器a的元素复制到容器b。如一个list容器中的元素复制到另一个已有元素的vector容器。本例效果如图14-3所示。

 

14-3  图书印刷——复制元素并自动输出

【实现过程】

这是两个演示,演示一把list容器的元素复制到另一个list容器中,演示二把一个list容器中的元素复制到另一个已有元素的vector容器的后面。其代码如下:

#include <iostream>

#include <list>

#include <deque>

using namespace std;

int main()

{

list<int> a;//list容器

list<int> b;

int i;

for (i=0; i < 30; ++i, a.push_back(i));   //在容器后端增加元素

std::list<int>::iterator rit = a.begin(); //返回容器前端的迭代器

std::list<int>::iterator rend = a.end(); //返回容器末端的迭代器

for(++rit;rit != rend;++rit)   //遍历容器b

b.push_back(*rit); //插入b

rit=b.begin(); //返回容器前端的迭代器

rend=b.end(); //返回容器末端的迭代器

for(;rit != rend;++rit)                   //遍历容器b

cout << *rit << ", ";

//显示容器元素的值

system("pause");

list<int> ilst ; //list容器

deque<int> oddDq , evenDq ;            //deque容器

int val = 0 ;

cout << "Please input the value : " << endl ;//输入一个值

while (cin >> val)

{

ilst.push_back(val) ; //插入list容器ilst

}

for (list<int>::iterator iter = ilst.begin() ; iter != ilst.end() ; iter ++)//遍历list容器ilst

{

if (*iter % 2) //如果是奇数

{

 oddDq.push_back(*iter) ; //插入deque容器到oddDq

}

else

evenDq.push_back(*iter) ; //插入deque容器到evenDq

 }

 for (deque<int>::iterator dter = oddDq.begin() ; dter != oddDq.end() ; dter ++)//遍历oddDq

{

cout << *dter << " " ; //显示容器元素的值

}

system("pause");

return 0;

}

【案例分析】

1)代码中演示了把list容器的元素复制到另一个list容器中,一个vector容器中的元素复制到另一个已有元素的vector容器的后面。

2insert()操作可以加入iterator范围的元素,如vector(向量)、list(列表)push_back()

 

提示:运用C++语言的STL时记住一句话,99%的情况不需要写for循环。如相同类型的vector a, b;,就可以编程为:a.insert(a.end(), b.begin(), b.end());

14.2  使用序列式容器

案例14-4  学生成绩转换为标准分(向量增长)

【案例描述】

向量容器灵活性在于定义向量容器后随时可以增加元素。本实例演示的是输入学生成绩计算标准分,因输入的数据长度是未知的,具有向量增长特性,这方面特性以后可以应用很广,不需要初始化内存。本例效果如图14-4所示。

 

14-4  学生成绩转换为标准分(向量增长)

【实现过程】

学生的成绩一般是原始成绩,要将学生的成绩转换为标准分,必须首先比较所有学生的成绩,取得最高分,将学生原始成绩除以最高分,然后乘上100。代码实现如下:

#include<iostream>

#include<vector>

using namespace std;

int main(){

  vector<double>  scorevector; //创建向量

  double max,temp; //最高分,暂存分数

  int i;

  cout<<"Input -1 to stop:"<<endl;

  cout<<"Enter the original score 1: ";

  cin>>max;                              //取得输入分数

  scorevector.push_back(max); //在容器后端增加元素

  for(i=1;true;i++) {                    //一直循环下去

     cout<<"Enter the original score "<<i+1<<": ";

   cin>>temp;

   if(temp==-1){                         //输入-1

  break;

}

   scorevector.push_back(temp); //在容器后端增加元素

   if(temp>max)                          //输入大于最高分

  max=temp;

  }

  max/=100;                              //同于max=max/100;

  cout<<"Output the standard scores: "<<endl;

  for(i=0;i<scorevector.size();i++) { //遍历向量

    scorevector[i]/=max;                 //同于scorevector[i]=scorevector[i]/max

    cout<<scorevector[i]<<" ";           //输出标准分

  }

 cout<<endl;

 system("pause");

 return 0;

}

【案例分析】

push_back()在容器后端增加元素。由于代码中没有给出学生人数,所以采用向量作为数据存储结构,因为向量的元素个数可以自动实现动态增长。

案例14-5  打印容器元素的值

【案例描述】

顺序容器可以用于存储线性表类型的数据结构,编程时候需要知道容器中较为重要的成员函数,list容器是一个标准双向链表。本例打印list容器元素的值,效果如图14-5所示。

 

14-5  打印容器元素的值

【实现过程】

程序主要是一个打印容器元素的值的函数PRINT_ELEMENTS(),输入一个容器的名称,返回第一个元素的指针,函数end()返回最后一个元素的下一位置的指针。代码实现如下:

#include <iostream>

#include <list>

#include <algorithm>

using namespace std;

template <class T>

//打印容器元素的值

inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="")

{

    typename T::const_iterator pos;

    std::cout << optcstr;

//begin返回第一个元素的指针,end返回最后一个元素的下一位置的指针(list为空时end()=begin())    for (pos=coll.begin(); pos!=coll.end(); ++pos) {

        std::cout << *pos << ' '; //打印容器元素

    }

    std::cout << std::endl;

}

int main()

{

    list<int> coll; //list对象的声明构造

    // insert elements from 1 to 8

    for (int i=1; i<=8; ++i) {

        coll.push_back(i); //增加一元素到链表尾

    }

    PRINT_ELEMENTS(coll,"initialized:                ");

system("pause");

}

【案例分析】

1)上述代码begin()返回第一个元素的指针,end()返回最后一个元素的下一位置的指针(list为空时end()=begin());push_back()增加一个元素到链表尾。

2list容器是一个标准双向链表,每个元素都知道其前一个与下一个数据元素,查找速度较慢,只能根据链表指针的指示逐一查找,但一旦找到相关位置,完成元素的插入和删除则很快。

案例14-6  一个简单的学生管理系统

【案例描述】

这是个综合的实例,目的是加深对顺序容器如vector和类函数理解及综合应用,编写软件目的大部分是信息处理,这是一个雏形的小型信息处理系统,本实例是个简单的学生管理系统管理方面的小软件,涉及到向量,通过输入如姓名信息进行查询。本例效果如图14-6所示。

 

14-6  一个简单的学生管理系统

【实现过程】

1)定义个学生类Cstudent,基于CStudent创建vector对象classes1,定义类函数输入学生信息inputStudentInfo、查找学生信息findStudent。其代码如下:

#include<iostream>

#include <vector>

using namespace std;

#ifndef STUDENTh

#define STUDENTh

#include<string>

using namespace std;

class CStudent //学生类

{

private:

 string strName; //姓名

 double chinese; //语文

 double math; //数学

 double english; //英语

public:

 CStudent();

 CStudent(std::string Name,double c,double m,double e);

    void SetChinese(double a); //输入语文成绩

 void SetMath(double a); //输入英语成绩

 void SetEnglish(double a); //输入数学成绩

 void SetName(std::string  c); //输入姓名

 std::string  returnName();           

 double returnChinese(); //返回语文成绩

 double returnMath(); //返回数学成绩

 double returnEnglish(); //返回英语成绩

 double returnTotalPerformance(); //返回总成绩

 double returnAverage(); //返回平均分

 ~CStudent(){} //析构函数

};

#endif

 

CStudent::CStudent() //构造函数

{

strName="General Student"; //初始化

chinese=0;

math=0;

english=0;

}

CStudent::CStudent(std::string Name,double c,double m,double e)//类赋值

{

strName=Name;

chinese=c;

math=m;

english=e;

}

void CStudent::SetChinese(double a){chinese=a;} //输入语文成绩

void CStudent::SetEnglish(double a){english=a;} //输入英语成绩

void CStudent::SetMath(double a){math=a;} //输入数学成绩

double CStudent::returnChinese (){return chinese;}//返回语文成绩

double CStudent::returnEnglish (){return english;}//返回英语成绩

double CStudent::returnMath (){return math;} //返回数学成绩

double CStudent::returnTotalPerformance(){return chinese+math+english;}//返回总成绩

double CStudent::returnAverage (){return (chinese+math+english)/3;}//返回平均分

string CStudent::returnName (){return strName;} //返回姓名

void CStudent::SetName (std::string c){strName=c;}

void inputStudentInfo(std::vector<CStudent>& vec);

int findStudent(std::vector<CStudent>& vec ,

    std::vector<CStudent>::iterator& it ,

    std::string str);

void inputStudentInfo(std::vector<CStudent>& vec) //输入学生信息

{

//代码略

}

int findStudent(std::vector<CStudent>& vec ,

    std::vector<CStudent>::iterator& it ,

    std::string str) //查找学生信息

{

 for( it=vec.begin() ; it != vec.end() ; it++ ) //遍历vec

 {

  if(str == (*it).returnName()) //查找相同的姓名

  {

   return 1 ; //查找到,返回1

   break ;

  }

 }

 it = NULL ;

 return 0 ; //未查找到返回0

}

2)基于CStudent创建vector对象classes1,输入学生信息,根据姓名查找学生信息,输出记录号、姓名和总成绩。代码如下:

int main()

{

 std::vector<CStudent> classes1; //基于CStudent创建vector对象classes1

 std::vector<CStudent>::iterator iter ;

 inputStudentInfo(classes1); //输入学生信息

 std::cout<<"Enter the name you want to check : " <<std::endl;

 char a[20];

 std::cin>>a;

 if(findStudent(classes1,iter,a)) //查找学生信息

 {

  std::cout<<iter->returnName()<<" performance : \n"

   <<"Chinese : "<<iter->returnChinese()

   <<"\nMath : "<<iter->returnMath()

   <<"\nEnglish : "<<iter->returnEnglish()<<std::endl;

 }

 else

 {

  std::cout<<"No found!\n";

 }

 int i ;

 std::cout<<"All students' performance descend by total performance :\n" ;

 //遍历iter

 for( iter = classes1.begin() , i = 1 ; iter != classes1.end() ; iter++ , i++ )

 {

  std::cout<<"The rank "<<i<<" is : "<<std::endl; //记录后

  std::cout<<iter->returnName()<<std::endl; //姓名

  std::cout<<iter->returnTotalPerformance()<<std::endl; //返回总成绩

 }

 system("pause");; //按任意键退出

 return 0 ;

}

【案例分析】

1)这是个简单的学生管理系统,根据输入的信息例如姓名等进行查询。设计顺序容器vector存储学生信息,根据姓名实现快速查询。

2vector函数begin()end()返回第一个元素、最后一个元素的指针,push_back()pop_back()在容器后端增加、删除元素。

 

提示:在此代码的基础上可以增加其他维护功能:例如插入、删除、修改等,按成绩进行排序等。

案例14-7  编写一个简单的计算器

【案例描述】

这是个综合的实例,目的是加深对顺序容器如vector(向量),容器适配器如stack(栈)和类理解及综合应用。灵活运用这些概念,可把现实生活中的事务用程序来实现,本实例演示计算器的程序,涉及到向量、容器适配器如栈、类等概念,运行效果如图14-7所示。

 

14-7  编写一个简单的计算器

【实现过程】

1)定义个类calculator,定义向量s存储计算表达式,栈symbol、result处理数字和运算符号。其代码如下:

#include<iostream>

#include<cstdlib>

#include<vector>

#include<stack>

#include<cmath>

using namespace std;

class calculator

{

private:

   vector<char>s; //vector容器

   stack<char,vector<char> >symbol; //栈(stack),容器适配器

   stack<char,vector<double> >result;

   vector<char>number;

public:

   int compare(char m)

   {

switch(m)

{

case '*':

case '/':

return 2;break;

case '+':

case '-':

return 1;break;

default:return 0;break;

}

   }

   void InputNumbers() //输入计算的表达式

   {

     //代码略

  }

   void OutputResult() //输出计算的表达式

   {

        //代码略

};

2)主函数定义个计算器类,调用输出计算的表达式函数。代码如下:

int main()

{

 char m='y';

 while(m=='y' || m=='Y')

 {

 calculator cal; //定义类

 cal.InputNumbers(); //输入计算的表达式

 cal.OutputResult(); //输出计算的表达式

 cout<<"是否继续计算【Y/N";

 m=getchar();m=getchar();

 }

}

【案例分析】

1)这是一个简单的计算器程序,根据用户输入计算表达式进行计算。代码是把数字和计算符号存储在栈中的。

2)代码主要对vector(向量),容器适配器如stack(栈)和类的理解和运用。push()进栈,symbol.pop()取栈顶元素;输入计算的表达式InputNumbers()分别把数字和计算符号入栈,再一个个取栈顶元素。输出计算的表达式OutputResult()对数字入栈和运算符号栈取栈顶元素,进行计算。

 

提示:在此代码的基础上可以增加计算器其他计算功能如平方、开方等。

案例14-8  一个经典的压缩算法

【案例描述】

游戏、音频、视频及图片等占据空间太大,在上传互联网的时候必须压缩,下载该文件后进行相应的解压缩才能运行。压缩的算法很多:字典算法、固定位长算法、RLE算法、LZ77算法等等。本实例演示的是经典的压缩算法Huffman算法,效果如图14-8所示。

 

14-8  一个经典的压缩算法

【实现过程】

压缩成员函数,遍历输入的strs每个字符,调用_encode_single(),进行压缩,把压缩结果插入容器。代码实现如下:

//以下为辅助类

template<typename T>

class will_delete{

 public:

will_delete(T* ptr){p= ptr;}

     operator T*(){return p;}

     T* operator->(){return p;}

T* p;

};

template<typename T>

class vtree{ //存储HuffmanTree的类

public:

vtree(){val=0;}

     vtree(will_delete<T> data){val= data;}

     ~vtree(){

         for(size_t i=0; i<_list.size(); i++) delete _list[i];

         delete val;

     }

     bool leaf()const{return _list.empty();}  //是否为空

     vector<vtree<T>*> _list;

     T* val;

 };

 //辅助类结束

 struct huffman_node{

     huffman_node(string st, size_t w){s=st;wight=w;}

     string s;

     size_t wight;

 };

 //辅助函数

 bool vtree_huffman_node_ja(vtree<huffman_node>* a, vtree<huffman_node>* b){

     return  a->val->wight > b->val->wight;

 }

 class huffman_rule{

 public:

     huffman_rule(vector<huffman_node>& data){

         for(size_t i=0; i<data.size(); i++)

             encode._list.push_back(new vtree<huffman_node>( new huffman_node (data[i].s,data[i].wight) )); //在容器后端增加元素

         while(encode._list.size()> 2){

             sort(encode._list.begin(), encode._list.end(), &vtree_huffman_node_ja); //排序算法

             vtree<huffman_node>* min1= encode._list.back();

             encode._list.pop_back(); //在容器后端删除元素

             vtree<huffman_node>* min2= encode._list.back();

             encode._list.pop_back();   //在容器后端删除元素

             encode._list.push_back(join(min1,min2));//在容器后端增加元素

         }

         size_t wight=0;

         switch(encode._list.size()){

         case 2:wight+=encode._list[1]->val->wight;

         case 1:wight+=encode._list[0]->val->wight;

         default:;

         }

         encode.val= new huffman_node("", wight);

     }

     vtree<huffman_node>* join(vtree<huffman_node>* a, vtree<huffman_node>* b){

         vtree<huffman_node>* ret= new vtree<huffman_node>(new huffman_node ("",a->val->wight+b->val->wight));

         ret->_list.push_back(a);    //在容器后端增加元素

         ret->_list.push_back(b);    //在容器后端增加元素

         return ret;

     }

     vector<bool> find_symbol(vtree<huffman_node>* ptree, string& symbol){

         if(ptree->leaf() && ptree->val->s==symbol) return vector<bool>();

     }

     vector<bool> encode_string(const vector<string>& strs){ //压缩函数

     //代码见212

     }

     vector<string> decode_bool(vector<bool>& code){ //解压函数

  //代码见213

     }

 private:

     //压缩函数         //代码见212

     static vector<bool> _encode_single(const vtree<huffman_node>& obj, const string& str){       }

     static string _decode_single(const vtree<huffman_node>& obj, vector<bool>::iterator& pbit, vector<bool>::iterator pend){           //代码见212   };

int _tmain(int argc, _TCHAR* argv[])  {  //代码略  }

【案例分析】

1)霍夫曼编码针对文本文件的一种压缩算法,基于统计编码的算法,属于无损压缩编码。其码长是变化的,出现频率高编码的长度较短;频率低编码长度较长。这样,处理全部信息的总码长一定小于实际信息的符号长度。

2)上面代码insert()在容器中间插入元素,rbegin()返回容器前端的倒转迭代器,rend()返回容器末端的倒转迭代器,push_back()在容器末尾增加新元素。

案例14-9  自定义函数实现数据压缩

【案例描述】

本实例代码见实例14-8Huffman是一种无损失的压缩算法,是文字或软件文档的最理想压缩方式,现在很流行的压缩软件如ZIPARJ都使用它。本例演示Huffman编码实现,效果如图14-9所示。

 

14-9  自定义函数实现数据压缩

【实现过程】

定义压缩函数encode_string(),遍历输入的待压缩的strs字符,调用压缩函数_encode_single(),递归调用_encode_single(),把压缩内容插入容器。代码实现如下:

    vector<bool> encode_string(const vector<string>& strs){ //压缩函数

         vector<bool> ret,temp;

         for(size_t i=0; i< strs.size(); i++){ //遍历strs字符

             temp= _encode_single(encode, strs[i]);

             ret.insert(ret.end(), temp.rbegin(), temp.rend()); //在容器中间插入元素

         }

         return ret;

     }

……

private:

//压缩函数

     static vector<bool> _encode_single(const vtree<huffman_node>& obj, const string& str){

         vector<bool> ret;

         if(obj.val->s==str){

             ret.push_back(true);    //返回值会被删除 只是表明找到了

             return ret;

         }

         for(size_t i=0; i<obj._list.size(); i++){

             ret= _encode_single(*obj._list[i], str); //压缩函数

             if(ret.size()){

                 if(obj._list[i]->leaf()) ret.pop_back(); //删除标识已找到的符号

                 ret.push_back(i==0?0:1); //在容器后端增加元素

                 return ret;

             }

         }

         ret.clear();    //清除容器内的元素

         return ret;

     }

【案例分析】

Huffman编码过程的几个步骤:

1)将信号源的符号按照出现概率递减的顺序排列。

2)将最下面出现的两个最小概率进行合并相加,得到的结果作为新符号的出现概率。

3)重复进行步骤12直到概率相加的结果等于1为止。

4)在合并运算时,概率大的符号用编码0表示,概率小的符号用编码1表示。

5)记录下概率为1处到当前信号源符号之间的0l序列,从而得到每个符号的编码。

案例14-10  自定义函数实现数据解压

【案例描述】

本实例代码见实例14-8。解码是编码的逆过程,即是根据码字查询Huffman码表,还原出初始值。本例演示Huffman解码实现,效果如图14-10所示。

 

14-10  自定义函数实现数据解压

【实现过程】

解码是编码的逆过程,即是根据码字查询Huffman码表,还原出初始值。其代码如下:

    vector<string> decode_bool(vector<bool>& code){ //解压函数

         vector<string> ret;

//定义了迭代器ibegin()返回指示容器中第一个元素

         vector<bool>::iterator i= code.begin();

         while(i!= code.end()){    //遍历

             ret.push_back(_decode_single(encode, i, code.end()));//在容器后端增加元素

         }

         return ret;

     }

……

 //解密

     static string _decode_single(const vtree<huffman_node>& obj, vector<bool>:: iterator& pbit, vector<bool>::iterator pend){

         while(!obj.leaf()){ //遍历直到叶节点

             bool path= *pbit;

             if(pbit!=pend){

                 pbit++;

             }else{

                 return ""; //返回值

             }

             return _decode_single(path==0?*obj._list[0]:*obj._list[1], pbit, pend); //递归

         }

         return obj.val->s; //返回值

     }

     vtree<huffman_node> encode;

 };

【案例分析】

霍夫曼编码具有如下特点:

1)编出来的码都是异字头码,保证了码的唯一可译性。

2)由于编码长度可变,使得译码时间较长,这样采用霍夫曼编码的压缩与还原相当费时。

3)编码长度不统一,硬件实现有难度。

4)对不同信号源的编码效率不同,当信号源的符号概率为2的负幂次方时,达到100%的编码效率;若信号源符号的概率相等,则编码效率最低。

5)由于01指定是任意的,故由上述过程编出的最佳码不是唯一的,但其平均码长是一样的,故不影响编码效率与数据压缩性能。

 

提示:解压是压缩的反过程,算法的实现过程正好相反。

案例14-11  高效倍增算法

【案例描述】

C++algorithmsort算法简单方便,可用来排序容器的内容,输入的值往往是默认的值,程序运行中能自动识别默认值。本例演示的是倍增算法,效果如图14-11所示。

 

14-11  高效倍增算法      

【实现过程】

主函数调用buildSA()buildSA()调用函数getLCP()cSort()实现排序算法的功能。代码实现如下:

#include <algorithm> //sort函数头文件

#include <cstring> //memset函数头文件

using namespace std;

const int MAX_SFX = 210000;

struct Sfx { //定义结构

    int i;  int key[2];

    bool operator < (const Sfx& s) const

    {   return key[0] < s.key[0]

|| key[0] == s.key[0] && key[1] < s.key[1]; } //||)逻辑或,(&&)逻辑与

};

int g_buf[MAX_SFX + 1];

Sfx g_tempSfx[2][MAX_SFX], *g_sa = g_tempSfx[0];

//基数排序

void cSort(Sfx* in, int n, int key, Sfx* out) {

    //cnt 中前 sizeof(int) * (n + 1) 个字节用 0 替换并返回 cnt

    int* cnt = g_buf;  memset( cnt, 0, sizeof(int) * (n + 1) );

    for (int i = 0; i < n; i++) { cnt[ in[i].key[key] ]++; }

    for ( i = 1; i <= n; i++) { cnt[i] += cnt[i - 1]; }

    for ( i = n - 1; i >= 0; i--)

        { out[ --cnt[ in[i].key[key] ] ] = in[i]; }

}

//创建字符串'text',长度为'len'的后缀数组

//写结果到全局数组'g_sa'

//创建后缀数组并排序复杂度 O(n * log n)

void buildSA(char* text, int len) {

    Sfx *temp = g_tempSfx[1];

    int* rank = g_buf; //rank[i]记录排序后的序号

    for (int i = 0; i < len; i++)

//g_sa[i].i 表示排名为i的位置

        { g_sa[i].i = g_sa[i].key[1] = i;  g_sa[i].key[0] = text[i]; }

    sort(g_sa, g_sa + len); //排序

    for ( i = 0; i < len; i++) { g_sa[i].key[1] = 0; }

    int wid = 1;

    while (wid < len) {

        rank[ g_sa[0].i ] = 1;

        for (int i = 1; i < len; i++)

        {   rank[ g_sa[i].i ] = rank[ g_sa[i - 1].i ];

            if ( g_sa[i-1] < g_sa[i] ) { rank[ g_sa[i].i ]++; } }

        for ( i = 0; i < len; i++)

            { g_sa[i].i = i;  g_sa[i].key[0] = rank[i];

              g_sa[i].key[1] = i + wid < len? rank[i + wid]: 0; }

        cSort(g_sa, len, 1, temp);       //按次关键字排序  

cSort(temp, len, 0, g_sa);       //按主关键字排序

        wid *= 2;            //倍增

    }

}

//是将a所指的内容赋给b所指的内容,l累加并返回值

int getLCP(char* a, char* b)

{ int l=0;  while(*a && *b && *a==*b) { l++; a++; b++; }  return l; }

void getLCP(char* text, Sfx* sfx, int len, int* lcp) {

    int* rank = g_buf; //rank[i]记录排序后的序号

    for (int i=0, r=0; i < len; i++, r++) { rank[ sfx[i].i ] = r; }

    lcp[0] = 0;

    if (rank[0])

        //递归

        { lcp[ rank[0] ] = getLCP( text, text + sfx[ rank[0]-1 ].i ); }  

    for ( i = 1; i < len; i++) {

        if ( !rank[i] ) { continue; }

        if (lcp[ rank[i - 1] ] <= 1)

//递归

{ lcp[ rank[i] ] = getLCP( text+i, text+sfx[ rank[i]-1 ].i ); }

        else

        { int L = lcp[ rank[i - 1] ] - 1;

//递归

          lcp[rank[i]] = L+getLCP(text+i+L, text+sfx[rank[i]-1].i+L); }

    }

}

//测试套件和用法的例子

#include <iostream>

using namespace std;

int main() {

    char str[] = "aabbaa{post.content}ababab"; //输入字符串

    int from[] = {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1};

    int lcp[13]; //存储输出字符串

    //调用buildSA(str, n),建立后缀数组并排序复杂度 O(n * log n)

    buildSA(str, 13);  

getLCP(str, g_sa, 13, lcp);

    for (int i=1; i<13; i++) //第一个后缀是无用的(空的)

     { cout<<from[g_sa[i].i]<<' '<<str+g_sa[i].i<<' '<<lcp[i]<<endl; }

   system("pause");

    return 0;

}

【案例分析】

1)倍增法是构造后缀数组一个比较实用的算法。其基本思想是先计算出每个后缀的k-前缀的rank值,然后在此基础上计算每个后缀的2k-前缀的rank值;k1开始,直到每个后缀都排出先后顺序为止,任何两个后缀都不会相等,也就是说每个后缀最终都能排出先后顺序。在处理2k-前缀时,只需要使用基数排序算法,先后对两位数字排序(可以采用基数排序算法对每一位数字排序)。

2)符号(||)逻辑或,(&&)逻辑与;memset( cnt, 0, sizeof(int) * (n + 1) ),将cnt中前sizeof(int) * (n + 1)个字节用0替换并返回cnt

 

提示:倍增法在最坏情况下,需要做lgn次基数排序,每一次基数排序的操作次数为2*O(n)。因此它的时间复杂度是O(nlgn)。倍增法虽然没有达到像DC3算法的线性复杂度,但是它的优点是实现比较简单,因此在实践中常被采用。

案例14-12  推箱子

【案例描述】

本实例演示的是训练玩家的逻辑思考能力的游戏,本实例举推箱子游戏,涉及到类和BFS算法,同时还要产生随机数,是类和算法的综合应用。本例效果如图14-12所示。

 

14-12  推箱子

【实现过程】

定义每一步的数据类型node,推箱子类Sokoban实现各种动作,Box_Bfs()是实现BFS算法。代码实现如下:

//箱子路径验证函数

//BFS算法对箱子验证是否可到目的地

void Sokoban::Box_Bfs(int bx, int by, int px, int py)

{

 queue<node>_Box; //创建箱子队列

 //visit对上一步走到下一步的记录,防止箱子走重复路劲

 //visit[i][j][z][k]表示箱子从点(i,j)到点(z,k)

 //visit[][][][]0时表示未走过,1时表示已走过

 int visit[H][L][H][L];

 memset(visit, 0, sizeof(visit)); //visit数组初始化

 s.bx = bx;  s.by = by; //将起始的箱子、人位置放入队列

 s.px = px;  s.py = py;

 _Box.push(s);

 int pe_x, pe_y;

 while(!_Box.empty()) //队列为空时跳出

    {

        s = _Box.front();

        _Box.pop();

        if(GameMap[s.bx][s.by] == Target) //到达目的地

        {

            Prove = 1;

            break;

        }

        for(int i = 0; i < 4; i++)

        {

            e.bx = s.bx + dx[i];  e.by = s.by + dy[i];

          

            switch(i) //人推箱子的位置

            {

            case 0:  pe_x = s.bx + dx[2]; pe_y = s.by + dy[2]; break;

            case 1:  pe_x = s.bx + dx[3]; pe_y = s.by + dy[3]; break;

            case 2:  pe_x = s.bx + dx[0]; pe_y = s.by + dy[0]; break;

            case 3:  pe_x = s.bx + dx[1]; pe_y = s.by + dy[1]; break;

            }

       //验证箱子和人的位置合法性

            if(!Check(e.bx, e.by) || !Check(pe_x, pe_y)

            || GameMap[e.bx][e.by] == Block || GameMap[pe_x][pe_y] == Block

            || visit[s.bx][s.by][e.bx][e.by] )

                continue;

       //如人可推箱子即进入队列

            if(Sokoban::People_Bfs(pe_x, pe_y))

            {

      //保存人推箱子后的位置

                e.px = pe_x;  e.py = pe_y;

                _Box.push(e);

                visit[s.bx][s.by][e.bx][e.by] = 1; //箱子路径的标记

            }

        }

 }

}

//人路径验证函数

//BFS算法对人验证是否可推箱子

bool Sokoban::People_Bfs(int ex, int ey)

{

    queue<node>_People;

    node t, end;

 //visit数组对人的路径进行标记,0为未走过,1为走过

    int visit[H][L];

 //visit数组初始化为0

 memset(visit, 0, sizeof(visit));

    t.px = s.px;  t.py = s.py; //人初始位置进入队列

    _People.push(t);

    visit[t.px][t.py] = 1;

    while(!_People.empty()) //队列为空时跳出

    {

        t = _People.front();

        _People.pop();

        if(t.px == ex && t.py == ey) //人可到达(ex,ey)该点

        return 1;

        for(int i = 0; i < 4; i++)

        {

            end.px = t.px + dx[i];  end.py = t.py + dy[i];

      //检查人的位置合法性

            if(!Check(end.px, end.py) || GameMap[end.px][end.py] == Block

   || GameMap[end.px][end.py] == Box || visit[end.px][end.py])

                 continue;

            _People.push(end); //进入队列

            visit[end.px][end.py] = 1; //记录

        }

    }

    return 0;

}

【案例分析】

1)推箱子是一个来自日本的古老游戏,可训练玩家的逻辑思考能力。在一个狭小的仓库中,要求把木箱放到指定的位置,稍不小心就会出现箱子无法移动或者通道被堵住的情况,只有巧妙利用有限的空间和通道,合理安排移动的次序和位置,才能顺利完成箱子的堆放。

2BFS算法(宽度优先搜索)原型是图的宽度优先遍历问题,即从源顶点s出发,遍历每一个节点。基本思路先扩展当前节点所有邻接的节点,然后再从这些顶点出发,遍历所有顶点即分层处理,再将遍历路径表示成树,也就是按层次遍历。

 

提示:每次运行程序的地图是不同的。

14.3  使用关联式容器

案例14-13  队列镜像

【案例描述】

双端队列是既可以在队头插入和删除,也可以在队尾插入和删除的一种特殊队列。因此在实际应用中,双端队列比普通队列的应用范围更加广泛。本例效果如图14-13所示。

 

14-13  队列镜像

【实现过程】

定义deque类型的容器deque_A,显示输出双端队列中的所有元素函数print(),元素从队尾进队列,尾部插入容器元素insert(),尾部删除容器元素pop_back(),头部插入insert()和删除容器元素pop_back()。代码实现如下:

#include<iostream>

#include<deque>

using namespace std;

template<class T>

void print(T &deq, char *str) //显示输出双端队列中的所有元素

{

T::iterator it;

cout<<"The elements of "<<str<<": ";

    //begin返回第一个元素的指针,end返回最后一个元素的下一位置的指针(list为空时end()=begin())

for(it=deq.begin();it!=deq.end();it++)

{   cout<<*it<<" "; } //显示容器元素

cout<<endl;

}

int main() {

    deque<char> deque_A; //创建双端队列

deque_A.push_back('c'); //从队尾进队列

deque_A.push_back('d');

  deque_A.push_front('b'); //从队头进队列

deque_A.push_front('a');

print(deque_A,"deque_A");

    //显示队头元素

cout<<"The first element of deque_A is "<<deque_A.front()<<endl;               

    //显示队尾元素

    cout<<"The last element of deque_A is "<<deque_A.back()<<endl;                

deque_A.insert(deque_A.begin(),'x');   //在队头插入元素

    deque_A.insert(deque_A.end(),'z');    //在队尾插入元素

print(deque_A,"deque_A");

    deque_A.pop_front();      //从队头出队列(删除元素)

print(deque_A,"deque_A");

deque_A.pop_back();      //从队尾出队列(删除元素)

print(deque_A,"deque_A");

    system("pause");

    return 0;

}

【案例分析】

这是双端队列容器实例,push_front()在容器前端增加元素;pop_front()在容器前端删除元素;push_back()在容器后端增加元素;pop_back()在容器后端删除元素。

 

提示:实际应用中,双端队列比普通队列的应用范围更加广泛。

案例14-14  反暴力破解

【案例描述】

穷举法或称为暴力破解法,是一种针对于密码的破译方法;即将密码进行逐个推算直到找出真正的密码为止。计算机用户出于安全的考虑,需进行反暴力处理。本例演示设下试误的可容许次数,以应对使用密码穷举法的破解者,效果如图14-14所示。

 

14-14  反暴力破解

【实现过程】

编写一个无回显的密码登录器,输入密码时,来保证安全性,要求在屏幕上显示的是星号******,要求只能够输入三次密码,多于三次,系统自动异常退出。代码实现如下:

//检索密码和账号

 void save_look( map<string,string> &m_mp, string &m_account, string &m_code)

 {

string str1,str2;

ifstream input("test.txt"); //用于文件的输入操作

while(input >> str1 >> str2)

m_mp.insert(make_pair(str1,str2)); //插入元素

input.close(); //关闭文件

map<string,string>::iterator iter = m_mp.find(m_account);//查找m_account

if(iter == m_mp.end())

{

cout << "\n这个账号不存在,是否要创建?请输入Y或者N" << endl;

char ch1;

while (cin >> ch1)

{

if((ch1 == 'Y')||(ch1 == 'y'))

{

m_mp.insert(make_pair(m_account,m_code)); //插入元素

ofstream output("test.txt", ios::app | ios::out); //文件的输出操作

// output.open("test.txt"); //打开文件

output.seekp(0,ios::end);

output << m_account << '\n' << m_code << endl;

output.close();

cout << "创建成功!" << endl;  

exit(0);

}

else if((ch1 =='N')||(ch1 =='n'))  {  exit(0);  }

else  {  cout << "输入错误! 请重新输入!" <<endl;  }  }  }

else  {

int i = 1;

while(m_mp[m_account] != m_code)  {

char ch1;

cout << "\n密码错误请重新输入!" << endl;

m_code = "";

i++;

if(i == 5)  {

cout << "\n对不起你重复次数太多!" << endl;

exit(0);  }

else  {   code_input(ch1,m_code); //密码输入函数  

}   }

cout << "\n账号密码正确!" << endl;  }  }

【案例分析】

密码验证机制是需设下试误的可容许次数,防止使用密码穷举法的破解者。当试误次数达到可容许次数时,密码验证系统会自动拒绝继续验证,有的甚至还会自动启动入侵警报机制。

这是密码登录程序是一个简单的演示,不和具体的数据库连接,暂时把输入的用户登录信息存在文件“test.txt”中。在关联容器map中,函数insert()插入元素,find()查找关键元素。

 

提示:可参照实例232233,基于MySQL数据库,利用SQL(结构化查询语言)存储数据,使用SQL语言插入记录、查询账号和密码。

14.4  关联式容器的成员函数操作

案例14-15  插队(在容器中部插入元素)

【案例描述】

在关联容器,如果需要一个键/值对(pair)来存储数据,map是一个很好的选择。map中的数据元素是由关键字和数据两部分组成。例如:在银行管理系统中,每个用户都有一个对应的账号。本例定义容器并插入元素,效果如图14-15所示。

 

14-15  插队(在容器中部插入元素)

【实现过程】

创建一个pair<int,string>数组sz,待插入的pair对象t,基于sz创建map对象obMt插入obM中,将t插入obM中,显示插入元素。代码实现如下:

#include <iostream>

#include <map> //使用map必须要使用的头文件

#include <string>

using namespace std;

int main()

{

pair<int,string> sz[2]={pair<int,string>(1,"A"),pair<int,string>(2,"B")};//创建一个pair<int,string>数组sz

pair<int,string> t(2,"X"); //待插入的pair对象

map<int,string> obM(sz,sz+2); //基于sz创建map对象obM

map<int,string>::iterator itM=obM.begin();//创建map<int,string>类内迭代器itM

    //t插入obM中,返回结果保存在pair<map<int,string>::iterator,bool>对象res

pair<map<int,string>::iterator,bool> res=obM.insert(t);

if (res.second) //判断是否插入成功

cout<<"插入成功"<<endl;

else

cout<<"已包含关键字与t相同的元素:"<<(*res.first).second<<endl;

multimap<int,string> obDM(sz,sz+2); //基于sz创建multimap对象obDM

multimap<int,string>::iterator itDM=obDM.begin();//创建multimap<int,string>类内迭代器itDM

itDM=obDM.insert(t); //执行插入操作

cout<<"插入的元素为:"<<(*itDM).second<<endl;

system("pause");

return 0;

}

【案例分析】

1)容器multimap(多映射),其特性map{键(key),值)}对的组成的集合。集合中的元素按键排列。multimap是允许键/值对有重复的集合。mapmultimap的关系如同setmultiset之间的关系,如果希望将键与值相关联就可以使用map/muitimap。包含在头文件< map >

2)如果需要一个键值对(pair)来存储数据,map是一个好的选择。使用参数数目可变的函数时要注意以下几点:

1、在定义函数时,固定参数部分必须放在参数表的前面,可变参数在后面,并用省略号“...”表示可变参数。在函数调用时,可以没有可变的参数,如代码simple_va_fun(int start, ...) 

2、必须使用函数va_start()来初始化可变参数,为取第一个可变的参数作好准备工作;使用函数va_arg()依次取各个可变的参数值;最后用函数va_end()做好结束工作,以便能正确地返回。

 

提示:容器set(集合)和multiset(多集)比较,set是一个元素集合,集合中的元素按有序的方式存储,set中没有重复的元素,但multiset中允许有重复的元素。但字需要使用元素集合,而且对元素的查找、插入和删除操作都较为频繁时,就可以使用set/multiset<set>在调用参数个数可变的函数时,必定有一个参数指明可变参数的个数或总的实参个数。包含在头文件<set>中。

14.5  迭代器

案例14-16  模拟文件资源管理系统

【案例描述】

这是个综合实例,目的加深对模拟文件资源管理系统理解。遍历目录就是给定一个目录,访问其中的所有文件(包括子目录下的文件),可实现快速对文件的属性修改、查找系统文件的目的。本例效果如图14-16所示。

 

14-16  模拟文件资源管理系统

【实现过程】

定义个函数getFiles()输入目录和容器,用_findfirst()_findnext()搜索所有的文件,主函数for循环遍历容器files。其代码如下:

void getFiles( string, vector<string>& );

int  main()  {

    vector<string>   files;

    getFiles( ".", files );

     // print the files get

    for   (int   j=0;   j<files.size();   ++j) { //遍历容器files

        cout   <<   files[j] << endl ; //打印容器的值

    }

system("pause");

    return   0;

}

void getFiles( string path, vector<string>& files ) {

    //文件句柄

    long   hFile   =   0;

    //文件信息

    struct _finddata_t fileinfo;   //存储文件各种信息的结构体

    string p;

//搜索与指定的文件名称匹配的第一个实例

    if   ((hFile   =   _findfirst(p.assign(path).append("/*").c_str(), &fileinfo))   !=   -1)  {

        do  {

            //如果是目录,迭代之

            //如果不是,加入列表

            if   ((fileinfo.attrib   &   _A_SUBDIR)) { //文件的属性attrib

  //字符串比较

            if   (strcmp(fileinfo.name,".")   !=   0   &&   strcmp(fileinfo.name, "..")   !=   0)

                   getFiles(   p.assign(path).append("/").append(fileinfo.name), files   ); //递归

            }  else  {

                files.push_back(p.assign(path).append("/").append(fileinfo.name)  );

            }

            //搜索与该函数提供的文件名称匹配的下一个实例

        }   while   (_findnext(hFile,   &fileinfo   )  ==   0);

        _findclose(hFile);   //关闭由FindFirstFile函数创建的一个搜索句柄

    }

}

【案例分析】

1)函数_findfirst(),搜索与指定的文件名匹配的第一个实例;若成功则返回第一个实例的句柄,否则返回-1L_findnext搜索与该函数提供的文件名匹配的下一个实例,若成功则返回0,否则返回-1_findclose关闭由FindFirstFile()函数创建的一个搜索句柄。所谓遍历目录,就是给定一个目录,访问其中的所有文件(包括子目录下的文件)。迭代是比较常用的遍历算法。

2)“资源管理器”是Windows系统提供的资源管理工具,可以用它查看本台电脑的所有资源,特别是它提供的树形的文件系统结构。

 

提示:“资源管理器”和“我的电脑”工具在使用功能上是一样的,两者都是用来管理系统资源的,或者说都是用来管理文件的。在“资源管理器”中还可以对文件进行各种操作,如:打开、复制、移动等。

14.6  泛型算法

案例14-17  反向输出

【案例描述】

反向输出可以编写个函数实现,但最简单的就是使用STL标准库的泛型算法,本实例讨论这方面问题,了解泛型算法的优点,演示反转容器中的字符串,效果如图14-17所示。

【实现过程】

函数demo1()输入一个字符串,主函数用reverse_copy()reverse()反转字符串。代码实现如下:

#include <iostream>

#include <algorithm>

#include <string>

using namespace std;

int demo1()

{

char a[500],b[500],*p,*q;

gets(a); //取得一个字符串

p=a;

q=b;

while(*p!='\0') //是否是字符串最后面

p++; //指针指向下一个位置

p=p-1;

while(p!=a-1)

{  *q=*p; //字符交换

p--; //指针指向下一个位置

q++; //指针增加一位置

}

*q='\0'; //字符串后面加'\0'

puts(b); //输出反转的字符串

cout<<endl;

return 0;

}

int main()

{

demo1();

    string first,second;

cout<<"输入一字符串:"<<endl;

    cin>>first;

    second.resize(first.size()); //resize函数用来改变string的大小

//begin()指向字符串第一个字符的迭代器,end()超尾值的迭代器

    reverse_copy(first.begin(),first.end(),second.begin());//使用reverse_copy函数

    cout<<"反向输出:"<<second<<endl; //使用reverse函数

    string str;

cout<<"输入一字符串:"<<endl;

    cin>>str;

    reverse(str.begin(),str.end()); //使用reverse函数

    cout<<"反向输出:"<<str<<endl;

   system("pause");

    return 0;

}

【案例分析】

1everse()函数实现反转一个容器内元素的顺序的功能。函数reverse(first,last);first为容器的首迭代器,last为容器的末迭代器,无返回值。

2resize()函数用来改变字符串string的大小,若小于string的长度size个字符,则截取前size个字符,若大于则用空格补充。

 

提示:reverse_copy()函数和reverse()函数的唯一区别在于:reverse_copy会将结果拷贝到另外一个容器中,不影响原容器的内容。

14.7  适配器

案例14-18  获取列队头尾

【案例描述】

容器适配器队列(queue),是在一端插入元素,在另一端取出元素,具有先进先出(first in, first out, FIFO)的特性的一种特殊队列,插入和删除速度都较快。当需要一个FIFO结构时就使用这个队列。本例实现取得容器头尾元素功能,效果如图14-18所示。

【实现过程】

程序主要是一个打印容器元素的值函数print(),主函数创建队列q,把元素压入队列,取队头元素和取队尾元素。代码如下:

#include<iostream>

#include<queue>

using namespace std;

template<class T>

void print(queue<T> &q)  

{

  if(q.empty()) //判断队列是否空

     cout<<"Queue is empty!"<<endl;

  else  {

 int j=q.size(); //取容器大小

  for(int i=0; i<j;i++) {

cout<<q.front()<<" ";    //返回容器中第一个元素的引用

         q.pop(); //出队列

  }

  cout<<endl;

 }}

int main()

{

  queue<char>  q; //创建队列

  q.push('a'); //进队列

  q.push('b');

  q.push('c');

  q.push('d');

   //取队头元素

  cout<<"The first element is : "<<q.front()<<endl;  

  //取队尾元素

  cout<<"The last element is : "<<q.back()<<endl;    

  cout<<"The queue is : "<<endl;

  print(q);  

  system("pause");

  return 0;

}

【案例分析】

1)代码front()返回容器中第一个元素的引用,back()返回容器中最后一个元素的引用程序。代码main()函数中创建队列,调用成员函数实现取队头元素和取队尾元素。

2queue(队列),在需要一个FIFO结构时就使用这个队列。包含头文件< queue >

 

提示:适用于vector的操作都适用于dequedeque还有push_front(将元素插入到前面)和pop_front(删除最前面的元素)操作的功能。

案例14-19  利用容器适配器实现栈功能

【案例描述】

容器适配器是指将某个底层顺序容器转换为另一种容器。即以顺序容器作为数据存储结构,将其转换为某种特定操作特性的新容器,如queuepriorityqueuestack,从而进一步扩展了容器的应用。本例效果如图14-19所示。

 

14-19  利用容器适配器实现栈功能

【实现过程】

定义个出栈函数output(),创建栈int_s,使用for循环进行进栈操作,调用output()实现出栈,并输出结果。其代码如下:

#include<iostream>

#include<vector>

#include<stack>

using namespace std;

template<class T>

void output(T &stackdata) //出栈函数

{

while(!stackdata.empty()) { //直到栈为空

    cout<<stackdata.top()<<" "; //取栈顶元素

    stackdata.pop(); //出栈

  }

  cout<<endl;

}

int main(){

  stack<int>  int_s; //创建栈

  stack< int,vector<int> > vec_stack;

  for(int i=0;i<8;i++)

{

int_s.push (i); //进栈

vec_stack.push(i);

}

  cout<<"Pop from int stack:"<<endl;

  output(int_s); //调用出栈函数

  cout<<"Pop from vec_stack:"<<endl;

  output(vec_stack);

  system("pause");

  return 0;

}

【案例分析】

stack(栈)是一个经典数据结构,要求数据元素具有FILO的特性,因此要转换为stack的顺序容器必须支持push_back(在容器后端添加元素),又支持pop_back(在容器后端删除元素);而顺序容器中vectordequelist都符合这些条件,因此都可以通过容器适配器转换为stack

14.8  本章练习