1
00:00:00,000 --> 00:00:02,832
>> [音乐播放]

2
00:00:02,832 --> 00:00:05,670

3
00:00:05,670 --> 00:00:08,560
>> DOUG LLOYD：好，因此在
这一点在使用过程中，

4
00:00:08,560 --> 00:00:15,300
我们已经介绍了很多C的基础知识
我们知道了很多关于变量，数组，

5
00:00:15,300 --> 00:00:17,610
指针，所有的好东西。

6
00:00:17,610 --> 00:00:21,610
排序的所有这些都是建立
在看到的基本面，

7
00:00:21,610 --> 00:00:23,880
但我们可以做更多的，对不对？

8
00:00:23,880 --> 00:00:27,930
我们可以结合东西
一起以有趣的方式。

9
00:00:27,930 --> 00:00:31,010
>> 因此，让我们做的是，让我们开始
另辟蹊径的什么C给我们，

10
00:00:31,010 --> 00:00:35,270
并开始创建自己的数据
利用这些建筑结构

11
00:00:35,270 --> 00:00:40,590
块一起做一些事情
真正有价值的，有用的。

12
00:00:40,590 --> 00:00:43,420
我们能做到这一点的方法之一是
谈收藏。

13
00:00:43,420 --> 00:00:48,360
因此，到目前为止，我们已经有某一种数据
结构较集合

14
00:00:48,360 --> 00:00:51,030
对喜欢价值观，相似的价值观。

15
00:00:51,030 --> 00:00:52,350
这将是一个数组。

16
00:00:52,350 --> 00:00:57,020
我们有一个整数集合或
字符等的集合。

17
00:00:57,020 --> 00:01:00,890
>> 的结构也进行排序数据的
结构收集信息，

18
00:01:00,890 --> 00:01:03,220
但它不是用来收集类似的值。

19
00:01:03,220 --> 00:01:08,090
它通常混合了不同的数据类型
一起在单一盒子。

20
00:01:08,090 --> 00:01:10,750
但它本身并不是
用于链接在一起

21
00:01:10,750 --> 00:01:16,920
或者连接到一起类似
项，如一个数组。

22
00:01:16,920 --> 00:01:20,960
数组是伟大的
元素查找，但召回

23
00:01:20,960 --> 00:01:24,262
这是非常困难
插入到一个数组，

24
00:01:24,262 --> 00:01:26,470
除非我们插入的
该数组的末尾。

25
00:01:26,470 --> 00:01:29,730
>> 而最好的例子，我有
因为这是插入排序。

26
00:01:29,730 --> 00:01:31,650
如果你还记得我们的视频
在插入排序，

27
00:01:31,650 --> 00:01:34,110
有很多的
参与其费用

28
00:01:34,110 --> 00:01:37,970
拿起元素，将它们转移
出适合的东西的方式

29
00:01:37,970 --> 00:01:41,290
成阵列的中间。

30
00:01:41,290 --> 00:01:44,690
阵列也从另一个患
问题，这是不灵活。

31
00:01:44,690 --> 00:01:47,150
当我们声明一个数组，
我们这一次机会吧。

32
00:01:47,150 --> 00:01:49,790
我们得到的说法，我想
这些元素。

33
00:01:49,790 --> 00:01:51,940
可能是100，它可能
是1000，它可能

34
00:01:51,940 --> 00:01:55,930
是x，其中x是一个数字，用户
给了我们一个提示，或在命令

35
00:01:55,930 --> 00:01:56,630
行。

36
00:01:56,630 --> 00:01:59,905
>> 但是，我们只有一次机会吧，我们
没有得到，然后说，哦，其实我

37
00:01:59,905 --> 00:02:04,360
需要101，或者我需要X加20。

38
00:02:04,360 --> 00:02:07,910
太晚了，我们已经宣布了
数组，如果我们想要获得101或x

39
00:02:07,910 --> 00:02:12,050
加上20，我们要声明
一个完全不同的阵列，

40
00:02:12,050 --> 00:02:15,540
复制数组中的所有元素
过来，然后我们有足够。

41
00:02:15,540 --> 00:02:19,880
而如果我们又错了，是什么
如果我们真的需要102或x加40，

42
00:02:19,880 --> 00:02:21,970
我们要再次做到这一点。

43
00:02:21,970 --> 00:02:26,250
因此，他们非常不灵活
对于调整我们的数据，

44
00:02:26,250 --> 00:02:29,360
但如果我们结合在一起的一些
我们已经已经基本知识

45
00:02:29,360 --> 00:02:33,230
了解指针和结构，
特别是使用动态存储

46
00:02:33,230 --> 00:02:36,180
分配使用malloc，我们
可以把这些碎片拼凑起来

47
00:02:36,180 --> 00:02:40,960
创建一个新的数据结构 - 一个
单链表，我们可能say--

48
00:02:40,960 --> 00:02:45,400
这使我们能够成长，
收缩值的集合

49
00:02:45,400 --> 00:02:48,800
我们不会有任何浪费的空间。

50
00:02:48,800 --> 00:02:53,320
>> 所以，再一次，我们称这样的想法，
这个概念，一个链表。

51
00:02:53,320 --> 00:02:56,320
特别是，在这个视频我们
谈到单向链表，

52
00:02:56,320 --> 00:02:59,185
然后另一个视频中，我们将讨论
关于双向链表，这

53
00:02:59,185 --> 00:03:01,560
只是在这里一个主题的变化。

54
00:03:01,560 --> 00:03:05,200
但一个单向链表
由节点，

55
00:03:05,200 --> 00:03:08,559
节点仅仅是一个抽象的term--
这只是一些我打电话

56
00:03:08,559 --> 00:03:10,350
这是一种
结构，基本上，我？

57
00:03:10,350 --> 00:03:16,190
只是要称之为node--，这
节点具有两个构件，或两个字段。

58
00:03:16,190 --> 00:03:20,300
它的数据，通常是一个
整数，字符浮子，

