1
00:00:00,000 --> 00:00:11,860

2
00:00:11,860 --> 00:00:13,120
>> SPEAKER 1: راست است، بنابراین ما می باشد.

3
00:00:13,120 --> 00:00:14,480
به CS50 خوش آمدید.

4
00:00:14,480 --> 00:00:16,510
این پایان هفته هفت است.

5
00:00:16,510 --> 00:00:20,200
به طوری که زمان گذشته به خاطر بیاورید، ما شروع
به دنبال کمی پیچیده تر

6
00:00:20,200 --> 00:00:21,100
ساختار دادهها.

7
00:00:21,100 --> 00:00:25,110
از آنجا که تا به حال، همه ما تا به حال واقعا
در اختیار ما این آرایه بود.

8
00:00:25,110 --> 00:00:29,340
>> اما قبل از اینکه ما آرایه به عنوان دور انداختن
همه که جالب توجه است، که در واقع آن را

9
00:00:29,340 --> 00:00:33,570
در واقع، آنچه که برخی از
علامت + از این داده ها ساده

10
00:00:33,570 --> 00:00:34,560
ساختار تا کنون؟

11
00:00:34,560 --> 00:00:36,110
آن را خوب در چیست؟

12
00:00:36,110 --> 00:00:39,450
تا آنجا که ما دیده ایم؟

13
00:00:39,450 --> 00:00:42,540
چه چیزی شما را؟

14
00:00:42,540 --> 00:00:44,028
هیچ چیز.

15
00:00:44,028 --> 00:00:45,020
>> دانشجو: [نامفهوم].

16
00:00:45,020 --> 00:00:45,395
>> SPEAKER 1: این چیه؟

17
00:00:45,395 --> 00:00:46,410
>> دانشجو: [نامفهوم].

18
00:00:46,410 --> 00:00:47,000
>> SPEAKER 1: اندازه ثابت.

19
00:00:47,000 --> 00:00:51,260
خوب، پس چرا اندازه ثابت هر چند خوب است؟

20
00:00:51,260 --> 00:00:53,180
>> دانشجو: [نامفهوم].

21
00:00:53,180 --> 00:00:56,240
>> SPEAKER 1: خوب، پس از آن کارآمد در
به این معنا که شما می توانید اختصاص

22
00:00:56,240 --> 00:01:00,070
مقدار ثابت از فضا، که امیدوارم
دقیقا به همان اندازه

23
00:01:00,070 --> 00:01:01,180
فضا به عنوان شما می خواهید.

24
00:01:01,180 --> 00:01:02,720
به طوری که می تواند کاملا به علاوه.

25
00:01:02,720 --> 00:01:06,530
>> یکی دیگر از سمت بالا یک آرایه چه خبر؟

26
00:01:06,530 --> 00:01:07,610
آره؟

27
00:01:07,610 --> 00:01:08,750
>> دانشجو: [نامفهوم].

28
00:01:08,750 --> 00:01:09,550
>> SPEAKER: 1 - با عرض پوزش؟

29
00:01:09,550 --> 00:01:11,270
>> دانشجو: [نامفهوم].

30
00:01:11,270 --> 00:01:13,620
>> SPEAKER 1: همه جعبه در حافظه
و یا در کنار یکدیگر.

31
00:01:13,620 --> 00:01:15,220
و این که مفید - چرا؟

32
00:01:15,220 --> 00:01:15,970
این کاملا درست است.

33
00:01:15,970 --> 00:01:18,611
اما چگونه می توان آن حقیقت ما بهره برداری؟

34
00:01:18,611 --> 00:01:21,500
>> دانشجو: [نامفهوم].

35
00:01:21,500 --> 00:01:24,490
>> SPEAKER 1: دقیقا، ما می توانید پیگیری
که در آن همه چیز فقط با دانستن

36
00:01:24,490 --> 00:01:28,560
یک آدرس، یعنی آدرس
اولین بایت آن تکه از حافظه است.

37
00:01:28,560 --> 00:01:30,420
و یا در مورد رشته،
آدرس اول

38
00:01:30,420 --> 00:01:31,460
کاراکتر در آن رشته است.

39
00:01:31,460 --> 00:01:33,330
و از آنجا، ما می توانید پیدا کنید
پایان رشته است.

40
00:01:33,330 --> 00:01:35,710
ما می توانیم عنصر دوم،
عنصر سوم، و غیره.

41
00:01:35,710 --> 00:01:38,740
>> و به این ترتیب راه فانتزی از توصیف این است که
از ویژگی های است که آرایه به ما بدهد

42
00:01:38,740 --> 00:01:40,020
با دسترسی تصادفی است.

43
00:01:40,020 --> 00:01:44,330
فقط با استفاده از براکت مربع
نماد و یک عدد باشد، شما می توانید پرش به

44
00:01:44,330 --> 00:01:48,070
یک عنصر خاص در آرایه
در زمان ثابت، O بزرگ

45
00:01:48,070 --> 00:01:49,810
یک، پس به صحبت می کنند.

46
00:01:49,810 --> 00:01:51,080
>> اما برخی از جنبه های منفی وجود دارد بوده است.

47
00:01:51,080 --> 00:01:53,110
چه آرایه انجام دهید نه به راحتی؟

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
آنچه در آن خوب نیست؟

50
00:01:57,170 --> 00:01:58,810
>> دانشجو: [نامفهوم].

51
00:01:58,810 --> 00:01:59,860
>> SPEAKER 1: این چیه؟

52
00:01:59,860 --> 00:02:00,530
>> دانشجو: [نامفهوم].

53
00:02:00,530 --> 00:02:01,460
>> SPEAKER 1: گسترش در اندازه.

54
00:02:01,460 --> 00:02:04,800
بنابراین جنبه های منفی از آرایه
دقیقا در مقابل از آنچه

55
00:02:04,800 --> 00:02:05,540
شاهد رشد آمارهای هستند.

56
00:02:05,540 --> 00:02:07,610
بنابراین یکی از جنبه های منفی است
که آن را به یک اندازه ثابت.

57
00:02:07,610 --> 00:02:09,400
بنابراین شما واقعا می تواند در آن رشد کند.

58
00:02:09,400 --> 00:02:13,510
شما می توانید یک تکه بزرگتر از دوباره اختصاص
حافظه، و سپس حرکت عناصر قدیمی

59
00:02:13,510 --> 00:02:14,460
به آرایه جدید.

60
00:02:14,460 --> 00:02:18,060
و سپس آرایه های قدیمی، برای
به عنوان مثال، با استفاده از malloc و یا مشابه

61
00:02:18,060 --> 00:02:21,180
بازتخصیص تابع نامیده می شود، که
حافظه reallocates.

62
00:02:21,180 --> 00:02:25,490
>> بازتخصیص، به عنوان یک کنار، تلاش می کند تا به شما بدهد
حافظه ای که در آینده به آرایه

63
00:02:25,490 --> 00:02:26,610
که شما در حال حاضر.

64
00:02:26,610 --> 00:02:28,740
اما ممکن است چیزهای حرکت
در اطراف در دسترس نباشد.

65
00:02:28,740 --> 00:02:30,710
اما در کوتاه مدت، که گران است، درست است؟

66
00:02:30,710 --> 00:02:33,440
از آنجا که اگر شما یک تکه از حافظه
این اندازه، اما شما واقعا می خواهید یک

67
00:02:33,440 --> 00:02:36,710
از این اندازه، و شما می خواهید برای حفظ
عناصر اصلی، شما باید

68
00:02:36,710 --> 00:02:40,510
تقریبا یک زمان فرایند کپی کردن خطی
که باید از اتفاق می افتد

69
00:02:40,510 --> 00:02:41,900
آرایه قدیمی به جدید.

70
00:02:41,900 --> 00:02:44,630
و واقعیت این است پرسیدن عامل
سیستم دوباره و دوباره و

71
00:02:44,630 --> 00:02:48,340
دوباره تکه های بزرگی از حافظه می توانید شروع به
به شما هزینه برخی از زمان نیز هست.

72
00:02:48,340 --> 00:02:52,250
پس از آن هم یک برکت و رحمت و لعنت در
پنهان، این واقعیت است که این آرایه ها

73
00:02:52,250 --> 00:02:53,860
اندازه ثابت هستند.

74
00:02:53,860 --> 00:02:56,790
اما در عوض چیزی است که اگر معرفی می کنیم
شبیه به این، که ما به نام وابسته به

75
00:02:56,790 --> 00:03:00,580
لیست، ما شاهد رشد آمارهای چند و
چند جنبه های منفی نیز هست.

76
00:03:00,580 --> 00:03:05,780
>> بنابراین یک لیست پیوندی است که به سادگی داده ها
ساختار از struct ها در C در این ساخته شده است

77
00:03:05,780 --> 00:03:09,850
مورد، که در آن ساختار، به یاد می آورند، فقط
یک ظرف برای یک یا چند خاص

78
00:03:09,850 --> 00:03:11,100
انواع متغیرها.

79
00:03:11,100 --> 00:03:16,110
در این مورد، چه نوع داده
به نظر می رسد داخل این ساختار که

80
00:03:16,110 --> 00:03:17,600
در زمان گذشته ما به نام گره؟

81
00:03:17,600 --> 00:03:19,380
هر یک از این مستطیل یک گره است.

82
00:03:19,380 --> 00:03:22,660
و هر یک از مستطیل کوچکتر
در داخل آن یک نوع داده است.

83
00:03:22,660 --> 00:03:25,300
چه نوع ما می گویند
آنها در روز دوشنبه بود؟

84
00:03:25,300 --> 00:03:26,478
آره؟

85
00:03:26,478 --> 00:03:27,870
>> دانشجو: [نامفهوم].

86
00:03:27,870 --> 00:03:30,721
>> SPEAKER 1: یک متغیر و یک اشاره گر، یا
به طور خاص، بین المللی، برای n

87
00:03:30,721 --> 00:03:32,180
و یک اشاره گر در پایین.

88
00:03:32,180 --> 00:03:35,360
هر دو از این اتفاق می افتد به 32 بیت، در
دست کم در یک کامپیوتر مثل این CS50

89
00:03:35,360 --> 00:03:37,980
لوازم خانگی، و به طوری که آنها هستید
به همان اندازه در اندازه کشیده شده است.

90
00:03:37,980 --> 00:03:42,260
>> پس چه با استفاده از اشاره گر
هر چند ظاهرا؟

91
00:03:42,260 --> 00:03:47,690
چرا اضافه کردن این فلش در حال حاضر وقتی که آرایه ها
بسیار زیبا و تمیز و ساده است؟

92
00:03:47,690 --> 00:03:50,460
آنچه که اشاره گر انجام
ما را در هر یک از این گره ها؟

93
00:03:50,460 --> 00:03:52,160
>> دانشجو: [نامفهوم].

94
00:03:52,160 --> 00:03:52,465
>> SPEAKER 1: دقیقا.

95
00:03:52,465 --> 00:03:54,120
آن را به شما گفتن که در آن
یک بعدی است.

96
00:03:54,120 --> 00:03:57,350
بنابراین من مرتب کردن بر اساس استفاده از قیاس
با استفاده از یک موضوع مرتب سازی بر اساس

97
00:03:57,350 --> 00:03:59,180
موضوع این گره با هم.

98
00:03:59,180 --> 00:04:01,760
و این دقیقا همان چیزی است که ما در حال انجام با
اشاره گر به دلیل هر یک از این

99
00:04:01,760 --> 00:04:06,360
تکه های حافظه ممکن است یا نه ممکن است
به هم پیوسته، پشت به پشت به پشت

100
00:04:06,360 --> 00:04:09,500
داخل RAM، چرا که هر زمانی که شما
تماس با malloc گفت، من به اندازه کافی

101
00:04:09,500 --> 00:04:12,510
کلمه در ادامه متن برای یک گره جدید، ممکن است
اینجا می شود و یا آن را ممکن است در اینجا.

102
00:04:12,510 --> 00:04:13,120
این ممکن است به اینجا.

103
00:04:13,120 --> 00:04:13,730
این ممکن است به اینجا.

104
00:04:13,730 --> 00:04:14,640
شما فقط نمی دانم.

105
00:04:14,640 --> 00:04:17,880
>> اما با استفاده از اشاره گرها در آدرس
این گره ها، شما می توانید کوک آنها را

106
00:04:17,880 --> 00:04:22,370
با هم در راه است که به نظر می رسد بصری
مانند یک لیست حتی اگر این چیزها

107
00:04:22,370 --> 00:04:26,770
همه از در سراسر یک یا خود را گسترش
دو یا چهار گیگابایت رم

108
00:04:26,770 --> 00:04:28,760
در داخل کامپیوتر خود تغییر دهید.

109
00:04:28,760 --> 00:04:33,230
>> بنابراین در حرکت نزولی، پس از آن،
یک لیست پیوندی چیست؟

110
00:04:33,230 --> 00:04:34,670
قیمت ما چه خبر
ظاهرا پرداخت؟

111
00:04:34,670 --> 00:04:36,010
>> دانشجو: [نامفهوم].

112
00:04:36,010 --> 00:04:36,920
>> SPEAKER 1: فضای بیشتر، درست است؟

113
00:04:36,920 --> 00:04:39,340
ایم، در این مورد، دو برابر مقدار
فضا از آنجا که ما رفته

114
00:04:39,340 --> 00:04:43,500
از 32 بیت برای هر گره، برای هر
INT، بنابراین در حال حاضر 64 بیت چون ما به

115
00:04:43,500 --> 00:04:45,050
نگه دارید در اطراف یک اشاره گر نیز هست.

116
00:04:45,050 --> 00:04:48,860
شما دریافت می کنید بهره وری بیشتر اگر ساختار خود را
بزرگتر از این چیزی که ساده است.

117
00:04:48,860 --> 00:04:52,020
در واقع اگر شما یک دانش آموز در داخل
که یک زن و شوهر از رشته ها است

118
00:04:52,020 --> 00:04:55,430
نام و خانه، شاید شماره ID،
شاید برخی از زمینه های دیگر در دسترس نباشد.

119
00:04:55,430 --> 00:04:59,000
>> بنابراین اگر شما ساختار بزرگ به اندازه کافی،
پس از آن شاید هزینه از اشاره گر است

120
00:04:59,000 --> 00:05:00,010
نه چنین معامله بزرگ است.

121
00:05:00,010 --> 00:05:03,570
این است که کمی در مورد گوشه ای است که در
ما در حال ذخیره سازی چنین بدوی ساده

122
00:05:03,570 --> 00:05:04,760
در داخل لیست پیوندی.

123
00:05:04,760 --> 00:05:05,790
اما نکته همان است.

124
00:05:05,790 --> 00:05:08,230
شما قطعا هزینه های بیشتر
حافظه است، اما شما در حال گرفتن

125
00:05:08,230 --> 00:05:08,990
انعطاف پذیری.

126
00:05:08,990 --> 00:05:12,280
از آنجا که در حال حاضر اگر من می خواهم برای اضافه کردن یک عنصر
در ابتدای این لیست،

127
00:05:12,280 --> 00:05:14,340
من به اختصاص یک گره جدید.

128
00:05:14,340 --> 00:05:17,180
و من باید فقط کسانی که به روز رسانی
فلش به نحوی فقط در حال حرکت

129
00:05:17,180 --> 00:05:17,980
برخی از اشاره گرها در اطراف.

130
00:05:17,980 --> 00:05:20,580
>> اگر من می خواهم برای قرار دادن چیزی به
وسط لیست، من لازم نیست

131
00:05:20,580 --> 00:05:24,410
فشار هر کس کنار مثل ما در
هفته گذشته با داوطلبان ما که

132
00:05:24,410 --> 00:05:25,700
نشان داده یک آرایه.

133
00:05:25,700 --> 00:05:29,470
من فقط می توانید اختصاص یک گره جدید
پس از آن درست نقطه مقابل فلش در

134
00:05:29,470 --> 00:05:32,290
جهات مختلف به دلیل آن را نمی کند
به در واقعی باقی می ماند

135
00:05:32,290 --> 00:05:35,670
حافظه یک خط درست مثل من کشیده ام
آن را در اینجا بر روی صفحه نمایش.

136
00:05:35,670 --> 00:05:38,400
>> و سپس در نهایت، اگر شما می خواهید وارد کنید
چیزی در انتهای لیست، آن را

137
00:05:38,400 --> 00:05:39,210
حتی ساده تر.

138
00:05:39,210 --> 00:05:43,320
این مرتب کردن بر اساس نماد دلخواه است،
اما اشاره گر 34 را یک حدس است.

139
00:05:43,320 --> 00:05:46,710
ارزش اشاره گر آن چیست
مرتب کردن بر اساس احتمال کشیده مثل قدیمی

140
00:05:46,710 --> 00:05:47,700
آنتن مدرسه وجود دارد؟

141
00:05:47,700 --> 00:05:48,920
>> دانشجو: [نامفهوم].

142
00:05:48,920 --> 00:05:49,900
>> SPEAKER 1: احتمالا صفر است.

143
00:05:49,900 --> 00:05:52,710
و در واقع این است که یک نویسنده
نمایندگی از تهی.

