1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] در برنامه نویسی، ما اغلب نیاز به نشان دادن لیستی از ارزش ها،

2
00:00:10,050 --> 00:00:12,840
مانند نام دانش آموزان در بخش

3
00:00:12,840 --> 00:00:15,100
یا نمرات خود را در آخرین مسابقه.

4
00:00:15,100 --> 00:00:17,430
>> در زبان C، اعلام کرد که آرایه را می توان مورد استفاده قرار گیرد

5
00:00:17,430 --> 00:00:19,160
برای ذخیره لیست.

6
00:00:19,160 --> 00:00:21,200
آسان به شمردن عناصر یک لیست

7
00:00:21,200 --> 00:00:23,390
ذخیره شده در یک آرایه، و اگر شما نیاز به دسترسی به

8
00:00:23,390 --> 00:00:25,050
یا تغییر عنصر i ام

9
00:00:25,050 --> 00:00:27,570
برای برخی از شاخص دلخواه من،

10
00:00:27,570 --> 00:00:29,910
است که می تواند در زمان ثابت انجام شده است،

11
00:00:29,910 --> 00:00:31,660
اما آرایه ها دارای معایب، بیش از حد.

12
00:00:31,660 --> 00:00:33,850
>> هنگامی که آنها را ما اعلام می کنیم، ما نیاز به گفتن نیست

13
00:00:33,850 --> 00:00:35,900
تا جلو چقدر بزرگ آنها،

14
00:00:35,900 --> 00:00:38,160
است که چگونه بسیاری از عناصر که می توانند ذخیره

15
00:00:38,160 --> 00:00:40,780
و چقدر بزرگ این عناصر هستند، است که بر اساس نوع آنها تعیین شده است.

16
00:00:40,780 --> 00:00:45,450
به عنوان مثال، اعضای هیات ARR (10)

17
00:00:45,450 --> 00:00:48,220
10 اقلام فروشگاه

18
00:00:48,220 --> 00:00:50,200
که به اندازه یک int است.

19
00:00:50,200 --> 00:00:52,590
>> ما می توانیم اندازه یک آرایه پس از اعلام تغییر نمی کند.

20
00:00:52,590 --> 00:00:55,290
ما را به یک آرایه جدید اگر ما می خواهیم برای ذخیره عناصر بیشتر است.

21
00:00:55,290 --> 00:00:57,410
دلیل این محدودیت وجود دارد این است که ما

22
00:00:57,410 --> 00:00:59,040
برنامه ذخیره آرایه کل

23
00:00:59,040 --> 00:01:02,310
به عنوان یک قطعه پیوسته از حافظه است.

24
00:01:02,310 --> 00:01:04,500
می گویند این بافر که در آن ما را در آرایه ذخیره می شود.

25
00:01:04,500 --> 00:01:06,910
ممکن است متغیر دیگر وجود دارد

26
00:01:06,910 --> 00:01:08,310
قرار گرفته است درست در کنار آرایه

27
00:01:08,310 --> 00:01:10,060
در حافظه، بنابراین ما می توانیم

28
00:01:10,060 --> 00:01:12,060
فقط آرایه بزرگتر.

29
00:01:12,060 --> 00:01:15,700
>> گاهی اوقات ما می خواهم سریع آرایه سرعت دسترسی به داده ها به تجارت

30
00:01:15,700 --> 00:01:17,650
برای انعطاف پذیری کمی بیشتر است.

31
00:01:17,650 --> 00:01:20,380
لیست پیوندی، یکی دیگر از ساختار داده های اولیه را وارد کنید

32
00:01:20,380 --> 00:01:22,360
شما ممکن است به عنوان آشنا با.

33
00:01:22,360 --> 00:01:24,200
در سطح بالا،

34
00:01:24,200 --> 00:01:26,840
یک لیست پیوندی ذخیره داده ها در یک دنباله ای از گره ها

35
00:01:26,840 --> 00:01:29,280
که با پیوندهایی به یکدیگر متصل شده،

36
00:01:29,280 --> 00:01:31,760
از این رو به نام "فهرست مرتبط است. '

