扬声器1:对,所以我们又回来了。 欢迎CS50。 是星期七月底。 所以记得,最后一次,我们开始 稍微复杂的看 的数据结构。 由于到现在为止,我们真的 在我们的处置是这样的,一个数组。 但在此之前我们不会丢弃数组 所有有趣的,这的确 实际上,是一些什么 加上这个简单的数据 结构,从而有多远? 什么是它擅长的? 到目前为止,我们已经看到? 你得到了什么? 什么也没有。 学生:[听不清]。 扬声器1:那是什么? 学生:[听不清]。 扬声器1:固定尺寸。 OK,那么,为什么是固定大小的好,虽然? 学生:[听不清]。 扬声器1:确定的,所以它的效率 这个意义上,你可以分配一个 固定大小的空间,希望 恰恰是尽可能多 空间,只要你想。 所以这可能是一个绝对加分。 一个数组的另一侧什么? 是吗? 学生:[听不清]。 扬声器1:所有的 - 对不起? 学生:[听不清]。 扬声器1:在内存中的所有箱子 或给对方。 这是有帮助的 - 为什么? 这是相当正确的。 但如何才能利用这一真理吗? 学生:[听不清]。 扬声器1:没错,我们可以跟踪 一切都只是知道 一个地址,即地址 该内存块的第一个字节。 或字符串的情况下, 地址的第一个 在该字符串中的字符。 并从那里,我们可以找到 结束的字符串。 我们可以找到的第二个元素, 第三个元素,依此类推。 等花俏的手法描述, 特点是阵列给我们 随机访问。 只需使用方括号 符号和数字,你可以跳 一个特定的数组中的元素 在固定时间内,大O 之一,可以这么说。 但也有一些缺点。 数组不是很容易做吗? 什么不擅长什么? 学生:[听不清]。 扬声器1:那是什么? 学生:[听不清]。 扬声器1:在规模扩大。 所以的缺点数组是 正好相反的是什么 一面是。 所以,一个缺点是 ,这是一个固定大小的。 所以你不能真正成长。 您可以重新分配更大的大块 内存中,然后将旧的元素 到新的数组。 然后释放旧的阵列, 例如,通过用malloc或类似的 函数调用realloc的, 重新分配内存。 REALLOC,顺便说一句,试图给你 内存阵列旁边 你已经有了。 但它也可能移动的东西 周围完全。 但总之,这是昂贵的,对不对? 因为如果你有一大块的内存 这个长度,但是你真的想要一个 这种规模,你要保留 你有原创要素, 大致的线性时间复制过程 需要发生 新的旧的阵列。 和现实要求的经营 系统一而再,再而 再大的内存块,就可以开始 花费你一些时间。 因此,它既是祝福和诅咒 伪装,但事实上,这些阵列 固定大小。 但是,如果我们引入,而不是东西 这样,我们称为联 列表中,我们得到了一些积极和 几个缺点在这里。 所以一个链表是一个简单的数据 结构由C结构 情况下,当一个struct,召回,只是 用容器的一个或多个特定 类型的变量。 在这种情况下,什么数据类型 似乎是里面的结构, 我们最后一次称为一个节点? 这些矩形中的每一个是一个节点。 并且每个小矩形 里面它是一种数据类型。 什么样的类型,我们说 他们在周一? 是吗? 学生:[听不清]。 扬声器1:变量和指针,或 更具体地说,一个int,对n, 和指针底部。 两个那些碰巧是32位,在 至少在电脑上像这样CS50 电器,所以他们 得出同样的大小。 那么,什么是使用指针 但显然? 为什么现在这个箭头数组时 这么漂亮,干净和简单的? 指针是什么做的 我们在这些节点中的每个节点? 学生:[听不清]。 扬声器1:没错。 它告诉你在哪里 下一个是。 所以我使用的比喻 使用一个线程来排序 线程这些节点连接在一起。 这正是我们正在做的 指针,因为每个这些 内存块可能会或可能不会 连续回背靠背 内部RAM,因为你每次 调用malloc说,给我足够的 字节一个新的节点,它可能 在这里,或者它可能是在这里。 这可能是在这里。 这可能是在这里。 你只是不知道。 但是,使用指针的地址 这些节点,你可以拼接 一起在视觉上看起来的方式 即使这些东西都像一个列表 传遍你的一个或 你的两个或4 GB的RAM 自己的电脑里面。 所以下行,那么, 链表是什么? 什么是我们的价格 显然支付? 学生:[听不清]。 扬声器1:更多的空间,对不对? 在这种情况下,我们已经增加了一倍 空间,因为我们已经走了 从32位的每个节点,每个 INT,所以现在64位的,因为我们有 保持周围的指针。 你得到更多的效率,如果你的结构 是大于这个简单的事情。 如果你确实有一个学生里面 这是一对夫妇的字符串 名称和房子,也许是一个ID号, 也许其他一些领域完全。 所以,如果你有一个足够大的结构, 那么也许成本的指针 没有什么大不了的。 这是一个位在一个角落的情况下 我们存储这样一个简单的原始 内的链接的列表。 但问题是相同的。 你肯定花更多 内存,但你得到 的灵活性。 因为现在如果我想添加一个元素 在此列表的开头, 我必须分配一个新的节点。 我有只更新那些 不知何故只是移动箭头 周围一些指针。 如果我要插入到的东西 中间的列表,我不必 抛开众人推像我们一样 周过去与我们的志愿者 表示一个数组。 我可以只分配一个新的节点, 然后就点中的箭头 不同的方向,因为它不 必须保持以实际的 内存一个真正像我画的线 这里的屏幕上。 最后,如​​果你想插入 在列表末尾的东西,这是 更容易。 这是任意符号, 但34的指针,以此来猜测。 其指针的价值是什么 可能拉有点像一个老 有学校天线? 学生:[听不清]。 扬声器1:这可能是空的。 事实上,这是一个作者的 表示空。 它是空的,因为你绝对 需要知道在哪里结束的联 名单,免得你保持以下 后,并按照这些箭头 一些垃圾值。 因此,空表示没有任何 更多的节点号为34的右侧, 在这种情况下。 因此,我们提出,我们可以实现 这个节点的代码。 我们已经看到这种 之前的语法。 用typedef定义一个新类型 我们,为我们提供了这样的代名词 对于char *字符串。 在这种情况下,它给我们 速记符号,使结构节点 而是可以被写成 节点,它是干净了很多。 这是少了很多冗长。 节点内显然是一个int 称为n和结构节点* 这意味着正是我们想要的 箭头的意思是,到另一个指针 完全相同的数据类型的节点。 我建议,我们可以实现一个 搜索这样的功能,这在 乍一看似乎 有点复杂。 但是,让我们来看看它在上下文中。 让我去到这里的家电。 让我打开一个名为 列表零点H。 只包含的定义,我们 只是刚才也看到了这些数据 类型称为一个节点。 因此,我们已经把到一个点h文件。 而顺便说一句,尽管这 程序,你将要看到的是 不是所有的,复杂的,它的的确确 当编写一个程序来公约 数据类型一样,把东西拉 有时,在里面你的常量 头文件不一定 你的C文件,当然,当你的 方案变得越来越大,从而使 你知道到哪里寻找既为 在某些情况下,文档或 基本这个样子, 某种类型的定义。 如果我现在打开列表零点 C,注意的几件事情。 它包括了几个头文件,最 我们之前见过。 它包括其自己的头文件。 顺便说一句,这就是为什么双 报价。在这里,相对于角度 括号就行了, 我已经强调了那里? 学生:[听不清]。 扬声器1:是啊,所以它是一个本地文件。 所以,如果你自己在这里的本地文件 第15行,例如,您可以使用 双引号,而不是 的尖括号。 现在,这是一种有趣的。 注意,我已经宣布为全球 这个程序的第18行的变量 被称为第一想法是这是 将是一个指针指向第一个 在我的链表节点,并且我 初始化为null,因为我 没有分配任何实际 节点只是还没有。 因此,这代表1973年,我们 刚才也看到了图片作为 该指针远 左手侧。 所以现在,该指针 不会有一个箭头。 相反,它仅仅是空的。 但它代表的会是怎样的 第一个实际的地址 在此列表中的节点。 所以,我已经实现了它是一个全球 因为,你会看到,这一切 计划并落实在生活中是 一个链表为我。 现在我已经得到了一些原型。 我决定实现的功能,如 缺失,插入,搜索和 穿越 - 最后只是徒步穿越 列表,打印出它的元素。 而现在,这里是我的主程序。 并且我们不会花太多时间 这些,因为这是那种,希望 现在的旧帽子。 我要做到以下几点: 而用户合作。 所以,我要打印 出此菜单。 我格式化它作为 干净,尽我所能。 如果用户在一个类型,即表示 他们要删除的东西。 如果用户有两种类型,即表示 他们要插入的东西。 等等。 我要提示 然后命令。 然后我要使用调用getInt。 所以这是一个非常简单的menuing 界面,您只需要输入 一些映射到一个 这些命令。 现在我有一个漂亮干净的开关 语句要切换 无论用户输入。 而且,如果他们输入了一个,我会 调用delete和突破。 如果他们输入了两个,我会 调用插入和突破。 现在请注意,我已经把每 这些在同一行上。 这是一种风格上的决定。 通常情况下,我们已经看到的东西 像这样。 但我刚刚决定,坦率地说,我的程序 看上去更具可读性,因为 它只有四个案件 像这样只列出。 完全合法使用样式。 我要做到这一点,只要 用户没有输入零,这是我 决定将意味着他们想戒烟。 所以,现在发现我什么 要在这里做。 我要去显然释放的清单。 但在短短的时刻。 首先,让我们来运行这个程序。 因此,让我一个更大的终端 窗口,点斜线列表0。 我要继续前进并插入 50这样的数字,现在打字两 你会看到列表中现在是50。 我的文字只是滚动了一下。 所以,现在看到列表中包含 数字50。 让我们做另一个采取两个插入。 让我们像一个输入的数量。 列表现在,接着为50。 所以这仅仅是一个文字表述 列表。 我们插入一个像 数字42,这是有希望的 要结束了,因为在中间 特别是各种程序 它插入他们的元素。 因此,我们有它。 超级简单的程序,可以 绝对使用一个数组,但我 碰巧使用一个链表 就这样我就可以动态地 增长和收缩。 因此,让我们来看看搜索,如果我 运行命令三,我想搜索 ,也就是说,43号。 显然并没有什么发现, 因为我回来没有反应。 因此,让我们再次做到这一点。 搜索。 50,或者更确切地说,搜索的搜索 42,有一个很好的 有点微妙的含义。 而且我发现有生命的意义。 42,如果你不知道 参考谷歌。 好的。 那么是什么为我做这个程序? 它只是让我插入从而 到目前为止,搜索元素。 让我们快进,那么, 我们瞟了一眼那个函数 周一传情。 所以,我要求这个功能,搜索 第一列表中的一个元素 一,提示用户,然后调用 调用getInt得到一个实际的int 要搜索。 然后注意到这一点。 我要创建一个临时变量 在第188行称为指针 - PTR - 可以把它叫做什么。 这是一个节点的指针 因为我说有节点*。 我初始化它等于 首先,让我实际上是我的 手指,可以这么说,就非常 列表中的第一个元素。 所以,如果我的右手是PTR我 指向同一件事,第一 是否对准。 现在,我们回到代码中, 接下来会发生什么 - 迭代时,这是一个共同的范式 像结构 链表。 我要做到以下几点,同时 指针不等于空,因此, 我的手指指着一些空 值,如果指针箭头n等于N。 我们首先会注意到,n是什么 用户输入每GetInts这里打电话。 和指针箭头N意味着什么呢? 好吧,如果我们再回到这里的图片, 如果我有一个手指指着 九,即第一个节点 箭头基本上意味着去那 节点,并抢在位置n的值, 在这种情况下,数据字段称为N。 顺便说一句 - 我们看到一对夫妇 星期前,当有人问 - 这个语法是新的,但它不 给我们的权力,我们 没有已经有了。 这句话是什么相当于使用 点符号和明星夫妇 星期前,当我们剥开 这一层有点过早? 学生:[听不清]。 扬声器1:没错,这是明星, 那么它是星点N, 括号在这里,它看起来, 坦率地说,我想了很多 更神秘的阅读。 但星级指针,一如既往 手段去那里。 而一旦你在那里,什么样的数据 现场你要访问吗? 那么你用点符号访问 一个结构的数据字段,我 特别希望N。 坦率地说,我认为这 只是很难阅读。 这是很难记得在哪里 做括号走, 明星和一切。 因此,世界上采取了一些句法 糖,可以这么说。 只是一个性感的说法, 这是等价的,并且 或许更直观。 如果指针确实是一个指针, 箭头符号手段去那里找 在这种情况下,该领域称为N。 所以,如果我找到它,发现我做什么。 我只是打印出来,我发现我%, 堵在这个int值。 我叫睡一秒钟只是一种 暂停在屏幕上的东西 给用户一个第二吸收 刚刚发生了什么。 然后我就打破。 否则,我该怎么办? 我更新指针等于 指针旁边的箭头。 所以,仅仅是明确的,这意味着去 在那里,我的老学校的符号。 因此,这只是意味着去任何 你指出,这在很 第一种情况是,我指着 结构九。 所以,我去那里。 然后点符号表示, 在未来获得价值。 但该值,即使它的绘制 作为窄,仅仅是一个数字。 这是一个数字地址。 所以这一行代码,无论 这样写,更神秘 的方式,还是这个样子,稍微 直观的方式,只是意味着移动我的手 从第一个节点到下一个, 然后下一个,然后 下一个,等等。 因此,我们不会纠缠于其他 插入和删除的实现 和遍历,前两个 这是相当复杂的。 而且,我认为这是很容易得到 做口头丢失。 但我们可以在这里做什么 尝试,以确定如何 最好做视觉。 因为我会提出,如果我们 要插入元素 现有的名单,其中 有五个要素 - 9,17,22,26,33 - 如果我要实现这 代码,我需要考虑如何去 这样做。 我建议采取小步 据此,在这种情况下,我的意思是什么 可能出现的情况,我们 可能遇到的一般? 当执行插入一个链接 名单,这恰好是一个 具体例的大小为5。 好吧,如果你要插入一个数字, 喜欢说的头号 保持排序顺序,其中 显然做一个需要数 走在这个具体的例子吗? 开始时一样。 但有趣的是 如果你要插入到这个 列表中,需要什么特殊的指针 显然要更新? 第一。 所以,我认为,这是第一种情况 我们可能要考虑, 方案涉及于 在列表的开头。 让我们为这事也许容易,甚至 更简单的情况下,相对来说。 假设我要插入 35号排序。 这显然​​属于那边。 那么,什么指针,显然是要 在这种情况下必须进行更新? 34的指针变得不空 但该结构的地址 含有数字35。 因此,案例二。 所以,我已经是量化排序 在这里我必须做多少工作。 最后,明显的中间的情况下是 的确,如果我在中间,要 插入像说23,云 在23和26之间,但 现在事情变得有点更 因为涉及什么 指针需要改变吗? 因此,22显然需要改变 因为他不能点到26了。 他需要,以指向新节点 我将不得不通过调用分配 malloc或一些等价。 但是,我也需要新的节点,23 在这种情况下,有它的指针 指向谁? 26。 而且也将是一个 这里的操作顺序。 因为如果我这样做愚蠢的是,我和 实例的开始处开始 列表中,我的目标是要插入23。 检查,它属于 在这里,近九? 号 它属于这里,未来17? 号 是否属于这里旁边22? 是。 现在,如果我在这里很愚蠢的,而不是 通过思考,我可能 分配我的新节点上为23。 我可能会更新指针 节点称为22,指着 在新的节点。 然后我有什么更新 新节点的指针? 学生:[听不清]。 扬声器1:没错。 指着26。 但是,该死,如果我没有已经更新 22的指针指向这个家伙, 现在我有孤儿,其余 列表,可以这么说。 所以,这里的操作顺序 会是重要的。 要做到这一点,我能偷, 说,六个月志愿者。 让我们来看看,如果我们不能做到这一点 视觉上,而不是代码明智。 我们有一些可爱的压力 今天为你的球。 OK,约一,两个,在 回 - 到底有没有。 三,四,双方你 家伙到底。 及五,六。 当然。 五和六。 好吧,我们还会回来 你们下一次。 好吧,我们就到了。 所有的权利,因为你先在这里 你想成为一个笨拙 在谷歌的玻璃在这里? 好,那么,OK,玻璃, 录制视频。 OK,你去好。 所有的权利,所以如果你们可以过来 在这里,我已经提前做好准备 一些数字。 好吧,我们在这里。 而你为什么不走一点 进一步的方式。 ,让我们看看,你叫什么名字, 谷歌玻璃? 学生:本。 扬声器1:本? OK,奔,你将是第一,从字面上。 因此,我们会向您发送 结束阶段。 所有的权利,和你的名字吗? 学生:贾森。 扬声器1:杰森,OK你 9号。 所以,如果你想遵循本办法。 学生:吉尔。 扬声器1:吉尔,你要去 17,如果我这样做 智能,我将不得不 在其另一端开始。 你走那条路。 22。 你是谁? 学生:玛丽。 扬声器1:玛丽,你会是22。 你的名字是什么? 学生:克里斯。 扬声器1:克里斯,你会是26。 然后最后。 学生:戴安娜。 扬声器1:戴安娜,你会是34。 所以你在这里。 好吧,如此完美排序 已经订购。 ,让我们继续前进,为此 这样我们就可以真的 - 奔你只是寻找一种 到无处存在。 OK,让我们继续前进,并描绘这个 使用武器,就像我,究竟 这是怎么回事。 因此,继续前进,给自己一个 步行或两个自己之间。 继续前进,用一只手点 你应该指向谁 在此基础上。 如果你只是指向空 直下到地板上。 OK,这样很好。 所以现在我们有一个链表,让我 建议,我会发挥的作用 PTR,所以我不会打扰 携带这种左右。 然后 - 有人愚蠢的惯例 - 你可以调用任何你想要的 - 前身指针,泼尼松指针 - 它只是我们给的绰号 我们的示例代码,我的左手。 另一方面,要保持 谁是谁在跟踪 下面的场景。 因此,假设,第一,我要拔掉 ,插入第一个例子,说 20,到列表中。 所以我需要有人来 体现我们20号。 所以我需要有人对malloc 从观众。 上来吧。 你叫什么名字? 学生:布莱恩。 扬声器1:布莱恩,所有的权利,所以你 须含20的节点。 好吧,我们在这里。 很显然, 不属于布赖恩? 因此,在中间 - 实际上, 等待一分钟。 我们这样做是为了 我们正在做这个了很多困难 比它需要的是在第一次。 OK,我们要免费布赖恩 和realloc的布赖恩五个。 好了,现在我们要插入 布赖恩五个。 这样一来就在这里 本只是一瞬间。 你大概可以告诉 这个故事是怎么回事。 但是,让我们仔细想想 操作顺序。 和它的正是这种视觉 要排队 与示例代码。 所以,我在这里已经PTR最初指向 不奔,本身的,但在任何 重视他包含在这种情况下 - 再次你叫什么名字? 学生:贾森。 扬声器1:杰森,所以我和Ben 指着杰森在这一刻。 所以现在我必须确定, 布赖恩属于哪里? 那么唯一,我曾访问 现在是他的n个数据项。 所以我要来检查, 布赖恩小于贾森? 答案是真实的。 那么现在需要什么发生, 以正确的顺序? 我需要更新多少指针 总在这个故事呢? 在哪里,我的手仍指向 杰森,和你的手 - 如果你想 把你的手,有点像,我 不知道,是一个问号。 好,好。 好吧,让你拥有 几个候选人。 奔或I或布赖恩或杰森 或其他人,这 指针需要改变吗? 总共有多少人? OK,所以两个。 我的指针并不真的无所谓了 因为我只是暂时的。 因此,它是这两个家伙,据推测, Ben和布赖恩。 所以我建议大家更新 奔,因为他是第一。 这个列表的第一个元素 现在将是布莱恩。 因此,本布赖恩点。 OK,现在该怎么办呢? 谁被指出在谁? 学生:[听不清]。 扬声器1:确定Brian拥有 以指向贾森。 但我已经失去了该指针的轨道? 我知道Jason是吗? 学生:[听不清]。 扬声器1:我做的,因为我 暂时指针。 而据推测,我并没有改变 指向新的节点。 所以,我们可以简单地布赖恩点 我指着谁。 我们就大功告成了。 所以,在插入 开始的名单。 有两个关键步骤。 一,我们必须更新奔,然后 我们也有更新布赖恩。 然后我没有打扰 其余的疲惫 名单,因为我们已经找到了自己的 位置,因为他属于 左侧的第一个元素。 所有的权利,所以非常简单。 事实上,感觉就像我们几乎 这太复杂了。 现在让我们为这事结束 列表,看到 开始的复杂性。 因此,如果现在,我的alloc从观众。 任何人想打55? 好吧,我先看到你的手。 上来吧。 嗯。 你叫什么名字? 学生:[听不清]。 扬声器1 Habata。 OK,就到了。 你会是55号。 所以,你,当然,属于 上面的列表末尾。 因此,让我们重播模拟与我 是PTR只是一瞬间。 所以,我首先要指向 无论奔指向。 我们都指向现在在布赖恩。 因此,图55是不小于5。 所以,我要更新自己的 Brian的下一个指针,指向谁 现在当然贾森。 图55是不小于9,所以 我要更新PTR。 我要更新PTR。 我要更新的PTR 我更新的PTR。 我要去 - 嗯,有什么 你的名字吗? 学生:戴安娜。 扬声器1:戴安娜是指指点点,当然, 在null与她的左手。 那么,这实际上Habata 属于清楚吗? 到左边,在这里。 所以,我怎么知道在这里把她 我想我搞砸了。 因为PTR艺术 时间在这一刻? NULL。 因此,即使,在视觉上,我们就可以 明显看到所有这些 这里的人在舞台上。 我以前没有记录 在列表中的人。 我没有手指指出, 在这种情况下,节点号为34。 因此,让我们真正开始过。 所以,现在我居然需要 一个第二局部变量。 这是什么,你会看到在 实际样品的C代码,在那里,因为我去, 当我更新我的右手指向 杰森,从而留下布赖恩的背后,我 最好开始用我的左手 更新我在哪里,让我去 通过这个名单 - 比我预期的更笨拙 现在这里视觉 - 我会去的 列表末尾。 这手仍是空的,这是非常 没用的,其他的比来表示 我很清楚在列表末尾, 但现在至少我有这个 前身指向这里,所以 现在是什么手和指针需要什么 要更新? 你想谁的手 先来重新配置? 学生:[听不清]。 扬声器1:OK,所以戴安娜的。 在哪里你想点 戴安娜的左指针? 在55中,据推测,从而使 我们已经有插入。 55指针应该在哪里去了? 向下,占空。 而我的手,在这一点上,不 不要紧,因为他们只是 临时变量。 所以,现在我们就大功告成了。 所以额外的复杂性 - 它并不难实现, 但我们需要一个辅助变量 确定之前,我将我的权利 另一方面,我更新我的左值 另一方面,泼尼松指针在这种情况下,因此 我有一个尾随指针 跟踪我在哪里。 顺便说一句,如果你以为这 通过,这种感觉就像是一个 必须保持有点烦 跟踪这个左手。 将另一种解决方案 这个问题已被? 如果你得到了重新设计数据 我们正在谈论的结构 通过吧? 如果这只是一种感觉有点 恼人的一样,两个指针 通过列表,谁还能 有,在一个理想的世界中,保持 我们所需要的信息? 是吗? 学生:[听不清]。 扬声器1:没错。 所以实际上是一个有趣的 胚芽的想法。 而前一个指针,这个想法 指向前一个元素。 如果我只是体现 列表本身的内部? 这将是难以想像 没有所有的纸张 掉落到地板上。 但是,假如这些人同时使用 他们手中没有先前 指针,和一个下一个指针,从而 执行什么,我们会打电话给一个双 链表。 这将允许我排序退, 更容易无我有, 程序员,不得不保持 手动跟踪 - 真正的手动 - 以前我一直 在列表中。 因此,我们将无法做到这一点。 我们将保持它的简单,因为这是 要来的价格,两倍 多的空间的指针, 如果你想要第二个。 但是,这确实是一个共同的 数据结构被称为一个 双向链表。 让我们在这里做最后的例子把 这些家伙,他们的苦难。 所以malloc的20。 来吧从那里的过道。 好吧,你叫什么名字? 学生:[听不清]。 扬声器1:对不起? 学生:[听不清]。 SPEAKER 1:Demeron的? 确定上来吧。 您应为20。 你显然要 属于17和22之间。 因此,让我吸取我的教训。 我要开始指针 指着布赖恩。 我要我的左手 只更新布莱恩,我谨 杰森,检查少做了20比9? 号 20小于17? 号 20小于22? 是。 那么,什么指针或手需要改变 他们指着呢? 因此,我们可以做的17指向20。 所以这就是罚款。 我们要指出在哪里 你的指针现在? 在22。 我们知道22,再次感谢 我临时指针。 因此,我们有“确定”。 所以在这临时存储 我一直保留着的轨道,每个人都。 现在,你可以直观地去到哪里 属于你,现在我们需要1,2,3, 4,5,6,7,8,9个压力球, 和掌声雷动 这些家伙,如果我们能。 干得漂亮。 [掌声] 扬声器1:所有权利。 您可能保持件 纸作为纪念。 好,那么相信我,这是一个很大 更容易穿行 人类比它的实际代码。 但你会发现在短短的时刻 现在,是相同的 - 哦,谢谢你。 谢谢 - 是,你会发现相同的数据 结构,链表,实际上可以 可以使用作为构建块更 复杂的数据结构。 实现过这里的主题是 我们绝对介绍 进入实施的复杂性 在此算法中。 插入,如果我们通过它去, 删除和搜索,是一个小的 比它更复杂 是一个数组。 但是,我们获得了一些活力。 我们得到一个自适应的数据结构。 但同样,我们付出的代价有一些 额外的复杂性,无论是在 执行它。 我们放弃了随机访问。 而且说实话,有没有一些不错的 干净的玻片,我可以给你, 这里说的是为什么一个链表 优于数组。 离开它。 由于主题现在再次发生,甚至 更何况在未来几周内, 不一定 一个正确的答案。 这就是为什么我们有独立的轴 问题集的设计。 这将是非常敏感的上下文 您是否要使用此数据 结构或那一个,会 取决于什么对你很重要条款 的资源和复杂性。 但是,让我提出,理想的数据 结构,圣杯,将 东西是恒定的时间, 不论多少东西 在它里面,它不会是惊人的,如果一个 返回的数据结构答案 常量时间。 是。 这个词是在巨大的字典。 “或”否“,这个词是没有的。 或任何这样的问题。 那么让我们来看看,如果我们不能至少 走,一步步走向。 让我提出了一个新的数据结构, 可用于不同的事情, 在这种情况下,所谓的哈希表。 所以我们实际上一眼 在一个数组中,在这种情况下, 有些武断,我画这 作为数组排序的哈希表 两维数组 - 或者更确切地说,它这里描绘为两 维数组 - 但是这仅仅是 大小为26的数组,例如,如果我们 调用数组桌,桌上托架 零是在顶部的矩形。 表托架25是矩形 在底部。 我这是怎么可能画出一个数据 我想存储结构中, 人的名字。 因此,举例来说,我不会画 整个事情上的开销,如果我 该数组,我现在要 调用一个哈希表,这又是 零的位置。 这里是位置 一个,等等。 我要求,我想用这个数据 结构,为了讨论的方便, 存储人的名字,Alice和Bob 查理和其他类似的名称。 所以,现在觉得这个作为起点 ,也就是说,一个字典 有很多的话。 他们正好是名 在我们的例子。 这是太有密切关系,也许, 实施一个拼写检查,因为我们 可能问题设置6。 所以,如果我们有一个总规模26阵列 因此,这是第25的位置 在底部,我要求爱丽丝 字典中的第一个字 名,我想插入RAM, 到该数据结构中,其中 爱丽丝的直觉告诉你, 在这个数组名称应该去? 我们有26个选项。 如果我们想要把她吗? 我们希望她在支架为零,对不对? 为爱丽丝,我们称之为零。 和B,和C将有两个。 因此,我们打算写 爱丽丝的名字在这里。 如果我们再插入鲍勃,他 名称会去这里。 查理会去这里。 如此反复向下 这样的数据结构。 这是一个美妙的数据结构。 为什么呢? 那么什么是运行时间 插入成这样的一个人的名字 数据结构的权利吗? 鉴于实施该表, 诚然,作为一个数组。 那么它的恒定时间。 这是一个顺序。 为什么呢? 那么你如何确定 爱丽丝属于? 你看看她的名字的信吗? 第一。 在那里,你可以得到,如果它是一个字符串, 只是看着串 支架零。 因此,第0个字符的字符串。 这是很容易的。 我们已在加密 分配星期前。 然后,一旦你知道Alice的 字母是大写的A,我们可以减去 关闭65或资本A本身, 这给了我们为零。 因此,我们现在知道,爱丽丝属于 在零的位置。 和给定的一个指针,指向这个数据 某种结构,多久? 它带我找到位置 阵列中的零? 只需一个步骤,这是恒定的时间 由于随机接入中,我们 建议的是一个数组的一个特征。 因此,在短期,搞清楚什么索引 Alice的名字,这是在 这种情况下,是A,或让刚刚解决 为零,其中B是C是 二,计算出 是恒定的时间。 我只是来看看她的第一个字母, 搞清楚其中零为 数组也是恒定的时间。 因此从技术上讲这是 像现在两个步骤。 但是,这仍然不变。 所以,我们称之为一大O,所以我们 爱丽丝插入到这个表中 常量时间。 不过,当然,我 天真在这里,对不对? 如果在课堂上有亚伦? 还是艾丽西亚? 或任何其他的名字开始 A.我们要去哪里放 那人,对不对? 我的意思是,现在只有三个 老百姓餐桌上,所以也许我们 应该把亚伦的位置 零壹两三个。 好吧,我可以在这里把A。 然而,如果我们尝试将大卫 这个名单,大卫去哪里? 现在,我们的系统开始打破 向下,向右? 因为现在,大卫在这里结束了 如果阿龙其实是在这里。 所以现在有一个整体思路 干净的数据结构,让我们 恒定的时间插入不再 恒定的时间,因为我有 检查,哦,该死的,有人已经 在爱丽丝的位置。 让我探究这些数据的其余部分 结构,寻找一个位置把 有人喜欢亚伦的名字。 等也开始 线性时间。 此外,如果你现在想找到 亚伦在此数据结构,你 检查和亚伦的名字是不是在这里。 理想情况下,你只说亚伦 而不是在数据结构中。 但是,如果你开始做空间 亚伦那里应该有一个D 或E,你最坏的情况下,有检查 整个数据结构,在 这种情况下,移交到的东西 表的大小成线性关系。 所以所有的权利,我会解决这个问题。 这里的问题是,我不得不 26此数组中元素。 让我改变它。 哎呀。 让我改变它,因此而幸福 大小26个,发现底部 指数将改变为n减1。 如果26显然是太小了人类的 的名字,因为有成千上万的 世界的名字,让我们使 在100或1000或10000。 让我们只分配更多的空间。 嗯,这并不一定减少 的概率,我们不会有两个 人们起的名字, 所以,你要尝试将 名位置零。 他们还在碰撞, 意味着我们仍然需要一个解决方案,把 爱丽丝亚伦和艾丽西亚和其他 名开始与A别处。 但多少的问题是什么? 什么的概率 有碰撞在一个数据 这样的结构? 好吧,让我 - 我们会回来的 这里这个问题。 看我们如何可能 先解决它。 让我拉起这个建议。 我们刚刚描述的是一种算法, 一个启发式称为线性 探测,即如果你试图插入 这里的东西在此数据 结构,该结构被称为一个哈希表, 而且也没有的房间里,你 真正探测的数据结构 检查,这是可用的? 这是这是可用? 这是? 而当它终于插入 名字,你原本打算 在该位置的其他地方。 但是,在最坏的情况下,唯一的现货 可能是最底层的数据 结构,数组的尽头。 因此,线性探测,在最坏的情况下, 下放成线性算法 亚伦,如果他恰好是最后插入 这个数据结构中,他可能会 碰撞,该第一位置,但 然后结束坏运气的最末尾。 因此,这是不是一个常数 一次圣杯的我们。 这种方法插入元素 一种数据结构,称为散列 表不似乎是恒定的时间 至少不会在一般的情况下。 它可以下放成线性的东西。 那么,如果我们解决冲突 有所不同呢? 因此,这里是一个更复杂 仍然接近 称为哈希表。 哈希,顺便说一句, 我的意思是指数 我前面提到的。 哈希的东西可以 想到作为一个动词。 所以,如果你哈希爱丽丝一个名字, 哈希函数,可以这么说, 应该返回一个数字。 在这种情况下是零,如果她是属于 位置为零,如果她属于 的位置,等等。 所以,我的哈希函数迄今一直 超级简单,只看着 在别人的名字的第一个字母。 但是哈希函数需要 输入某些数据块, 一个整数,字符串,等等。 它吐出一个典型的数字。 而且这个数字是该数据 在数据结构中的元素属于 这里称为哈希表。 所以只是凭直觉,这是一个 略有不同的上下文中。 这实际上是指一个例子 涉及的生日, 可能有多达 31月份中的天。 但是,什么人决定 做在发生碰撞时? 上下文,而不是现在的碰撞 名,生日,而是碰撞 如果两个人有相同的生日 10月2日,例如。 学生:[听不清]。 扬声器1:是啊,所以我们在这里有 利用链表。 因此,它看起来有点不同 把它比我们更早。 但是,我们似乎有一个数组 在左手侧。 这是一个索引,因为没有 特别的原因。 但它仍然是一个数组。 这是一个数组的指针。 每一元素,每个 这些圆圈或斜线 - 斜线 代表空 - 这些 指针显然指向 什么数据结构? 链表。 所以,现在我们有能力 硬到我们的程序代码 表的大小。 在这种情况下,我们知道从未有 在一个月内超过31天。 所以硬编码值,如31 在这种情况下合理。 在名称的上下文中,硬编码 26是不讲理的人 名字才开始,例如, 涉及A到Z的字母 我们可以塞进他们都到数据 只要结构,当我们得到一个 碰撞,我们不把这里的名字, 我们反而认为,这些细胞 不是字符串本身,而是作为 的指针,例如,爱丽丝。 然后爱丽丝可以有另一个指针 另一个名字开始 A.和鲍勃实际上是在这里。 如果有另一个名字开始 B,他结束了在这里。 等各元素与该 表二,如果我们设计一个 更巧妙一点 - 来吧 - 如果我们设计了这个多一点 巧妙的,现在变成了一个自适应数据 结构,那里是没有硬性限制 你可以插入多少元素 到它,因为如果你这样做有 碰撞,这很好。 只要继续下去,并将它附加到 我们所看到的有点前 被称为一个链表。 那么让我们来的暂停只是一瞬间。 碰撞的概率是什么 摆在首位? 对的,也许我过思考,也许 我在工程的这个问题, 因为你知道是什么吗? 是的,我可以拿出任意 关闭我的头顶部的例子喜欢 Allison和亚伦,但在现实中, 给定的均匀分布 投入,是一些随机插入 到一个数据结构,什么是真正的 碰撞的概率? 好吧原来,它实际上是 超高。 让我概括 问题是这个。 因此,在一个房间里的n CS50学生,什么是 的概率,至少 两名学生在房间里 有相同的生日吗? 因此,有什么。几个洪德 - 200,300人在这里和几个 今天在家百余人。 所以,如果你要问自己什么 两个人的概率 在这个房间里有相同的生日, 我们可以弄清楚了这一点。 其实我要求有两个 同一天生日的人。 举例来说,有没有人 今天生日吗? 昨天? 明天? 所有的权利,所以感觉像我要去 不得不做这363左右 次真正弄清楚 如果我们这样做,有碰撞。 或者,我们可以做到这一点数学 而不是繁琐 这样做。 并提出以下建议。 所以,我建议,我们可以模拟 两个人的概率 同一天生日的概率为1 减去的概率没有一个具有 同一天生日。 所以就弄这个,这只是 花哨的编写方式, 在房间里的第一人,他或她 可以有任何其中一个可能的 生日的一年,假设365天 与人道歉 2月29日生日。 因此,在这个房间里的第一人免费 有任意数量的生日 365的可能性,所以, 我们要做的,365除以365, 这是其中之一。 旁边的人在房间里,如果我们的目标 是为了避免碰撞时,也只能 有他或她的生日就如何 许多不同的可能的天? 364。 所以这个表达式中的第二项是 基本上这样做对我们的数学 通过减去一个可能的日子。 然后第二天,第二天, 第二天下来的总数 在房间里的人。 如果我们再考虑,又是什么 的概率不是人人有 独特的生日,但1减去再次 ,我们得到了什么是一个表达式 可以很稀奇 这个样子。 但它更有趣 看视觉。 这是一个图表上的x轴 多少人在房间里, 生日数。 在y轴上的概率是 碰撞时,两个人 具有相同的生日。 而从这个曲线是外卖 只要你喜欢40 同学们,你们是在90%的概率 ,combinatorically两个 人或以上有 同一天生日。 一旦你得到58人喜欢它的 几乎100%的机会两个 房间里的人将不得不 同一天生日,即使有 365或366个可能的桶, 只有58人在房间里。 只是统计学,你很可能会 得到的碰撞,在短 激励这个讨论。 即使我们得到看中这里, 开始这些连锁,我们还是 将有碰撞。 所以引出了一个问题,什么是 成本做插入和删除 进入这样一个数据结构? 那么让我提出 - 并让我回到屏幕上对 在这里 - 如果我们有n个元素 列表,所以如果我们试图插入 n个元素,我们有 总共有多少桶? 比方说,共31桶 在的情况下的生日。 什么是最大长度为一个 这些链可能? 如果再有31个可能 在一个给定月份的生日。 我们只是聚集大家 - 实际上这是一个愚蠢的例子。 让做26代替。 因此,如果实际拥有人名列 从A到Z,从而使 我们26的可能性。 我们使用一个数据结构,如 我们刚才看到的,据此,我们有 一个数组的指针,其中每个 指向一个链表地方的 第一份清单是每个人都 爱丽丝的名字。 第二个名单是每周与 命名开始, 为B,依此类推。 什么可能各有长短 这些列表,如果我们假设一个干净的 从A到Z的名称分配 在整个数据结构? 有n个人的数据结构中 除以26,如果他们很好 摊开在整个 的数据结构。 因此,每个这些的长度 链为n除以26。 但在大O表示法,那是什么? 什么是真的? 所以这真的只是N,对不对? 因为我们说,在过去, 唉你除以26。 是的,在现实中,它是速度更快。 但是,从理论上讲,它不能从根本上 所有的更快。 因此,我们不似乎是所有的东西 接近本圣杯。 事实上,这仅仅是线性时间。 哎呀,在这一点上,为什么我们不 只使用一个巨大的链表? 为什么我们不只是用一个巨大的 数组来存储的名称 每个人都在房间里吗? 嗯,还有东西 引人注目的一个哈希表? 还有一些引人注目的 关于数据结构的 看起来像这样吗? 此。 学生:[听不清]。 扬声器1:右键,并再次,如果它只是 一个线性时间算法,并有 线性时间的数据结构,我为什么不 只是在一个大的存储每个人的名字 阵列,或在一个大的链表? 停止CS这么更难 比它需要的吗? 什么是引人注目的,甚至 虽然我划出来? 学生:[听不清]。 扬声器1:插入都没有? 昂贵了。 因此,插入可能仍然 时间是恒定的,即使你的数据 结构看起来是这样的,琳琅满目的 指针,其中每个指向 潜在的链表。 你怎么能实现恒 时间插入的名字? 把它贴在了前面,对不对? 如果我们牺牲一个设计目标 所说,我们希望保持 每个人的名字,例如,排序, 舞台上所有的数字排序, 假设我们有一个 未分类的链表。 我们只需花费一个或两个步骤, 像Ben和布莱恩的情况下 早些时候,插入一个元素 在列表的开头。 因此,如果我们不关心排序的所有 开头的名字或全部 以B开头的名字,我们仍然可以 实现恒定的时间插入。 现在回头Alice或Bob或任何名称 更普遍的仍是什么? 大O的n除以26,在 理想情况下,每个人的均匀 分布,其中有尽可能多的 有Z的,这可能是 不现实的。 但是,这仍然是线性的。 但在这里,我们再回过头来点 渐近符号 理论上确实如此。 但在现实世界中,如果我要求 我的程序可以做一些26倍 速度比你的,其程序 你要喜欢使用? 你的还是我, 快26倍? 实际上,人是26 倍的速度,即使在理论上 我们的算法运行在相同的 渐近运行时间。 让我提出一个不同的 完全的解决方案。 如果这不吹你的头脑, 我们的数据结构。 因此,这是特里 - 样的一个愚蠢的名字。 它来自检索,字 拼写特里,T-R-I-E,因为 当然检索听起来像特里。 但是,这是历史 的特里字。 因此,一个特里确实是某种树, 它也是一上场就那个字。 即使你可以不太看到它 这个可视化,特里是一个 树结构,就像一个家庭树 在顶部和意见的一个祖先 孙子和重孙 离开底部。 但特里在每个节点是一个数组。 ,它是在一个数组 - 让 过于简单化了一会儿 - 这是一个 阵列,在这种情况下,大小为26,其中 每个节点是数组的大小为 26的方法,其中在第零个元素 数组代表A,最后 在每个这样的元素 数组代表Z。 所以,我建议,那么,这个数据 结构,称为一个特里,可 也用于存储字。 我们刚才也看到了,我们如何能够存储 的话,在这种情况下,名称,这样我们 前面所看到的,我们如何能够存储数字, 但如果我们专注于名或字符串 这里,发现什么有趣的。 我要求麦克斯韦的名字是 内的这样的数据结构。 你在哪里看到麦克斯韦? 学生:[听不清]。 扬声器1:在左边。 那么,有什么有趣的与此数据 而不是存储结构 串M-à-X-W-E-L-L反斜杠零,所有的 连续,就是你,而不是做 以下。 如果这是一个类似的数据结构的线索, 的每个节点又是一个数组, ,你想,你先存储麦克斯韦 指数和根的节点,所以 说话,最上面的节点, 右,所以在位置M, 大致可分为中间。 然后从那里,你遵循 一个子节点的指针,可以这么说。 所以家谱感, 你跟着它向下。 导致你到另一个节点 左边有,这是 只是另一个数组。 然后,如果你想存储麦克斯韦, 你找到指针,表示 A,这是此人在这里。 然后你去到下一个节点。 和通知 - 这就是为什么图片的 有点自欺欺人 - 这个节点看起来超级微小的。 但是,这样做的权利是Y和Z。 这只是笔者已截断 图片,让你实际上 看到的东西。 否则这幅画 将是巨大的宽。 所以,现在你的索引位置X,然后 W,然后E,那么L,L,然后有什么 这种好奇心? 那么,如果我们正在使用这种新 采取有关如何存储中的字符串 数据结构,你仍然需要 基本上在数据核对 结构词语到此为止。 换句话说,这些节点中的每个节点 不知何故要记住,我们 后面其实所有这些指针 并留下一点点 面包屑的底部,在这里对本 结构示意M-à-X-W-E-L-L 确实这个数据结构中。 因此,我们可能会做如下。 我们只是在图片中的每一个节点 锯有一个大小为27的数组。 它现在27,因为在p设置6个, 实际上,我们就会给你一个撇号, 所以我们可以有名称,如奥赖利 和其他带撇号。 但同样的想法。 在这些元素 阵列指向一个struct 节点,所以只是一个节点。 因此,这很容易让人想起 我们的链表。 然后我有一个布尔值,我将 致电字,这是只是要 如此,如果一个词结束 树中的节点。 它有效地代表小 三角形,我们刚才也看到了。 因此,如果有一个字在该节点处结束 树,那田字是真实的, 在概念上被检查过,或 我们绘制这个三角形,是有 这里是一个字。 所以这是一个特里。 现在的问题是,什么 是它的运行时间? 它是大O的n? 是别的原因呢? 好吧,如果你有n个名字,在此数据 结构,麦克斯韦只是其中之一 他们,什么是运行时间 插入或找到马克斯韦尔? 什么是运行时间 插入麦克斯韦? 如果有n其他名称 已经在表中? 是吗? 学生:[听不清]。 扬声器1:是的,它的长度 的名字,对不对? 所以M-A-X-W-E-L-L,所以这样的感觉 算法是大O七。 现在,当然,该名称 将长短不一。 也许这是一个简短的名称。 也许这是一个较长的名称。 但这里的关键是, 这是一个常数。 也许这不是真的不变, 不过神来,如果实事求是,在 字典里,可能有一些限制 中的字母的数目 在某个特定国家的人的名字。 因此,我们可以假设, 值是一个常数。 我不知道它是什么。 这也可能是大于 我们认为它是。 因为总有一些角落 一个疯狂的长名称的情况。 因此,让我们叫它K表,但它仍然是一个 常数,大概,因为每一个 命名在世界上,至少在 特定的国家,该长度或 短,所以它是恒定的。 但是,当我们已经说了一句大 O的一个恒定值,那是什么 真的等同吗? 这真的是同一件事 说恒定的时间。 现在,我们是一种欺骗,对吧? 我们利用一些理论 这里要说的是,订单的k 真的只是为了一个, 和它的持续时间。 但它确实是。 因为这里的关键洞察力是 如果我们有n个名字已经在这 数据结构,我们插入麦克斯韦 是需要我们的时间量 在所有受影响的插入麦克斯韦 有多少人 在数据结构中? 似乎不。 如果我有一个10亿多元素 特里,然后插入麦克斯韦, 他在所有受影响? 号 而这不同于任何一天的数据 结构到目前为止,我们已经看到,其中 你的算法的运行时间是 完全独立的多少 东西已经是或不是 在该数据结构中。 因此,与这提供了你现在是一个 机会对p六集,这将 再次涉及实施自己的 拼写检查器,读入150,000 的话,如何最有效地存储, 不一定是显而易见的。 虽然我渴望找到 圣杯,我不 声称,特里。 事实上,一个哈希表,很可能 被证明是更有效的。 但那些只是 - 这只是一个设计决策 你将不得不作出。 但在收盘让我们50岁左右 秒采取偷看是什么样的 下周提前超出了我们的过渡 从这个命令行 世界上,如果C程序网络的事情 基于语言,如PHP, JavaScript和互联网本身, 协议,如HTTP,你 理所当然的多年 现在,类型最 一天,也许,或可见一斑。 我们将开始剥开 层是什么是互联网。 什么是代码, 今天的基础工具。 所以,50秒这个传情。 我给你的净勇士。 [视频回放] 他带来一个消息。 有了自己的协议。 他来到世界残忍防火墙, 漠不关心的路由器和危险远 比死亡更糟糕。 他的速度快。 他很强壮。 他的TCPIP。 他有你的地址。 勇士净。 [END视频播放] 扬声器1:这是如何在互联网上 应下周工作。