1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:11,137
[MUSIC پخش]

3
00:00:11,137 --> 00:00:12,220
DAVID J. مالان: خوب.

4
00:00:12,220 --> 00:00:13,950
این CS50 است.

5
00:00:13,950 --> 00:00:18,560
این هفته پنج ادامه داد، و ما
برخی از خبر خوب و یک خبر بد.

6
00:00:18,560 --> 00:00:21,140
پس خبر خوب این است که CS50
راه اندازی این جمعه.

7
00:00:21,140 --> 00:00:24,430
اگر شما می خواهم برای پیوستن به ما،
سر به URL معمول است.

8
00:00:24,430 --> 00:00:28,670
اخبار حتی بهتر، بدون سخنرانی
این آینده دوشنبه از 13TH.

9
00:00:28,670 --> 00:00:31,970
کمی کمتر بهتر از اخبار،
مسابقه صفر چهارشنبه آینده است.

10
00:00:31,970 --> 00:00:33,840
جزئیات بیشتر را می توان
که در این URL را در اینجا.

11
00:00:33,840 --> 00:00:36,340
و در طی چند روز آینده
ما در جاهای خالی پر

12
00:00:36,340 --> 00:00:39,234
با توجه به اتاق
که ما محفوظ خواهد.

13
00:00:39,234 --> 00:00:41,400
اخبار بهتر است که وجود دارد خواهید
یک بررسی البته گسترده

14
00:00:41,400 --> 00:00:43,570
جلسه این آینده
دوشنبه شب.

15
00:00:43,570 --> 00:00:46,270
اقامت به البته در تنظیم
وب سایت برای مکان و جزئیات.

16
00:00:46,270 --> 00:00:49,290
بخش ها، حتی اگر آن است که یک
تعطیلات، نیز به خوبی تامین کند.

17
00:00:49,290 --> 00:00:50,490

18
00:00:50,490 --> 00:00:52,940
بهترین اخبار، سخنرانی روز جمعه.

19
00:00:52,940 --> 00:00:56,220
بنابراین این ما سنت است
، به عنوان در هر برنامه درسی.

20
00:00:56,220 --> 00:00:58,100
Just-- آن را به شگفت انگیز است.

21
00:00:58,100 --> 00:01:02,510
شما چیزهایی مانند دیدن
ساختمان داده زمان ثابت

22
00:01:02,510 --> 00:01:04,730
و جداول هش و درختان و تلاش می کند.

23
00:01:04,730 --> 00:01:07,150
و ما در مورد مشکلات تولد صحبت کنید.

24
00:01:07,150 --> 00:01:09,440
دسته کامل از مسائل
در انتظار روز جمعه.

25
00:01:09,440 --> 00:01:11,212

26
00:01:11,212 --> 00:01:12,200
OK.

27
00:01:12,200 --> 00:01:13,190
به هر حال.

28
00:01:13,190 --> 00:01:17,080
>> پس به یاد آورید که ما شده است
تمرکز بر این تصویر از چه

29
00:01:17,080 --> 00:01:18,980
در داخل از حافظه کامپیوتر را می دهد.

30
00:01:18,980 --> 00:01:22,875
بنابراین حافظه یا RAM که در آن برنامه است
وجود داشته باشد در حالی که شما آنها را در حال اجرا.

31
00:01:22,875 --> 00:01:25,215
اگر شما دوبار کلیک کنید
آیکون برای اجرای برخی از برنامه

32
00:01:25,215 --> 00:01:27,520
و یا دوبار کلیک کنید
آیکون برای باز کردن بعضی از فایل،

33
00:01:27,520 --> 00:01:30,430
آن را از سخت شما بارگذاری
رانندگی و یا درایو حالت جامد

34
00:01:30,430 --> 00:01:34,190
به RAM، حافظه دسترسی تصادفی، که در آن
آن زندگی می کند تا زمانی که قدرت خاموش می رود،

35
00:01:34,190 --> 00:01:36,700
درب لپ تاپ بسته می شود،
و یا شما را ترک برنامه است.

36
00:01:36,700 --> 00:01:38,960
>> حالا که حافظه، از
که شما احتمالا

37
00:01:38,960 --> 00:01:41,950
1 گیگابایت این روزها، 2
گیگابایت، و یا حتی خیلی بیشتر،

38
00:01:41,950 --> 00:01:44,420
به طور کلی گذاشته
برای یک برنامه داده شده

39
00:01:44,420 --> 00:01:47,170
در این نوع از مستطیل
مدل مفهومی

40
00:01:47,170 --> 00:01:50,860
به موجب آن ما باید پشته در پایین
و یک دسته از مسائل دیگر در بالای صفحه.

41
00:01:50,860 --> 00:01:53,140
چیزی که در بالا بسیار
ما در این تصویر دیده می شود

42
00:01:53,140 --> 00:01:55,670
قبل از اما هرگز صحبت در مورد
به اصطلاح بخش متن است.

43
00:01:55,670 --> 00:01:58,419
بخش متن تنها راه فانتزی
از گفت صفر و آنهایی که

44
00:01:58,419 --> 00:02:01,150
نوشتن برنامه واقعی وارد کنید.

45
00:02:01,150 --> 00:02:03,910
>> بنابراین، هنگامی که شما با دوبار کلیک
مایکروسافت ورد برای مک و یا PC خود را،

46
00:02:03,910 --> 00:02:08,030
و یا زمانی که شما نقطه اجرا بریده بریده ماریو در
کامپیوتر لینوکس در پنجره ترمینال خود را،

47
00:02:08,030 --> 00:02:12,460
صفر و آنهایی که آهنگسازی
کلمه یا ماریو به طور موقت ذخیره شده

48
00:02:12,460 --> 00:02:16,610
در RAM کامپیوتر خود را در به اصطلاح
بخش متن برای یک برنامه خاص.

49
00:02:16,610 --> 00:02:19,080
در زیر می رود که مقدار دهی اولیه
و داده های آماده سازی نشده.

50
00:02:19,080 --> 00:02:22,655
این ماده مانند متغیرهای جهانی است،
که ما استفاده می شود بسیاری از نمی کردم،

51
00:02:22,655 --> 00:02:24,910
اما در مواردی که ما کرده ایم
حال متغیر جهانی

52
00:02:24,910 --> 00:02:28,819
و یا آماری رشته تعریف شده است که
سخت است کلماتی مانند "سلام" کد گذاری

53
00:02:28,819 --> 00:02:31,860
که در از کاربر گرفته شده است
که به آنها کد گذاری شده به برنامه شما.

54
00:02:31,860 --> 00:02:34,230
>> در حال حاضر، به پایین در پایین ما
دارای پشته به اصطلاح.

55
00:02:34,230 --> 00:02:37,665
و پشته، تا کنون، ما شده است
با استفاده از برای آن دسته از اهداف؟

56
00:02:37,665 --> 00:02:39,706

57
00:02:39,706 --> 00:02:40,997
چه خبر از پشته شده است را برای استفاده می شود؟

58
00:02:40,997 --> 00:02:41,160
آره؟

59
00:02:41,160 --> 00:02:42,070
>> رسید توابع.

60
00:02:42,070 --> 00:02:43,320
>> DAVID J. مالان: برای توابع؟

61
00:02:43,320 --> 00:02:44,980
در چه حس برای توابع؟

62
00:02:44,980 --> 00:02:48,660
>> رسید وقتی که شما یک تابع فراخوانی،
استدلال را بر روی پشته کپی می شود.

63
00:02:48,660 --> 00:02:49,660
>> DAVID J. مالان: دقیقا.

64
00:02:49,660 --> 00:02:52,650
هنگامی که شما یک تابع فراخوانی، آن
استدلال را بر روی پشته کپی می شود.

65
00:02:52,650 --> 00:02:56,330
بنابراین هر X یا Y است و یا یا در B
که شما عبور را به یک تابع

66
00:02:56,330 --> 00:02:58,680
به طور موقت قرار داده و در
پشته به اصطلاح،

67
00:02:58,680 --> 00:03:02,000
درست مثل یکی از آننبرگ
سینی های غذاخوری، و همه چیز

68
00:03:02,000 --> 00:03:03,190
مانند متغیرهای محلی.

69
00:03:03,190 --> 00:03:06,290
اگر تابع مواد غذایی خود را و یا مبادله خود را
تابع باید متغیرهای محلی،

70
00:03:06,290 --> 00:03:08,602
مثل درجه حرارت، آن دو
در نهایت بر روی پشته.

71
00:03:08,602 --> 00:03:11,560
در حال حاضر، ما نمی خواهد بیش از حد صحبت کردن در مورد
آنها را، اما این متغیر های محیط زیست

72
00:03:11,560 --> 00:03:15,690
در پایین دیدیم در حالی که پیش زمانی که
من در صفحه کلید یک روز futzing شد

73
00:03:15,690 --> 00:03:20,050
آغاز شده و من دسترسی به همه چیز
مانند argv را 100 یا argv را 1000،

74
00:03:20,050 --> 00:03:22,320
فقط elements-- I را فراموش کرده ام
numbers-- اما

75
00:03:22,320 --> 00:03:24,330
شد قرار نیست به من دسترسی.

76
00:03:24,330 --> 00:03:26,581
ما شروع به دیدن برخی از
کاراکتر های بد بو بر روی صفحه نمایش.

77
00:03:26,581 --> 00:03:28,330
کسانی که به اصطلاح بود
متغیر های محیط زیست

78
00:03:28,330 --> 00:03:32,390
مانند تنظیمات جهانی برای من
برنامه یا کامپیوتر من، نه

79
00:03:32,390 --> 00:03:37,090
غیر مرتبط با اخیر
مشکلات را که مورد بحث ما،

80
00:03:37,090 --> 00:03:39,670
Shellshock، که شده است
فاکتورها باعث ایجاد پلاک کاملا چند کامپیوتر.

81
00:03:39,670 --> 00:03:42,960
>> حالا در آخر، در تمرکز امروز
ما در نهایت شما در پشته باشد.

82
00:03:42,960 --> 00:03:44,864
این بخش دیگری از حافظه است.

83
00:03:44,864 --> 00:03:47,030
و اساسا این همه
حافظه همان است است.

84
00:03:47,030 --> 00:03:48,040
این همان سخت افزار است.

85
00:03:48,040 --> 00:03:49,956
ما فقط نوع هستند
درمان دسته های مختلف

86
00:03:49,956 --> 00:03:51,460
از بایت ها برای مقاصد مختلف.

87
00:03:51,460 --> 00:03:56,540
پشته نیز خواهد بود که در آن
متغیر و حافظه که شما درخواست

88
00:03:56,540 --> 00:03:58,810
از سیستم عامل
است به طور موقت ذخیره می شود.

89
00:03:58,810 --> 00:04:01,890
>> اما نوع یک مشکل وجود دارد
در اینجا، به عنوان تصویر نشان میدهد.

90
00:04:01,890 --> 00:04:05,261
ما نوع دو
کشتی های به هم برخورد می کنند.

91
00:04:05,261 --> 00:04:08,010
از آنجا که شما به عنوان بیشتر و بیشتر استفاده کنید
از پشته، و همانطور که ما امروز می بینیم

92
00:04:08,010 --> 00:04:11,800
به بعد، به عنوان شما بیشتر و بیشتر از استفاده از
پشته، قطعا چیزهای بد ممکن است رخ دهد.

93
00:04:11,800 --> 00:04:15,054
و در واقع، ما می توانیم القا کنند که
خواسته یا ناخواسته.

94
00:04:15,054 --> 00:04:16,970
بنابراین مطلب یا داستان جالب آخرین
زمان این برنامه بود،

95
00:04:16,970 --> 00:04:20,570
که به خدمت هیچ کاربردی
هدف دیگر از برای نشان دادن

96
00:04:20,570 --> 00:04:24,750
چگونه شما به عنوان یک پسر بد در واقع می تواند را
استفاده از باگ در برنامه کسی

97
00:04:24,750 --> 00:04:28,460
و بیش از یک برنامه یا حتی یک
سیستم های کامپیوتری و یا کل سرور.

98
00:04:28,460 --> 00:04:31,660
پس فقط به نگاه به طور خلاصه، شما
توجه کنید که اصلی در پایین

99
00:04:31,660 --> 00:04:34,510
طول می کشد در خط فرمان
استدلال، به عنوان در argv را.

100
00:04:34,510 --> 00:04:38,480
و آن را تا یک تماس به یک تابع f،
اساسا یک تابع بی نام به نام

101
00:04:38,480 --> 00:04:40,250
ج، و آن را عبور در argv [1].

102
00:04:40,250 --> 00:04:43,960
>> پس هر کلمه نوع کاربر در در
اعلان پس از نام این برنامه،

103
00:04:43,960 --> 00:04:49,310
و سپس این تابع دلخواه تا
بالا، ج، طول می کشد در یک رشته، کاراکتر AKA *،

104
00:04:49,310 --> 00:04:51,720
همانطور که ما شروع کرده ایم به بحث در مورد،
و آن را فقط آن را "میاره."

105
00:04:51,720 --> 00:04:53,310
اما ما می تواند آن را هر چیزی تماس بگیرید.

106
00:04:53,310 --> 00:04:57,470
و سپس آن را اعلام کرد، در داخل
از f، آرایه ای از کاراکتر ها

107
00:04:57,470 --> 00:04:59,930
نام c-- 12 شخصیت های مانند.

108
00:04:59,930 --> 00:05:03,580
>> در حال حاضر، این داستان من گفتن
یک لحظه پیش، که در آن در حافظه

109
00:05:03,580 --> 00:05:06,720
ج است، و یا کسانی که 12
کاراکتر رفتن برای پایان دادن به؟

110
00:05:06,720 --> 00:05:07,570
فقط به روشن باشد.

111
00:05:07,570 --> 00:05:08,070
آره؟

112
00:05:08,070 --> 00:05:08,590
>> رسید از پشته.

113
00:05:08,590 --> 00:05:09,420
>> DAVID J. مالان: در پشته.

114
00:05:09,420 --> 00:05:10,720
پس ج یک متغیر محلی است.

115
00:05:10,720 --> 00:05:14,079
ما برای 12 کاراکتر یا 12 بایت درخواست.

116
00:05:14,079 --> 00:05:16,120
کسانی که می خواهند برای پایان دادن به
در پشته به اصطلاح.

117
00:05:16,120 --> 00:05:18,530
در حال حاضر در نهایت این تابع دیگر است
که در واقع بسیار مفید،

118
00:05:18,530 --> 00:05:20,571
اما ما واقعا استفاده نمی شود
آن خودمان، strncopy.

119
00:05:20,571 --> 00:05:21,550

120
00:05:21,550 --> 00:05:25,200
این بدان معنی است کپی رشته، اما
تنها N نامه ها، نفر حرف می باشد.

121
00:05:25,200 --> 00:05:31,990
بنابراین تعداد کاراکتر خواهد بود
از نوار به سی کپی شده است.

122
00:05:31,990 --> 00:05:32,980
و چگونه بسیاری از؟

123
00:05:32,980 --> 00:05:34,110
طول نوار.

124
00:05:34,110 --> 00:05:36,330
بنابراین به عبارت دیگر، که
یک خط، strncopy،

125
00:05:36,330 --> 00:05:39,500
رفتن به کپی
به طور موثر مانع در به ج.

126
00:05:39,500 --> 00:05:42,340
>> در حال حاضر، فقط به نوع پیش بینی
اخلاقی این داستان،

127
00:05:42,340 --> 00:05:44,750
آنچه که به طور بالقوه مشکل ساز که اینجا هستید؟

128
00:05:44,750 --> 00:05:49,710
اگر چه ما در حال چک کردن طول
از نوار و عبور آن را به strncopy،

129
00:05:49,710 --> 00:05:53,145
آنچه که دل و روده خود گفتن شما است
هنوز هم در مورد این برنامه شکسته؟

130
00:05:53,145 --> 00:05:54,410

131
00:05:54,410 --> 00:05:55,220
آره؟

132
00:05:55,220 --> 00:05:57,491
>> رسید آیا شامل نمی شود
اتاق برای شخصیت پوچ.

133
00:05:57,491 --> 00:05:59,990
DAVID J. مالان: آیا شامل نمی شود
اتاق برای شخصیت پوچ.

134
00:05:59,990 --> 00:06:02,073
به طور بالقوه، بر خلاف در
عمل گذشته ما حتی نمی

135
00:06:02,073 --> 00:06:04,810
چیزهای زیادی به عنوان یک به علاوه 1 به
جای که شخصیت تهی.

136
00:06:04,810 --> 00:06:06,649
اما حتی بدتر از آن.

137
00:06:06,649 --> 00:06:07,940
چه چیز دیگری ما شکست ها کاری انجام دهید؟

138
00:06:07,940 --> 00:06:08,432
آره؟

139
00:06:08,432 --> 00:06:09,307
>> رسید [نامفهوم]

140
00:06:09,307 --> 00:06:15,440

141
00:06:15,440 --> 00:06:16,440
DAVID J. مالان: کامل.