144
00:05:52,710 --> 00:05:56,310
و آن را به صفر است زیرا شما کاملا
باید بدانید که پایان مرتبط

145
00:05:56,310 --> 00:06:00,050
لیست است، تا مبادا شما را زیر و
به دنبال و پس از این فلش

146
00:06:00,050 --> 00:06:01,170
به برخی از ارزش زباله.

147
00:06:01,170 --> 00:06:06,230
بنابراین تهی دلالت خواهد کرد که وجود ندارد
گره های بیشتری را به سمت راست شماره 34،

148
00:06:06,230 --> 00:06:07,200
در این مورد.

149
00:06:07,200 --> 00:06:10,270
>> بنابراین ما پیشنهاد می کنند که ما می توانیم پیاده سازی
این گره در کد.

150
00:06:10,270 --> 00:06:12,130
و ما این نوع را دیده ام
نحو قبل از.

151
00:06:12,130 --> 00:06:15,090
Typedef فقط تعریف یک نوع جدید برای
ما، به ما می دهد مترادف مثل

152
00:06:15,090 --> 00:06:17,100
رشته کاراکتر * بود.

153
00:06:17,100 --> 00:06:21,030
در این مورد، آن را به ما بدهد
نماد مختصر به طوری که گره ساختار

154
00:06:21,030 --> 00:06:24,010
می توانید به جای فقط به عنوان نوشته شده است
گره، که یک پاک کننده زیادی.

155
00:06:24,010 --> 00:06:25,360
این بسیار کمتر دراز است.

156
00:06:25,360 --> 00:06:30,080
>> در داخل از یک گره است ظاهرا بین المللی
N نامیده می شود، و سپس یک گره در ساختار *

157
00:06:30,080 --> 00:06:34,670
که به معنی دقیقا همان چیزی است که ما می خواستیم
فلش به معنی، یک اشاره گر به دیگری

158
00:06:34,670 --> 00:06:36,940
گره از نوع داده های یکسان.

159
00:06:36,940 --> 00:06:40,300
و پیشنهاد می کنم که ما می توانیم پیاده سازی
تابع جستجو مانند این، که در

160
00:06:40,300 --> 00:06:41,890
نگاه اول ممکن است به نظر می رسد
کمی پیچیده است.

161
00:06:41,890 --> 00:06:43,330
اما اجازه دهید آن را در متن ببینید.

162
00:06:43,330 --> 00:06:45,480
>> به من اجازه رفتن را به دستگاه اینجا.

163
00:06:45,480 --> 00:06:48,460
اجازه دهید من باز کردن یک فایل به نام
نقطه صفر ساعت.

164
00:06:48,460 --> 00:06:53,950
و تنها شامل تعریف ما
فقط یک لحظه پیش برای این داده ها را دیدم

165
00:06:53,950 --> 00:06:55,390
نوع گره نامیده می شود.

166
00:06:55,390 --> 00:06:57,350
بنابراین ما این است که به یک فایل نقطه ساعت قرار داده است.

167
00:06:57,350 --> 00:07:01,430
>> و به عنوان یک به کنار، حتی اگر این
برنامه ای است که شما خواهید دید

168
00:07:01,430 --> 00:07:05,410
نه همه که پیچیده است، آن در واقع
کنوانسیون در هنگام نوشتن یک برنامه به

169
00:07:05,410 --> 00:07:10,270
قرار دادن چیزهایی مثل انواع داده ها، به جلو
ثابت گاهی اوقات، در داخل خود را

170
00:07:10,270 --> 00:07:13,210
فایل هدر و نه لزوما در
فایل C خود، قطعا هنگامی که خود را

171
00:07:13,210 --> 00:07:17,370
برنامه های بزرگ تر و بزرگ تر است، به طوری که
شما می دانید که در آن به نگاه هر دو برای

172
00:07:17,370 --> 00:07:20,840
مستندات در برخی موارد، یا
اصول اولیه مانند این،

173
00:07:20,840 --> 00:07:22,360
تعریف برخی از نوع.

174
00:07:22,360 --> 00:07:25,680
>> اگر من در حال حاضر باز کردن لیست صفر نقطه
ج، متوجه چند چیز.

175
00:07:25,680 --> 00:07:29,090
این شامل چند فایل هدر،
که ما قبلا دیده ام.

176
00:07:29,090 --> 00:07:31,980
این شامل فایل هدر خود را.

177
00:07:31,980 --> 00:07:35,200
>> و به عنوان یک کنار، چرا که دو برابر
به نقل از اینجا، به عنوان مخالف به زاویه

178
00:07:35,200 --> 00:07:38,340
براکت روی خط که
من آنجا هایلایت شده اید؟

179
00:07:38,340 --> 00:07:39,180
>> دانشجو: [نامفهوم].

180
00:07:39,180 --> 00:07:40,460
>> SPEAKER 1: بله پس از آن یک فایل محلی است.

181
00:07:40,460 --> 00:07:44,300
بنابراین اگر آن را در یک فایل محلی خود را در اینجا
در خط 15 به عنوان مثال، شما با استفاده از

182
00:07:44,300 --> 00:07:46,570
نقل قول دوتایی به جای
براکت زاویه دار.

183
00:07:46,570 --> 00:07:48,270
>> در حال حاضر این نوع جالب است.

184
00:07:48,270 --> 00:07:51,830
توجه کنید که من اعلام کرده ام جهانی
متغیر در این برنامه در خط 18

185
00:07:51,830 --> 00:07:55,910
نامیده می شود برای اولین بار، این ایده این است
رفتن به یک اشاره گر به اول

186
00:07:55,910 --> 00:07:59,190
گره در لیست پیوندی من، و من
مقداردهی اولیه آن را به تهی، چون من

187
00:07:59,190 --> 00:08:02,310
اختصاص داده شده هیچ واقعی
گره فقط رتبهدهی نشده است.

188
00:08:02,310 --> 00:08:07,570
>> پس این نشان دهنده، pictorially، آنچه که ما
یک لحظه پیش در تصویر به عنوان شاهد

189
00:08:07,570 --> 00:08:10,090
که اشاره گر در دور
سمت چپ دست.

190
00:08:10,090 --> 00:08:12,260
بنابراین در حال حاضر، که اشاره گر
فلش ندارد.

191
00:08:12,260 --> 00:08:14,590
آن را به جای فقط تهی است.

192
00:08:14,590 --> 00:08:17,880
اما آن را نشان دهنده چه خواهد بود
آدرس اولین واقعی

193
00:08:17,880 --> 00:08:19,480
گره در این لیست.

194
00:08:19,480 --> 00:08:22,120
بنابراین من اجرا کرده ام آن است که یک جهانی
چون، همانطور که شما خواهید دید، این همه

195
00:08:22,120 --> 00:08:25,310
برنامه در زندگی پیاده سازی
لیست پیوندی برای من.

196
00:08:25,310 --> 00:08:27,050
>> حالا من چند نمونه در اینجا.

197
00:08:27,050 --> 00:08:31,190
من تصمیم به پیاده سازی ویژگی های مانند
حذف، درج، جستجو، و

198
00:08:31,190 --> 00:08:31,740
پیمایش -

199
00:08:31,740 --> 00:08:35,210
آخرین پیاده روی در سراسر
لیست، چاپ کردن عناصر آن.

200
00:08:35,210 --> 00:08:36,750
و در حال حاضر در اینجا معمول اصلی من است.

201
00:08:36,750 --> 00:08:39,890
و ما زمان زیادی را صرف
این از آنجایی که این مرتب کردن بر اساس، امیدوارم

202
00:08:39,890 --> 00:08:41,780
کلاه های قدیمی در حال حاضر.

203
00:08:41,780 --> 00:08:45,370
>> من قصد دارم به انجام موارد زیر،
در حالی که کاربر همکاری می کند.

204
00:08:45,370 --> 00:08:47,300
بنابراین یکی، من قصد دارم برای چاپ
از این منو.

205
00:08:47,300 --> 00:08:49,420
و من آن را به عنوان فرمت ام
پاک به عنوان من می توانم.

206
00:08:49,420 --> 00:08:52,240
در صورتی که کاربر در انواع در یکی، این بدان معناست که
آنها می خواهند چیزی را حذف کنید.

207
00:08:52,240 --> 00:08:54,560
در صورتی که کاربر در انواع در دو، این بدان معناست که
آنها می خواهند به قرار دادن چیزی.

208
00:08:54,560 --> 00:08:55,930
و غیره.

209
00:08:55,930 --> 00:08:58,270
من قصد دارم پس از آن بی درنگ
پس از آن برای یک دستور.

210
00:08:58,270 --> 00:08:59,300
و سپس من قصد دارم به استفاده از GetInt.

211
00:08:59,300 --> 00:09:02,790
>> پس این است که یک واقعا menuing ساده
رابط که در آن شما فقط باید به نوع

212
00:09:02,790 --> 00:09:05,270
نقشه شماره یک
از این دستورات است.

213
00:09:05,270 --> 00:09:08,730
و در حال حاضر من یک سوئیچ خوب تمیز
بیانیه ای که به سوئیچ

214
00:09:08,730 --> 00:09:10,090
هر کاربر تایپ شوید.

215
00:09:10,090 --> 00:09:12,180
و اگر آنها به تایپ به یکی، من
تماس حذف و شکستن.

216
00:09:12,180 --> 00:09:14,380
اگر آنها تایپ دو، من
تماس برای درج و برای شکستن.

217
00:09:14,380 --> 00:09:16,490
>> و در حال حاضر متوجه من هر قرار داده ام
این در همان خط.

218
00:09:16,490 --> 00:09:18,360
این فقط یک تصمیم سبکی است.

219
00:09:18,360 --> 00:09:20,210
به طور معمول ما چیزی است که دیده ام
مثل این.

220
00:09:20,210 --> 00:09:23,260
اما من فقط تصمیم گرفت، رک و پوست کنده، برنامه های من
نگاه بیشتر قابل خواندن است به دلیل

221
00:09:23,260 --> 00:09:25,980
تنها چهار مورد بود
فقط آن را شبیه به این لیست است.

222
00:09:25,980 --> 00:09:28,360
کاملا مشروع استفاده از سبک.

223
00:09:28,360 --> 00:09:31,480
و من قصد دارم برای انجام این کار تا زمانی که
کاربر صفر تایپ نیست، که من

224
00:09:31,480 --> 00:09:33,910
تصمیم این معنی خواهد بود که آنها می خواهند به ترک.

225
00:09:33,910 --> 00:09:36,630
>> بنابراین در حال حاضر متوجه آنچه که من هستم
رفتن برای انجام در اینجا.

226
00:09:36,630 --> 00:09:38,650
من قصد دارم برای آزاد کردن لیست ظاهرا.

227
00:09:38,650 --> 00:09:40,230
اما بیشتر در مورد که در یک لحظه.

228
00:09:40,230 --> 00:09:41,640
بیایید برای اولین بار اجرای این برنامه.

229
00:09:41,640 --> 00:09:45,250
پس اجازه دهید من یک ترمینال بزرگتر
پنجره، نقطه بریده بریده لیست 0.

230
00:09:45,250 --> 00:09:49,510
من قصد دارم به جلو بروید و وارد
تایپ دو، مانند 50، و در حال حاضر

231
00:09:49,510 --> 00:09:51,590
شما خواهید دید این لیست در حال حاضر 50.

232
00:09:51,590 --> 00:09:53,380
و من فقط بر میگردین بالا کمی.

233
00:09:53,380 --> 00:09:55,940
بنابراین در حال حاضر متوجه این فهرست شامل
شماره 50.

234
00:09:55,940 --> 00:09:58,220
>> اجازه دهید قرار دادن دیگری با در نظر گرفتن دو.

235
00:09:58,220 --> 00:10:01,630
نوع در تعدادی مانند یک.

236
00:10:01,630 --> 00:10:03,940
لیست در حال حاضر، و پس از 50.

237
00:10:03,940 --> 00:10:06,020
بنابراین این فقط یک نمایندگی متنی
از لیست.

238
00:10:06,020 --> 00:10:10,550
و اجازه دهید وارد کردن شماره یک بیشتر شبیه
شماره 42، است که امیدوارم

239
00:10:10,550 --> 00:10:14,620
رفتن به تا پایان در وسط، به دلیل
این برنامه در نوع خاص آن

240
00:10:14,620 --> 00:10:16,320
عناصر آن را به عنوان آنها را درج.

241
00:10:16,320 --> 00:10:17,220
بنابراین ما آن را داشته باشد.

242
00:10:17,220 --> 00:10:20,730
برنامه فوق العاده ساده است که می تواند
کاملا یک آرایه استفاده کرده اند، اما من

243
00:10:20,730 --> 00:10:23,280
اتفاق می افتد به توان با استفاده از لیست پیوندی
بنابراین من می تواند به صورت پویا

244
00:10:23,280 --> 00:10:24,610
رشد و کوچک شدن آن.

245
00:10:24,610 --> 00:10:28,470
>> پس را برای جستجو یک نگاه کنیم، اگر من
دستور سوم را اجرا کنید، من می خواهم برای جستجو

246
00:10:28,470 --> 00:10:31,040
، می گویند، شماره 43.

247
00:10:31,040 --> 00:10:34,190
و هیچ چیز ظاهرا پیدا شد،
چون من پشت کردم هیچ پاسخ.

248
00:10:34,190 --> 00:10:35,010
بنابراین اجازه دهید این کار را دوباره انجام.

249
00:10:35,010 --> 00:10:35,690
جستجو کنید.

250
00:10:35,690 --> 00:10:39,520
جستجو اجازه دهید برای 50، یا به جای جستجو
42، که تا به خوبی

251
00:10:39,520 --> 00:10:40,850
معنای ظریف کمی.

252
00:10:40,850 --> 00:10:42,610
و من معنای زندگی وجود دارد در بر داشت.

253
00:10:42,610 --> 00:10:44,990
شماره 42، اگر شما نمی دانید
مرجع، آن را گوگل.

254
00:10:44,990 --> 00:10:45,350
بسیار خوب.

255
00:10:45,350 --> 00:10:47,130
بنابراین آنچه که این برنامه را برای من انجام می شود؟

256
00:10:47,130 --> 00:10:50,660
این فقط به من اجازه درج در نتیجه
دور و جستجو برای عناصر.

257
00:10:50,660 --> 00:10:53,650
>> بیایید سریع به جلو، و سپس، به
که عملکرد ما در نگاه

258
00:10:53,650 --> 00:10:55,360
در روز دوشنبه به عنوان یک تیزر.

259
00:10:55,360 --> 00:10:59,620
بنابراین این تابع، من ادعا می کنند، جستجو برای
یک عنصر در لیست را با اولین

260
00:10:59,620 --> 00:11:03,830
، باعث کاربر و پس از آن خواستار
GetInt برای به دست آوردن یک int واقعی

261
00:11:03,830 --> 00:11:05,060
که شما می خواهید برای جستجو.

262
00:11:05,060 --> 00:11:06,460
>> سپس این اطلاع می دهد.

263
00:11:06,460 --> 00:11:10,690
من قصد دارم برای ایجاد یک متغیر موقت
در خط 188 به نام اشاره گر -

264
00:11:10,690 --> 00:11:11,270
PTR -

265
00:11:11,270 --> 00:11:12,440
می تواند آن را به هر چیزی.

266
00:11:12,440 --> 00:11:16,140
و آن را یک اشاره گر به گره
چون من گفتم گره * وجود دارد.

267
00:11:16,140 --> 00:11:19,900
و من مقدار دهی اولیه آن را به صورت برابر
برای اولین بار است که من به طور موثر

268
00:11:19,900 --> 00:11:22,860
انگشت، پس به صحبت می کنند، در تاریخ بسیار
اولین عنصر از لیست.

269
00:11:22,860 --> 00:11:27,460
بنابراین اگر دست راست من در اینجا این است PTR من
اشاره به همان چیزی است که برای اولین بار

270
00:11:27,460 --> 00:11:28,670
است اشاره.

271
00:11:28,670 --> 00:11:31,430
>> بنابراین در حال حاضر در کد،
چه اتفاقی می افتد بعدی -

272
00:11:31,430 --> 00:11:35,070
این یک الگوی مشترک زمانی است که تکرار
بیش از یک ساختار مانند یک

273
00:11:35,070 --> 00:11:35,970
لیست پیوندی.

274
00:11:35,970 --> 00:11:40,410
من قصد دارم به انجام موارد زیر در حالی که
اشاره گر برابر است به تهی بنابراین نیست در حالی که

275
00:11:40,410 --> 00:11:47,530
انگشت من است اشاره در برخی از تهی
ارزش، اگر اشاره گر فلش N برابر N است.

276
00:11:47,530 --> 00:11:52,290
ما اول متوجه خواهید شد که n است
کاربر تایپ در هر GetInts ها تماس بگیرید در اینجا.

277
00:11:52,290 --> 00:11:54,280
>> و اشاره گر فلش N یعنی چه؟

278
00:11:54,280 --> 00:11:59,020
خوب اگر ما به عقب برویم به تصویر در اینجا،
اگر من یک انگشت اشاره در

