NekoMio's Blog

美しいものが起こることを常に信じている

  1. 1. 观前提示
  2. 2. 简介
    1. 2.1. 计算机程序设计语言
    2. 2.2. 计算模型
  3. 3. C语言 (划重点)
    1. 3.1. 语法
      1. 3.1.1. 1. 定义
      2. 3.1.2. 2. 输入输出
      3. 3.1.3. 流程控制
      4. 3.1.4. 运算符
      5. 3.1.5. 结构体
      6. 3.1.6. 指针
      7. 3.1.7. 函数传参与返回值
      8. 3.1.8. 字符串
    2. 3.2. 算法
      1. 3.2.1. 1. 交换两个变量的值
        1. 3.2.1.1. 2. 排序算法
        2. 3.2.1.2. 3. 二分查找
  4. 4. 写在最后

观前提示

本文中所有的代码都不保证可靠性,仅为一个便于理解的例子,如出现问题,本人概不负责,也请大家指正。

简介

本文简单的梳理了计导中的知识。

计算机程序设计语言

定义: 用于书写计算机程序的语言,用于表达和描述要加工的数据以及求解问题的步骤和过程。是根据预先定义的规则(语法)、由一个有限字母表上的字符构成的字符串的总体。

计算模型

  1. 图灵机
    1. 组成
      1. 一个无限长的纸带
      2. 一个读写头
      3. 内部状态
      4. 一个程序,用于对这个盒子进行控制
    2. 原理
      1. 根据程序的命令以及它的内部状态进行磁带的读写、移动 ,直至得到最后的结果。
  2. 自动机(有限状态自动机)
    1. 组成
      1. 一个有限状态控制器
      2. 一个读头
      3. 一条写有字符的输入带
    2. 工作原理
      1. 读头在输入带上从左向右移动,每当读头从带上读到一个字符时,便引起控制器状态的改变,同时读头右移一个符号的位置
    3. 状态转移图
      1. 点: 表示一种状态
      2. 边: 表示一种转移关系

C语言 (划重点)

语法

1. 定义

  1. 变量定义
    C 中常见的变量有以下几种

    1
    2
    3
    4
    5
    int a;
    long long b;
    char c;
    float b;
    double e;
  2. 函数定义

    1
    2
    3
    4
    return_type function_name( parameter list )
    {
    body of the function
    }
  3. 数组定义

    1. 一维数组
      1
      type arrayName[arraysize];
    2. 多维数组
      1
      type arrayName[arraysize1][..]..[..][arraysizen];
  4. 指针定义

    1
    type *var-name;

    type 是var-name所指向的类型

2. 输入输出

  1. 输入

    1
    2
    3
    int scanf(const char *format, ...);
    char *gets(char *s);
    char getchar(void);

    scanf()是格式化输入,
    gets()能读入一整行的字符,
    getcchar()能读入单独的一个字符

  2. 输出

    1
    2
    3
    int printf(const char *format, ...);
    int puts(const char *s);
    int putchar(int c);

    与上面类似
    printf() 是格式化输出,
    puts() 可以输出一个字符串,
    putchar() 可以输出一个单独的字符

  1. 格式化符号
字符 描述
d 有符号十进制数值int
u 十进制unsigned int
f double型输出10进制定点表示
s char数组字符串
c unsigned char

修饰符

字符 描述
l 对于整数类型,表示一个long尺寸的整型参数。 对于浮点类型,表示一个double尺寸的整型参数。
ll 对于整数类型,表示一个long long尺寸的整型参数。

更多内容参考printf format string

流程控制

  1. 判断语句

    1. if
      1
      2
      3
      4
      5
      if (...) {

      } else {

      }
      可以没有else 有多个嵌套
    2. switch
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      switch(...) {
      case ..:
      do some thing
      break;
      case ..:
      do some thing
      break;
      /* case的数量是任意的*/
      default: /* 可选的 */
      do some thing
      }
  2. 循环

    1. while
      1
      2
      3
      4
      while(condition)
      {

      }
    2. for
      1
      2
      3
      for ( init; condition; increment ) {

      }
    3. do…while
      1
      2
      3
      4
      do
      {

      }while( condition );

运算符

  1. 算术运算符 +-*/%
  2. 关系运算符 ==,!=,>,<,>=,<=
  3. 逻辑运算符 &&,||,!

结构体

1
2
3
4
5
6
7
struct struct_name {
type val_name_1;
...
type val_name_n;
} s1;