142
00:06:16,440 --> 00:06:18,490
ما سخت کدگذاری ام 12 بسیار خودسرانه.

143
00:06:18,490 --> 00:06:19,497

144
00:06:19,497 --> 00:06:21,330
این است که خیلی نمی
مشکل است، اما این واقعیت است

145
00:06:21,330 --> 00:06:25,630
که ما حتی چک کردن اگر نه
طول نوار کمتر از 12 است،

146
00:06:25,630 --> 00:06:28,530
که در این صورت آن را به
امن به آن را به حافظه

147
00:06:28,530 --> 00:06:30,260
به نام ج که ما اختصاص داده ایم.

148
00:06:30,260 --> 00:06:32,960
در واقع، اگر نوار مانند
20 حرف،

149
00:06:32,960 --> 00:06:39,010
این تابع به نظر می رسد کپی شود
20 حرف از نوار به ج، در نتیجه

150
00:06:39,010 --> 00:06:41,310
مصرف حداقل 8 بایت
که آن را نمی باید باشد.

151
00:06:41,310 --> 00:06:42,690
این مفهوم در اینجا.

152
00:06:42,690 --> 00:06:44,347
>> بنابراین در کوتاه مدت، برنامه های شکسته.

153
00:06:44,347 --> 00:06:45,180
مانند یک معامله بزرگ.

154
00:06:45,180 --> 00:06:46,360
شاید شما یک گسل تقسیم بندی کنید.

155
00:06:46,360 --> 00:06:47,651
ما همه اشکالات در برنامه دارند.

156
00:06:47,651 --> 00:06:50,196
همه ما ممکن است اشکالات دارند
در برنامه در حال حاضر.

157
00:06:50,196 --> 00:06:51,320
اما چه مفهوم است؟

158
00:06:51,320 --> 00:06:54,390
خوب، در اینجا یک نسخه بزرگنمایی در از است
این تصویر از حافظه کامپیوتر من است.

159
00:06:54,390 --> 00:06:56,230
این پایین پشته من است.

160
00:06:56,230 --> 00:06:59,644
و در واقع، در سطح بسیار پائین است چه
به نام پشته پدر و مادر معمول، راه های فانتزی

161
00:06:59,644 --> 00:07:00,560
گفتن که اصلی.

162
00:07:00,560 --> 00:07:03,772
به طوری که هر کس تابع به نام
ج که ما در حال صحبت کردن در مورد.

163
00:07:03,772 --> 00:07:05,230
بنابراین این پایین پشته است.

164
00:07:05,230 --> 00:07:06,640
آدرس بازگشت چیزی جدید است.

165
00:07:06,640 --> 00:07:08,810
این همواره وجود دارد،
همیشه در آن تصویر شده است.

166
00:07:08,810 --> 00:07:10,440
ما فقط هرگز توجه به آن نامیده می شود.

167
00:07:10,440 --> 00:07:15,290
از آنجا که معلوم است راه ج کار می کند
که زمانی که به یک تابع دیگر را فراخوانی،

168
00:07:15,290 --> 00:07:18,780
نه تنها استدلال به آن
تابع کنید را بر روی پشته قرار،

169
00:07:18,780 --> 00:07:22,470
نه تنها محلی تابع
متغیرهای کنید را بر روی پشته قرار،

170
00:07:22,470 --> 00:07:26,820
چیزی به نام آدرس بازگشت
همچنین می شود را بر روی پشته قرار داده است.

171
00:07:26,820 --> 00:07:33,330
به طور خاص، اگر تماس های اصلی مواد غذایی، اصلی
ایمیل خود را در حافظه، گاو نر چیزی،

172
00:07:33,330 --> 00:07:38,240
به طور موثر می شود را بر روی پشته قرار داده
به طوری که وقتی تابع f اجرای آن انجام می شود

173
00:07:38,240 --> 00:07:43,630
می داند که در آن به پرش به در متن
بخش به منظور ادامه اجرای.

174
00:07:43,630 --> 00:07:47,760
>> بنابراین اگر ما به لحاظ مفهومی در اینجا،
در اصلی، آنگاه f نامیده می شود می شود.

175
00:07:47,760 --> 00:07:50,200
چگونه ج می دانم که
به کنترل پشت دست؟

176
00:07:50,200 --> 00:07:52,020
خوب، این کمی
خرده نان به رنگ قرمز در اینجا،

177
00:07:52,020 --> 00:07:54,978
نام آدرس برگشت، آن را فقط
چک، آنچه که آدرس بازگشت است؟

178
00:07:54,978 --> 00:07:57,039
آه، به من اجازه پرش به اصلی در اینجا.

179
00:07:57,039 --> 00:07:59,080
و این کمی است
از ساده،

180
00:07:59,080 --> 00:08:00,750
زیرا صفر و آنهایی که
برای اصلی از لحاظ فنی

181
00:08:00,750 --> 00:08:01,967
تا اینجا در بخش فن آوری.

182
00:08:01,967 --> 00:08:03,800
اما این ایده است. ج
فقط باید بدانید که چه

183
00:08:03,800 --> 00:08:06,680
به جایی که در نهایت کنترل می گردد.

184
00:08:06,680 --> 00:08:09,790
>> اما کامپیوتر راه
از مدت ها گذاشته از همه چیز

185
00:08:09,790 --> 00:08:12,320
مانند متغیرهای محلی و
استدلال اینگونه است.

186
00:08:12,320 --> 00:08:17,180
بنابراین در بالای این تصویر در
آبی قاب پشته برای f است، پس همه

187
00:08:17,180 --> 00:08:19,630
از حافظه که f
به طور خاص با استفاده از است.

188
00:08:19,630 --> 00:08:22,990
بنابراین بر این اساس، توجه کنید که
نوار در این تصویر است.

189
00:08:22,990 --> 00:08:23,980
نوار استدلال آن بود.

190
00:08:23,980 --> 00:08:27,240
و ما ادعا کرد که استدلال به
توابع کنید را بر روی پشته قرار.

191
00:08:27,240 --> 00:08:29,910
و ج، البته،
همچنین در این تصویر.

192
00:08:29,910 --> 00:08:33,520
>> و فقط برای مقاصد نوشتاری،
توجه در گوشه سمت چپ بالای صفحه

193
00:08:33,520 --> 00:08:37,020
است چه ج براکت 0 باشد و
سپس کمی پایین به سمت راست

194
00:08:37,020 --> 00:08:38,220
ج براکت 11 است.

195
00:08:38,220 --> 00:08:41,240
بنابراین به عبارت دیگر، شما می توانید تصور کنید
که یک شبکه از بایت وجود دارد

196
00:08:41,240 --> 00:08:44,380
وجود دارد، اول آن است
بالا و چپ، پایین که

197
00:08:44,380 --> 00:08:48,360
آخرین از آن 12 بایت است.

198
00:08:48,360 --> 00:08:49,930
>> اما در حال حاضر سعی کنید به سرعت رو به جلو.

199
00:08:49,930 --> 00:08:55,580
چه در مورد این است که اتفاق می افتد اگر تصویب ما
در نوار رشته که بیش از ج؟

200
00:08:55,580 --> 00:08:59,130
و ما در حال چک کردن اگر
آن را در واقع بیش از 12.

201
00:08:59,130 --> 00:09:03,146
کدام بخش از این تصویر در حال رفتن به
توسط کلمه در ادامه متن 0، ​​1، 2، 3 رونویسی،

202
00:09:03,146 --> 00:09:07,890
نقطه نقطه نقطه، 11، و پس از آن
بد، 12، 13 تا 19؟

203
00:09:07,890 --> 00:09:11,820
آنچه در اینجا اتفاق می افتد،
اگر شما از سفارش استنباط

204
00:09:11,820 --> 00:09:14,790
که ج براکت 0 است در بالا
و ج براکت 11 است مرتب سازی بر اساس پایین

205
00:09:14,790 --> 00:09:15,812
در سمت راست؟

206
00:09:15,812 --> 00:09:16,796
آره؟

207
00:09:16,796 --> 00:09:19,260
>> رسید: خوب، این رفتن
به بازنویسی نوار کاراکتر *.

208
00:09:19,260 --> 00:09:22,260
>> DAVID J. مالان: آره، آن را مانند به نظر می رسد
شما به بازنویسی * نوار کاراکتر.

209
00:09:22,260 --> 00:09:26,245
و بدتر از آن، اگر شما در یک واقعا طولانی ارسال
رشته، شما حتی ممکن است بازنویسی چه؟

210
00:09:26,245 --> 00:09:27,460

211
00:09:27,460 --> 00:09:28,570
آدرس بازگشت.

212
00:09:28,570 --> 00:09:31,380
که دوباره است، درست مانند یک
خرده نان به برنامه که در آن بگویید

213
00:09:31,380 --> 00:09:34,060
برای رفتن به هنگامی که ج
انجام شده است که گفته می شود.

214
00:09:34,060 --> 00:09:37,140
>> پس چه مردمان بد به طور معمول انجام
است در صورتی که در یک برنامه آمده

215
00:09:37,140 --> 00:09:41,290
که آنها کنجکاو که آیا می
بهره برداری، حشره دار به گونه ای

216
00:09:41,290 --> 00:09:43,550
که او می تواند
استفاده از این اشکال،

217
00:09:43,550 --> 00:09:45,720
به طور کلی آنها را می کنید
این حق اولین بار.

218
00:09:45,720 --> 00:09:48,590
آنها فقط شروع به ارسال، به عنوان مثال،
رشته تصادفی به برنامه شما،

219
00:09:48,590 --> 00:09:50,260
آیا از صفحه کلید،
و یا رک و پوست کنده آنها احتمالا

220
00:09:50,260 --> 00:09:52,740
نوشتن یک برنامه کمی برای تنها
به طور خودکار تولید رشته ها،

221
00:09:52,740 --> 00:09:55,430
و شروع به کوبیدن در برنامه خود را با
ارسال در بسیاری از ورودی های مختلف

222
00:09:55,430 --> 00:09:56,340
در طول های مختلف.

223
00:09:56,340 --> 00:09:58,990
>> به محض این که تصادفات برنامه خود را،
که یک چیز شگفت انگیز است.

224
00:09:58,990 --> 00:10:01,020
این یعنی او
و یا او را کشف کرده است

225
00:10:01,020 --> 00:10:02,660
آنچه که احتمالا در واقع یک اشکال.

226
00:10:02,660 --> 00:10:05,830
و پس از آن آنها می توانند هوشمندانه تر کنید
و شروع به تمرکز دقیق تر

227
00:10:05,830 --> 00:10:07,420
در مورد چگونگی بهره برداری است که اشکال.

228
00:10:07,420 --> 00:10:11,480
به طور خاص، آنچه او ممکن است
انجام شده است، ارسال در بهترین حالت، سلام.

229
00:10:11,480 --> 00:10:12,210
هیچ معامله بزرگ است.

230
00:10:12,210 --> 00:10:14,750
این رشته که به اندازه کافی کوتاه است.

231
00:10:14,750 --> 00:10:18,100
اما اگر او می فرستد،
و ما آن را به عنوان تعمیم،

232
00:10:18,100 --> 00:10:20,890
حمله code-- تا صفر
و آنهایی که انجام کارهای

233
00:10:20,890 --> 00:10:25,150
مثل rm-رادیویی، که همه چیز را حذف
از هارد دیسک و یا ارسال اسپم

234
00:10:25,150 --> 00:10:27,000
و یا به نحوی به دستگاه حمله؟

235
00:10:27,000 --> 00:10:29,570
>> بنابراین اگر هر یک از این
نامه ها فقط نشان دهنده،

236
00:10:29,570 --> 00:10:32,380
مفهومی، حمله، حمله،
حمله، حمله، برخی از کد بد

237
00:10:32,380 --> 00:10:36,410
که شخص دیگری نوشت، اما
در صورتی که فرد به اندازه کافی هوشمند است

238
00:10:36,410 --> 00:10:40,790
نه تنها شامل تمام
از آن rm-RFS، بلکه

239
00:10:40,790 --> 00:10:46,100
باید تا آخرین بایت خود
یک تعداد که مربوط

240
00:10:46,100 --> 00:10:50,540
به آدرس خود
و یا کد حمله خود را خود

241
00:10:50,540 --> 00:10:53,820
که او در گذشت
با ارائه آن در اعلان،

242
00:10:53,820 --> 00:10:58,760
شما می توانید به طور موثر فریب کامپیوتر
به توجه به وقتی تابع f اجرای انجام می شود،

243
00:10:58,760 --> 00:11:02,400
آه، آن زمان برای من برای پرش
به آدرس بازگشت به رنگ قرمز.

244
00:11:02,400 --> 00:11:06,070
اما از آنجا که او دارد به نحوی
همپوشانی آدرس برگشت

245
00:11:06,070 --> 00:11:09,602
با تعداد خود،
و آنها به اندازه کافی هوشمند

246
00:11:09,602 --> 00:11:11,560
به پیکربندی که
تعداد برای اشاره، به شما به عنوان

247
00:11:11,560 --> 00:11:13,740
در فوق العاده بالا مشاهده کنید
گوشه سمت چپ وجود دارد،

248
00:11:13,740 --> 00:11:18,020
آدرس واقعی در کامپیوتر
حافظه از برخی از کد حمله خود را،

249
00:11:18,020 --> 00:11:21,740
پسر بد می تواند کامپیوتر ترفند
به اجرای کد خود را.

250
00:11:21,740 --> 00:11:23,700
>> و این کد، دوباره، می تواند هر چیزی.

251
00:11:23,700 --> 00:11:26,120
به طور کلی نام
کد پوسته، که فقط

252
00:11:26,120 --> 00:11:29,030
روشی برای گفتن که این نمی
به طور کلی چیزی به عنوان ساده به عنوان rm-رادیویی.

253
00:11:29,030 --> 00:11:32,340
این در واقع چیزی شبیه به هم زدن،
و یا یک برنامه واقعی است که به او

254
00:11:32,340 --> 00:11:37,230
و یا کنترل برنامه ریزی شده خود را به اجرا
هر چیز دیگری که آنها می خواهند.

255
00:11:37,230 --> 00:11:40,210
بنابراین در کوتاه مدت، این همه
برآمده از این واقعیت ساده

256
00:11:40,210 --> 00:11:44,490
که این مشکلات را درگیر چک کنید
مرزهای آرایه خود را.

257
00:11:44,490 --> 00:11:47,250
و از آنجایی که راه
کار کامپیوتر است که آنها

258
00:11:47,250 --> 00:11:49,430
استفاده از پشته از
به طور موثر، مفهومی،

259
00:11:49,430 --> 00:11:54,830
پایین به بالا، اما پس از آن عناصر
شما را بر روی پشته فشار رشد بالا به پایین،

260
00:11:54,830 --> 00:11:56,624
این فوق العاده مشکل ساز است.

261
00:11:56,624 --> 00:11:58,290
در حال حاضر، راه های به کار در اطراف این وجود دارد.

262
00:11:58,290 --> 00:12:00,800
و رک و پوست کنده، زبان وجود دارد
که با آن به اطراف این کار می کنند.

263
00:12:00,800 --> 00:12:03,100
جاوا ایمنی بدن است، به عنوان مثال،
در این موضوع خاص.

264
00:12:03,100 --> 00:12:04,110
از آنجا که شما اشاره گر را نمی دهد.

265
00:12:04,110 --> 00:12:05,943
آنها به شما نمی دهد
آدرس مستقیم به حافظه.

266
00:12:05,943 --> 00:12:08,560
پس با این قدرت که ما
به لمس هر چیزی را در حافظه

267
00:12:08,560 --> 00:12:11,580
ما می خواهیم می آید، مسلما، مخاطرات بزرگ است.

268
00:12:11,580 --> 00:12:12,430
>> بنابراین چشم را نگه دارید.

269
00:12:12,430 --> 00:12:14,596
اگر، رک و پوست کنده، در ماه
و یا سال های آینده، در هر زمان

270
00:12:14,596 --> 00:12:17,740
شما در مورد برخی از بهره برداری به عنوان خوانده شده
از یک برنامه یا یک سرور،

271
00:12:17,740 --> 00:12:22,370
اگر شما همیشه به یک اشاره از چیزی را ببینید
مانند حمله سرریز بافر،

272
00:12:22,370 --> 00:12:25,390
و یا سرریز پشته نوع دیگری است
از حمله، در روح مشابه،

273
00:12:25,390 --> 00:12:28,770
آنجا که الهام بخش وب سایت
نام، اگر شما آن را می دانم،

274
00:12:28,770 --> 00:12:33,170
این همه صحبت کردن در مورد تنها
پر به اندازه بعضی از خواص

275
00:12:33,170 --> 00:12:36,200
آرایه یا آرایه به طور کلی.

276
00:12:36,200 --> 00:12:38,822
هر گونه سؤال، پس از آن، در این؟

277
00:12:38,822 --> 00:12:39,780
آیا این را در خانه امتحان کنید.

278
00:12:39,780 --> 00:12:41,620

