[信息与通信]10_标准模板库1.ppt

程序设计实习 第十讲 标准模板库概述 问题1: 计算以自然数A为基的Blah数集 若Blah是一个自然数集合,A是Blah中的最小元素, 且下列两个条件同时成立: xBlah 2x+1Blah3x+1Blah yBlah, y=A(xBlah y=2x+1)(xBlah y=3x+1)； 记Blah(A)为以A为基的Blah数集. 编写一个程序, 输入两个正整数A和N, 输出按升序排序后Blah(A)中的第N个数字. 分析 从A出发, 计算Blah(A)的元素 Blah(A)是无穷集合 存储Blah(A)的元素 至少要存储N个自然数 N的大小由输入数据决定 问题2: 稀疏矩阵与向量的乘 稀疏矩阵: 包含大量零元素的大规模矩阵(比如103*103) 零与任何数据相乘或者相除, 结果都为零 任何数加零或者减零, 结果都不变 元素的类型通常为 double 稀疏矩阵的存储: 一维数组 行优先: 每一行的非零元素存储在一起, 存储完数组的一行后, 再存储数组的下一行 矩阵的每一行R对应数组的一个片段SEGMENT SEGMENT共有N+1个元素, N是数组第R行中非零元素的数量 SEGMENT的第一个元素记录整数N, 余下的N个元素是一个二元组col, val, 各记录一个非零元素. 其中col是非零元素所在的列, val是非零元素的值 编写一个程序, 实现稀疏矩阵与向量的乘. 程序有两个命令行参数, 分别是输入文件和输出文件. 输入文件和输出文件都是字符型文件 输入文件: 第一个数字是稀疏矩阵的行数N, 接着是第1行中非零元素的数量m1和m1个二元组col, val,第2行中非零元素的数量m2和m2个二元组col, val,……, 最后是一个整数M以及M个实数,分别所乘向量的长度及各元素的值 输出文件: N个实数, 记录输入稀疏矩阵与向量相乘的结果 分析 需要3个数组 数组1: 存储稀疏矩阵, 其元素是一个结构体 double val int n: SEGMENT的第一个元素记录对应行中非零元素的数量, 其他元素记录非零元素所在的列 数组2: 存储相乘的向量 数组3: 存储相乘的结果 每个数组的大小都是未知的 问题1和问题2的共性和不同之处 使用大规模的数组结构存储数据 数组的大小未知 数组元素的类型不同 写一个实现动态数组功能的类模板, 在不同的地方都可以直接使用 大规模数组是一种常用的数据结构, C++提供了这样的类模板, 编程时可以直接使用 问题1的参考代码 #include vector using namespace std; class CBlah { vectorint val; int i, j; public: CBlah(int arg); int operator[](int n); }; CBlah:: CBlah(int arg=1) { val.push_back(arg); i = 0; j = 0; return; } int CBlah::operator[](int n) { if ( val.size()n ) return val[n]; if ( val[i]*2val[j]*3 ) { val.push_back(val[i]*2+1); i++; } else { val.push_back(val[j]*3+1); j++; } return operator[](n); } template class T vector是C++提供一个类模板 实现数组存储空间的动态管理 提供数组上的常用处理算法 template class T VectorT::push_back(T element) 在数组的末尾添加一个元素 标准模板库 STL C++ 语言的核心优势之一就是便于软件的重用 C++中有两个方面体现重用： 1. 面向对象的思想：继承和多态，标准类库 2. 泛型程序设计(generic programming) 的思想： 模板机制，以及标准模板库 STL STL中的模板分两类 容器模板: 它们的模板类是用于大规模数据存储和访问的常见数据结构, 根据数据规模自动的动态调整存储空间 算法模板:它们的模板类是用于容器的常用处理算法 泛型程序设计，简单地说就是使用模板的程序设计法。 将一些常用的数据结构（比如链表，数组，二叉树）和算法（比如排序，查找）写成模板，以后则不论数据结构里放的是什么对象，算法针对什么样的对象，则都不必重新实现数据结构，重新编写算法。 标准模板库 (Standard Template Library) 就是一些常用数据结构和算法的模板