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