279
00:12:41,620 --> 00:12:42,300
>> خوب.

280
00:12:42,300 --> 00:12:47,270
بنابراین malloc که تا کنون جدید ما شده است
دوستان در آن ما می توانیم به حافظه اختصاص دهد

281
00:12:47,270 --> 00:12:50,540
که ما لزوما نمی دانند در
پیش که ما می خواهیم تا ما ندارد

282
00:12:50,540 --> 00:12:52,920
به کد سخت به ما
تعداد برنامه مانند 12.

283
00:12:52,920 --> 00:12:55,550
هنگامی که کاربر به ما می گوید که چه مقدار
داده او را به ورودی می خواهد،

284
00:12:55,550 --> 00:12:58,000
ما می توانیم از حافظه malloc.

285
00:12:58,000 --> 00:13:01,484
>> بنابراین malloc که معلوم است، به
جایی که با استفاده از آن،

286
00:13:01,484 --> 00:13:03,900
به صراحت زمان گذشته، و پس از آن
شما بچه ها شده اند با استفاده از آن

287
00:13:03,900 --> 00:13:08,160
برای getstring ندانسته برای
چند هفته، همه از حافظه malloc در

288
00:13:08,160 --> 00:13:09,820
می آید از پشته به اصطلاح.

289
00:13:09,820 --> 00:13:13,852
و این است که چرا getstring، به عنوان مثال،
می توانید حافظه به صورت پویا تخصیص

290
00:13:13,852 --> 00:13:16,060
بدون دانستن اینکه چه چیزی شما
رفتن به تایپ در پیش است،

291
00:13:16,060 --> 00:13:21,520
دست شما را به یک اشاره گر به حافظه،
و حافظه هنوز هم شما را نگه دارید،

292
00:13:21,520 --> 00:13:24,080
حتی پس از getstring بازده.

293
00:13:24,080 --> 00:13:27,450
از آنجا که فراخوان بعد از همه که
پشته به طور مداوم بالا و پایین رفتن،

294
00:13:27,450 --> 00:13:27,950
بالا و پایین.

295
00:13:27,950 --> 00:13:30,230
و به زودی به عنوان آن می رود
پایین، این بدان معناست که هر حافظه

296
00:13:30,230 --> 00:13:33,030
این تابع استفاده می شود باید
توان با هر کس دیگری استفاده نمی شود.

297
00:13:33,030 --> 00:13:34,570
در حال حاضر ارزش زباله است.

298
00:13:34,570 --> 00:13:36,120
>> اما پشته است در اینجا.

299
00:13:36,120 --> 00:13:39,360
و چه خوب است در مورد malloc است که
هنگامی که malloc حافظه اختصاص اینجا تا،

300
00:13:39,360 --> 00:13:42,070
آن نهفته نیست، برای
در اکثر موارد، توسط پشته.

301
00:13:42,070 --> 00:13:46,000
و به این ترتیب هر تابع می تواند دسترسی
حافظه است که malloc'd شده است،

302
00:13:46,000 --> 00:13:49,120
حتی با یک تابع مانند getstring،
حتی پس از آن برگردانده می شود.

303
00:13:49,120 --> 00:13:51,700
>> در حال حاضر، صحبت از malloc رایگان است.

304
00:13:51,700 --> 00:13:53,900
و در واقع، حکومت شما
نیاز به شروع به اتخاذ

305
00:13:53,900 --> 00:13:58,950
هر گونه، هر، هر زمان به شما استفاده از malloc
شما باید خودتان استفاده رایگان، در نهایت،

306
00:13:58,950 --> 00:14:00,280
در آن اشاره گر همان.

307
00:14:00,280 --> 00:14:03,289
در تمام این مدت ما نوشتن است
حشره دار، کد حشره دار، به دلایل زیادی.

308
00:14:03,289 --> 00:14:05,580
اما یکی از آنها بوده است
با استفاده از کتابخانه CS50، که

309
00:14:05,580 --> 00:14:09,010
خود را عمدا
حشره دار، آن نشت حافظه است.

310
00:14:09,010 --> 00:14:11,410
هر بار که شما getstring به نام ام
در طول چند هفته گذشته

311
00:14:11,410 --> 00:14:13,870
ما در حال درخواست از عامل
سیستم، لینوکس، برای حافظه است.

312
00:14:13,870 --> 00:14:15,780
و شما هرگز یک بار آن را به عقب داده شده.

313
00:14:15,780 --> 00:14:17,730
و این است که، در
عمل، چیز خوبی است.

314
00:14:17,730 --> 00:14:20,330
>> و Valgrind، یکی از
ابزار معرفی شده در Pset 4،

315
00:14:20,330 --> 00:14:22,900
همه چیز در مورد کمک به شما
در حال حاضر اشکالات مانند آن را پیدا کنید.

316
00:14:22,900 --> 00:14:27,060
اما از خود گذشتگی برای Pset 4 شما لازم نیست
برای استفاده از کتابخانه CS50 یا getstring.

317
00:14:27,060 --> 00:14:31,220
بنابراین هر گونه اشکالات مربوط به حافظه
در نهایت رفتن به خود شما.

318
00:14:31,220 --> 00:14:34,060
>> بنابراین malloc بیش از است
مناسب برای این منظور است.

319
00:14:34,060 --> 00:14:37,420
ما در واقع می تواند در حال حاضر حل
مشکلات اساسا متفاوت،

320
00:14:37,420 --> 00:14:41,640
و اساسا مشکلات را حل کند تر
به طور موثر به عنوان در هر وعده در هفته صفر است.

321
00:14:41,640 --> 00:14:44,720
تا کنون این آنتی ویروس است
ساختمان داده ما بود.

322
00:14:44,720 --> 00:14:47,804
و توسط ساختمان داده من فقط معنی
راه حافظه مفهوم

323
00:14:47,804 --> 00:14:50,720
در راه است که فراتر از فقط گفت می رود،
این یک int است، این کاراکتر است.

324
00:14:50,720 --> 00:14:52,930
ما می توانیم به همه چیز خوشه با هم شروع می شود.

325
00:14:52,930 --> 00:14:54,460
>> پس یک آرایه شبیه این بود.

326
00:14:54,460 --> 00:14:57,270
و چه کلیدی در مورد بود
آرایه است که آن را به شما می دهد

327
00:14:57,270 --> 00:14:59,724
پشت به پشت تکه
حافظه، که هر کدام

328
00:14:59,724 --> 00:15:02,765
در حال رفتن به از همان نوع است، اعضای هیات،
اعضای هیات، اعضای هیات، اعضای هیات، یا کاراکتر، کاراکتر، کاراکتر،

329
00:15:02,765 --> 00:15:03,330
کاراکتر.

330
00:15:03,330 --> 00:15:04,496
اما چند جنبه های منفی وجود دارد.

331
00:15:04,496 --> 00:15:06,570
این برای مثال،
آرایه ای از اندازه شش.

332
00:15:06,570 --> 00:15:10,650
فرض کنید که شما این مجموعه با شش پر
اعداد و پس از آن، به هر دلیل،

333
00:15:10,650 --> 00:15:13,187
کاربر خود را می خواهد به
شما یک شماره هفتم.

334
00:15:13,187 --> 00:15:14,020
از کجا می توانید آن را؟

335
00:15:14,020 --> 00:15:15,490

336
00:15:15,490 --> 00:15:18,990
>> راه حل چیست اگر شما
یک آرایه ایجاد شده در پشته،

337
00:15:18,990 --> 00:15:22,030
به عنوان مثال، فقط با هفته
دو نماد است که ما معرفی،

338
00:15:22,030 --> 00:15:23,730
از براکت مربع با تعداد در داخل؟

339
00:15:23,730 --> 00:15:25,160

340
00:15:25,160 --> 00:15:27,260
خوب، شما باید شش
اعداد در این جعبه.

341
00:15:27,260 --> 00:15:28,530
غرایز شما چه خواهد بود؟

342
00:15:28,530 --> 00:15:29,973
به کجا می خواهد شما می خواهید آن را قرار داده؟

343
00:15:29,973 --> 00:15:30,860
>> رسید [نامفهوم]

344
00:15:30,860 --> 00:15:31,315
>> DAVID J. مالان: متاسفم؟

345
00:15:31,315 --> 00:15:32,380
>> رسید آن را در پایان.

346
00:15:32,380 --> 00:15:33,796
>> DAVID J. مالان: قرار دادن در پایان.

347
00:15:33,796 --> 00:15:35,880
پس فقط به سمت راست،
در خارج از این جعبه.

348
00:15:35,880 --> 00:15:38,710
کدام خوبی خواهد بود، اما آن را
معلوم است که نمی تواند انجام دهد.

349
00:15:38,710 --> 00:15:41,350
از آنجا که اگر از شما خواسته ام
برای این بخش از حافظه،

350
00:15:41,350 --> 00:15:44,490
آن می تواند بر حسب تصادف که این می شود
است که توسط برخی از متغیر های دیگر استفاده می شود

351
00:15:44,490 --> 00:15:45,030
در دسترس نباشد.

352
00:15:45,030 --> 00:15:49,210
فکر می کنم یک هفته یا تا زمانی که ما گذاشته
از نام Zamyla و Davin و گیب را

353
00:15:49,210 --> 00:15:49,930
در حافظه است.

354
00:15:49,930 --> 00:15:51,638
آنها به معنای واقعی کلمه بود
پشت به پشت به پشت.

355
00:15:51,638 --> 00:15:53,550
بنابراین ما نمی توانیم لزوما
اعتماد که هر چه را

356
00:15:53,550 --> 00:15:55,800
بیش از اینجا در دسترس است برای من استفاده کنید.

357
00:15:55,800 --> 00:15:56,990
>> پس چه چیز دیگری ممکن است انجام دهید؟

358
00:15:56,990 --> 00:16:00,282
خب، یک بار متوجه شما
نیاز به یک مجموعه ای از اندازه هفت،

359
00:16:00,282 --> 00:16:02,490
شما فقط می تواند ایجاد
مجموعه ای از اندازه هفت سپس با استفاده از

360
00:16:02,490 --> 00:16:05,950
برای حلقه یا حلقه در حالی که،
کپی آن را به آرایه جدید،

361
00:16:05,950 --> 00:16:09,680
و پس از آن به نحوی فقط خلاص شدن از شر
این آرایه و یا فقط با استفاده از آن را متوقف کند.

362
00:16:09,680 --> 00:16:12,130
اما این به ویژه، موثر نیست.

363
00:16:12,130 --> 00:16:15,340
به طور خلاصه، آرایه اجازه ندهید
شما به صورت پویا تغییر اندازه.

364
00:16:15,340 --> 00:16:17,900
>> بنابراین از یک طرف شما
دسترسی تصادفی است که شگفت انگیز است.

365
00:16:17,900 --> 00:16:20,108
از آنجا که ما اجازه می دهد انجام کارهای
مانند تقسیم و حل،

366
00:16:20,108 --> 00:16:23,100
جستجوی دودویی، که همه ما انجام داده ایم
در مورد بر روی صفحه نمایش در اینجا صحبت کردیم.

367
00:16:23,100 --> 00:16:24,950
اما شما خود را به گوشه نقاشی.

368
00:16:24,950 --> 00:16:27,810
به محض این که شما آمار
پایان آرایه خود،

369
00:16:27,810 --> 00:16:29,980
شما باید انجام دهید بسیار
عملیات گران قیمت

370
00:16:29,980 --> 00:16:33,910
و یا ارسال یک دسته کامل از کد
در حال حاضر با این مشکل رسیدگی کند.

371
00:16:33,910 --> 00:16:36,680
>> بنابراین اگر به جای ما تا به حال
چیزی به نام لیست،

372
00:16:36,680 --> 00:16:38,820
و یا یک لیست پیوندی به ویژه؟

373
00:16:38,820 --> 00:16:41,930
داشتن چه می شود اگر به جای
مستطیل پشت به پشت به پشت،

374
00:16:41,930 --> 00:16:45,730
ما باید مستطیل است که کمی ترک
کمی از اتاق تکان دادن در بین آنها؟

375
00:16:45,730 --> 00:16:49,670
و حتی اگر من این رسم کرده ایم.
تصویر و یا اقتباس این تصویر

376
00:16:49,670 --> 00:16:54,696
از یکی از متون در اینجا برای بازگشت به
پشت به پشت بسیار منظم، در واقع،

377
00:16:54,696 --> 00:16:56,820
یکی از کسانی که مستطیل
می تواند تا اینجا در حافظه است.

378
00:16:56,820 --> 00:16:58,028
یکی از آنها را در اینجا می تواند تا شود.

379
00:16:58,028 --> 00:17:00,420
یکی از آنها می تواند در اینجا،
در اینجا، و غیره.

380
00:17:00,420 --> 00:17:02,910
>> اما اگر ما به خود جلب کرد،
در این مورد، فلش

381
00:17:02,910 --> 00:17:05,650
که به نحوی پیوند این
مستطیل با هم؟

382
00:17:05,650 --> 00:17:08,170
در واقع، ما دیده ایم فنی
تجسم از فلش.

383
00:17:08,170 --> 00:17:09,839

384
00:17:09,839 --> 00:17:13,710
چه ما در اخیر مورد استفاده قرار
روز که، در زیر هود،

385
00:17:13,710 --> 00:17:15,210
نماینده فلش است؟

386
00:17:15,210 --> 00:17:16,290

387
00:17:16,290 --> 00:17:17,349
یک اشاره گر، درست است؟

388
00:17:17,349 --> 00:17:19,780
>> پس چه می شود اگر، به جای
فقط ذخیره سازی اعداد،

389
00:17:19,780 --> 00:17:23,130
مانند 9، 17، 22، 26، 34،
اگر ما ذخیره نمی شوند

390
00:17:23,130 --> 00:17:27,079
تنها تعداد اما یک اشاره گر
در کنار هر عدد مانند؟

391
00:17:27,079 --> 00:17:30,690
به طوری که بسیار شبیه به شما یک موضوع
سوزن از طریق یک دسته کامل از پارچه،

392
00:17:30,690 --> 00:17:32,950
همه چیز به نحوی تساوی
با هم، به طور مشابه می تواند

393
00:17:32,950 --> 00:17:35,550
ما با اشاره گر، به عنوان
تجسم های فلش در اینجا،

394
00:17:35,550 --> 00:17:38,550
نوع با هم بافتن
این مستطیل فردی

395
00:17:38,550 --> 00:17:41,780
به طور موثر با استفاده از اشاره گر
در کنار هر تعداد که

396
00:17:41,780 --> 00:17:46,065
اشاره به برخی از عدد بعدی، که
اشاره به، به نوبه خود، برخی از عدد بعدی؟

397
00:17:46,065 --> 00:17:47,940
بنابراین به عبارت دیگر، آنچه که
اگر ما در واقع می خواستم

398
00:17:47,940 --> 00:17:49,820
برای پیاده سازی چیزی شبیه به این؟

399
00:17:49,820 --> 00:17:53,610
خوب متاسفانه، این مستطیل ها،
حداقل یکی از با 9، 17، 22،

400
00:17:53,610 --> 00:17:57,040
و به این ترتیب، این دیگر
مربع زیبا با اعداد یک.

401
00:17:57,040 --> 00:17:59,960
پایین، مستطیل
زیر 9، به عنوان مثال،

402
00:17:59,960 --> 00:18:04,330
نشان دهنده چیزی است که باید
یک اشاره گر، 32 بیت.

403
00:18:04,330 --> 00:18:09,460
در حال حاضر، من هنوز از هر نوع داده آگاه نیست
در C است که به شما نه تنها یک int

404
00:18:09,460 --> 00:18:11,630
اما یک اشاره گر در دسترس نباشد.

405
00:18:11,630 --> 00:18:15,020
>> پس چه راه حل اگر ما می خواهیم
به اختراع جواب خود ما در این؟

406
00:18:15,020 --> 00:18:15,760
آره؟

407
00:18:15,760 --> 00:18:16,640
>> رسید [نامفهوم]

408
00:18:16,640 --> 00:18:17,360
>> DAVID J. مالان: آن چیست؟

409
00:18:17,360 --> 00:18:17,880
>> رسید ساختار جدید.

410
00:18:17,880 --> 00:18:19,590
>> DAVID J. مالان: آره، پس چرا
ما یک ساختار جدید ایجاد کنید،

411
00:18:19,590 --> 00:18:20,920
و یا در C، یک ساختار؟

412
00:18:20,920 --> 00:18:25,990
ما ساختار دیده می شود قبل از، اگر به طور خلاصه،
که در آن ما با یک ساختار دانش آموز سر و کار داشتن

413
00:18:25,990 --> 00:18:27,780
مثل این که یک نام و یک خانه داشت.

414
00:18:27,780 --> 00:18:31,980
در Pset 3 برک آوت شما با استفاده از یک کل
دسته از GRect structs-- و GOvals

415
00:18:31,980 --> 00:18:34,810
که استنفورد به ایجاد
اطلاعات خوشه با هم.

