##内联成员函数

• inline + 成员函数
• 整个函数体出现在类定义内部

  1 2 3 4 5 6

  class B{ inline void func1(); void func2() { } };

定义常量

• const int MAX_VAL = 23;
• const string SCHOOL_NAME = “QDU”;

定义常量指针

不可通过常量指针修改其所指向的内容

1
2
3
4
5
6
7

int n, m;
const int *p = &n;
*p = 5;//error
n = 4; // ok
p = &m; //ok
//常量指针可通过强制类型转化 转化为非常量指针
int * p1 = (int *)p;//ok

定义常应用

1
2
3
4

int n;
const int &r = n;
r = 5;
n = 4;

位运算的简单应用

六种位运算符

& 按位与

用处

• 将变量某些位清0且同时保持其他位不变
  example: 将int变量n的低8位全置成0， 而其余位不变, n = n & 0xffffff00;
• 获取变量中的某一位
  example: 判断一个int类型变量第n位是否是1(从右往左， 从0开始数), n & 0x80 是否等于 0x80(即1000 0000)
• 判断一个数字的奇偶
  example: 一个数 ^ 1 的结果就是二进制的最末位

| 按位或

用处

• 将变量某些位置1且同时保持其他位不变
  example: 将int类型变量n的低8位全置成1， 而其余位不变， n |= 0xff(1111 1111)
• 二进制特定位上无条件赋值
  example: 把二进制最末尾变1, (n | 1) - 1

^ 按位异或

规则

• 相同取0，相异取1

特点

• 若a ^ b = c, 那么就有 c ^ b = a以及 c ^ a = b.此规律可用来进行简单的加密和解密

用处

• 将变量某些位取反且同时保持其他位不变
  example: 将int类型变量n的低8位取反， 而其余位不变， n = n ^ 0xff(1111 1111)

  1 2 3 4 5

  0000 0000 1111 1111 ^ 0010 1110 1001 0000 == 0010 1110 0110 1111

• 不使用中间变量交换a, b的值

  1 2 3

  a = a ^ b; b = a ^ b; a = a ^ b;

~ 按位非（单目）

<< 左移

规则

• 高位直接丢弃， 低位补0

  用处

• 把一个数左移n位就相当于乘以2的n次方// 但可能改变符号

  >> 右移

  规则

• 低位直接丢弃， 大多数C/C++编译器规定， 如果原符号位为1， 则右移时高位就补充1， 原符号位位0， 则右移时高位就补充0

  用处

• 把一个数右移n位就相当于除以2的n次方（不改变符号）， 但时向小里取整， 而不是丢失小数位
• 写出一个表达式的值与 a的第n位相同(从右向左， 从0开始): (a >> n) & 1 或 (a & (1 << n)) >> n //0 <= n < 31

2017年2月9日的总结与计划

今天是2017年2月9日， 距离开学还有8天， 距离蓝桥杯还有58天。

这个假期到目前为止， 做了如下事情：

1. 学会github和linux的初级使用。
2. PAT 乙级刷到了满分。
3. 参加蓝桥训练。

但是在这个过程中觉得自己还有有很多的不足，

学而不思则罔，思而不学则殆 ——《论语·为政》

所以需要在剩下的一个周时间里， 整理刷题的解题报告。

在刷PAT乙级和蓝桥的时候自己总结了如下知识点， 对自己提高是很有帮助的

1. 动态规划。
2. 离散数学的矩阵乘法。
3. 位运算。
4. C语言的字符串（蓝桥比较喜欢考。
5. C++中的sort和qsort不同的适用情况和compare函数的编写以及对于二维数组的排序。
6. C++中的string类， 还有stringstream的各种方法。
7. C++的输入输出流清空， 和有效数字输出， 四舍五入， 前导零输出
8. 大整数的四则运算。
9. STL中equal(), reverse()， find()等方法的使用。
10. 最大公约数， 最小公倍数的数学知识。
11. 快速幂。
12. pair, vector, stack, set, map的使用
13. 针对一些特殊题目的思路的总结。

剩下几天的安排：

看做过的题， 学新东西， 写博客， 看蓝桥视频， 看coursera的北大C++视频

