CS50笔记 笔记整理

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（）；最好：Ω（）