这节课掌握重要情报，教授家里养了Googly和Hamster两只猫，名字取得好恶趣味233
Course Overview
- Enum and enum class
- Prim's and Kruskal's algorithms
- 重载and友元函数
- STL and STL in C++11
- 输出随机图
Suggested Readings
- C++ for C Programmers, ch. 8
- C++ by Dissection, ch. 6-7
1. enum and enum class
enum中变量是可以进行比较的，但是在enum type中， 变量在类型上已经有了区别，所以不能进行比较。在有了类型区别以后，代码安全性就有所提升不会不小心触发类型转换引起麻烦
enum Color{RED, BLUE, WHITE} //颜色类
enum Traffic{RED, Yellow, GREEN} //交通灯
// 这种情况下 Color::RED == Traffic::RED
enum class Color{RED, BLUE, WHITE} //颜色类
enum class Traffic{RED, Yellow, GREEN} //交通灯
// 使用enum class时 Color::RED != Traffic::RED
2. MST最小生成树
生成树：图中的边的集合，构成一棵树，这些边连起了图中所有的定点，并且树中不能有环。对于一个有N个节点的图，生成树有N-1个边。
Prim算法：
从单个顶点开始，将距离闭集中所有节点最近的一个节点放入闭集中，并记录它和闭集的最短距离，一次一个节点，将节点连接到现有树。
Prim算法属于贪心算法，贪心算法秉持了在局部挑选最优的概念。
Kruskal's算法：
Kruskal算法从边出发，从最小边出发，用贪心算法取下一个最小权重的边加入到已得到的联通分量里，如果成环则不加入。
3.重载and友元函数
访问类的私有成员有两种方式：通过类的成员函数和通过友元函数。成员函数的第一个参数默认为类的对象，在第一个参数非此类对象的时候就很不方便，例如冲裁ostream <<的时候，此时就需要通过友元的方式在类体外定义友元函数
class point{
friend ostream& operator<<(ostream& out, point p);
private:
int x, y;
};
ostream& operator<<(ostream& out, const point& p){
out << "("<<p.x<<", "<<p.y<<")";
return out;
} //不加friend报错
4.STL and STL in C++11
- STL
STL容器是由container, algorithm, iterator组成的
container包括vector, list, map
iterator包括forward, backward, random
algorithms包括sort, permute
// vector example
#include <vector>
using namesapce std;
vector<int> v(10)
for (vector<int>::iterator p = v.begin(); p != v.end(); ++p) // vector遍历
cout << *p <<'\t'
- auto
在使用中 vector<int>::iterator 这样的表达是十分麻烦且容易出错的，C++11中启用了一个新功能auto。auto意味着推断类型，因此被auto标注的类型必须是可以推断的，如果auto不能理解该类型，auto就无法工作。上面的例子可以写成
for (vector<int>::iterator p = v.begin(); ...) //原始写法
for (auto p = v.begin(); ...)// 用auto修饰的写法，编译器知道该表达式的类型为一个vector迭代器
// 其他例子
auto i = 3; // i是int类型
auto d = 3.7; // d是double类型
auto c = d; // c是double类型
- vector methods
#include <vector>
using namesapce std;
vector<int> v;
v.size(); // vector的长度
v.resize(int size); // resize the vector
// Constructors
vector<T> v; // empty vector
vector<T> v(n); // size n with default constructor T() called for each element
vector<T> v(n, value); value is of type T (or convertible to T)
- fstream: use with a file
- C++11的循环功能
#include <iostream>
#include <iterator>
#include <fstream>
#include <vector>
ifstream data_file("data.txt"); // text file containing data
istream_iterator<int> start(data_file), end;
vector<int> data(start, end); // start与end之间所有的数据都会保存在data里面
for(double d: data) // C++11 for 新用法
sum += d;
for(auto& element: data) // auto infers type
element = element + 2; // allows mutate
// another example
ifstream word_file("word.txt");
istream_iterator<string> start(word_file), end;
vector<string> words(start, end) // vector会自动用空格作为分割
// print the vectore
for(auto str: words)
cout << str <<'\t';
sort(words.begin(), words.end()); // sort the vector
- iterators category
- input(weakest), 只允许读入数据，每条数据只能看一遍。必须实现++, dereferencing operator *, ==, !=
// use an input iterator
#include<istream>
#include<fstream>
#include<numeric>
using namespace std;
s
int main(){
ifstream myin('data')
istream_iterator<int> in(myin); //begin of the file
istream_iterator<int> eos; //end of stream
cout<<"sum of data is"<<accumulate(in, eos, 0)<<endl;//accumulate在numeric库中,从0开始累计
}
- output, 输出迭代器，每条数据只能写一遍
- forward, 可读可写，可以被重复使用，每边只能是单向的
- bidirectional, 允许多遍使用，双向
- random access(strongest), 随机访问，复杂度为O(1)
STL的原则是，使用最弱的迭代器实现最高校的算法
5.输出随机图
最后使用本节课的内容完成随机图的生成和输出
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <fstream>
using namesapce std;
double prob()
{
return (static_cast<double> (rand())/RAND_MAX)
// rand()和RAND_MAX都是整数，rand() 输出一个小于RAND_MAX的正整数，如果不转换成double类型相除就会等于0，转换成double得到介于0，1之间的值
}
int main(){
int size = 15;
double density; //get from user
cout <<"graph size?"<<endl;
cin >> size;
cout<< "graph density(0,1)?"<<endl;
cin >> density;
// creat matrices off heap
bool** graph; // present a graph in a bool matrix
int ** color;
int** cost;
srand(time(0)) // seed random number generator
graph = new bool*[size];
color = new int*[size];
cost = new int*[size];
for (int i=0;i<size;++i){
graph[i] = new bool[size];
color[i] = new int[size];
cost[i] = new int[size];
}
// generate graph
for(int i=0;i<size;++i) //generate undirected edges
for(int j=i; j<size;++j)
if(i==j) graph[i][j]=false; //no loops
else graph[i][j] = graph[j][i] = (prob()<density)
for(int i=0;i<size;++i) //generate cost and color
for(int j=i;j<size;++j)
if (graph[i][j]){
color[i][j] = color[j][i] = rand()%3; //3种颜色
cost[i][j] = cost[j][i] = prob()*30; //成本的范围0-30
}
ofstream outp("graph_data.txt");
outp <<size<<"\n";
for(int i=0;i<size; ++i)
for(int j=0;j<size;++j){
if(graph[i][j])
outp << i <<'\t' <<j<<'\t'<<
cost[i][j]<<'\t'<<color[i][j]<<'\t'
}
}
C++ Part A完结
自此C++ Part完结撒花🎉
更多C++功能如lambda将在Part B中继续介绍
网友评论