37
00:01:31,760 --> 00:01:33,840
همانطور که خواهیم دید، این تفاوت در طراحی

38
00:01:33,840 --> 00:01:35,500
منجر به مزایا و معایب مختلف

39
00:01:35,500 --> 00:01:37,000
از یک آرایه.

40
00:01:37,000 --> 00:01:39,840
>> در اینجا برخی از کد C برای یک لیست بسیار ساده مرتبط از اعداد صحیح.

41
00:01:39,840 --> 00:01:42,190
شما می توانید ببینید که ما به نمایندگی هر گره

42
00:01:42,190 --> 00:01:45,520
در این لیست به عنوان یک ساختار که شامل 2 چیز است،

43
00:01:45,520 --> 00:01:47,280
یک عدد صحیح برای ذخیره به نام 'وال

44
00:01:47,280 --> 00:01:50,460
و یک لینک به گره بعدی در لیست

45
00:01:50,460 --> 00:01:52,990
که ما آن را به عنوان یک اشاره گر به نام نشان دهنده بعدی.

46
00:01:54,120 --> 00:01:56,780
به این ترتیب، ما می توانیم کل لیست پیگیری

47
00:01:56,780 --> 00:01:58,790
با تنها یک اشاره گر به گره 1،

48
00:01:58,790 --> 00:02:01,270
و پس از آن ما می توانیم اشاره گرهای بعدی را دنبال کنید

49
00:02:01,270 --> 00:02:03,130
به گره 2،

50
00:02:03,130 --> 00:02:05,280
به گره 3،

51
00:02:05,280 --> 00:02:07,000
به گره 4،

52
00:02:07,000 --> 00:02:09,889
و به همین ترتیب، تا زمانی که ما به انتهای لیست را دریافت کنید.

53
00:02:10,520 --> 00:02:12,210
>> ممکن است شما قادر به دیدن 1 مزیت این است

54
00:02:12,210 --> 00:02:14,490
بیش از ساختار آرایه استاتیک - با یک لیست پیوندی

55
00:02:14,490 --> 00:02:16,450
ما یک تکه بزرگ از حافظه نیاز دارید در دسترس نباشد.

56
00:02:17,400 --> 00:02:20,530
1 گره از لیست می تواند زندگی می کنند، در این محل در حافظه

57
00:02:20,530 --> 00:02:23,160
و گره 2 می تواند تمام راه را در اینجا.

58
00:02:23,160 --> 00:02:25,780
ما می توانیم به تمام گره ها بدون توجه به جایی که در حافظه آنها،

59
00:02:25,780 --> 00:02:28,890
چرا که با شروع از گره 1، اشاره گر در کنار هر یک از گره

60
00:02:28,890 --> 00:02:31,700
به ما می گوید دقیقا همان جایی که برای رفتن به بعدی.

61
00:02:31,700 --> 00:02:33,670
>> علاوه بر این، ما لازم نیست برای گفتن جلو

62
00:02:33,670 --> 00:02:36,740
بزرگ که چگونه یک لیست پیوندی خواهد بود که راه ما را با آرایه های استاتیک را،

63
00:02:36,740 --> 00:02:39,060
از آنجا که ما می توانیم به اضافه کردن گره به یک لیست

64
00:02:39,060 --> 00:02:42,600
تا زمانی که این فضا وجود دارد جایی در حافظه برای گره های جدید.

65
00:02:42,600 --> 00:02:45,370
بنابراین، لیست های پیوندی بسیار آسان برای تغییر اندازه به صورت پویا.

66
00:02:45,370 --> 00:02:47,950
بگو، بعد از آن در این برنامه ما نیاز به اضافه کردن گره های بیشتر

67
00:02:47,950 --> 00:02:49,350
به لیست ما است.

68
00:02:49,350 --> 00:02:51,480
برای درج یک گره جدید به لیست ما در پرواز،

69
00:02:51,480 --> 00:02:53,740
همه ما باید انجام دهیم این است که تخصیص حافظه برای آن گره،

