1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] Trong lập trình, chúng ta thường cần để đại diện cho danh sách các giá trị,

2
00:00:10,050 --> 00:00:12,840
chẳng hạn như tên của học sinh trong phần một

3
00:00:12,840 --> 00:00:15,100
hoặc điểm trên bài kiểm tra mới nhất.

4
00:00:15,100 --> 00:00:17,430
>> Trong ngôn ngữ C, tuyên bố mảng có thể được sử dụng

5
00:00:17,430 --> 00:00:19,160
để lưu trữ danh sách.

6
00:00:19,160 --> 00:00:21,200
Thật dễ dàng để liệt kê các yếu tố của một danh sách

7
00:00:21,200 --> 00:00:23,390
lưu trữ trong một mảng, và nếu bạn cần truy cập

8
00:00:23,390 --> 00:00:25,050
hoặc sửa đổi danh sách các yếu tố thứ i

9
00:00:25,050 --> 00:00:27,570
đối với một số chỉ số tùy ý,

10
00:00:27,570 --> 00:00:29,910
mà có thể được thực hiện trong thời gian liên tục,

11
00:00:29,910 --> 00:00:31,660
nhưng mảng có nhược điểm, quá.

12
00:00:31,660 --> 00:00:33,850
>> Khi chúng ta tuyên bố chúng, chúng ta cần phải nói

13
00:00:33,850 --> 00:00:35,900
lên phía trước họ là lớn như thế nào,

14
00:00:35,900 --> 00:00:38,160
có nghĩa là, họ có thể lưu trữ nhiều yếu tố

15
00:00:38,160 --> 00:00:40,780
và làm thế nào lớn những yếu tố này, được xác định bởi kiểu của họ.

16
00:00:40,780 --> 00:00:45,450
Ví dụ, int arr (10)

17
00:00:45,450 --> 00:00:48,220
có thể lưu trữ 10 bản ghi

18
00:00:48,220 --> 00:00:50,200
có kích thước của một int.

19
00:00:50,200 --> 00:00:52,590
>> Chúng ta không thể thay đổi kích thước của một mảng sau khi khai báo.

20
00:00:52,590 --> 00:00:55,290
Chúng ta phải thực hiện một mảng mới nếu chúng ta muốn lưu trữ nhiều yếu tố.

21
00:00:55,290 --> 00:00:57,410
Lý do hạn chế này tồn tại là chúng tôi

22
00:00:57,410 --> 00:00:59,040
chương trình lưu trữ toàn bộ mảng

23
00:00:59,040 --> 00:01:02,310
như là một đoạn tiếp giáp của bộ nhớ.

24
00:01:02,310 --> 00:01:04,500
Nói đây là bộ đệm mà chúng tôi lưu trữ trong mảng của chúng tôi.

25
00:01:04,500 --> 00:01:06,910
Có thể có các biến số khác

26
00:01:06,910 --> 00:01:08,310
nằm ngay bên cạnh các mảng

27
00:01:08,310 --> 00:01:10,060
trong bộ nhớ, do đó, chúng ta không thể

28
00:01:10,060 --> 00:01:12,060
chỉ cần thực hiện các mảng lớn hơn.

29
00:01:12,060 --> 00:01:15,700
>> Đôi khi chúng tôi muốn thương mại tốc độ nhanh chóng truy cập dữ liệu của mảng

30
00:01:15,700 --> 00:01:17,650
cho một ít linh hoạt hơn.

31
00:01:17,650 --> 00:01:20,380
Nhập danh sách liên kết, một cấu trúc dữ liệu cơ bản

32
00:01:20,380 --> 00:01:22,360
bạn có thể không quen thuộc với.

33
00:01:22,360 --> 00:01:24,200
Ở mức độ cao,

34
00:01:24,200 --> 00:01:26,840
một danh sách liên kết lưu trữ dữ liệu trong một chuỗi các nút

35
00:01:26,840 --> 00:01:29,280
được kết nối với nhau với các liên kết,

36
00:01:29,280 --> 00:01:31,760
vì thế cái tên "danh sách liên kết.

37
00:01:31,760 --> 00:01:33,840
Như chúng ta sẽ thấy, sự khác biệt trong thiết kế

38
00:01:33,840 --> 00:01:35,500
dẫn đến lợi thế và nhược điểm khác nhau