279
00:11:59,020 --> 00:12:02,960
که اولین گره حاوی نه،
فلش اساسا به معنی رفتن به آن

280
00:12:02,960 --> 00:12:08,860
گره و گرفتن مقدار در محل سکونت،
در این مورد، زمینه داده نامیده می شود.

281
00:12:08,860 --> 00:12:14,120
>> همانطور که به کنار - و ما شاهد این یک زن و شوهر
هفته پیش زمانی که کسی که خواسته -

282
00:12:14,120 --> 00:12:18,840
این نحو جدید است، اما آن را نمی کند
قدرت به ما بدهد که ما

283
00:12:18,840 --> 00:12:20,040
در حال حاضر نیست داشته باشد.

284
00:12:20,040 --> 00:12:25,325
این عبارت معادل با استفاده از چه بود
دات نت نویسی و ستاره یک زن و شوهر

285
00:12:25,325 --> 00:12:29,490
هفته پیش هنگامی که ما پوست کنده
این لایه کمی قبل از موعد مقرر؟

286
00:12:29,490 --> 00:12:31,780
>> دانشجو: [نامفهوم].

287
00:12:31,780 --> 00:12:38,880
>> SPEAKER 1: دقیقا، این ستاره بود، و
سپس آن را ستاره دات نفر بود، با

288
00:12:38,880 --> 00:12:41,930
پرانتز در اینجا، که به نظر می رسد،
رک و پوست کنده، من فکر می کنم بسیاری

289
00:12:41,930 --> 00:12:43,320
بیشتر مرموز به خواندن.

290
00:12:43,320 --> 00:12:46,270
اما ستاره اشاره گر، مثل همیشه،
معنی وجود دارد.

291
00:12:46,270 --> 00:12:49,090
و هنگامی که شما وجود دارد، چه داده
زمینه می خواهید برای دسترسی به؟

292
00:12:49,090 --> 00:12:52,730
خوب شما استفاده از نماد نقطه برای دسترسی به
یک فیلد داده از struct ها، و من

293
00:12:52,730 --> 00:12:54,140
به طور خاص می خواهید N.

294
00:12:54,140 --> 00:12:56,240
>> صادقانه بگویم، من این استدلال
فقط سخت تر به خواندن.

295
00:12:56,240 --> 00:12:58,080
آن را سخت تر به یاد داشته باشید که در آن
آیا پرانتز،

296
00:12:58,080 --> 00:12:59,030
ستاره و همه از آن.

297
00:12:59,030 --> 00:13:02,150
بنابراین جهان به تصویب رسید برخی نحوی
شکر، پس به صحبت می کنند.

298
00:13:02,150 --> 00:13:04,740
فقط یک راه های سکسی از گفتن،
این معادل است، و

299
00:13:04,740 --> 00:13:05,970
شاید بیشتر بصری.

300
00:13:05,970 --> 00:13:09,600
اگر اشاره گر است که در واقع یک اشاره گر،
فلش استفاده از نماد به وجود دارد و پیدا کردن

301
00:13:09,600 --> 00:13:11,890
زمینه در این مورد به نام.

302
00:13:11,890 --> 00:13:13,660
>> بنابراین اگر آن را پیدا کنم، متوجه آنچه که من انجام می دهند.

303
00:13:13,660 --> 00:13:17,430
من به سادگی نسخه قابل چاپ کردن، متوجه شدم درصد من،
متصل کردن در ارزش که int.

304
00:13:17,430 --> 00:13:20,730
من اسمش خواب برای یک ثانیه فقط به نوع
از چیزهایی مکث بر روی صفحه نمایش

305
00:13:20,730 --> 00:13:22,900
کاربر دوم به جذب
فقط چه اتفاقی افتاده.

306
00:13:22,900 --> 00:13:24,290
و سپس من را بشکند.

307
00:13:24,290 --> 00:13:26,330
در غیر این صورت، چه می توانم بکنم؟

308
00:13:26,330 --> 00:13:30,960
اشاره گر به روز رسانی من برابر
اشاره گر arrow بعدی.

309
00:13:30,960 --> 00:13:35,840
>> بنابراین فقط به روشن است، این به این معنی بروید
، با استفاده از نماد قدیمی مدرسه من وجود دارد.

310
00:13:35,840 --> 00:13:39,580
بنابراین این حالت فقط بدان معناست برای رفتن به هر
شما در حال اشاره در، که در بسیار

311
00:13:39,580 --> 00:13:43,660
مورد اول این است که من با اشاره به
ساختار نه در آن.

312
00:13:43,660 --> 00:13:44,510
بنابراین من آنجا رفته ام.

313
00:13:44,510 --> 00:13:47,880
و پس از آن نماد نقطه به معنای،
دریافت ارزش در بعدی.

314
00:13:47,880 --> 00:13:50,470
>> اما ارزش، حتی اگر آن را کشیده
به عنوان باریک، فقط یک عدد است.

315
00:13:50,470 --> 00:13:51,720
این یک آدرس عددی است.

316
00:13:51,720 --> 00:13:55,670
بنابراین این یک خط کد، اعم از
نوشته شده شبیه به این، مرموز تر

317
00:13:55,670 --> 00:14:00,190
راه، و یا شبیه به این، کمی بیشتر
راه بصری، فقط به معنای حرکت دست من

318
00:14:00,190 --> 00:14:03,460
از اولین گره به یک بعدی،
و سپس یکی بعد، و پس از آن

319
00:14:03,460 --> 00:14:05,320
یکی از آینده، و غیره.

320
00:14:05,320 --> 00:14:09,920
>> بنابراین ما نمی خواهد از سوی دیگر ساکن
پیاده سازی شده از درج و حذف

321
00:14:09,920 --> 00:14:14,030
و پیمایش، دو مورد اول از
که نسبتا درگیر شده است.

322
00:14:14,030 --> 00:14:17,010
و من فکر می کنم آن را بسیار آسان برای به دست آوردن
از دست رفته در هنگام انجام آن را بطور شفاهی.

323
00:14:17,010 --> 00:14:19,890
اما آنچه ما در اینجا می توانید انجام دهید این است
سعی برای تعیین چگونگی

324
00:14:19,890 --> 00:14:21,640
بهترین به انجام این کار بصری.

325
00:14:21,640 --> 00:14:24,800
از آنجا که من می خواهم پیشنهاد می کنند که اگر ما
می خواهم به قرار دادن عناصر به این

326
00:14:24,800 --> 00:14:26,680
لیست موجود، که
دارای پنج عنصر -

327
00:14:26,680 --> 00:14:29,530
9، 17، 22، 26، و 33 -

328
00:14:29,530 --> 00:14:33,300
اگر من قرار بود به پیاده سازی این
کد، من نیاز به در نظر گرفتن چگونه به

329
00:14:33,300 --> 00:14:34,160
در مورد انجام این کار است.

330
00:14:34,160 --> 00:14:37,720
>> و من می خواهم پیشنهاد در نظر گرفتن گام های کودک
به موجب آن، در این مورد منظورم این است که چه هستند

331
00:14:37,720 --> 00:14:41,090
حالات ممکن است که ما
ممکن است به طور کلی روبرو می شوند؟

332
00:14:41,090 --> 00:14:44,120
هنگام اجرای قرار دادن برای مرتبط
لیست است، این فقط اتفاق می افتد به عنوان یک

333
00:14:44,120 --> 00:14:46,090
مثال خاص از اندازه پنج.

334
00:14:46,090 --> 00:14:50,420
خوب اگر شما می خواهید برای وارد کردن یک عدد،
می گویند که شماره یک، و

335
00:14:50,420 --> 00:14:53,380
حفظ نظم مرتب شده باشد، که در آن
به وضوح می کند شماره یک نیاز به.

336
00:14:53,380 --> 00:14:55,686
در این مثال خاص؟

337
00:14:55,686 --> 00:14:56,840
در ابتدا می خواهم.

338
00:14:56,840 --> 00:15:00,030
>> اما آنچه جالب است این است که وجود دارد
اگر شما می خواهید به قرار دادن یکی به این

339
00:15:00,030 --> 00:15:04,100
لیست، آنچه اشاره گر خاص نیاز دارد
به ظاهرا به روز شده؟

340
00:15:04,100 --> 00:15:04,610
برای اولین بار.

341
00:15:04,610 --> 00:15:07,830
بنابراین می خواهم بگویم، این اولین مورد است
که ما ممکن است بخواهید در نظر گرفتن،

342
00:15:07,830 --> 00:15:11,140
سناریو شامل قرار دادن در
آغاز از لیست.

343
00:15:11,140 --> 00:15:15,400
>> بیایید شهامت شاید به عنوان آسان و یا حتی
مورد ساده تر، نسبتا صحبت کردن.

344
00:15:15,400 --> 00:15:18,110
فرض کنید من می خواهم برای وارد کردن
شماره 35 به منظور طبقه بندی شده اند.

345
00:15:18,110 --> 00:15:20,600
آن را به وضوح بیش از وجود دارد تعلق دارد.

346
00:15:20,600 --> 00:15:25,320
بنابراین چه چیزی اشاره گر بدیهی است که رفتن به
در این سناریو به روز شده؟

347
00:15:25,320 --> 00:15:30,060
اشاره گر 34 تبدیل شدن به تهی نیست
اما آدرس از ساختارها (struct)

348
00:15:30,060 --> 00:15:31,800
حاوی تعداد 35.

349
00:15:31,800 --> 00:15:32,750
به طوری که دو مورد است.

350
00:15:32,750 --> 00:15:36,190
بنابراین در حال حاضر، من نوعی از کوانتیزه هستم
چقدر کار من باید انجام دهید در اینجا.

351
00:15:36,190 --> 00:15:39,880
>> و در نهایت، در مورد متوسط ​​آشکار است
در واقع، در وسط، اگر من می خواهم به

352
00:15:39,880 --> 00:15:45,870
قرار دادن چیزی مانند 23، است که می رود
بین 23 و 26 است، اما

353
00:15:45,870 --> 00:15:48,680
در حال حاضر همه چیز کمی بیشتر
درگیر زیرا آنچه

354
00:15:48,680 --> 00:15:52,800
اشاره گر نیاز به تغییر دارند؟

355
00:15:52,800 --> 00:15:56,680
بنابراین 22 بدیهی است که نیاز به تغییر
چرا که او نه می تواند تا 26 نقطه دیگر.

356
00:15:56,680 --> 00:16:00,320
او نیاز به اشاره به گره جدید است که
من باید با تماس با اختصاص

357
00:16:00,320 --> 00:16:01,770
malloc و یا برخی از معادل آن.

358
00:16:01,770 --> 00:16:05,990
>> اما پس از آن من هم نیاز است که گره جدید، 23
در این مورد، به اشاره گر خود را

359
00:16:05,990 --> 00:16:07,870
اشاره در آنها؟

360
00:16:07,870 --> 00:16:08,560
26.

361
00:16:08,560 --> 00:16:10,380
و رفتن به یک وجود دارد
منظور از عملیات در اینجا.

362
00:16:10,380 --> 00:16:13,410
از آنجا اگر من این کار احمقانه، و من
برای شروع عنوان مثال در ابتدای

363
00:16:13,410 --> 00:16:16,040
لیست، و هدف من این است به قرار دادن 23.

364
00:16:16,040 --> 00:16:18,610
و من چک می کنم، آن را متعلق
در اینجا، در نزدیکی نه؟

365
00:16:18,610 --> 00:16:18,950
شماره

366
00:16:18,950 --> 00:16:20,670
آیا این به اینجا تعلق، در کنار 17؟

367
00:16:20,670 --> 00:16:20,940
شماره

368
00:16:20,940 --> 00:16:22,530
آیا آن تعلق دارد در اینجا در کنار به 22؟

369
00:16:22,530 --> 00:16:23,300
بله.

370
00:16:23,300 --> 00:16:26,400
>> در حال حاضر اگر من در اینجا احمق هستم، و نه
فکر این را از طریق، من ممکن است

371
00:16:26,400 --> 00:16:28,320
تخصیص گره جدید من برای 23.

372
00:16:28,320 --> 00:16:32,080
من ممکن است اشاره گر از به روز رسانی
گره به نام 22، با اشاره

373
00:16:32,080 --> 00:16:33,080
آن را در گره جدید است.

374
00:16:33,080 --> 00:16:36,140
و سپس آنچه را می توانم برای به روز رسانی
اشاره گر به گره های جدید می شود؟

375
00:16:36,140 --> 00:16:38,120
>> دانشجو: [نامفهوم].

376
00:16:38,120 --> 00:16:38,385
>> SPEAKER 1: دقیقا.

377
00:16:38,385 --> 00:16:39,710
اشاره در 26.

378
00:16:39,710 --> 00:16:45,590
اما dammit اگر من در حال حاضر به روز رسانی
اشاره گر 22 را به نقطه در این مرد، و

379
00:16:45,590 --> 00:16:48,260
در حال حاضر من یتیم، بقیه
لیست، پس به صحبت می کنند.

380
00:16:48,260 --> 00:16:52,140
بنابراین منظور از عملیات در اینجا
رفتن مهم است.

381
00:16:52,140 --> 00:16:55,100
>> برای انجام این کار می تواند از من سرقت،
گویند، شش داوطلبان.

382
00:16:55,100 --> 00:16:57,650
و بیایید ببینید که اگر ما نمی توانیم این کار را انجام
بصری به جای کد عاقلانه.

383
00:16:57,650 --> 00:16:59,330
و ما باید برخی از استرس های دوست داشتنی
توپ را برای شما امروز.

384
00:16:59,330 --> 00:17:02,510
خوب، چگونه در مورد یک، دو، در
پشت - در پایان وجود دارد.

385
00:17:02,510 --> 00:17:04,530
سه، چهار، هر دو از شما
بچه ها در پایان.

386
00:17:04,530 --> 00:17:05,579
و پنج، شش.

387
00:17:05,579 --> 00:17:05,839
مطمئن شوید.

388
00:17:05,839 --> 00:17:06,450
پنج و شش.

389
00:17:06,450 --> 00:17:08,390
تمامی حق و خواهیم آمد
به شما بچه ها دفعه بعد.

390
00:17:08,390 --> 00:17:09,640
همه حق است، در بالا آمده است.

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> همه حق است، از آنجایی که شما در اینجا هستید،
می خواهم شما را به سختی

393
00:17:14,819 --> 00:17:16,119
در گوگل شیشه ای اینجا؟

394
00:17:16,119 --> 00:17:19,075
همه حق است، بنابراین، خوب، شیشه ای،
ضبط یک ویدیو.

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
خوب، شما خوب به آن بروید.

397
00:17:24,589 --> 00:17:27,950
>> همه حق است، بنابراین اگر شما بچه ها می توانند بیش از
در اینجا، من از پیش آماده

398
00:17:27,950 --> 00:17:30,110
برخی از اعداد.

399
00:17:30,110 --> 00:17:31,240
همه حق است، آمده بر روی بیش از اینجا.

400
00:17:31,240 --> 00:17:33,440
و چرا شما نه کمی
بیشتر که راه.

401
00:17:33,440 --> 00:17:35,520
و اجازه دهید را ببینید، نام شما چیست،
با شیشه گوگل؟

402
00:17:35,520 --> 00:17:35,910
>> دانشجو: بن.

403
00:17:35,910 --> 00:17:36,230
>> SPEAKER 1: بن؟

404
00:17:36,230 --> 00:17:38,380
OK، بن، شما خواهد بود برای اولین بار، به معنای واقعی کلمه.

405
00:17:38,380 --> 00:17:40,580
بنابراین ما قصد داریم برای شما ارسال
به پایان مرحله است.

406
00:17:40,580 --> 00:17:41,670
همه حق است، و نام خود را؟

407
00:17:41,670 --> 00:17:41,990
>> دانشجو: جیسون.

408
00:17:41,990 --> 00:17:44,530
>> SPEAKER 1: جیسون، OK نظر شما
تعداد نه.

409
00:17:44,530 --> 00:17:46,700
بنابراین اگر شما می خواهید به دنبال بن که راه.

410
00:17:46,700 --> 00:17:47,010
>> دانشجو: جیل.

411
00:17:47,010 --> 00:17:49,630
>> SPEAKER 1: جیل، شما در حال رفتن به
17، که اگر من می خواهم این موضوع را بیشتر انجام می شود

412
00:17:49,630 --> 00:17:51,260
هوشمندانه، من می خواهم که
آغاز شده در انتهای دیگر.

413
00:17:51,260 --> 00:17:52,370
شما بروید که راه.

414
00:17:52,370 --> 00:17:53,030
22.

415
00:17:53,030 --> 00:17:53,670
و شما؟

416
00:17:53,670 --> 00:17:53,980
>> دانشجو: مریم.

417
00:17:53,980 --> 00:17:56,130
>> SPEAKER 1: مری، شما باید 22.

418
00:17:56,130 --> 00:17:58,420
و نام خود را است؟

419
00:17:58,420 --> 00:17:58,810
>> دانشجو: کریس.

420
00:17:58,810 --> 00:18:00,100
>> SPEAKER 1: کریس، شما خواهید بود 26.