59
00:03:20,300 --> 00:03:23,790
或者可以是某种其他数据类型
您已经定义了类型定义。

60
00:03:23,790 --> 00:03:29,290
它包含一个指向
相同类型的另一节点。

61
00:03:29,290 --> 00:03:34,710
>> 因此，我们有两件事情里面
这个节点，数据和指针

62
00:03:34,710 --> 00:03:36,380
到另一个节点。

63
00:03:36,380 --> 00:03:39,370
如果你开始显现
这一点，你可以考虑一下

64
00:03:39,370 --> 00:03:42,280
像链节点的那
连接在一起。

65
00:03:42,280 --> 00:03:45,070
我们的第一个节点，它
包含数据，和一个指针

66
00:03:45,070 --> 00:03:49,110
到第二个节点，其中包含
数据，和一个指针到该第三节点。

67
00:03:49,110 --> 00:03:52,940
所以这就是为什么我们称它为
链接列表，它们链接在一起。

68
00:03:52,940 --> 00:03:56,070
>> 这是什么特别的
节点结构是什么样子？

69
00:03:56,070 --> 00:04:01,120
好吧，如果你从我们的视频回忆
定义自定义类型，类型高清，

70
00:04:01,120 --> 00:04:05,400
我们可以定义一个结构 - 和
键入这样定义的结构。

71
00:04:05,400 --> 00:04:11,240
tyepdef结构sllist，然后我
使用这个词的价值在这里随意

72
00:04:11,240 --> 00:04:13,891
以指示真的任何数据类型。

73
00:04:13,891 --> 00:04:16,890
你可以传递一个整数或浮点数，
你可以有一切你想要的。

74
00:04:16,890 --> 00:04:19,389
它不再仅仅限于
整数，或者类似的东西。

75
00:04:19,389 --> 00:04:22,790
因此，值是任意
数据类型，然后一个指针

76
00:04:22,790 --> 00:04:26,310
到同一类型的另一节点。

77
00:04:26,310 --> 00:04:29,690
>> 现在，有一个小抓
这里定义的结构

78
00:04:29,690 --> 00:04:33,030
当它是一个自我参照结构。

79
00:04:33,030 --> 00:04:35,340
我必须有一个临时的
命名为我的结构。

80
00:04:35,340 --> 00:04:37,640
在这一天我的结束
显然想将它命名

81
00:04:37,640 --> 00:04:43,030
SLL节点，这是最终的新
名字我喜欢的类型定义的一部分，

82
00:04:43,030 --> 00:04:47,450
但我不能使用SLL节点
在这中间。

83
00:04:47,450 --> 00:04:51,430
是的原因，我没有
创建了一个名为类型SLL节点

84
00:04:51,430 --> 00:04:55,200
直到我在这里打这个最后一点。

85
00:04:55,200 --> 00:04:59,720
直到这一点，我必须有
另一种方式来参考此数据类型。

86
00:04:59,720 --> 00:05:02,440
>> 而这是一个自
参照数据类型。

87
00:05:02,440 --> 00:05:06,314
它; S的一个数据类型
结构，它包含一个数据，

88
00:05:06,314 --> 00:05:08,480
和一个指针到另一个
相同类型的结构。

89
00:05:08,480 --> 00:05:11,750
所以，我需要能够引用
这种数据类型至少暂时

90
00:05:11,750 --> 00:05:14,910
所以给它一个暂时的
结构sllist名

91
00:05:14,910 --> 00:05:18,540
让我那么说我想要一个
指向另一个结构sllist，

92
00:05:18,540 --> 00:05:24,690
一个结构sllist明星，然后
我已经完成了定义后，

93
00:05:24,690 --> 00:05:27,220
我现在可以把这种类型的SLL节点。

94
00:05:27,220 --> 00:05:30,520
>> 所以这就是为什么你看到有
一个临时的名字在这里，

95
00:05:30,520 --> 00:05:31,879
但这里的永久名字。

96
00:05:31,879 --> 00:05:33,920
有时候，你可能会看到
结构的定义，

97
00:05:33,920 --> 00:05:36,570
例如，是不
自我指涉，是

98
00:05:36,570 --> 00:05:39,390
没有说明的名字在这里。

99
00:05:39,390 --> 00:05:43,040
它只想说typedef结构，
打开大括号，然后定义它。

100
00:05:43,040 --> 00:05:45,620
但是，如果你是结构是自
引用，因为这个人是，

101
00:05:45,620 --> 00:05:49,010
你需要指定一个
临时类型名称。

102
00:05:49,010 --> 00:05:51,310
但最终，现在
我们已经做到了这一点，

103
00:05:51,310 --> 00:05:53,620
我们只能参考
这些节点，这些单位，

104
00:05:53,620 --> 00:05:57,900
作为目的SLL节点
这段视频的其余部分。

105
00:05:57,900 --> 00:06:00,900
>> 好吧，让我们知道如何
创建一个链接列表节点。

106
00:06:00,900 --> 00:06:03,240
我们知道如何定义
一个链接列表节点。

107
00:06:03,240 --> 00:06:06,670
现在，如果我们要开始
用它们来收集信息，

108
00:06:06,670 --> 00:06:10,360
有一对夫妇经营的我们
需要了解和使用。

109
00:06:10,360 --> 00:06:12,860
我们需要知道如何创建
链表凭空。

110
00:06:12,860 --> 00:06:14,901
如果没有清单已经，
我们要开始的。

111
00:06:14,901 --> 00:06:16,960
因此，我们需要能够
以创建一个链表，

112
00:06:16,960 --> 00:06:19,130
我们需要大概搜索
通过链接列表

113
00:06:19,130 --> 00:06:21,830
找到我们正在寻找的元素。

114
00:06:21,830 --> 00:06:24,430
我们需要的是能够插入
新事物进入榜单，

115
00:06:24,430 --> 00:06:25,930
我们希望我们的名单能够成长。

116
00:06:25,930 --> 00:06:28,638
同样，我们希望能够
从我们的名单中删除的东西，

