计算机编程 初学笔记09

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.内存地址指针有什么用1string 的底层原理与指针关联①string 的底层原理原理②指针替换get_string2文件的读写文件指针3检查文件名是否通过二、数据结构一回顾指针二数据结构有那些1.数组arrays1数组的缺陷2数组结构缺陷的解决方式2.链表linked lists1链表的原理2链表的缺陷3链表的编程实现3.二叉搜索树binary search trees4.哈希表hash tables5.检索tries三数据结构能解决哪些问题1.队列queues2.字典dictionaries三、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,y1.分配内存自上而下堆栈调用函数自下而上缓冲区溢出heap overflow堆溢出malloc分配空间太多stack overflow堆栈溢出调用函数太多②指针替换get_string选择传递地址而不是变量给scanf的原因与swap函数是一样的如果只传递值那么只会得到一个副本NULL表示没有指针也就是说实际上没有给要输入的值分配任何内存需要给自己分配一个数组并传递到函数string char *字符串string字符数组所以char * 字符数组即指针数组2文件的读写文件指针.csv格式属于用逗号分隔值的简单电子表格格式3检查文件名是否通过二、数据结构一回顾指针①利用sizeof分配int、float等的内存二数据结构有那些1.数组arrays1数组的缺陷数组必须预先声明大小如果没有事先知道并分配好内存或者想要临时增加内存用数组会很麻烦①移动一个数组需要On的时间②硬编码数组的代码实现②动态分配内存的指针代码实现注意malloc位于stdlib.h文件中每次分配内存之后都必须要检查是否已经正确分配内存2数组结构缺陷的解决方式③实现在数组后面添加数字④使用realloc重新分配内存2.链表linked lists1链表的原理struct设置结构.进入数据结构访问结构的具体属性*解锁指针/去访问地址链表与数组的区别数组是固定的内存块如果想要增加数据需要重新分配内存realloc也只是使其更加简单但实质工作完全相同分配更大内存-负责原有数据-……①使用2个内存空间一个存储值一个存储第二个值的地址NULL是一个指针只是底层全是0②链表只是一个包含多个内存块的数据结构以某种方式联系在一起③自定义node数字1的下面是一个指针这个指针将指向2指针地址而不是就是数值2的地址指针本身也就是说数字1的下面是存储的是2地址sruct node * 指向节点node结构的指针typedef更改结构体的名称并没有创造新的结构如typedef char * string将char * 重命名为stringstruct创建新的结构体④链表图示④空链表④为链表分配空间将这个节点的值设置为2④将这个节点的值设置为2同⑥④将这个节点的指针设置为NULL占位④检查分配是否为空⑤实现链接⑤实现链接⑥将4添加到链表⑥将4添加到链表⑥链接2和4⑥只要下一个节点的next不是NULL就链接断开链接及插入节点后再次链接需要拥有一个临时指针tmp⑦分配1这个新节点以等待被插入⑦插入1节点必须先链接1和2而不是list和1因为这样才不会丢失2-4-5这三个节点⑦链接1节点目前也叫n先将原来list所指向的内容传递给n节点的next再将n节点的地址存入list这个头指针2链表的缺陷①链表无法直观地看到存储的值所以链表失去了随机访问的权限在链表中插入和搜索时间复杂度都是On3链表的编程实现#include stdio.h #include stdlib.h //定义链表节点node typedef struct node { int number; struct node *next; } node; int main(void) { //初始化空链表list node *list NULL; //初始化节点n,存储1 node *nmalloc(sizeof(node)); if(n!NULL) { n-number 1; n-next NULL; //空链表list指向节点n的地址把n的地址赋值给list的地址 list n; } //初始化节点m,存储2; node *mmalloc(sizeof(node)); if(m!NULL) { m-number 2; m-next NULL; //上面的节点n指向现在节点m的地址 list-next m;//等价于(*list).nextn;其中*list其实就已经到达了n1节点处 } //初始化节点x,存储3 node *xmalloc(sizeof(node)); if(x!NULL) { x-number 3; x-next NULL; //上面的m指向现在节点x的地址 list-next-next x;//等价于(*(*list).next).nextn; } //打印 //类似于for(int i0;in;i);都是初始化条件自增 //定义一个临时指针tmp,可以指向节点将起初始化为空链表list(); //因为两者都是地址所以无论list指向什么tmp也会指向什么 for(node *tmplist;tmp!NULL;tmptmp-next) { printf(%i\n,tmp-number); } //释放内存 while(list !NULL) { node *tmp list-next; free(list); list tmp; } }3.二叉搜索树binary search trees①树的图示二叉搜索树在树的任何节点左边小于它右边大于它递归②定义两个指针③递归搜索树中的50的思路通过树搜索的时间复杂度为4.哈希表hash tables①哈希表图示竖向为数组横向为列表哈希值的时间复杂度需要与空间复杂度衡量考虑如果使用大量空间最终可以实现O1但是这样明显得不偿失最合适的应该是On5.检索tries遵循花费一种资源节省另外一种资源的模式①trie是一棵树每个节点本质上都是一个数组②完全牺牲空间去存储值存储3个姓名示例tries搜索和插入的时间是恒定的时间的复杂度是Ok,k是一个常数即实际可以使用O1表示三数据结构能解决哪些问题1.队列queues1先进先出的FIFO数据结构enqueue入队dequeue出队2后进先出的LIFO数据结构堆栈推push将元素推入堆栈弹出pop删除顶部元素2.字典dictionaries三、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; }