struct struct_name s2;
1
2
3
4
5
6
7
typedef struct {
type val_name_1;
...
type val_name_n;
}struct_name;

truct_name s1, s2;

一个结构体可以简单的理解为将多个变量组合成了一个变量。
在定义结构体之后,我们相当于构造了一种新的变量类型。
我们可以用这种变量类型来定义变量。
访问结构体中的变量需要使用 . 运算符。

指针

  1. 指向变量的指针
    指针变量存储了另一个变量的地址。
    比如
    1
    2
    int a;
    int *p = &a;
    这样 p 变量中就储存了 a 的地址。
    我们访问一个变量
    可以直接通过变量名访问
    也可以通过它的地址来间接访问它的值。
  1. 指向指针的指针
    我们知道指针也是一种变量
    所以我们也可以定义一个指向指针的指针,形如 int **p
    我们这样理解,p 指向了另一个指针,而那一个指针指向的是一个变量。
    我们可以直接将一个指针解引用后的值当做一个完整的变量。
    也就是说我们可以将 *p 当做一个整体来理解, 它在一定意义上与它指向的变量的变量名等价。
  1. 指向函数的指针

    1
    return_type (*function_name)( parameter list );

    请注意第一个括号不能省略, 否则将会变成返回一个指针的函数
    函数指针可以指向一个函数,其中 parameter list 中的参数名称可以省略,但不能省略参数名称。类似于函数声明。

  2. 指向结构体的指针
    指向结构体的指针与指向变量的指针类似。
    问题在于 . 运算符的优先级高于 *运算符的优先级,所以我们要去元素的话 (*a).b 一定要加括号。
    这样很麻烦,所以我们有一种新的运算符 ->, 则 (*a).b 等价于 a->b 这样更加简洁易懂。

函数传参与返回值

  1. 传参为按值传递,在函数内函数的参数不会影响原来的值。
  2. 如果想要修改原来的值,那么我们要传入的值一定是要修改的值的地址。
  3. 将数组作为函数参数时,只可以省略第一维的大小,而且其他维的大小在传参的时候都要对应,而且传入数组时,数组内的元素可以被修改。
  4. 函数无法返回一个数组。

字符串

在C语言中字符串就是字符数组。
字符串的结尾是'\0',对应ASCII码为0
在string.h 库中有不少关于字符串的常用函数如strlen(), strcpy()。
我这里不再展开,大家可以再网上查阅相关内容。

算法

1. 交换两个变量的值

假设我们有两个变量a和b, 我们要交换他们

1
2
3
int temp = a;
a = b;
b = temp;
2. 排序算法

我们主要学习一下冒泡排序
冒泡排序第k次循环将第k大(第k小)的数字移动到第k前(第k后)
然后在n-1轮之后就能获得一个排好序的数组

我们设 a[i] 是需要排序的数组。

1
2
3
4
5
6
7
8
9
for (int i = 1; i < n; i++) {
for (int j = 1; j <= n - i; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
3. 二分查找

我们先考虑最简单的二分法
假设我们有一个长度为 n 已经从小到大排序好的数组 a[i]
我们想知道一个数 $x$ 是否在 a[i] 中出现。
这时我们可以通过二分来找这个数

1
2
3
4
5
6
7
8
9
10
int l = 0, r = n, ans = n + 1;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] == x) {
ans = mid;
break;
}
if (a[mid] < x) l = mid + 1;
else (a[mid] > x) r = mid - 1;
}

最后求出的 ans 就是 $x$ 的位置, 如果没有找到的话 ans 就是 n + 1

另一种二分为二分答案
二分答案是指,我们对一个问题答案的值进行二分。
通过逻辑判断得出我们真正的答案是比我们分出的值大还是小, 从而修改 l,r 的值。
二分答案的条件是我们问题的答案具有单调性,
比如说,a 如果可行, 那么比 a 大的一定不可行, a 如果不可行, 比 a 小的一定不可行。
这样我们就可以进行二分了。

写在最后

由于篇幅有限,我很多内容不能写的很详细,也省略了一部分内容,很多内容还是要依靠大家自己复习。
希望大家能认真复习,祝愿大家在期末中取得好成绩。

计导成绩更多的来自于平时的积累,要多打代码,多刷OJ题,当代码量达到一定水平之后,量变就会引发质变,会让大家对编程有一个全新的理解。

本文作者 : NekoMio
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
本文链接 : https://www.nekomio.com/2019/12/18/155/

本文最后更新于 天前,文中所描述的信息可能已发生改变