39
00:01:35,500 --> 00:01:37,000
hơn một mảng.

40
00:01:37,000 --> 00:01:39,840
>> Dưới đây là một số mã C cho một danh sách liên kết rất đơn giản các số nguyên.

41
00:01:39,840 --> 00:01:42,190
Bạn có thể thấy rằng chúng tôi đã đại diện cho mỗi nút

42
00:01:42,190 --> 00:01:45,520
trong danh sách như là một cấu trúc, trong đó có 2 điều,

43
00:01:45,520 --> 00:01:47,280
một số nguyên để lưu trữ được gọi là 'val'

44
00:01:47,280 --> 00:01:50,460
và một liên kết đến nút tiếp theo trong danh sách

45
00:01:50,460 --> 00:01:52,990
mà chúng tôi đại diện như một con trỏ được gọi là 'bên cạnh.'

46
00:01:54,120 --> 00:01:56,780
Bằng cách này, chúng ta có thể theo dõi toàn bộ danh sách

47
00:01:56,780 --> 00:01:58,790
với chỉ duy nhất một con trỏ đến nút 1,

48
00:01:58,790 --> 00:02:01,270
và sau đó chúng ta có thể thực hiện theo các con trỏ tiếp theo

49
00:02:01,270 --> 00:02:03,130
đến nút thứ 2,

50
00:02:03,130 --> 00:02:05,280
nút thứ 3,

51
00:02:05,280 --> 00:02:07,000
nút thứ 4,

52
00:02:07,000 --> 00:02:09,889
và như vậy, cho đến khi chúng tôi nhận được đến cuối của danh sách.

53
00:02:10,520 --> 00:02:12,210
>> Bạn có thể có thể thấy được 1 lợi thế này có

54
00:02:12,210 --> 00:02:14,490
trên cấu trúc mảng tĩnh với một danh sách liên kết,

55
00:02:14,490 --> 00:02:16,450
chúng ta không cần một đoạn lớn của bộ nhớ hoàn toàn.

56
00:02:17,400 --> 00:02:20,530
Nút 1 của danh sách có thể sống tại nơi này trong bộ nhớ,

57
00:02:20,530 --> 00:02:23,160
và nút thứ 2 có thể là tất cả các cách trên đây.

58
00:02:23,160 --> 00:02:25,780
Chúng tôi có thể nhận được tất cả các nút không có vấn đề trong bộ nhớ,

59
00:02:25,780 --> 00:02:28,890
bởi vì bắt đầu tại nút 1, con trỏ tiếp theo mỗi nút

60
00:02:28,890 --> 00:02:31,700
cho chúng ta biết chính xác nơi để đi tiếp theo.

61
00:02:31,700 --> 00:02:33,670
>> Ngoài ra, chúng tôi không cần phải nói lên phía trước

62
00:02:33,670 --> 00:02:36,740
một danh sách liên kết lớn như thế nào sẽ là cách chúng tôi làm với mảng tĩnh,

63
00:02:36,740 --> 00:02:39,060
kể từ khi chúng tôi có thể tiếp tục thêm các nút vào một danh sách

64
00:02:39,060 --> 00:02:42,600
miễn là có không gian một nơi nào đó trong bộ nhớ cho các nút mới.

65
00:02:42,600 --> 00:02:45,370
Do đó, danh sách liên kết dễ dàng để thay đổi kích thước tự động.

66
00:02:45,370 --> 00:02:47,950
Nói, trong chương trình chúng ta cần thêm các nút hơn

67
00:02:47,950 --> 00:02:49,350
vào danh sách của chúng tôi.

68
00:02:49,350 --> 00:02:51,480
Để chèn một nút mới vào danh sách của chúng tôi trên bay,

69
00:02:51,480 --> 00:02:53,740
tất cả chúng ta phải làm là cấp phát bộ nhớ cho nút đó,

70
00:02:53,740 --> 00:02:55,630
tiếng tom trong giá trị dữ liệu,

71
00:02:55,630 --> 00:02:59,070
và sau đó đặt nó mà chúng tôi muốn bằng cách điều chỉnh con trỏ thích hợp.

72
00:02:59,070 --> 00:03:02,310
>> Ví dụ, nếu chúng ta muốn đặt một nút ở giữa