416
00:18:34,810 --> 00:18:38,580
بنابراین اگر ما این ایده را مشابه از
کلمات کلیدی "typedef" و "ساختار"

417
00:18:38,580 --> 00:18:42,890
و پس از آن برخی چیزهای خاص به دانش آموزان،
و تکامل این به شرح زیر است:

418
00:18:42,890 --> 00:18:46,210
typedef ساختار node-- و گره است
فقط یک علم کامپیوتر بسیار عمومی

419
00:18:46,210 --> 00:18:49,980
مدت چیزی در یک ساختار داده ها،
یک ظرف در یک ساختار داده ها.

420
00:18:49,980 --> 00:18:53,900
یک گره I ادعا است که به
تعداد اعضای هیات، کاملا سر راست،

421
00:18:53,900 --> 00:18:58,810
و پس از آن کمی cryptically بیشتر،
این خط دوم، گره ساختار * بعدی.

422
00:18:58,810 --> 00:19:01,300
اما از نظر فنی کمتر،
آنچه که خط دوم است

423
00:19:01,300 --> 00:19:02,980
کد داخل آکولاد؟

424
00:19:02,980 --> 00:19:03,737
آره؟

425
00:19:03,737 --> 00:19:04,851
>> رسید [نامفهوم]

426
00:19:04,851 --> 00:19:06,600
DAVID J. مالان:
اشاره گر به گره دیگر.

427
00:19:06,600 --> 00:19:09,910
بنابراین مسلما، نحو (Syntax) کمی مرموز.

428
00:19:09,910 --> 00:19:13,250
اما اگر شما آن را به عنوان خوانده شده به معنای واقعی کلمه،
بعد به نام یک متغیر است.

429
00:19:13,250 --> 00:19:14,410
نوع داده آن چیست؟

430
00:19:14,410 --> 00:19:18,206
این یک کمی طولانی این زمان،
اما از نوع گره ساختار است *.

431
00:19:18,206 --> 00:19:22,960
هر زمان دیده ایم چیزی ستاره، که
به معنی آن است که یک اشاره گر به نوع داده است.

432
00:19:22,960 --> 00:19:26,810
بنابراین بعد ظاهرا
اشاره گر به گره ساختار.

433
00:19:26,810 --> 00:19:28,310
>> در حال حاضر، آنچه که یک گره ساختار است؟

434
00:19:28,310 --> 00:19:31,044
خوب، شما متوجه آن نگاه کنید
کلمات مشابه در سمت راست بالا.

435
00:19:31,044 --> 00:19:33,960
و در واقع، شما همچنین کلمه را ببینید
"گره" را در اینجا در سمت چپ پایین.

436
00:19:33,960 --> 00:19:35,640
و این در واقع فقط یک راحتی.

437
00:19:35,640 --> 00:19:39,930
توجه کنید که در تعریف دانش آموز ما
در کلمه "دانش آموز" تنها یک بار وجود دارد.

438
00:19:39,930 --> 00:19:42,510
و این به دلیل یک دانش آموز
شی بود خود ارجاع نمی شود.

439
00:19:42,510 --> 00:19:45,340
هیچ چیز در داخل از یک دانش آموز وجود دارد
که نیاز به نقطه را به یکی دیگر از دانشجویان،

440
00:19:45,340 --> 00:19:45,610
persay.

441
00:19:45,610 --> 00:19:47,630
این امر می تواند مرتب کردن بر اساس
عجیب و غریب در جهان واقعی است.

442
00:19:47,630 --> 00:19:50,880
>> اما با یک گره در یک مرتبط
لیست، ما می خواهیم یک گره

443
00:19:50,880 --> 00:19:53,970
به ارجاع به یک شی مشابه است.

444
00:19:53,970 --> 00:19:57,900
و به این ترتیب متوجه تغییر در اینجا نیست
فقط آنچه در داخل آکولاد است.

445
00:19:57,900 --> 00:20:00,800
اما ما اضافه کردن کلمه "گره"
در بالای و همچنین

446
00:20:00,800 --> 00:20:02,930
اضافه کردن آن را به پایین
به جای "دانش آموز."

447
00:20:02,930 --> 00:20:06,000
و این تنها یکی از جزئیات فنی است
به طوری که، دوباره، ساختار داده ها خود را

448
00:20:06,000 --> 00:20:11,380
می تواند خود ارجاع، به طوری که
گره می تواند به چنین گره دیگر اشاره می کنند.

449
00:20:11,380 --> 00:20:13,840
>> پس چه است این در نهایت
رفتن به برای ما چیست؟

450
00:20:13,840 --> 00:20:17,560
خب، یک، این مسائل در داخل
محتویات گره های ما است.

451
00:20:17,560 --> 00:20:19,360
این چیزی که در اینجا،
بالا سمت راست، خیلی

452
00:20:19,360 --> 00:20:20,860
که، دوباره، ما می توانیم به خودمان مراجعه کنید.

453
00:20:20,860 --> 00:20:23,401
و پس از آن مسائل بیرونی ترین،
حتی اگر گره یک اصطلاح جدید است،

454
00:20:23,401 --> 00:20:25,500
شاید، آن را هنوز هم
همان دانش آموز و چه

455
00:20:25,500 --> 00:20:27,520
در زیر هود در SPL بود.

456
00:20:27,520 --> 00:20:31,095
>> بنابراین اگر ما در حال حاضر می خواستم برای شروع
اجرای این لیست پیوندی،

457
00:20:31,095 --> 00:20:33,220
چگونه ممکن است ما در ترجمه
چیزی شبیه به این کد؟

458
00:20:33,220 --> 00:20:35,350
خوب، اجازه دهید فقط ببینید
نمونه ای از یک برنامه ای است که

459
00:20:35,350 --> 00:20:36,840
در واقع با استفاده از لیست پیوندی.

460
00:20:36,840 --> 00:20:40,870
در میان کد توزیع امروز
برنامه ای به نام فهرست صفر است.

461
00:20:40,870 --> 00:20:44,980
و اگر من این اجرا I فوق العاده ایجاد شده
GUI ساده، رابط کاربر گرافیکی،

462
00:20:44,980 --> 00:20:46,460
اما آن را واقعا فقط تابع () printf.

463
00:20:46,460 --> 00:20:50,930
و در حال حاضر من خودم چند منو داده ام
options-- حذف، درج، جستجو،

464
00:20:50,930 --> 00:20:51,750
و گذشتن از.

465
00:20:51,750 --> 00:20:52,630
و ترک.

466
00:20:52,630 --> 00:20:55,970
این عملیات فقط رایج در می
ساختار داده ها شناخته شده است به عنوان یک لیست لینک کنید.

467
00:20:55,970 --> 00:20:58,409
>> در حال حاضر، حذف است که به
یک شماره از لیست حذف کنید.

468
00:20:58,409 --> 00:21:00,200
درج رفتن به اضافه
تعداد به لیست.

469
00:21:00,200 --> 00:21:02,181
جستجو در حال رفتن به نگاه
شماره در لیست.

470
00:21:02,181 --> 00:21:04,930
و گذشتن از فقط یک راه فانتزی
گفتن، راه رفتن از طریق لیست،

471
00:21:04,930 --> 00:21:06,245
آن را چاپ، اما که این.

472
00:21:06,245 --> 00:21:07,720
آیا آن را در هر راه را تغییر دهید.

473
00:21:07,720 --> 00:21:08,570
>> بنابراین اجازه دهید این را امتحان کنید.

474
00:21:08,570 --> 00:21:10,160
اجازه دهید به پیش بروید و نوع 2.

475
00:21:10,160 --> 00:21:12,710
و پس از آن من قصد دارم به
وارد کردن تعداد، می گویند 9.

476
00:21:12,710 --> 00:21:13,620
را وارد کنید.

477
00:21:13,620 --> 00:21:17,480
و در حال حاضر برنامه من است تنها
برنامه ریزی برای گفتن، لیست در حال حاضر 9.

478
00:21:17,480 --> 00:21:20,190
در حال حاضر، اگر من به جلو و
انجام دادن دوباره، اجازه

479
00:21:20,190 --> 00:21:23,680
من به جلو و زوم کردن و تایپ 17.

480
00:21:23,680 --> 00:21:25,770
در حال حاضر لیست من 9 است، پس از آن 17.

481
00:21:25,770 --> 00:21:27,750
اگر من کار را دوباره وارد کنید، اجازه دهید یک جست و خیز.

482
00:21:27,750 --> 00:21:32,400
به جای 22، به عنوان در تصویر ما ام
شده است به دنبال در اینجا، اجازه دهید من پرش های پیش رو

483
00:21:32,400 --> 00:21:34,630
و قرار دادن 26 بعدی.

484
00:21:34,630 --> 00:21:36,230
من می خواهم به نوع 26.

485
00:21:36,230 --> 00:21:37,755
این فهرست که من انتظار می رود.

486
00:21:37,755 --> 00:21:40,630
اما در حال حاضر، فقط برای دیدن در صورتی که این کد
در حال رفتن به انعطاف پذیر، به من اجازه دهید اکنون

487
00:21:40,630 --> 00:21:43,520
نوع 22، که حداقل
مفهومی، اگر ما

488
00:21:43,520 --> 00:21:46,520
نگه داشتن این طبقه بندی شده اند، که در واقع
رفتن به یک گل دیگه در حال حاضر،

489
00:21:46,520 --> 00:21:48,690
باید در بین 17 و 26 است.

490
00:21:48,690 --> 00:21:50,270
بنابراین من آمار را وارد کنید.

491
00:21:50,270 --> 00:21:51,380
در واقع، کار می کند.

492
00:21:51,380 --> 00:21:54,950
و بنابراین در حال حاضر به من اجازه قرار دادن
آخرین، در این تصویر، 34.

493
00:21:54,950 --> 00:21:55,450
>> خوب.

494
00:21:55,450 --> 00:21:58,980
بنابراین در حال حاضر اجازه دهید من تصریح می کند که
حذف و گذشتن از جستجو و انجام،

495
00:21:58,980 --> 00:21:59,760
در واقع، کار می کنند.

496
00:21:59,760 --> 00:22:04,180
در واقع، اگر من جستجو را اجرا کنید، اجازه دهید
جستجو برای شماره 22، را وارد کنید.

497
00:22:04,180 --> 00:22:05,010
این است 22.

498
00:22:05,010 --> 00:22:07,580
بنابراین این چیزی است که این
برنامه فهرست صفر می کند.

499
00:22:07,580 --> 00:22:10,230
>> اما آنچه که در واقع رفتن
در که پیاده سازی این؟

500
00:22:10,230 --> 00:22:14,530
خب، اول من ممکن است، و در واقع
من لازم، یک فایل با نام list0.h.

501
00:22:14,530 --> 00:22:16,540

502
00:22:16,540 --> 00:22:20,690
و در جایی در این وجود دارد
خط، typedef، گره ساختار،

503
00:22:20,690 --> 00:22:24,850
پس من باید آکولاد من، اعضای هیات نفر، و
پس از آن struct-- چه تعریف بود؟

504
00:22:24,850 --> 00:22:26,530

505
00:22:26,530 --> 00:22:28,545
گره ساختار بعدی.

506
00:22:28,545 --> 00:22:29,920

507
00:22:29,920 --> 00:22:31,045
بنابراین ما نیاز به ستاره.

508
00:22:31,045 --> 00:22:33,420
در حال حاضر از لحاظ فنی ما را به دریافت
عادت رسم آن را در اینجا.

509
00:22:33,420 --> 00:22:35,670
شما ممکن است کتاب های درسی را مشاهده کنید و
منابع آنلاین این کار را انجام وجود دارد.

510
00:22:35,670 --> 00:22:36,660
این عملکرد معادل آن.

511
00:22:36,660 --> 00:22:37,980
در واقع، این است که به طور معمول کمی بیشتر است.

512
00:22:37,980 --> 00:22:40,563
اما من که مطابق با آنچه
ما زمان گذشته و این کار را.

513
00:22:40,563 --> 00:22:42,350
و سپس در آخر، من قصد دارم برای انجام این کار.

514
00:22:42,350 --> 00:22:45,550
>> بنابراین در یک فایل هدر
در جایی، در list0.h

515
00:22:45,550 --> 00:22:49,200
امروز این تعریف ساختار است،
و شاید برخی از چیزهای دیگر است.

516
00:22:49,200 --> 00:22:52,580
در همین حال در list0c وجود دارد
رفتن به چند چیز.

517
00:22:52,580 --> 00:22:54,740
اما ما قصد داریم به تنها
شروع و این پایان نیست.

518
00:22:54,740 --> 00:22:59,690
List0.h یک فایل من می خواهم
در فایل C من باشد.

519
00:22:59,690 --> 00:23:03,910
و پس از آن در برخی از نقطه من
رفتن به هوشمند، اصلی، از درجه اعتبار ساقط.

520
00:23:03,910 --> 00:23:06,530
و پس از آن من قصد دارم به
برخی از کارهای در اینجا.

521
00:23:06,530 --> 00:23:10,620
من هم از رفتن به یک
نمونه اولیه، مانند خالی، جستجو، اعضای هیات،

522
00:23:10,620 --> 00:23:13,610
نفر، که هدف در زندگی است
برای جستجوی یک عنصر.

523
00:23:13,610 --> 00:23:18,310
و سپس در اینجا من ادعا می کنند در
کد امروز، از درجه اعتبار ساقط، جستجو، اعضای هیات، نفر،

524
00:23:18,310 --> 00:23:21,020
هیچ نقطه و ویرگول بدین اما آکولاد باز.

525
00:23:21,020 --> 00:23:25,049
و در حال حاضر من می خواهم به نحوی جستجو
برای یک عنصر در این لیست.

526
00:23:25,049 --> 00:23:27,340
اما ما به اندازه کافی ندارد
اطلاعات بر روی صفحه نمایش است.

527
00:23:27,340 --> 00:23:29,800
من نمی در واقع
نشان داده شده در لیست خود دارد.

528
00:23:29,800 --> 00:23:33,070
بنابراین یکی از راه های ما می تواند پیاده سازی
یک لیست پیوندی در یک برنامه

529
00:23:33,070 --> 00:23:37,520
است I نوع می خواهید برای انجام کاری
مانند اعلان ها اینجا مرتبط است.

530
00:23:37,520 --> 00:23:40,520
برای سادگی، من قصد دارم به
این جهانی است، حتی اگر در ما به طور کلی

531
00:23:40,520 --> 00:23:41,645
باید این بیش از حد انجام ندهید.

532
00:23:41,645 --> 00:23:43,260
اما از آن خواهد شد این مثال ساده.

533
00:23:43,260 --> 00:23:45,890
بنابراین من می خواهم به اعلام
یک لیست پیوندی در اینجا.

534
00:23:45,890 --> 00:23:47,010
در حال حاضر، چگونه ممکن است من که؟

535
00:23:47,010 --> 00:23:48,810

536
00:23:48,810 --> 00:23:50,750
>> در اینجا تصویری از یک لیست پیوندی است.

537
00:23:50,750 --> 00:23:53,030
و من واقعا نمی
می دانم که در حال حاضر چگونه

538
00:23:53,030 --> 00:23:56,710
من قصد دارم به نمایندگی از حدود بروید
بسیاری از چیزهایی که با یک فقط

539
00:23:56,710 --> 00:23:58,040
متغیر در حافظه است.

540
00:23:58,040 --> 00:23:59,160
اما فکر می کنم یک لحظه.

541
00:23:59,160 --> 00:24:00,830
در تمام این مدت ما داشته ایم
رشته، که ما پس از آن

542
00:24:00,830 --> 00:24:02,913
نشان داد که آرایه از
شخصیت ها، که ما پس از آن

543
00:24:02,913 --> 00:24:05,740
نشان داد که فقط یک اشاره گر
به اولین کاراکتر

544
00:24:05,740 --> 00:24:08,890
در آرایه ای از کاراکتر ها
که متناهی.

545
00:24:08,890 --> 00:24:13,530
پس با این منطق، و با این
نوع تصویر از بذر افکار خود را،

546
00:24:13,530 --> 00:24:17,964
چه نیاز ما در واقع در ارسال ما
کد برای نشان دادن یک لیست پیوندی؟

547
00:24:17,964 --> 00:24:21,130
چه مقدار از این اطلاعات کار ما نیاز
را به تصرف در کد C، به شما می گویند؟

548
00:24:21,130 --> 00:24:22,654

549
00:24:22,654 --> 00:24:23,154
آره؟

550
00:24:23,154 --> 00:24:24,738
>> رسید ما نیاز به یک اشاره گر به گره.

551
00:24:24,738 --> 00:24:26,237
DAVID J. مالان: یک اشاره گر به گره.

552
00:24:26,237 --> 00:24:29,320
به طور خاص، که گره را خود
غرایز است برای حفظ یک اشاره گر به؟

553
00:24:29,320 --> 00:24:30,026
>> رسید اولین گره.

554
00:24:30,026 --> 00:24:31,942
>> DAVID J. مالان: آره،
احتمالا فقط در صفحه اول

