CS50笔记 第三集
——哈佛大学CS50《计算机导论》课程(2019) 学习平台：哔哩哔哩
目录
CS50笔记 第三集
一、温故知新
（一）第一集 引言
1.什么是计算机科学?
2.如何表示input和output?
3.如何从input到output?
4.如何开始运行?
5.一些概念
（二）第二集 C语言
1.如何使用C语言平替scratch语言的格式？
（1）通用结构
（2）C语言功能
2.C语言如何运行程序？
（1）思路
（2）工具
3.一些概念
（1）数值类型
（2）CS50提供的函数
（3）占位符
（4）数字溢出
4.实践小妙招
（三）第三集 代码原理与优化
1.汇编底层原理是什么？
2.如何调试代码错误？
3.如何优化代码？
（1）数组
（2）字符串
（3）命令行参数
二、算法
（一）算法的种类
1.线性搜索（linear search）
2.二进制搜索（binary search）
（二）算法的描述术语
1.O
2.Ω
3.θ
（三）算法的编程实现
1.线性搜索
（1）简单实现
（2）自己定义数据类型
2.二进制搜索
（1）冒泡排序
（2）选择排序
（3）递归与合并排序
①递归
②合并排序
一、温故知新
（一）第一集 引言
1.什么是计算机科学?
计算机科学是指：解决问题的过程 ；input→〖一系列计算〗→output
2.如何表示input和output?
用二进制（0/1）表示input和output，二进制可以表示数字、文字、图片、视频、音乐
3.如何从input到output?
用算法实现从input到output，算法有优劣
4.如何开始运行?
通过伪代码翻译算法后运行
5.一些概念
函数、条件、布尔表达式、循环、变量、线程、事件、编程语言（C、Python、Scratch）
（二）第二集 C语言
1.如何使用C语言平替scratch语言的格式？
（1）通用结构
printf：print表示打印，f表示格式，即：打印格式化文本；<stdio.h>：printf等功能的保存位置；引号、分号要注意
（2）C语言功能
可以获取输入内容、设置变量、使用if······else······条件、使用while循环、for循环
2.C语言如何运行程序？
（1）思路
input→〖一系列计算〗→output
源代码→〖编译〗→机器代码
（2）工具
源代码编辑器：VScode、CS50 IDE等
编译器：MingW64
编译指令：Clang、ls、rm、mkdir、rmdir
3.一些概念
（1）数值类型
bool、char、double、float、int、long、string
（2）CS50提供的函数
get_char、get_double、get_float、get_int、get_long、get_string
（3）占位符
%c、%f、%i、%li、%s
（4）数字溢出
4.实践小妙招
①如果是在文件夹里面，编译时，需要带上文件夹的名字，用/分隔
②利用 .+数字+f 可以保留小数，保留几位数字填几
③ %是取余运算符；cd 可以转移到想要去的目录；//后面是注释
④cd 后面不加任何东西会返回最开始的目录；pwd 可以显示处于哪个目录下
⑤在终端按向上的箭头，可以复制之前输入的代码指令；字符引用采用单引号；||表示或
⑥for后面使用分号隔开，两个for循环的使用构成二维
⑦最开始的声明就是复制标题，告诉C，你见过这个函数了，可以编译了
（三）第三集 代码原理与优化
1.汇编底层原理是什么？
（1）预处理（preprocessing）
（2）编译(compiling)
（3）组装(assembling)
（4）链接(linking)
2.如何调试代码错误？
（1）help50
（2） printf
（3）断点调试debug50
（4）check50
（5）style50
3.如何优化代码？
（1）数组
数组：表示相同类型的值的列表
表面上，电脑存储的是字符，实际上是存储的代表这些字符的都是二进制代码，所以不同类型的数据之间，是可以相互转换的
PS：
不要出现重复硬编码，因为更改时，可能会忽略；可以使用变量/常量
C语言整数/整数结果为整数
（2）字符串
数组与字符串的本质相同
数组与单个变量转换，内存是确定的,1int=4个位，同样的，数组与字符串本质相同，可以用[]访问字符串中的单个字符
s[0]表示字符串的起点，空字符(8位0）表示字符串结束，那么就可以用[]获取字符串数组中的字符
（3）命令行参数
指在程序之后的提示符下键入一个或多个单词，即取代get_string/get_int等
PS：main函数的输入与返回值，文件名称存储于argv[0]中，第一个输入存储在为argv[1]
二、算法
（一）算法的种类
1.线性搜索（linear search）
①伪代码表示的线性搜索
2.二进制搜索（binary search）
①伪代码表示的二进制搜索
（二）算法的描述术语
1.O
①不用术语描述的算法
②用术语
O描述的算法
③当问题足够大时，n与n/2效率并无区别，称为n的量级，log下面的2，也可以没有
O（
）：冒泡排序，选择排序
O（
）：合并排序
O（n）：线性搜索（linear search）
O（
）：二进制搜索（binary search）
O（1）
2.Ω
Ω（）：选择排序
Ω（
）：合并排序
Ω（n）：冒泡排序（当无交换就停止时）
Ω（）
Ω（1）：线性搜索（linear search）、二进制搜索（binary search）
3.θ
θ：描述最优解与最差解相同的算法
（）：选择排序
（）：合并排序
（n）
（）
（1）
（三）算法的编程实现
1.线性搜索
（1）简单实现
①线性搜索int：是成功的
②线性搜索字符串：失败（第10行）无法实现，因为字符串不是数据类型，而是一个数组，既然是数组，就可能有多个char,在C语言中，需要比较每一个字符相同，字符串才会相同，python语言倒是可以直接比较
③线性搜索字符串：成功，可以用string.h文件中的strcmp去比较字符串，两个字符串相同时，返回0
④找到EMMA的电话：前提是名字与电话本身已经一一对应
（2）自己定义数据类型
关键词：
typedef：定义一个类型
struct：可以放置多种数据类型的容器
自己定义如string的数据类型用来寻找emma的电话案例
2.二进制搜索
二进制搜索需要先排序
（1）冒泡排序
定义：比较相邻的元素并交换它们的位置来排序，每次都会将当前未排序部分中的最大元素移动到末尾。
遍历次数：(n-1)*(n-1)
时间：最差：O（）；最好：Ω（）
如果规定：没有交换就停止，那么最好的是：Ω（n）
（2）选择排序
定义：从未排序的部分中选出最小的元素，放到已排序部分的末尾
遍历次数：第一个用时：n；第二个n-1；第三个n-2；以此类推，合计：n（n+1）/2=n²/2+n/2
时间：最差：O（）；最好：Ω（）
（3）递归与合并排序
①递归
A.递归伪代码示例
B.用迭代循环实现金字塔编程示例
C.用递归实现金字塔
②合并排序
A.合并排序伪代码
B.合并排序流程图
分成2半的时间需要：
(如上面的3行）
每次合并需要读取所有元素，即所需时间为n（如上面的8列）
时间：最差：O（）；最好：Ω（）