73
00:03:02,310 --> 00:03:04,020
thứ 2 và 3 nút của danh sách,

74
00:03:04,020 --> 00:03:06,800
 chúng ta sẽ không phải di chuyển các nút 2 hoặc 3 ở tất cả.

75
00:03:06,800 --> 00:03:09,190
Nói rằng chúng tôi đang chèn nút này màu đỏ.

76
00:03:09,190 --> 00:03:12,890
Tất cả những gì chúng ta phải làm là đặt con trỏ tới các nút mới

77
00:03:12,890 --> 00:03:14,870
để trỏ đến nút thứ 3

78
00:03:14,870 --> 00:03:18,580
và sau đó ReWire con trỏ tới nút thứ 2

79
00:03:18,580 --> 00:03:20,980
để trỏ đến nút mới của chúng tôi.

80
00:03:22,340 --> 00:03:24,370
Vì vậy, chúng ta có thể thay đổi kích thước danh sách của chúng tôi trên bay

81
00:03:24,370 --> 00:03:26,090
kể từ khi máy tính của chúng tôi không dựa vào chỉ mục,

82
00:03:26,090 --> 00:03:28,990
mà thay vào liên kết sử dụng con trỏ để lưu trữ chúng.

83
00:03:29,120 --> 00:03:31,600
>> Tuy nhiên, một bất lợi của danh sách liên kết

84
00:03:31,600 --> 00:03:33,370
là, không giống như một mảng tĩnh,

85
00:03:33,370 --> 00:03:36,690
máy tính có thể không chỉ nhảy đến giữa của danh sách.

86
00:03:38,040 --> 00:03:40,780
Kể từ khi máy tính có truy cập mỗi nút trong danh sách liên kết

87
00:03:40,780 --> 00:03:42,330
để có được đến kế tiếp,

88
00:03:42,330 --> 00:03:44,770
nó sẽ mất nhiều thời gian hơn để tìm thấy một nút cụ thể

89
00:03:44,770 --> 00:03:46,400
hơn nó sẽ trong một mảng.

90
00:03:46,400 --> 00:03:48,660
Để đi qua toàn bộ danh sách cần có thời gian tỷ lệ thuận

91
00:03:48,660 --> 00:03:50,580
với chiều dài của danh sách,

92
00:03:50,580 --> 00:03:54,630
hoặc O (n) trong ký hiệu tiệm cận.

93
00:03:54,630 --> 00:03:56,510
Tính trung bình, đạt bất kỳ nút

94
00:03:56,510 --> 00:03:58,800
cũng cần có thời gian tỷ lệ thuận với n.

95
00:03:58,800 --> 00:04:00,700
>> Bây giờ, hãy viết một số mã

96
00:04:00,700 --> 00:04:02,000
làm việc với các danh sách liên kết.

97
00:04:02,000 --> 00:04:04,220
Hãy nói rằng chúng tôi muốn có một danh sách liên kết các số nguyên.

98
00:04:04,220 --> 00:04:06,140
Chúng tôi có thể đại diện cho một nút trong danh sách của chúng tôi một lần nữa

99
00:04:06,140 --> 00:04:08,340
như là một cấu trúc với 2 lĩnh vực,

100
00:04:08,340 --> 00:04:10,750
một giá trị số nguyên được gọi là 'val'

101
00:04:10,750 --> 00:04:13,490
và một con trỏ đến nút tiếp theo của danh sách.

102
00:04:13,490 --> 00:04:15,660
Vâng, có vẻ đơn giản.

103
00:04:15,660 --> 00:04:17,220
>> Hãy nói rằng chúng ta muốn viết một chức năng

104
00:04:17,220 --> 00:04:19,329
đi qua danh sách và in ra

105
00:04:19,329 --> 00:04:22,150
giá trị được lưu trữ trong các nút cuối cùng của danh sách.

106
00:04:22,150 --> 00:04:24,850
Vâng, điều đó có nghĩa là chúng tôi sẽ cần phải đi qua tất cả các nút trong danh sách

107
00:04:24,850 --> 00:04:27,310
để tìm người cuối cùng, nhưng vì chúng tôi không thêm

108
00:04:27,310 --> 00:04:29,250
hoặc xóa bất cứ điều gì, chúng tôi không muốn thay đổi