70
00:02:53,740 --> 00:02:55,630
با صدای تلپ ارزش داده،

71
00:02:55,630 --> 00:02:59,070
و پس از آن جایی که ما با تنظیم اشاره گر مناسب می خواهید قرار دهید.

72
00:02:59,070 --> 00:03:02,310
>> برای مثال، اگر ما می خواستیم به جای یک گره در میان

73
00:03:02,310 --> 00:03:04,020
2nd و 3 گره از لیست،

74
00:03:04,020 --> 00:03:06,800
 ما نمی خواهد که به حرکت در گره های 2 یا 3.

75
00:03:06,800 --> 00:03:09,190
می گویند که ما در حال قرار دادن این گره قرمز.

76
00:03:09,190 --> 00:03:12,890
همه ما می خواهم که برای انجام مجموعه ای از اشاره گر به گره جدید

77
00:03:12,890 --> 00:03:14,870
برای اشاره به گره 3

78
00:03:14,870 --> 00:03:18,580
و سپس اشاره گر گره 2 rewire به

79
00:03:18,580 --> 00:03:20,980
برای اشاره به گره جدید است.

80
00:03:22,340 --> 00:03:24,370
بنابراین، ما می توانیم لیست ما را در پرواز آن، اندازه آن را تغییر

81
00:03:24,370 --> 00:03:26,090
از کامپیوتر ما می کند بر روی نمایه سازی تکیه نیست،

82
00:03:26,090 --> 00:03:28,990
بلکه در ارتباط با استفاده از اشاره گرها به آنها را ذخیره.

83
00:03:29,120 --> 00:03:31,600
>> با این حال، یک نقطه ضعف در ارتباط لیست

84
00:03:31,600 --> 00:03:33,370
این است که، برخلاف یک آرایه ایستا،

85
00:03:33,370 --> 00:03:36,690
کامپیوتر فقط به وسط لیست نمی تواند پرش.

86
00:03:38,040 --> 00:03:40,780
از آنجا که کامپیوتر برای دیدار هر گره در لیست پیوندی

87
00:03:40,780 --> 00:03:42,330
برای رسیدن به یک بعدی،

88
00:03:42,330 --> 00:03:44,770
آن را به دیگر یک گره خاص برای پیدا کردن

89
00:03:44,770 --> 00:03:46,400
از آن را در یک آرایه.

90
00:03:46,400 --> 00:03:48,660
برای پیمایش لیست کامل طول می کشد زمان متناسب

91
00:03:48,660 --> 00:03:50,580
به طول از لیست،

92
00:03:50,580 --> 00:03:54,630
یا O (N) در نماد مجانبی است.

93
00:03:54,630 --> 00:03:56,510
به طور متوسط، رسیدن به هر گره

94
00:03:56,510 --> 00:03:58,800
نیز طول می کشد زمان متناسب با N.

95
00:03:58,800 --> 00:04:00,700
>> در حال حاضر، اجازه دهید در واقع نوشتن برخی از کد

96
00:04:00,700 --> 00:04:02,000
که با این نسخهها کار با لیست های پیوندی می باشد.

97
00:04:02,000 --> 00:04:04,220
بیایید می گویند ما می خواهیم یک لیست پیوندی از اعداد صحیح.

98
00:04:04,220 --> 00:04:06,140
ما می توانیم یک گره در لیست ما باشد دوباره

99
00:04:06,140 --> 00:04:08,340
به عنوان یک ساختار با 2 رشته،

100
00:04:08,340 --> 00:04:10,750
یک مقدار صحیح به نام 'وال

101
00:04:10,750 --> 00:04:13,490
و بعد اشاره گر به گره بعدی از لیست.

102
00:04:13,490 --> 00:04:15,660
خب، به نظر می رسد به اندازه کافی ساده است.

103
00:04:15,660 --> 00:04:17,220
>> بیایید می گویند ما می خواهیم برای نوشتن یک تابع

104
00:04:17,220 --> 00:04:19,329
که عبور از لیست و چاپ

105
00:04:19,329 --> 00:04:22,150
ارزش در آخرین گره از لیست ذخیره می شود.