555
00:24:31,942 --> 00:24:34,030
و متوجه، اولین
گره یک شکل متفاوت است.

556
00:24:34,030 --> 00:24:37,690
این تنها نیمی از اندازه از ساختار است،
زیرا این در واقع تنها یک اشاره گر.

557
00:24:37,690 --> 00:24:44,650
بنابراین آنچه شما در واقع می تواند انجام دهد، اعلام
یک لیست پیوندی به گره نوع است *.

558
00:24:44,650 --> 00:24:47,780
و اجازه دهید فقط آن را برای اولین بار تماس بگیرید
و مقدار دهی اولیه آن را به تهی.

559
00:24:47,780 --> 00:24:49,910
بنابراین تهی، دوباره، به زودی
را به تصویر اینجا.

560
00:24:49,910 --> 00:24:53,620
نه تنها null به عنوان مثل یک خاص استفاده می شود
مقدار بازگشتی برای چیزهایی مانند getstring

561
00:24:53,620 --> 00:24:57,770
و malloc، پوچ است نیز صفر
اشاره گر، به دلیل نبود یک اشاره گر،

562
00:24:57,770 --> 00:24:58,430
اگر شما خواهد شد.

563
00:24:58,430 --> 00:25:00,309
این فقط به معنای چیزی است که هنوز در اینجا.

564
00:25:00,309 --> 00:25:02,100
در حال حاضر برای اولین بار، من می تونستیم
نام این هر چیزی.

565
00:25:02,100 --> 00:25:04,200
من می توانم آن را "فهرست" نامیده می شود
و یا هر تعداد از چیزهای دیگر.

566
00:25:04,200 --> 00:25:06,960
اما من آن را خواستار "اولین" به طوری که
خطوط آن را با این عکس.

567
00:25:06,960 --> 00:25:10,280
بنابراین درست مثل یک رشته را می توان ارائه
با آدرس اولین بایت آن،

568
00:25:10,280 --> 00:25:11,280
بنابراین می توانید یک لیست پیوندی.

569
00:25:11,280 --> 00:25:13,480
و ما به داده های دیگر را ببینید
ساختار به نمایندگی

570
00:25:13,480 --> 00:25:16,700
تنها با یک اشاره گر،
32 بیتی فلش، با اشاره

571
00:25:16,700 --> 00:25:18,740
در اولین گره در ساختار.

572
00:25:18,740 --> 00:25:20,340
>> اما در حال حاضر اجازه دهید یک مشکل پیش بینی.

573
00:25:20,340 --> 00:25:23,230
اگر من فقط به یاد
در برنامه من آدرس

574
00:25:23,230 --> 00:25:27,220
از گره اول، اولین
مستطیل در این ساختار داده ها،

575
00:25:27,220 --> 00:25:31,760
چه بهتر که این مورد در مورد
اجرای بقیه لیست من؟

576
00:25:31,760 --> 00:25:35,820
جزئیات کلیدی که رفتن چه
برای اطمینان از این در واقع کار می کند؟

577
00:25:35,820 --> 00:25:39,250
و با "در واقع کار می کند" I
معنی، بسیار شبیه به یک رشته،

578
00:25:39,250 --> 00:25:42,180
اجازه می دهد تا ما را از اولین کاراکتر به
در نام Davin به دوم،

579
00:25:42,180 --> 00:25:44,755
به سوم، به
چهارم، به پایان،

580
00:25:44,755 --> 00:25:47,880
چگونه ما می دانیم زمانی که ما در پایان هستید
از یک لیست پیوندی است که به نظر می رسد مثل این؟

581
00:25:47,880 --> 00:25:50,035

582
00:25:50,035 --> 00:25:50,660
هنگامی که آن را تهی.

583
00:25:50,660 --> 00:25:53,640
و این نوع از عنوان I نشان داده ام
مانند قدرت، مهندس برق،

584
00:25:53,640 --> 00:25:56,420
با زمین کمی
نماد، از انواع.

585
00:25:56,420 --> 00:25:58,246
اما این فقط به معنی تهی در این مورد.

586
00:25:58,246 --> 00:26:00,370
شما می توانید آن را به هر تعداد در قرعه کشی
از راه، اما این کاربر

587
00:26:00,370 --> 00:26:02,800
اتفاق افتاده است برای استفاده از این نماد را اینجا.

588
00:26:02,800 --> 00:26:06,260
>> تا زمانی که ما در حال نخ کشیدن برگهای توتون
تمام این گره با هم،

589
00:26:06,260 --> 00:26:08,600
تنها یاد آوردن جایی که
یکی از اولین است، تا زمانی

590
00:26:08,600 --> 00:26:11,760
ما به عنوان یک نماد ویژه در قرار داده
آخرین گره در لیست،

591
00:26:11,760 --> 00:26:15,130
و ما تهی استفاده کنید، زیرا که
آنچه که ما را در دسترس ما،

592
00:26:15,130 --> 00:26:16,480
این لیست کامل می باشد.

593
00:26:16,480 --> 00:26:20,190
و حتی اگر فقط من به شما یک اشاره گر را به
عنصر اول، شما، برنامه نویس،

594
00:26:20,190 --> 00:26:22,486
مطمئنا می تواند بقیه از آن دسترسی داشته باشید.

595
00:26:22,486 --> 00:26:24,360
اما اجازه دهید اجازه دهید ذهن شما
سرگردان کمی،

596
00:26:24,360 --> 00:26:26,140
اگر آنها در حال حاضر نمی
کاملا wandered-- چه

597
00:26:26,140 --> 00:26:28,723
رفتن به زمان در حال اجرا از
پیدا کردن هر چیزی در این لیست؟

598
00:26:28,723 --> 00:26:30,450

599
00:26:30,450 --> 00:26:33,470
لعنت آن، آن را O بزرگ از n است،
است که بد نیست، در انصاف.

600
00:26:33,470 --> 00:26:34,800
اما این خطی است.

601
00:26:34,800 --> 00:26:37,980
ما شده اند تا با توجه به آنچه از ویژگی های
آرایه های حرکت بیشتر

602
00:26:37,980 --> 00:26:43,130
به سمت این تصویر از به صورت پویا
با هم بافته شده و یا گره های مرتبط است؟

603
00:26:43,130 --> 00:26:44,970

604
00:26:44,970 --> 00:26:46,687
ما تا دسترسی تصادفی داده ام.

605
00:26:46,687 --> 00:26:48,770
یک آرایه خوب است زیرا است
همه چیز ریاضی

606
00:26:48,770 --> 00:26:50,340
بازگشت به عقب به عقب به عقب.

607
00:26:50,340 --> 00:26:52,370
هر چند این تصویر
به نظر می رسد بسیار، و حتی

608
00:26:52,370 --> 00:26:55,830
هر چند آن را مانند این به نظر می رسد گره
سادگی فاصله از هم جدا، در واقعیت

609
00:26:55,830 --> 00:26:56,830
آنها در هر نقطه می تواند باشد.

610
00:26:56,830 --> 00:27:01,590
OX1، Ox50، Ox123، Ox99، این
گره در هر نقطه می تواند باشد.

611
00:27:01,590 --> 00:27:05,960
از آنجا که malloc تخصیص حافظه می کند
از پشته، اما در هر نقطه از پشته.

612
00:27:05,960 --> 00:27:09,080
شما لزوما نمی دانند که این
رفتن به پشت به پشت به پشت.

613
00:27:09,080 --> 00:27:12,460
و به این ترتیب این تصویر در واقع در
نمی شود کاملا این بسیار.

614
00:27:12,460 --> 00:27:16,140
>> پس از آن رفتن را به یک بیت از
کار به پیاده سازی این تابع.

615
00:27:16,140 --> 00:27:17,880
بنابراین در حال حاضر در اجرای جستجو دهید.

616
00:27:17,880 --> 00:27:20,250
و ما به نوع ببینید
راه هوشمندانه برای انجام این کار.

617
00:27:20,250 --> 00:27:24,660
بنابراین اگر من یک تابع جستجو هستم و
I داده شده من یک متغیر، عدد صحیح n

618
00:27:24,660 --> 00:27:28,490
به دنبال، من نیاز به دانستن
نحو جدید برای نگاه کردن درون

619
00:27:28,490 --> 00:27:32,400
از یک ساختار که
با اشاره به، برای پیدا کردن نفر.

620
00:27:32,400 --> 00:27:33,210
بنابراین اجازه دهید این کار را انجام.

621
00:27:33,210 --> 00:27:36,030
>> پس اول من قصد دارم به
پیش رو و اعلام یک گره *.

622
00:27:36,030 --> 00:27:39,400
و من قصد دارم به آن تماس بگیرید
اشاره گر، فقط با کنوانسیون.

623
00:27:39,400 --> 00:27:41,710
و من قصد دارم به آن مقداردهی اولیه به اولین.

624
00:27:41,710 --> 00:27:43,770
و در حال حاضر من می توانم این کار را انجام
در تعدادی از راه.

625
00:27:43,770 --> 00:27:45,436
اما من قصد دارم به یک رویکرد مشترک.

626
00:27:45,436 --> 00:27:50,180
در حالی که اشاره گر است به برابر نیست
تهی، و نحو معتبر است.

627
00:27:50,180 --> 00:27:54,550
و آن را فقط به معنی انجام موارد زیر، به طوری که
زمانی که شما در هیچ چیز اشاره نمی کند.

628
00:27:54,550 --> 00:27:55,800
چه می خواهند انجام دهم؟

629
00:27:55,800 --> 00:28:01,939
>> اگر اشاره گر نقطه نفر، اجازه دهید من می آیند
به که، equals-- برابر چه؟

630
00:28:01,939 --> 00:28:03,105
چه ارزش هستم من به دنبال؟

631
00:28:03,105 --> 00:28:04,920

632
00:28:04,920 --> 00:28:06,590
تعداد واقعی است که در گذشته بود.

633
00:28:06,590 --> 00:28:09,020
بنابراین در اینجا یکی دیگر از ویژگی ها
از C و بسیاری از زبان های.

634
00:28:09,020 --> 00:28:13,705
حتی اگر ساختار به نام گره
یک نفر ارزش، کاملا مشروع

635
00:28:13,705 --> 00:28:17,530
به استدلال های محلی نیز
یا متغیر به نام n است.

636
00:28:17,530 --> 00:28:20,085
از آنجا که حتی ما، با
چشم انسان، می تواند تشخیص

637
00:28:20,085 --> 00:28:22,087
که این تعداد احتمالا
متفاوت از این تعداد.

638
00:28:22,087 --> 00:28:23,420
از آنجا که نوشتن متفاوت است.

639
00:28:23,420 --> 00:28:26,211
شما یک نقطه و یک اشاره گر داریم،
در حالی که این یکی هم چنین چیزی.

640
00:28:26,211 --> 00:28:27,290
پس این خوب است.

641
00:28:27,290 --> 00:28:29,120
این OK به آنها را همان چیزی را.

642
00:28:29,120 --> 00:28:32,380
>> اگر من شما را در این پیدا کردن، من هستم
رفتن به خواهید برای انجام کاری

643
00:28:32,380 --> 00:28:35,000
مانند اعلام کند که ما در بر داشت نفر.

644
00:28:35,000 --> 00:28:37,930
و ما را ترک که به عنوان یک
ارسال نظر یا کد شبه.

645
00:28:37,930 --> 00:28:40,190
دیگری، و در اینجا
بخش جالب، چه

646
00:28:40,190 --> 00:28:47,320
من می خواهم به انجام اگر گره فعلی
است شامل n که من اهمیت ندارد؟

647
00:28:47,320 --> 00:28:50,700
چگونه این کارها را رسیدن به من؟

648
00:28:50,700 --> 00:28:53,710
اگر انگشت من در
لحظه PTR است، و آن را

649
00:28:53,710 --> 00:28:55,920
اشاره در هر
برای اولین بار است اشاره در،

650
00:28:55,920 --> 00:28:59,290
چگونه انگشت من حرکت من
به گره بعدی در کد؟

651
00:28:59,290 --> 00:29:01,915
خوب، چه خرده نان ما است
به دنبال در این مورد؟

652
00:29:01,915 --> 00:29:03,464

653
00:29:03,464 --> 00:29:04,380
رسید [نامفهوم].

654
00:29:04,380 --> 00:29:05,630
DAVID J. مالان: آره، تا بعد.

655
00:29:05,630 --> 00:29:06,640

656
00:29:06,640 --> 00:29:09,824
بنابراین اگر من به بازگشت به من
کد اینجا، در واقع، من

657
00:29:09,824 --> 00:29:12,990
رفتن به جلو بروید و می گویند اشاره گر، که
فقط یک variable-- موقت آن است

658
00:29:12,990 --> 00:29:15,320
یک نام عجیب و غریب، PTR، اما
درست مثل temp--

659
00:29:15,320 --> 00:29:19,234
من قصد دارم به راه اشاره گر
به هر اشاره گر is-- برابر

660
00:29:19,234 --> 00:29:22,150
و دوباره، این است که برای رفتن به یک
حشره دار کمی برای یک نقطه moment-- بعدی.

661
00:29:22,150 --> 00:29:23,551

662
00:29:23,551 --> 00:29:26,550
به عبارت دیگر، من قصد دارم به من
انگشت که اشاره به این گره

663
00:29:26,550 --> 00:29:31,247
در اینجا و من قصد دارم برای گفتن، شما می دانید
چه، نگاهی به زمینه بعدی

664
00:29:31,247 --> 00:29:33,330
و حرکت انگشت خود را به
هر چه آن را اشاره در.

665
00:29:33,330 --> 00:29:35,163
و این است که به
تکرار، تکرار، تکرار کنید.

666
00:29:35,163 --> 00:29:37,630
اما وقتی انگشت من می کند
جلوگیری از انجام هر چیزی در همه؟

667
00:29:37,630 --> 00:29:40,095
به محض این که چه خط از ضربات کد در؟

668
00:29:40,095 --> 00:29:40,970
رسید [نامفهوم]

669
00:29:40,970 --> 00:29:43,060
DAVID J. مالان: اگر در حالی که نقطه
اشاره گر برابر تهی نیست.

670
00:29:43,060 --> 00:29:44,900
در برخی از نقطه انگشت من
رفتن به اشاره است در تهی

671
00:29:44,900 --> 00:29:47,070
و من قصد دارم به درک
که در پایان به این لیست است.

672
00:29:47,070 --> 00:29:48,910
در حال حاضر، این است که کمی
دروغ های سفید برای سادگی.

673
00:29:48,910 --> 00:29:51,580
به نظر می رسد که حتی اگر ما
فقط یاد گرفته این نماد نقطه

674
00:29:51,580 --> 00:29:55,220
برای سازه، اشاره گر است یک ساختار نیست.

675
00:29:55,220 --> 00:29:56,580
PTR چیزی است؟

676
00:29:56,580 --> 00:29:58,350
فقط به nitpicky است.

677
00:29:58,350 --> 00:29:59,720

678
00:29:59,720 --> 00:30:01,360
این یک اشاره گر به یک گره است.

679
00:30:01,360 --> 00:30:03,120
این یک گره به خودی خود نیست.

680
00:30:03,120 --> 00:30:06,650
اگر من تا به حال هیچ ستاره در اینجا، اشاره گر
absolutely-- آن یک گره است.

681
00:30:06,650 --> 00:30:08,650
این مثل یک هفته
تعریف یک متغیر،

682
00:30:08,650 --> 00:30:10,120
حتی اگر کلمه "گره" جدید است.

683
00:30:10,120 --> 00:30:13,860
>> اما به محض معرفی می کنیم
ستاره، آن را در حال حاضر یک اشاره گر به گره.

684
00:30:13,860 --> 00:30:17,960
و متاسفانه شما می توانید استفاده کنید
نماد نقطه برای یک اشاره گر.

685
00:30:17,960 --> 00:30:21,070
شما مجبور به استفاده از فلش
نماد، که، کاملا،

686
00:30:21,070 --> 00:30:23,470
اولین بار هر قطعه است
نحو به نظر می رسد بصری.

687
00:30:23,470 --> 00:30:25,245
این به معنای واقعی کلمه مثل یک پیکان به نظر می رسد.

688
00:30:25,245 --> 00:30:26,370
و به طوری که یک کار خوب است.

689
00:30:26,370 --> 00:30:28,995
و در اینجا به معنای واقعی کلمه
به نظر می رسد مثل یک فلش.

690
00:30:28,995 --> 00:30:31,870
بنابراین من فکر می کنم که la-- من نمی این
فکر می کنم من بیش از حد مرتکب here-- I

691
00:30:31,870 --> 00:30:34,120
فکر می کنم که آخرین قطعه جدید
نحو ما در حال رفتن برای دیدن.

692
00:30:34,120 --> 00:30:36,500
و خدا را شکر، آن را در واقع
کمی بیشتر بصری.

693
00:30:36,500 --> 00:30:40,090
>> در حال حاضر، برای کسانی از شما که
ممکن است راه های قدیمی را ترجیح می دهند،