109
00:04:29,250 --> 00:04:32,210
cấu trúc nội bộ của các con trỏ tiếp theo trong danh sách.

110
00:04:32,210 --> 00:04:34,790
>> Vì vậy, chúng tôi sẽ cần một con trỏ đặc biệt cho traversal

111
00:04:34,790 --> 00:04:36,940
mà chúng ta sẽ gọi là "thu thập thông tin. '

112
00:04:36,940 --> 00:04:38,870
Nó sẽ thu thập dữ liệu thông qua tất cả các yếu tố của danh sách

113
00:04:38,870 --> 00:04:41,190
theo chuỗi của con trỏ tới.

114
00:04:41,190 --> 00:04:43,750
Tất cả chúng tôi đã được lưu trữ một con trỏ đến nút 1,

115
00:04:43,750 --> 00:04:45,730
hoặc 'đầu' của danh sách.

116
00:04:45,730 --> 00:04:47,370
Điểm Đầu nút 1.

117
00:04:47,370 --> 00:04:49,120
Đó là kiểu con trỏ-to-node.

118
00:04:49,120 --> 00:04:51,280
>> Để có được các nút 1 thực tế trong danh sách,

119
00:04:51,280 --> 00:04:53,250
chúng ta phải dereference con trỏ này,

120
00:04:53,250 --> 00:04:55,100
nhưng trước khi chúng ta có thể dereference nó, chúng ta cần phải kiểm tra

121
00:04:55,100 --> 00:04:57,180
con trỏ là null đầu tiên.

122
00:04:57,180 --> 00:04:59,190
Nếu đó là vô giá trị, danh sách là trống rỗng,

123
00:04:59,190 --> 00:05:01,320
và chúng ta nên in ra một thông điệp rằng, bởi vì danh sách có sản phẩm nào,

124
00:05:01,320 --> 00:05:03,250
không có nút qua.

125
00:05:03,250 --> 00:05:05,190
Tuy nhiên, chúng ta hãy nói rằng trong danh sách là không có sản phẩm nào.

126
00:05:05,190 --> 00:05:08,340
Nếu không, thì chúng ta nên thu thập dữ liệu thông qua toàn bộ danh sách

127
00:05:08,340 --> 00:05:10,440
cho đến khi chúng tôi nhận được các nút cuối cùng của danh sách,

128
00:05:10,440 --> 00:05:13,030
và làm thế nào chúng ta có thể biết chúng tôi đang tìm kiếm tại các nút cuối cùng trong danh sách?

129
00:05:13,670 --> 00:05:16,660
>> Vâng, nếu con trỏ tới một nút là null,

130
00:05:16,660 --> 00:05:18,320
chúng tôi biết chúng tôi đang ở cuối

131
00:05:18,320 --> 00:05:22,390
tiếp theo kể từ khi con trỏ sẽ không có nút tiếp theo trong danh sách để trỏ đến.

132
00:05:22,390 --> 00:05:26,590
Đó là thực hành tốt để luôn luôn giữ cho con trỏ tới nút cuối cùng khởi tạo null

133
00:05:26,590 --> 00:05:30,800
có một tài sản được tiêu chuẩn hóa cảnh báo chúng tôi khi chúng tôi đã đạt đến cuối danh sách.

134
00:05:30,800 --> 00:05:33,510
>> Vì vậy, nếu thu thập thông tin → tiếp theo là null,

135
00:05:34,120 --> 00:05:38,270
hãy nhớ rằng cú pháp mũi tên là một phím tắt cho dereferencing

136
00:05:38,270 --> 00:05:40,010
một con trỏ đến một cấu trúc, sau đó truy cập

137
00:05:40,010 --> 00:05:42,510
trường tiếp theo của nó tương đương với vụng về:

138
00:05:42,510 --> 00:05:48,750
(* Bánh xích) tiếp theo.

139
00:05:49,820 --> 00:05:51,260
Một khi chúng ta đã tìm thấy các nút cuối cùng,

140
00:05:51,260 --> 00:05:53,830
chúng tôi muốn in thu thập thông tin → val,

141
00:05:53,830 --> 00:05:55,000
giá trị trong các nút hiện tại

142
00:05:55,000 --> 00:05:57,130
mà chúng ta biết là người cuối cùng.