106
00:04:22,150 --> 00:04:24,850
خب، این بدان معناست که ما باید به گذشتن از تمام گره های موجود در لیست

107
00:04:24,850 --> 00:04:27,310
برای پیدا کردن یکی از آخرین، اما از آنجایی که ما در حال اضافه نکرده

108
00:04:27,310 --> 00:04:29,250
یا پاک کردن هر چیزی، ما نمی خواهم به تغییر

109
00:04:29,250 --> 00:04:32,210
ساختار داخلی اشاره گرهای بعدی در لیست است.

110
00:04:32,210 --> 00:04:34,790
>> بنابراین، ما به یک اشاره گر به طور خاص برای پیمایش نیاز

111
00:04:34,790 --> 00:04:36,940
که ما بهش زنگ می زنم خزنده.

112
00:04:36,940 --> 00:04:38,870
آن را از طریق تمامی عناصر را از لیست به خزیدن

113
00:04:38,870 --> 00:04:41,190
به دنبال زنجیره ای از اشاره گرهای بعدی.

114
00:04:41,190 --> 00:04:43,750
همه ما ذخیره می شود یک اشاره گر به گره 1،

115
00:04:43,750 --> 00:04:45,730
یا "سر" از فهرست.

116
00:04:45,730 --> 00:04:47,370
نقطه سر به گره 1.

117
00:04:47,370 --> 00:04:49,120
آن را از نوع اشاره گر به گره است.

118
00:04:49,120 --> 00:04:51,280
>> برای به دست آوردن واقعی 1 گره در لیست،

119
00:04:51,280 --> 00:04:53,250
ما به dereference این اشاره گر،

120
00:04:53,250 --> 00:04:55,100
اما قبل از ما می توانید آن را dereference، ما نیاز به بررسی

121
00:04:55,100 --> 00:04:57,180
اگر اشاره گر پوچ است برای اولین بار.

122
00:04:57,180 --> 00:04:59,190
اگر تهی، این فهرست خالی است،

123
00:04:59,190 --> 00:05:01,320
و ما باید نسخه قابل چاپ کردن یک پیام که، چرا که لیست خالی است،

124
00:05:01,320 --> 00:05:03,250
گره تاریخ و زمان آخرین وجود ندارد.

125
00:05:03,250 --> 00:05:05,190
اما، اجازه دهید می گویند که این فهرست خالی است.

126
00:05:05,190 --> 00:05:08,340
اگر این طور نیست، پس ما باید از طریق لیست کل خزیدن

127
00:05:08,340 --> 00:05:10,440
تا زمانی که ما به آخرین گره از لیست را دریافت کنید،

128
00:05:10,440 --> 00:05:13,030
و چگونه می تواند به ما بگوید اگر ما به دنبال در آخرین گره در لیست؟

129
00:05:13,670 --> 00:05:16,660
>> خوب، اگر اشاره گر گره تهی،

130
00:05:16,660 --> 00:05:18,320
ما می دانیم که ما در پایان هستید

131
00:05:18,320 --> 00:05:22,390
از اشاره گر بعدی آخرین گره بعدی در این لیست به نقطه را به را داشته باشد.

132
00:05:22,390 --> 00:05:26,590
این تمرین خوبی است که همیشه نگه داشتن اشاره گر بعدی آخرین گره مقداردهی اولیه به تهی

133
00:05:26,590 --> 00:05:30,800
به یک ویژگی استاندارد است که به ما هشدار وقتی که ما به انتهای لیست.

134
00:05:30,800 --> 00:05:33,510
>> بنابراین، اگر خزنده → بعدی صفر است،

135
00:05:34,120 --> 00:05:38,270
به یاد داشته باشید که ترکیب فلش است یک میانبر برای غیر مرجع

136
00:05:38,270 --> 00:05:40,010
اشاره گر به ساختار، و سپس دسترسی به

137
00:05:40,010 --> 00:05:42,510
میدان های بعدی آن معادل بی دست و پا:

138
00:05:42,510 --> 00:05:48,750
(خزنده).