694
00:30:40,090 --> 00:30:42,550
شما هنوز هم می تواند نماد نقطه استفاده کنید.

695
00:30:42,550 --> 00:30:45,380
اما به عنوان در روز دوشنبه
گفتگو، ما برای اولین بار

696
00:30:45,380 --> 00:30:50,530
نیاز به رفتن وجود دارد، رفتن به آن
آدرس، و سپس دسترسی به زمین میشه.

697
00:30:50,530 --> 00:30:51,897
بنابراین این نیز درست است.

698
00:30:51,897 --> 00:30:53,730
و رک و پوست کنده، این است که
کمی کوته نظرانه غالب تر است.

699
00:30:53,730 --> 00:30:56,530
شما به معنای واقعی کلمه می گفت، ارجاع
اشاره گر و رفتن وجود دارد.

700
00:30:56,530 --> 00:30:59,320
سپس با شتاب الله ضرغامی، زمینه به نام n است.

701
00:30:59,320 --> 00:31:01,370
اما رک و پوست کنده، هیچ کس می خواهد
به نوع و یا خواندن این.

702
00:31:01,370 --> 00:31:03,620
و به این ترتیب جهان اختراع
نماد پیکان، که

703
00:31:03,620 --> 00:31:06,980
معادل، یکسان است،
آن را فقط قند نحوی است.

704
00:31:06,980 --> 00:31:10,570
بنابراین یک راه فانتزی گفتن این
به نظر می رسد بهتر است، یا به نظر می رسد ساده تر.

705
00:31:10,570 --> 00:31:12,296
>> بنابراین در حال حاضر من قصد دارم به یک چیز دیگر.

706
00:31:12,296 --> 00:31:15,420
من قصد دارم برای گفتن "شکسته" یک بار من
یافت پس از آن من را نگه نمی به دنبال آن است.

707
00:31:15,420 --> 00:31:17,620
اما این جان کلام است
از تابع جستجو.

708
00:31:17,620 --> 00:31:21,710
اما این خیلی آسان تر، در
پایان، از طریق کد راه رفتن نیست.

709
00:31:21,710 --> 00:31:25,570
این در واقع اجرای رسمی
جستجو در کد توزیع امروز.

710
00:31:25,570 --> 00:31:30,530
من به جرات می گویند که درج است
به ویژه سرگرم کننده را از طریق راه رفتن

711
00:31:30,530 --> 00:31:33,180
بصری، و نه حذف، حتی
هر چند در پایان روز

712
00:31:33,180 --> 00:31:35,460
آنها جوش پایین به نسبتا
فن آوری هوشمند ساده است.

713
00:31:35,460 --> 00:31:36,330
>> بنابراین اجازه دهید این کار را انجام.

714
00:31:36,330 --> 00:31:39,250
اگر شما که به طنز من اینجا، من
را یک دسته از توپ های استرس.

715
00:31:39,250 --> 00:31:40,620
من یک دسته از اعداد به ارمغان آورد.

716
00:31:40,620 --> 00:31:46,562
و می تواند ما فقط چند داوطلب
برای نشان دادن 9، 17، 20، 22، 29، و 34؟

717
00:31:46,562 --> 00:31:48,270
بنابراین اساسا همه
که امروز در اینجا.

718
00:31:48,270 --> 00:31:50,170

719
00:31:50,170 --> 00:31:52,760
این یکی، دو، سه بود،
چهار، پنج، شش نفر.

720
00:31:52,760 --> 00:31:55,740
و از من خواسته شده به go-- مشاهده کنید، هیچ
یکی در پشت دست خود را بالا می برد.

721
00:31:55,740 --> 00:32:01,910
OK، یک، دو، سه، چهار،
five-- اجازه دهید من بار balance-- شش.

722
00:32:01,910 --> 00:32:03,051
OK، شما شش در آمده است.

723
00:32:03,051 --> 00:32:04,050
ما افراد دیگر نیاز دارند.

724
00:32:04,050 --> 00:32:05,460
ما توپ های استرس اضافی به ارمغان آورد.

725
00:32:05,460 --> 00:32:08,200
و اگر شما می توانید، برای
فقط یک لحظه، خط

726
00:32:08,200 --> 00:32:10,490
خود فقط
مثل این عکس بنویسید.

727
00:32:10,490 --> 00:32:15,200

728
00:32:15,200 --> 00:32:15,959
>> خوب.

729
00:32:15,959 --> 00:32:17,125
بیایید ببینید، چه نام شما چیه؟

730
00:32:17,125 --> 00:32:17,550
>> رسید اندرو.

731
00:32:17,550 --> 00:32:18,800
>> DAVID J. مالان: اندرو،
شما شماره 9 می باشد.

732
00:32:18,800 --> 00:32:19,540
از ملاقات شما خوشبختم.

733
00:32:19,540 --> 00:32:20,400
در اینجا شما بروید.

734
00:32:20,400 --> 00:32:21,593

735
00:32:21,593 --> 00:32:22,176
رسید جن.

736
00:32:22,176 --> 00:32:22,662
DAVID J. مالان: جن.

737
00:32:22,662 --> 00:32:23,162
دیوید.

738
00:32:23,162 --> 00:32:23,765
شماره 17.

739
00:32:23,765 --> 00:32:24,950

740
00:32:24,950 --> 00:32:25,450
بله؟

741
00:32:25,450 --> 00:32:26,400
>> رسید من جولیا هستم.

742
00:32:26,400 --> 00:32:26,980
>> DAVID J. مالان: جولیا، دیوید.

743
00:32:26,980 --> 00:32:27,545
شماره 20.

744
00:32:27,545 --> 00:32:28,507

745
00:32:28,507 --> 00:32:29,340
رسید مسیحی.

746
00:32:29,340 --> 00:32:30,715
DAVID J. مالان: مسیحی، دیوید.

747
00:32:30,715 --> 00:32:31,541
شماره 22.

748
00:32:31,541 --> 00:32:32,040
و؟

749
00:32:32,040 --> 00:32:32,649
>> رسید JP.

750
00:32:32,649 --> 00:32:33,440
DAVID J. مالان: JP.

751
00:32:33,440 --> 00:32:34,880
شماره 29.

752
00:32:34,880 --> 00:32:37,080
پس پیش بروید و in-- اوه اوه.

753
00:32:37,080 --> 00:32:38,486

754
00:32:38,486 --> 00:32:38,985
اوه اوه.

755
00:32:38,985 --> 00:32:39,650

756
00:32:39,650 --> 00:32:40,150
آماده به کار.

757
00:32:40,150 --> 00:32:41,360

758
00:32:41,360 --> 00:32:42,390
20.

759
00:32:42,390 --> 00:32:43,682
آیا کسی که یک مارکر؟

760
00:32:43,682 --> 00:32:44,890
رسید من Sharpie کردم.

761
00:32:44,890 --> 00:32:45,660
DAVID J. مالان: شما Sharpie کردم؟

762
00:32:45,660 --> 00:32:46,159
OK.

763
00:32:46,159 --> 00:32:47,577

764
00:32:47,577 --> 00:32:49,160
و یا کسی که یک تکه کاغذ؟

765
00:32:49,160 --> 00:32:51,562

766
00:32:51,562 --> 00:32:52,270
صرفه جویی در سخنرانی.

767
00:32:52,270 --> 00:32:53,810

768
00:32:53,810 --> 00:32:55,362
بیا.

769
00:32:55,362 --> 00:32:56,320
رسید ما آن را کردم.

770
00:32:56,320 --> 00:32:57,600
DAVID J. مالان: ما آن را کردم؟

771
00:32:57,600 --> 00:32:58,577
خوب، از شما سپاسگزارم.

772
00:32:58,577 --> 00:33:01,380

773
00:33:01,380 --> 00:33:02,520
در اینجا ما بروید.

774
00:33:02,520 --> 00:33:03,582
این از شما بود؟

775
00:33:03,582 --> 00:33:04,540
شما فقط روز را نجات داد.

776
00:33:04,540 --> 00:33:05,670

777
00:33:05,670 --> 00:33:07,220
بنابراین 29.

778
00:33:07,220 --> 00:33:10,510

779
00:33:10,510 --> 00:33:11,110
خوب.

780
00:33:11,110 --> 00:33:13,360

781
00:33:13,360 --> 00:33:14,890
من اشتباه 29، اما OK.

782
00:33:14,890 --> 00:33:15,720
برو جلو.

783
00:33:15,720 --> 00:33:18,114
خوب، من به شما می دهد
قلم خود را به عقب لحظه ای.

784
00:33:18,114 --> 00:33:19,280
بنابراین ما باید این دوستان در اینجا.

785
00:33:19,280 --> 00:33:20,330
بیایید یک دیگر داشته باشد.

786
00:33:20,330 --> 00:33:23,750
گیب، آیا شما می خواهید بازی
عنصر اول که اینجا هستید؟

787
00:33:23,750 --> 00:33:25,705
ما شما نیاز به نقطه
در این دوستان خوب است.

788
00:33:25,705 --> 00:33:26,930

789
00:33:26,930 --> 00:33:31,030
بنابراین 9، 17، 20، 22، مرتب کردن بر اساس
از 29، و پس از آن 34.

790
00:33:31,030 --> 00:33:32,160

791
00:33:32,160 --> 00:33:33,325
آیا ما به کسی از دست می دهند؟

792
00:33:33,325 --> 00:33:33,950
من یک 34.

793
00:33:33,950 --> 00:33:36,730
از کجا did-- OK، که می خواهد به 34؟

794
00:33:36,730 --> 00:33:37,605
OK، در آمد تا، 34.

795
00:33:37,605 --> 00:33:39,280

796
00:33:39,280 --> 00:33:41,220
خوب، این خواهد بود
به خوبی به ارزش اوج.

797
00:33:41,220 --> 00:33:41,550
نام شما چیست؟

798
00:33:41,550 --> 00:33:42,040
>> رسید پیتر.

799
00:33:42,040 --> 00:33:43,456
>> DAVID J. مالان: پیتر، در آمده است.

800
00:33:43,456 --> 00:33:46,810
همه حق است، بنابراین در اینجا
تمام دسته از گره.

801
00:33:46,810 --> 00:33:49,060
هر یک از شما بچه ها را نشان می
یکی از این مستطیل.

802
00:33:49,060 --> 00:33:51,930
و گیب، کمی عجیب و غریب
انسان از، نشان دهنده اول است.

803
00:33:51,930 --> 00:33:54,850
پس اشاره گر خود را کمی کوچکتر
بر روی صفحه نمایش از هر کس دیگری.

804
00:33:54,850 --> 00:33:58,120
و در این مورد، هر یک از شما در سمت چپ
دست در حال رفتن به یکی از دو نقطه پایین،

805
00:33:58,120 --> 00:34:01,085
در نتیجه به نمایندگی تهی، بنابراین
از فقدان یک اشاره گر،

806
00:34:01,085 --> 00:34:03,210
و یا آن را به اشاره می شود
در یک گره در کنار شما.

807
00:34:03,210 --> 00:34:05,440
>> بنابراین در حال حاضر اگر شما زر و زیور اراستن
خودتان مانند تصویر

808
00:34:05,440 --> 00:34:07,585
در اینجا، به جلو و نقطه
در هر یک از دیگر، با گیب

809
00:34:07,585 --> 00:34:11,030
در اشاره به ویژه در
تعداد 9 به نمایندگی از لیست.

810
00:34:11,030 --> 00:34:14,050
OK، و تعداد 34، دست چپ خود را
فقط باید اشاره شود در طبقه.

811
00:34:14,050 --> 00:34:15,750
>> OK، بنابراین این لیست پیوندی می باشد.

812
00:34:15,750 --> 00:34:17,580
بنابراین این سناریو در سوال است.

813
00:34:17,580 --> 00:34:20,210
و در واقع، این نماینده است
از یک کلاس از مشکلات

814
00:34:20,210 --> 00:34:21,929
که شما ممکن است سعی کنید برای حل با کد.

815
00:34:21,929 --> 00:34:25,020
شما می خواهید برای قرار دادن در نهایت
یک عنصر جدید به لیست.

816
00:34:25,020 --> 00:34:27,494
در این مورد، ما قصد داریم به
سعی کنید با قرار دادن تعداد 55.

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
اما برای رفتن به وجود
موارد مختلف در نظر بگیرند.

819
00:34:30,860 --> 00:34:34,409
و در واقع، این است که برای رفتن به یک
از تصویر بزرگ takeaways در اینجا، است،

820
00:34:34,409 --> 00:34:35,659
موارد مختلف چه هستند.

821
00:34:35,659 --> 00:34:39,120
چه اگر شرایط مختلف و یا
شاخه که برنامه شما ممکن است؟

822
00:34:39,120 --> 00:34:42,024
>> خب، تعداد شما در تلاش برای
درج، که ما اکنون می دانیم به 55،

823
00:34:42,024 --> 00:34:44,650
اما اگر شما نمی دانید
در پیش، من اعتقاد داشتن

824
00:34:44,650 --> 00:34:47,840
سقوط به حداقل سه
شرایط ممکن است.

825
00:34:47,840 --> 00:34:49,717
کجا ممکن است یک عنصر جدید است؟

826
00:34:49,717 --> 00:34:51,050
رسید و در پایان و یا متوسط ​​است.

827
00:34:51,050 --> 00:34:54,150
DAVID J. مالان: در پایان، در
در عمق و یا در آغاز.

828
00:34:54,150 --> 00:34:56,650
پس من ادعا می کنند حداقل وجود دارد
سه مشکل ما نیاز به حل کند.

829
00:34:56,650 --> 00:34:58,691
اجازه دهید را انتخاب کنید چه چیزی شاید
مسلما از ساده ترین

830
00:34:58,691 --> 00:35:01,090
یک، که در آن عنصر جدید
تعلق در آغاز.

831
00:35:01,090 --> 00:35:04,040
من می خواهم به کد کاملا
مانند جستجو، که من فقط نوشتم.

832
00:35:04,040 --> 00:35:07,670
و من قصد دارم به PTR، که
من در اینجا با انگشت من را نشان،

833
00:35:07,670 --> 00:35:08,370
به طور معمول.

834
00:35:08,370 --> 00:35:12,430
>> و به یاد داشته باشید، آنچه که ارزش
آیا ما PTR به مقداردهی اولیه؟

835
00:35:12,430 --> 00:35:15,300
بنابراین ما آن را مقدار دهی اولیه تهی در ابتدا.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
اما پس از آن چه که ما یک بار کار می کنیم
در داخل تابع جستجو ما بودند؟

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
ما آن را برابر با مجموعه اول،
که به این معنا نیست انجام این کار.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
اگر من مجموعه PTR برابر برای اولین بار، چه
باید دست من واقعا اشاره می شود؟

842
00:35:30,570 --> 00:35:31,070
راست.

843
00:35:31,070 --> 00:35:33,290
بنابراین اگر گیب و من در حال رفتن
به ارزش برابر در اینجا،

844
00:35:33,290 --> 00:35:34,760
ما به هر دو نقطه نیاز در شماره 9.

845
00:35:34,760 --> 00:35:36,420
>> بنابراین این آغاز داستان ما بود.

846
00:35:36,420 --> 00:35:38,700
و در حال حاضر این فقط ساده،
حتی اگر از دستور جدید است.

847
00:35:38,700 --> 00:35:40,580
از نظر مفهومی این فقط جستجوی خطی است.

848
00:35:40,580 --> 00:35:42,750
آیا 55 برابر با 9؟

849
00:35:42,750 --> 00:35:45,559
یا نه، اجازه دهید کمتر از 9 می گویند.

850
00:35:45,559 --> 00:35:47,600
از آنجا که من در تلاش برای
کشف کردن که در آن برای قرار دادن 55.

851
00:35:47,600 --> 00:35:51,270
کمتر از 9، کمتر از 17، کمتر
از 20، کمتر از 22، کمتر از 29،

852
00:35:51,270 --> 00:35:52,510
کمتر از 34، نه.

853
00:35:52,510 --> 00:35:55,080
بنابراین در حال حاضر ما در مورد هستید
یکی از حداقل سه.

854
00:35:55,080 --> 00:35:59,910
>> اگر من می خواهم برای وارد کردن 55 در اینجا، چه
خط کد نیاز به عمل کند؟

855
00:35:59,910 --> 00:36:01,890
چگونه این تصویر از
انسان نیاز به تغییر؟

856
00:36:01,890 --> 00:36:03,181
با دست چپ من چه کار کنم؟

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
این باید تهی است در ابتدا،
چرا که من در انتهای فهرست هستم.

859
00:36:07,360 --> 00:36:09,318
و چه اتفاقی می افتد
در اینجا با پیتر، بود؟

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
او به وضوح رفتن به نقطه را به من.

862
00:36:12,430 --> 00:36:15,580
پس من ادعا می کنند حداقل دو خط وجود دارد
کد را در کد نمونه از امروز