143
00:05:57,130 --> 00:05:59,740
Nếu không, nếu chúng ta không được nêu ra tại các nút cuối cùng trong danh sách,

144
00:05:59,740 --> 00:06:02,340
chúng ta phải di chuyển đến nút tiếp theo trong danh sách

145
00:06:02,340 --> 00:06:04,750
và kiểm tra nếu đó là người cuối cùng.

146
00:06:04,750 --> 00:06:07,010
Để làm điều này, chúng ta chỉ cần đặt con trỏ trình thu thập thông tin của chúng tôi

147
00:06:07,010 --> 00:06:09,840
để trỏ đến giá trị tiếp theo của nút hiện tại,

148
00:06:09,840 --> 00:06:11,680
có nghĩa là, nút tiếp theo trong danh sách.

149
00:06:11,680 --> 00:06:13,030
Điều này được thực hiện bằng cách thiết lập

150
00:06:13,030 --> 00:06:15,280
thu thập thông tin = thu thập thông tin → sau.

151
00:06:16,050 --> 00:06:18,960
Sau đó, chúng ta lặp lại quá trình này, với một vòng lặp ví dụ,

152
00:06:18,960 --> 00:06:20,960
cho đến khi chúng tôi tìm thấy các nút cuối cùng.

153
00:06:20,960 --> 00:06:23,150
Vì vậy, ví dụ, nếu thu thập thông tin đã chỉ vào đầu,

154
00:06:24,050 --> 00:06:27,710
chúng tôi thiết lập thu thập thông tin chỉ để thu thập thông tin → tiếp theo,

155
00:06:27,710 --> 00:06:30,960
mà là giống như các lĩnh vực tiếp theo của nút 1.

156
00:06:30,960 --> 00:06:33,620
Vì vậy, bây giờ thu thập thông tin của chúng tôi được trỏ đến nút thứ 2,

157
00:06:33,620 --> 00:06:35,480
và, một lần nữa, chúng ta lặp lại điều này với một vòng lặp,

158
00:06:37,220 --> 00:06:40,610
cho đến khi chúng tôi đã tìm thấy các nút cuối cùng, đó là,

159
00:06:40,610 --> 00:06:43,640
nơi con trỏ tiếp theo của nút là chỉ để null.

160
00:06:43,640 --> 00:06:45,070
Và chúng tôi đã có nó,

161
00:06:45,070 --> 00:06:47,620
chúng tôi đã tìm thấy các nút cuối cùng trong danh sách, và in giá trị của nó,

162
00:06:47,620 --> 00:06:50,800
chúng tôi chỉ sử dụng thu thập thông tin → val.

163
00:06:50,800 --> 00:06:53,130
>> Traversing không phải là quá xấu, nhưng những gì về chèn?

164
00:06:53,130 --> 00:06:56,290
Cho phép nói rằng chúng tôi muốn chèn một số nguyên vào vị trí thứ 4

165
00:06:56,290 --> 00:06:58,040
trong một danh sách số nguyên.

166
00:06:58,040 --> 00:07:01,280
Đó là giữa 3 và 4 nút hiện tại.

167
00:07:01,280 --> 00:07:03,760
Một lần nữa, chúng ta phải đi qua các danh sách chỉ để

168
00:07:03,760 --> 00:07:06,520
được các yếu tố thứ 3, một trong chúng tôi đang chèn sau.

169
00:07:06,520 --> 00:07:09,300
Vì vậy, chúng tôi tạo ra một con trỏ thu thập thông tin một lần nữa để đi qua các danh sách,

170
00:07:09,300 --> 00:07:11,400
kiểm tra xem con trỏ đầu của chúng tôi là vô giá trị,

171
00:07:11,400 --> 00:07:14,810
và nếu nó không phải, chỉ con trỏ trình thu thập thông tin của chúng tôi tại nút đầu.

172
00:07:16,880 --> 00:07:18,060
Vì vậy, chúng ta đang ở các yếu tố 1.

173
00:07:18,060 --> 00:07:21,020
Chúng tôi phải đi về phía trước thêm 2 yếu tố trước khi chúng ta có thể chèn,

174
00:07:21,020 --> 00:07:23,390
vì vậy chúng tôi có thể sử dụng một vòng lặp for