117
00:06:28,638 --> 00:06:30,250
我们希望我们的名单，以便能够收缩。

118
00:06:30,250 --> 00:06:32,160
而在年底我们
计划，特别是

119
00:06:32,160 --> 00:06:34,550
如果你还记得，我们是
动态分配内存

120
00:06:34,550 --> 00:06:38,337
以通常建这些列表，
我们要释放所有的内存

121
00:06:38,337 --> 00:06:39,670
当我们用它做的工作。

122
00:06:39,670 --> 00:06:44,627
因此，我们需要能够删除一个
整个链表在​​一个失败的一举。

123
00:06:44,627 --> 00:06:46,460
因此，让我们通过
某些操作

124
00:06:46,460 --> 00:06:51,192
和我们怎样才能使其可视化，
在伪代码说话特别。

125
00:06:51,192 --> 00:06:53,150
因此，我们要创建一个
链表，所以也许我们

126
00:06:53,150 --> 00:06:56,480
要定义一个函数
这个原型。

127
00:06:56,480 --> 00:07:01,690
SLL节点明星，创造，而我路过
在一个参数，一些任意数据

128
00:07:01,690 --> 00:07:05,530
再次键入某些任意数据类型的，。

129
00:07:05,530 --> 00:07:10,482
但是我returning--这个功能应该
还给我一个指针，以一个单

130
00:07:10,482 --> 00:07:11,190
链接列表节点。

131
00:07:11,190 --> 00:07:14,050
同样，我们正在努力创造
链表凭空，

132
00:07:14,050 --> 00:07:17,900
所以我需要一个指针
当我做了该名单。

133
00:07:17,900 --> 00:07:19,420
>> 那么，什么是这里涉及的步骤？

134
00:07:19,420 --> 00:07:20,960
好了，第一件事我
要做的是动态

135
00:07:20,960 --> 00:07:22,550
分配空间用于新的节点。

136
00:07:22,550 --> 00:07:26,689
同样，我们正在创造出来的薄
空气中，所以我们需要为它的malloc空间。

137
00:07:26,689 --> 00:07:28,480
当然，马上
我们的malloc后，

138
00:07:28,480 --> 00:07:31,692
我们经常检查，以确保我们的
pointer--我们没有得到回空。

139
00:07:31,692 --> 00:07:33,650
因为如果我们尝试
尊重一个空指针，

140
00:07:33,650 --> 00:07:36,190
我们要遭受
段错误，我们不希望出现这种情况。

141
00:07:36,190 --> 00:07:39,510
>> 然后，我们要填补该领域，
我们要初始化值字段

142
00:07:39,510 --> 00:07:41,690
并初始化下一字段。

143
00:07:41,690 --> 00:07:45,450
然后我们想用于：最终的
函数原型indicates--我们要

144
00:07:45,450 --> 00:07:49,940
的指针返回到SLL节点。

145
00:07:49,940 --> 00:07:51,710
那么是什么让这个样子视觉？

146
00:07:51,710 --> 00:07:55,230
嗯，首先我们要动态地
分配空间用于新SLL节点，

147
00:07:55,230 --> 00:07:58,320
所以我们malloc--这
视觉表示

148
00:07:58,320 --> 00:08:00,020
节点，我们刚刚创建。

149
00:08:00,020 --> 00:08:02,757
我们检查，以确保
它不是null--在这种情况下，

150
00:08:02,757 --> 00:08:04,840
画面不会有
示，如果它为空，

151
00:08:04,840 --> 00:08:07,298
我们会耗尽内存，
所以我们好去那里。

152
00:08:07,298 --> 00:08:10,200
所以，现在我们是在步骤C，
初始化节点值字段。

153
00:08:10,200 --> 00:08:12,280
那么，在此基础上功能
叫我用在这里，

154
00:08:12,280 --> 00:08:16,700
貌似我想通过在6，
所以我会在值字段6。

155
00:08:16,700 --> 00:08:18,865
现在，初始化下一个字段。

156
00:08:18,865 --> 00:08:21,640
好了，我该怎么办那里，
旁边有个什么吧，

157
00:08:21,640 --> 00:08:23,600
这是在列表中的唯一事情。

158
00:08:23,600 --> 00:08:27,206
那么什么是列表中，接下来的事情？

159
00:08:27,206 --> 00:08:29,660
>> 它不应该指向什么，对吧。

160
00:08:29,660 --> 00:08:33,600
还有没有别的那里，所以有什么
我们知道，这一概念的nothing--

161
00:08:33,600 --> 00:08:35,638
指向什么？

162
00:08:35,638 --> 00:08:37,929
它应该是，也许我们要
把一个空指针出现，

163
00:08:37,929 --> 00:08:40,178
我会代表空
指针只是一个红盒子，

164
00:08:40,178 --> 00:08:41,559
我们不能再往前走。

165
00:08:41,559 --> 00:08:44,430
正如我们将看到一个小以后，
我们将有最终链

166
00:08:44,430 --> 00:08:46,330
箭头连接
这些节点一起，

167
00:08:46,330 --> 00:08:48,480
但是当你打的
红色的框，这就是空，

168
00:08:48,480 --> 00:08:51,150
我们不能再往前走，
这是该列表的末尾。

169
00:08:51,150 --> 00:08:53,960
>> 最后，我们只是想
返回一个指向该节点。

170
00:08:53,960 --> 00:08:56,160
因此，我们会打电话给它新的，
并返回新

171
00:08:56,160 --> 00:08:59,370
因此它可被用
无论函数创建它。

172
00:08:59,370 --> 00:09:03,100
所以我们去，我们已经创建了一个单
链表节点无中生有，

173
00:09:03,100 --> 00:09:05,920
现在我们有了一个可以使用的列表。

174
00:09:05,920 --> 00:09:08,260
>> 现在，让我们说，我们已经
有大型连锁，

175
00:09:08,260 --> 00:09:09,800
我们要找到的东西在里面。

