C++程序设计:原理与实践(进阶篇)15.1 存储和处理数据

简介:

摘要


Programming: Principles and Practice Using C++, Second Edition

容器和迭代器

只做一件事,并把它做好。多个程序协同工作。

——Doug McIlory

本章和下一章将分别介绍C++标准库(STL)中的容器和算法部分。STL是一个用于处理C++程序中数据的可扩展框架。我们首先通过一个简单的例子来说明STL的设计理念和基本概念,然后详细讨论迭代器、链表和STL中的容器。STL通过序列(sequence)和迭代器(iterator)的概念将容器(数据)和算法(处理)关联起来。本章的内容为下一章介绍通用和高效的算法奠定了基础。作为示例,本章实现了一个文字编辑器的基本框架。


15.1 存储和处理数据


在处理数据量很大的问题之前,我们先来看一个简单的例子,它说明了解决一般数据处理问题的基本方法。Jack和Jill分别负责测量来往车辆的速度,结果用浮点数来表示。Jack是一个C语言的程序员,所以将测量值保存到一个数组中,而Jill将测量值保存到一个vector对象中。如果我们要在程序中使用他们的数据,该如何操作呢?

我们可以让Jack和Jill的程序将结果分别写到某个文件中,然后再从文件中读入数据。使用这种方法,我们的程序将与Jack和Jill所选用的数据结构和接口彻底无关。通常,这种程序之间的独立性是一种很好的特性,此时我们可以采用第10和11章中介绍的方法来获得输入数据,并利用vector<double>对象来进行计算。

但是,如果我们的任务不适合使用文件呢?假设我们必须每秒钟调用一次数据生成函数来获得一组新的数据。例如,下面的程序每秒都会调用Jack和Jill的函数来获得将要处理的数据:

 

 

上面这段代码假设我们要自己安排存储数据的空间,而且在用完这些数据之后要自己负责删除。另一个假设是我们不能重写Jack和Jill的代码,而且通常我们也不想这样做。

15.1.1 处理数据

显然,这个例子过于简单,但是它与很多实际问题并没有本质区别。如果我们能够很好地解决这个例子,就能够处理一大类通用的编程问题。问题的关键在于我们无法控制提供数据的程序以什么形式来存储数据。我们可以自由决定是沿用原有的数据格式,还是转换为另一种形式来进行存储和处理。

我们想要如何处理数据?排序?找出最大值?找出平均值?找出大于65的值?比较Jill和Jack的数据?处理需求多种多样,我们只能根据具体任务来编写处理程序。这里,我们主要是学习怎样处理数据,完成大量数据的计算。首先从简单的处理开始:找到数据集合中的最大值。我们可以将fct()函数中内容为“…处理…”的注释行替换为下面这段代码:

 

 

注意访问Jill数据时使用的语法(*jill_data)[i]。get_from_jill()函数返回一个指向vector对象的指针,即vector<double>*。为了获得数据内容,我们首先要解引用指针以获得vector——*jill_data,然后对其使用下标操作。然而,*jill_data[i]并不是我们想要的结果,因为运算符[]的优先级要高于运算符*,所以这个表达式的含义是*(jill_data[i]),必须在*jill_data外使用括号,结果即为(*jill_data)[i]。

试一试

如果可以修改Jill的代码,应该如何修改代码的接口来避免复杂的数据访问方法?

15.1.2 泛化代码

我们希望使用统一的方法来访问和处理数据,这样可以避免因为每次获得的数据格式不同而编写不同的处理代码。下面我们以Jack和Jill的代码为例,讨论如何让我们的代码更通用、更统一。

显然,我们对Jack和Jill的数据的处理方法很相似。但是两段代码有一些恼人的差异:jack_count和jill_data->size(),jack_data[i]和(*jill_data)[i]。我们可以通过使用引用来避免第二个不同之处:

 

 

这段代码已经非常接近处理Jack数据的代码了。接下来如何编写一个可以同时处理Jack和Jill数据的函数呢?方法有很多(参考习题3),出于通用性的考虑(这一点在接下来的两章中十分明显),我们选择下面这种基于指针的方法:

 

 

使用这个函数,数据处理代码可以改写为:

 

这段代码更加简洁:不仅省去了很多变量的定义,并且只出现了一段循环代码(在high()中)。如果我们想要得到最大值,只需查看*jack_high和*jill_high,例如:

 

注意,high()函数要求所处理的数据保存在一个数组中,所以“找出最大值”的算法返回的是指向数组元素的指针。