139
00:05:49,820 --> 00:05:51,260
هنگامی که ما پیدا کرده ام آخرین گره

140
00:05:51,260 --> 00:05:53,830
ما می خواهیم به چاپ خزنده → وال،

141
00:05:53,830 --> 00:05:55,000
مقدار در گره

142
00:05:55,000 --> 00:05:57,130
که ما می دانیم که یکی از آخرین.

143
00:05:57,130 --> 00:05:59,740
در غیر این صورت، اگر ما در آخرین گره در لیست هنوز رتبهدهی نشده است

144
00:05:59,740 --> 00:06:02,340
ما باید به حرکت بر روی گره بعدی در لیست

145
00:06:02,340 --> 00:06:04,750
را چک کرده و در صورتی که یکی از آخرین.

146
00:06:04,750 --> 00:06:07,010
برای انجام این کار، ما فقط اشاره گر خزنده ما

147
00:06:07,010 --> 00:06:09,840
به نقطه را به ارزش گره فعلی،

148
00:06:09,840 --> 00:06:11,680
است که گره بعدی در لیست است.

149
00:06:11,680 --> 00:06:13,030
این است که با تنظیم انجام می شود

150
00:06:13,030 --> 00:06:15,280
خزنده خزنده → بعدی.

151
00:06:16,050 --> 00:06:18,960
سپس این روند را تکرار می کنیم، با یک حلقه به عنوان مثال،

152
00:06:18,960 --> 00:06:20,960
تا زمانی که ما پیدا کردن گره تاریخ و زمان آخرین.

153
00:06:20,960 --> 00:06:23,150
بنابراین، برای مثال، اگر خزنده با اشاره به سر،

154
00:06:24,050 --> 00:06:27,710
ما مجموعه ای خزنده اشاره به خزنده → بعدی،

155
00:06:27,710 --> 00:06:30,960
که همان است که در این زمینه بعد از گره 1 است.

156
00:06:30,960 --> 00:06:33,620
بنابراین، در حال حاضر خزنده ما این است که با اشاره به گره 2،

157
00:06:33,620 --> 00:06:35,480
و دوباره تکرار می کنیم این کار را با یک حلقه،

158
00:06:37,220 --> 00:06:40,610
تا زمانی که ما پیدا کرده ام گره گذشته است، که،

159
00:06:40,610 --> 00:06:43,640
جایی که اشاره گر گره با اشاره به تهی.

160
00:06:43,640 --> 00:06:45,070
و در آنجا ما آن را داشته باشد،

161
00:06:45,070 --> 00:06:47,620
ایم و زمان آخرین گره در لیست یافت، و ارزش خود را به چاپ

162
00:06:47,620 --> 00:06:50,800
ما فقط خزنده → وال استفاده کنید.

163
00:06:50,800 --> 00:06:53,130
>> عبور است خیلی بد نیست، اما آنچه در مورد قرار دادن؟

164
00:06:53,130 --> 00:06:56,290
بیایید می گویند ما می خواهیم برای قرار دادن یک عدد صحیح به سمت 4

165
00:06:56,290 --> 00:06:58,040
در یک لیست صحیح است.

166
00:06:58,040 --> 00:07:01,280
که بین گره های 3 و 4.

167
00:07:01,280 --> 00:07:03,760
باز هم، ما باید به گذشتن از این لیست فقط به

168
00:07:03,760 --> 00:07:06,520
رسیدن به عنصر 3، یکی از ما پس از قرار دادن.

169
00:07:06,520 --> 00:07:09,300
بنابراین، یک اشاره گر خزنده ما دوباره این لیست را به گذشتن از،

170
00:07:09,300 --> 00:07:11,400
اگر اشاره گر سر ما تهی است،

171
00:07:11,400 --> 00:07:14,810
و اگر این طور نیست، نقطه اشاره گر خزنده ما در گره سر.

172
00:07:16,880 --> 00:07:18,060
بنابراین، ما در عنصر 1 هستید.

173
00:07:18,060 --> 00:07:21,020
ما باید برای رفتن به جلو 2 بیشتر عناصر قبل از ما می توانید وارد،