421
00:18:00,100 --> 00:18:00,740
و سپس در آخر.

422
00:18:00,740 --> 00:18:01,400
>> دانشجو: دیانا.

423
00:18:01,400 --> 00:18:02,670
>> SPEAKER 1: دیانا، شما باید 34.

424
00:18:02,670 --> 00:18:03,920
بنابراین شما بر روی بیش به اینجا می آیند.

425
00:18:03,920 --> 00:18:06,360
>> همه حق است، پس کامل طبقه بندی شده اند
سفارش در حال حاضر.

426
00:18:06,360 --> 00:18:09,600
و اجازه دهید به جلو و این کار را انجام
به طوری که ما واقعا می تواند -

427
00:18:09,600 --> 00:18:11,720
بن شما فقط نوع نگاه
به هیچ جا وجود دارد.

428
00:18:11,720 --> 00:18:15,670
خوب، پس اجازه دهید به جلو و به تصویر کشیدن این
با استفاده از اسلحه، بسیار شبیه به من بود، دقیقا،

429
00:18:15,670 --> 00:18:16,250
چه خبر است.

430
00:18:16,250 --> 00:18:19,540
پس پیش بروید و خودتان را
پای پیاده و یا دو نفر بین خودتان.

431
00:18:19,540 --> 00:18:22,900
و جلو بروید و اشاره با یک دست به
هر کس که شما باید در اشاره

432
00:18:22,900 --> 00:18:23,470
بر اساس این.

433
00:18:23,470 --> 00:18:25,890
و اگر شما صفر هستید فقط اشاره
راست پایین به طبقه.

434
00:18:25,890 --> 00:18:27,690
خوب، خیلی خوب است.

435
00:18:27,690 --> 00:18:32,290
>> بنابراین در حال حاضر ما باید یک لیست پیوندی، و اجازه دهید من
پیشنهاد می کنند که من نقش بازی

436
00:18:32,290 --> 00:18:35,110
PTR، بنابراین من نمی خواهد زحمت
حمل این اطراف.

437
00:18:35,110 --> 00:18:37,830
و پس از آن - کنوانسیون کسی احمقانه -
شما می توانید هر چیزی که شما می خواهید تماس بگیرید -

438
00:18:37,830 --> 00:18:39,800
سلف اشاره گر، اشاره گر pred -

439
00:18:39,800 --> 00:18:43,930
آن را فقط نام مستعار ما در به
کد نمونه ما به دست چپ من.

440
00:18:43,930 --> 00:18:47,240
از سوی دیگر که رفتن به نگه داشتن
ردیابی است که که در

441
00:18:47,240 --> 00:18:48,400
سناریوهای زیر.

442
00:18:48,400 --> 00:18:52,390
>> بنابراین فرض، برای اولین بار، من می خواهم به دل و جرات کردن
که اولین نمونه قرار دادن، می گویند

443
00:18:52,390 --> 00:18:54,330
20، به لیست.

444
00:18:54,330 --> 00:18:57,160
بنابراین من قصد دارم به کسی نیاز به
تجسم عدد 20 برای ما.

445
00:18:57,160 --> 00:18:58,950
بنابراین من نیاز به کسی malloc
از مخاطب.

446
00:18:58,950 --> 00:18:59,380
بیا بالا.

447
00:18:59,380 --> 00:19:00,340
نام شما چیست؟

448
00:19:00,340 --> 00:19:01,300
>> دانشجو: برایان.

449
00:19:01,300 --> 00:19:05,270
>> SPEAKER 1: برایان، همه حق است، بنابراین شما
باید گره حاوی 20 باشد.

450
00:19:05,270 --> 00:19:06,810
همه حق است، آمده بر روی بیش از اینجا.

451
00:19:06,810 --> 00:19:10,025
و بدیهی است، که در آن
برایان تعلق دارد؟

452
00:19:10,025 --> 00:19:12,190
بنابراین، در وسط - در واقع،
یک دقیقه صبر کنید.

453
00:19:12,190 --> 00:19:13,420
ما در حال انجام این کار خارج از دستور.

454
00:19:13,420 --> 00:19:17,170
ما در حال ساخت این خیلی سخت تر
از آن باید در ابتدا باشد.

455
00:19:17,170 --> 00:19:21,210
خوب، ما قصد داریم به رایگان برایان
و بازتخصیص برایان پنج.

456
00:19:21,210 --> 00:19:23,680
>> خوب، بنابراین در حال حاضر ما می خواهیم برای وارد کردن
برایان به عنوان پنج.

457
00:19:23,680 --> 00:19:25,960
بنابراین بر روی بیش به اینجا می آیند در کنار
بن برای فقط یک لحظه.

458
00:19:25,960 --> 00:19:28,250
و شما احتمالا می تواند بگوید
که این ماجرا می گذرد.

459
00:19:28,250 --> 00:19:30,500
اما بیایید با دقت در مورد فکر می کنم
منظور از عملیات.

460
00:19:30,500 --> 00:19:32,880
و آن را دقیقا همین بصری
که رفتن به خط تا

461
00:19:32,880 --> 00:19:34,080
با آن نمونه کد.

462
00:19:34,080 --> 00:19:40,120
بنابراین در اینجا من PTR اشاره در ابتدا
در بن، فی نفسه نیست، اما در هر

463
00:19:40,120 --> 00:19:43,245
ارزش او وجود دارد، که در این مورد
- نام خود را دوباره؟

464
00:19:43,245 --> 00:19:43,670
>> دانشجو: جیسون.

465
00:19:43,670 --> 00:19:47,350
>> SPEAKER 1: جیسون، به طوری که هر دو بن و من
با اشاره به جیسون در این لحظه.

466
00:19:47,350 --> 00:19:49,700
بنابراین در حال حاضر من مجبور به تعیین،
برایان کجا تعلق دارند؟

467
00:19:49,700 --> 00:19:53,500
بنابراین تنها چیزی که من به اینترنت دسترسی دارند
در حال حاضر او نفر قلم داده است.

468
00:19:53,500 --> 00:19:58,280
بنابراین من قصد دارم برای چک کردن،
برایان کمتر از جیسون؟

469
00:19:58,280 --> 00:19:59,770
پاسخ درست است.

470
00:19:59,770 --> 00:20:03,680
>> بنابراین آنچه در حال حاضر نیاز به اتفاق می افتد،
در جهت درست است؟

471
00:20:03,680 --> 00:20:07,120
من نیاز به به روز رسانی چگونه بسیاری از اشاره گرها
در مجموع در این داستان؟

472
00:20:07,120 --> 00:20:10,720
از کجا دست من است هنوز هم در اشاره
جیسون، و دست خود را - اگر شما می خواهید

473
00:20:10,720 --> 00:20:12,930
قرار دادن دست خود را مانند، مرتب کردن، من
نمی دانم، یک علامت سوال.

474
00:20:12,930 --> 00:20:14,070
خوب، خوب است.

475
00:20:14,070 --> 00:20:15,670
>> همه حق است، بنابراین شما باید
چند نامزد.

476
00:20:15,670 --> 00:20:20,500
یا بن یا من یا برایان و یا جیسون
یا هر کس دیگری، که

477
00:20:20,500 --> 00:20:21,370
اشاره گر نیاز به تغییر؟

478
00:20:21,370 --> 00:20:23,260
چگونه بسیاری در مجموع؟

479
00:20:23,260 --> 00:20:24,080
>> OK SO دو.

480
00:20:24,080 --> 00:20:27,090
اشاره گر من واقعا مهم نیست دیگر
چون من فقط به طور موقت هستم.

481
00:20:27,090 --> 00:20:31,370
پس از آن این دو نفر، احتمالا،
هر دو بن و برایان.

482
00:20:31,370 --> 00:20:34,410
بنابراین اجازه دهید به من پیشنهاد می کنند که ما به روز رسانی
بن، از او برای اولین بار می باشد.

483
00:20:34,410 --> 00:20:36,350
این عنصر برای اولین بار از این لیست
در حال حاضر رفتن به برایان.

484
00:20:36,350 --> 00:20:38,070
بنابراین نقطه بن در برایان.

485
00:20:38,070 --> 00:20:39,320
خوب، در حال حاضر چه؟

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> چه کسی می شود که در آنها اشاره کرد؟

488
00:20:43,460 --> 00:20:44,710
>> دانشجو: [نامفهوم].

489
00:20:44,710 --> 00:20:46,180
>> SPEAKER 1: OK بنابراین برایان
به در اشاره جیسون.

490
00:20:46,180 --> 00:20:48,360
اما من از دست داده مسیر که اشاره گر؟

491
00:20:48,360 --> 00:20:49,980
آیا من می دانم که در آن جیسون است؟

492
00:20:49,980 --> 00:20:50,790
>> دانشجو: [نامفهوم].

493
00:20:50,790 --> 00:20:52,620
>> SPEAKER 1: من، از آنجایی که من هستم
اشاره گر به طور موقت.

494
00:20:52,620 --> 00:20:55,110
و احتمالا، من تغییر نکرده است
در گره جدید اشاره.

495
00:20:55,110 --> 00:20:58,300
بنابراین ما به سادگی می توانید نقطه برایان
در هر کس به من اشاره در.

496
00:20:58,300 --> 00:20:59,000
و ما در حال انجام می شود.

497
00:20:59,000 --> 00:21:01,890
بنابراین مورد، درج در
آغاز از لیست.

498
00:21:01,890 --> 00:21:02,950
دو مرحله اصلی وجود دارد.

499
00:21:02,950 --> 00:21:06,750
یکی از ما باید برای به روز رسانی از بن، و سپس
ما نیز باید برای به روز رسانی برایان.

500
00:21:06,750 --> 00:21:09,230
و سپس من لازم نیست به زحمت
، جستجو از طریق بقیه

501
00:21:09,230 --> 00:21:12,680
لیست، چرا که ما در حال حاضر او
محل، چون او به تعلق

502
00:21:12,680 --> 00:21:14,080
سمت چپ عنصر اول است.

503
00:21:14,080 --> 00:21:15,400
>> همه حق است، بنابراین خیلی سر راست است.

504
00:21:15,400 --> 00:21:18,110
در واقع، احساس می کند مانند ما تقریبا هستید
و این بیش از حد پیچیده است.

505
00:21:18,110 --> 00:21:20,240
پس اجازه دهید در حال حاضر شهامت پایان
لیست، و ببینید که در آن

506
00:21:20,240 --> 00:21:21,380
پیچیدگی آغاز می شود.

507
00:21:21,380 --> 00:21:24,560
بنابراین اگر در حال حاضر، من alloc از مخاطبان.

508
00:21:24,560 --> 00:21:25,540
هر کس می خواهید به بازی 55؟

509
00:21:25,540 --> 00:21:26,700
همه حق است، من دست خود را برای اولین بار دیدم.

510
00:21:26,700 --> 00:21:29,620
بیا بالا.

511
00:21:29,620 --> 00:21:30,030
آره.

512
00:21:30,030 --> 00:21:31,177
نام شما چیست؟

513
00:21:31,177 --> 00:21:32,310
>> دانشجو: [نامفهوم].

514
00:21:32,310 --> 00:21:33,240
>> SPEAKER 1: Habata.

515
00:21:33,240 --> 00:21:33,890
خوب، بیا.

516
00:21:33,890 --> 00:21:35,730
شما عدد 55 باشد.

517
00:21:35,730 --> 00:21:37,820
بنابراین شما، البته، متعلق
در انتهای لیست.

518
00:21:37,820 --> 00:21:41,850
بنابراین پخش شبیه سازی با من
PTR برای فقط یک لحظه.

519
00:21:41,850 --> 00:21:44,050
بنابراین من برای اولین بار رفتن به نقطه در
هر بن در اشاره.

520
00:21:44,050 --> 00:21:45,900
ما هر دو طرف در حال حاضر در برایان.

521
00:21:45,900 --> 00:21:48,420
بنابراین 55 است نه کمتر از پنج.

522
00:21:48,420 --> 00:21:52,510
بنابراین من قصد دارم به خودم به روز رسانی
با اشاره به اشاره گر بعدی برایان، که

523
00:21:52,510 --> 00:21:54,450
اکنون البته جیسون.

524
00:21:54,450 --> 00:21:57,310
55 کمتر از نه نیست، بنابراین
من قصد دارم برای به روز رسانی PTR.

525
00:21:57,310 --> 00:21:58,890
من قصد دارم برای به روز رسانی PTR.

526
00:21:58,890 --> 00:22:02,290
من قصد دارم برای به روز رسانی PTR
من قصد دارم برای به روز رسانی PTR.

527
00:22:02,290 --> 00:22:05,060
و من قصد دارم به - HMM، آنچه
نام خود را دوباره؟

528
00:22:05,060 --> 00:22:05,560
>> دانشجو: دیانا.

529
00:22:05,560 --> 00:22:09,190
>> SPEAKER 1: دیانا اشاره است، البته،
در تهی با دست چپ خود.

530
00:22:09,190 --> 00:22:13,030
پس کجا Habata در واقع
به وضوح تعلق دارد؟

531
00:22:13,030 --> 00:22:15,050
به سمت چپ، در اینجا.

532
00:22:15,050 --> 00:22:19,460
پس چگونه می توانم من می دانم که او را در اینجا
من فکر می کنم من پیچ ام.

533
00:22:19,460 --> 00:22:22,420
چون چیزی که PTR هنر
این لحظه در زمان؟

534
00:22:22,420 --> 00:22:23,240
تهی.

535
00:22:23,240 --> 00:22:25,580
بنابراین حتی اگر، بصری، ما می توانیم
بدیهی است که تمام این را ببینید

536
00:22:25,580 --> 00:22:26,610
بچه ها در اینجا روی صحنه.

537
00:22:26,610 --> 00:22:29,680
من مسیر قبلی نگه داشته است
فرد در لیست.

538
00:22:29,680 --> 00:22:33,210
من انگشت اشاره را نداشته باشند،
در این مورد، گره شماره 34.

539
00:22:33,210 --> 00:22:34,760
>> پس در واقع بیش از این شروع کنیم.

540
00:22:34,760 --> 00:22:37,560
بنابراین در حال حاضر من در واقع نیازی
یک متغیر محلی است.

541
00:22:37,560 --> 00:22:40,980
و این همان چیزی است که شما در دیدن
کد C نمونه واقعی، جایی که به عنوان من می روم،

542
00:22:40,980 --> 00:22:45,860
هنگامی که دست راست خود را به روز رسانی کنم به نقطه
جیسون، در نتیجه ترک برایان پشت سر، من

543
00:22:45,860 --> 00:22:51,440
بهتر است شروع به استفاده از دست چپ من را به
به روز رسانی که در آن من بود، به طوری که به عنوان من به

544
00:22:51,440 --> 00:22:52,700
از طریق این لیست -

545
00:22:52,700 --> 00:22:55,040
به سختی از من در نظر گرفته شده
در حال حاضر اینجا بصری -

546
00:22:55,040 --> 00:22:56,740
من قصد دارم برای رسیدن به
انتهای لیست.

547
00:22:56,740 --> 00:23:00,020
>> این دست است که هنوز هم صفر است، که بسیار
بی فایده، دیگر نسبت به نشان می دهد

548
00:23:00,020 --> 00:23:02,980
من به وضوح هستم در انتهای لیست،
اما در حال حاضر حداقل من این

549
00:23:02,980 --> 00:23:08,270
اشاره گر سلف اشاره در اینجا، بنابراین
در حال حاضر چه دست و اشاره گر نیاز دارند

550
00:23:08,270 --> 00:23:10,150
به روز شود؟

551
00:23:10,150 --> 00:23:13,214
چه کسانی به دست شما می خواهید
به پیکربندی مجدد برای اولین بار؟

552
00:23:13,214 --> 00:23:15,190
>> دانشجو: [نامفهوم].

553
00:23:15,190 --> 00:23:16,220
>> SPEAKER 1: OK، بنابراین دیانا.

554
00:23:16,220 --> 00:23:21,110
که در آن شما می خواهید به نقطه
اشاره گر چپ دیانا در؟

555
00:23:21,110 --> 00:23:23,620
در 55، احتمالا، به طوری که
ما در آنجا قرار داده ام.

556
00:23:23,620 --> 00:23:25,560
و 55 اشاره گر که در آن باید برود؟

557
00:23:25,560 --> 00:23:27,000
پایین، به نمایندگی از تهی.

558
00:23:27,000 --> 00:23:28,890
و تو دست من، در این نقطه، نمی کنند
مهم زیرا آنها فقط

559
00:23:28,890 --> 00:23:30,070
متغیرهای موقت.

560
00:23:30,070 --> 00:23:31,030
بنابراین در حال حاضر ما در حال انجام می شود.

561
00:23:31,030 --> 00:23:34,650
>> بنابراین پیچیدگی اضافی وجود دارد - و
آن است که سخت به پیاده سازی نیست،

562
00:23:34,650 --> 00:23:38,660
اما ما نیاز به یک متغیر ثانویه به
شوید که قبل از من راست من حرکت

