C语言程序设计
目录
- 目录
- 0. 简介
- 1. 第一章 C语言快速入门
- 2. 第二章 输入输出和基本运算
- 3. 分支语句和循环语句
- 4. 第四章 循环综合应用
- 5. 第五章 数组
- 6. 第六章 函数和位运算
- 7. 第七章 字符串
- 8. 第八章 指针(一)
- 9. 第九章 指针(二)
- 10. 第十章 程序结构和简单算法
- 11. 第十一章 文件读写
- 12. C++的STL
0. 简介
这篇博客记录了北大郭炜老师的网课: 程序设计与算法(一)C语言程序设计的随堂笔记。该课程有对应的讲义与习题,讲义在MOOC网站上有,习题在openjudge网站上有。具体课程而言,我选择了第十六次开课。
1. 第一章 C语言快速入门
1.1. 信息在计算机中的表示
1.1.1. 用0和1表示各种信息
- 计算机中的所有信息都是用0、1表示
- 二进制数的一位,称为一个比特(bit), 简写b
- 八个二进制位称为一个字节(byte), 简写B
- 1KB, 1MB, 1GB, 1TB
- ASCII编码方案:用8个连续的0或1来表示一个字母数字和标点符号,一共有256种不同的组合
1.1.2. 十进制到二进制的互相转换
- 十进制数是数的十进制表示形式的简称
- 短除法,每次除以进制,余数就是这个进制的最小位数
1.1.3. K进制小数
- K进制小数和整数的定义类似,只不过变成了K的负次方,比如小数后的第一位是$K^{-1}$
1.1.4. 十六进制数到二进制数的相互转换
1.2. C语言快速入门
- 空格也是一个字符
- C语言中输入输出: scanf、printf
- 程序的注释:
- 多行注释: /* … */
- 单行注释: //
1.3. 变量和数据类型初探
1.3.1. 什么是变量
- 变量就是一个代号, 程序运行时系统会自动为变量分配内存空间,于是变量就代表了系统分配的那片内存空间
- 变量有名字和类型两种属性,变量的类型决定了一个变量占用多少个字节
- 变量的定义要在使用之前
- 一个变量不能定义两次
1.3.2. 变量的命名规则
- 变量不能以数字开头
- 变量只能由大小写字母、数字和下划线组成
- 变量名不能和C++系统预留的一些保留字重复
1.3.3. C++的基本数据类型
- float的取值范围是绝对值的范围
- 整型、实数型、布尔型、字符型
- 用sizeof()可以返回数据类型所占的字节数
- 变量在定义的时候可以给它指定一个初始值
1.4. 变量和数据类型进阶
- 整型可以分为有符号整型和无符号整型
- 有符号整数的表示方式
- 将最左边的位看作符号位,符号位为0表示非负数,其绝对值就是除去符号位以外的部分
- 符号位为1,则表示是负数,其绝对值是除符号位以外的部分取反后加1
- 将一个负整数转化为有符号整数是: 符号位取1,其余部分取该负整数的绝对值的二进制表示取反加1
1.4.1. 数据类型的自动转换
- 有些不同的数据类型之间是相容的,可以相互赋值
- int a = 11.34, 其实就是a=11
- 整型数据也可以转换为字符型数据, 但只会留下最右边的一个字节
- 看一个例子
1.5. 常量
1.5.1. 整型常量
- 十六进制整型常量以0x开头
- 一个十六进制位正好对应四个二进制位
- 0开头的是八进制数
1.5.2. 字符型常量
- 字符型常量表示一个字符,用单引号括起来
- 字符型常量和变量都占一个字节,内部存放的是ASCII编码
- 小写字母的ASCII编码比大写字母大
- 字符型常量中有一部分以‘\’开头, 被称为转义字符
- 字符串常量用双引号括起来,字符常量用单引号括起来
1.5.3. 符号常量
- 为了阅读和修改方便, 常用一个由字母和数字组成的符号来代表某个常量
- #define 常量名 常量值
- 尽量多用符号常量,少用数值常量
2. 第二章 输入输出和基本运算
2.1. 输入输出进阶
2.1.1. 输入输出控制符
- 在printf和scanf中可以使用以%开头的控制符,指明要输入和输出的数据类型
- 常用的格式控制符
2.1.2. 用scanf读入不同类型的变量
- 输入字符时,不会跳过空格
- 如果在输入中有scanf中出现的非控制字符,则这些字符会被跳过
2.1.3. 控制printf输出整数的宽度
- 比如用%nd和%0nd控制输出整型的长度
- 用%.nf控制输出浮点数的精度
2.1.4. 用C++的cout进行输出
- cout « …
- endl可以进行换行
2.1.5. 用C++的cin进行输入
- cin » …
- cin、cout的速度比printf、scanf慢,输入输出数据量大的时候用后者
- 一个程序不要同时使用cout和printf
2.2. 算术运算符和算术表达式
2.2.1. 赋值运算符
- a += b 等同于 a = a + b
2.2.2. 算术运算符
- 加减乘除
- %表示取余数
- 两个整数进行加减乘都可能导致计算结果超出了结果类型所能表示的范围,这种情况就是溢出
- 如果溢出,则直接丢弃溢出的部分
- 有时计算的最终结果似乎不会溢出,但中间结果可能溢出,这也会导致程序出错
- 解决溢出的办法是尽量使用高精度的数据类型
- 除法的结果、类型和操作数中精度高的类型相同
2.2.3. 模运算
- 求余数的运算符%也称为模运算符,两个操作数都是整数类型
2.2.4. 自增运算符 ++
- 自增运算符有前置用法和后置用法
- 前置用法: ++ a 表示将a的值加1,表达式返回a+1后的值
- 后置用法: a ++ 表示将a的值加1,表达式返回值为a加1前的值
2.3. 关系运算符和逻辑表达式
2.3.1. 关系运算符
- 一共有六种关系运算符用于数值的比较
- 比较的结果是bool类型
2.3.2. 逻辑运算符和逻辑表达式
- 逻辑运算符用于表达式的逻辑操作,有&&、||、!这三种,操作结果为true或false
- 逻辑表达式是短路运算,即对逻辑表达式的计算在整个表达式的值已经能够断定的时候停止
2.4. 其他运算符及运算符优先级
2.4.1. 强制类型转换运算符
- (int)、(char)这样的运算符就是强制将操作数转换为指定类型
2.4.2. 部分运算符的优先级
3. 分支语句和循环语句
3.1. if语句
3.1.1. 条件分支结构
- 有时候我们希望满足一个条件执行一种语句,另一个条件执行另一种语句
3.1.2. if语句
- if语句可以没有else if,也可以没有else
- 如果语句组只有一条语句,则不需要{}
- if语句可以嵌套
- else总是和离它最近的if配对,加一个花括号可以解决这个问题
3.2. switch语句
- 可以没有default语句
- 注意常量表达式不能带变量
3.3. for循环
3.3.1. for循环语句
- 注意是先执行语句组然后执行表达式3
- 表达式1和表达式3都可以是用逗号连接的若干个表达式
- for循环可以嵌套,形成多重for循环
- for语句括号里面的表达式1、表达式2、表达式3可以任何一个都不写,但是分号必须保留
3.4. while循环和do while循环
3.4.1. while循环
3.4.2. do while循环
- 如果希望循环至少要执行一次,那么可以用do while循环
4. 第四章 循环综合应用
4.1. break语句和continue语句
4.1.1. break语句
- break语句出现在循环体中,其作用是跳出循环
- 在多重循环中,break语句只能跳出直接包含它的那一重循环
4.1.2. continue语句
- continue可以出现在循环体中,其作用是立即结束本次循环,并回到循环开头判断是否要进行下一次循环
4.2. OJ输入数据的处理
4.2.1. scanf表达式的值
- scanf()表达式其实是有返回值的,返回值为int类型,表示成功读入的变量个数
- scamf()值为EOF则说明输入数据已经结束
- ctrl+z表示输入结束
- 这样就可以处理无结束标记的OJ题目输入
4.2.2. 用freopen重定向输入
- 调试程序时,每次运行程序都要输入测试数据,太麻烦
- 可以将测试数据存入文件,然后用freopen将输入由键盘重定向为文件,则运行程序时不再需要输入数据
5. 第五章 数组
5.1. 数组
- 数组可以用来表达类型相同的元素的集合,集合的名字就是数组名
- 一维数组的定义方法如下:
- 元素个数必须是常量或常量表达式
- sizeof()可以访问数组所占字节
- 数组名代表数组的地址
- 数组一般不要定义在main里面,尤其是大数组
5.2. 筛法求素数
- 之前我们判断一个数n是不是素数,使用2到根号n之间的所有整数去除n,也就是穷举
- 筛法:把2到n中所有的数都列出来,然后从2开始,先划掉n内所有2的倍数,然后每次从下一个剩下的数开始,划掉其n内的所有倍数,最后剩下的数就是素数
- 筛法会稍微快一点,用空间换时间
- 代码如下:
5.3. 数组初始化
- 在定义一个一维数组的同时,可以给数组中的元素赋初值
- 如果在定义数组的时候,如给全部元素赋值,则可以不给出数组元素的个数
- 可以用数组取代复杂分支结构
- 使用string须包含头文件
5.4. 数组越界
- 数组元素的下标,可以是任何整数,可以是负数,也可以大于数组的元素个数,不会导致编译错误
- 但如果将越界写入了别的变量的内存空间,就很有可能出错
5.5. 二维数组
- 二维数组的定义:
- 二维数组的访问可以直接用下标访问
- 二维数组的初始化也是用{}
- 二维数组初始化时,如果对每行都进行初始化,则不用写行数或列数
6. 第六章 函数和位运算
6.1. 函数
- 函数可以实现某一功能,当程序中需要使用该项功能时,只需要写一条语句,调用实现该功能的函数即可
- 函数的定义:
- 函数的调用: 函数名(参数1, 参数2…)
- 函数中至少含有一个return, 如果函数的类型为void, 则用return;
- 定义函数的参数叫做形参, 调用函数时的参数叫做实参
- 函数的定义一般在调用之前
- 但是函数的调用语句前面有函数的声明即可,不一定要有定义
- C/C++程序从main函数开始
- 函数的形参是实参的一个拷贝,形参的改变一般不会影响到实参
- 一维数组作为形参时不用写出元素的个数,这时候形参的改变会影响实参
- 二维数组作为形参时,必须写明数组有多少列,不用写明有多少行
6.2. 递归初步
- 一个函数,自己调用自己,就是递归
- 递归函数得有终止条件
6.3. 库函数和头文件
- 头文件<cmath>中包含很多数学库函数的声明
- 库函数的定义一般在.lib文件中
- 库函数: C/C++标准规定, 编译器自带的函数
- 头文件: C++编译器提供许多头文件, 比如: iostream、cmath、string
- 头文件内部包含很多库函数的声明以及其他信息, 比如cin、cout的定义
6.4. 位运算
- 位运算: 用于对整数类型变量中的某一位(bit)或者若干位进行操作
- C++提供了六种位运算符来进行位运算操作
6.4.1. 按位与&
- 比如表达式(21 & 18)的结果是16
- 通常用来将某变量中的某些位清0且同时保留其他位不变
6.4.2. 按位或|
- 比如“21|18”的结果是23
- 按位或运算通常用来将某些变量中的某些位置1且保留其他位不变
6.4.3. 按位异或^
- 异或是逻辑运算, 如果两个值相同返回0, 如果两个值不同返回1
- 异或运算通常用来将某变量中的某些位取反
- 异或运算的特点:
6.4.4. 按位非~
- 按位非运算符~是单目运算符,其功能是将操作数中的二进制位0变成1,1变成0
6.4.5. 左移运算符«
- 9 « 4 表示将9的二进制表示左移4位
6.4.6. 右移运算符»
- 右移时,移出最右边的位就被丢弃
- 对于有符号数,在右移时,符号位将一起移动,并且大多数C++编译器规定,如果圆符号位为1,则右移时高位就补充1,原符号位为0,则右移时高位就补充0
7. 第七章 字符串
7.1. 字符串的形式和存储
- 字符串常量占据内存的字节数等于字符串中字符数目加1,多出来的是结尾字符'\0'
- 空串""也是合法的字符串常量
- 包含'\0'字符的一维char数组,就是一个字符串,其中存放的字符串即为'\0'前面的字符组成
- 可以给一维数组这么赋值: char title[] = "Prison Break"
- '\0'可以视为字符数组结束标志
7.2. 输入字符串
- 用scanf也可以将字符串读入字符数组
- scanf会自动添加结尾’\0’
- scanf读入到空格为止
- scanf(“%s”, line) 不用取地址符
- 读入一行到字符串组: cin.getline(char buf[], int bufsize), 读入一行,自动添加’\0’, 回车换行符不会写入buf, 但是会从输入流中去掉
- 也可以用gets(char buf[])来读入一行到字符数组,回车换行符不会写入buf,但是会从输入流中去掉,可能导致数组越界
7.3. 字符串库函数
- 使用字符串库函数需要 #include <cstring>
- 形参为char []类型,则实参可以是char数组或字符串常量
- 字符串拷贝 strcpy(char[] dest, char[] src) 拷贝src到dest
- 字符串比较大小 int strcmp(char[] s1, char[] s2) 是根据字符的ASCII码值进行比较,大写字母比小写字母小
- 求字符串长度 int strlen(char[] s)
- 字符串拼接 strcat(char[] s1, char[] s2) 将s2拼接到s1后面
- 字符串转成大写 strupr(char [])
- 字符串转成小写 strlwr(char [])
8. 第八章 指针(一)
8.1. 指针的基本概念和用法
- 指针也称作指针变量,大小为4个字节(或8个字节)的变量,其内容代表一个内存地址
- 通过指针,能够对该指针指向的内存区域进行读写
- 指针的定义: 类型名 * 指针变量名
- 比如: int * p = (int *) 40000
- p指向地址40000,地址p就是地址40000
- * p就代表地址40000开始处的若干个字节的内容
- 我们可以通过指针访问其指向的内存空间
- 指针定义总结
- 指针用法,一般是让指针指向一个变量的地址
8.2. 指针的意义和相互赋值
- 有了指针,就有了自由访问内存空间的手段
- 不同类型的指针,如果不经过强制类型转换,不能直接互相赋值
8.3. 指针的运算
- 两个同类型的指针变量,可以比较大小
- 两个同类型的指针变量,可以相减
- 指针变量加减一个整数的结果是指针
- 指针变量可以自增自减
- 指针可以用下标运算符[]进行运算
8.4. 指针作为函数参数
- 地址0不能访问,指向地址0的指针就是空指针
- 可以用NULL关键字对任何类型的指针进行赋值,NULL实际上就是整数0.值为NULL的指针就是空指针
- 指针可以作为条件表达式使用,如果指针的值为NULL,则相当于为假,值不为NULL,就相当于为真
8.5. 指针和数组
- 数组的名字是一个指针常量,指向数组的起始地址
- 作为函数形参时, T *p与 T p[] 等价
9. 第九章 指针(二)
9.1. 指针和二维数组、指向指针的指针
- 二维数组的每一行都是一维数组,也就是指针
- 指向指针的指针:
9.2. 指针和字符串
- 字符串常量的类型就是char *
- 字符数组名的类型也是char *
9.3. 字符串库函数
- 字符串操作库函数
- 这些字符串操作库函数都需要include<cstring>
9.4. void指针和内存操作函数
- void指针: void * p
- 可以用任何类型的指针对void指针进行赋值或初始化
- 对于void指针,*p没有定义,++p、–p,p += n、p+n、p-n均无定义
- 内存操作库函数memset
- 内存操作库函数memcpy
9.5. 函数指针
- 程序运行期间,每个函数都会占用一段连续的内存空间。而函数名就是该函数所占内存区域的起始地址(也称入口地址)
- 我们可以将函数的入口地址赋给一个指针变量,使该指针变量指向该函数,然后通过指针变量就可以调用这个函数,这种指向函数的指针变量称为函数指针
- 定义形式:
- 使用方法:
- 函数指针和qsort库函数
- pfcompare是比较函数
10. 第十章 程序结构和简单算法
10.1. 结构
- 在现实问题中,常常需要用一组不同类型的数据来描述一个事物
- C++允许程序员自己定义新的数据类型。因此针对“学生”这种事物,可以定义一种新名为Student的数据类型,一个student类型的变量就能描述一个学生的全部信息,同理,还可以定义数据类型worker来表示工人
- 结构(struct): 用struct关键字来定义一个结构,也就定义了一个新的数据类型
- student即成为自定义的类型的名字,可以用来定义变量
- 两个同类型的结构变量,可以相互赋值,结构变量之间不能用比较运算符进行计算
- 一般来说,一个结构变量所占的内存空间的大小就是结构中所有成员变量大小之和
- 一个结构的成员变量可以是任何类型的,包括可以是另一个结构类型
- 结构的成员变量可以是指向本结构类型的变量的指针
- 访问结构变量的成员变量: 一个结构变量的成员变量完全可以和一个普通变量一样来使用,也可以取得其地址
- 结构变量名.成员变量名
- 结构变量可以在定义时进行初始化:(使用花括号和逗号)
- 结构数组也可以定义,就是把结构体名字看作变量类型使用
- 指向结构变量的指针,通过指针访问其指向的结构变量的成员变量
10.2. 全局变量、局部变量、静态变量
- 定义在函数内部的变量叫局部变量(函数的形参也是局部变量)
- 定义在所有函数的外面的变量叫做全局变量
- 全局变量在所有函数中均可以使用,局部变量只能在定义它的内部函数中使用
- 静态变量: 全局变量都是静态变量,局部变量定义时如果前面加了static关键字,则该变量也成为静态变量
- 静态变量在整个程序运行期间都是固定不变的
- 局部变量在函数每次调用时地址都可能不同
- 如果未明确初始化,则静态变量会被自动初始化为全0,局部非静态变量的值则随机
- 静态变量只初始化一次,也就是下次调用函数的时候不进行初始化
10.3. 变量的作用域和生存周期
- 变量名、函数名、类型名统称为标识符
- 一个标识符能够起作用的范围,叫做该标识符的作用域
- 使用标识符的语句,必须出现在它们的声明或者定义之后
- 在单文件的程序中,结构、函数和全局变量的作用域是其定义所在的整个文件
- 函数的形参的作用域是整个函数
- 局部变量的作用域,是从定义它的语句开始,到包含它的最内层的那一对大括号{}的右大括号为止
- for循环里定义的循环控制变量,其作用域是整个for循环
- 同名标识符的作用域,可能一个被另一个包含,则在小的作用域里,作用域大的那个标识符被屏蔽,不起作用
- 所谓变量的生存期,值的是在此期间,变量占有内存空间,其占有的内存空间只能归它使用,不会用来存放别的东西
- 而变量的生存期终止,就意味着该变量不再占有内存空间,它原来占有的内存空间,随时可能被派作他用
- 全局变量的生存期,从程序被装入内存开始,到整个程序结束
- 静态局部变量的生存期,从定义它的语句第一次被执行开始,直到程序结束
- 函数形参的生存期从函数执行开始,到函数返回时结束,非静态局部变量的生存期,从执行到定义它的语句开始,一旦程序执行了它的作用域之外,其生存期即告终止
10.4. 选择排序和插入排序
10.4.1. 选择排序
- 排序问题: 编程接收键盘输入的若干个整数,排序后从小到大输出,先输入一个整数n,表明有n个整数需要排序,接下来再输入待排序的n个整数
- 选择排序:
- 选择最小的整数,与第i位的整数更换位置
10.4.2. 插入排序
- 插入排序就是将数组分为有序和无序,每次让无序最左边的元素与有序分别比较,插入到合适的位置
10.5. 冒泡排序
- 冒泡排序同样是将数组分为有序和无序两组,无序在左边,有序在右边,每次将无序部分两两比较,较大的在右边
- 上面三种简单排序算法,都要做$n^2$量级次数的比较,其中n是元素个数
- 而比较好的排序算法,如快速排序,归并排序等,只需要做$n*log_2n$量级次数的比较
10.6. 程序或算法的时间复杂度
- 一个程序或算法的时间效率,也称为时间复杂度,有时简称复杂度
- 复杂度常用大的字母O和小写字母n来表示,比如O(n), n代表问题的规模
- 复杂度也有平均复杂度和最坏复杂度两种,两种可能一致,也可能不一致
- 如果复杂度是多个n的函数之和,则只关心随n的增长增长得最快的那个函数
- 一些例子
11. 第十一章 文件读写
11.1. 文件读写概述
- 二进制文件: 本质上所有文件都是0、1串,因此都是二进制文件。但是一般将内容不是文字,记事本打开看是乱码的文件,称为二进制文件
- 文本文件: 内容是文字,用记事本打开能看到文字的文件
- 文件读写相关函数在头文件cstdio中声明: #include <cstdio>
- fopen函数打开文件,返回FILE * 指针,指向和文件相关的一个FILE变量,FILE是一个struct
- 文件读写结束后,一定要fclose关闭文件,否则可能导致数据没被保存,或者无法打开其他文件
- 一些读写函数都需要FILE *指针进行
11.1.1. 打开文件的函数
- 打开文件的模式
- 二进制打开和文本打开的区别:
- 主要是二进制打开的话会有换行符的区别,最好还是用二进制打开
- 文件名的绝对路径和相对路径:
11.2. 文本文件读写
11.2.1. 文本文件读写
- 我们希望写一个文件读写程序:
11.2.1. 文本文件读写(另一种函数)
- fgets是读取一行
- 读取整个文本文件并输出
- fputs是输出一行
11.3. 二进制文件读写概述
11.3.1. 文件的读写指针
- 这都是C语言读写的规则
- fseek的作用是将读写指针定位到距离origin位置offset字节处
11.3.2. 二进制文件读写
- 用fread进行二进制读文件
- 用fgetc进行二进制读文件
-
fgetc是用来读取一个字节
-
用fwrite二进制写文件
- 用fputc二进制写文件
11.4. 创建和读取二进制文件
- 用二进制文件存学生信息比用文本方式存的好处: 可能节约空间、便于快速读取、改单个学生信息
11.5. 修改二进制文件
- 用r+b打开文件既读又写时,如果做了读操作,则做写操作之前一定要用fssek重新定位文件读写指针
11.6. 文件拷贝程序
- 文件拷贝程序mycopy示例
12. C++的STL
12.1. STL排序算法sort
- STL: standard template library 标准模板库
- 包含一些常用的算法如排序查找,还有常用的数据结构如可变长数组、链表、字典等
- 要使用其中的算法,需要#include <algorithm>
- 用sort进行排序(用法一)
- 用sort进行排序(用法二)
- 用sort进行排序(用法三),用自定义的排序规则对任何类型T的数组进行排序
- 几个自定义排序规则例子
12.2. STL二分查找算法
12.2.1. 用binary_search进行二分查找
- 用法一:
- 用法二:
12.2.2. 用lower_bound二分查找下界
- 用法一:
- 用法二:
12.2.3. 用upper_bound二分查找上界
- 用法一:
- 用法二:
12.3. multiset
- STL中的平衡二叉树数据结构
- 有时需要在大量增加、删除数据的同时,还要进行大量数据的查找
- 可以使用平衡二叉树数据结构存放数据,体现在STL中,就是以下四种排序容器: multiset、set、multimap、map
- multiset的用法:
- multiset上的迭代器
- 自定义排序规则的multiset用法:
12.4. set
- set和multiset的区别在于容器里面不能有重复元素
- set插入元素可能不成功
- pair模板的用法
- set的例子
12.5. multimap
- multimap容器里面的元素,都是pair形式的
- multimap的应用
- 代码实现细节
12.6. map
- map和multimap的区别: 不能有关键字重复的元素, 可以使用[], 下标为关键字, 返回值为first和关键字相同的元素的second
- 插入元素可能失败
Comments