174
00:07:21,020 --> 00:07:23,390
بنابراین ما می توانیم یک حلقه for استفاده کنید

175
00:07:23,390 --> 00:07:26,430
اعضای هیات من = 1؛ <3، من + +

176
00:07:26,430 --> 00:07:28,590
و در هر تکرار از حلقه،

177
00:07:28,590 --> 00:07:31,540
پیشبرد اشاره گر خزنده ما رو به جلو با 1 گره

178
00:07:31,540 --> 00:07:34,570
با چک کردن اگر میدان گره فعلی تهی است،

179
00:07:34,570 --> 00:07:37,550
و اگر این طور نیست، حرکت خزنده اشاره گر به گره بعدی

180
00:07:37,550 --> 00:07:41,810
تنظیم آن را به اشاره گر گره برابر است.

181
00:07:41,810 --> 00:07:45,210
بنابراین، از آنجا که حلقه برای ما می گوید: برای انجام این کار

182
00:07:45,210 --> 00:07:47,550
دو بار،

183
00:07:49,610 --> 00:07:51,190
ما رسیده گره 3،

184
00:07:51,190 --> 00:07:53,110
و یک بار اشاره گر خزنده ما رسیده است گره پس از

185
00:07:53,110 --> 00:07:55,270
که ما می خواهیم برای وارد کردن عدد صحیح جدید ما،

186
00:07:55,270 --> 00:07:57,050
چگونه ما در واقع قرار دادن؟

187
00:07:57,050 --> 00:07:59,440
>> خوب، عدد صحیح ما را به لیست قرار

188
00:07:59,440 --> 00:08:01,250
به عنوان بخشی از ساختار گره خود را،

189
00:08:01,250 --> 00:08:03,140
از آنجا که این در واقع دنباله ای از گره ها است.

190
00:08:03,140 --> 00:08:05,690
بنابراین، اجازه دهید یک اشاره گر به گره

191
00:08:05,690 --> 00:08:08,910
به نام 'new_node،'

192
00:08:08,910 --> 00:08:11,800
و آن را به نقطه را به حافظه است که ما در حال حاضر اختصاص

193
00:08:11,800 --> 00:08:14,270
در پشته برای گره خود،

194
00:08:14,270 --> 00:08:16,000
و چه مقدار حافظه آیا ما نیاز به اختصاص؟

195
00:08:16,000 --> 00:08:18,250
خب، به اندازه یک گره،

196
00:08:20,450 --> 00:08:23,410
و ما می خواهیم برای تنظیم زمینه وال خود را به عدد صحیح است که ما می خواهیم برای وارد کردن.

197
00:08:23,410 --> 00:08:25,590
بیایید می گویند، 6.

198
00:08:25,590 --> 00:08:27,710
در حال حاضر، گره حاوی مقدار صحیح ما.

199
00:08:27,710 --> 00:08:30,650
این هم تمرین خوبی برای مقداردهی به فیلد بعدی گره جدید

200
00:08:30,650 --> 00:08:33,690
به نقطه را به تهی،

201
00:08:33,690 --> 00:08:35,080
اما در حال حاضر چه؟

202
00:08:35,080 --> 00:08:37,179
>> ما باید برای تغییر ساختار داخلی از لیست

203
00:08:37,179 --> 00:08:40,409
و اشاره گرهای بعدی موجود در لیست موجود

204
00:08:40,409 --> 00:08:42,950
گره 3 و 4.

205
00:08:42,950 --> 00:08:46,560
از آنجا که اشاره گرها تعیین منظور از فهرست،

206
00:08:46,560 --> 00:08:48,650
و از آنجایی که ما در حال قرار دادن گره جدید ما

207
00:08:48,650 --> 00:08:50,510
حق را به وسط لیست،

208
00:08:50,510 --> 00:08:52,010
می توان آن را کمی از روی حیله و تزویر است.

209
00:08:52,010 --> 00:08:54,250
دلیلش این است که به یاد داشته باشید، کامپیوتر ما