863
00:36:15,580 --> 00:36:18,570
که رفتن به پیاده سازی این
سناریو از اضافه کردن 55 در دم.

864
00:36:18,570 --> 00:36:20,950
و می تواند من کسی هاپ
و فقط نشان دهنده 55؟

865
00:36:20,950 --> 00:36:22,200
خوب، شما 55 جدید است.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> بنابراین در حال حاضر اگر بعد
سناریو می آید همراه،

868
00:36:27,054 --> 00:36:29,720
و ما می خواهیم برای وارد کردن در
شروع و یا سر به این لیست؟

869
00:36:29,720 --> 00:36:31,100
و چه نام شما، شماره 55 است؟

870
00:36:31,100 --> 00:36:31,420
>> رسید جک.

871
00:36:31,420 --> 00:36:32,295
>> DAVID J. مالان: جک؟

872
00:36:32,295 --> 00:36:33,585
OK، ملاقات با شما خوشبختم.

873
00:36:33,585 --> 00:36:34,210
روی خوش آمدید.

874
00:36:34,210 --> 00:36:36,640
بنابراین در حال حاضر ما در حال رفتن به
وارد کردن، می گویند، تعداد 5.

875
00:36:36,640 --> 00:36:39,840
در اینجا مورد دوم است
سه ما با قبل از آمد.

876
00:36:39,840 --> 00:36:43,050
بنابراین اگر 5 متعلق در آغاز،
بیایید ببینید که چگونه پیدا کنیم که از.

877
00:36:43,050 --> 00:36:46,310
I مقداردهی اولیه PTR من
اشاره گر به تعداد 9 دوباره.

878
00:36:46,310 --> 00:36:49,140
و من متوجه شدم، آه، 5 است کمتر از 9.

879
00:36:49,140 --> 00:36:50,880
پس این تصویر را برای ما حل کنند.

880
00:36:50,880 --> 00:36:54,820
چه کسانی به دست، در گیب و یا دیوید
or-- چه نام تعداد 9 چیست؟

881
00:36:54,820 --> 00:36:55,740
>> رسید جن.

882
00:36:55,740 --> 00:36:58,406
>> DAVID J. مالان: hands-- جن را
که از دست ما نیاز به تغییر؟

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK، بنابراین گیب اشاره به آنچه که در حال حاضر؟

885
00:37:00,970 --> 00:37:01,640
در من.

886
00:37:01,640 --> 00:37:02,750
من گره جدید است.

887
00:37:02,750 --> 00:37:04,870
بنابراین من فقط نوع حرکت
در اینجا به آن بصری را ببینید.

888
00:37:04,870 --> 00:37:06,435
و در عین حال چه نقطه است که من؟

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
هنوز هم جایی که من اشاره می کنم.

891
00:37:09,020 --> 00:37:10,000
به طوری که آن را.

892
00:37:10,000 --> 00:37:13,717
بنابراین واقعا یک خط از رفع کد
این موضوع خاص، به نظر می رسد.

893
00:37:13,717 --> 00:37:14,800
همه حق است، به طوری که خوب است.

894
00:37:14,800 --> 00:37:17,580
و کسی که می تواند یک حفره یا سوراخ به مدت 5؟

895
00:37:17,580 --> 00:37:18,080
بیا تا.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
ما به شما زمان بعدی دریافت کنید.

898
00:37:21,320 --> 00:37:24,280
>> همه حق است، بنابراین now-- و
به عنوان یک به کنار، نام

899
00:37:24,280 --> 00:37:28,510
من به اشاره صریح و روشن از درست نیست
در حال حاضر، اشاره گر pred، اشاره گر سلف

900
00:37:28,510 --> 00:37:31,260
و اشاره گر جدید، که
فقط نام داده شده

901
00:37:31,260 --> 00:37:35,280
در نمونه کد به اشاره گر یا
دست من در این نوع از اشاره در اطراف.

902
00:37:35,280 --> 00:37:36,060
نام شما چیست؟

903
00:37:36,060 --> 00:37:36,700
>> رسید کریستین.

904
00:37:36,700 --> 00:37:37,100
>> DAVID J. مالان: کریستین.

905
00:37:37,100 --> 00:37:38,090
روی خوش آمدید.

906
00:37:38,090 --> 00:37:42,180
همه حق است، بنابراین اجازه دهید در حال حاضر در نظر
یک سناریوی کمی بیشتر آزار دهنده،

907
00:37:42,180 --> 00:37:46,350
به موجب آن من می خواهم برای وارد کردن
چیزی شبیه به 26 را به این.

908
00:37:46,350 --> 00:37:47,090
20؟

909
00:37:47,090 --> 00:37:47,590
چه؟

910
00:37:47,590 --> 00:37:50,510
این are-- چیز خوبی که داریم این قلم.

911
00:37:50,510 --> 00:37:51,955
همه حق است، 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
اگر کسی می تواند قطعه دیگری از دریافت
مقاله آماده، فقط در case-- همه حق.

914
00:37:57,570 --> 00:37:58,370
اوه، جالب است.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
خب این یک مثال است
از یک اشکال سخنرانی.

917
00:38:02,390 --> 00:38:03,894
OK چه خوب دوباره نام خود را؟

918
00:38:03,894 --> 00:38:04,560
رسید جولیا.

919
00:38:04,560 --> 00:38:07,559
DAVID J. مالان: جولیا، می تواند به شما پاپ
و وانمود کنید که هرگز آنجا نبودی؟

920
00:38:07,559 --> 00:38:09,040
OK، این هرگز اتفاق افتاده است.

921
00:38:09,040 --> 00:38:09,680
با تشکر از شما.

922
00:38:09,680 --> 00:38:12,180
بنابراین فرض کنید ما می خواهیم وارد
جولیا به این لیست در ارتباط است.

923
00:38:12,180 --> 00:38:13,780
او تعداد 20 است.

924
00:38:13,780 --> 00:38:15,530
و البته او
رفتن به تعلق در

925
00:38:15,530 --> 00:38:17,521
begin-- را در هر چیزی اشاره نشده است.

926
00:38:17,521 --> 00:38:20,020
پس دست خود را نوع می تواند
پایین صفر و یا برخی از ارزش زباله.

927
00:38:20,020 --> 00:38:21,210
اجازه دهید داستان سریع بگویید.

928
00:38:21,210 --> 00:38:22,980
من اشاره در شماره 5 این زمان.

929
00:38:22,980 --> 00:38:23,880
سپس من تیک بزنید 9.

930
00:38:23,880 --> 00:38:25,130
سپس من تیک بزنید 17.

931
00:38:25,130 --> 00:38:26,247
سپس من تیک بزنید 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
و من می دانم، آه، جولیا
باید قبل از 22 است.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
پس چه اتفاقی باید بیفتد؟

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
چه کسانی به دست نیاز به تغییر؟

938
00:38:36,910 --> 00:38:38,360
در جولیا، معدن، or--
چه نام خود را دوباره چیست؟

939
00:38:38,360 --> 00:38:39,230
>> رسید مسیحی.

940
00:38:39,230 --> 00:38:40,060
>> DAVID J. مالان: مسیحی یا؟

941
00:38:40,060 --> 00:38:40,560
>> رسید اندی.

942
00:38:40,560 --> 00:38:40,905
>> DAVID J. مالان: اندی.

943
00:38:40,905 --> 00:38:41,654
مسیحی یا اندی؟

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
اندی نیاز به نقطه در؟

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
جولیا.

948
00:38:47,341 --> 00:38:47,840
خوب.

949
00:38:47,840 --> 00:38:48,960
بنابراین اندی، آیا شما می خواهید به نقطه در جولیا؟

950
00:38:48,960 --> 00:38:50,120
اما یک دقیقه صبر کنید.

951
00:38:50,120 --> 00:38:53,260
در داستان تا کنون،
I مرتب کردن بر اساس یکی هستم

952
00:38:53,260 --> 00:38:56,800
مسئول، به این معنا که
اشاره گر چیزی که است

953
00:38:56,800 --> 00:38:57,850
حرکت را از طریق لیست.

954
00:38:57,850 --> 00:39:00,800
ما ممکن است یک نام برای اندی است، اما
هیچ متغیر به نام اندی است.

955
00:39:00,800 --> 00:39:04,320
تنها متغیر های دیگر ما است
برای اولین بار، که توسط گیب، بیان کرد.

956
00:39:04,320 --> 00:39:07,690
>> پس این است که در واقع به همین دلیل در نتیجه
کنون ما در این مورد نیاز نیست ام.

957
00:39:07,690 --> 00:39:10,846
اما در حال حاضر بر روی صفحه نمایش وجود دارد
دوباره ذکر است از اشاره گر pred.

958
00:39:10,846 --> 00:39:11,970
بنابراین، اجازه دهید صریح و روشن تر باشد.

959
00:39:11,970 --> 00:39:14,820
اگر این اشاره گر است، من تا به حال بهتر
یک کمی آگاهی بیشتر

960
00:39:14,820 --> 00:39:15,950
در مورد تکرار من.

961
00:39:15,950 --> 00:39:19,580
اگر برای شما مهم نیست من رفتن را از طریق اینجا
دوباره، با اشاره در اینجا، اشاره کنید.

962
00:39:19,580 --> 00:39:22,500
اما اجازه بدهید من یک اشاره گر pred،
اشاره گر سلف، که

963
00:39:22,500 --> 00:39:24,740
نوع اشاره به
عنصر من فقط در بود.

964
00:39:24,740 --> 00:39:27,330
بنابراین، هنگامی که من در اینجا، در حال حاضر
به روز رسانی دست چپ من.

965
00:39:27,330 --> 00:39:29,370
زمانی که من در اینجا به روز رسانی دست من سمت چپ.

966
00:39:29,370 --> 00:39:33,090
و در حال حاضر من نه تنها یک اشاره گر به
این عنصر که بعد از جولیا می رود،

967
00:39:33,090 --> 00:39:36,300
من هنوز یک اشاره گر به
اندی، عنصر قبل از.

968
00:39:36,300 --> 00:39:39,430
بنابراین شما دسترسی داشته باشند، در اصل،
پودرهای سوخاری، اگر شما خواهد شد،

969
00:39:39,430 --> 00:39:41,500
به همه اشاره گر لازم.

970
00:39:41,500 --> 00:39:43,710
>> پس اگر من اشاره در
کنسرت اندی و من هم با اشاره

971
00:39:43,710 --> 00:39:47,105
در مسیحیت، که دست
اکنون باید در جای دیگر اشاره می شود؟

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
بنابراین اندی هم اکنون می توانید در جولیا نقطه.

974
00:39:51,960 --> 00:39:54,460
جولیا هم اکنون می توانید در مسیحیت اشاره می کنند.

975
00:39:54,460 --> 00:39:56,950
از آنجا که او می تواند کپی من
اشاره گر دست راست است.

976
00:39:56,950 --> 00:40:00,044
و این به طور موثر شما قرار می دهد
بازگشت به این مکان اینجا.

977
00:40:00,044 --> 00:40:02,460
بنابراین در کوتاه مدت، حتی اگر این
ما در نظر گرفتن نوع برای همیشه

978
00:40:02,460 --> 00:40:04,510
در واقع به روز رسانی
لیست پیوندی، متوجه

979
00:40:04,510 --> 00:40:06,580
که عملیات
نسبتا ساده است.

980
00:40:06,580 --> 00:40:10,030
این از یکی، دو، سه
خط کد در نهایت.

981
00:40:10,030 --> 00:40:12,780
اما پیچیده در اطراف آن
خط کد احتمالا

982
00:40:12,780 --> 00:40:16,350
یک بیت از منطق است که به طور موثر
سوال، که در آن ما می پرسد؟

983
00:40:16,350 --> 00:40:18,970
آیا ما در آغاز،
در عمق و یا پایان؟

984
00:40:18,970 --> 00:40:21,890
>> در حال حاضر، قطعا وجود دارد برخی از دیگر
عملیات ما ممکن است پیاده سازی.

985
00:40:21,890 --> 00:40:24,880
و این تصاویر در اینجا فقط به تصویر می کشد
آنچه که ما فقط با انسان ها انجام داد.

986
00:40:24,880 --> 00:40:26,080
چه در مورد حذف؟

987
00:40:26,080 --> 00:40:30,650
اگر من می خواهم، به عنوان مثال،
حذف تعداد 34 یا 55،

988
00:40:30,650 --> 00:40:34,680
من ممکن است همین نوع از کد داشته باشد،
اما من قصد دارم به نیاز به یک یا دو مرحله دارد.

989
00:40:34,680 --> 00:40:36,110
از آنجا که چه چیزی جدید؟

990
00:40:36,110 --> 00:40:40,460
اگر من کسی را حذف و در پایان،
مانند تعداد 55 و سپس 34،

991
00:40:40,460 --> 00:40:42,995
آنچه همچنین دارای تغییر که من انجام این کار؟

992
00:40:42,995 --> 00:40:44,870
من به evict-- نمی
چه نام خود را دوباره چیست؟

993
00:40:44,870 --> 00:40:45,380
>> رسید جک.

994
00:40:45,380 --> 00:40:46,255
>> DAVID J. مالان: جک.

995
00:40:46,255 --> 00:40:49,770
من نه تنها به evict-- جک آزاد،
تا به معنای واقعی کلمه با تلفن رایگان جک، و یا حداقل

996
00:40:49,770 --> 00:40:53,530
اشاره گر وجود دارد بیش از حد، اما در حال حاضر
آنچه باید با پیتر عوض کنم؟

997
00:40:53,530 --> 00:40:55,510
دست او بهتر شروع به اشاره کردن.

998
00:40:55,510 --> 00:40:59,300
از آنجا که در اسرع وقت من آزاد در تماس
جک، اگر پیتر هنوز در جک اشاره

999
00:40:59,300 --> 00:41:02,530
و به همین دلیل من حفظ تراورس
لیست و دسترسی به این اشاره گر،

1000
00:41:02,530 --> 00:41:05,650
که زمانی که تقسیم بندی دوست قدیمی ما است
گسل ممکن است در واقع پا زدن در.

1001
00:41:05,650 --> 00:41:07,860
از آنجا که ما داده ایم
حافظه به جک.

1002
00:41:07,860 --> 00:41:10,760
>> شما می توانید اقامت وجود دارد
ناشیانه برای فقط یک لحظه.

1003
00:41:10,760 --> 00:41:13,410
از آنجا که ما فقط یک زن و شوهر
عملیات نهایی در نظر بگیرند.

1004
00:41:13,410 --> 00:41:15,600
از بین بردن سر از لیست،
یا beginning-- و این یکی را

1005
00:41:15,600 --> 00:41:16,349
کمی آزار دهنده است.

1006
00:41:16,349 --> 00:41:19,640
از آنجا که ما می دانیم که گیب
است نوع ویژه ای در این برنامه است.

1007
00:41:19,640 --> 00:41:21,440
از آنجا که در واقع، او اشاره گر خود را.

1008
00:41:21,440 --> 00:41:24,860
او نه تنها که در اشاره،
به عنوان تقریبا هر کس دیگری است.

1009
00:41:24,860 --> 00:41:28,112
>> بنابراین، هنگامی که سر از لیست است
حذف، که دست نیاز به تغییر در حال حاضر؟

1010
00:41:28,112 --> 00:41:29,070
نام و نام خانوادگی خود را دوباره چه خبر؟

1011
00:41:29,070 --> 00:41:29,450
>> رسید کریستین.

1012
00:41:29,450 --> 00:41:31,408
>> DAVID J. مالان: I افتضاح هستم
در نام، ظاهرا.

1013
00:41:31,408 --> 00:41:34,011
بنابراین کریستین و گیب،
که دست نیاز به تغییر

1014
00:41:34,011 --> 00:41:36,510
زمانی که ما سعی می کنیم به حذف کریستین،
شماره 5، از تصویر؟

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
OK، بنابراین اجازه دهید کار را انجام گیب.

1017
00:41:38,820 --> 00:41:40,950
گیب رفتن به نقطه،
احتمالا، در شماره 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
اما بعد چه باید اتفاق می افتد؟

1020
00:41:44,642 --> 00:41:46,600
رسید کریستین باید
تهی است [نامفهوم].

1021
00:41:46,600 --> 00:41:50,244
DAVID J. مالان: OK، ما باید احتمالا
make-- من شنیده ام "تهی" جایی.

1022
00:41:50,244 --> 00:41:51,410
رسید نول و آزاد خود را.

1023
00:41:51,410 --> 00:41:51,855
DAVID J. مالان: تهی چه؟

1024
00:41:51,855 --> 00:41:53,074
رسید نول و آزاد خود را.

1025
00:41:53,074 --> 00:41:54,490
DAVID J. مالان: صفر و آزاد خود را.

1026
00:41:54,490 --> 00:41:55,422
بنابراین این بسیار آسان است.

1027
00:41:55,422 --> 00:41:58,380
و این عالی است که شما هم اکنون به نوعی هستیم
ایستاده وجود دارد، نه متعلق.

1028
00:41:58,380 --> 00:42:00,430
از آنجا که شما بوده ام
جدا از لیست.