176
00:09:09,800 --> 00:09:12,716
我们希望有一个功能是怎么回事
返回true或false，这取决于

177
00:09:12,716 --> 00:09:15,840
在该列表中是否存在某个值。

178
00:09:15,840 --> 00:09:18,160
函数原型，或
声明该函数，

179
00:09:18,160 --> 00:09:23,320
可能看起来像this-- BOOL发现，和
那么我们想传递的两个参数。

180
00:09:23,320 --> 00:09:26,996
>> 第一，是一个指针，指向
该链接的表的第一个元素。

181
00:09:26,996 --> 00:09:29,620
这实际上是你会
总想跟踪，

182
00:09:29,620 --> 00:09:33,110
实际上可能是东西，
你甚至放在一个全局变量。

183
00:09:33,110 --> 00:09:35,360
一旦你创建一个列表，
你永远，永远

184
00:09:35,360 --> 00:09:38,990
要保持的非常轨迹
列表的第一个元素。

185
00:09:38,990 --> 00:09:43,690
这样，你可以参考其他所有
只是简单地跟着链条元素，

186
00:09:43,690 --> 00:09:47,300
无需保持指针
完整的每一个元素。

187
00:09:47,300 --> 00:09:50,920
你只需要跟踪第一
一个，如果他们都链接在一起。

188
00:09:50,920 --> 00:09:52,460
>> 然后是第二件事
我们传递再次

189
00:09:52,460 --> 00:09:54,376
是任意some--
我们的任何数据类型

190
00:09:54,376 --> 00:09:59,640
寻找有内
希望列表中的节点之一。

191
00:09:59,640 --> 00:10:00,980
那么哪些步骤？

192
00:10:00,980 --> 00:10:04,250
好了，我们做的第一件事是
我们创建了一个横向的指针

193
00:10:04,250 --> 00:10:06,015
指向列表头部。

194
00:10:06,015 --> 00:10:08,890
那么，为什么我们这样做，我们已经
有一个指针在表头，

195
00:10:08,890 --> 00:10:10,974
为什么我们不只是移动了一绕？

196
00:10:10,974 --> 00:10:13,140
嗯，就像我刚才说的，
这对我们来说真的很重要

197
00:10:13,140 --> 00:10:17,580
要始终保持轨道的
列表中的第一个元素。

198
00:10:17,580 --> 00:10:21,270
所以它实际上更好
创建一个副本，

199
00:10:21,270 --> 00:10:25,350
并用它来从不左右移动，所以我们
意外离开，否则我们永远

200
00:10:25,350 --> 00:10:30,430
有一个指针在某些时候是
右边上的列表中的第一个元素。

201
00:10:30,430 --> 00:10:33,290
因此，它是最好创建一个
我们使用移动第二个。

202
00:10:33,290 --> 00:10:35,877
>> 然后，我们只是比较是否
在该节点的值字段

203
00:10:35,877 --> 00:10:38,960
就是我们正在寻找的东西，如果它是
不，我们只是移动到下一个节点。

204
00:10:38,960 --> 00:10:41,040
我们继续这样做，
过来，过来，过来，

205
00:10:41,040 --> 00:10:44,811
直到我们要么找到
元素，或者我们打

206
00:10:44,811 --> 00:10:47,310
null--我们已经走到了尽头
列表，它是不存在的。

207
00:10:47,310 --> 00:10:50,540
这应该有希望打铃
你刚才线性搜索，

208
00:10:50,540 --> 00:10:54,430
我们只是复制它
一个单向链表结构

209
00:10:54,430 --> 00:10:56,280
代替使用一个阵列，以做到这一点。

210
00:10:56,280 --> 00:10:58,210
>> 所以这里有一个例子
一个单向链表。

211
00:10:58,210 --> 00:11:00,043
这其中包括
五个节点，我们有

212
00:11:00,043 --> 00:11:04,330
一个指针的头
列表中，这就是所谓的列表。

213
00:11:04,330 --> 00:11:07,385
我们要做的第一件事就是
再次，创建遍历指针。

214
00:11:07,385 --> 00:11:09,760
所以，我们现在两个指针
这点同样的事情。

215
00:11:09,760 --> 00:11:15,025
>> 现在，请注意这里。此外，我也没
必须对malloc的TRAV任何空间。

216
00:11:15,025 --> 00:11:18,970
我并没有说TRAV等于的malloc
东西时，该节点已经存在，

217
00:11:18,970 --> 00:11:21,160
在内存空间已经存在。

218
00:11:21,160 --> 00:11:24,290
因此，所有我实际上做的是
创建另一个指针。

219
00:11:24,290 --> 00:11:28,210
我不是mallocing额外
空间，只是现在的两个指针

220
00:11:28,210 --> 00:11:31,370
指向同样的事情。

221
00:11:31,370 --> 00:11:33,710
>> 所以是2我在找什么？

222
00:11:33,710 --> 00:11:37,220
哦，不，所以不是我
将移动到下一个。

223
00:11:37,220 --> 00:11:41,740
所以基本上我会说，
TRAV等于TRAV旁边。

224
00:11:41,740 --> 00:11:43,630
3我在寻找什么，没有。

225
00:11:43,630 --> 00:11:45,780
所以，我继续走
通过，直到最后

226
00:11:45,780 --> 00:11:48,690
到6这就是我要找
用于基于所述函数调用

227
00:11:48,690 --> 00:11:51,600
我在上面
在那里，所以我做了。

228
00:11:51,600 --> 00:11:54,150
>> 现在，如果元件我什么
寻找的是不在列表中，

229
00:11:54,150 --> 00:11:55,510
难道还要去上班？

230
00:11:55,510 --> 00:11:57,120
好了，注意到列表
这里是微妙的不同，

231
00:11:57,120 --> 00:11:59,410
这是另一件事是
用链表重要的，

232
00:11:59,410 --> 00:12:01,780
不必保留
它们在任何特定的顺序。

