博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
CS50 2013-Week5 学习笔记
阅读量:4099 次
发布时间:2019-05-25

本文共 1980 字,大约阅读时间需要 6 分钟。

本以为这节课很难。但是课中讲的Array、Linked List、Stack、Queue、Binary search tree、Hash table,刚好以前都看到过。


Array

前面课程中提到过。

比如int a[8];语句。 定义一个能存储8个整型数据的数组a,系统会为数组a 分配一片连续的存储空间(例如,1201~1232),数组中元素按下标从小到大排列,每个元素占用相应的4个字节。
另外,数组名a是常量,代表数组占用存储空间的起始地址(这里1201)。

这里写图片描述

随后,可以对数组元素赋值,如a[1] = 2;,将2写到地址1205对应的存储空间里。

这时候输出列表,发现第二个元素为2,其他的没赋值元素好奇怪,暂时没有弄清楚。如下图:

这里写图片描述


Linked List

首先,需要有一个指针指向列表的第一个元素,知道链表从哪儿开始的。

然后,每个元素除了数据域存储数据,还有指针域指向下一个元素。
然后,不需要连续的存储空间,只要有指针存储下一个元素的地址就行。
链表的最后一个元素指针指向Null,标志这链表的结尾。

这里写图片描述

例如,如果要在上述链表中搜索一个元素02:

首先通过头指针查看头指针指向的元素值是否等于02,
发现不等于,查看指针指向的下一个元素值是否等于02
最后发现有个元素等于02,返回True。
如果直到指针指向Null,都没有发现搜索元素,返回False。


链表中增加元素(到链表开头),如下图:

复制头指针的地址,使要增加的元素同样指向第一个元素。

使头指针指向要增加的这个元素。

这里写图片描述

这里写图片描述

其余的链表操作还有增加元素到链表中间、删除元素等。


Stack

这个遇到好多次了,能说出一些:

last in,first out。
每次增加元素会放在栈顶,每次也只能取出栈顶的元素。

视频中有两个例子,

显示餐厅的托盘,一大堆托盘,放托盘时,只能放在最上面。拿托盘时,也只能拿最上面的。
还有叠衣服到箱子里,每次放衣服放在最上面,拿衣服也只能拿最上面的,一直只能穿一套衣服。


Queue

队列,first in, first out。

像正常的排队买东西一样,队列最前面的先买。最前面的买到了,第二个买。

然后,重要的一个概念:

假如队列只有8个位置。(Capacity)

现在8个位置都有人排队。(Size)
第一个人买完后,又来了一个人排队。

一般的做法是所有的人前移一个位置,留出最后一个位置给新来的人。

更巧妙的做法,可以新来的人直接站在第一个位置。只要第二个人的位置变成队列的开头就行了。

大致如下图:

这里写图片描述


Tree

树结构,看下边的 Binary Search Tree,每次比较搜索值与当前节点值,能确定下次往左搜索还是往右搜索。不用遍历所有数据了。

首先有一个指针指向tree结构的根节点,知道二叉树从哪儿开始的。

根节点有两个指针,左边的指针指向的子节点的值小于根节点的值,右边子节点的值大于根节点的值。
同样,下面的子节点一样会有一个或两个字节点。

例如,搜索66:

首先开始时指针指向的值为55, 66大于55,看55右边的指针。
55右边的指针指向77, 66小于77,看77左边的指针。
77左边的指针指向66,等于66,返回True,完成了搜索。

这里写图片描述

使用二叉树搜索,最重要的是二叉树的结构要平衡。

比如,下面的二叉树结构,符合搜索二叉树的定义。只是这样的二叉树和链表差不多,看不出二叉树搜索的优势了。

这里写图片描述


然后视频中最后了一些编码和hash tables。

标准ASCII码用7位二进制数表示128个可能的字符。

例如 65 代表A 等等。

所有的字母都占用一样的内存或许不太理想。

当然,可以自己按照字母出现的频率来编码。字母出现频率高,相应的编码也简单,方便使用和存储(Morse Code)。

比如 一段文字 AAAEEEBBCCCCDDDDDDDD。

A出现的频率为15%,B 10%,C 20%,D 40%,E 15%。

按照最小的两个数互相结合成一个新的数的原理。如下:

首先,五个数中最小的两个数是 10%和15%,结合后变成25%。
现在,四个数中最小的两个数是 15%和20%,结合后变成35%。
然后,三个数中最小的两个数是 25%和35%,结合后变成60%。
60%和40%结合成了1。

到了编码环节,按照节点左边编码为0,右边编码为1。

A的编码为001,B的编码为000,C的编码为011,D的编码为1,E的编码为010。
(暂时没看到多大的优势,3个二进制数能表示8个字符,这里只有E编码为一个二进制数,其他4个字符还是3个二进制数表示。如果需要编码的字符多了,会很明显的优势,出现频率高的字符编码也少,就不用占用那么多内存了。)

这里写图片描述


关于视频后面的 hash 表,暂时没去找更详细的介绍。

最后放上数据结构的定义:

你可能感兴趣的文章
OpenFeign学习(五):OpenFeign请求结果处理及重试控制
查看>>
OpenFeign学习(六):OpenFign进行表单提交参数或传输文件
查看>>
OpenFeign学习(七):Spring Cloud OpenFeign的使用
查看>>
Ribbon 学习(二):Spring Cloud Ribbon 加载配置原理
查看>>
Ribbon 学习(三):RestTemplate 请求负载流程解析
查看>>
深入理解HashMap
查看>>
XML生成(一):DOM生成XML
查看>>
XML生成(三):JDOM生成
查看>>
Ubuntu Could not open lock file /var/lib/dpkg/lock - open (13:Permission denied)
查看>>
collect2: ld returned 1 exit status
查看>>
C#入门
查看>>
查找最大值最小值
查看>>
杨辉三角
查看>>
冒泡排序法
查看>>
C#中ColorDialog需点两次确定才会退出的问题
查看>>
16、Memento 备忘录模式
查看>>
Java基础篇(一)
查看>>
数据库
查看>>
mysql update与group by
查看>>
nginx反代 499 502 bad gateway 和timeout
查看>>