563
00:23:38,660 --> 00:23:42,140
دست، من مقدار سمت چپ من به روز رسانی
دست، اشاره گر pred در این مورد، پس از

564
00:23:42,140 --> 00:23:45,860
که من آن را یک اشاره گر دنباله
برای پیگیری از جایی که من بود.

565
00:23:45,860 --> 00:23:49,360
در حال حاضر به عنوان یک کنار، اگر شما به فکر این
از طریق، این احساس مانند آن را

566
00:23:49,360 --> 00:23:51,490
کمی آزار دهنده است که به حفظ
پیگیری این دست چپ.

567
00:23:51,490 --> 00:23:54,015
>> چه می خواهند یکی دیگر از راه حل
برای این مشکل شده اند؟

568
00:23:54,015 --> 00:23:56,500
اگر شما به طراحی مجدد داده ها
ساختار ما در حال صحبت کردن

569
00:23:56,500 --> 00:23:59,630
از طریق در حال حاضر؟

570
00:23:59,630 --> 00:24:02,690
اگر این نوع فقط یک کمی احساس
آزار دهنده به، مانند، دو اشاره گر

571
00:24:02,690 --> 00:24:08,430
رفتن را از طریق لیست، چه کس دیگری می تواند
اند، در یک دنیای ایده آل، داشت

572
00:24:08,430 --> 00:24:10,160
اطلاعات است که ما نیاز داریم؟

573
00:24:10,160 --> 00:24:11,360
آره؟

574
00:24:11,360 --> 00:24:12,610
>> دانشجو: [نامفهوم].

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> SPEAKER 1: دقیقا.

577
00:24:16,150 --> 00:24:19,130
بنابراین در واقع وجود دارد جالب
نطفه یک ایده.

578
00:24:19,130 --> 00:24:22,470
و این ایده از یک اشاره گر قبلی،
اشاره به عنصر قبلی.

579
00:24:22,470 --> 00:24:25,580
چه می شود اگر من فقط گنجانده شده است که
داخل خود لیست

580
00:24:25,580 --> 00:24:27,810
و آن را به سختی به تجسم
این کار را بدون کاغذ

581
00:24:27,810 --> 00:24:28,830
در حال سقوط به زمین است.

582
00:24:28,830 --> 00:24:31,860
اما فرض کنید که این بچه ها استفاده از هر دو
دست خود را به یک قبلی

583
00:24:31,860 --> 00:24:35,950
اشاره گر، و یک اشاره گر بعد، در نتیجه
اجرای آنچه ما می خواهیم تماس بگیرید مضاعف

584
00:24:35,950 --> 00:24:36,830
لیست پیوندی.

585
00:24:36,830 --> 00:24:41,090
که اجازه می دهد من به عقب مرتب سازی بر اساس:
بسیار راحت تر بدون من،

586
00:24:41,090 --> 00:24:43,800
برنامه نویس، نیاز به نگه داشتن
ردیابی دستی -

587
00:24:43,800 --> 00:24:44,980
واقعا دستی -

588
00:24:44,980 --> 00:24:47,280
از جایی که من قبلا
در لیست.

589
00:24:47,280 --> 00:24:48,110
بنابراین ما نمی خواهد انجام دهد.

590
00:24:48,110 --> 00:24:50,950
ما آن را ساده نگه دارید چرا که
رفتن در قیمت آمده است، دو بار به عنوان

591
00:24:50,950 --> 00:24:53,450
فضای زیادی برای اشاره گر،
اگر شما می خواهید.

592
00:24:53,450 --> 00:24:55,760
اما این در واقع مشترک
ساختار داده ها شناخته شده است به عنوان یک

593
00:24:55,760 --> 00:24:57,410
مضاعف لیست پیوندی.

594
00:24:57,410 --> 00:25:01,310
>> اجازه دهید مثال نهایی در اینجا قرار داده و
این بچه ها از بدبختی خود.

595
00:25:01,310 --> 00:25:03,270
بنابراین malloc 20.

596
00:25:03,270 --> 00:25:05,320
بیا تا از راهرو وجود دارد.

597
00:25:05,320 --> 00:25:06,280
همه حق است، نام شما چیست؟

598
00:25:06,280 --> 00:25:07,440
>> دانشجو: [نامفهوم].

599
00:25:07,440 --> 00:25:07,855
>> SPEAKER 1: با عرض پوزش؟

600
00:25:07,855 --> 00:25:08,480
>> دانشجو: [نامفهوم].

601
00:25:08,480 --> 00:25:09,410
>> SPEAKER 1: Demeron؟

602
00:25:09,410 --> 00:25:10,230
خوب در بالا آمده است.

603
00:25:10,230 --> 00:25:11,910
شما باید 20.

604
00:25:11,910 --> 00:25:14,720
شما به وضوح می رویم به
بین 17 و 22 تعلق دارند.

605
00:25:14,720 --> 00:25:16,150
بنابراین اجازه دهید به من درس من یاد بگیرند.

606
00:25:16,150 --> 00:25:18,150
من قصد دارم برای شروع اشاره گر
با اشاره به برایان.

607
00:25:18,150 --> 00:25:21,190
و من قصد دارم به دست چپ من
فقط به برایان به روز رسانی که من به حرکت

608
00:25:21,190 --> 00:25:23,600
جیسون، بررسی می کند 20 کمتر از نه؟

609
00:25:23,600 --> 00:25:24,060
شماره

610
00:25:24,060 --> 00:25:25,430
20 کمتر از 17 است؟

611
00:25:25,430 --> 00:25:25,880
شماره

612
00:25:25,880 --> 00:25:27,450
20 کمتر از 22 است؟

613
00:25:27,450 --> 00:25:28,440
بله.

614
00:25:28,440 --> 00:25:34,070
بنابراین چه چیزی اشاره گر ها و یا دست های نیاز به تغییر
جایی که آنها در حال اشاره در حال حاضر؟

615
00:25:34,070 --> 00:25:37,070
>> بنابراین ما می توانیم 17 اشاره در 20.

616
00:25:37,070 --> 00:25:37,860
به طوری که خوب است.

617
00:25:37,860 --> 00:25:40,080
کجا ما می خواهیم به نقطه
اشاره گر شما در حال حاضر؟

618
00:25:40,080 --> 00:25:41,330
در 22.

619
00:25:41,330 --> 00:25:45,410
و ما می دانیم که در آن 22 است، دوباره به لطف
به اشاره گر موقتی من.

620
00:25:45,410 --> 00:25:46,760
بنابراین ما OK وجود دارد.

621
00:25:46,760 --> 00:25:49,440
بنابراین به دلیل این ذخیره سازی موقت
من مسیر که در آن هر کس را نگه داشته ام.

622
00:25:49,440 --> 00:25:55,055
و در حال حاضر شما بصری می تواند به جایی که
به شما تعلق دارند، و در حال حاضر ما نیاز به 1، 2، 3،

623
00:25:55,055 --> 00:25:58,410
4، 5، 6، 7، 8، 9 توپ استرس،
و دور از کف زدن برای

624
00:25:58,410 --> 00:25:59,770
این بچه ها، اگر ما می تواند.

625
00:25:59,770 --> 00:26:00,410
سادگی انجام می شود.

626
00:26:00,410 --> 00:26:05,320
>> [تشویق حضار]

627
00:26:05,320 --> 00:26:06,330
>> SPEAKER 1: بسیار خوب.

628
00:26:06,330 --> 00:26:09,860
و شما می توانید قطعات را
کاغذ به عنوان یادگاری.

629
00:26:09,860 --> 00:26:15,930
>> همه حق است، بنابراین، من اعتماد زیادی
آسان تر است تا از طریق آن راه رفتن با

630
00:26:15,930 --> 00:26:17,680
انسان از آن را با کد واقعی است.

631
00:26:17,680 --> 00:26:22,690
اما آنچه شما در فقط یک لحظه پیدا
در حال حاضر، همان است - آه، از شما سپاسگزارم.

632
00:26:22,690 --> 00:26:23,630
با تشکر از شما -

633
00:26:23,630 --> 00:26:29,360
این است که شما که همان داده ها
ساختار، یک لیست پیوندی، در واقع می تواند

634
00:26:29,360 --> 00:26:33,200
به عنوان یک بلوک ساختمان حتی بیشتر استفاده می شود
ساختار داده های پیچیده.

635
00:26:33,200 --> 00:26:37,620
>> و برای درک بیش از حد به موضوع اینجا را کلیک کنید این است که
ایم کاملا معرفی مطلب

636
00:26:37,620 --> 00:26:40,060
پیچیدگی به پیاده سازی
این الگوریتم.

637
00:26:40,060 --> 00:26:43,940
درج، و اگر ما را از طریق آن رفت،
حذف و جستجو، کم است

638
00:26:43,940 --> 00:26:46,660
پیچیده تر از آن
با یک آرایه بود.

639
00:26:46,660 --> 00:26:48,040
اما ما برخی از پویایی به دست آورید.

640
00:26:48,040 --> 00:26:50,180
ما ساختار داده انطباقی.

641
00:26:50,180 --> 00:26:54,010
>> اما باز هم، ما پرداخت قیمت با بعضی از
پیچیدگی اضافی، هر دو در

642
00:26:54,010 --> 00:26:54,910
اجرای آن.

643
00:26:54,910 --> 00:26:56,750
و به ما داده تا با دسترسی تصادفی است.

644
00:26:56,750 --> 00:27:00,450
و به صداقت، برخی از خوبی وجود ندارد
اسلاید تمیز من می توانم به شما بدهد که

645
00:27:00,450 --> 00:27:03,120
می گوید در اینجا این است که چرا یک لیست پیوندی
بهتر است از یک آرایه است.

646
00:27:03,120 --> 00:27:04,100
و آن را ترک که در آن.

647
00:27:04,100 --> 00:27:07,520
از آنجا که موضوع مطرح شد در حال حاضر، حتی
بیشتر از آن در هفته های آینده،

648
00:27:07,520 --> 00:27:10,200
که لزوما وجود ندارد
پاسخ صحیح.

649
00:27:10,200 --> 00:27:13,830
>> این است که چرا ما باید محور جداگانه
طراحی برای مجموعه مشکل است.

650
00:27:13,830 --> 00:27:17,700
از آن خواهد شد بسیار حساس زمینه
آیا شما می خواهید به استفاده از این داده ها

651
00:27:17,700 --> 00:27:21,750
ساختار یا آن یکی، و آن را
بستگی دارد چه برای شما در شرایط

652
00:27:21,750 --> 00:27:24,620
منابع و پیچیدگی.

653
00:27:24,620 --> 00:27:28,830
>> اما اجازه دهید به من پیشنهاد که داده های ایده آل
ساختار، جام مقدس، خواهد بود

654
00:27:28,830 --> 00:27:32,200
چیزی که زمان ثابت است،
صرف نظر از اینکه چگونه چیزهای زیادی

655
00:27:32,200 --> 00:27:36,940
در داخل آن، نه آن را شگفت انگیز می شود اگر
ساختار داده ها بازگشت پاسخ در

656
00:27:36,940 --> 00:27:37,920
زمان ثابت.

657
00:27:37,920 --> 00:27:38,330
بله.

658
00:27:38,330 --> 00:27:40,110
این واژه در فرهنگ لغت بزرگ خود است.

659
00:27:40,110 --> 00:27:41,550
یا نه، این کلمه است.

660
00:27:41,550 --> 00:27:43,270
و یا هر مشکل وجود ندارد.

661
00:27:43,270 --> 00:27:46,360
خب بیایید ببینید که اگر ما نمی توانیم حداقل
را یک گام به سمت آن.

662
00:27:46,360 --> 00:27:50,190
>> اجازه دهید یک ساختمان داده جدید پیشنهاد من که
می توان برای چیزهای مختلف مورد استفاده قرار گیرد،

663
00:27:50,190 --> 00:27:52,260
در این مورد به نام جدول هش.

664
00:27:52,260 --> 00:27:55,590
و به همین ترتیب ما در واقع بازگشت به زود گذر
در یک آرایه، در این مورد، و

665
00:27:55,590 --> 00:28:00,550
تا حدودی خودسرانه، من کشیده ام
جدول هش را به عنوان یک آرایه با مرتب کردن بر اساس

666
00:28:00,550 --> 00:28:02,810
آرایه دو بعدی -

667
00:28:02,810 --> 00:28:05,410
و یا به جای آن را در اینجا به عنوان یک دو نشان داده شده است
آرایه بعدی - اما این فقط

668
00:28:05,410 --> 00:28:10,770
آرایه ای از اندازه 26، به طوری که اگر ما
تماس جدول آرایه، براکت جدول

669
00:28:10,770 --> 00:28:12,440
صفر مستطیل در بالای صفحه است.

670
00:28:12,440 --> 00:28:15,090
جدول براکت 25 مستطیل است
در پایین.

671
00:28:15,090 --> 00:28:18,620
و این است که چگونه ممکن است اطلاعات قرعه کشی
ساختاری که در آن من می خواهم برای ذخیره

672
00:28:18,620 --> 00:28:19,790
نام مردم.

673
00:28:19,790 --> 00:28:24,370
>> بنابراین به عنوان مثال، من به قرعه کشی نیست
همه چیز در اینجا در بالای سر، اگر من

674
00:28:24,370 --> 00:28:29,160
تا به حال این آرایه، که من در حال حاضر رفتن به
یک جدول هش تماس بگیرید، و این دوباره

675
00:28:29,160 --> 00:28:31,360
محل صفر.

676
00:28:31,360 --> 00:28:34,840
این مکان است
یک، و غیره.

677
00:28:34,840 --> 00:28:37,880
من ادعا می کنند که من می خواهم به استفاده از این داده ها
ساختار، برای خاطر از بحث و گفتگو،

678
00:28:37,880 --> 00:28:42,600
برای ذخیره نام مردم، Alice و Bob
و چارلی و نام دیگر از این قبیل.

679
00:28:42,600 --> 00:28:46,110
بنابراین از این در حال حاضر به عنوان آغاز فکر می کنم
، می گویند، یک فرهنگ لغت

680
00:28:46,110 --> 00:28:47,520
با تعداد زیادی از کلمات.

681
00:28:47,520 --> 00:28:49,435
آنها اتفاق می افتد به نام
در مثال ما در اینجا.

682
00:28:49,435 --> 00:28:52,560
و این همه بیش از حد وابسته است، شاید، به
پیاده سازی کنترل کننده املا، همانطور که ما

683
00:28:52,560 --> 00:28:54,400
ممکن است برای مشکل مجموعه شش.

684
00:28:54,400 --> 00:28:59,300
>> بنابراین اگر ما آرایه ای از حجم کلی 26
به طوری که این محل 25

685
00:28:59,300 --> 00:29:03,390
در پایین، و من ادعا می کنند که آلیس است
اولین کلمه در فرهنگ لغت

686
00:29:03,390 --> 00:29:07,260
نام هایی که من می خواهم برای وارد کردن به رم،
به این ساختار داده ها، که در آن

687
00:29:07,260 --> 00:29:12,480
غرایز شما گفتن که آلیس
نام باید در این آرایه برود؟

688
00:29:12,480 --> 00:29:13,510
>> ما 26 گزینه.

689
00:29:13,510 --> 00:29:14,990
که در آن ما می خواهیم به او قرار داده است؟

690
00:29:14,990 --> 00:29:16,200
ما او را می خواهم در براکت صفر، درست است؟

691
00:29:16,200 --> 00:29:18,280
برای آلیس، اجازه دهید که صفر تماس بگیرید.

692
00:29:18,280 --> 00:29:20,110
و B، و C خواهد بود.

693
00:29:20,110 --> 00:29:22,600
بنابراین ما در حال رفتن به نوشتن
نام و نام خانوادگی آلیس در اینجا.

694
00:29:22,600 --> 00:29:24,890
اگر ما پس از آن وارد باب، او
نام در اینجا خواهد رفت.

695
00:29:24,890 --> 00:29:27,280
چارلی در اینجا خواهد رفت.

696
00:29:27,280 --> 00:29:30,500
و غیره را از طریق
ساختار داده ها.

697
00:29:30,500 --> 00:29:32,090
>> این ساختار داده ها فوق العاده است.

698
00:29:32,090 --> 00:29:32,730
چرا؟

699
00:29:32,730 --> 00:29:37,460
خب چه زمان در حال اجرا است
قرار دادن نام یک انسان را به این

700
00:29:37,460 --> 00:29:39,850
ساختار داده ها در حال حاضر؟

701
00:29:39,850 --> 00:29:43,702
با توجه به این که این جدول اجرا شده است،
واقعا، به عنوان یک آرایه.

702
00:29:43,702 --> 00:29:44,940
خب زمان ثابت آن است.

703
00:29:44,940 --> 00:29:45,800
این منظور از یک است.

704
00:29:45,800 --> 00:29:46,360
چرا؟

705
00:29:46,360 --> 00:29:48,630
>> خوب چگونه می توانم شما تعیین
که در آن آلیس متعلق است؟

706
00:29:48,630 --> 00:29:51,000
شما که در آن نامه نام او نگاه می کنید؟

707
00:29:51,000 --> 00:29:51,490
اول.

