算法笔记阅读1

发表于 | 分类于

新开了个目录，因为发现其他的目录似乎不太合适。就当记录自己平时的一些笔记好了，现在看晴神宝典，据说是PAT神级书，希望我甲级考高分啦！下面就是简单的记录一些自己不太知道，或者容易忘记的东西，以后也都是这样。下面记的是一些基础知识。

变量型

  1. int: 一个整数占32bit，取值范围大致是-210^9~210^9(-2^31~2^31-1).
  2. long long: 一个整数占用64bit，取值-2^63~2^63-1
  3. 如果long long型赋大于2^31-1的初值，则需要在初值后面加上LL，否则会编译错误。
  4. 对于浮点型，以后都是用double来存储。
  5. 小写字母比大写字母的ASCII码大32。

  6. C的字符串常量

    1
    2
    3
    4
    5
    6
    #include <cstdio>
    int main(){
        char str1[25] = "wo ai de ren bu ai wo";
        char str2[25] = "so sad a story it is.";
        printf("%s, %s", str1, str2);
    }

  7. 整型常量在赋值给布尔型变量时会自动转换成true(非零)或者false(零)

  8. 常量定义

    1
    2
    3
    4
    // 宏定义,符号常量
    # define pi 3.14
    // const 常量
    const double pi = 3.14;

  9. scanf(“格式控制”, 变量地址); 如scanf(“%d”, &n); 另外要注意，数组名称本身代表了这个数组第一个元素的地址，所以不需要再加取地址运算符。在scanf中，除了char数组整个输入的情况不加&s之外，其他变量类型都需要加&。

    1
    2
    char str[23] = "23 sfs fsa";
    scanf("%s", str);

  10. scanf对其他格式符(如%d)的输入是以空白符（空格、Tab）为结束判断标志；字符数组使用%s读入的时候以空格跟换行为读入结束标志。另外，scanf的%c格式是可以读入空格跟换行的。以下面为例子，c为空格：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    #include <cstdio>
    int main(){
        int a;
        char c, str[10];
        scanf("%d%d%s", &a, &c, str);
        printf("a=%d,c=%c,str=%s", a, c, str);
    }
    //输入: 1 a bcd
    //输出：a=1,c= ,str=a(在我的电脑上测试,str输出乱码)

  11. scanf的double类型变量为%lf，而在printf则为%f。

三种实用的输出格式

(1) %md
%md可以使不足m位的int型变量以m位进行右对齐输出，其中高位用空格补齐；如果变量本身超过m位，则保持原样。实例：

1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>
int main(){
    int a = 123, b = 1234567;
    printf("%5d\n", a);
    printf("%5d\n", b);
    return 0;
}
/*
输出:
  123   //不足5位，前面自动用两个空格填充
1234567 //大于5位，直接输出
*/

(2)%0md
和%md唯一的不同点是，当变量不足m位时，将在前面补足够数量的0而不是空格。非常实用啊！以后就可以不用判断了，比如时间等。

1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>
int main(){
    int a = 123, b = 1234567;
    printf("%05d\n", a);
    printf("%05d\n", b);
    return 0;
}
/*
输出：
00123
1234567
*/

(3)%.mf
保留m位小数。如保留1位: be accurate to 1 decimal place.

继续

  1. getchar用来输入单个字符，putchar用来输出单个字符。另外注意，getchar()可以用来识别换行符。gets用来输入一行字符串(识别\n换行符作为输入结束，因此scanf完一个整数后，如果要使用gets，需要先用getchar接收整数后的换行符)。
  2. fabs(double x)用来对double型变量取绝对值，abs用于整型。
  3. floor(double x)和ceil(double)分别用于double型变量的向下取整和向上取整。

  4. sin(double x), cos(double x), tan(double x)参数要求是弧度制，示例：

    1
    double db1 = sin(pi*45/180);

  5. asin(double x), acos(double x), atan(double x)。

  6. round(double x) 代表四舍五入取整。
  7. switch语句
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    switch(表达式){
        case 常量表达式1:
            ...
            break;
        case 常量表达式2:
            ...
            break;
        default:
            ...;
    }

由于case本身默认把两个case之间的内容全部作为上一个case的内容，因此不需要加大括号。

  1. break可强制退出switch语句和循环；continue在需要的地方临时结束循环的当前轮回，然后进入下一个轮回。
  2. 对数组而言，如果不赋值，则系统会随机赋值；如果赋值但没有全部赋完，则没有赋值的位置一般为0。
  3. 特别提醒：如果数组大小较大（大概10^6级别），则需要将其定义在主函数外面，否则会使程序异常退出。原因是函数内部申请的局部变量来自系统栈，允许申请的空间较小；而函数外部申请的全部变量来自静态存储区，允许申请的空间较大。
  4. memset(数组名, 值, sizeof(数组名)); 建议只能赋值0或-1，如果赋值其他值，使用fill，但速度慢。

冒泡排序

算法复杂度:O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <cstdio>
int main(){
    int a[10] = {3,1,4,5,2}; 
    for(int i=1; i<=4; i++){ //进行n-1趟排序
        for(int j=0; j<5-i; j++){ //这里之所以是5-i，是因为到后面只需要比较前面的元素
            if(a[j] > a[j+1]){
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] =  temp;
            }
        }
    }
}