[音乐播放] DOUG LLOYD:好,因此在 这一点在使用过程中, 我们已经介绍了很多C的基础知识 我们知道了很多关于变量,数组, 指针,所有的好东西。 排序的所有这些都是建立 在看到的基本面, 但我们可以做更多的,对不对? 我们可以结合东西 一起以有趣的方式。 因此,让我们做的是,让我们开始 另辟蹊径的什么C给我们, 并开始创建自己的数据 利用这些建筑结构 块一起做一些事情 真正有价值的,有用的。 我们能做到这一点的方法之一是 谈收藏。 因此,到目前为止,我们已经有某一种数据 结构较集合 对喜欢价值观,相似的价值观。 这将是一个数组。 我们有一个整数集合或 字符等的集合。 的结构也进行排序数据的 结构收集信息, 但它不是用来收集类似的值。 它通常混合了不同的数据类型 一起在单一盒子。 但它本身并不是 用于链接在一起 或者连接到一起类似 项,如一个数组。 数组是伟大的 元素查找,但召回 这是非常困难 插入到一个数组, 除非我们插入的 该数组的末尾。 而最好的例子,我有 因为这是插入排序。 如果你还记得我们的视频 在插入排序, 有很多的 参与其费用 拿起元素,将它们转移 出适合的东西的方式 成阵列的中间。 阵列也从另一个患 问题,这是不灵活。 当我们声明一个数组, 我们这一次机会吧。 我们得到的说法,我想 这些元素。 可能是100,它可能 是1000,它可能 是x,其中x是一个数字,用户 给了我们一个提示,或在命令 行。 但是,我们只有一次机会吧,我们 没有得到,然后说,哦,其实我 需要101,或者我需要X加20。 太晚了,我们已经宣布了 数组,如果我们想要获得101或x 加上20,我们要声明 一个完全不同的阵列, 复制数组中的所有元素 过来,然后我们有足够。 而如果我们又错了,是什么 如果我们真的需要102或x加40, 我们要再次做到这一点。 因此,他们非常不灵活 对于调整我们的数据, 但如果我们结合在一起的一些 我们已经已经基本知识 了解指针和结构, 特别是使用动态存储 分配使用malloc,我们 可以把这些碎片拼凑起来 创建一个新的数据结构 - 一个 单链表,我们可能say-- 这使我们能够成长, 收缩值的集合 我们不会有任何浪费的空间。 所以,再一次,我们称这样的想法, 这个概念,一个链表。 特别是,在这个视频我们 谈到单向链表, 然后另一个视频中,我们将讨论 关于双向链表,这 只是在这里一个主题的变化。 但一个单向链表 由节点, 节点仅仅是一个抽象的term-- 这只是一些我打电话 这是一种 结构,基本上,我? 只是要称之为node--,这 节点具有两个构件,或两个字段。 它的数据,通常是一个 整数,字符浮子, 或者可以是某种其他数据类型 您已经定义了类型定义。 它包含一个指向 相同类型的另一节点。 因此,我们有两件事情里面 这个节点,数据和指针 到另一个节点。 如果你开始显现 这一点,你可以考虑一下 像链节点的那 连接在一起。 我们的第一个节点,它 包含数据,和一个指针 到第二个节点,其中包含 数据,和一个指针到该第三节点。 所以这就是为什么我们称它为 链接列表,它们链接在一起。 这是什么特别的 节点结构是什么样子? 好吧,如果你从我们的视频回忆 定义自定义类型,类型高清, 我们可以定义一个结构 - 和 键入这样定义的结构。 tyepdef结构sllist,然后我 使用这个词的价值在这里随意 以指示真的任何数据类型。 你可以传递一个整数或浮点数, 你可以有一切你想要的。 它不再仅仅限于 整数,或者类似的东西。 因此,值是任意 数据类型,然后一个指针 到同一类型的另一节点。 现在,有一个小抓 这里定义的结构 当它是一个自我参照结构。 我必须有一个临时的 命名为我的结构。 在这一天我的结束 显然想将它命名 SLL节点,这是最终的新 名字我喜欢的类型定义的一部分, 但我不能使用SLL节点 在这中间。 是的原因,我没有 创建了一个名为类型SLL节点 直到我在这里打这个最后一点。 直到这一点,我必须有 另一种方式来参考此数据类型。 而这是一个自 参照数据类型。 它; S的一个数据类型 结构,它包含一个数据, 和一个指针到另一个 相同类型的结构。 所以,我需要能够引用 这种数据类型至少暂时 所以给它一个暂时的 结构sllist名 让我那么说我想要一个 指向另一个结构sllist, 一个结构sllist明星,然后 我已经完成了定义后, 我现在可以把这种类型的SLL节点。 所以这就是为什么你看到有 一个临时的名字在这里, 但这里的永久名字。 有时候,你可能会看到 结构的定义, 例如,是不 自我指涉,是 没有说明的名字在这里。 它只想说typedef结构, 打开大括号,然后定义它。 但是,如果你是结构是自 引用,因为这个人是, 你需要指定一个 临时类型名称。 但最终,现在 我们已经做到了这一点, 我们只能参考 这些节点,这些单位, 作为目的SLL节点 这段视频的其余部分。 好吧,让我们知道如何 创建一个链接列表节点。 我们知道如何定义 一个链接列表节点。 现在,如果我们要开始 用它们来收集信息, 有一对夫妇经营的我们 需要了解和使用。 我们需要知道如何创建 链表凭空。 如果没有清单已经, 我们要开始的。 因此,我们需要能够 以创建一个链表, 我们需要大概搜索 通过链接列表 找到我们正在寻找的元素。 我们需要的是能够插入 新事物进入榜单, 我们希望我们的名单能够成长。 同样,我们希望能够 从我们的名单中删除的东西, 我们希望我们的名单,以便能够收缩。 而在年底我们 计划,特别是 如果你还记得,我们是 动态分配内存 以通常建这些列表, 我们要释放所有的内存 当我们用它做的工作。 因此,我们需要能够删除一个 整个链表在​​一个失败的一举。 因此,让我们通过 某些操作 和我们怎样才能使其可视化, 在伪代码说话特别。 因此,我们要创建一个 链表,所以也许我们 要定义一个函数 这个原型。 SLL节点明星,创造,而我路过 在一个参数,一些任意数据 再次键入某些任意数据类型的,。 但是我returning--这个功能应该 还给我一个指针,以一个单 链接列表节点。 同样,我们正在努力创造 链表凭空, 所以我需要一个指针 当我做了该名单。 那么,什么是这里涉及的步骤? 好了,第一件事我 要做的是动态 分配空间用于新的节点。 同样,我们正在创造出来的薄 空气中,所以我们需要为它的malloc空间。 当然,马上 我们的malloc后, 我们经常检查,以确保我们的 pointer--我们没有得到回空。 因为如果我们尝试 尊重一个空指针, 我们要遭受 段错误,我们不希望出现这种情况。 然后,我们要填补该领域, 我们要初始化值字段 并初始化下一字段。 然后我们想用于:最终的 函数原型indicates--我们要 的指针返回到SLL节点。 那么是什么让这个样子视觉? 嗯,首先我们要动态地 分配空间用于新SLL节点, 所以我们malloc--这 视觉表示 节点,我们刚刚创建。 我们检查,以确保 它不是null--在这种情况下, 画面不会有 示,如果它为空, 我们会耗尽内存, 所以我们好去那里。 所以,现在我们是在步骤C, 初始化节点值字段。 那么,在此基础上功能 叫我用在这里, 貌似我想通过在6, 所以我会在值字段6。 现在,初始化下一个字段。 好了,我该怎么办那里, 旁边有个什么吧, 这是在列表中的唯一事情。 那么什么是列表中,接下来的事情? 它不应该指向什么,对吧。 还有没有别的那里,所以有什么 我们知道,这一概念的nothing-- 指向什么? 它应该是,也许我们要 把一个空指针出现, 我会代表空 指针只是一个红盒子, 我们不能再往前走。 正如我们将看到一个小以后, 我们将有最终链 箭头连接 这些节点一起, 但是当你打的 红色的框,这就是空, 我们不能再往前走, 这是该列表的末尾。 最后,我们只是想 返回一个指向该节点。 因此,我们会打电话给它新的, 并返回新 因此它可被用 无论函数创建它。 所以我们去,我们已经创建了一个单 链表节点无中生有, 现在我们有了一个可以使用的列表。 现在,让我们说,我们已经 有大型连锁, 我们要找到的东西在里面。 我们希望有一个功能是怎么回事 返回true或false,这取决于 在该列表中是否存在某个值。 函数原型,或 声明该函数, 可能看起来像this-- BOOL发现,和 那么我们想传递的两个参数。 第一,是一个指针,指向 该链接的表的第一个元素。 这实际上是你会 总想跟踪, 实际上可能是东西, 你甚至放在一个全局变量。 一旦你创建一个列表, 你永远,永远 要保持的非常轨迹 列表的第一个元素。 这样,你可以参考其他所有 只是简单地跟着链条元素, 无需保持指针 完整的每一个元素。 你只需要跟踪第一 一个,如果他们都链接在一起。 然后是第二件事 我们传递再次 是任意some-- 我们的任何数据类型 寻找有内 希望列表中的节点之一。 那么哪些步骤? 好了,我们做的第一件事是 我们创建了一个横向的指针 指向列表头部。 那么,为什么我们这样做,我们已经 有一个指针在表头, 为什么我们不只是移动了一绕? 嗯,就像我刚才说的, 这对我们来说真的很重要 要始终保持轨道的 列表中的第一个元素。 所以它实际上更好 创建一个副本, 并用它来从不左右移动,所以我们 意外离开,否则我们永远 有一个指针在某些时候是 右边上的列表中的第一个元素。 因此,它是最好创建一个 我们使用移动第二个。 然后,我们只是比较是否 在该节点的值字段 就是我们正在寻找的东西,如果它是 不,我们只是移动到下一个节点。 我们继续这样做, 过来,过来,过来, 直到我们要么找到 元素,或者我们打 null--我们已经走到了尽头 列表,它是不存在的。 这应该有希望打铃 你刚才线性搜索, 我们只是复制它 一个单向链表结构 代替使用一个阵列,以做到这一点。 所以这里有一个例子 一个单向链表。 这其中包括 五个节点,我们有 一个指针的头 列表中,这就是所谓的列表。 我们要做的第一件事就是 再次,创建遍历指针。 所以,我们现在两个指针 这点同样的事情。 现在,请注意这里。此外,我也没 必须对malloc的TRAV任何空间。 我并没有说TRAV等于的malloc 东西时,该节点已经存在, 在内存空间已经存在。 因此,所有我实际上做的是 创建另一个指针。 我不是mallocing额外 空间,只是现在的两个指针 指向同样的事情。 所以是2我在找什么? 哦,不,所以不是我 将移动到下一个。 所以基本上我会说, TRAV等于TRAV旁边。 3我在寻找什么,没有。 所以,我继续走 通过,直到最后 到6这就是我要找 用于基于所述函数调用 我在上面 在那里,所以我做了。 现在,如果元件我什么 寻找的是不在列表中, 难道还要去上班? 好了,注意到列表 这里是微妙的不同, 这是另一件事是 用链表重要的, 不必保留 它们在任何特定的顺序。 你可以,如果你想要的,但 你可能已经注意到了 我们不是跟踪 我们是在什么数量的元素。 这就是那种一笔交易中,我们 有链表节阵列, 难道我们没有 随机访问了。 我们不能只是说,我想 去第0个元素, 或者我的数组的第6元, 我可以在一个阵列做。 我不能说我想去的 第0个元素,或者第6元, 或我的链表25元件, 有没有与之相关的索引。 因此它并不真正的问题 如果我们保留以我们的名单。 如果你想你 当然可以,但有 没有理由,他们需要 以任何顺序被保留。 如此反复,让我们试着 在此列表中发现6。 好了,我们开始在 开始,我们没有发现6, 然后我们继续没有找到 6,直到我们最终到达这里。 所以现在TRAV指向节点 含有8,和六不在那里。 因此,下一步将是 去下一个指针, 所以说TRAV等于TRAV旁边。 好了,接下来TRAV,以表示 红色框出现,为空。 因此,有无处可 走,所以在这一点 我们可以得出结论,我们已经达到 链表的末尾, 和图6是不是在那里。 并且将它返回 假在这种情况下。 好了,我们怎么插入一个新的 节点插入到链表? 因此,我们已经能够创造 链表从哪儿冒出来, 但我们可能要 建立一个链条,而不是 创建一批独特的名单。 我们希望有一列表 有一堆在它的节点, 不是一堆列表与单个节点。 因此,我们不能只是一味地使用Create 功能我们前面定义的,现在我们 要插入到一个 已经存在列表。 所以这种情况下,我们将 传入两个参数, 指针的头部 链表,我们要添加到。 再次,这就是为什么它是如此 重要的是,我们始终 跟踪它,因为 这是我们唯一的办法真的 不得不指整个列表是 刚刚通过的指针的第一个元素。 因此,我们要传递一个 指针,该第一元件, 和任何价值,我们 要添加到列表中。 而最终这个功能 是否会返回一个指针 到链表的新掌门人。 什么是这里涉及的步骤? 好了,就像创建, 我们需要动态分配 一个新的节点空间,并进行检查,以 确保我们不会耗尽内存,再一次, 因为我们使用的malloc。 然后,我们要填充 并插入节点, 所以放多少,什么 val为,到节点。 我们要在插入节点 链表的开头。 还有一个原因是我 要做到这一点,它 可能是值得考虑第二 在这里暂停视频, 想想我为什么会想 在插入一个链接开始 名单。 再次,我前面提到的 它并没有真正 的问题,如果我们在任何保护它 顺序,所以也许这是一个线索。 而你看到的,如果我们会发生什么 想用于:或者只是第二 以前,当我们打算 通过搜索你 可以看到什么可能 发生,如果我们试图 插入在列表的末尾。 因为我们没有一个 指针的列表的末尾。 因此原因,我想 插入开头, 是因为我可以马上做到这一点。 我有一个指针指向开始, 我们将看到这一场视觉在第二。 但是,如果我想插入底, 我要从头开始, 遍历所有的方式向 到底,然后把它钉住。 因此,这将意味着 在列表的末尾插入 将成为n的Ø 操作时,要回 我们的讨论 计算复杂性。 它会变成n操作,其中的邻 作为列表越来越大,大, 大,它会变得越来越 更难以粘性的东西 上在末端。 但它总是很容易 钉东西之初, 你总是在开头。 我们将看到一个可视化的这个了。 然后,一旦我们完成了,一旦 我们插入新的节点, 我们希望我们的指针返回 链表新的头,这 因为我们要插入在 开始,居然会 一个指向我们刚刚创建的节点。 让我们想象这一点, 因为我认为这将帮助。 因此,这里是我们的名单,它由 四个元素,一个节点含有15, 它指向一个节点 含有9,其 指向包含13的节点, 指向包含一个节点 10,它具有空 指针作为其下一个指针 所以这是该列表的末尾。 因此,我们要插入一个 用价值12新节点 在这个初 列表中,我们怎么办? 嗯,首先,我们的malloc空间的 节点,然后我们把12在那里。 所以,现在我们已经到了一个 决策点,对不对? 我们有几个 指针,我们可以 移动,哪一个应该我们搬进去? 我们应该做出12点 列表中 - 新掌门 或不好意思,我们应该让12 指向老首长的名单? 或者我们应该说, 列表现在开始在12。 有一个区别 在那里,我们将看看 在与两国在第二会发生什么。 但是这将导致一个 对于侧边栏很大的话题, 这是一个的 用链表最棘手的事情 被安排指针 以正确的顺序。 如果你搬东西坏了, 你可以结束了意外 孤儿列表的其余部分。 这里是一个很好的例子。 所以,让我们的想法of-- 好了,我们已经创建了12。 我们知道,12将是 列表中的新掌门人, 所以我们为什么不正义之举 该列表指针指向那里。 好了,这是很好的。 所以,现在在那里做12下一个点? 我的意思是,在视觉上我们可以看到 它将指向15, 作为人类,它真的很明显给我们。 计算机如何知道的? 我们没有任何东西 指着15了,对不对? 我们已经失去了任何参考15的能力。 我们不能说新的箭头旁边的equals 什么东西,有什么也没有。 事实上,我们已经成为孤儿 列表的其余 通过这样做,我们已经 不小心打破了链条。 我们当然不希望这样做。 因此,让我们回去再试试这个。 也许做正确的事 是设置12的下一个指针 到旧头部列表的第一, 那么我们可以将名单上。 而事实上,是这样的 正确的顺序我们 需要遵循当我们 正与单向链表。 我们总是希望连接 新元素到列表中, 之前,我们需要的那种 改变的重要一步 其中链表的头。 再次,这是这样一个根本的东西, 我们不想失去它的轨道。 所以我们要确保 一切都链接在一起, 我们继续之前的指针。 所以,这将是正确的顺序, 这是连接12到列表中, 然后说,该清单启动12。 如果我们所说的名单开始在12和 然后试图连接12到列表中, 我们已经看到发生了什么。 我们失去了对列表进行的错误。 好了,还有一件事谈。 如果我们要摆脱什么 整个链表一次? 同样,我们mallocing 这一切的空间,所以我们 需要释放它的时候,我们就大功告成了。 所以,现在我们想删除 整个链表。 那么,我们要怎么办? 如果我们已经达到了空指针,我们 想停下来,否则,只是删除 该列表的其余部分,然后让我自由。 删除列表的其余部分, 然后释放当前节点。 这是什么声音一样, 有什么技术,我们聊 有关以前这听起来像不像? 删除其他人,然后 回来并删除了我。 这是递归的,我们所做的 问题稍微小了一点, 我们说每个人都删除 否则的话,你可以删除我。 而进一步下跌的道路,节点 会说,否则删除每一个人。 但最终,我们会得到的 点的列表为空, 这就是我们的基本情况。 因此,让我们来看看这个, 以及这可能会奏效。 因此,这里是我们的名单,这是相同的 列出我们只是在谈论, 这里面的步骤。 有大量的文字在这里,但 希望可视化将帮助。 因此,我们have--,我还拉 我们的堆栈帧图 从我们的视频调用栈, 并希望这一切 同时会告诉你这是怎么回事。 因此,这里是我们的伪代码。 如果我们到达空 指针,停止,否则, 删除列表的其余部分, 然后释放当前节点。 所以,现在,列表中 - 我们是指针 传递摧毁点至12。 12不是一个空指针,所以我们 要删除列表的其余部分。 什么是删除 我们剩下的参与? 嗯,这意味着制作 呼吁摧毁,说 即图15是的开头 其余的,我们要摧毁名单。 这样一来,呼吁销毁 12是种搁置。 它冻结在那里,等待 呼吁摧毁15,完成其工作。 好了,15不是一个空指针, 所以它会说,没事, 同时,删除列表的其余部分。 列表的其余部分开始 9,所以我们只 等到你删除所有 的东西,然后回来,并删除了我。 那么9会说,好吧, 我不是一个空指针, 所以从这里删除其余的名单。 所以尽量和销毁13。 13说,我不是空指针, 同样的事情,它通过降压。 10不是空指针,10 包含一个空指针, 但10本身不是一个 空指针现在, 因此它通过降压太。 现在列出点那里, 真正将指向some-- 如果我的形象有更多的空间, 它会指向一些随机的空间 我们不知道它是什么。 这是空指针虽然名单 简直是现在设置它的值空。 它指向正确的红色方框内。 我们达到了一个空指针,所以 我们可以停下来,我们就大功告成了。 所以那紫色帧now--在 stack--的顶部是这样的活动框架, 但它的完成。 如果我们已经达到了一个空指针,停止。 我们没有做任何事情,我们 无法释放空指针, 我们没有任何的malloc 空间,所以我们就大功告成了。 这样功能框架 被破坏,并且我们 resume--我们拿起我们离开 关具有下一最高一个,这 这是深蓝色的框在这里。 于是我们拿起身在何方,我们不放过​​。 我们删除的休息 列表了,所以现在我们 要释放当前节点。 所以,现在我们可以免费这个节点,现在 我们已经达到了函数的结束。 而这样的功能框架被破坏, 我们拿起在浅蓝色的。 因此,says--我已经done-- 删除列表的其余部分,所以 释放当前节点。 而现在的黄色框为 回堆栈的顶部。 所以你看,我们现在是 从右破坏列表中离开了。 会发生什么,不过, 如果我们做事情的方法不对? 就像当我们试图 添加元素。 如果我们搞砸链,如果 我们没有连接的指针 以正确的顺序,如果我们 刚刚释放的第一个元素, 如果我们只是释放了 头列表,现在我们 没有办法参考 列表的其余部分。 因此,我们将有 孤立的一切, 我们将不得不什么 所谓的内存泄漏。 如果您从我们的视频回忆 动态内存分配, 这不是很好的事情。 因此,正如我所说, 有几个操作 我们需要用工作 与有效链表。 你可能已经注意到我省略之一, 从链接中删除一个单个元件 名单。 我这样做的原因 是它是一种实际 棘手思考如何删除 从一个单独的单个元件 链表。 我们需要能够跳过 一些在列表中,这 意味着我们得到一个point--我们 要删除这node-- 但为了使其所以我们 不会丢失任何信息, 我们需要连接这 节点在这里,在这里。 所以我大概那个做错了 从视觉角度。 因此,我们在一开始,我们 列表中,我们正在着手通过, 我们要删除此节点。 如果我们只是将其删除, 我们已经打破了链条。 这个节点就在这里 指的是一切, 它包含从这里掉了链子。 因此,我们需要做的其实 之后,我们到了这一点, 是我们需要退一步之一, 在连接这个节点,这个节点, 所以我们可以再删除 一个在中间。 但单链表不 为我们提供了一种倒退。 因此,我们需要可以保持 两个指针,然后将它们移动 一前一后的排序断步骤, 另外,因为我们去,或者到一个地步 然后通过发送另一个指针。 正如你所看到的, 可以变得有些混乱。 幸运的是,我们有 另一种方式来解决, 当我们谈论双向链表。 我是道格·劳埃德,这是CS50。