708
00:29:51,490 --> 00:29:54,350
و شما می توانید، اگر آن را به یک رشته،
فقط به دنبال در رشته

709
00:29:54,350 --> 00:29:55,200
براکت صفر.

710
00:29:55,200 --> 00:29:57,110
بنابراین شخصیت صفر از رشته است.

711
00:29:57,110 --> 00:29:57,610
که آسان است.

712
00:29:57,610 --> 00:30:00,350
ما که در رمزنگاری
انتساب هفته قبل در دیتا بیس ثبت شده است.

713
00:30:00,350 --> 00:30:05,310
و سپس یک بار شما می دانید که آلیس
نامه سرمایه، ما می توانیم تفریق

714
00:30:05,310 --> 00:30:08,160
کردن 65 یا سرمایه خود را،
که به ما صفر است.

715
00:30:08,160 --> 00:30:10,940
بنابراین ما در حال حاضر می دانیم که آلیس به آن تعلق دارد
در محل صفر.

716
00:30:10,940 --> 00:30:14,240
>> و با توجه به یک اشاره گر به این داده ها
ساختار، نوعی، چه مدت طول می کشد

717
00:30:14,240 --> 00:30:18,840
آن را به من را برای پیدا کردن محل
صفر در یک آرایه؟

718
00:30:18,840 --> 00:30:22,080
فقط یک گام، درست آن زمان ثابت است
به دلیل دسترسی تصادفی ما

719
00:30:22,080 --> 00:30:23,780
پیشنهاد یکی از ویژگی های یک آرایه بود.

720
00:30:23,780 --> 00:30:28,570
بنابراین در کوتاه مدت، تا بدانند چه شاخص
نام آلیس است، که در

721
00:30:28,570 --> 00:30:32,610
این مورد، A، و یا اجازه دهید فقط حل و فصل
که به صفر، B یک و C است.

722
00:30:32,610 --> 00:30:34,900
دو، بدانند که از
زمان ثابت است.

723
00:30:34,900 --> 00:30:38,510
من فقط باید به حرف اول خود را نگاه کنید،
بدانند که در آن صفر است

724
00:30:38,510 --> 00:30:40,460
آرایه زمان ثابت است.

725
00:30:40,460 --> 00:30:42,140
بنابراین از لحاظ فنی که
مانند دو مرحله است.

726
00:30:42,140 --> 00:30:43,330
اما این هنوز ثابت است.

727
00:30:43,330 --> 00:30:46,880
بنابراین ما تماس بگیرید که O بزرگ یکی، بنابراین ما
آلیس در این جدول درج

728
00:30:46,880 --> 00:30:48,440
زمان ثابت.

729
00:30:48,440 --> 00:30:50,960
>> اما البته، من
ساده و بی تکلف در اینجا، درست است؟

730
00:30:50,960 --> 00:30:53,240
چه می شود اگر هارون در کلاس وجود دارد؟

731
00:30:53,240 --> 00:30:53,990
یا آلیشیا؟

732
00:30:53,990 --> 00:30:57,230
و یا هر نام دیگر و با شروع
A. از کجا می خواهیم برای قرار دادن

733
00:30:57,230 --> 00:31:00,800
آن شخص، درست است؟

734
00:31:00,800 --> 00:31:03,420
منظورم این است که، در حال حاضر تنها سه وجود دارد
مردم روی میز، بنابراین شاید ما

735
00:31:03,420 --> 00:31:07,490
باید آرون در محل قرار داده است
صفر یک دو سه.

736
00:31:07,490 --> 00:31:09,480
>> راست، من می توانم در اینجا قرار داده است.

737
00:31:09,480 --> 00:31:13,350
اما پس از آن، اگر ما سعی می کنیم به قرار دادن داود به
این لیست، که در آن دیوید برود؟

738
00:31:13,350 --> 00:31:15,170
در حال حاضر سیستم ما شروع به شکستن
پایین، درست است؟

739
00:31:15,170 --> 00:31:19,210
از آنجا که در حال حاضر دیوید به پایان می رسد تا اینجا
اگر آرون است که در واقع در اینجا.

740
00:31:19,210 --> 00:31:23,060
و بنابراین در حال حاضر تمام این ایده داشتن یک
ساختار داده ها پاک است که به ما می دهد

741
00:31:23,060 --> 00:31:28,010
اضافه زمان ثابت است و دیگر هیچ
زمان ثابت، چون من به

742
00:31:28,010 --> 00:31:31,240
چک، آه، damnit، کسی که در حال حاضر
در محل آلیس.

743
00:31:31,240 --> 00:31:35,320
>> اجازه بدهید من بقیه از این داده ها بررسی
ساختار، به دنبال یک نقطه برای قرار دادن

744
00:31:35,320 --> 00:31:37,130
کسی مثل نام هارون.

745
00:31:37,130 --> 00:31:39,390
و به طوری که بیش از حد شروع
را به زمان خطی است.

746
00:31:39,390 --> 00:31:42,710
علاوه بر این، اگر شما در حال حاضر خواهید برای پیدا کردن
آرون در این ساختار داده، و شما

747
00:31:42,710 --> 00:31:45,430
بررسی کنید، و نام آرون است که در اینجا نیست.

748
00:31:45,430 --> 00:31:47,960
در حالت مطلوب، شما فقط می گویند آرون
در ساختار داده ها نیست.

749
00:31:47,960 --> 00:31:51,530
اما اگر شما شروع به ساخت اتاق برای
آرون که در آن باید وجود داشته بوده است D

750
00:31:51,530 --> 00:31:55,600
یا E، شما، بدترین حالت، برای بررسی
کل ساختار داده ها در

751
00:31:55,600 --> 00:31:59,480
که در این صورت آن را به چیزی devolves
خطی در اندازه میز.

752
00:31:59,480 --> 00:32:00,920
>> بنابراین همه حق است، من این را حل کنند.

753
00:32:00,920 --> 00:32:04,200
مشکل در اینجا است که من تا به حال
26 عنصر در این آرایه.

754
00:32:04,200 --> 00:32:05,000
اجازه دهید آن را تغییر بدهید.

755
00:32:05,000 --> 00:32:06,010
اوه.

756
00:32:06,010 --> 00:32:10,600
اجازه دهید آن را تغییر دهید به طوری که نه
اندازه 26 در مجموع، متوجه پایین

757
00:32:10,600 --> 00:32:12,720
شاخص در حال رفتن به تغییر به n منهای 1.

758
00:32:12,720 --> 00:32:16,610
اگر 26 است که به وضوح بیش از حد کوچک برای انسان '
نام، زیرا هزاران وجود دارد

759
00:32:16,610 --> 00:32:20,830
نام جهان، اجازه دهید فقط مطمئن
در 100 یا 1،000 10،000.

760
00:32:20,830 --> 00:32:22,960
بیایید فقط اختصاص فضای بسیار بیشتری.

761
00:32:22,960 --> 00:32:27,230
>> خوب است که لزوما کاهش نمی دهد
احتمال این که ما نمی دو

762
00:32:27,230 --> 00:32:31,510
مردم با نام شروع، و
بنابراین، شما قرار بود به تلاش برای قرار دادن یک

763
00:32:31,510 --> 00:32:33,120
نام در محل صفر هنوز.

764
00:32:33,120 --> 00:32:36,850
آنها هنوز هم در حال رفتن به برخورد می کنند، که
معنی است که ما هنوز هم نیاز به یک راه حل برای قرار دادن

765
00:32:36,850 --> 00:32:41,020
آلیس و هارون و آلیشیا و دیگر
نام شروع با جاهای دیگر.

766
00:32:41,020 --> 00:32:43,460
اما چه مقدار از یک مشکل است؟

767
00:32:43,460 --> 00:32:46,870
احتمال است که شما
برخورد در داده ها

768
00:32:46,870 --> 00:32:48,240
ساختار شبیه به این؟

769
00:32:48,240 --> 00:32:52,570
>> خوب، به من اجازه دهید - ما می آیند
به این سوال در اینجا.

770
00:32:52,570 --> 00:32:55,530
و در چگونه ما ممکن است نگاه کنید
ابتدا آن را حل کنید.

771
00:32:55,530 --> 00:32:58,480
اجازه دهید من بکشد تا این پیشنهاد در اینجا.

772
00:32:58,480 --> 00:33:02,020
چیزی که ما فقط به شرح داده شده است، الگوریتم،
اکتشافی نامیده می شود خطی

773
00:33:02,020 --> 00:33:05,030
کاوش به موجب آن، اگر شما سعی در درج
چیزی در اینجا در این داده ها

774
00:33:05,030 --> 00:33:08,920
ساختار، است که به نام جدول هش،
و هیچ اتاق وجود دارد، شما

775
00:33:08,920 --> 00:33:12,000
واقعا بررسی ساختار داده ها
چک کردن، این در دسترس است؟

776
00:33:12,000 --> 00:33:13,430
آیا این موجود است و این در دسترس است؟

777
00:33:13,430 --> 00:33:13,980
آیا این در دسترس است؟

778
00:33:13,980 --> 00:33:17,550
و هنگامی که آن را در نهایت، شما وارد
نام است که شما در اصل در نظر گرفته شده

779
00:33:17,550 --> 00:33:19,370
در جای دیگر در آن محل.

780
00:33:19,370 --> 00:33:23,360
اما در بدترین حالت، تنها نقطه
ممکن است پایین از داده ها

781
00:33:23,360 --> 00:33:25,090
ساختار پایان از آرایه.

782
00:33:25,090 --> 00:33:30,130
>> بنابراین کاوش خطی، در بدترین حالت،
devolves به یک الگوریتم خطی که در آن

783
00:33:30,130 --> 00:33:34,500
هارون، اگر او اتفاق می افتد به درج شود آخرین
در این ساختار داده، او ممکن است

784
00:33:34,500 --> 00:33:39,540
برخورد با این مکان برای اولین بار، اما
سپس توسط بد شانس در پایان.

785
00:33:39,540 --> 00:33:43,940
پس این است که ثابت نیست
زمان جام مقدس برای ما.

786
00:33:43,940 --> 00:33:47,650
این رویکرد از قرار دادن عناصر به
ساختار داده ها به نام یک رشته هش

787
00:33:47,650 --> 00:33:52,050
جدول به نظر نمی رسد به زمان ثابت
حداقل نه در حالت کلی.

788
00:33:52,050 --> 00:33:54,000
این می تواند به چیزی خطی واگذاردن.

789
00:33:54,000 --> 00:33:56,970
>> پس چه می شود اگر حل و فصل ما برخورد
تا حدودی متفاوت است؟

790
00:33:56,970 --> 00:34:00,740
بنابراین در اینجا پیچیده تر است
رویکرد به آنچه هنوز

791
00:34:00,740 --> 00:34:02,800
به نام جدول هش.

792
00:34:02,800 --> 00:34:05,890
و هش، به عنوان به کنار، آنچه
منظورم این است که این شاخص که

793
00:34:05,890 --> 00:34:07,070
من به آن اشاره پیش از آن.

794
00:34:07,070 --> 00:34:09,810
به چیزی هش می تواند
به عنوان یک فعل تصور.

795
00:34:09,810 --> 00:34:13,690
>> بنابراین اگر شما مخلوط آلیس یک نام،
یک تابع هش، پس به صحبت می کنند،

796
00:34:13,690 --> 00:34:14,710
باید یک عدد بازگشت.

797
00:34:14,710 --> 00:34:18,199
در این حالت صفر است اگر او در آن تعلق دارد
محل صفر، اگر او در آن تعلق دارد

798
00:34:18,199 --> 00:34:20,000
محل، و غیره.

799
00:34:20,000 --> 00:34:24,360
بنابراین تابع هش من تا کنون بوده است
فوق العاده ساده است، فقط به دنبال در

800
00:34:24,360 --> 00:34:26,159
حرف اول نام کسی.

801
00:34:26,159 --> 00:34:29,090
اما یک تابع هش طول می کشد به عنوان
ورودی برخی از قطعه ای از داده ها،

802
00:34:29,090 --> 00:34:30,210
رشته ای، بین المللی، هر چیز دیگری.

803
00:34:30,210 --> 00:34:32,239
و آن را تف کردن به طور معمول یک عدد.

804
00:34:32,239 --> 00:34:35,739
و این تعداد است که در آن است که داده ها
عنصر به آن تعلق دارد در یک ساختار داده ها

805
00:34:35,739 --> 00:34:37,800
در اینجا به عنوان یک جدول هش شناخته شده است.

806
00:34:37,800 --> 00:34:41,400
>> بنابراین فقط به طور مستقیم، این است که
زمینه کمی متفاوت است.

807
00:34:41,400 --> 00:34:44,170
این در واقع اشاره به عنوان مثال
مربوط به جشن های تولد، که در آن

808
00:34:44,170 --> 00:34:46,850
وجود دارد ممکن است به عنوان بسیاری از
31 روز در ماه.

809
00:34:46,850 --> 00:34:52,239
اما چه این فرد تصمیم به
در صورت برخورد انجام دهید؟

810
00:34:52,239 --> 00:34:55,304
بافت در حال حاضر در حال، نه یک برخورد
اسم دارد، اما برخورد تولد،

811
00:34:55,304 --> 00:35:00,760
اگر دو نفر همان روز تولد
در 2nd اکتبر، به عنوان مثال.

812
00:35:00,760 --> 00:35:02,120
>> دانشجو: [نامفهوم].

813
00:35:02,120 --> 00:35:05,010
>> SPEAKER 1: آره، بنابراین در اینجا ما
اعمال نفوذ از لیست های پیوندی.

814
00:35:05,010 --> 00:35:07,830
بنابراین به نظر می رسد کمی متفاوت
از ما آن را قبلا به خود جلب کرد.

815
00:35:07,830 --> 00:35:10,790
اما ما به نظر می رسد به یک آرایه
در سمت چپ.

816
00:35:10,790 --> 00:35:13,230
این یک شاخص است، بدون هیچ
دلیل خاصی.

817
00:35:13,230 --> 00:35:14,630
اما هنوز هم یک آرایه.

818
00:35:14,630 --> 00:35:16,160
آرایه ای از اشاره گر است.

819
00:35:16,160 --> 00:35:20,670
و هر یک از این عناصر، هر یک از
این حلقهها یا اسلش - اسلش

820
00:35:20,670 --> 00:35:23,970
به نمایندگی از تهی - هر یک از این
اشاره گر ظاهرا به اشاره

821
00:35:23,970 --> 00:35:25,730
چه ساختار داده؟

822
00:35:25,730 --> 00:35:26,890
لیست پیوندی.

823
00:35:26,890 --> 00:35:30,530
>> بنابراین در حال حاضر ما توانایی
کد سخت به برنامه های ما

824
00:35:30,530 --> 00:35:32,010
اندازه جدول.

825
00:35:32,010 --> 00:35:35,360
در این مورد، ما می دانیم و هرگز وجود ندارد
بیش از 31 روز در ماه است.

826
00:35:35,360 --> 00:35:38,480
خیلی سخته برنامه نویسی یک مقدار مانند 31
مناسب در این زمینه است.

827
00:35:38,480 --> 00:35:42,700
در زمینه نام، برنامه نویسی سخت
26 معقول نیست مردم

828
00:35:42,700 --> 00:35:46,340
نام تنها با شروع به عنوان مثال،
الفبای مربوط از طریق زهرا

829
00:35:46,340 --> 00:35:50,180
>> ما می توانیم همه آنها را به آن داده خودرا برای امتحان اماده
ساختار تا زمانی که، هنگامی که ما یک

830
00:35:50,180 --> 00:35:55,330
برخورد، ما با نام قرار نیست در اینجا،
به جای آن ما از این سلول ها فکر می کنم

831
00:35:55,330 --> 00:36:00,270
نه به عنوان رشته خود، بلکه به عنوان
اشاره گر به، برای مثال، آلیس.

832
00:36:00,270 --> 00:36:03,660
و سپس آلیس می تواند یکی دیگر از اشاره گر
به نام دیگری شروع با

833
00:36:03,660 --> 00:36:06,150
A. و باب در واقع بیش از اینجا می رود.

834
00:36:06,150 --> 00:36:10,850
>> و اگر نام دیگری شروع وجود دارد
با B، او به پایان می رسد تا بیش از اینجا.

835
00:36:10,850 --> 00:36:15,070
و به همین ترتیب هر یک از عناصر این
جدول دو، اگر ما طراحی این

836
00:36:15,070 --> 00:36:17,350
کمی هوشمندانه تر -

837
00:36:17,350 --> 00:36:18,125
بیا -

838
00:36:18,125 --> 00:36:22,950
اگر ما این است که یک کمی بیشتر طراحی
هوشمندانه، در حال حاضر تبدیل به داده های تطبیقی

839
00:36:22,950 --> 00:36:27,720
ساختار، که در آن هیچ محدودیتی سخت وجود دارد
چگونه بسیاری از عناصر شما می توانید وارد کنید

840
00:36:27,720 --> 00:36:30,700
به آن به دلیل اگر شما مجبور
برخورد، که خوب است.

