国宝马兰所有权利。 欢迎回到CS50。 这是第8周开始。 记得这个问题集5结束 带着一点点的挑战。 因此,假如你恢复你所有的 教学研究员和加利福尼亚州的照片 在card.raw文件,你有资格 现在发现所有的那些人, 一个幸运的获胜者将步行回家与 这些东西,飞跃运动 你可以使用最后的设备 项目,例如。 ,每一年,这会导致 有点cre​​epiness。 所以我想我会做什么是购 与您指出 来回走了过 后期工作人员名单。 举例来说,就在昨天晚上,报价 引文结束,从一名工作人员 成员,“我只是一个学生敲 我的门,跟我拍一张照片。 潜行者,我告诉你。“开始了 相当的描述,然后我们感动 就到了,一个小时左右后,“我有一个 后部分学生在等着我 他有我们的名字和照片 几张纸。“所有权利。 所以组织,但不 这一切令人毛骨悚然。 那么,“我是出城的这个周末, 当我回来的时候,有一个在 我的 卧室里。“[笑] 国宝的马兰:下报价从工作人员 成员,“一个学生来我家 萨默维尔今早凌晨4点“。 工作人员,“我得到了我的酒店在圣 旧金山和一名学生被等待 我在大堂有三个数码单反相机“。 相机类型。 “我什至不对员工这学期, 但学生闯进我家 早晨和记录了整个事情 与谷歌的玻璃。“最后, “至少12人翘首 等待着我,当我离开了我 豪华轿车,然后我 醒了。“所有权利。 因此,在拍摄的照片中,你可能 回想一下,这家伙在这里,你是谁 可能知道米洛香蕉,谁住 劳伦·卡瓦略,我们的头 教学研究员。 米洛,米洛,来这里的孩子。 米洛。 米洛。 你要知道,他的穿着谷歌的玻璃,所以 我们会告诉你这一切之后。 因此,这是米洛,如果你想 后来与他拍一张照片。 如果你想看看 在那里的观众。 确定。 这是很好的素材。 嗯,香蕉米洛。 哦,不做到这一点。 [笑] 确定。 所以一个单词,然后是什么样的未来, 因为当我们开始转型, 具体而言,这个星期在从C 命令行环境PHP和 JavaScript和SQL,HTML和CSS 一个基于网络的环境中,我们将 你的所有装备 更多知识 潜在的最终项目。 为此,当然是有 传统举行研讨会 上切线主题的 当然。 非常相关的编程和 应用开发等等,但 不一定探索 当然自己的教学大纲。 所以,如果你可能有兴趣在一个 今年的研讨会, 注册cs50.net/seminar。 有旧研讨会 在cs50.net/seminars。 和今年迄今名册 惊人的Web应用程序使用Ruby on 导轨,这是一种替代 语言PHP。 计算语言学。 到iOS,这是 平台,用于iPhone和 iPad的发展。 JavaScript的Web应用程序的,我们将讨论 ,但在本次研讨会中,你会去 的更多细节。 蹦蹦运动,所以我们实际上也有 我们的朋友从大跃进运动, 公司本身,加入我们的行列。 明天,其实,为客户提供 一个动手的研讨会,如果 你的兴趣。 meteor.js,另一种技术 而不是在浏览器中使用JavaScript, 但在服务器上。 Node.js的,这是非常 在该静脉。 圆滑的Andr​​oid设计。 Android的一个非常受欢迎的替代 的iOS和Windows Phone 和其他移动平台。 和Web安全主动防御。 因此,事实上,如果你想 搞这个,让我 注意到这一点。 我们非常高兴地说, 我们的朋友在大跃进 运动,这是一个启动 - 这个装置实际上只是来到 出几个月前 - 慷慨捐赠30个此类设备 类尽可能多的学生,如果 你想借硬件 朝学期结束,并用它来 实际的最终项目。 他们支持的语言数量。 他们没有,他们没有PHP的,所以 实现一个或多个这些研讨会 可能证明的兴趣。 和所有的人将被拍摄下来的 倘若你是不是能够 亲自出席。 通过时间表公布 电子邮件作为我们巩固客房。 最后,如​​果你去 projects.cs.50.net,这是一个网站 我们维持每年我们邀请 人们从社会,教师, 部门,人员,并且都 在CS50至外侧的 提出项目设想。 学生群体感兴趣的东西。 部门关心的事情。 因此,不要打开,如果你在挣扎 与你的不确定性 自己想解决的。 所以我们推出了一个可以说是最后一次 比我们更复杂的数据结构 在过去的几周里看到。 我们一直在使用数组漂亮 高兴地作为一个有用的,如果 简单化的数据结构。 然后,我们介绍了这些, 当然链表。 到底是什么东西的动机之一 引入这个数据结构? 是吗? 那是什么? 观众:动态大小。 大卫马兰:动态尺寸。 因此,而数组中,你必须 知道它的大小时提前 你分配。 链表,你不这样做 要知道。 你可以只是malloc的,或更普遍的, 增拨 节点,可以这么说,任何时候,你 要插入更多的数据。 节点没有预定的意义。 这只是一个普通术语,描述 我们某种容器 使用我们的数据结构存储 一些感兴趣的项目,在这个 情况是整数。 但是总是有一个权衡。 因此,我们得到的数据的大小动态 结构,但我们付出什么样的价格? 链表的缺点是什么? 是吗? 观众:需要更多的内存。 国宝马兰:它需要更多的 内存,究竟怎么了? 观众:[听不清]。 DAVID马兰:没错。 所以,现在我们已经指针 额外的内存,我们以前 并不需要,因为优势 一个数组,当然是 一切连片, 背靠背, 为您提供了随机访问。 因为只需使用方括号 符号,或更技术上的指针 算术,很简单,此外, 你可以访问任何 在固定时间内的元素。 而事实上,这是一种暗示 另一个价格,我们正在与支付 链表。 会发生什么情况的运行时间 像搜索,如果我想 找到一些价值和内部 链表? 成为我的运行时间是什么? 大O的n。 如果它的排序? 如果数据结构的排序? 我可以做的更好的比大 n为O的搜索? 没有,因为在最坏的情况下,它可能会 很好地进行排序,但数量 你要找的可能是很大的。 它可能是第100号, 可能发生的事情是所有 在结束的方式。 因为你只能访问一个链接 在本实施的喜爱 其第一个节点的方式,你 依然是那样的运气了。 你必须遍历整个事情 从第一次到最后,为了找到 像100那么大价值。 或确定,如果它是 甚至没有。 因此,我们不能做什么算法在数据 结构看起来像这样吗? 我们不能这样做,因为二进制搜索 二进制搜索需要,我们有 随机访问。 我们只能从位置到飞跃 的位置,而无需遵循 这些面包屑的形式 所有这些指针。 现在,我们怎么实现呢? 那么,如果我们到屏幕上,在这里,如果 我们可以很快地重新实现此数据 结构 - 我的笔迹​​不是所有的 在这里,伟大的,但我们会尽力。 所以typedef结构,什么我 要调用这个东西在这里? 节点。 因此,我将让我们开始。 而现在,需要将里面的 该单独的数据结构 链表? 多少个字段? 所以两个。 一个是很容易的。 所以INT N。 我们可以称之为ñ我们想要的东西, 但它应该是一个int,如果我们 实现链表为整数。 现在什么第二 现场有吗? 结构节点。 所以,如果我做节点,然后我 可以调用这个也是我想做的事情, 但仅仅是明确的,我会打电话 未来,因为我们一直在做的事情。 然后我会关闭我的花括号。 而现在,作为最后一次, 我把节点。 但是,如果我声明,这是作为一个 节点,我为什么懒得如此 详细在这里宣布结构 节点下,而不是 只是节点*? 是吗? 观众:[听不清]。 DAVID马兰:没错。 没错。 由于C真的需要你从字面上 只看到的定义节点 一路下来这里,你可以不 是指它在这里。 因此,我们有这种先发制人 声明在这里,这是无可否认 更详细。 节点结构,这意味着 我们现在可以访问它 内部的数据结构。 顺便说一句,因为这是 现在成为一个更主观一点, 明星可以在技术上走在这里, 它可以去这里,它可以 甚至在中间。 我们已经通过,在风格指南 当然,把公约 星旁边的数据 型,在这种情况下, 将结构节点。 但实现大量课本 在线参考,事实上,你可能会 看到它的另一侧。 但是,仅仅实现这两个实际上会 工作,你应该仅仅是 一致的。 好的。 所以这是我们的宣言 结构节点。 但后来我们开始做更多 复杂的事情。 例如,我们决定引进 如哈希表的东西。 因此,这里是一个哈希表大小为n, 索引从0到n的左上方 减去1的左下角。 这可能是一个散列 表中的任何东西。 但我们讨论了什么事情 使用一个哈希表怎么样? 存储是什么? 名称。 我们可以做名字,如 我们做了最后一次。 真的,你可以存储任何东西。 我们将再次看到这 PHP和JavaScript中。 哈希表是一个很好的瑞士排序 瑞士军刀,允许你存储 几乎任何你想要的内侧 它的关联值的键。 键与值。 现在,在这个简单的情况下,我们的 只是数字键。 我们正在实施一个哈希 表中为一个数组。 等键是0, 1,2,等等。 因此,我们作为人类,最后决定 本周,你知道吗,如果我们 去商店名称,让我们只是 随意,但相当合理的, 假设Alice,一个名字, 只是索引为0。 鲍勃,一个B的名字,将被索引 为1,等等。 因此,我们不得不投入之间的映射, 是字符串,和散列 的位置,这是数字的。 因此,该过程通常被称为 哈希函数,你可以真正 在代码中实现它。 如果我想实现的哈希函数 这不正是我们 刚刚描述的从去年的时候,我可能会 声明一个函数,它作为 例如输入 - ,让我们做到这一点在此 屏幕在这里。 如果我想实现一个哈希 的功能,我可能会说, 这样的事情。 这将返回一个int。 这将被称为哈希,它是 要接受的参数是一个 字符串,或者我们可以更恰当, 说的char *,我们会打电话给它s。 然后这一切功​​能, 最终,返回一个int。 现在,它是如何可能 不那么清晰。 我要实现这个没有任何 现在形成的错误检查。 我只是一味地说,返回 无论是在s支架0,减, 比方说,资本用分号。 完全打破。 它并不完美,因为 一,什么如果s是空? 不好的事情将要发生。 二,如果在此的第一个字母 名字是不是一个大写字母? 这不会变成 出。 这可能是一个小写字母 不是一个字母。 所以完全改进的余地, 但是这是基本的想法。 我们上周口头 只是一个过程的映射爱丽丝 0和Bob 1可以表示 当然更公式为C 在这里发挥作用。 再次调用哈希,将一个字符串作为 输入,然后莫名其妙地做一些事情 与该输入信号以产生一个输出。 不像我们的黑箱描述 长期以来,我们已经完成了。 我不知道如何,这可能是 引擎盖下工作。 对于问题集6,面临的挑战之一 是你来决定什么 您的哈希函数是什么? 这是怎么回事,里面那个黑 框,据推测,它会是一个 比这更有趣一点, 肯定更容易出错 这个特殊的检查比 实现。 但可能会出现问题,对不对? 如果我们有一个数据结构,例如 一,什么是一个问题 你可以运行到随着时间的推移,当您插入 越来越多的名字进入 哈希表? 你得到的碰撞,对不对? 如果你有爱丽丝和亚伦, 两个人的名字发生 开始与A? 这引出了一个问题,在那里你 把第二个这样的名字? 那么,你可能天真地把它 鲍勃属于的地方,但随后鲍勃是 拧种,如果您尝试 插入他的名字旁边, 有没有他的空间。 所以,你不妨把鲍勃·查理在哪里, 你能想象这个非常迅速 下放成有点乱。 线性的东西到底是哪里你 只需要搜索整个事情 寻找Alice或Bob 或亚伦查理。 因此,而不是我们提出的,而不是只 线性开放空间探测的 横卧在那里,我们的名字 提出一个票友的方法。 哈希表仍与实现 的索引数组,但数据不同的 现在,这些指数分别为指针。 指点一下吗? 链表的指针。 因为召回链表是 真的只是一个指针,指向一个节点, 节点具有一个下一个域,该节点 有一个下一个域,等等。 所以,你现在觉得这个数组 作为一个哈希表的左手侧 导致一个链表。 如果你得到一个优势是 Alice和亚伦之间的碰撞, 你是做什么的 第二个这样的人吗? 你只重视他或她的 端,甚至开始 该链表。 而实际上,让我们只是面条通过 第二。 哪里最有意义? 如果我插入爱丽丝和她结束 第一的位置,然后我尝试 插入亚伦的名字,而且也 显然是一个碰撞,我应该把 他开始时 链表? 这是在那个第一的位置, 或在结束了吗? 观众:[听不清]。 DAVID马兰:OK。 我听说开始。 为什么在开始? 观众:[听不清]。 DAVID马兰:OK。 它是按字母顺序排列的,所以这是很好的。 这是一个很好的属性。 它会来救我的潜在的一段时间。 它不会让我做二进制搜索,但我 可能至少能够打出来 一个循环,如果我知道,好了,我的方式 过去亚伦将在此 链表排序。 我没有浪费我的时间寻找 所有的方式结束。 所以这是合理的。 你为什么要插入 在碰撞的名字 列表开始? 那是什么? 观众:[听不清]。 国宝马兰:这可能需要很长一段时间 得到的列表末尾。 而事实上,长。 越多的名字你插入 开始,不再 链要得到的。 的时间越长,挂钩 列表会得到什么。 所以,你真的只是 浪费你的时间。 也许你更好的维护 恒定的插入时间,大O 1, 始终把碰撞名 该链表的开头, 而不是尽可能多担心 关于排序。 什么是最好的答案吗? 目前还不清楚。 一种取决于什么 分布模式是什么 你的名字插入。 这不一定 一个明显的答案。 但在这里,再次 设计的机会。 因此,我们再看着这件事情, 真正的另一大机遇 为对集6。 与实现,如果你还没有的话, 的Zamyla潜入这两个哈希 表和尝试,更详细。 和视频演练的是 嵌入在对一套规范。 这是特里 - T-R-I-E。什么是有趣的 这是运行时间 寻找一个名字,像麦克斯韦 最后一次,是大O是什么? 那是什么? 观众:数字字母。 国宝马兰:字母数。 我听说了两件事情。 字母和恒定的时间数。 所以,让我们与第一。 的字母数。 那么,这样的数据结构,召回, 像一棵树,一个家庭树,每个 的节点组成的数组。 这些数组指针 其他这样的节点,或其他这样的 树中的数组。 因此,如果我们想要再确定 麦克斯韦是否是在这里,我可能去 第一阵列,​​在最顶部的 树中,所谓的根,顶部 特里,然后按照米指针, 然后是一个指针,那么x, W,E,L,L。 然后当我看到一些特殊的符号, 在这里表示为三角形。 在代码中,你会看到我们建议您 为bool实施,只是说是 或没有,一个字在这里停止。 那么,一旦我们去参加M-à-X-W-E-L-L, 感觉就像七,也许 八,如果我们走过去吧,八 步骤找麦克斯韦。 还是让我们叫它K.但记得最后 的时候,我认为,如果有 切实的最大长度上 字,像40一些奇怪的字符, 最大长度意味着 一个恒定值。 所以真的,是的,这是技术上的大O 8或7,或真大O K.,但 如果有一个有限的上限是什么 K表,这是一个常数。 所以它的大O 1 在一天结束时。 不是在现实世界中。 当你真正开始看 时钟程序的运行。 这绝对是有点 比真正的恒定速度较慢 时间与步骤。 这将是七八步, 但仍然好得多 比大O n表示这样的算法 的大小取决于什么 的数据结构。 请注意,这里的上攻,我们可以插入 百万名到这个 数据结构,但很多步 它是要带我们去找到 麦克斯韦在这种情况下? 没有。 他不受影响。 到今天为止,我不认为我们已经看到了 的一个例子的数据结构或 完全的算法 不受外部 这样的行为。 但是,这不能是惊人的。 这不能是唯一的解决方案 对于p-集 而事实并非如此。 这不一定是数据 结构应该吸引到, 因为像哈希表,权衡。 你付出的代价是什么? 内存。 我的意思是,这是一个穷凶极恶 的内存量。 你不能完全看到它,因为这里 这幅画的作者 显然截断所有阵列 和我们没有看到很多A的 B的和C和Q和Y 和Z的这些数组中。 但是,他们在那里。 每个节点是一个整体的阵列 约26或更多的字节,每个字节 这代表一个字母。 在我们的案例中,这样我们就可以支持27 单引号的问题集。 因此,这个数据结构是真的, 非常密集和广泛。 这本身最终可能会放缓 下来的东西,或者至少是成本你 更多的空间。 但同样,我们可以得出 这里的比较。 回忆了一段时间后,我们取得了很大成就 更令人兴奋的运行时间排序 当我们使用归并排序,但价格 我们实现N个记录n为合并支付 排序要求,我们花 什么资源? 更多的空间。 我们需要一个辅助阵列 复制人,就像 我们在这里做的,在舞台上。 如此反复,没有明显的赢家, 只是主观设计 作出的决定。 好的。 因此,这个怎么样? 任何人都承认,D-霍尔? 确定。 所以,我们三个做。 奥美大厦。 因此,这是奥美的餐饮。 我敢打赌,所有食堂 这样的托盘堆。 这实际上是代表 的东西,我们已经 显然已经看到。 我们把它称为名副其实的堆栈。 栈,您 计算机的内存,数据去 当功能被调用。 例如,什么样的东西去 相对于在堆栈上 我们已经讨论过的内存布局 在过去的几周? 那是什么? 观众:函数调用。 DAVID马兰:对不起。 观众:函数调用。 DAVID马兰:通话功能,但 具体而言,每个里面有什么 这些帧? 什么样的东西呢? 嗯。 因此,局部变量。 任何时候,我们需要一些本地存储, 像一个说法,或INT I,或int 温度,或任何地方 变量,我们已经 将在堆栈上。 我们称之为堆栈,因为 该分层想法。 的比赛只是一种现实, 其概念。 但事实证明,一摞还可以 被看作是一个数据结构,一个 替代一个数组,另一种 链表。 概念上的东西更有趣 仍然可以 那些采用 的东西,但它是一个不同类型的 数据结构的支持,真的, 只有两个操作。 但是,您可以添加票友 功能不止这些。 但这些都是基础知识 - push和pop。 用栈的想法是,如果我 这里有,带或不带安南伯格 知道,一个托盘从隔壁 数字9就可以了。 所以只是一个int。 我要推到数据 结构,目前是空的。 考虑这个堆栈的底部。 我会推到9号 堆叠,而现在它就在那里。 但有趣的关于堆栈 是,如果我现在要推 其他一些值,比如17,我推 入堆栈,我要做的事情 直观的东西,我只是 说得不对,我们人类 会倾向于把它之上。 但是,什么是有趣 ,我怎么在9? 你知道,我不是没有做一些努力。 那么,什么是有趣的 堆栈,设计, 这是一个后进先出的数据结构。 傻的方式描述 后进先出。 所以最后一个数字 在这个时候的时间是17。 所以,如果我想流行的东西 栈,它只能是17。 所以这是一个强制性的顺序 这里的操作,其中的最后一个项目 在成为第一个出。 因此,首字母缩写词,后进先出法。 那么,为什么会这样有用吗? 是的语境中,你 我想这样的一个数据结构? 那么,它肯定是有用的 内的一台计算机。 所以操作系统显然使用此 一种数据结构栈。 我们还会看到同样的想法 当它涉及到网页。 因此,本周和下周超越, 而当你开始实现Web 称为HTML页面的语言,你可以 实际使用的数据结构,如 这是为了确定的页面 是正确的格式。 因为我们会看到所有的网页遵循 一种层次,压痕 在一天结束时,将是 引擎盖下的树结构。 所以,更多的只是一点点。 但现在,让我们提出一个 此刻,我们怎么可能去 相当于一个堆栈是什么? 最后,我提议,我们实施 像这样的代码堆栈。 因此,堆栈里面它都将有 两件事情,一个数组,称为托盘 只是要符合演示。 和该阵列中的每个项目 将是一个int类型的。 和能力大概是什么? 因为我没有写 这里完整定义。 这可能是最大的 数组的大小。 而且它可能急剧宣布 上面的文件顶部的定义,一些 所隐含类型的常量 单纯的资本。 所以某处容量定义 作为可能的最大尺寸。 同时,内部的数据结构 被称为一个堆栈将有 只是一个整数 只是作为大小。 所以,如果我现在代表这 形象,让我们假设,这 全黑方块代表我的筹码。 在它的内部有两个变量。 所以我要画 第一个作为大小。 第二个我要去 以画为一个数组。 但只是为了让事情变得有序, 通常我会画一个像数组 这一点,但它是一种很好的 如果我们匹配的现实,或 相匹配的心智模式。 所以,让我来代替数组绘制 垂直,这仅仅是再次, 艺术家的演绎。 并不真正的问题是什么呢 引擎盖下。 我们会说,在默认情况下, 容量将是三个。 因此,这将是位置0,这 将位置1,本 将位置2。 如果我贿赂应力球, 有人想拿出并运行 登上这里只是一瞬间吗? OK,首先看到你的手。 上来吧。 好的。 所以我相信这是史蒂芬。 上来吧。 好的。 但是,假定现在我们后退到初始 世界的状态,我 刚刚宣布堆栈,它是 将是三能力。 但规模尚未确定。 托盘尚未确定。 因此,一对夫妇的问题先。 让我给你话筒,这样你就可以 更积极参加。 那么,什么是大小里面在这一刻 如果所有我做过的时间 宣布栈 一行代码? 史蒂芬:不多。 国宝MALAN:OK,不多。 大家知不知道里面有什么大小, 我们不知道里面有什么 这个数组在这里? 史蒂芬:随机码,对不对? 只是 - 国宝马兰:是的,我要 调用它的代码,但随机 - 史蒂芬:事情。 国宝马兰:就像是随机的事情 史蒂芬:位。 国宝MALAN:位,对不对? 因此,垃圾值,对不对? 因此,0和1的排列。 以前的惯例遗迹 此内存。 我们真的不知道什么值 ,所以我们通常吸引他们 问号。 所以,首先我们推测 想在这里做 - 让我给这个领域里面 有一个名字 - 托盘。 我们应该怎么想必初始化 如果我们想大小 开始使用该协议栈? 史蒂芬:纸盒子3。 国宝马兰:那么,“确定”。 很明显,容量声明 其他地方为三个。 而这正是我用过 分配数组。 大小要参阅多少 盘目前在栈上。 史蒂芬:零。 DAVID马兰,因此,它应该是零。 因此,继续前进,并与任何手指, 大小绘制一个零。 好的。 所以,现在,这里面有什么 在这里,我们不知道。 这些真的只是垃圾值。 因此,我们可以得出问号,但 让我们保持板面干净 因为它并不重要 那里有什么。 我们不需要初始化数组 什么,因为如果我们知道, 堆栈的大小是零,好,我们 不应被看什么 反正在这个数组 这个时间点。 所以,现在想我推 数9入堆栈。 我们应该如何更新数据结构 这个黑盒子里面? 什么样的价值观需要改变吗? 史蒂芬: - 大小? DAVID马兰:OK。 大小应该变成什么样? 史蒂芬:大小将是一个。 DAVID马兰:OK。 因此,大小应成为一体。 所以你可以在一对夫妇的方式做到这一点。 让我给你,现在你的 手指是一个橡皮擦。 好的。 那么现在你的手指一刷。 好的。 现在有什么改变, 很明显,在数据结构中? 史蒂芬:我们打算从 底部9。 国宝马兰:9。 好,好。 所以还是什么都无所谓的 一个或两个位置,因为他们是 垃圾值,但我们不应该打扰 因为大小是寻找 告诉我们,只有第一个元素 实际上是合法的。 所以现在我推17到列表中。 这个画面会发生什么事? 史蒂芬:那么大小是要去两个。 DAVID马兰:OK。 你橡皮擦 - 哎呀。 你是一个橡皮擦。 史蒂芬:橡皮擦。 DAVID马兰:你刷。 史蒂芬:刷机。 DAVID马兰:OK。 还有什么? 史蒂芬:那么,我们 - 国宝马兰:我们推17。 史蒂芬:我们坚持17之上,所以 - 国宝马兰:OK,好。 史蒂芬 - 砸下来。 国宝马兰所有权利。 它变得容易。 我不会帮你这个时候。 推22。 史蒂芬:完成。 成为一个橡皮擦。 我成为一刷。 然后我把22。 国宝马兰:22。 优秀的。 所以有更多的时间。 我现在要推 入堆栈26。 史蒂芬:哦。 噢,天哪。 你真的让我猝不及防。 国宝马兰:你也没 看到这一切吗? 史蒂芬:我没有看到这一切。 我们可以重新初始容量? DAVID马兰:这是一个很好的问题。 所以我们自己画 这里的一个角落里。 史蒂芬真的是没有利好出尽 因为我们这个数组分配 静态的,可以这么说,里面 的数据结构。 我们已经基本上硬编码 它是大小为3。 因此,我们不能真的重新分配。 我们可以,如果我们回去,我们 重新定义托盘是一个指针, 然后,我们使用malloc手的内存。 因为如果我们得到了内存 通过malloc堆, 然后释放它。 但在此之前,我们可以释放它 重新分配一个更大的内存块, 更新指针,等等。 但现在,这是真的 最好的,我们能做到。 push和pop大概是 有一些错误的信号。 因此,举例来说,我们实施 推可以返回一个布尔值 以前返回真实的,真实的,真实的。 但第四次,这将有 返回false,例如。 好的。 非常出色。 恭喜。 你赚你的压力,今天的球。 [掌声] 史蒂芬:谢谢。 DAVID马兰:谢谢你。 OK,所以这似乎是没有太大的 向前迈进了一步,对不对? 我们描述的数据结构。 这是令人信服的,对不对? 操作系统喜欢它。 显然,网络可以利用这个 和其他应用程序依旧。 但是我们是一个愚蠢的限制 备份排序本周二的限制 我们有固定大小的数组。 所以,确实有一对夫妇 方法我们可以解决这个问题。 我们可以动态分配的数组, 不是由硬编码我 在这里完成的,而是重新申报 这一点,只是很清楚, 这样的事情。 诠释*托盘,而不是决定 尚未容量。 但是,当我宣布堆栈别处 在我的代码,然后,我可以调用malloc, 得到一个块的地址 内存和I可以分配 该地址托盘。 然后,因为它只是一大块 的记忆,我可以继续使用方 括号表示法在通常的方式。 这还是因为同样的原因,有此排序 阵列和功能上等同于 的内存块来 从malloc。 我们可以把一个像其他 使用指针运算或 方括号。 所以这是一种方法。 但是,是怎么回事,我们可能会实现这个 相同的数据结构,有可能? 对吗? 我觉得像我们刚刚解决了这个 一个星期前的问题。 这是解决这个问题的 史蒂芬跑进? 所以,链表,对吧。 问题是,如果我们画 自己分配到一个角落里 提前内存太少,我们 然后以某种方式处理,很好, 为什么不干脆避免这种情况 共发出? 为什么不干脆宣布托盘是一个 指针指向一个节点,因此一个链表, 然后简单地分配新的节点 每次史蒂芬需要,以适应 成的数据结构的数目。 所以画面将不得不改变。 它不会是清洁和 简单,只是三个整数的数组。 现在,它的将是一个指针,指向 结构,该结构是要 有一个int和一个next指针。 这将导致通过该指针 另一个这样的结构 另一个这样的结构。 所以图片实际上会 得到一个有些混乱。 我们早就箭头搭售 一切融合在一起。 但是,这是罚款,正确的,因为 我们已经看到了如何做到这一点。 一旦你得到舒适 实施类似一个链接 列表,你就必须做,如果你 选择实现一个哈希表 单独链接的p组6,你可以 使用它作为一个构建块,或 成分,或在Scratch说话, 程序的东西,你说,你 创建了自己的一块拼图 然后,你可以重复使用。 所以权衡,但潜在的解决方案 我们实际上已经看到过。 所以很多时候,你看到每 一年或两年,当苹果发布 一些新的东西,所有的疯狂的人 外面排队的苹果 商店买他们的边际 在硬件升级。 我这样说,这是确定的,因为 我的那些人之一。 那么什么样的数据结构 可能代表这个现实吗? 好吧,我们姑且称之为一个队列,一条线。 因此,英国会调用它通常是 反正排队,所以这是一个好听的名字。 而且,这两个操作,一个队列 应支持,我们会叫排队 操作和出队操作, 这两种相近的 push和pop的精神。 这只是形式的不同 惯例,我们调用这些。 但排队的东西意味着添加 或插入的数据结构。 出列意味着将其删除。 但是,而堆栈是一个后进先出的数据 结构,队列是先入 先出的数据结构。 如果你是行的第一人, 你将是第一人获得 脱节和购买新设备。 试想一下,这些人会如何心烦 如果苹果,而不是用一个堆栈, 比如,实行采摘 组成你的新玩具。 所以队列有意义,当然, 我们能想到的各种 应用程序,想必,队列, 尤其是当你要公平。 那么,我们怎么可能实现这些 作为一个数据结构? 好吧,我建议,我们可能 需要做的是这种方式。 所以我打算到现在已经有数字。 因此,我们将保持它的简单,而不是 不一定谈托盘。 只是数字,人们得到。 容量是怎么回事,再次修复 人的总数,可以在 这条线,三个或 任何其他值。 不过,我建议,我需要跟踪 的大小不仅 队列中,有多少东西都在里面了。 因此,大小是电流大小,容量 是的最大尺寸。 又一次的,命名 按照惯例。 为什么我需要一个额外的int里面 队列来跟踪谁在 前面的行吗? 为什么我需要做的,在这种情况呢? 好了,这是怎么图片 要改变呢? 我也许可以重用 这张图片。 让我继续前进,抹去了这里。 我们会给这个稍微 不同的名字在这里。 让我们摆脱了17,让我们摆脱 9,让我们摆脱了3。 让的添加另一件事。 我提议由我需要跟踪 列表的前面,这仅仅是 将是一个int。 我们要保持它的简单。 现在没有链表。 我们得承认,我们要 颠簸起来反对这个限制。 但什么我想看看 发生这个时间呢? 因此,假设我继续前进,第一 人来了线, 它是9号。 我们确实有压力球。 我可以说,偷两三人? 一,二,三? 上来吧。 从正面看,由于 我们会让这个快。 现在你们每个人将要 线苹果的风扇男孩。 你会不会接受苹果的硬件 这虽然结束。 好的。 所以,你是9号,你 17号,22号。 这些都是任意数字,如 学生ID或诸如此类的东西。 在短短的时刻,让我们开始 开始添加的东西。 我要跑董事会这次在这里。 因此,在这种情况下,我已经初始化 前面是 - 其实,我真的不关心什么 前面,因为大小为零。 因此,这可能也只是 是一个问号。 这些都是问号。 所以,现在我们将开始看到一些 排队的人在店里。 9号,所以如果你是第一个 凌晨5点,提前去排队, 或前一天晚上。 确定。 所以,现在9号是在这里。 因此,图9是列表的前面。 所以我要继续前进,并更新 这个电流的大小的数据 结构不能为0了, 但为1。 我打算把9日 列表的前面。 让我继续前进,切换屏幕 所以我们可以看到过去我们在这里。 现在,我想要什么 放在前面? 我要跟踪 现在前面的队列 是在位置0。 因为接下来会发生什么呢? 好吧,我想现在排队 17。 因此第一跳有线。 再次,那种门 店会到这里来。 所以,现在我已经增加了17。 即使这些家伙堵 在屏幕上,这是确定的, 因为我们可以看到它在这里。 抱歉。 观众:我们可以移动 - 国宝马兰:没有,这是确定的。 在那里,这是巨大的。 因此,图17是内部的队列。 我需要更新哪些 现在虽然领域呢? OK,绝对大小。 关于前呢? OK,没。 前不应该改变,因为 不同的堆栈,我们 要维护公平。 因此,如果9排在第一,我们希望9 成为第一个出列 进店。 事实上,让我们看到。 之前,我们插入22,让我们 继续前进,出队9。 你叫什么名字呢? 观众:杰克。 国宝马兰:杰克是怎么回事 现在被出列。 所以你走进商店。 并假装商店 在那边。 所以,现在需要什么 - 二叔DIT-dit的! 什么需要现在发生? 设计决定。 所以不是一个坏的本能,但 - 你叫什么名字呢? 观众:大卫。 大卫DAVID马兰。 所以,大卫做了什么? 他试图修复数据排序 从他的位置的结构和移动 进入Jake的前位置。 这很好,如果我们愿意 接受,作为一个 实施细节。 但首先,让我们来更新数据 结构之前,我们做到这一点。 因为我不喜欢的想法 人在这条线转移。 这没什么大不了的,如果大卫它 一步到位,但再次,想回 当我们已经有8名志愿者在 阶段,我们所做的一样插入 排序,我们不得不开始 感动身边的每一个人。 这引起了昂贵的,对不对? 这让我畏缩关于大O 大O N,n的平方了。 这不是感觉像 一个理想的结果。 因此,让我们刚刚更新。 因此,该队列的大小 不再是2。 现在只需1。 但是我现在可以更新的东西 我没有更新之前, 列表的前面。 我可以这样说,是位置1? 所以,现在我们这里的垃圾值, 垃圾价值在这里,大卫在 这个垃圾中间。 但是,该数据结构 仍是完好的。 事实上,我不甚至需要 改变Jake的前数 9,因为谁在乎。 我有足够的信息,现在在 大小,我知道有一个人在 此队列。 我知道那个人 在位置1,而不是0。 我不计数。 所以1。 因此,数据结构还OK。 那么,接下来会发生什么呢? 让我们排队 - 你叫什么名字? 观众:Callen先生。 国宝马兰:Callen先生。 让我们排队Callen先生, 图22是在队列中。 所以,现在这里有什么改变吗? 前不会 改变,很明显。 尺寸要改变再次2。 和22结束在这里,图9是仍然存在, 但它实际上是一个 现在垃圾值。 这只是杰克过去的残余。 所以,现在发生什么,如果 我队列中取出大卫? 最后一个操作,出队的大卫。 我们可能会改变,但我提议,让我们 做尽可能小的工作。 现在我的数据结构去 备份的大小从2到1。 但是,队列前面的 现在变成2。 我不需要改变这些数字 只是还没有,因为他们是 只是垃圾值。 但现在发生了什么? 假设我自己排队,26? 我觉得我属于这里。 所以,我正在排队。 所以我属于这里。 而且,即使你做的不是很 欣赏这视觉在舞台上, 因为我们有足够的空间,我应该 不会站在这里,为什么呢? 观众:你出界。 国宝马兰:右。 我是出界。 我已经超越索引的 此阵列的界限。 我真的应该于一体的 三个可能的位置。 现在,在最自然的去吗? 我建议,我们的杠杆 每周一招。 mod运算符,百分比。 因为我在技术上站在 位置3,但我做的3模能力, SO 3,百分号,3 - 容量3。 那是什么? 什么是余 3除以3? 0。 所以,把我杰克是, 这实际上是不错的。 所以,现在的实施 这个东西要 是有点头疼。 这真的只是一条线 头痛,代码。 但至少现在有垃圾 这里的价值,但有两个 这里正当整数。 我要求,现在我们已经做了 这正是我们需要做的,只要 我们改变了杰克的 的值是26。 我们现在有足够的信息仍然 保持完整 这样的数据结构。 我们依然是那样的运气,当我们 要插入四个或更多的总 元素,但我至少可以做出漂亮 有效地利用这个常数 时间,其实。 我不必担心转移 大家作为大卫的倾向是。 堆栈上的任何问题, 此队列? 观众:是的原因 你需要的大小,以便你知道 在那里有一个人? DAVID马兰:没错。 我需要知道数组的大小 因为我需要确切地知道如何 许多这些值都是合法的, 所以,我可以找到放在哪里 旁边的人。 没错。 大小是 - 其实,我们并没有更新。 我自己在26加入。 大小,而不是1,而是2。 所以,现在这的确有助于我找到 列表头,这是不为0,不 1,但为2。 列表的前面 确实是22号。 因为他排在第一,所以他应该 被允许进入商店我面前, 尽管在视觉上,我站在 靠近商店。 没事吧? 这些家伙的掌声鼓励 我们会让他们离开那里。 [掌声] 国宝马兰:我可以让 你守托盘。 我们可以看到发生什么,如果 你想要的,但也许不会。 好的。 所以,现在没有什么离开我们? 好吧,让我建议,有一个 其他一些数据结构,我们可以 开始加入到我们的工具包,将 实际上是非常非常相关,因为 我们潜入网络的东西。 这再次有某种联系 树的形式 一种叫DOM,文件 对象模型。 但是,我们会看到更多的 用不了多久。 让我提出的确定性 现在你可能知道什么叫树 更多的家庭树,在那里你 在有一些祖先 树根。 重男轻女或女家长 树的最顶端。 没有他们的配偶,在这种情况下。 但是,现在我们有什么,我们会打电话给 孩子,这是挂的节点 关闭左子或右的孩子, 这里所描述的箭头。 换句话说,在树的数据结构 电脑,一棵树零 或多个节点。 如果它有至少一个节点, 这就是所谓的根。 这是视觉上的东西 我们在上面画。 该节点,像任何其他节点, 具有零个,一个或两个,或三个, 然而,许多孩子 数据结构支持。 在这种情况下,根存储 值,有两个孩子,2和3, 所以我们一般称之为左 儿童和3的右孩子。 然后当我们得到下降到5,6, 7,6可能被称为中间的孩子。 如果你有四个孩子, 它变得扑朔迷离。 因此,我们停止使用那种 口头上的快捷方式。 但它确实只是一个家族树。 和这里的叶子的节点 自己有没有孩子。 他们挂在树的底部。 那么,我们怎么可能实现的树 具有最大限度仅有的两个孩子吗? 我们会打电话给它一个二叉树。 毕再次意思是两个,在该 的情况下,像二进制。 因此,它可以具有零个,一个 两个孩子最大限度。 我会建议我们实行节点 该结构与一个整数n, 然后两个三分球,一个叫 离开后,一个叫权。 但这些都是刚刚好 任意约定。 ,什么是现在不错的,特别是如果你 样的挣扎概念 递归,或认为这是不 一个真正的解决方案,任何东西, 特别是如果你能 耗尽内存。 现在,我们正在谈论数据 结构和算法,使 我们遍历和操作, 事实证明,递归回来 一个更引人注目 如果没有美丽的方式。 所以我的建议是实施 搜索功能。 鉴于两个输入 - 所以认为这是一个黑盒子。 鉴于两个输入,正和一个int 一棵树的指针,一个指向一个 节点,还是真的一棵树的根,我 声称,该函数可以返回 真的还是假的,值n 是这种树内。 这个黑盒子里面有什么? 那么,四分支。 起初只是检查。 如果树是空的,只是返回false。 如果没有节点,有没有N, 有没有多少,只是返回false。 如果你正在寻找的价值,N,虽然 ,不到树箭头N, 只是要清楚,这是什么意思时, 我写的树,然后箭头 符号,N? 没错。 这意味着取消引用 指针称为树。 去那里,然后拿到里面的 节点并获取其字段名为N。 然后比较实际n表示 通过搜索反对。 因此,如果n是小于n的值 在树节点本身,好了, 这是什么意思? 这乍一看没什么意思。 对吗? 就像当你有一个数组 值,你可能喜欢的应用二进制 作为一种形式的分搜索 而治之。 但假设没有什么我们需要做 二进制搜索在所有的工作 在电话簿和 前面的例子吗? 如何进行排序。 因此,让我们细化的定义树 这里不只是一棵树,它可以 有任意数量的儿童。 不只是一个二叉树,它可以 最大限度有0,1,或2。 但是,作为一个二叉搜索树,或BST, 这仅仅是一个奇特的方式说一个 二叉树每个节点的 左子节点,如果存在,是 小于该节点。 而每一个节点的右子, 如果存在,是更大的 比该节点本身。 所以,换句话说,如果你是画 树出来,所有的数字都 这样精心平衡,这样,如果 你有55根,33可以去 在它的左边,因为它是小于55。 77可以去其正确的,因为 它是大于55。 但是现在注意到,相同的定义, 这是一个递归定义口头, 已申请33。 33的左子必须比它少, 和33的右子,44岁,必须 大于它。 所以这是一个二叉搜索树, 我建议,使用一点点 递归,我们现在能够找到N。 因此,如果n是小于值n的 当前节点,我要去 进取,撑船,所以说话,只是 返回任何回答是的 为n 树的左子。 再次注意,这个函数只是 预计节点明星, 到一个节点的指针。 所以,我一定可以做树 左箭头,这将导致 去到另一个节点。 但是,该节点是什么? 那么,根据这个声明, 剩下的只是一个指针,所以,仅仅 意味着我通过搜索功能 不同的指针,即 就是代表 我的左子树。 因此,在这种情况下,指针33,如果 同时,如果是我们的样本输入 n是大于上面的n值 当前树中的节点,那么我 要继续前进,平底船在其他 方向,只是说,我不 知道此值n是树中, 但我知道,如果它是,它是我的 右分支,可以这么说。 因此,让我叫递归搜索, 再通过一个n,但在传递 我的右孩子指针。 换句话说,如果我目前在55 ,我知道我在寻找99 99 大于55,所以就像我撕毁 电话簿星期前,我们 去正确的,同样是我们 要去这里。 我不知道,如果它是在我的右 孩子,它不是,77是有,但 我知道这是在那个方向。 因此,我呼吁搜索在我的右孩子, 77,让搜索身影从 如果99本任意 例如实际上是存在的。 否则,什么是最终的情况? 如果树是空是一个案例。 如果n小于当前节点的 值是另一种情况。 如果n为大于当前 节点的值是第三种情况。 第四和最后的情况是什么? 我认为我们的情况下,对不对? 它必须是n在 当前节点我。 所以,如果我在寻找55在这一点上 在故事中,那支 树将返回true。 那么,什么有趣的是,我们 实际上,不像周过去,我们种 有两个基例。 ,他们不必 所有在顶部。 顶部是一个基本情况,因为如果 树是空的,有没有什么关系。 只是返回一个硬编码 值false。 底部分支排序 默认情况下,如果我们检查 空,我们已经检查了,如果它应该是 离开了,但是它不应该是,我们已经 检查,如果它应该是正确的,但它 不应该的,清楚地,它必须是 右边我们在哪里。 这是一个基本情况。 因此,有两个递归例 夹在中间。 但我可以写 这在任何顺序。 我只是认为这样的感觉自然 首先检查可能的错误, 然后检查左,右检查,然后 假设你是在节点 你实际上是在寻找。 那么,为什么会这样有用吗? 因此,原来 - 让我跳一个传情 在这里,在网上。 我们将开始使用不是一个 在第一编程语言,但 标记语言。 一种标记语言,是一个 类似的精神编程 语言,但它不会给你的 能够表达自己的逻辑。 它只是给你的能力, 表达自己的结构。 你想放的东西在哪里 在页面上,网页? 你想让它是什么颜色的? 你想让它什么字体大小? 什么话你实际上 想在网页上吗? 所以这是一种标记语言。 但然后我们会很迅速推出 JavaScript中,这是一个完全成熟的 编程语言。 在语法上非常相似的外观 C,但还会有一些 不错,功能更强大,更 用户友好的功能。 和挫折 在本学期,我们会点 即将实施的拼写少得多 使用其他语言的代码行 比C本身允许的,但对于原因 我们很快就会明白。 这将是第一个这样的网页。 这将是完全给人留下深刻印象, 我们的第一个。 简单地说,你好世界。 但是,如果你从来没有见过它 之前,这是HTML, 超文本标记语言。 如果你去某些菜单选项 任何浏览器,在任何网页上 在互联网上,你可以看到的HTML 一些人写信给 创建该网页。 它可能看起来并不 短暂或整齐。 但它会按照这些模式 开放式支架和斜线 字母和潜在的数字。 我想我给你传情 你就可以做什么 后服用CS50。 让我去到cs.harvard.edu /抢劫, 我们自己的罗布·鲍登的主页。 他给我们看。 所以你很快就能够做到这一点。 此外,你听到什么 今天上午 - 你今早 - [仓鼠跳舞音乐] - 你将能作出这种。 等待着我们在周三。 然后我们会看到你。 [仓鼠跳舞音乐] 国宝马兰:在未来CS50 -