试一试

这段程序中有两个潜在的严重错误。其中一个会导致程序崩溃,另一个会导致high()函数返回错误的结果。下面将要介绍的通用技术会充分暴露出这两个错误,并给出系统的避免方法。现在我们只需要找出这两个错误,并提出修改意见。

high()函数的局限性在于只能处理某个特定的问题:

只能处理数组。vector的元素必须保存在数组中,但实际上数据的存储方式还有可能是list和map(见15.4节和15.6.1节)。

可以处理double类型的vector或数组,但是无法处理其他类型的元素,例如vector<double*>或char[10]。

只能找出最大值,无法完成其他简单的数据计算功能。

下面,我们探讨如何在更通用的数据集合上进行计算。

通过指针的方式来实现“找出最大值”的算法会带来一个意想不到的通用性:我们不仅可以找出整个数组或vector中的最大值,还可以找出数组或vector的某个部分的最大值,例如:

 

 

这里high1指向vecotr中前半部分的最大值,high2指向vecotr中后半部分的最大值。下面是这个结果的图示:

 

high()函数的参数是指针,这样的代码偏于底层,更容易引起错误。我们怀疑对于大多数程序员来说,找出vector中最大值的代码显然应像下面这样:

 

然而,这段代码失去了我们“偶然”从high()所获得的灵活性——我们不能用f?ind_highest()来查找vector某一部分中的最大值。我们实际上只是为了同时处理数组和vector才决定“摆弄指针”,但却意外地获得了某种灵活性。应该记住:代码泛化可以获得适用于多个问题的通用函数。

相关文章
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
139 77
|
1月前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
58 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
C++ 芯片
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
67 19
|
1月前
|
存储 编译器 数据安全/隐私保护
【C++面向对象——类与对象】CPU类(头歌实践教学平台习题)【合集】
声明一个CPU类,包含等级(rank)、频率(frequency)、电压(voltage)等属性,以及两个公有成员函数run、stop。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中,类是创建对象的蓝图。类的声明定义了类的成员,包括数据成员(变量)和成员函数(方法)。一个简单的类声明示例如下: classMyClass{ public: int
46 13
|
1月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
46 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
42 10
|
1月前
|
算法 C++
【C++数据结构——图】最小生成树(头歌实践教学平台习题) 【合集】
【数据结构——图】最小生成树(头歌实践教学平台习题)目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:【合集】任务描述 本关任务:编写一个程序求图的最小生成树。相关知识 为了完成本关任务,你需要掌握:1.建立邻接矩阵,2.Prim算法。建立邻接矩阵 上述带权无向图对应的二维数组,根据它建立邻接矩阵,如图1建立下列邻接矩阵。注意:INF表示无穷大,表示整数:32767 intA[MAXV][MAXV];Prim算法 普里姆(Prim)算法是一种构造性算法,从候选边中挑
42 10
|
1月前
|
编译器 数据安全/隐私保护 C++
【C++面向对象——继承与派生】派生类的应用(头歌实践教学平台习题)【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括: 1. **类的继承关系基础概念**:介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**:详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**:解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类,添加特定属性并测试这些类的功能。最终通过创建教师和助教实例,验证代码
48 5
|
1月前
|
存储 算法 搜索推荐
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类(头歌实践教学平台习题)【合集】
1. **相关排序和查找算法的原理**:介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**:讲解如何定义`Array`类,包括类的声明和实现,以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**:探讨内存管理和正确访问数组元素的方法,确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**:解释排序和查找函数的参数传递方式及返回值处理,确保函数功能正确实现。 通过掌握这些知识,可以顺利地将排序和查找算法封装到`Array`类中,并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
38 5
|
1月前
|
Serverless 编译器 C++
【C++面向对象——类的多态性与虚函数】计算图像面积(头歌实践教学平台习题)【合集】
本任务要求设计一个矩形类、圆形类和图形基类,计算并输出相应图形面积。相关知识点包括纯虚函数和抽象类的使用。 **目录:** - 任务描述 - 相关知识 - 纯虚函数 - 特点 - 使用场景 - 作用 - 注意事项 - 相关概念对比 - 抽象类的使用 - 定义与概念 - 使用场景 - 编程要求 - 测试说明 - 通关代码 - 测试结果 **任务概述:** 1. **图形基类(Shape)**:包含纯虚函数 `void PrintArea()`。 2. **矩形类(Rectangle)**:继承 Shape 类,重写 `Print
46 4