233
00:12:01,780 --> 00:12:05,390
你可以，如果你想要的，但
你可能已经注意到了

234
00:12:05,390 --> 00:12:09,310
我们不是跟踪
我们是在什么数量的元素。

235
00:12:09,310 --> 00:12:13,150
>> 这就是那种一笔交易中，我们
有链表节阵列，

236
00:12:13,150 --> 00:12:15,300
难道我们没有
随机访问了。

237
00:12:15,300 --> 00:12:18,150
我们不能只是说，我想
去第0个元素，

238
00:12:18,150 --> 00:12:21,410
或者我的数组的第6元，
我可以在一个阵列做。

239
00:12:21,410 --> 00:12:25,080
我不能说我想去的
第0个元素，或者第6元，

240
00:12:25,080 --> 00:12:30,360
或我的链表25元件，
有没有与之相关的索引。

241
00:12:30,360 --> 00:12:33,660
因此它并不真正的问题
如果我们保留以我们的名单。

242
00:12:33,660 --> 00:12:36,080
如果你想你
当然可以，但有

243
00:12:36,080 --> 00:12:38,567
没有理由，他们需要
以任何顺序被保留。

244
00:12:38,567 --> 00:12:40,400
如此反复，让我们试着
在此列表中发现6。

245
00:12:40,400 --> 00:12:43,200
好了，我们开始在
开始，我们没有发现6，

246
00:12:43,200 --> 00:12:47,690
然后我们继续没有找到
6，直到我们最终到达这里。

247
00:12:47,690 --> 00:12:52,790
所以现在TRAV指向节点
含有8，和六不在那里。

248
00:12:52,790 --> 00:12:55,250
>> 因此，下一步将是
去下一个指针，

249
00:12:55,250 --> 00:12:57,440
所以说TRAV等于TRAV旁边。

250
00:12:57,440 --> 00:13:00,750
好了，接下来TRAV，以表示
红色框出现，为空。

251
00:13:00,750 --> 00:13:03,020
因此，有无处可
走，所以在这一点

252
00:13:03,020 --> 00:13:06,120
我们可以得出结论，我们已经达到
链表的末尾，

253
00:13:06,120 --> 00:13:07,190
和图6是不是在那里。

254
00:13:07,190 --> 00:13:10,980
并且将它返回
假在这种情况下。

255
00:13:10,980 --> 00:13:14,540
>> 好了，我们怎么插入一个新的
节点插入到链表？

256
00:13:14,540 --> 00:13:17,310
因此，我们已经能够创造
链表从哪儿冒出来，

257
00:13:17,310 --> 00:13:19,370
但我们可能要
建立一个链条，而不是

258
00:13:19,370 --> 00:13:22,620
创建一批独特的名单。

259
00:13:22,620 --> 00:13:25,700
我们希望有一列表
有一堆在它的节点，

260
00:13:25,700 --> 00:13:28,040
不是一堆列表与单个节点。

261
00:13:28,040 --> 00:13:31,260
因此，我们不能只是一味地使用Create
功能我们前面定义的，现在我们

262
00:13:31,260 --> 00:13:33,860
要插入到一个
已经存在列表。

263
00:13:33,860 --> 00:13:36,499
>> 所以这种情况下，我们将
传入两个参数，

264
00:13:36,499 --> 00:13:39,290
指针的头部
链表，我们要添加到。

265
00:13:39,290 --> 00:13:40,910
再次，这就是为什么它是如此
重要的是，我们始终

266
00:13:40,910 --> 00:13:43,400
跟踪它，因为
这是我们唯一的办法真的

267
00:13:43,400 --> 00:13:46,690
不得不指整个列表是
刚刚通过的指针的第一个元素。

268
00:13:46,690 --> 00:13:49,360
因此，我们要传递一个
指针，该第一元件，

269
00:13:49,360 --> 00:13:52,226
和任何价值，我们
要添加到列表中。

270
00:13:52,226 --> 00:13:54,600
而最终这个功能
是否会返回一个指针

271
00:13:54,600 --> 00:13:57,980
到链表的新掌门人。

272
00:13:57,980 --> 00:13:59,700
>> 什么是这里涉及的步骤？

273
00:13:59,700 --> 00:14:02,249
好了，就像创建，
我们需要动态分配

274
00:14:02,249 --> 00:14:05,540
一个新的节点空间，并进行检查，以
确保我们不会耗尽内存，再一次，

275
00:14:05,540 --> 00:14:07,150
因为我们使用的malloc。

276
00:14:07,150 --> 00:14:09,080
然后，我们要填充
并插入节点，

277
00:14:09,080 --> 00:14:12,730
所以放多少，什么
val为，到节点。

278
00:14:12,730 --> 00:14:17,310
我们要在插入节点
链表的开头。

279
00:14:17,310 --> 00:14:19,619
>> 还有一个原因是我
要做到这一点，它

280
00:14:19,619 --> 00:14:21,910
可能是值得考虑第二
在这里暂停视频，

281
00:14:21,910 --> 00:14:25,860
想想我为什么会想
在插入一个链接开始

282
00:14:25,860 --> 00:14:26,589
名单。

283
00:14:26,589 --> 00:14:28,630
再次，我前面提到的
它并没有真正

284
00:14:28,630 --> 00:14:33,020
的问题，如果我们在任何保护它
顺序，所以也许这是一个线索。

285
00:14:33,020 --> 00:14:36,040
而你看到的，如果我们会发生什么
想用于：或者只是第二

286
00:14:36,040 --> 00:14:37,360
以前，当我们打算
通过搜索你

287
00:14:37,360 --> 00:14:39,235
可以看到什么可能
发生，如果我们试图

288
00:14:39,235 --> 00:14:41,330
插入在列表的末尾。

289
00:14:41,330 --> 00:14:44,750
因为我们没有一个
指针的列表的末尾。

290
00:14:44,750 --> 00:14:47,490
>> 因此原因，我想
插入开头，

291
00:14:47,490 --> 00:14:49,380
是因为我可以马上做到这一点。

