CS50笔记 第八集——哈佛大学CS50《计算机导论》课程(2019) 学习平台哔哩哔哩目录CS50笔记 第八集一第一集 引言1.什么是计算机科学?2.如何表示input和output?3.如何从input到output?4.如何开始运行?5.一些概念二第二集 C语言1.如何使用C语言平替scratch语言的格式2.C语言如何运行程序3.一些概念三第三集 代码原理与优化1.汇编底层原理是什么2.如何调试代码错误3.如何优化代码四第四集 算法1.算法的种类有哪些2.如何描述算法3.如何用编程实现算法五第五集 内存与指针1.内存地址怎么表示2.内存地址指针有什么用六第六集 数据结构1.数据结构有那些2.数据结构能解决哪些问题七第七集 python1.python语法是怎样的2.python有什么用3.python有何独特之处二、SQL(Structured Query Language 结构化查询语言一SQL基础1..csv文件2.sqlite3库二关系型数据库relational databases1.C\R\U\D2.SQL数据类型3.SQL特有语法实践三数据处理1.数据下载2.数据提取1用python提取数据2用SQL提取数据①格式转换②提取数据三、CS50听课感想一第一集 引言1.什么是计算机科学?计算机科学是指解决问题的过程input→〖一系列计算〗→output2.如何表示input和output?用二进制0/1表示input和output二进制可以表示数字、文字、图片、视频、音乐3.如何从input到output?用算法实现从input到output算法有优劣4.如何开始运行?通过伪代码翻译算法后运行5.一些概念函数、条件、布尔表达式、循环、变量、线程、事件、编程语言C、Python、Scratch二第二集 C语言1.如何使用C语言平替scratch语言的格式C语言可以获取输入内容、设置变量、使用if······else······条件、使用while循环、for循环2.C语言如何运行程序1思路input→〖一系列计算〗→output源代码→〖编译〗→机器代码2工具源代码编辑器VScode、CS50 IDE等编译器MingW64编译指令Clang、ls、rm、mkdir、rmdir、pwd显示处于哪个目录下3.一些概念数值类型bool、char、double、float、int、long、string占位符%c、%f、%i、%li、%s数字溢出三第三集 代码原理与优化1.汇编底层原理是什么预处理、编译、组装、链接2.如何调试代码错误help50、 printf 、断点调试debug50、check50、style503.如何优化代码用数组、字符串、命令行参数优化PSmain函数的输入与返回值文件名称存储于argv[0]中第一个输入存储在为argv[1]四第四集 算法1.算法的种类有哪些线性搜索、二进制搜索2.如何描述算法O最差解Ω最优解θ最优解与最差解相同的算法3.如何用编程实现算法1线性搜索自己定义数据类型typedef、struct2二进制搜索冒泡排序、选择排序、递归与合并排序五第五集 内存与指针1.内存地址怎么表示用16进制0x表示指针计算机内存中的地址用数据类型*来表示地址是什么*前往地址2.内存地址指针有什么用1string 的底层原理与指针关联①string 的底层原理原理没有string sEMMA;只有char *sEMMA;这表示存储emma首字母e的地址使用malloc分配空间进行字符的复制使用free释放内存结果不受影响将输入传给函数时实际传递的是值的副本副本被称为a,b;所以swap函数交换了a,b;没有交换x,y分配内存自上而下堆栈调用函数自下而上缓冲区溢出heap overflow堆溢出malloc分配空间太多stack overflow堆栈溢出调用函数太多②指针替换get_string选择传递地址而不是变量给scanf的原因与swap函数是一样的如果只传递值那么只会得到一个副本NULL表示没有指针也就是说实际上没有给要输入的值分配任何内存需要给自己分配一个数组并传递到函数string char *字符串string字符数组所以char * 字符数组即指针数组2文件的读写文件指针.csv格式属于用逗号分隔值的简单电子表格格式3检查文件名是否通过六第六集 数据结构可以利用sizeof分配int、float等的内存每次分配内存之后都必须要检查是否已经正确分配内存1.数据结构有那些1数组arrays数组必须预先声明大小如果没有事先知道并分配好内存或者想要临时增加内存用数组会很麻烦重新分配内存复制或使用realloc重新分配内存移动一个数组需要On的时间PSmalloc位于stdlib.h文件中2链表linked lists链表只是一个包含多个内存块的数据结构以某种方式联系在一起使用2个内存空间一个存储值一个存储第二个值的地址NULL是一个指针只是底层全是0sruct node * 指向节点node结构的指针数字的下面是一个指针这个指针将指向第二个指针地址而不是就是第二个数组的地址指针本身也就是说数字的下面是存储的是节点的地址typedef更改结构体的名称并没有创造新的结构如typedef char * string将char * 重命名为stringstruct创建新的结构体断开链接及插入节点后再次链接需要拥有一个临时指针tmp插入1节点必须先链接1和2而不是list和1因为这样才不会丢失2-4-5这三个节点链表无法直观地看到存储的值所以链表失去了随机访问的权限在链表中插入和搜索时间复杂度都是On3二叉搜索树binary search trees通过树搜索的时间复杂度为4哈希表hash tables哈希值的时间复杂度需要与空间复杂度衡量考虑如果使用大量空间最终可以实现O1但是这样明显得不偿失最合适的应该是On5检索tries遵循花费一种资源节省另外一种资源的模式它是一棵树每个节点本质上都是一个数组完全牺牲空间去存储值tries搜索和插入的时间是恒定的时间的复杂度是Ok,k是一个常数即实际可以使用O1表示2.数据结构能解决哪些问题1队列queues先进先出的FIFO数据结构enqueue入队dequeue出队后进先出的LIFO数据结构堆栈推push将元素推入堆栈弹出pop删除顶部元素2字典dictionaries七第七集 python1.python语法是怎样的用python实现输入、设置变量、if……elif……else……条件、while循环、for循环与range()函数⑥for循环python的说明文档http://docs.python.orghttp://docs.python.org/2.python有什么用python可以用简洁的代码处理复杂的事情但相对于C语言来说它所需的时间要更多and 替代、or替代|| 使用数组定义函数及参数输入命名参数设置input代替get_stringinput只能代替get_string也就是说它返回的永远是一个字符串如果想要整数等其他类型需要强制转换数据类型3.python有何独特之处正则表达式regular expressions. 任何字符.* 0个或多个字符. 1个或多个字符 可选内容^ 开始输入$ 结束输入re.search、|表示或、表示可选择内容、lower()或IGNORECASE强制转换大小写;^$固定头尾二、SQL(Structured Query Language 结构化查询语言一SQL基础1..csv文件注意这里没有调用f函数只是传递它的名称②lambda函数的定义2.sqlite3库①通过SQL语句建立数据库②通过SQL语句排序③组合排序④限制数量的组合排序⑤改表头⑥混合应用二关系型数据库relational databases1.C\R\U\DCREATE创建READ读取UPDATE更新DELETE删除映射关键字insert增加select选择update更新delete删除2.SQL数据类型①BLOB二进制②INTEGER整数smallintinteger32bitsbigint64bits③NUMERIC数字类booleandatedatetimenumeric(scale,precision)timetimestamp④REAL:类似于浮点数real实数32bitsdouble precision双精度64bits⑤TEXT文本char(n)varchar(n)text3.SQL特有语法实践CREAT TABLE table(column type, ...); //创建表格INSERT INTO table (colum, …) VALUES(value, …); //添加数据到表格SELECT colums FROM table WHERE condition; //选择满足条件的数据UPDATE table SET columnvalue WHERE condition; //满足条件时更新表格列名DELETE FROM table WHERE condition; //满足条件时删除数据DROP TABLE favorites; //删除整个表格函数AVG //平均数COUNT //统计计数DISTINCT //去重MAX //最大MIN /最小……①DISTINCT过滤重复项WHERE 当后面加条件LIKE 像模糊取值后面有%%属于通配符相当于搜索一切带有%%中间词的词LIMIT取值范围限定后面跟数字如取10个就是LIMIT 10GROUP BY 组织ORDER BY排序JOINORDER BY排序②WHERE当③LIKE模糊取值%%属于通配符相当于搜索一切带有a1的词④LIKE模糊取值与非模糊取值的区别⑤更新数据⑥DELETE删除数据⑦DROP TABLE 删除整个表格三数据处理1.数据下载IMDB说明链接https://developer.imdb.com/non-commercial-datasets/①②③④IMDB数据下载链接https://datasets.imdbws.com/⑤⑥⑦在CS50中打开2.数据提取1用python提取数据①②(虽然不知道哪里出错了没有实际打开但代码确实如此③搜索The Crown因为这里打开错误但代码无误④查看有多少条数据⑤使用命令行下载文件⑥解压以.gz结尾的文件⑦筛选有用的数据强制转换类型判断年份这里不知道为什么死活不行⑧程序优化⑨在csv文档中再次搜索想要的信息2用SQL提取数据①格式转换A.CS50内置SQL库可以链接到.db结尾的文件B.创建空数据库方式1_终端创建B.创建空数据库方式1_终端创建C.创建空数据库方式2_python代码创建D.将数据插入数据库或者说转为.db类型存储②提取数据A.进入sqlite3B.使用.schema查看数据库中的数据类型C.读取10条数据D.统计数据数量E.\N要用引号引起来否则会报错F.通过唯一标识符建多个关联的表G.查看表标题H.多表关联查询I.不知道为什么做不出教程老师那种凡是逗号分隔就用多行显示的效果个人认为应该是python代码的问题尤其是最后将genres加入建立的第二个表时J.想要的效果应该是下面那个多的K.因为“凡是逗号分隔就用多行显示的效果”这个效果做不出来导致这里的多表联合查询页失败了只能找出5个而非21个L.JOIN链接两表L.JOIN链接两表2M.嵌套查询N.显式连接PRIMARY KRY主键FOREIGN KEY外键UNIQUE唯一键INDEX索引O.创建索引O.创建索引O.创建索引标题BEGIN TRANSACTIONCOMMITROLLBACK用户不配合输入三、CS50听课感想1.这简直是天书整堂课听得我那叫一个昏昏欲睡尤其是道最后讲用户不配合输入那里开始完全更不上了2.没什么基础直接听英文版的果然还是太过勉强了一些不过无妨这个课主要用来训练一下思维即可最开始的几门课对人的思维影响往往是最深刻的所以哪怕花费了大量的时间去学习也未可厚非反正现在我唯一拥有的资源就是时间3.累计疑惑①Unsigned和fread()函数用法②链表的指针实现list-next m;list-next-next x;③循环打印列表的自增tmptmp-next④链表内存的释放while(list !NULL) { node *tmp list-next; free(list); list tmp; }⑤传递函数名称与调用函数有什么不同⑥怎么强制转换list类型为int⑦SQL如何实现凡是逗号分隔就用多行显示的效果⑧用户不配合输入的原因和解决方法是什么