210
00:08:54,250 --> 00:08:56,250
تنها می داند که محل گره ها در لیست

211
00:08:56,250 --> 00:09:00,400
به دلیل از اشاره گر های بعدی ذخیره شده در گره های قبلی است.

212
00:09:00,400 --> 00:09:03,940
بنابراین، اگر ما تا به حال از دست رفته ردیابی هر یک از این نقاط،

213
00:09:03,940 --> 00:09:06,860
می گویند با تغییر یکی از اشاره گرهای بعدی در لیست ما،

214
00:09:06,860 --> 00:09:09,880
به عنوان مثال، می گویند ما تغییر

215
00:09:09,880 --> 00:09:12,920
میدان گره 3

216
00:09:12,920 --> 00:09:15,610
اشاره به برخی از گره در اینجا.

217
00:09:15,610 --> 00:09:17,920
ما می خواهم از شانس باشد، چرا که ما می خواهیم

218
00:09:17,920 --> 00:09:20,940
هر گونه ایده که در آن برای پیدا کردن بقیه از لیست،

219
00:09:20,940 --> 00:09:23,070
و این بدیهی است که واقعا بد است.

220
00:09:23,070 --> 00:09:25,080
بنابراین، ما باید واقعا دقیق در مورد نظم

221
00:09:25,080 --> 00:09:28,360
که در آن اشاره گرهای بعدی ما دستکاری در هنگام درج.

222
00:09:28,360 --> 00:09:30,540
>> بنابراین، به این ساده، اجازه دهید بگویم که

223
00:09:30,540 --> 00:09:32,220
ما 4 گره

224
00:09:32,220 --> 00:09:36,200
A، B، C، و D نامیده می شود، با فلش به نمایندگی از زنجیره ای از اشاره گرها

225
00:09:36,200 --> 00:09:38,070
که اتصال گره ها.

226
00:09:38,070 --> 00:09:40,050
بنابراین، ما باید به درج گره جدید ما

227
00:09:40,050 --> 00:09:42,070
در بین گره های C و D.

228
00:09:42,070 --> 00:09:45,060
این مهم به آن را در جهت درست انجام دهد، و من به شما نشان می دهد که چرا.

229
00:09:45,060 --> 00:09:47,500
>> اجازه دهید نگاهی به راه اشتباه آن را انجام دهد.

230
00:09:47,500 --> 00:09:49,490
با سلام، ما می دانیم که گره جدید است بلافاصله پس از C،

231
00:09:49,490 --> 00:09:51,910
بنابراین مجموعه بعدی اشاره گر C به شما اجازه می دهد تا

232
00:09:51,910 --> 00:09:54,700
به نقطه را به new_node.

233
00:09:56,530 --> 00:09:59,180
همه حق است، به نظر می رسد خوب، ما فقط باید برای پایان دادن به در حال حاضر توسط

234
00:09:59,180 --> 00:10:01,580
نقطه گره بعدی اشاره گر به D،

235
00:10:01,580 --> 00:10:03,250
اما صبر کنید، چگونه می تواند ما انجام این کار؟

236
00:10:03,250 --> 00:10:05,170
تنها چیزی که می تواند ما را که در آن D بود،

237
00:10:05,170 --> 00:10:07,630
اشاره گر بعدی قبلا در C ذخیره می شود،

238
00:10:07,630 --> 00:10:09,870
اما ما فقط بازنویسی که اشاره گر

239
00:10:09,870 --> 00:10:11,170
برای اشاره به گره جدید

240
00:10:11,170 --> 00:10:14,230
بنابراین ما دیگر هیچ سرنخی که در آن D است در حافظه،

241
00:10:14,230 --> 00:10:17,020
و ما بقیه فهرست را از دست داده است.

242
00:10:17,020 --> 00:10:19,000
خوب در تمام.

243
00:10:19,000 --> 00:10:21,090
>> بنابراین، چگونه ما حق انجام این کار؟

244
00:10:22,360 --> 00:10:25,090
اول، نقطه بعدی اشاره گر گره جدید در D.

245
00:10:26,170 --> 00:10:28,990
در حال حاضر، هر دو گره جدید و C در کنار اشاره گر