292
00:14:49,380 --> 00:14:52,730
我有一个指针指向开始，
我们将看到这一场视觉在第二。

293
00:14:52,730 --> 00:14:55,605
但是，如果我想插入底，
我要从头开始，

294
00:14:55,605 --> 00:14:58,760
遍历所有的方式向
到底，然后把它钉住。

295
00:14:58,760 --> 00:15:01,420
因此，这将意味着
在列表的末尾插入

296
00:15:01,420 --> 00:15:04,140
将成为n的Ø
操作时，要回

297
00:15:04,140 --> 00:15:06,720
我们的讨论
计算复杂性。

298
00:15:06,720 --> 00:15:10,140
它会变成n操作，其中的邻
作为列表越来越大，大，

299
00:15:10,140 --> 00:15:13,310
大，它会变得越来越
更难以粘性的东西

300
00:15:13,310 --> 00:15:14,661
上在末端。

301
00:15:14,661 --> 00:15:17,410
但它总是很容易
钉东西之初，

302
00:15:17,410 --> 00:15:19,060
你总是在开头。

303
00:15:19,060 --> 00:15:21,620
>> 我们将看到一个可视化的这个了。

304
00:15:21,620 --> 00:15:24,100
然后，一旦我们完成了，一旦
我们插入新的节点，

305
00:15:24,100 --> 00:15:26,880
我们希望我们的指针返回
链表新的头，这

306
00:15:26,880 --> 00:15:29,213
因为我们要插入在
开始，居然会

307
00:15:29,213 --> 00:15:31,060
一个指向我们刚刚创建的节点。

308
00:15:31,060 --> 00:15:33,280
让我们想象这一点，
因为我认为这将帮助。

309
00:15:33,280 --> 00:15:36,661
>> 因此，这里是我们的名单，它由
四个元素，一个节点含有15，

310
00:15:36,661 --> 00:15:38,410
它指向一个节点
含有9，其

311
00:15:38,410 --> 00:15:41,370
指向包含13的节点，
指向包含一个节点

312
00:15:41,370 --> 00:15:44,840
10，它具有空
指针作为其下一个指针

313
00:15:44,840 --> 00:15:47,010
所以这是该列表的末尾。

314
00:15:47,010 --> 00:15:50,200
因此，我们要插入一个
用价值12新节点

315
00:15:50,200 --> 00:15:52,720
在这个初
列表中，我们怎么办？

316
00:15:52,720 --> 00:15:58,770
嗯，首先，我们的malloc空间的
节点，然后我们把12在那里。

317
00:15:58,770 --> 00:16:02,211
>> 所以，现在我们已经到了一个
决策点，对不对？

318
00:16:02,211 --> 00:16:03,960
我们有几个
指针，我们可以

319
00:16:03,960 --> 00:16:06,770
移动，哪一个应该我们搬进去？

320
00:16:06,770 --> 00:16:09,250
我们应该做出12点
列表中 - 新掌门

321
00:16:09,250 --> 00:16:13,020
或不好意思，我们应该让12
指向老首长的名单？

322
00:16:13,020 --> 00:16:15,319
或者我们应该说，
列表现在开始在12。

323
00:16:15,319 --> 00:16:17,110
有一个区别
在那里，我们将看看

324
00:16:17,110 --> 00:16:19,870
在与两国在第二会发生什么。

325
00:16:19,870 --> 00:16:23,350
>> 但是这将导致一个
对于侧边栏很大的话题，

326
00:16:23,350 --> 00:16:26,280
这是一个的
用链表最棘手的事情

327
00:16:26,280 --> 00:16:30,980
被安排指针
以正确的顺序。

328
00:16:30,980 --> 00:16:34,520
如果你搬东西坏了，
你可以结束了意外

329
00:16:34,520 --> 00:16:36,050
孤儿列表的其余部分。

330
00:16:36,050 --> 00:16:37,300
这里是一个很好的例子。

331
00:16:37,300 --> 00:16:40,540
所以，让我们的想法of--
好了，我们已经创建了12。

332
00:16:40,540 --> 00:16:43,180
我们知道，12将是
列表中的新掌门人，

333
00:16:43,180 --> 00:16:47,660
所以我们为什么不正义之举
该列表指针指向那里。

334
00:16:47,660 --> 00:16:49,070
>> 好了，这是很好的。

335
00:16:49,070 --> 00:16:51,560
所以，现在在那里做12下一个点？

336
00:16:51,560 --> 00:16:54,580
我的意思是，在视觉上我们可以看到
它将指向15，

337
00:16:54,580 --> 00:16:57,250
作为人类，它真的很明显给我们。

338
00:16:57,250 --> 00:17:00,300
计算机如何知道的？

339
00:17:00,300 --> 00:17:02,720
我们没有任何东西
指着15了，对不对？

340
00:17:02,720 --> 00:17:05,869
>> 我们已经失去了任何参考15的能力。

341
00:17:05,869 --> 00:17:11,460
我们不能说新的箭头旁边的equals
什么东西，有什么也没有。

342
00:17:11,460 --> 00:17:13,510
事实上，我们已经成为孤儿
列表的其余

343
00:17:13,510 --> 00:17:16,465
通过这样做，我们已经
不小心打破了链条。

344
00:17:16,465 --> 00:17:18,089
我们当然不希望这样做。

345
00:17:18,089 --> 00:17:20,000
>> 因此，让我们回去再试试这个。

346
00:17:20,000 --> 00:17:24,060
也许做正确的事
是设置12的下一个指针

347
00:17:24,060 --> 00:17:28,290
到旧头部列表的第一，
那么我们可以将名单上。

348
00:17:28,290 --> 00:17:30,420
而事实上，是这样的
正确的顺序我们

349
00:17:30,420 --> 00:17:32,836
需要遵循当我们
正与单向链表。

350
00:17:32,836 --> 00:17:36,460
我们总是希望连接
新元素到列表中，