总之， 还是要打好基础， 一步一步来，假期七天肯定不够了， 开学慢慢来吧。

邻接矩阵实现

水题做多会变傻的。 —— 静静学姐

最近做水题上瘾， 这道题无论如何还是要用邻接表做一遍，先用的dijkstra的邻接矩阵水一下，挖个坑： 以后要用邻接表做一遍！！！

• 注意判断重边即可~ （邻接矩阵多加个if语句就好

我的代码：github

函数指针的声明

类型名 (* 指针变量名)(参数类型1, 参数类型2, ……)

1

int (*typeOfSort)(const void *elem1, const void *elem2);

可以通过strcmp函数比较输入的命令行， 来决定升序或降序排序

1
2
3
4

if(strcmp(argv[1], "as"))
    typeOfSort = ascending;
if(strcmp(argv[1], "ds"))
    typeOfSort = dscending;

qosrt用 法：

1

void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void *));

参数：

1. 待排序数组首地址
2. 数组中待排序元素数量
3. 各元素的占用空间大小
4. 指向函数的指针，用于确定排序的顺序

typeOfSort所指向的函数类型需要程序员自己编写

1. 如果 elem1 在 elem2之前返回负整数
2. 如果 elem1 在 elem2之后返回正整数
3. 如果 elem1 与 elem2的顺序无所谓，返回**0

在比较具体数字之前需要将const int 类型的指针转化为const int 类型

1

const int *value1 = (const int *)elem1;

命令行参数以空格区分不同命令，如果要输入带有空格的字符串如 Hello World 需使用双引号括起

argc: 代表启动程序时， 命令行参数的个数， C/C++规定， 可执行程序本身的文件名， 也算作一个命令行参数， 因此， argc的值至少是1
argv： 指针数组， 其中每个元素都是一个char* 类型的指针， 每个指针指向一个字符串， 若命令行参数内部用空格， 用双引号括起来即可， 如下实例中的”hello world”
如果输入的字符中带有双引号的话： 123”456 就是 123”””456 “A””B” 就是 “””A””””””B””” ， 带有百分号的话：%号转义就是两个百分比：%%

1

example：myprogram "hello world"

我的代码：github

带有反向图的Dijkstra

题目描述
POJ3268 Silver Cow Party

知识点:

1. 求其他cow到目标cow， 再返回原本所在位置的本质： 正向求目标cow到其他cow的距离 加 反向图后目标cow到其他cow的距离
2. 反向图时，关于对角线对称的操作， 第二个for循环开始 j = i， 否则一个点被倒置两次，又回到了开始状态。
3. isVisit数组中的要求的点partyPlace， 在开始dijkstra前设置为true

我的代码: github

3D BFS

题目描述
POJ2551 Dungeon Master
感受：

1. 比图上的BFS多了一个维度， 多考虑一下就可以了， 就是代码量有点宏大
2. ACM是多组输入输出， 一定记得清空 isVisit 之类具有标记和存储功能的数组!!!!!

我的代码: github

书没有博客详细系列

啊哈磊的博客园

比较难以理解的部分

1. 利用i给各个边编号。
2. first存储了每个点第一条边的序号(i)
3. next存储第i边的下一条边的序号(i)
4. 因为是有向图，每条边只能在一个邻接表中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <iostream>
using namespace std;
int main()
{
    int nPoint, nSide;
    cin >> nPoint >> nSide;
    int u[10], v[10], w[10];
    int first[10], next[10];
    for(int i = 1; i <= nPoint; i++)
    {
        first[i] = -1;
    }
    // i 是每条边的序号
    //first存储了每个点第一条 边的序号
    //next存储了第i边下一条边的序号
    //因为是有向图， 所以每一边的只可能是一个点的第一条边或者下一条边
    for(int i = 1; i <= nSide; i++)
    {
        cin >> u[i] >> v[i] >> w[i];
        next[i] = first[u[i]];
        first[u[i]] = i;
    }
    for(int i = 1; i <= nPoint; i++)
    {
        int k = first[i];
        while(k != -1)
        {
            cout << u[k] << v[k] << w[k] << endl;
            k = next[k];
        }
    }
    return 0;
}