175
00:07:23,390 --> 00:07:26,430
int i = 1; i <3; i + +

176
00:07:26,430 --> 00:07:28,590
và trong mỗi lần lặp của vòng lặp,

177
00:07:28,590 --> 00:07:31,540
tiến trình thu thập thông tin của chúng tôi con trỏ về phía trước bằng 1 nút

178
00:07:31,540 --> 00:07:34,570
bằng cách kiểm tra nếu trường tiếp theo của nút hiện tại là null,

179
00:07:34,570 --> 00:07:37,550
và nếu nó không phải, di chuyển con trỏ trình thu thập thông tin của chúng tôi đến nút tiếp theo

180
00:07:37,550 --> 00:07:41,810
bằng cách thiết lập nó bằng con trỏ tới các nút hiện tại.

181
00:07:41,810 --> 00:07:45,210
Vì vậy, kể từ khi vòng lặp cho chúng tôi nói rằng để làm điều đó

182
00:07:45,210 --> 00:07:47,550
hai lần,

183
00:07:49,610 --> 00:07:51,190
chúng tôi đã đạt đến nút thứ 3,

184
00:07:51,190 --> 00:07:53,110
và một khi con trỏ trình thu thập thông tin của chúng tôi đã đạt đến các nút sau khi

185
00:07:53,110 --> 00:07:55,270
mà chúng tôi muốn để chèn số nguyên mới của chúng tôi,

186
00:07:55,270 --> 00:07:57,050
làm thế nào để chúng tôi thực sự làm các việc chèn?

187
00:07:57,050 --> 00:07:59,440
>> Vâng, nguyên mới của chúng tôi đã được đưa vào danh sách

188
00:07:59,440 --> 00:08:01,250
như là một phần của struct node riêng của mình,

189
00:08:01,250 --> 00:08:03,140
vì đây thực sự là một chuỗi các nút.

190
00:08:03,140 --> 00:08:05,690
Vì vậy, chúng ta hãy làm một con trỏ mới đến nút

191
00:08:05,690 --> 00:08:08,910
được gọi là 'new_node,

192
00:08:08,910 --> 00:08:11,800
và thiết lập nó để trỏ đến bộ nhớ mà bây giờ chúng ta phân bổ

193
00:08:11,800 --> 00:08:14,270
trên heap cho nút chính nó,

194
00:08:14,270 --> 00:08:16,000
và chúng ta cần phải phân bổ bao nhiêu bộ nhớ?

195
00:08:16,000 --> 00:08:18,250
, Kích thước của một nút,

196
00:08:20,450 --> 00:08:23,410
và chúng tôi muốn thiết lập lĩnh vực val đến số nguyên mà chúng tôi muốn chèn.

197
00:08:23,410 --> 00:08:25,590
Hãy nói rằng, 6.

198
00:08:25,590 --> 00:08:27,710
Bây giờ, nút chứa giá trị số nguyên của chúng tôi.

199
00:08:27,710 --> 00:08:30,650
Nó cũng tốt thực hành để khởi tạo trường tiếp theo của nút mới

200
00:08:30,650 --> 00:08:33,690
chỉ để null,

201
00:08:33,690 --> 00:08:35,080
nhưng bây giờ những gì?

202
00:08:35,080 --> 00:08:37,179
>> Chúng ta phải thay đổi cấu trúc nội bộ của danh sách

203
00:08:37,179 --> 00:08:40,409
và các con trỏ tiếp theo chứa hiện tại của danh sách

204
00:08:40,409 --> 00:08:42,950
Thứ 3 và thứ 4 nút.

205
00:08:42,950 --> 00:08:46,560
Kể từ khi con trỏ tiếp theo xác định thứ tự của danh sách,

206
00:08:46,560 --> 00:08:48,650
và kể từ khi chúng tôi đang chèn nút mới của chúng tôi

207
00:08:48,650 --> 00:08:50,510
ngay chính giữa của danh sách,

208
00:08:50,510 --> 00:08:52,010
nó có thể được một chút khôn lanh.

209
00:08:52,010 --> 00:08:54,250
Điều này là bởi vì, hãy nhớ rằng, máy tính của chúng tôi

210
00:08:54,250 --> 00:08:56,250
chỉ biết vị trí của các nút trong danh sách