1029
00:42:00,430 --> 00:42:02,820
شما به طور موثر بوده است
یتیم را از لیست.

1030
00:42:02,820 --> 00:42:07,770
و به این ترتیب ما بهتر بود تماس رایگان در حال حاضر در
کریستین را که حافظه را به عقب.

1031
00:42:07,770 --> 00:42:10,240
در غیر این صورت هر زمان که ما
حذف یک گره از لیست

1032
00:42:10,240 --> 00:42:14,230
ما ممکن است به این ترتیب فهرست
کوتاه تر، اما در واقع کاهش نیست

1033
00:42:14,230 --> 00:42:15,096
اندازه در حافظه است.

1034
00:42:15,096 --> 00:42:17,720
و به این ترتیب اگر ما به حفظ اضافه و
اضافه کردن، اضافه کردن چیزهایی به لیست،

1035
00:42:17,720 --> 00:42:19,280
کامپیوتر من ممکن است آهسته تر
و کندتر و آهسته تر،

1036
00:42:19,280 --> 00:42:21,740
چرا که من در حال اجرا هستم از
حافظه، حتی اگر من در واقع نه

1037
00:42:21,740 --> 00:42:25,580
با استفاده از بایت کریستین را
حافظه دیگر.

1038
00:42:25,580 --> 00:42:28,500
>> بنابراین در پایان دیگر وجود دارد
سناریو، حذف course--

1039
00:42:28,500 --> 00:42:30,640
در وسط، حذف
در پایان، ما به عنوان شاهد.

1040
00:42:30,640 --> 00:42:32,348
اما جالب تر
چالش در حال حاضر است

1041
00:42:32,348 --> 00:42:34,770
رفتن به در نظر گرفتن دقیقا
چه زمان در حال اجرا است.

1042
00:42:34,770 --> 00:42:36,640
بنابراین نه تنها می تواند شما را نگه دارید شما
تکه های کاغذ، اگر، گیب،

1043
00:42:36,640 --> 00:42:38,640
شما نمی خواهد ذهن دادن
همه رو با استرس.

1044
00:42:38,640 --> 00:42:42,100
از شما بسیار سپاسگزارم برای لیست پیوندی ما
از داوطلبان در اینجا، اگر شما می توانید.

1045
00:42:42,100 --> 00:42:45,320
>> [تشویق حضار]

1046
00:42:45,320 --> 00:42:46,700
>> DAVID J. مالان: خوب.

1047
00:42:46,700 --> 00:42:51,110
بنابراین زن و شوهر از تحلیلی
سوالات و سپس، اگر من می تواند.

1048
00:42:51,110 --> 00:42:59,670
ما این نماد دیده می شود قبل از،
O بزرگ و امگا، مرزهای بالایی

1049
00:42:59,670 --> 00:43:02,520
و مرزهای پایین تر در
زمان برخی از الگوریتم در حال اجرا.

1050
00:43:02,520 --> 00:43:04,950
بنابراین اجازه دهید فقط در نظر
یک زن و شوهر از سوالات.

1051
00:43:04,950 --> 00:43:07,090
>> یک، و ما آن را گفت:
قبل، چه در حال حرکت است

1052
00:43:07,090 --> 00:43:10,647
زمان جستجو برای
لیست در نظر O بزرگ؟

1053
00:43:10,647 --> 00:43:13,480
چه یک حد بالا در حال اجرا
زمان جستجو یک لیست پیوندی

1054
00:43:13,480 --> 00:43:16,340
که توسط داوطلبان ما اجرا که اینجا هستید؟

1055
00:43:16,340 --> 00:43:17,820
این O بزرگ از n، خطی است.

1056
00:43:17,820 --> 00:43:20,630
از آنجا که در بدترین حالت،
این عنصر، مانند 55،

1057
00:43:20,630 --> 00:43:23,830
ما ممکن است به دنبال ممکن است که در آن
جک تمام راه در پایان بود.

1058
00:43:23,830 --> 00:43:28,250
و متاسفانه، بر خلاف یک آرایه
ما نمی توانیم دریافت فانتزی این زمان.

1059
00:43:28,250 --> 00:43:31,820
حتی اگر همه انسانها ما بودند
طبقه بندی شده اند از عناصر کوچک، 5،

1060
00:43:31,820 --> 00:43:35,900
تمام راه را تا به این عنصر بزرگتر،
55، که معمولا چیز خوبی است.

1061
00:43:35,900 --> 00:43:38,815
اما این به چه فرض
دیگر به ما اجازه انجام دهید؟

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
رسید [نامفهوم]

1064
00:43:40,650 --> 00:43:40,920
DAVID J. مالان: بگو دوباره؟

1065
00:43:40,920 --> 00:43:41,800
رسید دسترسی تصادفی.

1066
00:43:41,800 --> 00:43:43,049
DAVID J. مالان: دسترسی تصادفی.

1067
00:43:43,049 --> 00:43:46,330
و به نوبه خود این بدان معناست که ما می توانیم بدون
دیگر استفاده از صفر ضعیف، شهود،

1068
00:43:46,330 --> 00:43:49,365
و گویایی از با استفاده از باینری
جستجو و تقسیم و تسخیر.

1069
00:43:49,365 --> 00:43:51,240
از آنجا که حتی اگر ما
انسان به وضوح می تواند

1070
00:43:51,240 --> 00:43:54,610
ببینید که اندی و یا مسیحی بودند
تقریبا در وسط این فهرست،

1071
00:43:54,610 --> 00:43:57,670
ما تنها می دانیم که به عنوان یک
کامپیوتر های دستکاری لیست

1072
00:43:57,670 --> 00:43:59,029
از همان ابتدا.

1073
00:43:59,029 --> 00:44:00,570
بنابراین ما تا که دسترسی تصادفی داده ام.

1074
00:44:00,570 --> 00:44:04,380
>> O پس بزرگ از n در حال حاضر بالا است
محدود در زمان جستجو است.

1075
00:44:04,380 --> 00:44:07,920
چه در مورد امگا از جستجوی ما؟

1076
00:44:07,920 --> 00:44:11,535
چه پایین تر حد در جستجو است
برای برخی از تعداد در این لیست؟

1077
00:44:11,535 --> 00:44:12,410
رسید [نامفهوم]

1078
00:44:12,410 --> 00:44:13,040
DAVID J. مالان: بگو دوباره؟

1079
00:44:13,040 --> 00:44:13,420
رسید یکی.

1080
00:44:13,420 --> 00:44:13,800
DAVID J. مالان: یک.

1081
00:44:13,800 --> 00:44:14,760
زمان ثابت است.

1082
00:44:14,760 --> 00:44:17,020
در بهترین حالت، کریستین است
در واقع در ابتدای فهرست.

1083
00:44:17,020 --> 00:44:19,020
و ما به دنبال
شماره 5، پس ما او را در بر داشت.

1084
00:44:19,020 --> 00:44:19,787
بنابراین هیچ معامله بزرگ است.

1085
00:44:19,787 --> 00:44:22,370
اما او کردم به در می شود
شروع از لیست در این مورد.

1086
00:44:22,370 --> 00:44:23,745
چه در مورد چیزی شبیه حذف شود؟

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
چه می شود اگر شما می خواهید یک عنصر را حذف کنید؟

1089
00:44:26,300 --> 00:44:29,200
چه حد بالا و حد پایین تر
در حذف چیزی را از یک مرتبط

1090
00:44:29,200 --> 00:44:29,699
لیست؟

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
رسید [نامفهوم]

1093
00:44:36,070 --> 00:44:36,420
DAVID J. مالان: بگو دوباره؟

1094
00:44:36,420 --> 00:44:37,067
رسید نفر.

1095
00:44:37,067 --> 00:44:38,900
DAVID J. مالان: نفر است
در واقع حد بالای.

1096
00:44:38,900 --> 00:44:41,700
از آنجا که در بدترین حالت ما سعی می کنیم
برای حذف جک، که ما فقط.

1097
00:44:41,700 --> 00:44:43,050
او تمام راه را در پایان است.

1098
00:44:43,050 --> 00:44:45,419
ما طول می کشد برای همیشه لطفا برای، و یا
نفر گام برای رسیدن به او پیدا کنید.

1099
00:44:45,419 --> 00:44:46,460
به طوری که یک حد بالا.

1100
00:44:46,460 --> 00:44:47,430
که خطی است، مطمئن شوید.

1101
00:44:47,430 --> 00:44:50,970
و بهترین حالت زمان در حال اجرا، و یا
از مرزهای پایین تر در بهترین حالت

1102
00:44:50,970 --> 00:44:51,975
خواهد بود زمان ثابت است.

1103
00:44:51,975 --> 00:44:54,600
از آنجا که شاید ما سعی می کنیم را حذف کنید
کریستین، و ما فقط خوش شانس

1104
00:44:54,600 --> 00:44:55,558
او در آغاز راه است.

1105
00:44:55,558 --> 00:44:56,350
حالا یک دقیقه صبر کنید.

1106
00:44:56,350 --> 00:44:59,370
گیب نیز در آغاز بود،
و ما نیز تا به حال به روز رسانی گیب.

1107
00:44:59,370 --> 00:45:01,150
به طوری که فقط یک قدم نیست.

1108
00:45:01,150 --> 00:45:04,210
پس از آن در واقع ثابت
زمان، در بهترین حالت،

1109
00:45:04,210 --> 00:45:06,345
برای حذف کوچکترین عنصر؟

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
این است، اگر چه آن ممکن است دو،
سه، و یا حتی 100 خط کد،

1112
00:45:10,960 --> 00:45:14,000
اگر آن را به همان تعداد از این
خطوط، در برخی از حلقه،

1113
00:45:14,000 --> 00:45:16,577
و مستقل از اندازه
از لیست، کاملا.

1114
00:45:16,577 --> 00:45:18,660
حذف عنصر در
ابتدای فهرست،

1115
00:45:18,660 --> 00:45:21,940
حتی اگر ما را برای مقابله با
گیب، هنوز زمان ثابت است.

1116
00:45:21,940 --> 00:45:24,220
>> بنابراین این به نظر می رسد مثل یک
گام عظیم به عقب.

1117
00:45:24,220 --> 00:45:27,000
و چه اتلاف وقت
اگر، در هفته اول و هفته

1118
00:45:27,000 --> 00:45:30,250
صفر ما تا به حال نه تنها
کد شبه اما کد واقعی

1119
00:45:30,250 --> 00:45:35,780
برای پیاده سازی چیزی است که ورود به سیستم را
پایگاه نفر، و یا به سیستم وارد شوید، و نه، از n، پایه 2،

1120
00:45:35,780 --> 00:45:37,150
از نظر زمان در حال اجرا است.

1121
00:45:37,150 --> 00:45:40,710
پس چرا هک می ما می خواهیم برای شروع
با استفاده از چیزی شبیه به یک لیست پیوندی؟

1122
00:45:40,710 --> 00:45:41,517
آره.

1123
00:45:41,517 --> 00:45:44,022
>> رسید بنابراین شما می توانید اضافه کنید
عناصر به آرایه.

1124
00:45:44,022 --> 00:45:46,230
DAVID J. مالان: بنابراین شما می توانید
عناصر به آرایه اضافه کنید.

1125
00:45:46,230 --> 00:45:47,550
و این بیش از حد موضوعی است.

1126
00:45:47,550 --> 00:45:49,740
و ما همچنان برای دیدن
این، این تجارت کردن، خیلی

1127
00:45:49,740 --> 00:45:51,573
مثل ما دیده ایم
تجارت کردن با مرتب کردن بر اساس ادغام.

1128
00:45:51,573 --> 00:45:54,606
ما واقعا می تواند سرعت بخشیدن به
جستجو و مرتب سازی، و نه،

1129
00:45:54,606 --> 00:45:57,480
اگر ما یک فضای کمی بیشتر خرج و
یک تکه اضافی از حافظه

1130
00:45:57,480 --> 00:45:58,760
یا یک آرایه برای مرتب سازی ادغام.

1131
00:45:58,760 --> 00:46:01,270
اما ما صرف
فضا، اما ما در زمان صرفه جویی.

1132
00:46:01,270 --> 00:46:04,820
در این مورد، ما
از دست دادن زمان، اما ما

1133
00:46:04,820 --> 00:46:08,170
به دست آوردن انعطاف پذیری،
پویایی اگر شما خواهد شد،

1134
00:46:08,170 --> 00:46:10,280
که مسلما یکی از ویژگی های مثبت است.

1135
00:46:10,280 --> 00:46:11,520
>> ما همچنین در حال گذراندن فضا.

1136
00:46:11,520 --> 00:46:13,710
به چه معنا است مرتبط
لیست گران تر

1137
00:46:13,710 --> 00:46:15,700
از نظر فضا از یک آرایه؟

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
فضای اضافی از کجا می آید؟

1140
00:46:19,920 --> 00:46:20,460
آره؟

1141
00:46:20,460 --> 00:46:21,800
>> رسید [نامفهوم] اشاره گر.

1142
00:46:21,800 --> 00:46:23,310
>> DAVID J. مالان: بله، ما
همچنین اشاره گر داشته باشد.

1143
00:46:23,310 --> 00:46:25,560
پس این minorly آزار دهنده
در آن دیگر هستم

1144
00:46:25,560 --> 00:46:27,780
I ذخیره سازی فقط برای اعضای هیات
برای نشان دادن یک int.

1145
00:46:27,780 --> 00:46:30,990
من ذخیره سازی یک int و یک
اشاره گر، که آن هم 32 بیت.

1146
00:46:30,990 --> 00:46:33,470
بنابراین من به معنای واقعی کلمه دو برابر
مقدار فضای درگیر.

1147
00:46:33,470 --> 00:46:36,040
به طوری که تجارت کردن است، اما
که در مورد اعضای هیات است.

1148
00:46:36,040 --> 00:46:39,580
فرض کنید که شما مقدار int برای ذخیره کنید،
اما فرض کنید هر یک از این مربع ها

1149
00:46:39,580 --> 00:46:43,290
و یا هر یک از این انسان بود به نمایندگی
یک کلمه، کلمه انگلیسی است که

1150
00:46:43,290 --> 00:46:46,430
ممکن است پنج حرف، 10
شخصیت ها، شاید حتی بیشتر.

1151
00:46:46,430 --> 00:46:49,940
سپس با اضافه کردن فقط 32 بیت تر
ممکن است کمتر از یک معامله بزرگ است.

1152
00:46:49,940 --> 00:46:52,160
>> اگر هر یک از دانش آموزان
در تظاهرات

1153
00:46:52,160 --> 00:46:55,107
به معنای واقعی کلمه بود. ساختمانها دانشجویی که
نام و خانه ها و شاید

1154
00:46:55,107 --> 00:46:57,065
شماره تلفن ها و توییتر
دسته و مانند آن.

1155
00:46:57,065 --> 00:46:59,564
بنابراین همه زمینه ما آغاز شده
صحبت کردن در مورد روز دیگر،

1156
00:46:59,564 --> 00:47:02,410
بسیار کمتر از یک معامله بزرگ به عنوان
گره های ما را دریافت کنید جالب تر

1157
00:47:02,410 --> 00:47:05,972
و بزرگ به صرف، سوگند ملایمی، اضافی
اشاره گر فقط به آنها را با هم پیوند دارند.

1158
00:47:05,972 --> 00:47:07,180
اما در واقع، آن را یک تجارت کردن است.

1159
00:47:07,180 --> 00:47:09,560
و در واقع، فعال است
پیچیده تر، به عنوان نظر شما

1160
00:47:09,560 --> 00:47:11,770
توسط دستکاری از طریق ببینید
که مثال خاص.

1161
00:47:11,770 --> 00:47:14,302
اما اگر وجود دارد
برخی از جام مقدس است.

1162
00:47:14,302 --> 00:47:17,010
چه اگر ما یک قدم را ندارد
به عقب اما قدم بزرگی

1163
00:47:17,010 --> 00:47:19,180
و پیاده سازی داده ها
ساختار از طریق آن ما

1164
00:47:19,180 --> 00:47:22,870
می توانید عناصر مانند جک و یا پیدا کردن
کریستین یا هر عنصر دیگر

1165
00:47:22,870 --> 00:47:25,870
در این آرایه در زمان ثابت درست است؟

1166
00:47:25,870 --> 00:47:26,920
جستجو ثابت است.

1167
00:47:26,920 --> 00:47:28,320
حذف ثابت است.

1168
00:47:28,320 --> 00:47:29,570
درج ثابت است.

1169
00:47:29,570 --> 00:47:32,260
همه این عملیات ثابت می باشد.

1170
00:47:32,260 --> 00:47:33,750
خواهد بود که جام مقدس است.

1171
00:47:33,750 --> 00:47:36,690
و این جایی است که ما
را انتخاب کنید تا دفعه بعد.

1172
00:47:36,690 --> 00:47:38,600
سپس شما را مشاهده کنید.

1173
00:47:38,600 --> 00:47:39,371