351
00:17:36,460 --> 00:17:41,010
之前，我们需要的那种
改变的重要一步

352
00:17:41,010 --> 00:17:43,360
其中链表的头。

353
00:17:43,360 --> 00:17:46,740
再次，这是这样一个根本的东西，
我们不想失去它的轨道。

354
00:17:46,740 --> 00:17:49,310
>> 所以我们要确保
一切都链接在一起，

355
00:17:49,310 --> 00:17:52,040
我们继续之前的指针。

356
00:17:52,040 --> 00:17:55,300
所以，这将是正确的顺序，
这是连接12到列表中，

357
00:17:55,300 --> 00:17:57,630
然后说，该清单启动12。

358
00:17:57,630 --> 00:18:00,860
如果我们所说的名单开始在12和
然后试图连接12到列表中，

359
00:18:00,860 --> 00:18:02,193
我们已经看到发生了什么。

360
00:18:02,193 --> 00:18:04,920
我们失去了对列表进行的错误。

361
00:18:04,920 --> 00:18:06,740
>> 好了，还有一件事谈。

362
00:18:06,740 --> 00:18:09,750
如果我们要摆脱什么
整个链表一次？

363
00:18:09,750 --> 00:18:11,750
同样，我们mallocing
这一切的空间，所以我们

364
00:18:11,750 --> 00:18:13,351
需要释放它的时候，我们就大功告成了。

365
00:18:13,351 --> 00:18:15,350
所以，现在我们想删除
整个链表。

366
00:18:15,350 --> 00:18:16,850
那么，我们要怎么办？

367
00:18:16,850 --> 00:18:20,460
>> 如果我们已经达到了空指针，我们
想停下来，否则，只是删除

368
00:18:20,460 --> 00:18:23,420
该列表的其余部分，然后让我自由。

369
00:18:23,420 --> 00:18:28,890
删除列表的其余部分，
然后释放当前节点。

370
00:18:28,890 --> 00:18:32,850
这是什么声音一样，
有什么技术，我们聊

371
00:18:32,850 --> 00:18:35,440
有关以前这听起来像不像？

372
00:18:35,440 --> 00:18:39,560
删除其他人，然后
回来并删除了我。

373
00:18:39,560 --> 00:18:42,380
>> 这是递归的，我们所做的
问题稍微小了一点，

374
00:18:42,380 --> 00:18:46,910
我们说每个人都删除
否则的话，你可以删除我。

375
00:18:46,910 --> 00:18:50,940
而进一步下跌的道路，节点
会说，否则删除每一个人。

376
00:18:50,940 --> 00:18:53,940
但最终，我们会得到的
点的列表为空，

377
00:18:53,940 --> 00:18:55,310
这就是我们的基本情况。

378
00:18:55,310 --> 00:18:57,010
>> 因此，让我们来看看这个，
以及这可能会奏效。

379
00:18:57,010 --> 00:18:59,759
因此，这里是我们的名单，这是相同的
列出我们只是在谈论，

380
00:18:59,759 --> 00:19:00,980
这里面的步骤。

381
00:19:00,980 --> 00:19:04,200
有大量的文字在这里，但
希望可视化将帮助。

382
00:19:04,200 --> 00:19:08,557
>> 因此，我们have--，我还拉
我们的堆栈帧图

383
00:19:08,557 --> 00:19:10,890
从我们的视频调用栈，
并希望这一切

384
00:19:10,890 --> 00:19:13,260
同时会告诉你这是怎么回事。

385
00:19:13,260 --> 00:19:14,510
因此，这里是我们的伪代码。

386
00:19:14,510 --> 00:19:17,830
如果我们到达空
指针，停止，否则，

387
00:19:17,830 --> 00:19:21,320
删除列表的其余部分，
然后释放当前节点。

388
00:19:21,320 --> 00:19:25,700
所以，现在，列表中 - 
我们是指针

389
00:19:25,700 --> 00:19:28,410
传递摧毁点至12。

390
00:19:28,410 --> 00:19:33,340
12不是一个空指针，所以我们
要删除列表的其余部分。

391
00:19:33,340 --> 00:19:35,450
>> 什么是删除
我们剩下的参与？

392
00:19:35,450 --> 00:19:37,950
嗯，这意味着制作
呼吁摧毁，说

393
00:19:37,950 --> 00:19:42,060
即图15是的开头
其余的，我们要摧毁名单。

394
00:19:42,060 --> 00:19:47,480
这样一来，呼吁销毁
12是种搁置。

395
00:19:47,480 --> 00:19:52,690
它冻结在那里，等待
呼吁摧毁15，完成其工作。

396
00:19:52,690 --> 00:19:56,280
>> 好了，15不是一个空指针，
所以它会说，没事，

397
00:19:56,280 --> 00:19:58,450
同时，删除列表的其余部分。

398
00:19:58,450 --> 00:20:00,760
列表的其余部分开始
9，所以我们只

399
00:20:00,760 --> 00:20:04,514
等到你删除所有
的东西，然后回来，并删除了我。

400
00:20:04,514 --> 00:20:06,680
那么9会说，好吧，
我不是一个空指针，

401
00:20:06,680 --> 00:20:09,020
所以从这里删除其余的名单。

402
00:20:09,020 --> 00:20:11,805
所以尽量和销毁13。

403
00:20:11,805 --> 00:20:15,550
13说，我不是空指针，
同样的事情，它通过降压。

404
00:20:15,550 --> 00:20:17,930
10不是空指针，10
包含一个空指针，

405
00:20:17,930 --> 00:20:20,200
但10本身不是一个
空指针现在，

406
00:20:20,200 --> 00:20:22,470
因此它通过降压太。

407
00:20:22,470 --> 00:20:25,560
>> 现在列出点那里，
真正将指向some--

408
00:20:25,560 --> 00:20:28,710
如果我的形象有更多的空间，
它会指向一些随机的空间

409
00:20:28,710 --> 00:20:29,960
我们不知道它是什么。

