1 00:00:00,000 --> 00:00:02,994 >> [音乐播放] 2 00:00:02,994 --> 00:00:05,426 3 00:00:05,426 --> 00:00:08,550 道格·劳埃德:所以我们一直在缓慢接近 而接近该数据的圣杯 4 00:00:08,550 --> 00:00:13,050 结构,一个我们可以插入 成,删除,并查找 5 00:00:13,050 --> 00:00:15,440 在固定的时间。 6 00:00:15,440 --> 00:00:16,270 对。 7 00:00:16,270 --> 00:00:17,280 这是排序的目标。 8 00:00:17,280 --> 00:00:19,720 我们希望能够做 事情非常,非常快。 9 00:00:19,720 --> 00:00:22,580 >> 难道我们发现这里的时候, 我们谈论的尝试? 10 00:00:22,580 --> 00:00:23,670 好吧,让我们一起来看看。 11 00:00:23,670 --> 00:00:25,628 因此,我们已经看到一些 不同的数据结构 12 00:00:25,628 --> 00:00:28,680 该处理的映射 所谓键 - 值对, 13 00:00:28,680 --> 00:00:32,080 一些映射数据块 其他一些数据片段 14 00:00:32,080 --> 00:00:36,020 所以我们知道在哪里可以找到 在结构信息。 15 00:00:36,020 --> 00:00:40,060 >> 因此对于阵列,例如,该 关键是该元素索引或阵列 16 00:00:40,060 --> 00:00:42,600 位置0或阵列1等。 17 00:00:42,600 --> 00:00:46,140 和的值是数据 存在在该位置。 18 00:00:46,140 --> 00:00:48,550 那么,什么是存储在阵列0? 19 00:00:48,550 --> 00:00:54,290 什么是存储在阵列1与刚 0和1,这将是键。 20 00:00:54,290 --> 00:00:56,360 >> 利用哈希表是 排序相同的想法。 21 00:00:56,360 --> 00:01:00,690 利用哈希表,我们有这个哈希 函数生成散列码。 22 00:01:00,690 --> 00:01:03,670 所以关键是数据的哈希码。 23 00:01:03,670 --> 00:01:06,530 和的值,特别是 我们谈到链接 24 00:01:06,530 --> 00:01:10,590 在哈希表的视频, 是数据的链表 25 00:01:10,590 --> 00:01:12,550 该散列到哈希码。 26 00:01:12,550 --> 00:01:14,050 对。 27 00:01:14,050 --> 00:01:16,050 那么另一种方法 这种方法有关系吗? 28 00:01:16,050 --> 00:01:21,000 怎么样的方法,其中 键被保证是唯一的, 29 00:01:21,000 --> 00:01:25,410 哈希表,在那里我们可以不像 结了两段数据 30 00:01:25,410 --> 00:01:27,200 具有相同的哈希码。 31 00:01:27,200 --> 00:01:30,020 然后,我们必须处理 通过两种探测以上 32 00:01:30,020 --> 00:01:33,340 最好链接来解决这个问题。 33 00:01:33,340 --> 00:01:37,520 >> 所以,现在我们可以保证 我们的重点将是独一无二的。 34 00:01:37,520 --> 00:01:39,690 如果我们的价值是什么 只是一些容易 35 00:01:39,690 --> 00:01:44,080 作为真假,它告诉我们,无论是 不能说资料片 36 00:01:44,080 --> 00:01:45,610 在结构上存在? 37 00:01:45,610 --> 00:01:48,180 布尔可能是简单的一个位。 38 00:01:48,180 --> 00:01:52,660 现实情况可能是一个 字节不是位的可能性较大。 39 00:01:52,660 --> 00:01:55,410 但是,这是一个很大小于 存储可能是50个字符的字符串, 40 00:01:55,410 --> 00:01:57,360 例如。 41 00:01:57,360 --> 00:02:02,210 >> 所以尝试,类似于哈希表, 其中结合阵列和链表, 42 00:02:02,210 --> 00:02:05,790 尝试结合阵列, 结构,和指针 43 00:02:05,790 --> 00:02:08,509 一起将数据存储在 一个有趣的方式,是 44 00:02:08,509 --> 00:02:11,550 从相当不同 什么我们到目前为止看到的。 45 00:02:11,550 --> 00:02:16,750 现在我们用数据作为路线图 导航这个数据结构。 46 00:02:16,750 --> 00:02:18,710 如果我们可以按照 路线图,如果我们能 47 00:02:18,710 --> 00:02:22,390 按照从数据 自始至终,我们将 48 00:02:22,390 --> 00:02:24,945 知道是该数据 存在于线索。 49 00:02:24,945 --> 00:02:28,310 >> 如果我们不能按照地图 从意味着结束可言, 50 00:02:28,310 --> 00:02:30,600 数据不能存在。 51 00:02:30,600 --> 00:02:32,890 再次,键这里是 保证是唯一的。 52 00:02:32,890 --> 00:02:36,020 所以一个哈希表不同的是,我们永远不会 必须处理的冲突在这里。 53 00:02:36,020 --> 00:02:39,090 并没有两段数据 有完全相同的路线图 54 00:02:39,090 --> 00:02:40,530 除非该数据是相同的。 55 00:02:40,530 --> 00:02:44,580 >> 如果我们插入约翰的话 我们寻找约翰。 56 00:02:44,580 --> 00:02:47,430 这是两个相同的块 数据吧,我们期待通过。 57 00:02:47,430 --> 00:02:49,880 但除此之外,任何 两个数据是 58 00:02:49,880 --> 00:02:52,750 保证有独特的路线图 通过这个数据结构。 59 00:02:52,750 --> 00:02:56,210 而且我们要看看 一会儿就好了一个视觉这一点。 60 00:02:56,210 --> 00:02:58,810 >> 我们将通过努力做到这一点 创建一个新的数据结构, 61 00:02:58,810 --> 00:03:00,564 映射以下键值对。 62 00:03:00,564 --> 00:03:03,480 在这种情况下,我们不打算使用 一些简单的布尔。 63 00:03:03,480 --> 00:03:06,200 实际上,我们将存储字符串。 64 00:03:06,200 --> 00:03:08,690 而该字符串是要 是一所大学的名字。 65 00:03:08,690 --> 00:03:12,140 >> 关键是要在今年 当大学成立。 66 00:03:12,140 --> 00:03:15,380 所有年大学 将要四位数字。 67 00:03:15,380 --> 00:03:19,840 因此,我们将使用这四个数字来 导航通过这个数据结构。 68 00:03:19,840 --> 00:03:22,270 而且我们可以看到,同样,如何 我们这样做,在短短一秒钟。 69 00:03:22,270 --> 00:03:25,110 >> 在路径的末端, 我们将看到名称 70 00:03:25,110 --> 00:03:30,250 对应的大学 到那个键,这四个数字。 71 00:03:30,250 --> 00:03:34,390 后面一个线索的基本思想 就是我们有一个中央的路线。 72 00:03:34,390 --> 00:03:35,640 所以,想想它像一棵树。 73 00:03:35,640 --> 00:03:39,211 这是拼写相似 并在概念上树。 74 00:03:39,211 --> 00:03:41,460 通常,当我们想到 树木在现实世界中, 75 00:03:41,460 --> 00:03:44,090 他们有一个根目录是在 地面和他们向上生长 76 00:03:44,090 --> 00:03:46,830 他们有分支机构 并且他们有叶。 77 00:03:46,830 --> 00:03:49,450 与基本思路 一线索是完全一样的, 78 00:03:49,450 --> 00:03:51,755 除了根锚定 竖立在天空。 79 00:03:51,755 --> 00:03:53,130 和叶子是在底部。 80 00:03:53,130 --> 00:03:55,750 >> 因此,它是一种像服用一棵树 和刚刚翻转倒扣。 81 00:03:55,750 --> 00:03:56,880 但仍有分支。 82 00:03:56,880 --> 00:03:59,463 而这些将是我们的途径, 这些将是我们连接 83 00:03:59,463 --> 00:04:02,220 从根到叶。 84 00:04:02,220 --> 00:04:04,200 在这种情况下,这些 路径,这些分支 85 00:04:04,200 --> 00:04:08,490 贴有告诉我们数字 去从那里我们走哪条路。 86 00:04:08,490 --> 00:04:11,800 >> 如果我们看到一个0,我们再往这个分支, 如果我们看到一个1,我们再往这个分支, 87 00:04:11,800 --> 00:04:12,900 等等。 88 00:04:12,900 --> 00:04:14,060 那么,这是什么意思? 89 00:04:14,060 --> 00:04:16,519 嗯,这意味着, 在每一个结点 90 00:04:16,519 --> 00:04:19,260 和中的每一个节点 中,每一个分支, 91 00:04:19,260 --> 00:04:23,020 有10种可能的 的地方,我们可以走了。 92 00:04:23,020 --> 00:04:27,690 因此,有10球 从每一个位置。 93 00:04:27,690 --> 00:04:30,610 >> 而这正是试图能得到 有点吓人的人 94 00:04:30,610 --> 00:04:34,460 谁是没有很多 在计算机科学之前的经验。 95 00:04:34,460 --> 00:04:35,960 但尝试是真的很漂亮真棒。 96 00:04:35,960 --> 00:04:37,793 如果你有 有机会与他们一起工作 97 00:04:37,793 --> 00:04:40,420 并且你愿意去挖掘,在 并与他们进行试验, 98 00:04:40,420 --> 00:04:44,234 他们真的很有趣 数据结构一起工作。 99 00:04:44,234 --> 00:04:46,900 如果我们要插入元素 到线索,我们需要做的 100 00:04:46,900 --> 00:04:51,360 正在建设的正确道路 从根到叶。 101 00:04:51,360 --> 00:04:55,390 以下是每一步都顺 的方式可能看起来像。 102 00:04:55,390 --> 00:04:59,660 我们要定义一个新的数据 结构为一个新的节点称为线索。 103 00:04:59,660 --> 00:05:02,560 >> 和这些数据的内 结构有两片。 104 00:05:02,560 --> 00:05:05,460 我们要保存 一所大学的名字。 105 00:05:05,460 --> 00:05:09,410 而且我们要存储 指针数组 106 00:05:09,410 --> 00:05:12,190 到相同类型的其他节点。 107 00:05:12,190 --> 00:05:14,780 所以,再一次,这是排序 无处不在的概念 108 00:05:14,780 --> 00:05:18,567 我们是,我们在10个可能的 的地方,我们可以走了。 109 00:05:18,567 --> 00:05:20,150 如果我们看到一个0,我们走上这条分支。 110 00:05:20,150 --> 00:05:22,690 如果我们看到一个1,这个分支, 等等等等等等。 111 00:05:22,690 --> 00:05:25,160 如果说9,我们走上这条分支。 112 00:05:25,160 --> 00:05:28,220 因此,在每一个结点, 我们可以去10个可能的地方。 113 00:05:28,220 --> 00:05:35,740 因此,每个节点必须包含10个三分球 到其他节点,对其他10个节点。 114 00:05:35,740 --> 00:05:39,810 >> 我们要存储的数据是 大学只是名字。 115 00:05:39,810 --> 00:05:41,060 因此,让我们建立一个线索。 116 00:05:41,060 --> 00:05:44,860 让我们插入一对夫妇 的物品进入我们的线索。 117 00:05:44,860 --> 00:05:46,740 因此,在最高层, 这是我们的根节点。 118 00:05:46,740 --> 00:05:49,740 这可能将是什么 你会在全球范围内申报。 119 00:05:49,740 --> 00:05:53,450 而你要在全球范围内保持 一个指向该节点始终。 120 00:05:53,450 --> 00:05:55,360 >> 你会说, 根等于和你 121 00:05:55,360 --> 00:05:57,580 将自己的malloc字典树节点。 122 00:05:57,580 --> 00:05:59,850 而且你永远也不会 再次触及根本。 123 00:05:59,850 --> 00:06:02,300 你想每次 开始导航通过, 124 00:06:02,300 --> 00:06:05,802 您设置另一个指针 等于根,如TRAV, 125 00:06:05,802 --> 00:06:07,760 这是例子,我 在我的很多影片使用 126 00:06:07,760 --> 00:06:11,090 在这里栈和队列 和链接列表等。 127 00:06:11,090 --> 00:06:13,320 >> 您可以设置另一个指针 所谓TRAV遍历。 128 00:06:13,320 --> 00:06:15,890 并使用TRAV导航 通过的数据结构。 129 00:06:15,890 --> 00:06:17,500 因此,让我们看看这个看起来。 130 00:06:17,500 --> 00:06:19,880 所以,现在,是什么 没有一个节点是什么样子? 131 00:06:19,880 --> 00:06:22,920 好了,就像我们的数据 结构声明指出, 132 00:06:22,920 --> 00:06:26,906 我们有一个字符串,它 在这种情况下是空的。 133 00:06:26,906 --> 00:06:27,780 这里没有什么。 134 00:06:27,780 --> 00:06:29,550 >> 和10指针数组。 135 00:06:29,550 --> 00:06:31,790 而现在,我们只 在这个线索1个节点。 136 00:06:31,790 --> 00:06:33,110 还有没有别的它。 137 00:06:33,110 --> 00:06:36,020 因此,所有的10个国家 指针指向为null。 138 00:06:36,020 --> 00:06:38,090 这就是红色表示。 139 00:06:38,090 --> 00:06:39,500 >> 让我们插入字符串哈佛。 140 00:06:39,500 --> 00:06:41,999 让我们插入的大学 哈佛的这个线索,这 141 00:06:41,999 --> 00:06:43,940 始建于1636年。 142 00:06:43,940 --> 00:06:48,220 我们要使用的密钥, 1636年,告诉我们,我们是 143 00:06:48,220 --> 00:06:50,140 将存储在哈佛的线索。 144 00:06:50,140 --> 00:06:51,470 现在,我们如何才能做到这一点? 145 00:06:51,470 --> 00:06:52,886 >> 它可能是这个样子。 146 00:06:52,886 --> 00:06:54,160 我们从根开始。 147 00:06:54,160 --> 00:06:56,920 我们有这10个地方,我们可以走了。 148 00:06:56,920 --> 00:06:59,900 根就像任何 该线索的其他节点。 149 00:06:59,900 --> 00:07:02,850 有10个地方,我们可以从这里走。 150 00:07:02,850 --> 00:07:07,215 >> 我们在哪里可能要 去,如果关键的是1636? 151 00:07:07,215 --> 00:07:08,340 这确实两个选项。 152 00:07:08,340 --> 00:07:08,450 对。 153 00:07:08,450 --> 00:07:10,825 我们可以建立从关键 从右到左,并开始与6。 154 00:07:10,825 --> 00:07:14,000 或者我们可以建立从关键 从左到右,从1开始。 155 00:07:14,000 --> 00:07:16,140 >> 它可能更 直观的作为一个人 156 00:07:16,140 --> 00:07:18,110 了解我们 刚去左到右。 157 00:07:18,110 --> 00:07:21,140 所以,如果我想插入 哈佛的这个线索, 158 00:07:21,140 --> 00:07:23,560 我可能要开始 通过从根开始, 159 00:07:23,560 --> 00:07:25,720 看我10选项 在我面前,说 160 00:07:25,720 --> 00:07:28,700 我想下井1路。 161 00:07:28,700 --> 00:07:29,700 好。 162 00:07:29,700 --> 00:07:31,810 >> 现在,1路目前为空。 163 00:07:31,810 --> 00:07:35,920 所以,如果我想继续沿着这条道路 插入这个元素为线索, 164 00:07:35,920 --> 00:07:42,040 我对malloc一个新的节点,有1 点在那里,然后我好去。 165 00:07:42,040 --> 00:07:46,460 >> 所以我基本上是在 点我站在那里 166 00:07:46,460 --> 00:07:50,270 在树或根 线索并有10个分支机构。 167 00:07:50,270 --> 00:07:52,260 但是,每个分支都有 门在它的前面。 168 00:07:52,260 --> 00:07:53,060 对。 169 00:07:53,060 --> 00:07:54,850 因为没有什么别的有。 170 00:07:54,850 --> 00:07:56,522 没有安全通道。 171 00:07:56,522 --> 00:07:58,980 这意味着什么 下所有的分支。 172 00:07:58,980 --> 00:08:02,532 如果我想开建 什么的,我想删除的大门。 173 00:08:02,532 --> 00:08:04,490 我想删除的门 在1号的前面。 174 00:08:04,490 --> 00:08:05,698 我希望走的。 175 00:08:05,698 --> 00:08:08,060 我想建立 另一个地方,我去。 176 00:08:08,060 --> 00:08:09,470 >> 这就是我在这里所做的。 177 00:08:09,470 --> 00:08:11,430 所以1不再指向空。 178 00:08:11,430 --> 00:08:13,830 我说,这是安全的走下来这里。 179 00:08:13,830 --> 00:08:15,789 我建了另一个节点。 180 00:08:15,789 --> 00:08:18,330 当我到达这个节点,我 有另外的决定。 181 00:08:18,330 --> 00:08:20,890 我要去哪里,从这里去? 182 00:08:20,890 --> 00:08:22,700 >> 好吧,我已经走了下来1。 183 00:08:22,700 --> 00:08:24,470 所以,现在我可能要下井6。 184 00:08:24,470 --> 00:08:24,970 对。 185 00:08:24,970 --> 00:08:27,100 再有,我有10个位置,我可以选择。 186 00:08:27,100 --> 00:08:30,060 现在让我们往下走6号。 187 00:08:30,060 --> 00:08:32,280 所以我清除门 在号码6的前方。 188 00:08:32,280 --> 00:08:33,250 而我走那里。 189 00:08:33,250 --> 00:08:34,580 我建一个节点。 190 00:08:34,580 --> 00:08:37,630 而且我已经达到了另一个结点。 191 00:08:37,630 --> 00:08:40,289 >> 再有,我有10个选择 为在那里我可以走了。 192 00:08:40,289 --> 00:08:42,799 我搬到从1到6。 193 00:08:42,799 --> 00:08:44,215 所以,现在我可能要到3。 194 00:08:44,215 --> 00:08:45,381 3,没有什么地方我可以去。 195 00:08:45,381 --> 00:08:48,980 所以我开道 和自己建​​一个新的空间。 196 00:08:48,980 --> 00:08:50,870 然后再从3,我在哪里要去? 197 00:08:50,870 --> 00:08:52,450 我想下去6。 198 00:08:52,450 --> 00:08:54,770 >> 而且,再一次,我不得不 清除做到这一点的方式。 199 00:08:54,770 --> 00:08:59,179 所以,现在我用我的钥匙插入创建 节点,并开始建立这个线索。 200 00:08:59,179 --> 00:09:00,220 我已经在根开始。 201 00:09:00,220 --> 00:09:03,666 我已经走了下来1636。 202 00:09:03,666 --> 00:09:05,540 现在我在底部 在该节点上存在。 203 00:09:05,540 --> 00:09:06,610 你也许能 看到它在屏幕上。 204 00:09:06,610 --> 00:09:07,735 >> 它以黄色突出显示。 205 00:09:07,735 --> 00:09:10,020 这就是我目前。 206 00:09:10,020 --> 00:09:11,300 我的键完成。 207 00:09:11,300 --> 00:09:13,030 我用尽我的钥匙每个位置上。 208 00:09:13,030 --> 00:09:15,040 因此,我不能再往前走。 209 00:09:15,040 --> 00:09:17,720 因此,在这点上,所有的余 真正需要做的是说好。 210 00:09:17,720 --> 00:09:18,990 那种这就像找 下来在地上, 211 00:09:18,990 --> 00:09:21,115 如果你设想 自己作为这种路径 212 00:09:21,115 --> 00:09:22,350 具有不同的连接。 213 00:09:22,350 --> 00:09:25,800 排序看不起排序和 喷在地面上画哈佛。 214 00:09:25,800 --> 00:09:26,800 这就是此名称。 215 00:09:26,800 --> 00:09:28,300 知道这是什么,在这个位置。 216 00:09:28,300 --> 00:09:31,870 如果我们从根开始,我们下去 1,然后6,然后3,然后6, 217 00:09:31,870 --> 00:09:32,780 我们在哪? 218 00:09:32,780 --> 00:09:35,640 那么,如果我们往下看 我们看到哈佛,然后 219 00:09:35,640 --> 00:09:38,960 我们知道,哈佛 成立于1636年的基础上的方式 220 00:09:38,960 --> 00:09:41,400 我们正在实施这个数据结构。 221 00:09:41,400 --> 00:09:43,177 所以这是希望简单。 222 00:09:43,177 --> 00:09:44,760 我们要做两个插入。 223 00:09:44,760 --> 00:09:50,060 并希望它会帮助 看到这样做的两倍以上。 224 00:09:50,060 --> 00:09:52,210 >> 现在,让我们插入另一所大学。 225 00:09:52,210 --> 00:09:54,630 让我们耶鲁插入到这个线索。 226 00:09:54,630 --> 00:09:57,037 耶鲁大学成立于1701年。 227 00:09:57,037 --> 00:09:58,870 因此,我们将开始在 根,因为我们总是这样。 228 00:09:58,870 --> 00:09:59,890 我们设定一个遍历指针。 229 00:09:59,890 --> 00:10:01,624 我们将用它来移动通过。 230 00:10:01,624 --> 00:10:03,790 我们要的第一件事情 做的是往下走的1路。 231 00:10:03,790 --> 00:10:05,830 这是我们的关键的第一位。 232 00:10:05,830 --> 00:10:08,420 但幸运的是,我们不这样做 做任何工作,这个时候。 233 00:10:08,420 --> 00:10:09,919 1.路径已被清除。 234 00:10:09,919 --> 00:10:13,520 我以前当我清除了 在1636插入哈佛大学。 235 00:10:13,520 --> 00:10:18,090 因此,我可以安全地移动 下来1,只是去那里。 236 00:10:18,090 --> 00:10:20,150 如果能下移1。 237 00:10:20,150 --> 00:10:22,930 >> 但现在,我想去7。 238 00:10:22,930 --> 00:10:24,280 我扫清了道路6。 239 00:10:24,280 --> 00:10:27,050 我知道,我可以放心地 继续向下进行6路径。 240 00:10:27,050 --> 00:10:29,220 但我需要继续在7路径。 241 00:10:29,220 --> 00:10:30,580 那么,我需要做什么? 242 00:10:30,580 --> 00:10:35,070 嗯,就像以前一样,我只需要 清除门,走出去的方式, 243 00:10:35,070 --> 00:10:38,740 并建立从7路一个新的节点。 244 00:10:38,740 --> 00:10:40,250 像这样。 245 00:10:40,250 --> 00:10:42,930 >> 所以,现在我已经搬到1,然后7。 246 00:10:42,930 --> 00:10:45,550 而现在发现,我有点 在这个新的支行。 247 00:10:45,550 --> 00:10:46,050 对。 248 00:10:46,050 --> 00:10:49,260 其他的一切,从16 对,我不关心。 249 00:10:49,260 --> 00:10:50,720 我没有做任何事情16。 250 00:10:50,720 --> 00:10:51,750 我做17的东西。 251 00:10:51,750 --> 00:10:58,380 >> 所以现在17,我要 排序这里开拓创新。 252 00:10:58,380 --> 00:11:00,462 下一个数字我的关键是0。 253 00:11:00,462 --> 00:11:01,670 我显然不能取得任何进展。 254 00:11:01,670 --> 00:11:02,628 我刚刚建立了这个节点。 255 00:11:02,628 --> 00:11:04,550 所以,我知道有没有 路径向前从这里开始。 256 00:11:04,550 --> 00:11:06,370 所以,我必须作出一个自己。 257 00:11:06,370 --> 00:11:09,360 >> 所以,我的malloc一个新的节点 并具有0点出现。 258 00:11:09,360 --> 00:11:12,770 再一次,我的malloc一个 新的节点,并有一个点出现。 259 00:11:12,770 --> 00:11:15,870 再次,我已经用尽了我的钥匙,1701。 260 00:11:15,870 --> 00:11:18,472 所以,我看下来,我喷漆耶鲁。 261 00:11:18,472 --> 00:11:19,680 这是这个节点的名称。 262 00:11:19,680 --> 00:11:24,660 >> 所以,现在如果我以往任何时候都需要的,如果耶鲁看 在这个线索,我从根开始, 263 00:11:24,660 --> 00:11:27,060 我下去1701,往下看。 264 00:11:27,060 --> 00:11:30,030 如果我看到耶鲁喷雾 涂到地面,再 265 00:11:30,030 --> 00:11:32,200 我知道耶鲁存在于这个线索。 266 00:11:32,200 --> 00:11:32,950 让我们做一个。 267 00:11:32,950 --> 00:11:36,430 让我们来达特茅斯插入到这个 特里,这是成立于1769年。 268 00:11:36,430 --> 00:11:37,750 >> 再从根开始。 269 00:11:37,750 --> 00:11:39,445 我的钥匙我的第一个数字是1。 270 00:11:39,445 --> 00:11:40,820 我可以肯定地向下移动,这条道路。 271 00:11:40,820 --> 00:11:42,400 已经存在。 272 00:11:42,400 --> 00:11:44,040 我的钥匙的下一个数字是7。 273 00:11:44,040 --> 00:11:45,890 我可以肯定地向下移动,这条道路。 274 00:11:45,890 --> 00:11:47,540 它的存在也是如此。 275 00:11:47,540 --> 00:11:49,000 >> 我的下一个是6。 276 00:11:49,000 --> 00:11:52,860 从这里,从那里我目前 在这中间节点黄色那里, 277 00:11:52,860 --> 00:11:56,060 6目前被锁定了。 278 00:11:56,060 --> 00:11:58,830 如果我想要走这条路, 我必须建立它自己。 279 00:11:58,830 --> 00:12:02,250 所以,我的malloc一个新的节点 并有6点在那里。 280 00:12:02,250 --> 00:12:04,250 然后,再次,我 在这里开拓创新。 281 00:12:04,250 --> 00:12:10,750 >> 所以,我的malloc一个新的节点,以便从 这node--路径编号9-然后现在 282 00:12:10,750 --> 00:12:13,584 如果我游1769年,我往下看。 283 00:12:13,584 --> 00:12:15,500 没有什么目前 喷漆那里。 284 00:12:15,500 --> 00:12:16,930 我可以写达特茅斯。 285 00:12:16,930 --> 00:12:20,710 我也插 达特茅斯到线索。 286 00:12:20,710 --> 00:12:23,450 >> 所以这是插入 事情到线索。 287 00:12:23,450 --> 00:12:25,384 现在,我们要寻找的东西。 288 00:12:25,384 --> 00:12:27,050 我们如何寻找东西的线索? 289 00:12:27,050 --> 00:12:29,170 嗯,这几乎是同样的想法。 290 00:12:29,170 --> 00:12:33,620 现在我们只是使用的关键数字 看看我们是否能够从根本导航 291 00:12:33,620 --> 00:12:37,170 到我们想去的线索。 292 00:12:37,170 --> 00:12:41,620 >> 如果我们在任何时候进入了死胡同,然后 我们知道,该元件不能存在 293 00:12:41,620 --> 00:12:44,500 否则这条道路会 已经被清除。 294 00:12:44,500 --> 00:12:45,930 如果我们让它一路 最后,我们需要做的 295 00:12:45,930 --> 00:12:48,471 是往下看,看看是否是 我们正在寻找的元素。 296 00:12:48,471 --> 00:12:49,335 如果是,成功。 297 00:12:49,335 --> 00:12:52,610 如果不是的话,失败。 298 00:12:52,610 --> 00:12:54,940 >> 因此,让我们搜索 哈佛大学在这个线索。 299 00:12:54,940 --> 00:12:56,020 我们从根开始。 300 00:12:56,020 --> 00:12:58,228 并再次,我们要 创建一个遍历指针 301 00:12:58,228 --> 00:12:59,390 做我们的动作我们。 302 00:12:59,390 --> 00:13:02,080 从根我们知道 我们需要去第一个地方是1, 303 00:13:02,080 --> 00:13:03,390 我们能做到这一点? 304 00:13:03,390 --> 00:13:03,982 我们可以。 305 00:13:03,982 --> 00:13:04,690 如果安全存在。 306 00:13:04,690 --> 00:13:06,660 我们可以去那里。 307 00:13:06,660 --> 00:13:08,440 >> 现在,我们需要去下一个地方是6。 308 00:13:08,440 --> 00:13:10,557 请问6路从这里存在吗? 309 00:13:10,557 --> 00:13:11,140 是的,确实如此。 310 00:13:11,140 --> 00:13:12,690 我们可以去6个路径。 311 00:13:12,690 --> 00:13:13,905 而我们在这里结束。 312 00:13:13,905 --> 00:13:16,130 >> 我们可以去从这里的3路? 313 00:13:16,130 --> 00:13:18,450 嗯,事实证明, 是的,存在了。 314 00:13:18,450 --> 00:13:20,790 而且我们可以得到从这里的6路? 315 00:13:20,790 --> 00:13:21,982 我们可以。 316 00:13:21,982 --> 00:13:24,002 >> 我们还没有完全回答 这个问题呢。 317 00:13:24,002 --> 00:13:25,710 但还有一个更 步骤,这是现在 318 00:13:25,710 --> 00:13:28,520 我们需要往下看, 看看这actually-- 319 00:13:28,520 --> 00:13:32,660 如果我们要寻找的哈佛大学,是 我们发现后,我们用尽了钥匙吗? 320 00:13:32,660 --> 00:13:35,430 在这个例子中,我们使用的是在这里, 这些年来始终是四位数字。 321 00:13:35,430 --> 00:13:40,280 但是,你可能会使用的例子, 你是存储单词的词典。 322 00:13:40,280 --> 00:13:44,060 >> 因此,而不是具有10个三分球 我的位置,你可能有26。 323 00:13:44,060 --> 00:13:46,040 一个用于每个字母。 324 00:13:46,040 --> 00:13:50,350 还有一些话像蝙蝠, 这是批量的一个子集,例如。 325 00:13:50,350 --> 00:13:53,511 所以,即使你到了 关键的结束,你看下来, 326 00:13:53,511 --> 00:13:55,260 你可能不会看到什么 你正在寻找。 327 00:13:55,260 --> 00:13:58,500 >> 所以,你总是要遍历 整个路径,然后 328 00:13:58,500 --> 00:14:01,540 如果你能够成功 遍历整个路径, 329 00:14:01,540 --> 00:14:03,440 往下看,做一个最后的确认。 330 00:14:03,440 --> 00:14:05,120 那是我在找什么? 331 00:14:05,120 --> 00:14:07,740 好吧,我开始后往下看 在顶部和去1636。 332 00:14:07,740 --> 00:14:08,240 我往下看。 333 00:14:08,240 --> 00:14:09,400 我看到哈佛。 334 00:14:09,400 --> 00:14:11,689 所以,是的,我成功了。 335 00:14:11,689 --> 00:14:13,980 如果什么什么我在寻找 是不是在线索,虽然。 336 00:14:13,980 --> 00:14:17,200 如果我在寻找普林斯顿, 该公司成立于1746年。 337 00:14:17,200 --> 00:14:20,875 所以,1746成为我的钥匙 浏览该线索。 338 00:14:20,875 --> 00:14:22,040 好吧,我从根开始。 339 00:14:22,040 --> 00:14:24,760 我希望首位 到下山的1路。 340 00:14:24,760 --> 00:14:25,590 我能做到吗? 341 00:14:25,590 --> 00:14:26,490 我可以。 342 00:14:26,490 --> 00:14:28,730 >> 我可以下去从那里的7路? 343 00:14:28,730 --> 00:14:29,230 是的,我可以。 344 00:14:29,230 --> 00:14:30,750 存在了。 345 00:14:30,750 --> 00:14:32,460 但我可以去​​从这里的4路? 346 00:14:32,460 --> 00:14:35,550 这就像问一个问题,就可以 我继续向下的小广场 347 00:14:35,550 --> 00:14:37,114 我在黄已经强调? 348 00:14:37,114 --> 00:14:38,030 有什么也没有。 349 00:14:38,030 --> 00:14:38,610 对。 350 00:14:38,610 --> 00:14:41,310 >> 有没有办法前进下来的4路。 351 00:14:41,310 --> 00:14:46,480 如果普林斯顿在这个线索,即4 已被清除我们了。 352 00:14:46,480 --> 00:14:49,130 因此在这一点上 我们已经到了一个死胡同。 353 00:14:49,130 --> 00:14:50,250 我们不能再往前走。 354 00:14:50,250 --> 00:14:53,440 因此,我们可以说,明确,没有。 355 00:14:53,440 --> 00:14:56,760 普林斯顿并不在此线索存在。 356 00:14:56,760 --> 00:14:58,860 >> 那么,这意味着什么? 357 00:14:58,860 --> 00:14:59,360 对。 358 00:14:59,360 --> 00:15:01,000 有很多怎么回事。 359 00:15:01,000 --> 00:15:02,500 有指针所有的地方。 360 00:15:02,500 --> 00:15:04,249 而且,正如你所看到的 刚刚从图中, 361 00:15:04,249 --> 00:15:07,010 有很多节点的 都是那种飞来飞去。 362 00:15:07,010 --> 00:15:13,480 但是请注意,每次我们想时间 检查东西是否是在特里, 363 00:15:13,480 --> 00:15:15,000 我们只有使4举动。 364 00:15:15,000 --> 00:15:17,208 >> 我们希望每一次 在线索中插入一些东西, 365 00:15:17,208 --> 00:15:20,440 我们必须做出4的动作,有可能 mallocing沿途的一些东西。 366 00:15:20,440 --> 00:15:23,482 但正如我们看到的,当我们插入 达特茅斯到线索, 367 00:15:23,482 --> 00:15:25,940 有时一些路径的 可能已经被清除了我们。 368 00:15:25,940 --> 00:15:30,520 所以作为我们的线索变得更大, 更大,我们有充分的时间少做工作 369 00:15:30,520 --> 00:15:32,270 插入新事物 因为我们已把 370 00:15:32,270 --> 00:15:35,746 内置了很多中间的 沿途分支。 371 00:15:35,746 --> 00:15:38,370 如果我们永远只能来看看 4东西,4仅仅是一个常数。 372 00:15:38,370 --> 00:15:41,750 那种我们确实正在接近 恒定的时间插入 373 00:15:41,750 --> 00:15:44,501 和恒定的时间查找。 374 00:15:44,501 --> 00:15:47,500 权衡,当然,在于 这个线索,因为你可能会说, 375 00:15:47,500 --> 00:15:49,030 是巨大的。 376 00:15:49,030 --> 00:15:51,040 这些节点中的每一个 占用了大量的空间。 377 00:15:51,040 --> 00:15:52,090 >> 但是,这是权衡。 378 00:15:52,090 --> 00:15:55,260 如果我们要真正快速 插入,真的很快删除, 379 00:15:55,260 --> 00:15:59,630 真正快速查找,我们要 有大量的数据到处乱飞。 380 00:15:59,630 --> 00:16:03,590 我们必须预留了很大的空间 和存储器,用于该数据结构 381 00:16:03,590 --> 00:16:04,290 存在。 382 00:16:04,290 --> 00:16:05,415 >> 所以这就是权衡。 383 00:16:05,415 --> 00:16:07,310 但看起来我们 可能已经找到了它。 384 00:16:07,310 --> 00:16:09,560 我们可能会发现, 数据结构的圣杯 385 00:16:09,560 --> 00:16:12,264 与快速插入, 缺失和查找。 386 00:16:12,264 --> 00:16:14,430 也许这将是一个 合适的数据结构 387 00:16:14,430 --> 00:16:18,890 用于任何信息 我们试图店。 388 00:16:18,890 --> 00:16:21,860 我是道格·劳埃德,这是CS50。 389 00:16:21,860 --> 00:16:23,433