算法笔记day1小结

最近在通过胡凡的算法笔记一书学习算法，准备开个帖子记录下每日学习进展，话不多说那就开始吧！

2.7指针

定义：内存地址称为指针 ， 指针变量即存储地址的变量。（虽然有点绕口，但可以理解为指针就是一个地址，对应着内存中的一个存储单元。unsigned类型的整数）。

指针的定义：

2.7.1 变量取址 &a (变量前加&符号，取变量的地址)

2.7.2 直接定义指针变量：

int* p (*号跟在类型名后面或者变量名前面都可以，如果跟在类型名后面定义多个指针时只对第一个生效，后续变量名前面需要带*号如int* p, *a, *b, 所以定义多个指针变量时*号一般都统一放在变量名前面)

指针与函数：

传值与传址， 函数参数的传递方式如果是传值，函数体中操作变量则变量的值不一定改变（全局变量），若是传地址，则变量的值会随之改变

引用：

c++中的一个语法，定义如下：

int increase(int &a)

引用不产生副本，而是给原变量起了个别名，所以在函数体中如果有涉及到对变量的操作，会改变原变量的值。?

2.8 结构体

2.8.1 结构体的定义：

struct Node{

? ? ? ?int id;

????????Node* next;

}node, n[100];?

大括号外定义了Node类型的node,n是一个结构体数组。结构体里可以定义除了自己本身之外的任何数据类型，也可以定义自身类型的指针变量

2.8.2? 结构体内元素的访问：

两种方式：“.” 和“->”

如node.id或者 (*(node.next)).id 或者 node.next->id

2.8.3 结构体的初始化

结构体内部会生成一个默认的构造函数： Node(){}; 我们可以重新定义构造函数 如：

Node(int _id, Node* _next){

? ? ? ? id = _id;

? ? ? ? next = _next;

}

也可以简化成一行：

Node(int _id, Node* _next):id(_id), next(_next){}

重新定义构造函数的好处是可以在定义结构体变量的时候直接给内部变量赋值，而不需要手动提供初始化参数。但是这时候就会把原来的构造函数覆盖掉，如果需要不经初始化定义则需将默认的构造函数也加上去。

2.9 补充

2.9.1 cin和cout

cin 和 cout为c++中的输入输出函数，需要引用头文件：

#include <iostream>

using namespace std;

使用方式如下：

int a;

double b;

char c[10];

cin >> a >> b >> c

（cin为将值读入变量所以箭头指向变量，cout为输出变量的值，则箭头指向cout，这样好记。）

如果需要读入一整行数据使用getline

char str[100];

cin.getline(str, 100);

如果是string容器，则

string str;

getline(cin, str);

cout如果要控制输出精度，则需要引用头文件：

#include <iomanip>

double b;

cout << setiosflags(ios::fixed) << setprecision(2) << b << " ggg" << "\n";

cin和cout在数据量大时比较耗时所以大部分时候推荐使用scanf，printf, 只有在十分必要的情况下如string容器才使用。

2.9.2 浮点数比较

浮点数在某些会损失精度的运算之后无法准确的比较值，这时候引入一个极小数来对误差进行修正。

默认使用的极小数为EPS 取10的-8次方或者表示为1e-8.

const double eps = 1e-8;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //一般使用的浮点精度误差范围

#define Equ(a,b) ((fabs((a)-(b))) < (eps))? ? ? ? ? ? ?// ==

#define More(a,b) (((a) - (b)) > (eps))? ? ? ? ? ? ? ? ? // >

#define Less(a,b) (((a) - (b)) < (-eps))? ? ? ? ? ? ? ? ? // <

#define MoreEqu(a, b) (((a) - (b)) > (-eps))? ? ? ? ? // >=

#define LessEqu(a, b)?(((a) - (b)) < (eps))? ? ? ? ? ? // <=

2.10 黑盒测试（输入输出方式）

2.10.1 单点测试

对数据逐个测试，判断每组数据的输出结果是否正确（PAT采用这种方式）

2.10.2 多点测试

要求程序能一次运行所有数据

2.10.2.1 While --- EOF型

while(scanf("%d", &a) != EOF){

????????...

}

while(scanf("%s", str) != EOF){

? ? ? ? ...

}

while(gets(str) != NULL){

? ? ? ? ...

}

当题目没有给定输入条件时默认读取到文件末尾，正常的控制台输入一般不会失败，读取到文件末尾无法读取时scanf会返回-1，c语言中使用EOF（end of file）来代表-1。

2.10.2.2 While --- break型

题目要求当输入的数据满足某个条件时停止输入。有如下两种写法：

while(scanf("%d", &a) != EOF){

??????if(a == 0 && b == 0) break;

}

while(scanf("%d", &a), a || b){

????????...

}

第二种写法更简洁。

2.10.2.3 While --- T型

题目给出测试数据的组数，然后才给出相应数量组数的输入数据，因此需要用一个变量T来存储组数。

int T, a;

scanf("%d", &T);

while(T--){

? ? ? ? scanf("%d", &a);

}

以上就是多点测试的三种输入类型，输出就不额外强调了。

多点测试中，每一次循环都要重置一下变量和数组，而重置数组一般使用memset或者fill函数。