246
00:10:28,990 --> 00:10:30,660
اشاره به همان گره، D،

247
00:10:30,660 --> 00:10:32,290
اما این خوب است.

248
00:10:32,290 --> 00:10:35,680
در حال حاضر ما می توانیم بعدی اشاره گر C در گره جدید اشاره کند.

249
00:10:37,450 --> 00:10:39,670
بنابراین، ما این کار را بدون از دست دادن هر گونه اطلاعات انجام می شود.

250
00:10:39,670 --> 00:10:42,280
در کد، C گره فعلی است

251
00:10:42,280 --> 00:10:45,540
که اشاره گر پیمایش خزنده با اشاره به

252
00:10:45,540 --> 00:10:50,400
و D توسط گره به میدان گره فعلی به آن اشاره شد نشان داده شده است،

253
00:10:50,400 --> 00:10:52,600
یا خزنده → بعدی.

254
00:10:52,600 --> 00:10:55,460
بنابراین، ما برای اولین بار مجموعه ای اشاره گر به گره جدید

255
00:10:55,460 --> 00:10:57,370
برای اشاره به خزنده → بعدی،

256
00:10:57,370 --> 00:11:00,880
راه همان است که ما بعدی اشاره گر new_node گفت: باید

257
00:11:00,880 --> 00:11:02,780
اشاره به D در تصویر است.

258
00:11:02,780 --> 00:11:04,540
سپس، ما می توانیم مجموعه ای اشاره گر به گره فعلی

259
00:11:04,540 --> 00:11:06,330
به گره جدید ما،

260
00:11:06,330 --> 00:11:10,980
همانطور که ما تا به حال صبر کنید تا نقطه C در طراحی new_node.

261
00:11:10,980 --> 00:11:12,250
در حال حاضر همه چیز در نظم، و ما را از دست دادن نیست

262
00:11:12,250 --> 00:11:14,490
پیگیری هر گونه داده، و ما قادر به فقط

263
00:11:14,490 --> 00:11:16,200
چوب گره جدید ما در وسط لیست

264
00:11:16,200 --> 00:11:19,330
بدون بازسازی همه چیز و یا حتی تغییر هر عنصر

265
00:11:19,330 --> 00:11:22,490
راه ما باید با یک آرایه با طول ثابت داشته است.

266
00:11:22,490 --> 00:11:26,020
>> بنابراین، لیست های پیوندی اساسی است، اما مهم، پویا ساختمان داده

267
00:11:26,020 --> 00:11:29,080
که هر دو مزایا و معایب

268
00:11:29,080 --> 00:11:31,260
در مقایسه به آرایه ها و ساختمان داده های دیگر،

269
00:11:31,260 --> 00:11:33,350
و به عنوان اغلب در مورد علم کامپیوتر،

270
00:11:33,350 --> 00:11:35,640
این مهم است که می دانم زمانی که به استفاده از هر ابزار،

271
00:11:35,640 --> 00:11:37,960
بنابراین شما می توانید از ابزار مناسب برای این کار سمت راست انتخاب کنید.

272
00:11:37,960 --> 00:11:40,060
>> برای تمرین بیشتر، سعی کنید به نوشتن توابع به

273
00:11:40,060 --> 00:11:42,080
حذف گره از لیست پیوندی -

274
00:11:42,080 --> 00:11:44,050
به یاد داشته باشید مراقب باشید در مورد که در آن شما تنظیم مجدد

275
00:11:44,050 --> 00:11:47,430
اشاره گر های بعدی خود را به اطمینان حاصل شود که شما یک تکه از لیست شما از دست دادن نیست -

276
00:11:47,430 --> 00:11:50,200
یا یک تابع به تعداد گره ها در یک لیست پیوندی،

277
00:11:50,200 --> 00:11:53,280
و یا یکی از سرگرم کننده، معکوس منظور از همه گره ها در یک لیست پیوندی.

278
00:11:53,280 --> 00:11:56,090
>> نام من ... است Steinkamp جکسون، این CS50 است.