410
00:20:29,960 --> 00:20:34,680
这是空指针虽然名单
简直是现在设置它的值空。

411
00:20:34,680 --> 00:20:36,820
它指向正确的红色方框内。

412
00:20:36,820 --> 00:20:39,960
我们达到了一个空指针，所以
我们可以停下来，我们就大功告成了。

413
00:20:39,960 --> 00:20:46,230
>> 所以那紫色帧now--在
stack--的顶部是这样的活动框架，

414
00:20:46,230 --> 00:20:47,017
但它的完成。

415
00:20:47,017 --> 00:20:48,600
如果我们已经达到了一个空指针，停止。

416
00:20:48,600 --> 00:20:51,290
我们没有做任何事情，我们
无法释放空指针，

417
00:20:51,290 --> 00:20:55,070
我们没有任何的malloc
空间，所以我们就大功告成了。

418
00:20:55,070 --> 00:20:57,590
这样功能框架
被破坏，并且我们

419
00:20:57,590 --> 00:21:00,930
resume--我们拿起我们离开
关具有下一最高一个，这

420
00:21:00,930 --> 00:21:02,807
这是深蓝色的框在这里。

421
00:21:02,807 --> 00:21:04,390
于是我们拿起身在何方，我们不放过​​。

422
00:21:04,390 --> 00:21:06,598
我们删除的休息
列表了，所以现在我们

423
00:21:06,598 --> 00:21:08,000
要释放当前节点。

424
00:21:08,000 --> 00:21:12,920
所以，现在我们可以免费这个节点，现在
我们已经达到了函数的结束。

425
00:21:12,920 --> 00:21:16,810
而这样的功能框架被破坏，
我们拿起在浅蓝色的。

426
00:21:16,810 --> 00:21:20,650
>> 因此，says--我已经done--
删除列表的其余部分，所以

427
00:21:20,650 --> 00:21:23,140
释放当前节点。

428
00:21:23,140 --> 00:21:26,520
而现在的黄色框为
回堆栈的顶部。

429
00:21:26,520 --> 00:21:29,655
所以你看，我们现在是
从右破坏列表中离开了。

430
00:21:29,655 --> 00:21:33,710

431
00:21:33,710 --> 00:21:37,280
>> 会发生什么，不过，
如果我们做事情的方法不对？

432
00:21:37,280 --> 00:21:39,410
就像当我们试图
添加元素。

433
00:21:39,410 --> 00:21:41,909
如果我们搞砸链，如果
我们没有连接的指针

434
00:21:41,909 --> 00:21:44,690
以正确的顺序，如果我们
刚刚释放的第一个元素，

435
00:21:44,690 --> 00:21:47,420
如果我们只是释放了
头列表，现在我们

436
00:21:47,420 --> 00:21:49,642
没有办法参考
列表的其余部分。

437
00:21:49,642 --> 00:21:51,350
因此，我们将有
孤立的一切，

438
00:21:51,350 --> 00:21:53,880
我们将不得不什么
所谓的内存泄漏。

439
00:21:53,880 --> 00:21:56,800
如果您从我们的视频回忆
动态内存分配，

440
00:21:56,800 --> 00:21:58,650
这不是很好的事情。

441
00:21:58,650 --> 00:22:00,810
>> 因此，正如我所说，
有几个操作

442
00:22:00,810 --> 00:22:04,010
我们需要用工作
与有效链表。

443
00:22:04,010 --> 00:22:08,430
你可能已经注意到我省略之一，
从链接中删除一个单个元件

444
00:22:08,430 --> 00:22:09,064
名单。

445
00:22:09,064 --> 00:22:10,980
我这样做的原因
是它是一种实际

446
00:22:10,980 --> 00:22:14,360
棘手思考如何删除
从一个单独的单个元件

447
00:22:14,360 --> 00:22:15,600
链表。

448
00:22:15,600 --> 00:22:19,950
我们需要能够跳过
一些在列表中，这

449
00:22:19,950 --> 00:22:22,975
意味着我们得到一个point--我们
要删除这node--

450
00:22:22,975 --> 00:22:25,350
但为了使其所以我们
不会丢失任何信息，

451
00:22:25,350 --> 00:22:30,530
我们需要连接这
节点在这里，在这里。

452
00:22:30,530 --> 00:22:33,390
>> 所以我大概那个做错了
从视觉角度。

453
00:22:33,390 --> 00:22:36,830
因此，我们在一开始，我们
列表中，我们正在着手通过，

454
00:22:36,830 --> 00:22:40,510
我们要删除此节点。

455
00:22:40,510 --> 00:22:43,440
如果我们只是将其删除，
我们已经打破了链条。

456
00:22:43,440 --> 00:22:45,950
这个节点就在这里
指的是一切，

457
00:22:45,950 --> 00:22:48,260
它包含从这里掉了链子。

458
00:22:48,260 --> 00:22:51,190
>> 因此，我们需要做的其实
之后，我们到了这一点，

459
00:22:51,190 --> 00:22:56,670
是我们需要退一步之一，
在连接这个节点，这个节点，

460
00:22:56,670 --> 00:22:58,590
所以我们可以再删除
一个在中间。

461
00:22:58,590 --> 00:23:02,120
但单链表不
为我们提供了一种倒退。

462
00:23:02,120 --> 00:23:05,160
因此，我们需要可以保持
两个指针，然后将它们移动

463
00:23:05,160 --> 00:23:09,527
一前一后的排序断步骤，
另外，因为我们去，或者到一个地步

464
00:23:09,527 --> 00:23:11,110
然后通过发送另一个指针。

465
00:23:11,110 --> 00:23:13,150
正如你所看到的，
可以变得有些混乱。

466
00:23:13,150 --> 00:23:15,360
幸运的是，我们有
另一种方式来解决，

467
00:23:15,360 --> 00:23:17,810
当我们谈论双向链表。

468
00:23:17,810 --> 00:23:20,720
>> 我是道格·劳埃德，这是CS50。

469
00:23:20,720 --> 00:23:22,298