211
00:08:56,250 --> 00:09:00,400
vì các con trỏ tiếp theo được lưu trữ trong các nút trước đó.

212
00:09:00,400 --> 00:09:03,940
Vì vậy, nếu chúng ta bao giờ mất theo dõi của bất kỳ các địa điểm này,

213
00:09:03,940 --> 00:09:06,860
nói bằng cách thay đổi một số các con trỏ tiếp theo trong danh sách của chúng tôi,

214
00:09:06,860 --> 00:09:09,880
Ví dụ, nếu chúng ta thay đổi

215
00:09:09,880 --> 00:09:12,920
nút thứ 3 trường tiếp theo

216
00:09:12,920 --> 00:09:15,610
để trỏ đến một số nút trên đây.

217
00:09:15,610 --> 00:09:17,920
Chúng tôi muốn được ra khỏi may mắn, bởi vì chúng tôi sẽ không

218
00:09:17,920 --> 00:09:20,940
có bất kỳ ý tưởng nơi để tìm thấy phần còn lại của danh sách,

219
00:09:20,940 --> 00:09:23,070
và đó rõ ràng là thực sự xấu.

220
00:09:23,070 --> 00:09:25,080
Vì vậy, chúng ta phải thực sự cẩn thận về đơn đặt hàng

221
00:09:25,080 --> 00:09:28,360
trong đó chúng ta thao tác con trỏ tiếp theo của chúng tôi trong quá trình chèn.

222
00:09:28,360 --> 00:09:30,540
>> Vì vậy, để đơn giản hóa điều này, chúng ta hãy nói rằng

223
00:09:30,540 --> 00:09:32,220
4 đầu tiên của chúng tôi các nút

224
00:09:32,220 --> 00:09:36,200
được gọi là A, B, C, và D, với các mũi tên đại diện cho chuỗi các con trỏ

225
00:09:36,200 --> 00:09:38,070
kết nối các nút.

226
00:09:38,070 --> 00:09:40,050
Vì vậy, chúng ta cần để chèn nút mới của chúng tôi

227
00:09:40,050 --> 00:09:42,070
giữa các nút C và D.

228
00:09:42,070 --> 00:09:45,060
Đó là quan trọng để làm điều đó theo thứ tự đúng, và tôi sẽ cho bạn thấy lý do tại sao.

229
00:09:45,060 --> 00:09:47,500
>> Hãy nhìn vào con đường sai để làm điều đó đầu tiên.

230
00:09:47,500 --> 00:09:49,490
Này, chúng tôi biết các nút mới đã đến ngay sau khi C,

231
00:09:49,490 --> 00:09:51,910
do đó, chúng ta hãy đặt con trỏ tới C

232
00:09:51,910 --> 00:09:54,700
chỉ new_node.

233
00:09:56,530 --> 00:09:59,180
Được rồi, có vẻ okay, chúng tôi chỉ cần có để hoàn thành bây giờ bằng cách

234
00:09:59,180 --> 00:10:01,580
điểm con trỏ tới nút mới đến D,

235
00:10:01,580 --> 00:10:03,250
nhưng chờ đợi, làm thế nào chúng ta có thể làm điều đó?

236
00:10:03,250 --> 00:10:05,170
Điều duy nhất mà có thể cho chúng tôi biết trong đó D,

237
00:10:05,170 --> 00:10:07,630
con trỏ tiếp theo được lưu trữ trước đó trong C,

238
00:10:07,630 --> 00:10:09,870
nhưng chúng tôi chỉ viết lại con trỏ

239
00:10:09,870 --> 00:10:11,170
để trỏ đến các nút mới,

240
00:10:11,170 --> 00:10:14,230
vì vậy chúng tôi không có bất kỳ mối trong đó D là trong bộ nhớ,

241
00:10:14,230 --> 00:10:17,020
và chúng tôi đã bị mất phần còn lại của danh sách.

242
00:10:17,020 --> 00:10:19,000
Không tốt ở tất cả.

243
00:10:19,000 --> 00:10:21,090
>> Vì vậy, làm thế nào để chúng tôi làm điều này đúng không?

244
00:10:22,360 --> 00:10:25,090
Đầu tiên, chỉ con trỏ tới các nút mới tại D.

245
00:10:26,170 --> 00:10:28,990
Bây giờ, cả hai nút mới và C tiếp theo con trỏ

