观前提示
本文中所有的代码都不保证可靠性,仅为一个便于理解的例子,如出现问题,本人概不负责,也请大家指正。
简介
本文简单的梳理了计导中的知识。
计算机程序设计语言
定义: 用于书写计算机程序的语言,用于表达和描述要加工的数据以及求解问题的步骤和过程。是根据预先定义的规则(语法)、由一个有限字母表上的字符构成的字符串的总体。
计算模型
- 图灵机
- 组成
- 一个无限长的纸带
- 一个读写头
- 内部状态
- 一个程序,用于对这个盒子进行控制
- 原理
- 根据程序的命令以及它的内部状态进行磁带的读写、移动 ,直至得到最后的结果。
- 组成
- 自动机(有限状态自动机)
- 组成
- 一个有限状态控制器
- 一个读头
- 一条写有字符的输入带
- 工作原理
- 读头在输入带上从左向右移动,每当读头从带上读到一个字符时,便引起控制器状态的改变,同时读头右移一个符号的位置
- 状态转移图
- 点: 表示一种状态
- 边: 表示一种转移关系
- 组成
C语言 (划重点)
语法
1. 定义
变量定义
C 中常见的变量有以下几种1
2
3
4
5int a;
long long b;
char c;
float b;
double e;函数定义
1
2
3
4return_type function_name( parameter list )
{
body of the function
}数组定义
- 一维数组
1
type arrayName[arraysize];
- 多维数组
1
type arrayName[arraysize1][..]..[..][arraysizen];
- 一维数组
指针定义
1
type *var-name;
type 是var-name所指向的类型
2. 输入输出
输入
1
2
3int scanf(const char *format, ...);
char *gets(char *s);
char getchar(void);scanf()
是格式化输入,gets()
能读入一整行的字符,getcchar()
能读入单独的一个字符输出
1
2
3int printf(const char *format, ...);
int puts(const char *s);
int putchar(int c);与上面类似
printf()
是格式化输出,puts()
可以输出一个字符串,putchar()
可以输出一个单独的字符
- 格式化符号
字符 | 描述 |
---|---|
d | 有符号十进制数值int |
u | 十进制unsigned int |
f | double型输出10进制定点表示 |
s | char数组字符串 |
c | unsigned char |
修饰符
字符 | 描述 |
---|---|
l | 对于整数类型,表示一个long尺寸的整型参数。 对于浮点类型,表示一个double尺寸的整型参数。 |
ll | 对于整数类型,表示一个long long尺寸的整型参数。 |
更多内容参考printf format string
流程控制
判断语句
- if可以没有else 有多个嵌套
1
2
3
4
5if (...) {
} else {
} - switch
1
2
3
4
5
6
7
8
9
10
11switch(...) {
case ..:
do some thing
break;
case ..:
do some thing
break;
/* case的数量是任意的*/
default: /* 可选的 */
do some thing
}
- if
循环
- while
1
2
3
4while(condition)
{
} - for
1
2
3for ( init; condition; increment ) {
} - do…while
1
2
3
4do
{
}while( condition );
- while
运算符
- 算术运算符
+-*/%
- 关系运算符
==
,!=
,>
,<
,>=
,<=
- 逻辑运算符
&&
,||
,!
结构体
1 | struct struct_name { |
1 | typedef struct { |
一个结构体可以简单的理解为将多个变量组合成了一个变量。
在定义结构体之后,我们相当于构造了一种新的变量类型。
我们可以用这种变量类型来定义变量。
访问结构体中的变量需要使用 .
运算符。
指针
- 指向变量的指针
指针变量存储了另一个变量的地址。
比如这样1
2int a;
int *p = &a;p
变量中就储存了a
的地址。
我们访问一个变量
可以直接通过变量名访问
也可以通过它的地址来间接访问它的值。
- 指向指针的指针
我们知道指针也是一种变量
所以我们也可以定义一个指向指针的指针,形如int **p
。
我们这样理解,p
指向了另一个指针,而那一个指针指向的是一个变量。
我们可以直接将一个指针解引用后的值当做一个完整的变量。
也就是说我们可以将*p
当做一个整体来理解, 它在一定意义上与它指向的变量的变量名等价。
指向函数的指针
1
return_type (*function_name)( parameter list );
请注意第一个括号不能省略, 否则将会变成返回一个指针的函数
函数指针可以指向一个函数,其中parameter list
中的参数名称可以省略,但不能省略参数名称。类似于函数声明。指向结构体的指针
指向结构体的指针与指向变量的指针类似。
问题在于.
运算符的优先级高于*
运算符的优先级,所以我们要去元素的话(*a).b
一定要加括号。
这样很麻烦,所以我们有一种新的运算符->
, 则(*a).b
等价于a->b
这样更加简洁易懂。
函数传参与返回值
- 传参为按值传递,在函数内函数的参数不会影响原来的值。
- 如果想要修改原来的值,那么我们要传入的值一定是要修改的值的地址。
- 将数组作为函数参数时,只可以省略第一维的大小,而且其他维的大小在传参的时候都要对应,而且传入数组时,数组内的元素可以被修改。
- 函数无法返回一个数组。
字符串
在C语言中字符串就是字符数组。
字符串的结尾是'\0'
,对应ASCII码为0
在string.h 库中有不少关于字符串的常用函数如strlen(), strcpy()。
我这里不再展开,大家可以再网上查阅相关内容。
算法
1. 交换两个变量的值
假设我们有两个变量a和b, 我们要交换他们
1 | int temp = a; |
2. 排序算法
我们主要学习一下冒泡排序
冒泡排序第k次循环将第k大(第k小)的数字移动到第k前(第k后)
然后在n-1
轮之后就能获得一个排好序的数组
我们设 a[i]
是需要排序的数组。
1 | for (int i = 1; i < n; i++) { |
3. 二分查找
我们先考虑最简单的二分法
假设我们有一个长度为 n
已经从小到大排序好的数组 a[i]
。
我们想知道一个数 $x$ 是否在 a[i]
中出现。
这时我们可以通过二分来找这个数
1 | int l = 0, r = n, ans = n + 1; |
最后求出的 ans
就是 $x$ 的位置, 如果没有找到的话 ans
就是 n + 1
另一种二分为二分答案。
二分答案是指,我们对一个问题答案的值进行二分。
通过逻辑判断得出我们真正的答案是比我们分出的值大还是小, 从而修改 l,r
的值。
二分答案的条件是我们问题的答案具有单调性,
比如说,a
如果可行, 那么比 a
大的一定不可行, a
如果不可行, 比 a
小的一定不可行。
这样我们就可以进行二分了。
写在最后
由于篇幅有限,我很多内容不能写的很详细,也省略了一部分内容,很多内容还是要依靠大家自己复习。
希望大家能认真复习,祝愿大家在期末中取得好成绩。
计导成绩更多的来自于平时的积累,要多打代码,多刷OJ题,当代码量达到一定水平之后,量变就会引发质变,会让大家对编程有一个全新的理解。