841
00:36:30,700 --> 00:36:34,690
فقط پیش بروید و اضافه آن را
چیزی است که ما یک کمی پیش دیدم

842
00:36:34,690 --> 00:36:38,290
شناخته شده به عنوان یک لیست پیوندی.

843
00:36:38,290 --> 00:36:39,690
>> خوب اجازه توقف برای فقط یک لحظه.

844
00:36:39,690 --> 00:36:42,570
احتمال برخورد چیست
در وهله اول؟

845
00:36:42,570 --> 00:36:45,480
راست، شاید من بیش از تفکر، شاید
من بیش از مهندسی این مشکل هستم،

846
00:36:45,480 --> 00:36:46,370
چون شما می دانید چه؟

847
00:36:46,370 --> 00:36:49,070
بله، من می توانم آمد تا با خودسرانه
نمونه خاموش بالا از سر من دوست

848
00:36:49,070 --> 00:36:52,870
آلیسون و هارون، اما در واقعیت،
با توجه به یک توزیع یکنواخت از

849
00:36:52,870 --> 00:36:56,990
ورودی، این است که برخی از اضافه تصادفی
را به یک ساختار داده ها، آنچه واقعا است

850
00:36:56,990 --> 00:36:58,580
احتمال برخورد؟

851
00:36:58,580 --> 00:37:01,670
خوب معلوم است، آن را در واقع
بالا فوق العاده است.

852
00:37:01,670 --> 00:37:03,850
اجازه بدهید من با تعمیم این
مشکل این است که به عنوان این است.

853
00:37:03,850 --> 00:37:08,890
>> بنابراین در یک اتاق از n CS50 دانش آموز، چه
احتمال این که حداقل

854
00:37:08,890 --> 00:37:11,010
دو دانش آموز در اتاق
همان روز تولد؟

855
00:37:11,010 --> 00:37:13,346
بنابراین چیزی است که وجود دارد. hund چند -

856
00:37:13,346 --> 00:37:16,790
200، 300 نفر در اینجا و چند
صد نفر در خانه امروز.

857
00:37:16,790 --> 00:37:20,670
بنابراین اگر شما می خواهید به خودمان بپرسیم چه
احتمال دو نفر

858
00:37:20,670 --> 00:37:23,930
در این اتاق که همان تولد،
ما می توانیم این رقم را.

859
00:37:23,930 --> 00:37:26,250
و من ادعا می کنند در واقع دو وجود دارد
مردم با همان تولد.

860
00:37:26,250 --> 00:37:29,560
>> به عنوان مثال، آیا کسی
امروز روز تولد؟

861
00:37:29,560 --> 00:37:31,340
دیروز؟

862
00:37:31,340 --> 00:37:32,590
فردا؟

863
00:37:32,590 --> 00:37:35,980
همه حق است، پس از آن احساس می کند مانند من قصد دارم
باید برای انجام این کار 363 یا بیشتر

864
00:37:35,980 --> 00:37:39,500
زمان محلی شما به واقع کشف کردن
اگر ما یک برخورد است.

865
00:37:39,500 --> 00:37:42,350
و یا ما فقط می تواند این کار را انجام دهند ریاضی
و نه از tediously است

866
00:37:42,350 --> 00:37:43,200
انجام این کار است.

867
00:37:43,200 --> 00:37:44,500
و به شرح زیر ارائه شده است.

868
00:37:44,500 --> 00:37:48,740
>> بنابراین پیشنهاد می کنم که ما می توانیم از مدل
احتمال دو نفر داشتن

869
00:37:48,740 --> 00:37:55,320
همان تولد به عنوان احتمال، از مجموع 1
منهای احتمال هیچ کس داشتن

870
00:37:55,320 --> 00:37:56,290
همان تولد.

871
00:37:56,290 --> 00:37:59,960
بنابراین برای دریافت این، و این فقط
راه فانتزی از نوشتن این،

872
00:37:59,960 --> 00:38:03,090
شخص اول در اتاق، او
می توانید هر یک از ممکن است داشته

873
00:38:03,090 --> 00:38:07,370
تولد با فرض 365 روز در سال،
با پوزش به افراد مبتلا به

874
00:38:07,370 --> 00:38:08,760
تولد فوریه 29.

875
00:38:08,760 --> 00:38:13,470
>> بنابراین فرد برای اولین بار در این اتاق رایگان
به هر تعداد از تولد

876
00:38:13,470 --> 00:38:18,280
از امکانات 365 به طوری که
ما می خواهیم انجام شده توسط 365 که 365 تقسیم،

877
00:38:18,280 --> 00:38:18,990
که یکی.

878
00:38:18,990 --> 00:38:22,700
شخصی که در کنار در اتاق، اگر هدف
برای جلوگیری از برخورد، تنها می تواند در

879
00:38:22,700 --> 00:38:26,460
داشته باشند و یا تولد خود را در مورد چگونگی
بسیاری از روز های مختلف ممکن است؟

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
بنابراین دوره دوم در این بیان است
اساسا انجام آن ریاضی برای ما

882
00:38:31,430 --> 00:38:33,460
با کم کردن یک روز امکان پذیر است.

883
00:38:33,460 --> 00:38:36,390
و سپس روز بعد، روز بعد،
روز بعد را به تعداد کل

884
00:38:36,390 --> 00:38:38,100
مردم در اتاق.

885
00:38:38,100 --> 00:38:41,290
>> و اگر ما پس از آن در نظر بگیرند، چه پس از آن است
احتمال داشتن همه

886
00:38:41,290 --> 00:38:45,265
جشن های تولد منحصر به فرد، اما دوباره 1 منهای
، بیان آنچه ما دریافت می کنید

887
00:38:45,265 --> 00:38:47,810
که بسیار fancifully می تواند
شبیه به این.

888
00:38:47,810 --> 00:38:50,330
اما این جالب تر
در نگاه بصری.

889
00:38:50,330 --> 00:38:55,120
این نمودار که در آن بر روی محور x است
تعداد زیادی از مردم در اتاق،

890
00:38:55,120 --> 00:38:56,180
تعدادی از تولد.

891
00:38:56,180 --> 00:38:59,840
در محور y احتمال
برخورد، دو نفر

892
00:38:59,840 --> 00:39:01,230
داشتن همان تولد.

893
00:39:01,230 --> 00:39:05,020
>> و غذای آماده را از این منحنی است
که به محض اینکه شما را وادار به دوست 40

894
00:39:05,020 --> 00:39:11,110
دانش آموزان، شما را در احتمال 90٪
به combinatorically دو

895
00:39:11,110 --> 00:39:13,550
مردم و یا داشتن بیش
همان تولد.

896
00:39:13,550 --> 00:39:18,600
و هنگامی که شما را وادار به دوست 58 نفر آن را
نزدیک به 100٪ از این دو شانس

897
00:39:18,600 --> 00:39:21,310
مردم در اتاق در حال رفتن به
همان روز تولد، حتی اگر وجود دارد

898
00:39:21,310 --> 00:39:26,650
365 یا 366 سطل ممکن است، و
تنها 58 نفر در اتاق.

899
00:39:26,650 --> 00:39:29,900
فقط آماری شما به احتمال زیاد
برخورد، که در کوتاه مدت

900
00:39:29,900 --> 00:39:31,810
انگیزه این بحث است.

901
00:39:31,810 --> 00:39:35,890
که حتی اگر ما فانتزی در اینجا، و
شروع به داشتن این زنجیره، ما هنوز

902
00:39:35,890 --> 00:39:36,950
رفتن به برخورد.

903
00:39:36,950 --> 00:39:42,710
>> به طوری که begs سوال، آنچه که
هزینه انجام اضافه و حذف

904
00:39:42,710 --> 00:39:44,850
را به یک ساختار داده شبیه به این؟

905
00:39:44,850 --> 00:39:46,630
خوب اجازه بدهید من پیشنهاد -

906
00:39:46,630 --> 00:39:51,570
و اجازه دهید برگردم به صفحه نمایش بیش از
- اگر ما عناصر ازت در

907
00:39:51,570 --> 00:39:56,330
لیست، بنابراین اگر ما در حال تلاش برای وارد کردن
n عنصر، و ما باید

908
00:39:56,330 --> 00:39:58,050
چگونه بسیاری از کل سطل؟

909
00:39:58,050 --> 00:40:03,450
بیایید می گویند 31 مجموع سطل
در مورد تولد.

910
00:40:03,450 --> 00:40:09,240
حداکثر طول یک چه خبر
از این زنجیره بالقوه؟

911
00:40:09,240 --> 00:40:12,670
>> اگر دوباره 31 امکان وجود دارد
تولدها در یک ماه داده شده است.

912
00:40:12,670 --> 00:40:14,580
و ما فقط انبوه شدن همه -

913
00:40:14,580 --> 00:40:15,580
در واقع این یک مثال: کامپیوتر و نرم افزار است.

914
00:40:15,580 --> 00:40:16,960
اجازه دهید به جای انجام 26.

915
00:40:16,960 --> 00:40:20,890
بنابراین اگر در واقع افرادی که نام
با شروع از A تا Z، در نتیجه دادن

916
00:40:20,890 --> 00:40:22,780
ما 26 احتمالات.

917
00:40:22,780 --> 00:40:25,920
و ما با استفاده از یک ساختار داده ها مانند
یکی از ما فقط دیدم، به موجب آن ما

918
00:40:25,920 --> 00:40:30,210
آرایه ای از اشاره گر، که هر کدام
امتیاز به یک لیست پیوندی که در آن

919
00:40:30,210 --> 00:40:32,360
اولین لیست همه است
با نام آلیس.

920
00:40:32,360 --> 00:40:35,770
فهرست دوم این است که هر با
نام شروع با یک، با شروع

921
00:40:35,770 --> 00:40:36,980
با B، و غیره.

922
00:40:36,980 --> 00:40:41,020
>> به احتمال زیاد از طول هر یک از چه خبر
این لیست اگر فرض کنیم یک تمیز خوب

923
00:40:41,020 --> 00:40:45,410
توزیع از نام های A تا Z
در سراسر کل ساختار داده؟

924
00:40:45,410 --> 00:40:50,210
افراد n در ساختار داده ها وجود دارد
تقسیم 26 و اگر آنها به خوبی هستیم

925
00:40:50,210 --> 00:40:52,110
گسترش بیش از کل
ساختار داده ها.

926
00:40:52,110 --> 00:40:54,970
به طوری که طول هر یک از این
زنجیره نفر تقسیم بر 26.

927
00:40:54,970 --> 00:40:57,380
اما در نماد O بزرگ، این است که؟

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
چه چیزی است که واقعا؟

930
00:41:02,440 --> 00:41:04,150
پس از آن واقعا فقط N، درست است؟

931
00:41:04,150 --> 00:41:06,620
از آنجا که ما در گذشته گفته ام،
اوه شما 26 تقسیم کنید.

932
00:41:06,620 --> 00:41:08,710
بله، در واقع آن را سریع تر است.

933
00:41:08,710 --> 00:41:12,720
اما در تئوری، آن را اساسا نمی
که سریعتر.

934
00:41:12,720 --> 00:41:16,040
>> بنابراین ما به نظر نمی رسد که بسیار
نزدیک تر به این جام مقدس.

935
00:41:16,040 --> 00:41:17,750
در واقع، این فقط زمان خطی است.

936
00:41:17,750 --> 00:41:20,790
هک، در این نقطه، چرا ما نمی
فقط استفاده از یکی از بزرگ لیست پیوندی؟

937
00:41:20,790 --> 00:41:23,510
چرا ما فقط استفاده از یک بزرگ
آرایه برای ذخیره نام

938
00:41:23,510 --> 00:41:25,010
هر کس در اتاق؟

939
00:41:25,010 --> 00:41:28,280
خوب، هنوز هم وجود دارد چیزی
قانع کننده در مورد یک جدول هش؟

940
00:41:28,280 --> 00:41:30,810
آیا هنوز هم وجود دارد چیزی فوتی و فوری
در مورد ساختار داده ها

941
00:41:30,810 --> 00:41:33,940
به نظر می رسد که این را دوست دارند؟

942
00:41:33,940 --> 00:41:35,182
این.

943
00:41:35,182 --> 00:41:37,050
>> دانشجو: [نامفهوم].

944
00:41:37,050 --> 00:41:39,840
>> SPEAKER 1: راست، و دوباره اگر آن را فقط
یک الگوریتم زمان خطی، و

945
00:41:39,840 --> 00:41:42,780
زمان ساختمان داده خطی، چرا من نمی
فقط نام همه را در یک بزرگ ذخیره

946
00:41:42,780 --> 00:41:44,210
آرایه، و یا در یک لیست بزرگ مرتبط است؟

947
00:41:44,210 --> 00:41:47,010
و متوقف کردن ساخت CS بسیار سخت تر
از آن نیاز دارد باشد؟

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
چه در این مورد قانع کننده است، حتی
هر چند من آن را خراشیده؟

950
00:41:53,190 --> 00:41:54,930
>> دانشجو: [نامفهوم].

951
00:41:54,930 --> 00:41:57,040
>> SPEAKER 1: درج نیستند؟

952
00:41:57,040 --> 00:41:58,140
گران قیمت دیگر.

953
00:41:58,140 --> 00:42:03,390
بنابراین اضافه بالقوه هنوز هم می تواند
زمان ثابت، حتی اگر داده های شما

954
00:42:03,390 --> 00:42:07,910
ساختار به نظر می رسد مثل این، آرایه ای از
اشاره گر، که هر کدام در اشاره

955
00:42:07,910 --> 00:42:09,550
به طور بالقوه یک لیست پیوندی.

956
00:42:09,550 --> 00:42:15,220
چگونه می تواند شما را ثابت رسیدن به
درج زمان نام؟

957
00:42:15,220 --> 00:42:16,280
استیک آن را در جلو، درست است؟

958
00:42:16,280 --> 00:42:19,290
>> اگر ما به یک گل برای طراحی از قربانی
پیشتر گفته شد، جایی که ما می خواستیم برای حفظ

959
00:42:19,290 --> 00:42:22,650
نام هر کس به عنوان مثال، طبقه بندی شده اند،
و یا همه اعداد در مرحله طبقه بندی شده اند،

960
00:42:22,650 --> 00:42:25,020
فرض کنید که ما
لیست نامرتب مرتبط است.

961
00:42:25,020 --> 00:42:29,960
این فقط ما هزینه های یک یا دو مرحله،
می خواهم در مورد بن و برایان

962
00:42:29,960 --> 00:42:32,750
پیشتر گفته شد، برای درج یک عنصر در
آغاز از لیست.

963
00:42:32,750 --> 00:42:36,090
بنابراین اگر ما در مورد مرتب سازی بر همه مهم نیست
از نام شروع با یا همه

964
00:42:36,090 --> 00:42:39,660
نام با B شروع، ما هنوز هم می توانید
دستیابی به قرار دادن زمان ثابت.

965
00:42:39,660 --> 00:42:43,900
در حال حاضر به دنبال آلیس و باب و یا هر نام
به طور کلی هنوز چه؟

966
00:42:43,900 --> 00:42:48,100
O بزرگ از n تقسیم بر 26، در
حالت ایده آل که در آن هر کس یکنواخت

967
00:42:48,100 --> 00:42:51,190
توزیع شده، که در آن به عنوان بسیاری وجود دارد
به عنوان Z، که احتمالا وجود دارد

968
00:42:51,190 --> 00:42:52,220
غیر واقعی است.

969
00:42:52,220 --> 00:42:53,880
اما این هنوز خطی است.

970
00:42:53,880 --> 00:42:57,120
>> اما در اینجا، ما آمده ایم به نقطه
نماد مجانبی

971
00:42:57,120 --> 00:42:58,600
از لحاظ نظری درست است.

972
00:42:58,600 --> 00:43:02,960
اما در دنیای واقعی، اگر من ادعا می کنند که
برنامه من می تواند به چیزی 26 بار انجام

973
00:43:02,960 --> 00:43:06,210
سریع تر از شما، که برنامه
می خواهید برای ترجیح می دهند با استفاده از؟

974
00:43:06,210 --> 00:43:09,660
شما یا من، که
26 برابر سریعتر؟

975
00:43:09,660 --> 00:43:14,320
در واقع، فردی که 26 است
بار سریعتر، حتی اگر از لحاظ نظری

976
00:43:14,320 --> 00:43:18,790
الگوریتم های ما در همان اجرا شود
مجانبی زمان در حال اجرا است.

977
00:43:18,790 --> 00:43:20,940
>> اجازه بدهید من پیشنهاد های مختلف
راه حل در دسترس نباشد.

978
00:43:20,940 --> 00:43:24,380
و اگر این ذهن خود را منفجر کنید،
ما از ساختارهای داده ای هستید.

979
00:43:24,380 --> 00:43:27,420
پس این است که آن درخت -

980
00:43:27,420 --> 00:43:28,520
نوع یک نام احمقانه.

981
00:43:28,520 --> 00:43:32,880
آن را از retrievals ها می آید، و کلمه
درخت پیشوندی، T-R--E، املای دلیل

982
00:43:32,880 --> 00:43:34,450
بازیابی البته برای تلفن های موبایل مانند درخت است.