246
00:10:28,990 --> 00:10:30,660
đang trỏ đến cùng một nút, D,

247
00:10:30,660 --> 00:10:32,290
nhưng đó là tiền phạt.

248
00:10:32,290 --> 00:10:35,680
Bây giờ chúng tôi có thể chỉ cho con trỏ tới C tại các nút mới.

249
00:10:37,450 --> 00:10:39,670
Vì vậy, chúng tôi đã làm điều này mà không bị mất bất kỳ dữ liệu nào.

250
00:10:39,670 --> 00:10:42,280
Trong mã, C là nút hiện tại

251
00:10:42,280 --> 00:10:45,540
traversal con trỏ thu thập thông tin được trỏ đến,

252
00:10:45,540 --> 00:10:50,400
và D được đại diện bởi các nút được trỏ đến bởi trường tiếp theo của nút hiện tại,

253
00:10:50,400 --> 00:10:52,600
hoặc thu thập thông tin → tiếp theo.

254
00:10:52,600 --> 00:10:55,460
Vì vậy, chúng tôi lần đầu tiên thiết lập con trỏ tới các nút mới

255
00:10:55,460 --> 00:10:57,370
chỉ để thu thập thông tin → tiếp theo,

256
00:10:57,370 --> 00:11:00,880
theo cùng một cách chúng tôi đã nói con trỏ tới new_node

257
00:11:00,880 --> 00:11:02,780
trỏ đến D trong hình minh hoạ.

258
00:11:02,780 --> 00:11:04,540
Sau đó, chúng ta có thể đặt con trỏ tới các nút hiện tại

259
00:11:04,540 --> 00:11:06,330
nút mới của chúng tôi,

260
00:11:06,330 --> 00:11:10,980
cũng giống như chúng tôi đã phải chờ đợi đến điểm C để new_node trong các bản vẽ.

261
00:11:10,980 --> 00:11:12,250
Bây giờ tất cả mọi thứ theo thứ tự, và chúng tôi đã không mất

262
00:11:12,250 --> 00:11:14,490
theo dõi bất kỳ dữ liệu nào, và chúng tôi đã có thể chỉ cần

263
00:11:14,490 --> 00:11:16,200
dính nút mới của chúng tôi ở giữa của danh sách

264
00:11:16,200 --> 00:11:19,330
mà không cần xây dựng lại toàn bộ điều hoặc thậm chí thay đổi bất kỳ yếu tố

265
00:11:19,330 --> 00:11:22,490
cách chúng ta đã có thể có với một mảng có độ dài cố định.

266
00:11:22,490 --> 00:11:26,020
>> Vì vậy, danh sách liên kết là một cấu trúc dữ liệu động cơ bản, nhưng quan trọng

267
00:11:26,020 --> 00:11:29,080
trong đó có cả ưu và nhược điểm

268
00:11:29,080 --> 00:11:31,260
so với mảng và cấu trúc dữ liệu khác,

269
00:11:31,260 --> 00:11:33,350
và như thường là trường hợp trong khoa học máy tính,

270
00:11:33,350 --> 00:11:35,640
điều quan trọng cần biết khi sử dụng mỗi công cụ,

271
00:11:35,640 --> 00:11:37,960
vì vậy bạn có thể chọn đúng công cụ cho công việc phải.

272
00:11:37,960 --> 00:11:40,060
>> Đối với thực hành nhiều hơn, hãy thử viết chức năng

273
00:11:40,060 --> 00:11:42,080
xóa các nút từ một danh sách liên kết

274
00:11:42,080 --> 00:11:44,050
nhớ phải cẩn thận về thứ tự mà bạn sắp xếp lại

275
00:11:44,050 --> 00:11:47,430
Con trỏ tiếp theo của bạn để đảm bảo rằng bạn không bị mất một đoạn danh sách của bạn -

276
00:11:47,430 --> 00:11:50,200
hoặc một chức năng để tính các nút trong một danh sách liên kết,

277
00:11:50,200 --> 00:11:53,280
hoặc một niềm vui, để đảo ngược thứ tự của tất cả các nút trong một danh sách liên kết.

278
00:11:53,280 --> 00:11:56,090
>> Tên tôi là Jackson Steinkamp, ​​đây là CS50.