983
00:43:34,450 --> 00:43:36,580
اما این تاریخ
درخت پیشوندی کلمه.

984
00:43:36,580 --> 00:43:40,980
>> بنابراین یک درخت پیشوندی است که در واقع نوعی از درخت،
و آن را نیز بازی در آن کلمه است.

985
00:43:40,980 --> 00:43:46,330
و حتی شما می توانید کاملا آن را ببینید
با این تجسم، یک درخت پیشوندی است

986
00:43:46,330 --> 00:43:50,790
درخت ساختار، مانند یک درخت خانواده با
یک جد در بالا و تعداد زیادی

987
00:43:50,790 --> 00:43:54,530
نوه و نوه بزرگ
به عنوان برگ در پایین.

988
00:43:54,530 --> 00:43:58,100
اما هر گره در درخت یک آرایه است.

989
00:43:58,100 --> 00:44:00,680
و آن را در یک آرایه - و اجازه
ساده برای یک لحظه - آن را

990
00:44:00,680 --> 00:44:04,600
آرایه، در این مورد، اندازه 26، که در آن
هر گره دوباره مجموعه ای از اندازه

991
00:44:04,600 --> 00:44:09,000
26، که در آن عنصر صفر در آن
آرایه نشان دهنده، و آخرین

992
00:44:09,000 --> 00:44:11,810
عنصر در هر یک از چنین
آرایه نشان دهنده زهرا

993
00:44:11,810 --> 00:44:15,520
>> بنابراین پیشنهاد می کنم، پس، که این داده ها
ساختار، شناخته شده به عنوان یک درخت، می تواند

994
00:44:15,520 --> 00:44:17,600
استفاده می شود همچنین برای ذخیره کلمات.

995
00:44:17,600 --> 00:44:21,740
ما یک لحظه پیش دیدم که چگونه ما می تواند ذخیره
کلمات، و یا در این مورد نام، و ما

996
00:44:21,740 --> 00:44:25,440
قبلا دیدم که چگونه ما می توانیم اعداد را ذخیره،
اما اگر ما تمرکز بر روی نام و یا رشته

997
00:44:25,440 --> 00:44:27,460
در اینجا، متوجه چه چیزی جالب است.

998
00:44:27,460 --> 00:44:32,210
من ادعا می کنند که نام ماکسول است
در داخل این ساختار داده ها.

999
00:44:32,210 --> 00:44:33,730
از کجا می توانم ماکسول می بینید؟

1000
00:44:33,730 --> 00:44:35,140
>> دانشجو: [نامفهوم].

1001
00:44:35,140 --> 00:44:36,240
>> SPEAKER 1: در سمت چپ.

1002
00:44:36,240 --> 00:44:39,910
پس چه جالب با این داده ها
ساختار است و نه از فروشگاه

1003
00:44:39,910 --> 00:44:46,200
رشته M-A-X-W-E-L-L بک اسلش صفر، تمام
contiguously، آنچه که شما به جای انجام

1004
00:44:46,200 --> 00:44:46,890
شرح زیر است.

1005
00:44:46,890 --> 00:44:50,510
اگر این درخت مانند ساختار داده است،
هر یک از گره ها که دوباره یک آرایه،

1006
00:44:50,510 --> 00:44:54,650
و شما می خواهید برای ذخیره ماکسول، برای بار اول شما
شاخص و غیره گره ریشه است، به طوری

1007
00:44:54,650 --> 00:44:57,810
به صحبت می کنند، گره بالاترین،
در محل M، درست است، بنابراین

1008
00:44:57,810 --> 00:44:59,160
تقریبا به عمق دفاع حریف.

1009
00:44:59,160 --> 00:45:03,740
و سپس از آنجا، شما به دنبال یک
اشاره گر به گره های یک کودک، پس به صحبت می کنند.

1010
00:45:03,740 --> 00:45:06,150
بنابراین در مفهوم شجره نامه،
شما به دنبال آن رو به پایین است.

1011
00:45:06,150 --> 00:45:09,030
و به شما که منجر به گره دیگر
در سمت چپ وجود دارد، که

1012
00:45:09,030 --> 00:45:10,540
فقط یکی دیگر از آرایه.

1013
00:45:10,540 --> 00:45:14,710
>> و پس از آن اگر شما می خواهید برای ذخیره ماکسول،
شما در پیدا کردن اشاره گر است که نشان دهنده

1014
00:45:14,710 --> 00:45:16,430
A، که این یکی در اینجا است.

1015
00:45:16,430 --> 00:45:17,840
سپس شما به گره بعدی بروید.

1016
00:45:17,840 --> 00:45:20,100
و توجه کنید - این است که چرا تصویر
یک فریب کمی -

1017
00:45:20,100 --> 00:45:21,990
این گره نگاه فوق العاده کوچک است.

1018
00:45:21,990 --> 00:45:26,050
اما به حق این Y و Z. است به
این فقط نویسنده کوتاه است

1019
00:45:26,050 --> 00:45:27,630
تصویر به طوری که شما در واقع
چیز را ببینید.

1020
00:45:27,630 --> 00:45:30,400
در غیر این صورت به این تصویر
خواهد بود بسیار گسترده ای است.

1021
00:45:30,400 --> 00:45:36,180
بنابراین در حال حاضر شما شاخص به محل X، پس از آن
W، E، L، L. سپس چه

1022
00:45:36,180 --> 00:45:37,380
این کنجکاوی؟

1023
00:45:37,380 --> 00:45:41,250
>> خوب، اگر ما با استفاده از این نوع جدید
را در چگونه برای ذخیره یک رشته در

1024
00:45:41,250 --> 00:45:44,500
ساختار داده ها، شما هنوز هم نیاز به
اساسا چک کردن در داده ها

1025
00:45:44,500 --> 00:45:47,250
ساختار که یک کلمه در اینجا به پایان می رسد.

1026
00:45:47,250 --> 00:45:50,830
به عبارت دیگر، هر یک از این گره ها
به نحوی به خاطر داشته باشید که ما

1027
00:45:50,830 --> 00:45:53,500
در واقع به دنبال این اشاره گر
و در حال ترک کمی

1028
00:45:53,500 --> 00:45:58,370
نان خرده نان در پایین در اینجا از این
ساختار برای نشان دادن M-A-X-W-E-L-L

1029
00:45:58,370 --> 00:46:00,230
در واقع در این ساختار داده ها.

1030
00:46:00,230 --> 00:46:02,040
>> بنابراین ما ممکن است این کار را به شرح زیر انجام دهید.

1031
00:46:02,040 --> 00:46:06,810
هر یک از گره که در تصویر ما فقط
اره یک، آرایه ای از اندازه 27 است.

1032
00:46:06,810 --> 00:46:10,550
و آن را در حال حاضر 27، چرا که در ص شش،
ما در واقع به شما در مواقع حذف حرف یا بخشی از کلمه را،

1033
00:46:10,550 --> 00:46:13,590
بنابراین ما می توانیم به نامهایی چون انتشارات O'reilly به
و دیگران با آپوستروف.

1034
00:46:13,590 --> 00:46:14,820
اما همین ایده.

1035
00:46:14,820 --> 00:46:17,710
هر یک از این عناصر در
آرایه به یک struct

1036
00:46:17,710 --> 00:46:19,320
گره، بنابراین فقط یک گره است.

1037
00:46:19,320 --> 00:46:21,430
پس این است که بسیار یادآور
لیست پیوندی ما.

1038
00:46:21,430 --> 00:46:24,550
>> و پس از آن من بولی، که من
کلمه تماس، است که فقط برای رفتن به

1039
00:46:24,550 --> 00:46:29,120
درست اگر یک کلمه به پایان می رسد در این
گره در درخت است.

1040
00:46:29,120 --> 00:46:32,870
این به طور موثر نشان دهنده کمی
مثلث ما یک لحظه پیش دیدم.

1041
00:46:32,870 --> 00:46:37,190
بنابراین اگر یک کلمه به پایان می رسد که در آن گره در
درخت، که فیلد کلمه درست باشد،

1042
00:46:37,190 --> 00:46:41,990
است که مفهومی چک کردن، یا
ما در حال رسم این مثلث، بله وجود دارد

1043
00:46:41,990 --> 00:46:44,080
یک کلمه در اینجا است.

1044
00:46:44,080 --> 00:46:45,120
>> بنابراین این درخت است.

1045
00:46:45,120 --> 00:46:48,540
و در حال حاضر سوال این است که، چه
زمان در حال اجرا است؟

1046
00:46:48,540 --> 00:46:49,930
آیا آن بزرگ O N؟

1047
00:46:49,930 --> 00:46:51,410
آیا چیز دیگری است؟

1048
00:46:51,410 --> 00:46:57,330
خوب، اگر شما نفر نام در این داده ها
ساختار، ماکسول تنها یکی از

1049
00:46:57,330 --> 00:47:02,330
آنها، چه زمان در حال اجرا است
قرار دادن یا پیدا کردن ماکسول؟

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
زمان در حال اجرا
قرار دادن ماکسول؟

1052
00:47:09,050 --> 00:47:11,740
اگر نامهای نفر دیگر وجود دارد
در حال حاضر در جدول؟

1053
00:47:11,740 --> 00:47:12,507
آره؟

1054
00:47:12,507 --> 00:47:15,429
>> دانشجو: [نامفهوم].

1055
00:47:15,429 --> 00:47:17,550
>> SPEAKER 1: آره، آن را به طول
نام، درست است؟

1056
00:47:17,550 --> 00:47:24,420
بنابراین M-X-W-E-L-L تا آن را مانند این احساس می کند
الگوریتم O بزرگ از هفت است.

1057
00:47:24,420 --> 00:47:26,580
در حال حاضر، البته، نام
در طول متفاوت خواهد بود.

1058
00:47:26,580 --> 00:47:27,380
شاید آن یک نام کوتاه است.

1059
00:47:27,380 --> 00:47:28,600
شاید آن یک نام دیگر است.

1060
00:47:28,600 --> 00:47:33,390
اما آنچه کلیدی در اینجا این است که
آن یک عدد ثابت است.

1061
00:47:33,390 --> 00:47:36,810
و شاید آن را واقعا ثابت نیست،
اما خدا، اگر در واقع، در یک

1062
00:47:36,810 --> 00:47:41,570
فرهنگ لغت، احتمالا وجود دارد برخی از محدودیت
در تعداد حروف در

1063
00:47:41,570 --> 00:47:43,820
نام فرد در یک کشور خاص.

1064
00:47:43,820 --> 00:47:46,940
>> و بنابراین ما می توانیم فرض کنیم که
ارزش ثابت است.

1065
00:47:46,940 --> 00:47:47,750
من نمی دانم آنچه در آن است.

1066
00:47:47,750 --> 00:47:50,440
این احتمالا بزرگتر از
ما فکر می کنیم آن است.

1067
00:47:50,440 --> 00:47:52,720
از آنجا که همیشه برخی از گوشه وجود دارد
با نام دیوانه طولانی.

1068
00:47:52,720 --> 00:47:56,360
بنابراین اجازه دهید آن را K می نامند، اما هنوز هم
ثابت احتمالا، زیرا هر

1069
00:47:56,360 --> 00:48:00,190
نام در جهان، حداقل در
کشور خاص، این است که طول یا

1070
00:48:00,190 --> 00:48:01,780
کوتاه تر، پس از آن ثابت است.

1071
00:48:01,780 --> 00:48:04,490
اما هنگامی که ما گفته ایم چیزی بزرگ است
O یک مقدار ثابت، چه که

1072
00:48:04,490 --> 00:48:07,760
واقعا معادل؟

1073
00:48:07,760 --> 00:48:10,420
این واقعا همان چیزی است
عنوان کرد و گفت زمان ثابت است.

1074
00:48:10,420 --> 00:48:11,530
>> در حال حاضر ما نوع تقلب هستید، درست است؟

1075
00:48:11,530 --> 00:48:15,340
ما نوع از اعمال نفوذ برخی از نظریه
در اینجا می گویند که خوب، منظور از k است

1076
00:48:15,340 --> 00:48:17,450
واقعا فقط یک سفارش از،
زمان و ثابت آن است.

1077
00:48:17,450 --> 00:48:18,200
اما واقعا است.

1078
00:48:18,200 --> 00:48:22,550
از آنجا که بینش کلیدی در اینجا این است که
اگر ما نفر نام در حال حاضر در این

1079
00:48:22,550 --> 00:48:26,010
ساختار داده ها، و ما درج ماکسول،
مدت زمانی که طول می کشد تا

1080
00:48:26,010 --> 00:48:29,530
درج ماکسول در همه آسیب دیده
که چگونه بسیاری از مردم

1081
00:48:29,530 --> 00:48:31,100
در ساختار داده ها هستند؟

1082
00:48:31,100 --> 00:48:31,670
به نظر نمی رسد.

1083
00:48:31,670 --> 00:48:36,280
اگر من تا به حال یک میلیارد عناصر بیشتر به این
درخت پیشوندی، و سپس وارد ماکسول،

1084
00:48:36,280 --> 00:48:38,650
او در همه تحت تاثیر قرار می گیرد؟

1085
00:48:38,650 --> 00:48:39,050
شماره

1086
00:48:39,050 --> 00:48:42,950
و این بر خلاف هر یک از داده های روز
ساختار ما را دیده ام تا کنون، که در آن

1087
00:48:42,950 --> 00:48:46,820
زمان اجرای الگوریتم خود را
به طور کامل مستقل از اینکه چقدر

1088
00:48:46,820 --> 00:48:51,430
مسائل است و یا در حال حاضر نیست
در این ساختار داده ها.

1089
00:48:51,430 --> 00:48:54,650
>> و به همین ترتیب با این می توان شما در حال حاضر است
فرصت برای P مجموعه شش، که خواهد شد

1090
00:48:54,650 --> 00:48:58,310
دوباره شامل اجرای خود را
غلطیاب املایی، خواندن در 150،000

1091
00:48:58,310 --> 00:49:01,050
کلمات، چگونه بهترین برای ذخیره آن
لزوما آشکار نیست.

1092
00:49:01,050 --> 00:49:04,030
و اگر چه من آرزو کردم برای پیدا کردن
جام مقدس، من نمی

1093
00:49:04,030 --> 00:49:05,330
ادعا می کنند که یک درخت پیشوندی است.

1094
00:49:05,330 --> 00:49:09,810
در واقع، جدول هش ممکن است به خیلی خوب
اثبات بسیار کارآمد تر است.

1095
00:49:09,810 --> 00:49:10,830
ولی برای کسانی که فقط -

1096
00:49:10,830 --> 00:49:14,620
این فقط یکی از تصمیم گیری های طراحی
شما باید مطمئن.

1097
00:49:14,620 --> 00:49:18,920
>> اما در بسته اجازه دهید 50 یا بیشتر
ثانیه را زیرچشمی نگاه کردن در چه نهفته است

1098
00:49:18,920 --> 00:49:22,190
پیش هفته آینده و فراتر از آن ما گذار
از این خط فرمان

1099
00:49:22,190 --> 00:49:26,220
اگر برنامه C به چیزهایی وب
و بر اساس زبان مانند پی اچ پی و

1100
00:49:26,220 --> 00:49:30,350
جاوا اسکریپت و اینترنت به خودی خود،
پروتکل ها مانند HTTP، که شما باید

1101
00:49:30,350 --> 00:49:32,870
گرفته شده برای سال اعطا شده
در حال حاضر، و تایپ شده در هر

1102
00:49:32,870 --> 00:49:34,440
روز، شاید، و یا دیده می شود.

1103
00:49:34,440 --> 00:49:37,420
و ما را به پوست پشت شروع
لایه هایی از آنچه اینترنت است.

1104
00:49:37,420 --> 00:49:40,650
و آنچه را که کد این است که
زمینه ابزار و امروز.

1105
00:49:40,650 --> 00:49:43,230
پس از 50 ثانیه از این تیزر به اینجا.

1106
00:49:43,230 --> 00:49:46,570
من تو را رزمندگان خالص را.

1107
00:49:46,570 --> 00:49:51,370
>> [پخش ویدئو]

1108
00:49:51,370 --> 00:49:56,764
>> او با پیام آمد.

1109
00:49:56,764 --> 00:50:00,687
با استفاده از یک پروتکل خود را.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
او به جهان از فایروال بی رحمانه،
uncaring روتر، و خطرات دور

1112
00:50:19,780 --> 00:50:22,600
بدتر از مرگ است.

1113
00:50:22,600 --> 00:50:23,590
او سریع است.

1114
00:50:23,590 --> 00:50:25,300
او قوی است.

1115
00:50:25,300 --> 00:50:27,700
او TCPIP است.

1116
00:50:27,700 --> 00:50:30,420
و او آدرس خود را.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
رزمندگان خالص.

1119
00:50:34,590 --> 00:50:35,290
>> [END پخش ویدئو]

1120
00:50:35,290 --> 00:50:38,070
>> SPEAKER 1: این است که چگونه اینترنت
باید به عنوان هفته آینده کار می کنند.

1121
00:50:38,070 --> 00:50:40,406