1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> SPEAKER 1: خوب، پس این است
CS50 این پایان هفته پنج است.

3
00:00:15,860 --> 00:00:19,220
به یاد بیاورید که آخرین باری که ما
به دنبال آغاز شده در داده خیال باف

4
00:00:19,220 --> 00:00:22,310
ساختار است که شروع به حل
مشکلات، آغاز شده است که به معرفی

5
00:00:22,310 --> 00:00:25,640
مشکلات جدید است، اما کلید این
مرتب کردن بر اساس نخ بود که ما

6
00:00:25,640 --> 00:00:27,940
شروع به انجام از گره به گره.

7
00:00:27,940 --> 00:00:30,085
بنابراین این البته
یک لیست تنهایی مرتبط.

8
00:00:30,085 --> 00:00:31,960
و تنهایی مرتبط،
منظور من فقط یک وجود دارد

9
00:00:31,960 --> 00:00:33,380
موضوع بین هر یک از این گره ها.

10
00:00:33,380 --> 00:00:35,890
معلوم است شما می توانید خیال باف انجام
چیزهایی مانند لیست مضاعف مرتبط

11
00:00:35,890 --> 00:00:38,470
به موجب آن شما یک فلش
که در هر دو جهت، که

12
00:00:38,470 --> 00:00:40,320
می توانید با راندمان خاص کمک کند.

13
00:00:40,320 --> 00:00:42,000
اما این حل مشکل؟

14
00:00:42,000 --> 00:00:43,500
مشکل این را حل کند؟

15
00:00:43,500 --> 00:00:46,620
چرا ما در روز دوشنبه مراقبت کرد؟

16
00:00:46,620 --> 00:00:49,820
چرا، در تئوری، آیا ما در روز دوشنبه مراقبت؟

17
00:00:49,820 --> 00:00:50,630
این چیکار می کنه؟

18
00:00:50,630 --> 00:00:51,950
>> مخاطبان: ما به صورت پویا می توانید آن را تغییر اندازه دهید.

19
00:00:51,950 --> 00:00:53,740
>> SPEAKER 1: خوب، پس ما می توانیم
به صورت پویا تغییر اندازه آن.

20
00:00:53,740 --> 00:00:54,710
خب هر دو از شما انجام می شود.

21
00:00:54,710 --> 00:00:57,560
بنابراین شما به صورت پویا می توانید این تغییر اندازه
ساختار داده ها، در حالی که یک آرایه،

22
00:00:57,560 --> 00:01:00,760
به یاد بیاورید، شما باید بدانید که
پیشینی چه مقدار فضای شما می خواهید

23
00:01:00,760 --> 00:01:03,870
و اگر شما نیاز به یک کمی بیشتر
فضا، شما نوع از شانس هستید.

24
00:01:03,870 --> 00:01:05,560
شما باید برای ایجاد یک آرایه کاملا جدید است.

25
00:01:05,560 --> 00:01:07,893
شما باید به حرکت تمام خود را
داده ها از یکی به دیگری،

26
00:01:07,893 --> 00:01:10,600
در نهایت آزاد آرایه های قدیمی
اگر شما می توانید، و سپس ادامه دهید.

27
00:01:10,600 --> 00:01:13,891
که فقط احساس می کند بسیار پر هزینه و بسیار
ناکارآمد، و در واقع می توان آن را.

28
00:01:13,891 --> 00:01:14,890
اما این تمام خوب نیست.

29
00:01:14,890 --> 00:01:18,180
ما پرداخت قیمت، چه بود
از قیمت های واضح تر ما

30
00:01:18,180 --> 00:01:20,550
پرداخت با استفاده از یک لیست پیوندی؟

31
00:01:20,550 --> 00:01:22,825
>> مخاطبان: ما مجبور به استفاده از
فضای دو برای هر یک.

32
00:01:22,825 --> 00:01:25,200
SPEAKER 1: آره، بنابراین ما نیاز
حداقل دو بار به عنوان فضای زیادی است.

33
00:01:25,200 --> 00:01:27,700
در واقع، من متوجه شدم این تصویر
حتی یک کمی گمراه کننده است،

34
00:01:27,700 --> 00:01:32,200
چرا که در IDE CS50 در بسیاری از مدرن
کامپیوتر، یک اشاره گر و یا یک آدرس

35
00:01:32,200 --> 00:01:33,700
در واقع چهار بایت است.

36
00:01:33,700 --> 00:01:36,090
این بسیار اغلب این
روز هشت بایت، که

37
00:01:36,090 --> 00:01:38,530
معنی پایین ترین
مستطیل وجود دارد در واقع

38
00:01:38,530 --> 00:01:40,900
از نوع دو برابر
بزرگ به عنوان آنچه که من کشیده ام،

39
00:01:40,900 --> 00:01:44,409
که بدان معنی است شما با استفاده از سه برابر
فضای آنجا که ما در غیر این صورت ممکن است.

40
00:01:44,409 --> 00:01:46,700
در حال حاضر در همان زمان، ما
هنوز صحبت بایت، درست است؟

41
00:01:46,700 --> 00:01:49,140
ما لزوما در حال صحبت کردن نیست
مگابایت یا گیگابایت،

42
00:01:49,140 --> 00:01:51,000
مگر اینکه این داده ها سازه ها مطلع بزرگ است.

43
00:01:51,000 --> 00:01:54,510
>> و بنابراین، امروز ما شروع به در نظر
چگونه ممکن است ما داده اکتشاف

44
00:01:54,510 --> 00:01:57,310
موثر تر اگر در
واقع داده بزرگتر می شود.

45
00:01:57,310 --> 00:02:00,360
اما اجازه دهید سعی کنید به متعارف و استاندارد
عملیات اول

46
00:02:00,360 --> 00:02:02,460
که شما می توانید در این کار را انجام
انواع ساختمان داده.

47
00:02:02,460 --> 00:02:04,790
بنابراین چیزی شبیه به یک مرتبط
لیست کلی از

48
00:02:04,790 --> 00:02:07,514
عملیات مانند حذف،
قرار دادن، و جستجو کنید.

49
00:02:07,514 --> 00:02:08,639
و چه چیزی که من در؟

50
00:02:08,639 --> 00:02:11,222
این تنها بدان معنی است که معمولا،
اگر مردم با استفاده از لیست پیوندی،

51
00:02:11,222 --> 00:02:14,287
آنها یا شخص دیگری را اجرا کرده است
توابع مانند حذف، درج،

52
00:02:14,287 --> 00:02:16,120
و جستجو، بنابراین شما می توانید
در واقع انجام کاری

53
00:02:16,120 --> 00:02:18,030
با ساختار داده ها مفید است.

54
00:02:18,030 --> 00:02:20,760
بنابراین اجازه دهید نگاهی سریع
در ما چگونه ممکن است پیاده سازی

55
00:02:20,760 --> 00:02:24,530
برخی از کد برای یک لیست پیوندی شرح زیر است.

56
00:02:24,530 --> 00:02:27,885
>> بنابراین این فقط برخی از کد C است،
حتی یک برنامه کامل

57
00:02:27,885 --> 00:02:29,260
که من واقعا به سرعت شلاق تا.

58
00:02:29,260 --> 00:02:32,300
به صورت آنلاین در توزیع نمی
کد، دلیل آن در واقع اجرا نمی شود.

59
00:02:32,300 --> 00:02:33,790
اما توجه کنید من فقط
با یک نظر، گفت:

60
00:02:33,790 --> 00:02:36,130
نقطه نقطه نقطه، چیزی وجود دارد
وجود دارد، نقطه نقطه نقطه، چیزی وجود دارد.

61
00:02:36,130 --> 00:02:38,410
و اجازه دهید فقط نگاه
چه بخش آبدار هستند.

62
00:02:38,410 --> 00:02:40,790
بنابراین در خط سه،
به یاد آورید که این در حال حاضر

63
00:02:40,790 --> 00:02:45,960
ما پیشنهاد اعلام یک گره آخرین
زمان، یکی از کسانی که اشیاء مستطیل شکل است.

64
00:02:45,960 --> 00:02:48,790
از آن است که یک int است که ما N پاسخ،
اما ما می تواند آن را هر چیزی پاسخ،

65
00:02:48,790 --> 00:02:51,920
و پس از آن یک ستاره ساختار گره به نام آینده.

66
00:02:51,920 --> 00:02:55,520
و فقط به روشن، که دوم
خط، در خط شش، این است که؟

67
00:02:55,520 --> 00:02:57,930
چه چیزی است که برای ما انجام می دهند؟

68
00:02:57,930 --> 00:03:01,044
از آنجا که آن را قطعا به نظر می رسد بیشتر
مرموز از متغیرهای معمول ما.

69
00:03:01,044 --> 00:03:02,740
>> مخاطبان: این باعث می شود آن را بیش از یک حرکت.

70
00:03:02,740 --> 00:03:04,650
>> SPEAKER 1: این باعث می شود آن را بیش از یک حرکت.

71
00:03:04,650 --> 00:03:08,580
و به عبارت دقیق تر،
آن را به آدرس فروشگاه

72
00:03:08,580 --> 00:03:11,582
از گره که به معنای
معنایی در کنار آن، درست است؟

73
00:03:11,582 --> 00:03:13,540
پس از آن به رفتن نیست
لزوما هر چیزی حرکت می کند.

74
00:03:13,540 --> 00:03:15,290
این فقط رفتن به
ذخیره یک مقدار است که

75
00:03:15,290 --> 00:03:17,170
رفتن به آدرس
برخی از گره های دیگر،

76
00:03:17,170 --> 00:03:20,810
و به همین دلیل ما ساختار گفت
ستاره گره، ستاره دلالت

77
00:03:20,810 --> 00:03:22,370
یک اشاره گر و یا یک آدرس.

78
00:03:22,370 --> 00:03:26,390
OK، بنابراین در حال حاضر اگر شما فرض کنیم که ما
این N در دسترس ما، و اجازه دهید

79
00:03:26,390 --> 00:03:29,490
فرض کنیم که شخص دیگری است
درج یک دسته کامل از اعداد صحیح

80
00:03:29,490 --> 00:03:30,400
به یک لیست پیوندی.

81
00:03:30,400 --> 00:03:35,640
و لیست پیوندی است
توسط برخی از نقطه به نقطه اشاره

82
00:03:35,640 --> 00:03:39,040
یک متغیر به نام لیست که
در اینجا به عنوان یک پارامتر،

83
00:03:39,040 --> 00:03:43,120
چگونه در مورد خط بروم
14 اجرای جستجو؟

84
00:03:43,120 --> 00:03:45,990
به عبارت دیگر، اگر من هستم اجرای
تابع هدف در زندگی که

85
00:03:45,990 --> 00:03:48,889
این است که به یک int و پس از آن
آغاز یک لیست پیوندی،

86
00:03:48,889 --> 00:03:50,430
که یک اشاره گر به لیست پیوندی است.

87
00:03:50,430 --> 00:03:52,992
مانند اول، که من فکر می کنم دیوید
داوطلب ما در روز دوشنبه بود،

88
00:03:52,992 --> 00:03:54,700
او با اشاره به شد
طیف مرتبط لیست،

89
00:03:54,700 --> 00:03:57,820
آن را به عنوان هر چند ما در حال عبور
دیوید در عنوان آرگومان ما در اینجا.

90
00:03:57,820 --> 00:03:59,990
چگونه ما در مورد تراورس این لیست است؟

91
00:03:59,990 --> 00:04:04,640
خب، معلوم است که حتی اگر
اشاره گر نسبتا جدید در حال حاضر به ما،

92
00:04:04,640 --> 00:04:07,010
ما می توانیم این کار را انجام نسبتا
صریح.

93
00:04:07,010 --> 00:04:09,500
>> من قصد دارم به جلو بروید و
تعریف یک متغیر موقت که

94
00:04:09,500 --> 00:04:12,364
توسط کنوانسیون فقط رفتن
به نام اشاره گر، یا PTR،

95
00:04:12,364 --> 00:04:14,030
اما شما می توانید آن را هر چیزی که می خواهید تماس بگیرید.

96
00:04:14,030 --> 00:04:16,470
و من قصد دارم به مقداردهی اولیه
آن را به شروع از لیست.

97
00:04:16,470 --> 00:04:20,050
بنابراین شما می توانید نوع از این فکر می کنم
به عنوان من معلم روز دیگر،

98
00:04:20,050 --> 00:04:23,580
نوع اشاره در کسی
در میان انسان ما را به عنوان داوطلب.

99
00:04:23,580 --> 00:04:26,470
بنابراین من یک متغیر موقت که هستم
فقط در همین اشاره

100
00:04:26,470 --> 00:04:31,390
که ما به نام اتفاقی
داوطلب داود اشاره شده است.

101
00:04:31,390 --> 00:04:35,440
حالا در حالی که اشاره گر است
تهی نیست، به دلیل فراخوان

102
00:04:35,440 --> 00:04:40,350
که تهی برخی از ارزش نگهبان خاصی است
demarcates پایان از لیست،

103
00:04:40,350 --> 00:04:44,280
بنابراین در حالی که من در اشاره نمی
زمین مانند گذشته داوطلب ما

104
00:04:44,280 --> 00:04:47,190
بود، اجازه دهید به جلو
و زیر را انجام.

105
00:04:47,190 --> 00:04:51,820
اگر اشاره گر و در حال حاضر من از نوع می خواهید
برای انجام آنچه ما با دانش آموز بود

106
00:04:51,820 --> 00:04:57,410
structure-- اگر اشاره گر نقطه بعدی
equals-- نه، اگر اشاره گر نقطه N برابر با

107
00:04:57,410 --> 00:05:02,290
برابر با متغیر ازت،
استدلال شده است که در گذشت،

108
00:05:02,290 --> 00:05:05,370
پس از آن من می خواهم به جلو بروید
و می گویند بازگشت واقعی است.

109
00:05:05,370 --> 00:05:11,020
من پیدا کرده اند N تعداد داخل
یکی از گره از لیست پیوندی است.

110
00:05:11,020 --> 00:05:13,500
اما نقطه دیگر
با این نسخهها کار در این زمینه،

111
00:05:13,500 --> 00:05:17,260
چون اشاره گر، PTR، است
در واقع یک اشاره گر، آدرس،

112
00:05:17,260 --> 00:05:20,632
ما در واقع می توانید زیبا
استفاده از نهایت یک قطعه از نحو

113
00:05:20,632 --> 00:05:22,590
این نوع از می سازد
حس بصری و در واقع

114
00:05:22,590 --> 00:05:27,870
استفاده از فلش در اینجا، که به معنی رفتن از
که آدرس به عدد صحیح وجود دارد در.

115
00:05:27,870 --> 00:05:30,160
پس از آن در بسیار شبیه
روح به عملگر نقطه،

116
00:05:30,160 --> 00:05:33,860
اما به دلیل اشاره گر یک اشاره گر نیست
و نه یک ساختار واقعی خود،

117
00:05:33,860 --> 00:05:35,380
ما فقط استفاده از فلش.

118
00:05:35,380 --> 00:05:40,620
>> بنابراین اگر گره فعلی است که من،
متغیر موقت، من اشاره در

119
00:05:40,620 --> 00:05:43,060
نه N، چه من می خواهم کاری انجام دهید؟

120
00:05:43,060 --> 00:05:45,910
خب، با داوطلبان انسانی من
که ما در اینجا به حال و روز دیگر،

121
00:05:45,910 --> 00:05:49,710
اگر برای اولین بار است که انسان من یکی نیست
می خواهید، و شاید انسان دوم است

122
00:05:49,710 --> 00:05:52,660
یکی من می خواهم، و سوم، من
نیاز به نگه داشتن از لحاظ جسمی در حال حرکت.

123
00:05:52,660 --> 00:05:54,690
مانند چگونه از طریق یک لیست مرحله من؟

124
00:05:54,690 --> 00:05:57,470
هنگامی که ما یک آرایه به حال شما،
درست مثل من به علاوه به علاوه انجام داد.

125
00:05:57,470 --> 00:06:03,660
اما در این مورد، آن را به کافی
انجام اشاره گر، می شود، اشاره گر، بعدی.

126
00:06:03,660 --> 00:06:07,580
به عبارت دیگر، در این زمینه بعد
مثل این است که همه از دست چپ

127
00:06:07,580 --> 00:06:10,880
که داوطلبان انسانی ما در روز دوشنبه
با استفاده از به نقطه در برخی از گره های دیگر بود.

128
00:06:10,880 --> 00:06:12,890
این همسایه ها بعدی خود بودند.

129
00:06:12,890 --> 00:06:17,060
>> بنابراین اگر من می خواهم به قدم از طریق این لیست،
من فقط می توانید انجام به علاوه به علاوه دیگر،

130
00:06:17,060 --> 00:06:20,120
من به جای می گویند
من، اشاره گر است، رفتن

131
00:06:20,120 --> 00:06:24,650
برابر هر زمینه است،
رشته بعدی است، درست است،

132
00:06:24,650 --> 00:06:28,350
زیر همه کسانی که دست چپ
که ما در مرحله اشاره حال

133
00:06:28,350 --> 00:06:30,000
به برخی از ارزش های پس از آن.

134
00:06:30,000 --> 00:06:32,590
و اگر من از طریق دریافت
که طیف تکرار،

135
00:06:32,590 --> 00:06:39,330
و در نهایت، من ضربه های پوچ داشتن نیست
یافت N عین حال، من فقط بازگشت نادرست است.

136
00:06:39,330 --> 00:06:44,100
پس دوباره، که ما در اینجا انجام می دهند،
به عنوان در هر تصویر یک لحظه پیش،

137
00:06:44,100 --> 00:06:47,840
توسط اشاره به شروع
ابتدای فهرست احتمالا.

138
00:06:47,840 --> 00:06:50,970
و پس از آن را بررسی کنم، ارزش است
من به دنبال به نه برابر است؟

139
00:06:50,970 --> 00:06:52,650
اگر چنین است، من به راست و من انجام می شود.

140
00:06:52,650 --> 00:06:56,450
اگر نه، من دست من به روز رسانی،
اشاره گر AKA، به نقطه

141
00:06:56,450 --> 00:06:59,540
در محل فلش در کنار، و
پس از آن محل فلش آینده،

142
00:06:59,540 --> 00:07:00,480
و بعدی.

143
00:07:00,480 --> 00:07:03,770
من به سادگی راه رفتن را از طریق این آرایه است.

144
00:07:03,770 --> 00:07:06,010
>> پس دوباره، چه کسی اهمیت میدهد؟

145
00:07:06,010 --> 00:07:07,861
مانند آنچه این یک عنصر برای است؟

146
00:07:07,861 --> 00:07:10,360
خب، به یاد آورید که ما معرفی
مفهوم پشته، که

147
00:07:10,360 --> 00:07:15,400
یک داده نوع مقاله تا آنجا که آن را
یک چیز C، آن چیزی که CS50 نیست،

148
00:07:15,400 --> 00:07:19,430
این یک ایده انتزاعی، این ایده های
انباشته همه چیز در بالای یکدیگر

149
00:07:19,430 --> 00:07:21,820
که می تواند در اجرا
مجموعه ای از روش های مختلف.

150
00:07:21,820 --> 00:07:25,600
و یکی از راه های ما پیشنهاد می شد
یک آرایه، یا با یک لیست پیوندی.

151
00:07:25,600 --> 00:07:29,570
و معلوم است که canonically، یک
پشته از حداقل دو عملیات.

152
00:07:29,570 --> 00:07:32,320
و کلمات وزوز هستند فشار، به
فشار چیزی را بر روی پشته،

153
00:07:32,320 --> 00:07:34,770
مانند یک سینی جدید در
سالن غذاخوری، و یا پاپ،

154
00:07:34,770 --> 00:07:39,000
که به معنی به حذف بالاترین
سینی را از پشته در ناهار خوری

155
00:07:39,000 --> 00:07:41,500
سالن، و پس از آن شاید برخی از
عملیات دیگر نیز هست.

156
00:07:41,500 --> 00:07:45,770
پس چگونه ممکن است ساختار تعریف می کنیم
که ما در حال حاضر خواستار یک پشته؟

157
00:07:45,770 --> 00:07:50,020
>> خب، ما باید تمام نیاز
نحو در اختیار ما در C. من می گویم،

158
00:07:50,020 --> 00:07:53,830
من یک تعریف نوع را
یک ساختار داخل یک پشته،

159
00:07:53,830 --> 00:07:58,030
من قصد دارم به یک آرایه است، از یک
تمام دسته از اعداد و پس از اندازه.

160
00:07:58,030 --> 00:08:00,930
بنابراین به عبارت دیگر، اگر من می خواهم
برای اجرای این کد در،

161
00:08:00,930 --> 00:08:03,830
به من اجازه رفتن و فقط نوع
رسم این می گوید.

162
00:08:03,830 --> 00:08:06,317
پس این است که گفت، من را
ساختار که کردم یک آرایه،

163
00:08:06,317 --> 00:08:09,400
و من نمی دانم که چه ظرفیت است
ظاهرا برخی از ثابت که من

164
00:08:09,400 --> 00:08:10,858
تعریف جاهای دیگر، و این خوب است.

165
00:08:10,858 --> 00:08:15,260
اما فرض این تنها یکی،
دو، سه، چهار، پنج.

166
00:08:15,260 --> 00:08:16,700
بنابراین ظرفیت 5 است.

167
00:08:16,700 --> 00:08:21,730
این عنصر در داخل من
ساختار خواهد شد اعداد نامیده می شود.

168
00:08:21,730 --> 00:08:24,020
و پس از آن من نیاز به یک
متغیر دیگر ظاهرا

169
00:08:24,020 --> 00:08:27,814
اندازه که در ابتدا به نام من قصد دارم
به تصریح است به صفر مقداردهی اولیه.

170
00:08:27,814 --> 00:08:29,730
اگر هیچ چیز در آن وجود دارد
پشته، اندازه صفر است،

171
00:08:29,730 --> 00:08:31,420
و آن را ارزش زباله در اعداد است.

172
00:08:31,420 --> 00:08:33,450
من هیچ ایده چه چیزی در آن وجود دارد فقط رتبهدهی نشده است.

173
00:08:33,450 --> 00:08:36,059
>> بنابراین اگر من می خواهم به فشار
چیزی را بر روی پشته،

174
00:08:36,059 --> 00:08:40,780
گمان می کنم فشار تابع، و
من می گویم فشار 50، مانند شماره 50،

175
00:08:40,780 --> 00:08:44,090
که در آن شما پیشنهاد
من آن را در قرعه کشی این آرایه؟

176
00:08:44,090 --> 00:08:47,124
پنج پاسخ های متفاوت وجود دارد.

177
00:08:47,124 --> 00:08:48,790
کجا می خواهید به فشار شماره 50؟

178
00:08:48,790 --> 00:08:51,899
اگر هدف در اینجا، دوباره، با
تابع فشار، تصویب در بحث

179
00:08:51,899 --> 00:08:52,940
50، که در آن آن را قرار دهم؟

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
پنج possible-- 20٪ احتمال
از حدس زدن صحیح می باشد.

182
00:08:59,052 --> 00:08:59,896
بله؟

183
00:08:59,896 --> 00:09:00,740
>> رسید سمت راست.

184
00:09:00,740 --> 00:09:01,990
>> SPEAKER 1: سمت راست.

185
00:09:01,990 --> 00:09:08,359
در حال حاضر 25٪ احتمال وجود دارد
از حدس زدن صحیح می باشد.

186
00:09:08,359 --> 00:09:09,650
به طوری که در واقع خوب است.

187
00:09:09,650 --> 00:09:12,770
بر اساس قرارداد، من با یک آرایه می گویند،
ما به طور کلی را در سمت چپ شروع

188
00:09:12,770 --> 00:09:14,519
اما ما می توانیم قطعا
شروع در سمت راست.

189
00:09:14,519 --> 00:09:17,478
بنابراین اسپویلر در اینجا خواهد بود من
احتمالا رفتن به آن را رسم در سمت چپ،

190
00:09:17,478 --> 00:09:20,060
فقط در یک آرایه طبیعی که در آن دوست
من شروع به رفتن چپ به راست.

191
00:09:20,060 --> 00:09:21,780
اما اگر شما می توانید تلنگر
حساب، خوب است.

192
00:09:21,780 --> 00:09:23,060
آن را فقط معمولی نیست.

193
00:09:23,060 --> 00:09:24,880
خوب، من نیاز به ایجاد یک
تغییر بیشتر است.

194
00:09:24,880 --> 00:09:27,710
در حال حاضر که من چیزی تحت فشار قرار دادند
بر روی پشته، چه بعدی؟

195
00:09:27,710 --> 00:09:29,400
>> همه حق است، من به افزایش اندازه.

196
00:09:29,400 --> 00:09:32,600
بنابراین اجازه دهید من جلو و فقط به
به روز رسانی این است که صفر بود.

197
00:09:32,600 --> 00:09:35,950
و به جای آن در حال حاضر، من قصد دارم
به در ارزش یک قرار داده است.

198
00:09:35,950 --> 00:09:39,460
و در حال حاضر گمان می کنم یکی دیگر از فشار
تعداد روی پشته، مانند 51.

199
00:09:39,460 --> 00:09:42,680
خوب، من به یک
تغییر، که تا به اندازه دو.

200
00:09:42,680 --> 00:09:46,100
و پس از آن گمان می کنم فشار یک
تعداد روی پشته مانند 61،

201
00:09:46,100 --> 00:09:52,530
در حال حاضر من نیاز به بروز رسانی به اندازه یک
زمان، و ارزش 3 به عنوان اندازه.

202
00:09:52,530 --> 00:09:54,690
و در حال حاضر گمان می کنم پاسخ پاپ.

203
00:09:54,690 --> 00:09:57,250
در حال حاضر موسیقی پاپ، توسط کنوانسیون،
یک استدلال می کند را ندارد.

204
00:09:57,250 --> 00:10:00,430
با یک پشته، کل
نقطه استعاره سینی

205
00:10:00,430 --> 00:10:03,450
این است که شما اختیار ندارد
به رفتن که سینی، همه شما می توانید انجام دهید

206
00:10:03,450 --> 00:10:06,330
پاپ بالاترین یکی از
پشته، فقط به خاطر.

207
00:10:06,330 --> 00:10:08,010
این چیزی است که این ساختار داده است.

208
00:10:08,010 --> 00:10:12,250
>> بنابراین با این منطق اگر من
می گویند پاپ، چه می آید؟

209
00:10:12,250 --> 00:10:13,080
بنابراین 61.

210
00:10:13,080 --> 00:10:15,402
بنابراین آنچه که واقعا از کامپیوتر می باشد
قصد دارم در حافظه؟

211
00:10:15,402 --> 00:10:16,610
کد من چه کاری انجام دهید؟

212
00:10:16,610 --> 00:10:20,330
آنچه را که شما پیشنهاد
ما بر روی صفحه نمایش را تغییر دهید؟

213
00:10:20,330 --> 00:10:23,410
چه باید تغییر دهید؟

214
00:10:23,410 --> 00:10:24,960
متاسف؟

215
00:10:24,960 --> 00:10:26,334
بنابراین ما از 61 خلاص شوید.

216
00:10:26,334 --> 00:10:27,500
بنابراین من قطعا می تواند انجام دهد.

217
00:10:27,500 --> 00:10:28,640
و من می توانید از 61 خلاص شوید.

218
00:10:28,640 --> 00:10:30,980
و پس از آن چه دیگر
تغییر اتفاقی باید بیفتد؟

219
00:10:30,980 --> 00:10:33,160
حجم احتمالا برای رفتن به دو.

220
00:10:33,160 --> 00:10:34,210
و به این ترتیب که خوب است.

221
00:10:34,210 --> 00:10:36,690
اما یک دقیقه صبر کنید، اندازه
یک لحظه پیش سه بود.

222
00:10:36,690 --> 00:10:38,240
بیایید فقط بررسی سلامت عقل سریع است.

223
00:10:38,240 --> 00:10:41,810
چگونه ما می دانیم که ما را
می خواستم به 61 خلاص شوید؟

224
00:10:41,810 --> 00:10:42,760
از آنجا که ما در حال ظاهر.

225
00:10:42,760 --> 00:10:46,450
و بنابراین من این اندازه املاک دوم داشته باشد.

226
00:10:46,450 --> 00:10:48,470
>> یک دقیقه صبر کنید، من
فکر بازگشت به هفته دو

227
00:10:48,470 --> 00:10:51,660
زمانی که ما شروع به صحبت در مورد
آرایه ها، که در آن این مکان صفر بود،

228
00:10:51,660 --> 00:10:55,920
این مکان یکی بود، این محل بود
دو، این مکان سه، چهار است،

229
00:10:55,920 --> 00:10:58,460
آن را مانند به نظر می رسد
رابطه بین اندازه

230
00:10:58,460 --> 00:11:02,780
و عنصر که من می خواهم به حذف
از آرایه به نظر می رسد فقط چه؟

231
00:11:02,780 --> 00:11:05,120
حجم منهای یک.

232
00:11:05,120 --> 00:11:07,786
و به این ترتیب این که چگونه به عنوان انسان
ما می دانیم که 61 اولین بار می آید.

233
00:11:07,786 --> 00:11:09,160
چگونه کامپیوتر رفتن به می دانم؟

234
00:11:09,160 --> 00:11:11,701
هنگامی که کد خود را، که در آن شما احتمالا
می خواهم به انجام یک منهای اندازه،

235
00:11:11,701 --> 00:11:14,950
پس از سه منهای یک دو، و آن این است
معنی است که ما می خواهیم از 61 خلاص شوید.

236
00:11:14,950 --> 00:11:18,000
و سپس ما در واقع می توانید به روز رسانی
اندازه به طوری که اندازه کن

237
00:11:18,000 --> 00:11:20,300
از سه به دو می رود.

238
00:11:20,300 --> 00:11:24,520
و فقط به موشکاف، من قصد دارم
به پیشنهاد که من انجام می شود، درست است؟

239
00:11:24,520 --> 00:11:27,660
شما به طور مستقیم پیشنهاد
درست من باید از 61 خلاص شوید.

240
00:11:27,660 --> 00:11:30,700
اما من ندارد نوع
مرتب کردن بر اساس از شر آنها خلاص 61؟

241
00:11:30,700 --> 00:11:33,790
من به طور موثر را فراموش کرده ام
که در واقع وجود دارد.

242
00:11:33,790 --> 00:11:37,680
و فکر می کنم به PSET4، اگر شما را خوانده ام
مقاله در مورد پزشکی قانونی، پی دی اف

243
00:11:37,680 --> 00:11:40,780
که ما تا به حال شما بچه ها به عنوان خوانده شده، و یا شما
این هفته برای PSET4 به عنوان خوانده شده.

244
00:11:40,780 --> 00:11:44,300
به یاد بیاورید که این در واقع به وابسته
کل ایده کامپیوتر پزشکی قانونی.

245
00:11:44,300 --> 00:11:47,820
چه یک کامپیوتر به طور کلی می کند
فقط فراموش آن چیزی است،

246
00:11:47,820 --> 00:11:51,300
اما در رفتن نیست و مانند
سعی کنید آن را خراش و یا زیر پا بگذارند

247
00:11:51,300 --> 00:11:54,560
کسانی که بیت با صفر و آنهایی که
و یا برخی از الگوی تصادفی دیگر

248
00:11:54,560 --> 00:11:56,690
مگر اینکه شما خودتان این کار را به عمد.

249
00:11:56,690 --> 00:11:58,930
بنابراین شهود خود را بود
خوب، اجازه دهید از 61 خلاص شوید.

250
00:11:58,930 --> 00:12:00,650
اما در واقعیت، ما لازم نیست به زحمت.

251
00:12:00,650 --> 00:12:04,040
ما فقط نیاز به فراموش کرد که
آن وجود دارد با تغییر اندازه ما است.

252
00:12:04,040 --> 00:12:05,662
>> در حال حاضر یک مشکل با این پشته وجود دارد.

253
00:12:05,662 --> 00:12:07,620
اگر من هل دادن همه چیز
بر روی پشته، چه

254
00:12:07,620 --> 00:12:11,167
بدیهی است که اتفاق می افتد
تنها در یک زمان چند لحظه؟

255
00:12:11,167 --> 00:12:12,500
ما قصد داریم به اجرا از فضا.

256
00:12:12,500 --> 00:12:13,580
و چه کار کنیم؟

257
00:12:13,580 --> 00:12:14,680
ما نوع پیچ.

258
00:12:14,680 --> 00:12:19,000
این پیاده سازی اجازه نمی
ما تغییر اندازه آرایه، به دلیل استفاده از

259
00:12:19,000 --> 00:12:21,240
این نحو، اگر شما
فکر می کنم به دو هفته،

260
00:12:21,240 --> 00:12:23,520
هنگامی که شما اعلام کرده ام
به اندازه یک آرایه،

261
00:12:23,520 --> 00:12:26,780
ما را دیده اند که در آن مکانیزم
شما می توانید اندازه آرایه را تغییر دهید.

262
00:12:26,780 --> 00:12:29,020
و در واقع C که ویژگی را ندارد.

263
00:12:29,020 --> 00:12:32,524
اگر شما می گویم من پنج را
Nths، آنها را شماره های تماس،

264
00:12:32,524 --> 00:12:33,940
که همه شما در حال رفتن به آن را دریافت کند.

265
00:12:33,940 --> 00:12:38,790
بنابراین ما در حال حاضر از دوشنبه، دارند
توانایی بیان یک راه حل

266
00:12:38,790 --> 00:12:42,480
هر چند، ما فقط نیاز به نیشگون گرفتن و کشیدن
تعریف پشته ما

267
00:12:42,480 --> 00:12:46,840
به برخی از آرایه سخت رمزی نیست،
اما فقط برای ذخیره یک آدرس.

268
00:12:46,840 --> 00:12:47,890
>> حالا چرا این است؟

269
00:12:47,890 --> 00:12:51,690
در حال حاضر ما فقط باید راحت با
این واقعیت است که زمانی که برنامه من اجرا می شود،

270
00:12:51,690 --> 00:12:53,730
من احتمالا رفتن به
باید بپرسید انسان،

271
00:12:53,730 --> 00:12:55,110
چگونه بسیاری از اعداد را می خواهید برای ذخیره؟

272
00:12:55,110 --> 00:12:56,776
بنابراین ورودی بالاخره باید از جایی آمده است.

273
00:12:56,776 --> 00:12:59,140
اما هنگامی که من می دانم که
شماره، سپس من فقط می توانید

274
00:12:59,140 --> 00:13:02,470
استفاده از آنچه تابع را به
من یک تکه از حافظه؟

275
00:13:02,470 --> 00:13:03,580
من می توانم از malloc استفاده کنید.

276
00:13:03,580 --> 00:13:06,710
و من می توانم هر تعداد از گویند
من می خواهم بایت برای این Nths.

277
00:13:06,710 --> 00:13:10,910
و تمام من برای ذخیره اعداد در
متغیر در اینجا در داخل این ساختار

278
00:13:10,910 --> 00:13:13,480
باید چه؟

279
00:13:13,480 --> 00:13:18,440
آنچه در واقع به می رود
اعداد در این سناریو؟

280
00:13:18,440 --> 00:13:21,300
آره، یک اشاره گر به اولین
بایت از آن تکه از حافظه،

281
00:13:21,300 --> 00:13:24,940
و یا به طور خاص، آدرس
از اولین کسانی که بایت است.

282
00:13:24,940 --> 00:13:27,300
مهم نیست که اگر آن را یکی
بایت یا یک میلیارد بایت

283
00:13:27,300 --> 00:13:28,890
من فقط باید در مورد مراقبت از اول.

284
00:13:28,890 --> 00:13:31,530
از آنجا که آنچه تضمین malloc و
من تضمین سیستم عامل،

285
00:13:31,530 --> 00:13:34,170
این است که تکه از حافظه من
دریافت کنید، آن را برای رفتن به هم پیوسته.

286
00:13:34,170 --> 00:13:35,378
وجود دارد که نمی تواند شکاف.

287
00:13:35,378 --> 00:13:38,576
بنابراین اگر من برای 50 خواسته ام
بایت یا 1،000 بایت،

288
00:13:38,576 --> 00:13:40,450
همه آنها در حال رفتن به
برگشت به پشت به پشت.

289
00:13:40,450 --> 00:13:44,500
و تا زمانی که من به یاد داشته باشید که چگونه بزرگ، چگونه
بسیار برای همه من نیاز به دانستن خواسته

290
00:13:44,500 --> 00:13:46,230
اولین آدرس است.

291
00:13:46,230 --> 00:13:48,660
>> بنابراین در حال حاضر ما باید توانایی در کد.

292
00:13:48,660 --> 00:13:51,280
البته، آن را به ما را
زمان بیشتری را برای ارسال این،

293
00:13:51,280 --> 00:13:55,900
ما در حال حاضر می تواند که حافظه تخصیص مجدد توسط
فقط ذخیره سازی آدرس های مختلف وجود دارد

294
00:13:55,900 --> 00:13:59,060
اگر ما می خواهیم یک بزرگتر و یا حتی
یک تکه کوچک تر از حافظه است.

295
00:13:59,060 --> 00:14:00,170
بنابراین در اینجا به یک خاموش تجارت است.

296
00:14:00,170 --> 00:14:01,360
در حال حاضر ما پویایی است.

297
00:14:01,360 --> 00:14:03,350
ما هنوز
contiguousness من ادعا.

298
00:14:03,350 --> 00:14:05,881
از آنجا که از malloc خواهد به ما بدهد
یک قطعه پیوسته از حافظه است.

299
00:14:05,881 --> 00:14:08,630
اما این است که برای رفتن به یک درد در
گردن برای ما، برنامه نویس،

300
00:14:08,630 --> 00:14:09,770
به واقع کد است.

301
00:14:09,770 --> 00:14:10,730
این کار فقط بیشتر است.

302
00:14:10,730 --> 00:14:13,930
ما نیاز به کد شبیه به آنچه که من بود
banging از فقط یک لحظه پیش.

303
00:14:13,930 --> 00:14:16,120
بسیار شدنی، اما می افزاید پیچیدگی.

304
00:14:16,120 --> 00:14:19,520
و پس از آن زمان توسعه، برنامه نویس
زمان هنوز یکی دیگر از منابع

305
00:14:19,520 --> 00:14:22,520
که ما ممکن است نیاز به صرف
برخی از زمان برای دریافت ویژگی های جدید است.

306
00:14:22,520 --> 00:14:24,020
و پس از آن البته یک صف وجود دارد.

307
00:14:24,020 --> 00:14:26,227
ما نمی خواهد به این رفتن
در جزئیات بسیار.

308
00:14:26,227 --> 00:14:27,560
اما آن را در روح بسیار مشابه است.

309
00:14:27,560 --> 00:14:31,220
من می توانم یک صف پیاده سازی، و
عملیات مربوط به آن،

310
00:14:31,220 --> 00:14:35,660
در نوبت قراردادن و یا dequeue، مانند اضافه یا حذف،
این فقط یک راه خیال باف از گفتن آن است،

311
00:14:35,660 --> 00:14:38,100
در نوبت قراردادن و یا dequeue، به شرح زیر.

312
00:14:38,100 --> 00:14:41,170
من فقط می توانم خودم را یک ساختار
که دوباره است آرایه یک عدد است،

313
00:14:41,170 --> 00:14:44,000
که دوباره تا به اندازه،
اما چرا من در حال حاضر نیاز

314
00:14:44,000 --> 00:14:46,940
برای پیگیری از جلوی صف؟

315
00:14:46,940 --> 00:14:50,630
من نیاز به دانستن
جلوی پشته من.

316
00:14:50,630 --> 00:14:53,570
خب، اگر من دوباره برای
queue-- بیا فقط سخت

317
00:14:53,570 --> 00:14:57,870
کد آن را به عنوان داشتن مانند پنج
اعداد صحیح در اینجا به طور بالقوه.

318
00:14:57,870 --> 00:15:00,940
بنابراین این صفر، یک، دو، سه، چهار است.

319
00:15:00,940 --> 00:15:03,430
این است برای رفتن به
اعداد به نام دوباره.

320
00:15:03,430 --> 00:15:06,940
و این خواهد شد به نام اندازه.

321
00:15:06,940 --> 00:15:10,056
>> چرا آن را کافی نیست
به اندازه فقط؟

322
00:15:10,056 --> 00:15:11,680
خوب، اجازه دهید آن اعداد همان فشار در.

323
00:15:11,680 --> 00:15:14,220
بنابراین من pushed-- من را enqueued، و یا تحت فشار قرار دادند.

324
00:15:14,220 --> 00:15:20,150
در حال حاضر من نوبت 50، و پس از آن
51، و پس از آن 61 و نقطه نقطه نقطه.

325
00:15:20,150 --> 00:15:21,070
به طوری که در نوبت قراردادن.

326
00:15:21,070 --> 00:15:23,176
من را enqueued 50، پس از آن 51، پس از آن 61.

327
00:15:23,176 --> 00:15:25,050
و به نظر می رسد یکسان
به پشته تا کنون،

328
00:15:25,050 --> 00:15:27,190
به جز من نیاز به یک تغییر دهید.

329
00:15:27,190 --> 00:15:33,680
من نیاز به به روز رسانی این اندازه، بنابراین من به
از صفر به یک به دو تا سه در حال حاضر.

330
00:15:33,680 --> 00:15:35,760
چگونه dequeue من؟

331
00:15:35,760 --> 00:15:36,890
چه با dequeue اتفاقی می افتد؟

332
00:15:36,890 --> 00:15:41,950
چه کسی باید اول آمده به این لیست
اگر آن را به خط در فروشگاه اپل؟

333
00:15:41,950 --> 00:15:42,780
بنابراین 50.

334
00:15:42,780 --> 00:15:44,700
بنابراین نوع سختتر این بار آن را.

335
00:15:44,700 --> 00:15:47,880
در حالی که آخرین بار آن را فوق العاده بود
آسان به فقط یک منهای اندازه،

336
00:15:47,880 --> 00:15:51,440
من به پایان آرایه من به طور موثر
که در آن اعداد هستند، آن را حذف 61.

337
00:15:51,440 --> 00:15:52,920
اما من نمی خواهم به حذف 61.

338
00:15:52,920 --> 00:15:55,030
من می خواهم به 50، که
وجود دارد در 5:00 AM شد

339
00:15:55,030 --> 00:15:56,790
به خط کردن برای
آیفون و یا فلان چیز جدید است.

340
00:15:56,790 --> 00:16:01,200
و به همین ترتیب برای خلاص شدن از شر 50، من
می توانید این نه فقط انجام، درست است؟

341
00:16:01,200 --> 00:16:02,547
من می توانید عبور از 50.

342
00:16:02,547 --> 00:16:04,380
اما ما فقط ما گفت:
لازم نیست که می شود تا مقعد

343
00:16:04,380 --> 00:16:06,330
به عنوان به خراش و یا مخفی کردن داده ها.

344
00:16:06,330 --> 00:16:08,090
ما فقط می توانید فراموش که در آن است.

345
00:16:08,090 --> 00:16:12,330
>> اما اگر اندازه را تغییر دهم در حال حاضر به
دو، این اطلاعات کافی است

346
00:16:12,330 --> 00:16:15,711
بدانید که چه چیزی در جریان است در صف من؟

347
00:16:15,711 --> 00:16:16,680
نه واقعا.

348
00:16:16,680 --> 00:16:19,830
مانند اندازه من دو است، اما
کجا صف شروع،

349
00:16:19,830 --> 00:16:22,980
به خصوص اگر من هنوز هم
تعداد کسانی که همان در حافظه است.

350
00:16:22,980 --> 00:16:24,260
50، 51، 61.

351
00:16:24,260 --> 00:16:27,090
بنابراین من نیاز به یاد داشته باشید
اکنون که در آن جلوی است.

352
00:16:27,090 --> 00:16:29,630
و بنابراین به عنوان من پیشنهاد تا
وجود دارد، ما باید فقط به نام

353
00:16:29,630 --> 00:16:33,729
جلو n ام، که اولیه
مقدار باید چه بوده است؟

354
00:16:33,729 --> 00:16:35,270
صفر، فقط آغاز این فهرست است.

355
00:16:35,270 --> 00:16:40,876
اما در حال حاضر علاوه بر طرح ساده
اندازه، ما فقط افزایش جلو.

356
00:16:40,876 --> 00:16:42,000
حالا در اینجا مشکل دیگری است.

357
00:16:42,000 --> 00:16:43,030
پس یک بار من را ادامه دهم.

358
00:16:43,030 --> 00:16:47,520
فرض کنید این تعداد است
مانند 121، 124، و پس از آن، لعنتی،

359
00:16:47,520 --> 00:16:48,610
من از فضای هستم.

360
00:16:48,610 --> 00:16:50,390
اما یک دقیقه صبر کنید، من نیستم.

361
00:16:50,390 --> 00:16:55,630
بنابراین در این مرحله در داستان،
فرض کنید که به اندازه یک، دو است،

362
00:16:55,630 --> 00:17:00,370
سه، چهار، بنابراین فرض کنید که
اندازه چهار است، جلو یکی است،

363
00:17:00,370 --> 00:17:01,621
بنابراین 51 است در جلو.

364
00:17:01,621 --> 00:17:04,329
من می خواهم برای قرار دادن شماره دیگری اینجا هست،
اما، لعنتی، من از فضا است.

365
00:17:04,329 --> 00:17:06,710
اما من واقعا، درست است؟

366
00:17:06,710 --> 00:17:11,192
که در آن می تواند برخی از قرار
ارزش اضافی، مانند 171؟

367
00:17:11,192 --> 00:17:13,400
آره، من فقط می تواند نوع
برو به بیش وجود دارد، درست است؟

368
00:17:13,400 --> 00:17:18,161
و سپس عبور از 50، و یا
فقط آن را با 171 بازنویسی.

369
00:17:18,161 --> 00:17:20,410
و اگر شما تعجب که چرا
تعداد ما اینقدر تصادفی،

370
00:17:20,410 --> 00:17:24,150
این ها برای کامپیوتر گرفته
دروس علوم در دانشگاه هاروارد پس از CS50.

371
00:17:24,150 --> 00:17:27,510
اما این یک بهینه سازی خوب بود،
چون در حال حاضر من فضا هدر رفتن نیست.

372
00:17:27,510 --> 00:17:30,750
من هنوز هم به یاد داشته باشید
چقدر بزرگ این چیزی که کل است.

373
00:17:30,750 --> 00:17:31,500
پنج کل است.

374
00:17:31,500 --> 00:17:33,375
برای این که من نمی خواهم
شروع جای نوشتن 51.

375
00:17:33,375 --> 00:17:36,260
بنابراین در حال حاضر من هنوز هم از فضا هستم،
بنابراین مشکل مانند قبل است.

376
00:17:36,260 --> 00:17:39,140
اما شما می توانید ببینید که چگونه با شرکت
در کد خود را، شما احتمالا

377
00:17:39,140 --> 00:17:41,910
برای نوشتن یک کمی بیشتر
پیچیدگی را که اتفاق می افتد.

378
00:17:41,910 --> 00:17:44,510
و در واقع، آنچه اپراتور
در C احتمالا اجازه می دهد تا

379
00:17:44,510 --> 00:17:48,110
شما جادویی این دوری را انجام دهد؟

380
00:17:48,110 --> 00:17:50,160
آره عملگر باقی مانده،
علامت درصد.

381
00:17:50,160 --> 00:17:53,160
پس چه نوع سرد در مورد یک صف،
حتی اگر ما را حفظ آرایه رسم

382
00:17:53,160 --> 00:17:56,520
این خطوط مستقیم مانند، اگر شما
نوع مورد این عنوان کرنش فکر می کنم

383
00:17:56,520 --> 00:18:00,341
به عنوان یک دایره، پس از آن فقط
به طور مستقیم آن نوع آثار روانی

384
00:18:00,341 --> 00:18:01,590
من فکر می کنم کمی پاک تر.

385
00:18:01,590 --> 00:18:05,190
باز هم باید به پیاده سازی
که مدل ذهنی در کد.

386
00:18:05,190 --> 00:18:07,550
به طوری که نه سخت است،
در نهایت، به پیاده سازی،

387
00:18:07,550 --> 00:18:12,430
اما ما هنوز از دست دادن size-- نه،
توانایی تغییر اندازه، مگر اینکه ما این کار را.

388
00:18:12,430 --> 00:18:15,310
>> ما باید از شر از آرایه خلاص شدن از شر، ما
جایگزین کردن آن با یک اشاره گر تک،

389
00:18:15,310 --> 00:18:20,010
و سپس در جایی در کد من من
تماس بگیرید آنچه تابع در واقع به ایجاد

390
00:18:20,010 --> 00:18:23,720
آرایه از اعداد به نام؟

391
00:18:23,720 --> 00:18:26,190
از malloc، و یا برخی مشابه
عملکرد، دقیقا.

392
00:18:26,190 --> 00:18:30,481
هر گونه سوال و یا بر روی پشته صف.

393
00:18:30,481 --> 00:18:30,980
آره؟

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
سوال خوبی بود.

396
00:18:34,240 --> 00:18:35,830
چه پیمانه استفاده می کنید در اینجا.

397
00:18:35,830 --> 00:18:38,520
بنابراین به طور کلی، هنگامی که با استفاده از
وزارت دفاع، شما می توانید آن را انجام دهید

398
00:18:38,520 --> 00:18:40,620
با اندازه
ساختار داده ها کل.

399
00:18:40,620 --> 00:18:44,120
بنابراین چیزی شبیه به پنج یا ظرفیت، اگر
آن را ثابت، احتمالا نقش دارند.

400
00:18:44,120 --> 00:18:47,100
اما فقط انجام پیمانه پنج
احتمالا کافی نیست،

401
00:18:47,100 --> 00:18:51,380
چرا که ما نیاز به دانستن ما انجام می دهیم
پوشش در اطراف اینجا یا اینجا یا اینجا.

402
00:18:51,380 --> 00:18:54,160
بنابراین شما احتمالا همچنین در حال
رفتن به خواهید برای شامل

403
00:18:54,160 --> 00:18:57,220
اندازه چیزی، یا
متغیر مقابل است.

404
00:18:57,220 --> 00:19:00,140
بنابراین آن را فقط این نسبتا
بیان ساده ریاضی،

405
00:19:00,140 --> 00:19:02,000
اما به پیمانه می شود عنصر کلیدی.

406
00:19:02,000 --> 00:19:03,330
>> فیلم به قدری کوتاه اگر شما خواهد شد.

407
00:19:03,330 --> 00:19:05,780
یک انیمیشن است که برخی
مردمی در یکی دیگر از دانشگاه

408
00:19:05,780 --> 00:19:08,060
کنار هم قرار دادن ایم که
اقتباس برای این بحث.

409
00:19:08,060 --> 00:19:12,630
این شامل جک یادگیری
حقایق در مورد صف و آمار.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> فیلم: روزی روزگاری،
بود یک پسر به نام جک است.

412
00:19:21,890 --> 00:19:25,330
که آن را به دوستان آمد،
جک یک استعداد ندارد.

413
00:19:25,330 --> 00:19:28,220
بنابراین جک رفت و به صحبت کردن با
پسر محبوب ترین او می دانست.

414
00:19:28,220 --> 00:19:30,920
او به لو رفت و پرسید، چه باید بکنم؟

415
00:19:30,920 --> 00:19:33,400
لو دیدم که دوست خود را
واقعا نگران و دلواپس بود.

416
00:19:33,400 --> 00:19:36,050
خب، او شروع، فقط
نگاه کنید که چگونه شما در حال لباس پوشیدن.

417
00:19:36,050 --> 00:19:38,680
آیا شما هر گونه لباس نیست
با نگاه های مختلف؟

418
00:19:38,680 --> 00:19:39,660
بله، گفت: جک.

419
00:19:39,660 --> 00:19:40,840
من مطمئن هستم که انجام می دهند.

420
00:19:40,840 --> 00:19:43,320
بیا به خانه من و
من آنها را به شما نشان دهد.

421
00:19:43,320 --> 00:19:44,550
به طوری که آنها را به جک رفت.

422
00:19:44,550 --> 00:19:47,520
و جک لو نشان داد جعبه
که در آن او نگه داشته، همه پیراهن او،

423
00:19:47,520 --> 00:19:49,260
و شلوار خود را، و جوراب خود را.

424
00:19:49,260 --> 00:19:52,290
لو گفت، من می بینم شما
تمام لباس های خود را در یک شمع.

425
00:19:52,290 --> 00:19:54,870
چرا شما پوشیدن برخی از
یک بار در چندی دیگران؟

426
00:19:54,870 --> 00:19:58,020
>> جک گفت: خوب، وقتی من
حذف لباس و جوراب،

427
00:19:58,020 --> 00:20:00,780
من آنها را بشویید و
آنها را دور در جعبه.

428
00:20:00,780 --> 00:20:03,210
سپس می آید بعدی
صبح، و من هاپ.

429
00:20:03,210 --> 00:20:06,380
من به جعبه بروید و
لباس هایم بالا.

430
00:20:06,380 --> 00:20:09,070
لو به سرعت متوجه شدم
مشکل با جک.

431
00:20:09,070 --> 00:20:12,080
او نگه داشته، لباس، سی دی،
و کتاب در پشته.

432
00:20:12,080 --> 00:20:14,420
زمانی که او برای ما
چیزی برای خواندن و یا به لباس،

433
00:20:14,420 --> 00:20:17,100
او می خواهم این کتاب بالا و یا لباس زیر را انتخاب کنید.

434
00:20:17,100 --> 00:20:19,500
سپس هنگامی که او انجام شد، او
آن را به سمت راست برگشت.

435
00:20:19,500 --> 00:20:21,970
برگشت آن خواهند رفت، در بالای پشته.

436
00:20:21,970 --> 00:20:24,460
من می دانم که راه حل،
گفت با صدای بلند پیروزی.

437
00:20:24,460 --> 00:20:27,090
شما نیاز به یادگیری به
شروع به استفاده از یک صف.

438
00:20:27,090 --> 00:20:29,870
لو لباس جک را گرفت و
آنها را در گنجه آویزان.

439
00:20:29,870 --> 00:20:32,710
و هنگامی که او را خالی کرده بود
جعبه، او فقط آن را پرتاب کرد.

440
00:20:32,710 --> 00:20:36,500
>> سپس به او گفت، در حال حاضر جک، در پایان
روز، لباس های خود را در سمت چپ قرار

441
00:20:36,500 --> 00:20:37,990
هنگامی که شما آنها را دور.

442
00:20:37,990 --> 00:20:41,300
و سپس فردا صبح هنگامی که شما
دیدن آفتاب، لباس های خود را

443
00:20:41,300 --> 00:20:43,440
در سمت راست، از انتهای خط.

444
00:20:43,440 --> 00:20:44,880
آیا شما نمی بینید؟ گفت لو.

445
00:20:44,880 --> 00:20:46,370
از آن خواهد شد تا خوب.

446
00:20:46,370 --> 00:20:49,770
شما همه چیز را یک بار لباس
قبل از اینکه شما پوشیدن چیزی دو بار.

447
00:20:49,770 --> 00:20:52,670
و با همه چیز در صف
در گنجه و قفسه خود،

448
00:20:52,670 --> 00:20:55,160
جک شروع به احساس
کاملا مطمئن از خود.

449
00:20:55,160 --> 00:20:59,720
همه به لطف و لو
صف فوق العاده اش.

450
00:20:59,720 --> 00:21:01,220
SPEAKER 1: همه حق است، آن را شایان ستایش.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
پس چه شده است واقعا
در زیر هود در حال حاضر؟

453
00:21:10,080 --> 00:21:12,370
که ما اشاره گر،
که ما از malloc،

454
00:21:12,370 --> 00:21:15,680
که ما توانایی ایجاد
تکه های حافظه برای خودمان

455
00:21:15,680 --> 00:21:16,344
به صورت پویا.

456
00:21:16,344 --> 00:21:18,510
بنابراین این یک تصویر است ما
فقط روز دیگر دیدم.

457
00:21:18,510 --> 00:21:21,180
ما واقعا ساکن نیست
بر روی آن، اما این تصویر

458
00:21:21,180 --> 00:21:24,180
در جریان بوده است زیر
هود برای هفته ها در حال حاضر.

459
00:21:24,180 --> 00:21:27,050
و این نشان دهنده، فقط
یک مستطیل است که ما کشیده ام،

460
00:21:27,050 --> 00:21:28,180
حافظه کامپیوتر شما.

461
00:21:28,180 --> 00:21:31,850
و شاید کامپیوتر شما و یا CS50
ID، دارای یک گیگابایت حافظه یا RAM

462
00:21:31,850 --> 00:21:33,050
و یا دو گیگابایت یا چهار.

463
00:21:33,050 --> 00:21:34,450
این واقعا مهم نیست.

464
00:21:34,450 --> 00:21:37,240
سیستم عامل شما
ویندوز یا Mac OS یا لینوکس،

465
00:21:37,240 --> 00:21:41,120
اساسا اجازه می دهد تا برنامه های خود را
به فکر می کنم که به آن دسترسی دارد

466
00:21:41,120 --> 00:21:42,982
به طور کامل از
حافظه کامپیوتر شما،

467
00:21:42,982 --> 00:21:45,440
حتی اگر شما ممکن است در حال اجرا
برنامه های متعدد در یک بار.

468
00:21:45,440 --> 00:21:46,990
پس در حقیقت، که واقعا کار می کنند.

469
00:21:46,990 --> 00:21:49,448
اما این نوع از یک توهم
به تمام برنامه های خود را داده است.

470
00:21:49,448 --> 00:21:53,110
بنابراین اگر شما تا به حال دو گیگابایت رم، این
این است که چگونه کامپیوتر ممکن است آن فکر می کنم.

471
00:21:53,110 --> 00:21:57,110
>> در حال حاضر اتفاقی، یکی از این
همه چیز، یکی از این بخش از حافظه،

472
00:21:57,110 --> 00:21:58,350
است یک پشته نامیده می شود.

473
00:21:58,350 --> 00:22:01,680
و در واقع هر زمان
تا کنون در نوشتن کد

474
00:22:01,680 --> 00:22:05,900
که شما به نام یک
تابع، برای مثال اصلی.

475
00:22:05,900 --> 00:22:08,410
به یاد بیاورید که هر زمان من
حافظه کامپیوتر کشیده شده است،

476
00:22:08,410 --> 00:22:10,640
من همیشه مرتب کردن بر اساس قرعه کشی
نیمی از یک مستطیل در اینجا

477
00:22:10,640 --> 00:22:12,520
و زحمت صحبت کردن
در مورد چه چیزی بالا.

478
00:22:12,520 --> 00:22:15,980
چرا که وقتی اصلی نامیده می شود، من ادعا
که شما این بریدن از حافظه

479
00:22:15,980 --> 00:22:16,970
که در اینجا پایین می رود.

480
00:22:16,970 --> 00:22:20,650
و اگر یک تابع اصلی به نام
مانند مبادله، به خوبی مبادله اینجا می رود.

481
00:22:20,650 --> 00:22:23,720
و معلوم است که
که در آن پایان دادن به.

482
00:22:23,720 --> 00:22:26,277
در چیزی به نام پشته
در داخل حافظه کامپیوتر شما.

483
00:22:26,277 --> 00:22:28,360
در حال حاضر در پایان روز،
این فقط آدرس.

484
00:22:28,360 --> 00:22:30,680
آن را مانند بایت صفر است،
یکی بایت، بایت 2 میلیارد.

485
00:22:30,680 --> 00:22:33,130
اما اگر شما در مورد آن فکر
این شی مستطیل شکل،

486
00:22:33,130 --> 00:22:35,130
همه ما در حال انجام هر
زمان ما با یک تابع است

487
00:22:35,130 --> 00:22:37,180
لایه بندی یک تکه جدید از حافظه است.

488
00:22:37,180 --> 00:22:41,700
ما در حال دادن که تابع یک تکه
حافظه خود را برای کار با.

489
00:22:41,700 --> 00:22:44,490
>> و به یاد که این مهم است.

490
00:22:44,490 --> 00:22:46,400
از آنجا که اگر لازم ما
چیزی شبیه به مبادله

491
00:22:46,400 --> 00:22:51,610
و دو متغیر های محلی مانند A و B و
ما این مقادیر را تغییر دهید از یک و دو

492
00:22:51,610 --> 00:22:55,130
به دو و یک، فراخوان
که زمانی که مبادله می گرداند،

493
00:22:55,130 --> 00:22:58,330
آن را به عنوان هر چند این قطعه
حافظه فقط رفته.

494
00:22:58,330 --> 00:23:00,080
در واقع، آن را هنوز هم
forensically به وجود دارد.

495
00:23:00,080 --> 00:23:01,940
و چیزی که هنوز هم در واقع وجود دارد.

496
00:23:01,940 --> 00:23:05,410
اما مفهومی، آن را به عنوان
هر چند آن را به طور کامل از بین رفته اند.

497
00:23:05,410 --> 00:23:10,910
و به این ترتیب هیچ اصلی از کار مطمئن شوید که
که در آن تابع swap انجام شد،

498
00:23:10,910 --> 00:23:14,890
مگر اینکه آن را در واقع در آن به تصویب رسید
استدلال شده توسط اشاره گر و یا توسط مرجع.

499
00:23:14,890 --> 00:23:17,790
در حال حاضر، راه حل اساسی
به این مسئله را با مبادله

500
00:23:17,790 --> 00:23:19,970
در حال عبور از چیزهایی که در آدرس های.

501
00:23:19,970 --> 00:23:23,250
اما معلوم است، بیش از حد، چه
شده است در جریان بالا که بخشی

502
00:23:23,250 --> 00:23:26,330
از مستطیل تمام این مدت است
در عین حال حافظه بیشتر وجود دارد وجود دارد.

503
00:23:26,330 --> 00:23:28,790
و هنگامی که شما به صورت پویا
تخصیص حافظه،

504
00:23:28,790 --> 00:23:32,020
آیا آن را در داخل از getstring، که
ما شده ایم انجام را برای شما در CS50

505
00:23:32,020 --> 00:23:34,710
کتابخانه، و یا اگر شما بچه ها
از malloc تماس بگیرید و بپرسید

506
00:23:34,710 --> 00:23:37,950
سیستم عامل برای یک تکه از
حافظه، آن را از پشته آمده است.

507
00:23:37,950 --> 00:23:40,960
آن را از جای دیگری می آید
در حافظه کامپیوتر شما

508
00:23:40,960 --> 00:23:42,220
که پشته نامیده می شود.

509
00:23:42,220 --> 00:23:43,430
و این هر متفاوت است.

510
00:23:43,430 --> 00:23:44,285
این RAM همان است.

511
00:23:44,285 --> 00:23:45,160
این حافظه همان است.

512
00:23:45,160 --> 00:23:49,080
آن را فقط به RAM است که تا
به جای پایین در اینجا وجود دارد.

513
00:23:49,080 --> 00:23:50,750
>> و به این ترتیب به چه معنا است؟

514
00:23:50,750 --> 00:23:53,650
خوب، اگر کامپیوتر شما دارای
مقدار محدودی از حافظه

515
00:23:53,650 --> 00:23:57,450
و پشته در حال رشد است، به طوری که
به صحبت می کنند، و پشته، با توجه

516
00:23:57,450 --> 00:23:59,349
این فلش، در حال رشد است به پایین.

517
00:23:59,349 --> 00:24:01,140
به عبارت دیگر، هر
زمان شما malloc تماس بگیرید،

518
00:24:01,140 --> 00:24:03,430
شما در حال داده یک تکه
حافظه از بالا،

519
00:24:03,430 --> 00:24:06,630
پس از آن شاید کمی پایین تر، پس از آن کمی
پایین تر، هر زمانی که شما malloc تماس بگیرید،

520
00:24:06,630 --> 00:24:10,100
پشته، آن را استفاده،
از نوع در حال رشد،

521
00:24:10,100 --> 00:24:11,950
در حال رشد نزدیک و نزدیکتر به چه؟

522
00:24:11,950 --> 00:24:13,382
پشته.

523
00:24:13,382 --> 00:24:14,840
بنابراین آیا این مانند یک ایده خوب به نظر می رسد؟

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
منظور من، که در آن واقعا روشن نیست
چه چیز دیگری شما می توانید اگر فقط شما انجام

526
00:24:22,140 --> 00:24:23,910
یک مقدار محدود از حافظه است.

527
00:24:23,910 --> 00:24:25,200
اما این قطعا بد است.

528
00:24:25,200 --> 00:24:27,920
این دو فلش در می
سقوط دوره برای یکدیگر است.

529
00:24:27,920 --> 00:24:31,930
>> و معلوم است که مرد بد است، مردمی که
به خصوص با برنامه نویسی خوب،

530
00:24:31,930 --> 00:24:36,140
و تلاش برای هک کامپیوتر،
می توانید این واقعیت بهره برداری.

531
00:24:36,140 --> 00:24:38,290
در واقع، اجازه دهید در نظر
یک قطعه کوچک است.

532
00:24:38,290 --> 00:24:41,350
بنابراین این مثال شما می توانید به عنوان خوانده شده
در مورد با جزئیات بیشتر در ویکیپدیا.

533
00:24:41,350 --> 00:24:43,100
ما شما را در نقطه
مقاله اگر کنجکاو.

534
00:24:43,100 --> 00:24:45,650
اما به طور کلی از یک حمله وجود دارد
شناخته شده به عنوان سرریز بافر که

535
00:24:45,650 --> 00:24:49,570
برای تا زمانی که انسان وجود داشته
توانایی دستکاری داشته اند

536
00:24:49,570 --> 00:24:53,120
حافظه کامپیوتر، به ویژه در C.
این یک برنامه بسیار خودسرانه است،

537
00:24:53,120 --> 00:24:55,130
اما اجازه دهید آن از پایین به بالا به عنوان خوانده شده.

538
00:24:55,130 --> 00:24:57,650
اصلی را به ستاره کاراکتر تعداد آنها و argv.

539
00:24:57,650 --> 00:24:59,830
پس از آن یک برنامه ای است که طول می کشد
آرگومان های خط فرمان.

540
00:24:59,830 --> 00:25:03,620
و همه اصلی می کند ظاهرا پاسخ است
یک تابع، آن را F برای سادگی.

541
00:25:03,620 --> 00:25:04,610
و آن را در چه می گذرد؟

542
00:25:04,610 --> 00:25:05,490
ی argv یک.

543
00:25:05,490 --> 00:25:09,320
بنابراین آن را به F عبور هر
کلمه این است که کاربر تایپ

544
00:25:09,320 --> 00:25:11,500
در اعلان پس از
نام برنامه را در همه.

545
00:25:11,500 --> 00:25:15,730
بنابراین بسیار شبیه سزار و یا ویژنر که
شما ممکن است به خاطر انجام می دهند با ی argv.

546
00:25:15,730 --> 00:25:16,680
>> پس چه F است؟

547
00:25:16,680 --> 00:25:19,760
F طول می کشد در یک رشته
به عنوان آرگومان های انحصاری خود

548
00:25:19,760 --> 00:25:22,100
AKA یک ستاره کاراکتر، همان
چیزی، به عنوان یک رشته است.

549
00:25:22,100 --> 00:25:24,920
و آن را به نام دلخواه
نوار در این مثال.

550
00:25:24,920 --> 00:25:27,710
و پس از آن کاراکتر C 12،
فقط در عبارت،

551
00:25:27,710 --> 00:25:31,750
چه کاراکتر C براکت 12 انجام برای ما؟

552
00:25:31,750 --> 00:25:33,440
چه کاری انجام میدهد؟

553
00:25:33,440 --> 00:25:36,490
تخصیص حافظه، به طور خاص
12 بایت برای 12 کاراکتر می باشد.

554
00:25:36,490 --> 00:25:36,990
دقیقا.

555
00:25:36,990 --> 00:25:40,000
و پس از آن در آخرین خط، هم بزنید و
کپی، شما احتمالا دیده ایم.

556
00:25:40,000 --> 00:25:43,360
این یک نسخه رشته است
تابع هدف در زندگی که

557
00:25:43,360 --> 00:25:48,160
است برای کپی کردن آرگومان دوم آن
به اولین آرگومان آن،

558
00:25:48,160 --> 00:25:51,190
اما تنها تا یک
تعداد معینی از بایت است.

559
00:25:51,190 --> 00:25:53,860
بنابراین استدلال سوم می گوید:
چگونه بسیاری از بایت باید به شما کپی کنید؟

560
00:25:53,860 --> 00:25:56,720
طول نوار،
هر کاربر تایپ در.

561
00:25:56,720 --> 00:25:59,320
و محتویات
نوار، این رشته، می

562
00:25:59,320 --> 00:26:02,330
کپی در حافظه در اشاره در C.

563
00:26:02,330 --> 00:26:04,060
>> بنابراین به نظر می رسد این نوع احمقانه، و آن است.

564
00:26:04,060 --> 00:26:06,300
این یک مثال ساختگی است،
اما آن را نماینده

565
00:26:06,300 --> 00:26:10,100
از یک کلاس از بردارهای حمله،
راه حمله به یک برنامه است.

566
00:26:10,100 --> 00:26:15,050
همه خوب و خوب اگر کاربر
انواع در یک کلمه که 11 کاراکتر

567
00:26:15,050 --> 00:26:18,040
یا کمتر، به علاوه بک اسلش صفر.

568
00:26:18,040 --> 00:26:22,830
اگر کاربر در بیش از
11 یا 12 یا 20 یا 50 کاراکتر؟

569
00:26:22,830 --> 00:26:25,090
این برنامه را به انجام چه خبر؟

570
00:26:25,090 --> 00:26:29,360
گسل بالقوه SEG. قرار است که
کورکورانه همه چیز را در نوار بالا کپی

571
00:26:29,360 --> 00:26:31,750
طول آن است، که
به معنای واقعی کلمه همه چیز را در نوار،

572
00:26:31,750 --> 00:26:36,307
به آدرس اشاره کرد C. اما C
تنها پیشگیرانه به عنوان 12 بایت داده شده است.

573
00:26:36,307 --> 00:26:37,640
اما هیچ چک اضافی وجود دارد.

574
00:26:37,640 --> 00:26:38,700
وجود ندارد در صورتی که شرایط.

575
00:26:38,700 --> 00:26:40,580
هیچ چک کردن خطا در اینجا وجود دارد.

576
00:26:40,580 --> 00:26:43,270
>> و بنابراین، آنچه این برنامه این است
برای انجام شده است فقط کورکورانه

577
00:26:43,270 --> 00:26:45,750
کپی یک چیز دیگر است.

578
00:26:45,750 --> 00:26:47,880
و بنابراین اگر ما این رسم
به عنوان یک تصویر، در اینجا

579
00:26:47,880 --> 00:26:49,860
فقط یک تکه از فضای حافظه.

580
00:26:49,860 --> 00:26:53,470
بنابراین اطلاع در پایین، ما
در نوار متغیر محلی است.

581
00:26:53,470 --> 00:26:57,330
به طوری که اشاره گر که رفتن به store--
نه که استدلال محلی که

582
00:26:57,330 --> 00:26:58,672
رفتن به ذخیره نوار رشته است.

583
00:26:58,672 --> 00:27:00,380
و پس از آن فقط متوجه
بالاتر از آن در یک پشته،

584
00:27:00,380 --> 00:27:02,505
زیرا هر بار که شما درخواست
برای حافظه در پشته،

585
00:27:02,505 --> 00:27:04,310
از آن می رود کمی
در بالای آن pictorially،

586
00:27:04,310 --> 00:27:06,270
توجه کنید که ما 12 بایت کردم وجود دارد.

587
00:27:06,270 --> 00:27:10,690
یکی از بالا سمت چپ C براکت صفر و است
یکی از پایین سمت راست C براکت 11 است.

588
00:27:10,690 --> 00:27:12,870
که چقدر کامپیوتر
رفتن به آن را پخش کردن.

589
00:27:12,870 --> 00:27:18,300
بنابراین فقط به طور مستقیم، اگر نوار دارای بیش
بیش از 12 کاراکتر در کل، از جمله

590
00:27:18,300 --> 00:27:25,790
بک اسلش صفر، که در آن است که
12 یا براکت C 12 برای رفتن؟

591
00:27:25,790 --> 00:27:28,440
و یا به جای که در آن در 12th است
شخصیت یا شخصیت 13TH،

592
00:27:28,440 --> 00:27:30,900
شخصیت صدم رفتن
برای پایان دادن به در تصویر؟

593
00:27:30,900 --> 00:27:33,400
در بالا یا زیر؟

594
00:27:33,400 --> 00:27:36,300
>> راست، چرا که حتی اگر
پشته خود رشد می کند به سمت بالا،

595
00:27:36,300 --> 00:27:39,590
هنگامی که شما مسائل را در قرار داده ام
آن، آن را به دلایل طراحی،

596
00:27:39,590 --> 00:27:41,294
قرار می دهد حافظه از بالا به پایین.

597
00:27:41,294 --> 00:27:44,460
بنابراین اگر شما بیش از 12 بایت کردم،
شما در حال رفتن به شروع به بازنویسی نوار.

598
00:27:44,460 --> 00:27:47,280
در حال حاضر که یک اشکال است، اما آن
واقعا یک معامله بزرگ است.

599
00:27:47,280 --> 00:27:51,130
اما این یک معامله بزرگ است، به دلیل وجود دارد
چیزهای بیشتری که در حافظه است.

600
00:27:51,130 --> 00:27:53,074
بنابراین در اینجا ما چگونه ممکن است
قرار سلام، روشن می شود.

601
00:27:53,074 --> 00:27:54,490
اگر من در سلام در اعلان تایپ.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O بک اسلش صفر، به پایان می رسد تا در
کسانی که 12 بایت، و ما فوق العاده امن است.

603
00:27:59,330 --> 00:28:00,330
همه خوب است.

604
00:28:00,330 --> 00:28:03,020
اما اگر تایپ کنید من چیزی
دیگر، به طور بالقوه آن

605
00:28:03,020 --> 00:28:05,860
رفتن به خزش به نوار فضا.

606
00:28:05,860 --> 00:28:08,405
اما بدتر از آن، آن را تبدیل
از این همه زمان،

607
00:28:08,405 --> 00:28:11,530
حتی اگر ما هرگز در مورد صحبت کردیم
آن، پشته برای چیزهای دیگر استفاده می شود.

608
00:28:11,530 --> 00:28:13,560
آن را فقط متغیرهای محلی است.

609
00:28:13,560 --> 00:28:15,100
>> C یک زبان سطح بسیار پایین است.

610
00:28:15,100 --> 00:28:17,810
و آن نوع مخفیانه
با استفاده از پشته هم

611
00:28:17,810 --> 00:28:21,260
به یاد داشته باشید زمانی که یک
تابع نامیده می شود، چه

612
00:28:21,260 --> 00:28:26,040
آدرس تابع قبلی،
پس از آن به که تابع می تواند پرش.

613
00:28:26,040 --> 00:28:29,980
بنابراین، هنگامی که تماس های اصلی مبادله، در میان
چیزهایی که روی پشته قرار می

614
00:28:29,980 --> 00:28:34,380
نه فقط معاوضه متغیرهای محلی،
و یا استدلال خود، همچنین مخفیانه تحت فشار قرار دادند

615
00:28:34,380 --> 00:28:37,510
بر روی پشته به عنوان نمایندگی
توسط تکه های قرمز در اینجا،

616
00:28:37,510 --> 00:28:40,520
آدرس اصلی فیزیکی است
در حافظه کامپیوتر شما،

617
00:28:40,520 --> 00:28:44,180
به طوری که وقتی مبادله انجام شده است، کامپیوتر
می داند که من نیاز به رفتن برگشت به بخش اصلی

618
00:28:44,180 --> 00:28:46,760
و پایان اجرای تابع اصلی.

619
00:28:46,760 --> 00:28:51,960
بنابراین این خطرناک است، چون اگر
نوع کاربر در خوبی بیش از سلام،

620
00:28:51,960 --> 00:28:57,030
به طوری که ورودی کاربر clobbers
و یا رونویسی که بخش قرمز،

621
00:28:57,030 --> 00:28:59,820
اگر منطقی کامپیوتر
فقط رفتن به کورکورانه فرض

622
00:28:59,820 --> 00:29:03,830
که بایت است که قطعه قرمز رنگ هستند
آدرس که به آن باید بازگشت،

623
00:29:03,830 --> 00:29:09,020
چه می شود اگر دشمن است و یا به اندازه کافی هوشمند
اندازه کافی خوش شانس برای قرار دادن یک دنباله ای از بایت

624
00:29:09,020 --> 00:29:13,450
وجود دارد که به نظر می رسد مانند آدرس،
اما آدرس از کد است

625
00:29:13,450 --> 00:29:18,730
که او می خواهد کامپیوتر
برای اجرای به جای اصلی.

626
00:29:18,730 --> 00:29:21,670
>> به عبارت دیگر، اگر چه
کاربران در حال تایپ کردن در اعلان،

627
00:29:21,670 --> 00:29:23,850
تنها چیزی نیست
مانند بی ضرر سلام،

628
00:29:23,850 --> 00:29:28,210
اما در واقع کد که معادل
تمام فایل های این کاربر را حذف کنید؟

629
00:29:28,210 --> 00:29:30,060
و یا رمز عبور خود را ایمیل به من؟

630
00:29:30,060 --> 00:29:31,940
ورود به سیستم یا شروع خود
کلید، درست است؟

631
00:29:31,940 --> 00:29:34,920
یک راه وجود دارد، اجازه دهید امروز تصریح،
که آنها می توانند در نوع نه فقط سلام

632
00:29:34,920 --> 00:29:36,711
جهان و یا نام خود،
آنها می توانند در اصل

633
00:29:36,711 --> 00:29:39,570
تصویب در کد، صفر و
آنهایی که، که کامپیوتر

634
00:29:39,570 --> 00:29:43,450
اشتباهات برای هر دو کد و یک آدرس.

635
00:29:43,450 --> 00:29:48,950
بنابراین تا حدودی انتزاعی البته، اگر
نوع کاربر در کافی کد خصمانه

636
00:29:48,950 --> 00:29:52,330
ما در اینجا به عنوان که باید تعمیم
الف حمله و یا دشمنان است.

637
00:29:52,330 --> 00:29:53,140
چیزهای بد.

638
00:29:53,140 --> 00:29:55,306
ما در مورد اهمیت نمی
اعداد یا صفر و یا آنهایی که

639
00:29:55,306 --> 00:29:59,470
امروز، به طوری که شما را تا پایان
نوشتن که بخش قرمز،

640
00:29:59,470 --> 00:30:01,580
توجه کنید که دنباله ای از بایت است.

641
00:30:01,580 --> 00:30:05,020
O 835 C صفر هشت صفر است.

642
00:30:05,020 --> 00:30:08,960
و در حال حاضر به عنوان مقاله ویکیپدیا در اینجا
پیشنهاد کرده است، اگر شما در حال حاضر در واقع شروع

643
00:30:08,960 --> 00:30:12,460
برچسب بایت در کامپیوتر شما
حافظه، چه مقاله ویکیپدیا

644
00:30:12,460 --> 00:30:19,060
ارائه طرح این است که، اگر آدرس
از بایتی بالا سمت چپ 80 C 0 3508 است.

645
00:30:19,060 --> 00:30:22,200
>> به عبارت دیگر، اگر آن مرد بد است
به اندازه کافی هوشمند با کد خود را

646
00:30:22,200 --> 00:30:26,650
به واقع یک عدد را در اینجا که
مربوط به آدرس از کد

647
00:30:26,650 --> 00:30:29,180
او تزریق
به کامپیوتر، شما

648
00:30:29,180 --> 00:30:31,050
می توانید کامپیوتر فریب
به انجام کاری.

649
00:30:31,050 --> 00:30:34,140
از بین بردن فایل، ایمیل
همه چیز، خرناس ترافیک خود را،

650
00:30:34,140 --> 00:30:36,710
به معنای واقعی کلمه هر چیزی می تواند باشد
به کامپیوتر تزریق می شود.

651
00:30:36,710 --> 00:30:39,220
و به این ترتیب یک سرریز بافر
حمله در هسته خود

652
00:30:39,220 --> 00:30:43,530
فقط یک احمق، احمق
مهم از یک آرایه است که

653
00:30:43,530 --> 00:30:45,840
لازم نیست مرزهای خود را بررسی می شود.

654
00:30:45,840 --> 00:30:48,850
و این چیزی است که فوق العاده خطرناک
و به طور همزمان فوق العاده قدرتمند

655
00:30:48,850 --> 00:30:52,560
در C این است که ما در واقع دارای
دسترسی به هر نقطه در حافظه است.

656
00:30:52,560 --> 00:30:55,320
این به ما است، برنامه نویسان،
که نوشتن کد اصلی

657
00:30:55,320 --> 00:30:59,330
برای بررسی طول رفو از هر
آرایه های که ما در حال دستکاری.

658
00:30:59,330 --> 00:31:00,750
بنابراین به روشن باشد، چه ثابت است؟

659
00:31:00,750 --> 00:31:03,190
اگر ما به این رول
کد، من باید نه فقط

660
00:31:03,190 --> 00:31:08,000
تغییر طول نوار، چه
دیگری باید چک شود؟

661
00:31:08,000 --> 00:31:10,620
چه چیز دیگری باید انجام به
جلوگیری از این حمله به طور کامل؟

662
00:31:10,620 --> 00:31:14,110
من نمی خواهم به فقط کورکورانه می گویند
که شما باید به عنوان بسیاری بایت کپی

663
00:31:14,110 --> 00:31:16,140
به عنوان طول نوار است.

664
00:31:16,140 --> 00:31:18,910
من می خواهم بگویم، کپی به عنوان
بایت های بسیاری به عنوان در نوار هستند

665
00:31:18,910 --> 00:31:24,090
تا اختصاص داده
حافظه، و یا 12 حداکثر.

666
00:31:24,090 --> 00:31:27,450
بنابراین من نیاز به نوعی از شرایط اگر
می کند که بررسی طول نوار،

667
00:31:27,450 --> 00:31:32,800
اما اگر آن را بیش از 12، ما کد فقط سخت
12 به عنوان حداکثر فاصله ممکن.

668
00:31:32,800 --> 00:31:35,910
در غیر این صورت بافر به اصطلاح
حمله سرریز می تواند رخ دهد.

669
00:31:35,910 --> 00:31:38,451
در پایین آن اسلاید،
اگر شما کنجکاو هستید به ادامه مطلب

670
00:31:38,451 --> 00:31:41,200
مقاله واقعی اصلی است
اگر شما می خواهم به نگاهی.

671
00:31:41,200 --> 00:31:44,550
>> اما در حال حاضر، در میان قیمت
پرداخت در اینجا ناکارآمدی بود.

672
00:31:44,550 --> 00:31:46,680
به طوری که یک سریع بود
کم نگاه در چه سطح

673
00:31:46,680 --> 00:31:49,709
مشکلات هم اکنون می توانید بوجود می آیند که ما
دسترسی به حافظه کامپیوتر را داشته باشد.

674
00:31:49,709 --> 00:31:51,750
اما مشکل دیگری که ما
در حال حاضر در روز دوشنبه تصادفا

675
00:31:51,750 --> 00:31:53,800
فقط ناکارآمدی بود
از یک لیست پیوندی.

676
00:31:53,800 --> 00:31:56,019
ما به زمان خطی.

677
00:31:56,019 --> 00:31:57,560
ما دیگر باید یک آرایه به هم پیوسته.

678
00:31:57,560 --> 00:31:58,980
ما با دسترسی تصادفی نیست.

679
00:31:58,980 --> 00:32:00,710
ما می توانیم علامت کروشه مربع استفاده کنید.

680
00:32:00,710 --> 00:32:04,590
ما به معنای واقعی کلمه مجبور به استفاده از یک حلقه در حالی که
مانند یکی از من نوشت یک لحظه پیش.

681
00:32:04,590 --> 00:32:09,740
اما در روز دوشنبه، ما ادعا کرد که ما می توانیم
خزش آن را به حوزه بهره وری

682
00:32:09,740 --> 00:32:13,040
دستیابی به چیزی که
لگاریتمی شاید، و یا بهترین و در عین حال،

683
00:32:13,040 --> 00:32:16,120
شاید حتی چیزی که
اصطلاح زمان ثابت است.

684
00:32:16,120 --> 00:32:19,840
پس چگونه می توان این کار را با استفاده از این جدید
ابزار، به این آدرس، این اشاره گر،

685
00:32:19,840 --> 00:32:22,210
و چیزهایی از خود ما نخ؟

686
00:32:22,210 --> 00:32:23,960
خب، فرض کنید که
در اینجا، این یک دسته

687
00:32:23,960 --> 00:32:27,170
از اعداد است که ما می خواهیم برای ذخیره در
ساختار داده ها و جستجو موثر است.

688
00:32:27,170 --> 00:32:30,960
ما کاملا می توانید به هفته عقب
دو، این پرتاب به یک آرایه،

689
00:32:30,960 --> 00:32:33,150
و جستجو آنها را با استفاده جستجوی دودویی.

690
00:32:33,150 --> 00:32:34,040
تفرقه بینداز و حکومت کن.

691
00:32:34,040 --> 00:32:37,720
و در واقع شما نوشت
جستجوی دودویی در PSET3،

692
00:32:37,720 --> 00:32:40,100
که در آن شما اجرا برنامه پیدا کردن.

693
00:32:40,100 --> 00:32:40,890
اما شما می دانید چه.

694
00:32:40,890 --> 00:32:45,060
این نوع از بیشتر وجود دارد
راه هوشمندانه از انجام این کار.

695
00:32:45,060 --> 00:32:47,390
آن را کمی بیشتر
پیچیده و شاید

696
00:32:47,390 --> 00:32:50,830
ما اجازه می دهد که چرا باینری
جستجو بسیار سریع تر است.

697
00:32:50,830 --> 00:32:52,980
اول، اجازه دهید به معرفی
مفهوم از یک درخت.

698
00:32:52,980 --> 00:32:54,730
که حتی اگر در
درختان واقعیت نوع

699
00:32:54,730 --> 00:32:57,730
رشد شبیه به این، در جهان از کامپیوتر
علم آنها از نوع رشد رو به پایین

700
00:32:57,730 --> 00:33:00,830
مانند یک درخت خانواده، که در آن شما
پدربزرگ و مادربزرگ خود یا پدربزرگ و مادربزرگ بزرگ

701
00:33:00,830 --> 00:33:04,580
و یا فلان چیز در بالا، ایلخانی و
مادر خانواده، یکی فقط

702
00:33:04,580 --> 00:33:07,930
به اصطلاح ریشه، گره، زیر
که کودکان خود هستند،

703
00:33:07,930 --> 00:33:11,442
زیر که کودکان خود را، و یا
فرزندان آن به طور کلی.

704
00:33:11,442 --> 00:33:13,400
و هر کسی حلق آویز کردن
پایین خانواده

705
00:33:13,400 --> 00:33:16,070
درخت، علاوه بر این که
جوان در خانواده،

706
00:33:16,070 --> 00:33:19,520
همچنین می توانید فقط عام شود
به نام برگ از درخت.

707
00:33:19,520 --> 00:33:21,800
>> بنابراین این فقط یک دسته است
از کلمات و تعاریف

708
00:33:21,800 --> 00:33:25,790
برای چیزی به نام یک درخت در کامپیوتر
علم، بسیار شبیه به یک شجره نامه.

709
00:33:25,790 --> 00:33:28,770
اما برداشت رویایی وجود دارد
درختان، که یکی از آنها

710
00:33:28,770 --> 00:33:30,780
است یک درخت جستجوی دودویی نامیده می شود.

711
00:33:30,780 --> 00:33:34,380
و شما می توانید نوع کسی را دست انداختن
جدا چه این چیزی که.

712
00:33:34,380 --> 00:33:37,180
خوب، آن را دودویی به چه معنا؟

713
00:33:37,180 --> 00:33:41,455
کجا باینری از اینجا می آیند؟

714
00:33:41,455 --> 00:33:41,955
متاسف؟

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
آن را آنقدر هم یا نه.

717
00:33:47,210 --> 00:33:52,000
این بیشتر که هر یک از گره ها ندارد
بیش از دو فرزند، به عنوان ما اینجا را ببینید.

718
00:33:52,000 --> 00:33:54,990
به طور کلی، tree-- و
پدر و مادر و پدربزرگ و مادربزرگ خود را

719
00:33:54,990 --> 00:33:57,640
می توانید به عنوان بسیاری از بچه ها و یا
نوه به عنوان آنها در واقع می خواهم،

720
00:33:57,640 --> 00:34:00,820
و بنابراین به عنوان مثال ما سه
کودکان را که گره دست راست،

721
00:34:00,820 --> 00:34:05,480
اما در یک درخت دودویی، یک گره است
صفر، یک، یا دو بچه حداکثر.

722
00:34:05,480 --> 00:34:08,496
و ملک خوب است،
چرا که اگر آن را توسط دو پوش،

723
00:34:08,496 --> 00:34:10,620
ما قصد داریم قادر به
گرفتن یک پایگاه ورود به سیستم کمی دو

724
00:34:10,620 --> 00:34:11,975
عمل در جریان است در اینجا در نهایت!

725
00:34:11,975 --> 00:34:13,350
بنابراین ما باید چیزی لگاریتمی است.

726
00:34:13,350 --> 00:34:14,558
اما بیشتر که در یک لحظه.

727
00:34:14,558 --> 00:34:19,810
درخت جستجوی بدان معنی است که اعداد
مرتب به طوری که کودک چپ

728
00:34:19,810 --> 00:34:22,429
مقدار بیشتر از ریشه است.

729
00:34:22,429 --> 00:34:26,010
و فرزند راست آن است
بزرگتر از ریشه.

730
00:34:26,010 --> 00:34:29,290
به عبارت دیگر، اگر شما هر یک از
گره ها، حلقه ها در این تصویر،

731
00:34:29,290 --> 00:34:31,840
و به نظر می رسد در سمت چپ آن
کودک و فرزند راست آن،

732
00:34:31,840 --> 00:34:34,739
برای اولین بار باید کمتر از باشد،
دوم باید بیشتر از باشد.

733
00:34:34,739 --> 00:34:36,159
بنابراین سلامت عقل را بررسی کنید 55.

734
00:34:36,159 --> 00:34:37,780
این کودک باقی مانده 33 است.

735
00:34:37,780 --> 00:34:38,620
این کمتر از.

736
00:34:38,620 --> 00:34:40,929
55، فرزند راست آن 77 است.

737
00:34:40,929 --> 00:34:41,783
آن را بیشتر از.

738
00:34:41,783 --> 00:34:43,199
و این یک تعریف بازگشتی است.

739
00:34:43,199 --> 00:34:46,480
ما می تواند هر یک از آن را بررسی کنید
گره ها و همان الگوی نگه دارید.

740
00:34:46,480 --> 00:34:49,389
>> پس چه خوب است در یک
درخت جستجوی دودویی است،

741
00:34:49,389 --> 00:34:52,204
که، ما می توانیم آن را پیاده سازی
با یک ساختار، فقط این را دوست.

742
00:34:52,204 --> 00:34:54,620
و حتی اگر ما در حال پرتاب
بسیاری از ساختارهای خود را،

743
00:34:54,620 --> 00:34:56,560
آنها تا حدودی هستید
بصری اکنون امیدوارم.

744
00:34:56,560 --> 00:35:00,570
نحو است که هنوز هم محرمانه برای مطمئن،
اما محتویات یک گره در این

745
00:35:00,570 --> 00:35:02,786
context-- و ما را حفظ
با استفاده از گره کلمه،

746
00:35:02,786 --> 00:35:04,910
آیا آن یک مستطیل است
بر روی صفحه نمایش و یا یک دایره،

747
00:35:04,910 --> 00:35:08,970
این فقط برخی از ظرف های عمومی است،
در این مورد یک درخت، مثل یک

748
00:35:08,970 --> 00:35:11,780
ما دیدیم، ما نیاز به یک عدد صحیح
در هر یک از گره

749
00:35:11,780 --> 00:35:15,460
و پس از آن من نیاز به دو اشاره گر اشاره
به فرزند چپ و فرزند راست،

750
00:35:15,460 --> 00:35:16,590
به ترتیب.

751
00:35:16,590 --> 00:35:20,730
به طوری که ما چگونه ممکن است
پیاده سازی است که در یک ساختار.

752
00:35:20,730 --> 00:35:22,315
و چگونه ممکن است آن را در کد پیاده سازی؟

753
00:35:22,315 --> 00:35:26,730
خوب، اجازه دهید یک سریع
در این مثال کوچک است.

754
00:35:26,730 --> 00:35:29,820
آن را کاربردی نیست، اما من
کپی و جا به جا که ساختار.

755
00:35:29,820 --> 00:35:33,510
و اگر تابع من برای یک فایل باینری
درخت جستجوی نامیده می شود جستجو،

756
00:35:33,510 --> 00:35:36,980
و این طول می کشد دو استدلال،
عدد n و یک اشاره گر

757
00:35:36,980 --> 00:35:41,400
به یک گره، به طوری که یک اشاره گر به درخت
و یا یک اشاره گر به ریشه یک درخت،

758
00:35:41,400 --> 00:35:43,482
چگونه می توانم در مورد جستجو برای N برود؟

759
00:35:43,482 --> 00:35:45,440
خب، اول، چون من
خرید و فروش با اشاره گر،

760
00:35:45,440 --> 00:35:46,750
من قصد دارم به انجام یک بررسی سلامت عقل.

761
00:35:46,750 --> 00:35:54,279
اگر برابر درخت برابر تهی، N است
در این درخت یا نه در این درخت؟

762
00:35:54,279 --> 00:35:55,070
این نمی تواند، درست است؟

763
00:35:55,070 --> 00:35:56,870
اگر من در گذشته های پوچ هستم،
هیچ چیز وجود دارد وجود دارد.

764
00:35:56,870 --> 00:35:59,230
من نیز ممکن است فقط
کورکورانه می گویند بازگشت نادرست است.

765
00:35:59,230 --> 00:36:04,050
اگر شما به من چیزی بدهد، من قطعا می تواند
پیدا کردن هر N. شماره پس چه چیز دیگری ممکن است من

766
00:36:04,050 --> 00:36:04,750
در حال حاضر بررسی؟

767
00:36:04,750 --> 00:36:12,830
من قصد دارم به خوبی دیگری اگر N است
کمتر از آنچه در گره درخت

768
00:36:12,830 --> 00:36:16,300
که من تحویل داده شده است که ارزش N.

769
00:36:16,300 --> 00:36:20,270
به عبارت دیگر، اگر تعداد من
به دنبال، N، کمتر از گره است

770
00:36:20,270 --> 00:36:21,340
که من به دنبال در.

771
00:36:21,340 --> 00:36:23,190
و گره من به دنبال
در است که به نام درخت،

772
00:36:23,190 --> 00:36:26,370
و به یاد از مثال قبلی
به ارزش در یک اشاره گر،

773
00:36:26,370 --> 00:36:28,310
من با استفاده از فلش نماد.

774
00:36:28,310 --> 00:36:35,960
بنابراین اگر N کمتر از درخت جهت دار است
N، من می خواهم به مفهومی به سمت چپ.

775
00:36:35,960 --> 00:36:38,590
چگونه می توانم بیان جستجوی سمت چپ؟

776
00:36:38,590 --> 00:36:41,560
برای روشن باشد، در صورتی که این
تصویر در سوال،

777
00:36:41,560 --> 00:36:44,612
و من تصویب شده است که بالاترین
فلش است که با اشاره به پایین.

778
00:36:44,612 --> 00:36:45,570
که اشاره گر درخت من است.

779
00:36:45,570 --> 00:36:48,060
من اشاره در ریشه درخت.

780
00:36:48,060 --> 00:36:52,100
و من به دنبال می گویند، برای
تعداد 44، خودسرانه.

781
00:36:52,100 --> 00:36:55,300
44 یا کمتر از
بیشتر از 55 بدیهی است؟

782
00:36:55,300 --> 00:36:56,360
پس از آن کمتر از.

783
00:36:56,360 --> 00:36:58,760
و بنابراین این اگر شرایط اعمال می شود.

784
00:36:58,760 --> 00:37:03,981
بنابراین مفهومی، چه چیزی می خواهید من
جستجو در کنار اگر من به دنبال 44؟

785
00:37:03,981 --> 00:37:04,480
آره؟

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> دقیقا، من می خواهم
جستجو در فرزند چپ

788
00:37:11,100 --> 00:37:12,789
و یا زیر درخت سمت چپ این تصویر است.

789
00:37:12,789 --> 00:37:14,830
و در واقع، به من اجازه دهید از طریق
تصویر پایین در اینجا

790
00:37:14,830 --> 00:37:17,770
برای فقط یک لحظه، از
من می توانم این خراش نیست.

791
00:37:17,770 --> 00:37:21,150
اگر من در اینجا شروع در 55، و
من می دانم که ارزش 44

792
00:37:21,150 --> 00:37:23,180
من به دنبال این است که
در سمت چپ، آن نوع

793
00:37:23,180 --> 00:37:26,010
مانند پاره شدن دفترچه تلفن در
نیم یا پاره شدن درخت در نیم.

794
00:37:26,010 --> 00:37:29,660
من دیگر در مورد مراقبت
این نیمه تمام از درخت است.

795
00:37:29,660 --> 00:37:33,270
و در عین حال، جالب، از نظر
ساختار، این چیزی بیش از اینجا که

796
00:37:33,270 --> 00:37:36,682
شروع می شود با 33، که خود را
یک درخت جستجوی دودویی است.

797
00:37:36,682 --> 00:37:39,890
گفتم کلمه بازگشتی قبل به دلیل
در واقع این یک ساختار داده است که

798
00:37:39,890 --> 00:37:41,707
توسط تعریف بازگشتی است.

799
00:37:41,707 --> 00:37:44,540
شما ممکن است یک درخت که این دارند
بزرگ است، اما هر یک از فرزندان خود

800
00:37:44,540 --> 00:37:46,870
نشان دهنده یک درخت فقط یک کمی کوچکتر است.

801
00:37:46,870 --> 00:37:50,910
به جای آن که پدر بزرگ
یا مادر بزرگ، در حال حاضر آن را فقط به مامان

802
00:37:50,910 --> 00:37:54,300
or-- من نمی توانم مادر نمی گویند
یا پدر، خواهد بود که عجیب و غریب.

803
00:37:54,300 --> 00:37:59,000
به جای دو فرزند وجود دارد
می خواهم برادر و خواهر و برادر است.

804
00:37:59,000 --> 00:38:01,120
نسل جدیدی از شجره نامه.

805
00:38:01,120 --> 00:38:02,900
اما ساختار، آن همان ایده است.

806
00:38:02,900 --> 00:38:06,790
و معلوم است من یک تابع دارند
که با من می توانم یک جستجوی دودویی جستجو

807
00:38:06,790 --> 00:38:07,290
درخت.

808
00:38:07,290 --> 00:38:08,680
آن را به نام جستجو.

809
00:38:08,680 --> 00:38:17,870
من برای N در درخت فلش سمت چپ جستجو
دیگری اگر N بزرگتر از ارزش است

810
00:38:17,870 --> 00:38:18,870
که من در حال حاضر در هستم.

811
00:38:18,870 --> 00:38:20,800
55 در داستان یک لحظه پیش.

812
00:38:20,800 --> 00:38:23,780
من یک تابع به نام
جستجو است که من فقط می توانید

813
00:38:23,780 --> 00:38:29,660
تصویب N و به صورت بازگشتی جستجو
زیر درخت و فقط بازگشت

814
00:38:29,660 --> 00:38:30,620
هر چه که پاسخ.

815
00:38:30,620 --> 00:38:33,530
دیگری من مقداری در مورد پایه نهایی کردم اینجا.

816
00:38:33,530 --> 00:38:35,310
>> مورد نهایی چیست؟

817
00:38:35,310 --> 00:38:36,570
درخت هم تهی.

818
00:38:36,570 --> 00:38:39,980
ارزش من هم به دنبال است
کمتر از آن و یا بیشتر از

819
00:38:39,980 --> 00:38:42,610
و یا برابر با آن.

820
00:38:42,610 --> 00:38:44,750
و من می توانم بگویم برابر
برابر است، اما منطقی آن

821
00:38:44,750 --> 00:38:46,500
معادل فقط گفت دیگری در اینجا.

822
00:38:46,500 --> 00:38:49,150
بنابراین درست چیزی است که چگونه پیدا کنم.

823
00:38:49,150 --> 00:38:51,710
بنابراین امیدوارم این است
حتی به عنوان مثال قانع کننده تر

824
00:38:51,710 --> 00:38:54,900
از تابع سیگما احمقانه
ما چند سخنرانی و عقب،

825
00:38:54,900 --> 00:38:58,360
که در آن بود به همان اندازه آسان به استفاده از یک حلقه
به تعداد بالا تمام اعداد از یک

826
00:38:58,360 --> 00:39:02,390
به N. در اینجا با یک ساختار داده
که خود را به صورت بازگشتی است

827
00:39:02,390 --> 00:39:07,050
تعریف شده و به صورت بازگشتی کشیده شده است، در حال حاضر ما
از این توانایی برای بیان خود

828
00:39:07,050 --> 00:39:09,780
در کد است که خود را بازگشتی است.

829
00:39:09,780 --> 00:39:12,580
بنابراین این همان کد دقیق در اینجا است.

830
00:39:12,580 --> 00:39:14,400
>> پس چه مشکلات دیگر می تواند ما را حل کند؟

831
00:39:14,400 --> 00:39:18,160
بنابراین یک گام سریع به دور از
درختان برای فقط یک لحظه.

832
00:39:18,160 --> 00:39:20,130
در اینجا است، می گویند، پرچم آلمان است.

833
00:39:20,130 --> 00:39:22,020
و به وضوح وجود دارد
الگوی این پرچم.

834
00:39:22,020 --> 00:39:23,811
و بسیاری از وجود دارد
پرچم ها در جهان است که

835
00:39:23,811 --> 00:39:27,560
عنوان ساده به عنوان این در
رنگ ها و الگوهای خود را.

836
00:39:27,560 --> 00:39:31,930
اما فرض کنید که این به عنوان یک ذخیره شده
.GIF، یا JPEG، یا بیت مپ، و یا یک پینگ،

837
00:39:31,930 --> 00:39:34,240
هر فرمت فایل گرافیکی
که با آن شما آشنا هستید،

838
00:39:34,240 --> 00:39:36,460
که برخی از آنها ما
بازی با در PSET4.

839
00:39:36,460 --> 00:39:41,550
این به نظر می رسد ارزشمند به ذخیره نمی
پیکسل سیاه و سفید، سیاه و سفید پیکسل، پیکسل سیاه و سفید،

840
00:39:41,550 --> 00:39:44,790
نقطه، نقطه، نقطه، یک دسته کامل از
پیکسل سیاه و سفید برای scanline اول،

841
00:39:44,790 --> 00:39:47,430
و یا ردیف، و سپس یک دسته کامل از
همان، سپس یک دسته کامل

842
00:39:47,430 --> 00:39:49,530
از همان، و سپس یک
تمام دسته از پیکسل های قرمز،

843
00:39:49,530 --> 00:39:53,020
پیکسل های قرمز، پیکسل های قرمز، پس از آن یک کل
دسته از پیکسل زرد، زرد، درست است؟

844
00:39:53,020 --> 00:39:55,050
>> چنین ناکارآمدی در اینجا وجود دارد.

845
00:39:55,050 --> 00:39:59,040
چگونه می خواهید به طور مستقیم
فشرده سازی پرچم آلمان

846
00:39:59,040 --> 00:40:01,320
اگر اجرای آن به عنوان یک فایل؟

847
00:40:01,320 --> 00:40:04,940
مانند چه اطلاعاتی را می ما نمی
زحمت ذخیره سازی بر روی دیسک به منظور

848
00:40:04,940 --> 00:40:08,040
کاهش اندازه پرونده ما را از مثل
یک مگابایت به یک کیلوبایت، چیزی

849
00:40:08,040 --> 00:40:09,430
کوچکتر؟

850
00:40:09,430 --> 00:40:13,130
در آن نهفته است افزونگی
در اینجا روشن می شود؟

851
00:40:13,130 --> 00:40:13,880
چه چیزی می تواند شما انجام دهد؟

852
00:40:13,880 --> 00:40:14,380
آره؟

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
دقیقا.

855
00:40:21,970 --> 00:40:24,550
چرا به جای به یاد داشته باشید
رنگ هر پیکسل رفو

856
00:40:24,550 --> 00:40:28,200
درست مثل شما در حال انجام در PSET4
با فرمت فایل بیت مپ،

857
00:40:28,200 --> 00:40:32,060
چرا شما فقط نشان دهنده
ستون سمت چپ از پیکسل ها، به عنوان مثال

858
00:40:32,060 --> 00:40:35,370
یک دسته از پیکسل سیاه و سفید، یک دسته
قرمز، و یک دسته از زرد،

859
00:40:35,370 --> 00:40:39,210
و پس از آن فقط به نحوی رمز
ایده تکرار این 100 بار

860
00:40:39,210 --> 00:40:41,020
و یا تکرار این 1،000 بار؟

861
00:40:41,020 --> 00:40:43,430
که در آن 100 یا 1،000 است
فقط یک عدد صحیح است، بنابراین شما

862
00:40:43,430 --> 00:40:47,290
می توانید دور با فقط یک عدد تک
به جای صدها یا هزاران نفر

863
00:40:47,290 --> 00:40:48,270
پیکسل های اضافی.

864
00:40:48,270 --> 00:40:50,990
و در واقع، این که چگونه ما
می تواند پرچم آلمان فشرده سازی.

865
00:40:50,990 --> 00:40:51,490
و

866
00:40:51,490 --> 00:40:53,470
در حال حاضر حدود پرچم فرانسه چه؟

867
00:40:53,470 --> 00:40:58,930
و کمی نوعی از
ورزش ذهنی، که پرچم

868
00:40:58,930 --> 00:41:01,040
می توان بیشتر بر روی دیسک فشرده؟

869
00:41:01,040 --> 00:41:05,720
پرچم آلمان یا فرانسه
پرچم، اگر ما این رویکرد؟

870
00:41:05,720 --> 00:41:08,490
پرچم آلمان، به دلیل وجود دارد
افزونگی افقی است.

871
00:41:08,490 --> 00:41:12,190
و با طراحی، بسیاری از فایل های گرافیکی
فرمت در واقع به عنوان خطوط اسکن کار

872
00:41:12,190 --> 00:41:12,830
به صورت افقی.

873
00:41:12,830 --> 00:41:14,674
آنها می توانند کار
به صورت عمودی، فقط انسانیت

874
00:41:14,674 --> 00:41:17,090
سال پیش تصمیم گرفت که ما
به طور کلی از همه چیز ردیف فکر می کنم

875
00:41:17,090 --> 00:41:18,880
ردیف به جای ستون به ستون.

876
00:41:18,880 --> 00:41:20,820
پس در واقع اگر شما
به در فایل نگاه کنید

877
00:41:20,820 --> 00:41:24,670
اندازه یک پرچم آلمان و فرانسه
پرچم، تا زمانی که قطعنامه است

878
00:41:24,670 --> 00:41:27,530
در همین حال، هم عرض
و ارتفاع، این یکی

879
00:41:27,530 --> 00:41:31,580
در اینجا رفتن به بزرگتر، چرا که شما
باید به خودتان سه بار تکرار کنید.

880
00:41:31,580 --> 00:41:35,570
شما باید برای مشخص آبی، تکرار
خود را، سفید، خودتان را تکرار، قرمز،

881
00:41:35,570 --> 00:41:36,740
تکرار خودتان.

882
00:41:36,740 --> 00:41:39,000
شما نمی توانید فقط همه به
راه به سمت راست.

883
00:41:39,000 --> 00:41:41,200
و از سوی دیگر، به
روشن فشرده سازی

884
00:41:41,200 --> 00:41:43,910
در همه جا، اگر این
چهار فریم از یک video-- شما

885
00:41:43,910 --> 00:41:45,890
ممکن است به یاد آورید که یک فیلم
یا ویدئو است به طور کلی

886
00:41:45,890 --> 00:41:47,286
مانند 29 یا 30 فریم در ثانیه.

887
00:41:47,286 --> 00:41:50,410
آن را مانند یک کتاب تلنگر کوچک که در آن شما
فقط ببینید تصویر، تصویر، تصویر، تصویر،

888
00:41:50,410 --> 00:41:54,410
تصویر فقط فوق العاده سریع پس از آن به نظر می رسد
بازیگران بر روی صفحه نمایش در حال حرکت.

889
00:41:54,410 --> 00:41:57,130
در اینجا یک زنبور عسل سرهم بندی کردن در است
بالای یک دسته از گل.

890
00:41:57,130 --> 00:41:59,790
و هر چند ممکن است آن را از
سخت است برای دیدن در نگاه اول،

891
00:41:59,790 --> 00:42:04,020
تنها چیزی که در حال حرکت در
این فیلم زنبور عسل است.

892
00:42:04,020 --> 00:42:06,880
>> چه گنگ در مورد ذخیره سازی است
ویدئو غیر فشرده.

893
00:42:06,880 --> 00:42:11,420
این نوع از زباله برای ذخیره ویدیو
به عنوان چهار عکس تقریبا یکسان است که

894
00:42:11,420 --> 00:42:13,670
متفاوت فقط تا آنجا که در آن زنبور عسل است.

895
00:42:13,670 --> 00:42:16,280
شما می توانید دور انداختن ترین
از آن اطلاعات

896
00:42:16,280 --> 00:42:20,190
و تنها به یاد داشته باشید، برای مثال،
قاب اول و آخر قاب،

897
00:42:20,190 --> 00:42:22,180
فریم های کلیدی اگر شما
تا به حال شنیده کلمه،

898
00:42:22,180 --> 00:42:24,337
و فقط در فروشگاه
وسط که در آن زنبور عسل است.

899
00:42:24,337 --> 00:42:26,170
و شما لازم نیست که
ذخیره تمام از صورتی،

900
00:42:26,170 --> 00:42:28,330
و آبی، و
ارزش سبز است.

901
00:42:28,330 --> 00:42:31,200
پس این است که تنها می گویند که
فشرده سازی است در همه جا.

902
00:42:31,200 --> 00:42:34,900
این روش اغلب با استفاده از این ما
و یا برای این روز داده شود.

903
00:42:34,900 --> 00:42:38,750
>> اما چگونه می توانم متن شما فشرده سازی؟

904
00:42:38,750 --> 00:42:40,450
نظر شما در مورد فشرده سازی متن بروید؟

905
00:42:40,450 --> 00:42:45,410
خوب، هر یک از شخصیت در
ASCII یک بایت، یا هشت بیت است.

906
00:42:45,410 --> 00:42:47,360
و این نوع از گنگ، درست است؟

907
00:42:47,360 --> 00:42:51,160
از آنجا که شما احتمالا نوع A
و E و I و O و تو خیلی

908
00:42:51,160 --> 00:42:55,270
بیشتر از مثل W و یا Q و یا Z،
بسته به زبان است که در آن

909
00:42:55,270 --> 00:42:56,610
شما در حال نوشتن قطعا.

910
00:42:56,610 --> 00:42:59,600
و چرا ما با استفاده از
هشت بیت برای هر حرف،

911
00:42:59,600 --> 00:43:02,040
از جمله دست کم
نامه محبوب، درست است؟

912
00:43:02,040 --> 00:43:05,300
چرا بیت کمتر برای استفاده از
حروف فوق العاده محبوب،

913
00:43:05,300 --> 00:43:07,760
مانند E، چیزهایی که شما حدس می زنم
برای اولین بار در چرخ از فورچون،

914
00:43:07,760 --> 00:43:10,450
و استفاده از بیت های بیشتری برای
حروف کمتر محبوب؟

915
00:43:10,450 --> 00:43:10,950
واسه چی؟

916
00:43:10,950 --> 00:43:13,130
از آنجا که ما فقط رفتن به
استفاده از آنها کمتر.

917
00:43:13,130 --> 00:43:15,838
>> خب، معلوم است که وجود دارد
تلاش برای انجام این کار بوده است.

918
00:43:15,838 --> 00:43:18,630
و اگر شما از درجه یاد
مدرسه یا دبیرستان، کد مورس.

919
00:43:18,630 --> 00:43:20,400
کد مورس است نقطه
و خط تیره است که می تواند

920
00:43:20,400 --> 00:43:24,270
منتقل شده در طول یک سیم به عنوان
برای تلفن های موبایل و یا سیگنال از نوعی.

921
00:43:24,270 --> 00:43:25,930
اما کد مورس است فوق العاده تمیز.

922
00:43:25,930 --> 00:43:29,010
این نوع از سیستم دوتایی در
که شما باید نقطه و یا خط تیره.

923
00:43:29,010 --> 00:43:30,977
اما اگر می بینید، برای مثال، دو نقطه.

924
00:43:30,977 --> 00:43:33,810
و یا اگر شما فکر می کنم به اپراتور
که مانند بوق، بوق، بوق می رود،

925
00:43:33,810 --> 00:43:36,760
بوق، هدف قرار دادن یک ماشه کوچک
که یک سیگنال،

926
00:43:36,760 --> 00:43:40,360
اگر شما، دریافت کننده، دو دریافت
نقطه، شما چه پیامی دریافت کرده اند؟

927
00:43:40,360 --> 00:43:43,490
کاملا خودسرانه.

928
00:43:43,490 --> 00:43:44,450
>> من؟

929
00:43:44,450 --> 00:43:45,060
من؟

930
00:43:45,060 --> 00:43:47,500
و یا چه about-- یا من؟

931
00:43:47,500 --> 00:43:49,570
شاید این فقط دو حق E بود؟

932
00:43:49,570 --> 00:43:52,480
پس این مشکل وجود دارد
از decodability با مورس

933
00:43:52,480 --> 00:43:54,890
کد، به موجب آن، مگر اینکه
شخص ارسال پیام شما

934
00:43:54,890 --> 00:43:59,510
در واقع مکث بنابراین شما می توانید از مرتب سازی بر اساس
دیدن و یا شنیدن شکاف بین حروف،

935
00:43:59,510 --> 00:44:02,990
کافی نیست فقط به
ارسال یک جریان از صفر و آنهایی که،

936
00:44:02,990 --> 00:44:05,610
و یا نقطه و خط تیره،
چرا که ابهام وجود دارد.

937
00:44:05,610 --> 00:44:08,640
E یک نقطه است، بنابراین اگر شما
دو نقطه دیدن و یا شنیدن دو نقطه،

938
00:44:08,640 --> 00:44:11,254
شاید آن را دو E یا شاید آن را یک I. است

939
00:44:11,254 --> 00:44:13,670
بنابراین ما نیاز به یک سیستم است که یک
کمی باهوش تر از آن.

940
00:44:13,670 --> 00:44:16,851
بنابراین مردی به نام سال هافمن
پیش تا دقیقا با این آمد.

941
00:44:16,851 --> 00:44:18,600
بنابراین ما فقط رفتن
به یک نگاه سریع

942
00:44:18,600 --> 00:44:20,114
چگونه درختان وابسته به این است.

943
00:44:20,114 --> 00:44:22,530
فرض کنید که این چند است
پیام احمقانه شما می خواهید برای ارسال،

944
00:44:22,530 --> 00:44:26,342
متشکل از فقط A، B، C است D'بازدید کنندگان و E،
اما بسیاری از افزونگی در اینجا وجود دارد.

945
00:44:26,342 --> 00:44:27,550
آن را به معنای انگلیسی.

946
00:44:27,550 --> 00:44:28,341
آن رمزگذاری شده است.

947
00:44:28,341 --> 00:44:30,540
این فقط یک پیام احمقانه است
با تعداد زیادی از تکرار.

948
00:44:30,540 --> 00:44:34,010
بنابراین اگر شما در واقع به حساب همه
الف، ب، ج، D'S، و E است، در اینجا

949
00:44:34,010 --> 00:44:34,890
فرکانس.

950
00:44:34,890 --> 00:44:37,800
20 درصد از نامه ها
الف، 45٪ از حروف

951
00:44:37,800 --> 00:44:39,660
می E، و سه فرکانس دیگر است.

952
00:44:39,660 --> 00:44:41,960
ما شمارش تا به صورت دستی
و فقط به ریاضی.

953
00:44:41,960 --> 00:44:44,579
>> پس از آن معلوم است که
هافمن، چند وقت پیش،

954
00:44:44,579 --> 00:44:46,620
متوجه شدم که، شما می دانید
چه، اگر شروع به ساختمان من

955
00:44:46,620 --> 00:44:51,172
یک درخت، و یا جنگل از درختان، اگر شما خواهد شد،
به شرح زیر، من می توانم زیر را انجام دهید.

956
00:44:51,172 --> 00:44:53,880
من از رفتن به یک گره به هر
از نامه ها که من در مورد مراقبت

957
00:44:53,880 --> 00:44:55,530
و من قصد دارم برای ذخیره
در داخل آن گره

958
00:44:55,530 --> 00:44:58,610
فرکانس به عنوان یک نقطه شناور
ارزش، یا شما می توانید آن را به یک N استفاده کنید، بیش از حد،

959
00:44:58,610 --> 00:45:00,210
اما ما فقط در اینجا استفاده از یک شناور.

960
00:45:00,210 --> 00:45:03,100
و الگوریتم است که
او پیشنهاد این است که شما

961
00:45:03,100 --> 00:45:07,210
این جنگل از تک گره
درختان، درختان فوق العاده کوتاه،

962
00:45:07,210 --> 00:45:11,920
و شما شروع به اتصال آنها را با
گروه های جدید، پدر و مادر جدید، اگر شما خواهد شد.

963
00:45:11,920 --> 00:45:16,150
و شما این کار را با انتخاب
دو کوچکترین فرکانس در یک زمان.

964
00:45:16,150 --> 00:45:18,110
بنابراین من 10٪ و 10٪ و جو در زمان.

965
00:45:18,110 --> 00:45:19,090
من یک گره جدید است.

966
00:45:19,090 --> 00:45:20,910
و من پاسخ به گره جدید 20٪.

967
00:45:20,910 --> 00:45:22,750
>> که دو گره با هم ترکیب کنیم؟

968
00:45:22,750 --> 00:45:23,810
این کمی مبهم است.

969
00:45:23,810 --> 00:45:26,643
بنابراین برخی از موارد گوشه ای به وجود
نظر است، اما به نگه داشتن چیزهای زیبا،

970
00:45:26,643 --> 00:45:29,300
من قصد دارم به را انتخاب کنید 20٪ -
من در حال حاضر کودکان را نادیده گرفت.

971
00:45:29,300 --> 00:45:33,640
من قصد دارم به را انتخاب کنید 20٪ و
15٪ و دو لبه جدید قرعه کشی.

972
00:45:33,640 --> 00:45:35,624
و در حال حاضر که دو گره
من منطقی ترکیب؟

973
00:45:35,624 --> 00:45:38,540
چشم پوشی از همه کودکان، همه
نوه، فقط در ریشه نگاه

974
00:45:38,540 --> 00:45:39,070
اکنون.

975
00:45:39,070 --> 00:45:42,220
که دو گره با هم کراوات من؟

976
00:45:42,220 --> 00:45:44,530
نقطه دو و 0.35.

977
00:45:44,530 --> 00:45:45,890
بنابراین اجازه دهید من در قرعه کشی دو لبه است.

978
00:45:45,890 --> 00:45:47,570
و پس از آن من تنها یک سمت چپ است.

979
00:45:47,570 --> 00:45:48,650
بنابراین در اینجا یک درخت.

980
00:45:48,650 --> 00:45:51,160
و آن را به عمد کشیده شده است
به نگاه نوع زیبا،

981
00:45:51,160 --> 00:45:55,870
اما توجه کنید که لبه دارند
همچنین صفر و یک برچسب شده است.

982
00:45:55,870 --> 00:45:59,510
پس همه از سمت چپ لبه صفر هستند
خودسرانه، اما به طور مداوم.

983
00:45:59,510 --> 00:46:01,170
تمام لبه های راست آنهایی هستند.

984
00:46:01,170 --> 00:46:05,070
>> و بنابراین، آنچه هافمن پیشنهاد شده است،
اگر شما می خواهید برای نشان دادن یک B،

985
00:46:05,070 --> 00:46:10,080
به جای نشان دهنده تعداد 66 عنوان
اسکی است که هشت بیت کل،

986
00:46:10,080 --> 00:46:13,360
شما می دانید چه، فروشگاه فقط
الگوی صفر، صفر، صفر،

987
00:46:13,360 --> 00:46:17,030
صفر، چرا که مسیر را
از درخت من، درخت آقای هافمن،

988
00:46:17,030 --> 00:46:18,600
به برگ از ریشه.

989
00:46:18,600 --> 00:46:20,970
اگر شما می خواهید برای ذخیره یک
E، در مقابل، نمی

990
00:46:20,970 --> 00:46:26,290
ارسال هشت بیت است که نشان دهنده E.
در عوض، ارسال چه الگوی بیت؟

991
00:46:26,290 --> 00:46:26,890
یکی.

992
00:46:26,890 --> 00:46:30,410
و چه خوب در مورد این است
که E نامه محبوب ترین است،

993
00:46:30,410 --> 00:46:32,340
و شما با استفاده از
کوتاه ترین کد برای آن است.

994
00:46:32,340 --> 00:46:34,090
بعدی محبوب ترین
نامه به نظر می رسد مانند آن

995
00:46:34,090 --> 00:46:37,380
A. بود و چگونه بسیاری از بیت
او با استفاده از پیشنهاد که؟

996
00:46:37,380 --> 00:46:38,270
صفر، یک.

997
00:46:38,270 --> 00:46:41,060
>> و چون آن را اجرا
عنوان این درخت، در حال حاضر

998
00:46:41,060 --> 00:46:43,350
اجازه دهید من وجود دارد تصریح
هیچ ابهامی در مورس

999
00:46:43,350 --> 00:46:46,090
کد، چرا که همه از
نامه شما در مورد مراقبت

1000
00:46:46,090 --> 00:46:48,780
در پایان این گوشه می باشد.

1001
00:46:48,780 --> 00:46:50,580
به طوری که فقط یک
استفاده از یک درخت.

1002
00:46:50,580 --> 00:46:52,538
این is-- و من موج
دست من در این که چگونه شما

1003
00:46:52,538 --> 00:46:55,570
ممکن است این به عنوان یک ساختار C پیاده سازی.

1004
00:46:55,570 --> 00:46:58,260
ما فقط نیاز به ترکیب
یک نماد، مانند یک کاراکتر،

1005
00:46:58,260 --> 00:46:59,910
و فرکانس در چپ و راست.

1006
00:46:59,910 --> 00:47:02,510
اما اجازه دهید در دو نگاه
نمونه نهایی است که شما

1007
00:47:02,510 --> 00:47:06,070
گرفتن کاملا آشنا با پس
مسابقه صفر در مجموعه ای مشکل پنج.

1008
00:47:06,070 --> 00:47:09,210
>> بنابراین ساختار داده ها وجود دارد
شناخته شده به عنوان یک جدول هش.

1009
00:47:09,210 --> 00:47:12,247
و یک جدول هش نوع
خنک در آن است که سطل.

1010
00:47:12,247 --> 00:47:14,830
و فرض چهار سطل وجود دارد
در اینجا، فقط چهار فضاهای خالی.

1011
00:47:14,830 --> 00:47:20,830
در اینجا یک دسته کارت، و در اینجا است
باشگاه، بیل زدن، باشگاه، الماس، باشگاه،

1012
00:47:20,830 --> 00:47:25,960
الماس، باشگاه، الماس،
clubs-- این است که به صورت تصادفی.

1013
00:47:25,960 --> 00:47:30,330
قلب، hearts-- بنابراین من
bucketizing همه از ورودی است.

1014
00:47:30,330 --> 00:47:32,430
و یک جدول هش نیازهای
به در ورودی خود را نگاه کنید،

1015
00:47:32,430 --> 00:47:34,850
و سپس آن را در یک خاص قرار
مشخصات، بر اساس آنچه می بینید.

1016
00:47:34,850 --> 00:47:35,600
این الگوریتم است.

1017
00:47:35,600 --> 00:47:37,980
و من با استفاده از فوق العاده
الگوریتم های بصری ساده است.

1018
00:47:37,980 --> 00:47:40,030
سخت ترین قسمت بود که
به خاطر سپردن آنچه در تصاویر بود.

1019
00:47:40,030 --> 00:47:41,590
و پس از آن چهار مجموع چیزها وجود دارد.

1020
00:47:41,590 --> 00:47:45,440
>> در حال حاضر پشته، در حال رشد بودند که
یک چیز طراحی عمدی در اینجا است.

1021
00:47:45,440 --> 00:47:46,540
اما چه چیز دیگری ممکن است انجام دهم؟

1022
00:47:46,540 --> 00:47:49,080
پس در واقع در اینجا ما یک
دسته از کتاب آزمون مدرسه قدیمی.

1023
00:47:49,080 --> 00:47:51,240
فرض کنید که یک دسته از
نام دانش آموزان در اینجا.

1024
00:47:51,240 --> 00:47:52,570
در اینجا یک جدول هش بزرگتر است.

1025
00:47:52,570 --> 00:47:54,867
به جای چهار سطل،
من، اجازه دهید بگویم 26.

1026
00:47:54,867 --> 00:47:57,950
و ما نمی به قرض 26
همه چیز از خارج [؟ آننبرگ؟]، به طوری که

1027
00:47:57,950 --> 00:48:00,289
در اینجا پنج است که نشان دهنده
A تا Z. و اگر من

1028
00:48:00,289 --> 00:48:03,580
یک دانش آموز که نام با یک شروع می شود را مشاهده کنید،
من قصد دارم به او و یا مسابقه او قرار داده است.

1029
00:48:03,580 --> 00:48:08,850
اگر کسی با C شروع می شود، بیش از وجود دارد،
A-- در واقع، نمی خواهم به انجام این کار.

1030
00:48:08,850 --> 00:48:10,060
B می رود بیش از اینجا.

1031
00:48:10,060 --> 00:48:13,390
بنابراین من A و B و C و
در حال حاضر اینجا دانش آموز دیگری است.

1032
00:48:13,390 --> 00:48:16,212
اما اگر این جدول هش
اجرا با یک آرایه،

1033
00:48:16,212 --> 00:48:17,920
من از پیچ نوع
در این نقطه، درست است؟

1034
00:48:17,920 --> 00:48:19,510
من از نوع نیاز به قرار دادن این جایی.

1035
00:48:19,510 --> 00:48:24,380
>> بنابراین یکی از راه حل من می توانم این است، همه
درست است، یک مشغول است، B مشغول است، C مشغول است.

1036
00:48:24,380 --> 00:48:28,880
من قصد دارم به او را در D. بنابراین در
اول، من با دسترسی تصادفی فوری

1037
00:48:28,880 --> 00:48:31,064
به هر یک از سطل برای دانش آموزان است.

1038
00:48:31,064 --> 00:48:33,230
اما در حال حاضر این نوع از محول
به چیزی خطی،

1039
00:48:33,230 --> 00:48:36,750
چرا که اگر من می خواهم به جستجو برای کسی
نام و نام خانوادگی که شروع می شود با، من اینجا چک کنید.

1040
00:48:36,750 --> 00:48:38,854
اما اگر این است که A نمی
دانش آموز من به دنبال،

1041
00:48:38,854 --> 00:48:41,520
من نوعی باید شروع به چک
سطل، زیرا آنچه من

1042
00:48:41,520 --> 00:48:44,530
مرتب کردن بر اساس خطی بود
بررسی ساختار داده ها.

1043
00:48:44,530 --> 00:48:47,710
یک راه احمقانه گفتن فقط نگاه
برای اولین باز در دسترس است،

1044
00:48:47,710 --> 00:48:51,850
قرار داده و به عنوان یک طرح B، پس به صحبت می کنند،
و یا طرح D در این مورد، ارزش

1045
00:48:51,850 --> 00:48:53,340
در آن مکان به جای.

1046
00:48:53,340 --> 00:48:56,470
این فقط به طوری که اگر شما
26 مکان و دانش آموزان رو

1047
00:48:56,470 --> 00:49:00,600
با نام Q و یا Z، یا چیزی شبیه به
که، حداقل شما با استفاده از فضا.

1048
00:49:00,600 --> 00:49:03,140
>> اما ما در حال حاضر دیده تر
راه حل های هوشمندانه در اینجا، درست است؟

1049
00:49:03,140 --> 00:49:04,870
چه کار می کنید به جای
اگر شما یک برخورد؟

1050
00:49:04,870 --> 00:49:06,670
اگر دو نفر
نام A، آنچه را که

1051
00:49:06,670 --> 00:49:09,160
یک هوشمندانه تر و یا شده
راه حل بصری از

1052
00:49:09,160 --> 00:49:12,840
قرار دادن یک که در آن D قرار است به؟

1053
00:49:12,840 --> 00:49:14,810
چرا من فقط
خارج [؟ آننبرگ؟]،

1054
00:49:14,810 --> 00:49:19,960
مانند از malloc، گره دیگر، آن را
در اینجا، و سپس قرار دادن که یک دانش آموز است.

1055
00:49:19,960 --> 00:49:22,120
به طوری که من اساسا
نوعی از یک آرایه،

1056
00:49:22,120 --> 00:49:25,590
و یا شاید به زیبایی بیشتر به عنوان ما
شروع به دیدن یک لیست پیوندی.

1057
00:49:25,590 --> 00:49:29,520
>> و به این ترتیب یک جدول هش یک ساختار است
که می تواند فقط شبیه به این،

1058
00:49:29,520 --> 00:49:33,900
اما هوشمندانه تر، شما چیزی به نام
زنجیره جداگانه، به موجب آن یک جدول هش

1059
00:49:33,900 --> 00:49:38,340
کاملا به سادگی یک آرایه است، هر یک از
که عناصر یک عدد نیست،

1060
00:49:38,340 --> 00:49:40,470
به خودی خود یک لیست پیوندی است.

1061
00:49:40,470 --> 00:49:45,080
به طوری که شما دسترسی فوق العاده سریع
تصمیم گیری که در آن به هش ارزش خود را به.

1062
00:49:45,080 --> 00:49:48,059
بسیار شبیه با مثال کارت،
من تصمیم فوق العاده سریع ساخته شده است.

1063
00:49:48,059 --> 00:49:49,600
قلب در اینجا می رود، الماس در اینجا می رود.

1064
00:49:49,600 --> 00:49:52,180
در اینجا همان، A در اینجا می رود،
D در اینجا می رود، B در اینجا می رود.

1065
00:49:52,180 --> 00:49:55,740
بنابراین فوق العاده سریع نگاه یو پی اس، و اگر
شما اتفاق می افتد به اجرا را به یک مورد

1066
00:49:55,740 --> 00:49:59,429
برخورد که در آن شما را کردم، دو
مردم با همین نام، و سپس

1067
00:49:59,429 --> 00:50:00,970
شما فقط شروع به ارتباط آنها با هم.

1068
00:50:00,970 --> 00:50:03,900
و شاید شما آنها را طبقه بندی شده اند حفظ
بر اساس حروف الفبا، شاید شما نمی کنند.

1069
00:50:03,900 --> 00:50:05,900
اما حداقل در حال حاضر ما پویایی است.

1070
00:50:05,900 --> 00:50:10,250
بنابراین در یک طرف ما فوق العاده سریع
زمان ثابت، و نوع زمان خطی

1071
00:50:10,250 --> 00:50:14,110
درگیر اگر این لیست های پیوندی
شروع به گرفتن یک کمی طولانی است.

1072
00:50:14,110 --> 00:50:16,880
>> بنابراین این نوع از احمقانه،
سال شوخی نخبه پیش.

1073
00:50:16,880 --> 00:50:19,590
در CS50 هک مراسم،
هنگامی که دانش آموزان بررسی در،

1074
00:50:19,590 --> 00:50:22,040
برخی TF یا CA هر سال
فکر می کند آن را خنده دار قرار داده تا

1075
00:50:22,040 --> 00:50:27,772
نشانه شبیه به این، که در آن فقط
معنی است که اگر نام خود را شروع می شود با A،

1076
00:50:27,772 --> 00:50:28,870
رفتن در این راه.

1077
00:50:28,870 --> 00:50:31,110
اگر نام شما شروع می شود
با B، به this-- OK،

1078
00:50:31,110 --> 00:50:33,290
این خنده دار است شاید بعدا در ترم.

1079
00:50:33,290 --> 00:50:36,420
اما یکی دیگر از وجود دارد
راه های انجام این، TOO.

1080
00:50:36,420 --> 00:50:37,410
بازگشت به که.

1081
00:50:37,410 --> 00:50:38,600
>> بنابراین این ساختار وجود دارد.

1082
00:50:38,600 --> 00:50:40,420
و این است که ما آخرین
ساختار برای امروز،

1083
00:50:40,420 --> 00:50:42,400
که چیزی به نام یک درخت پیشوندی است.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E، که برای برخی از دلیل کوتاه است
برای بازیابی، اما آن را به نام درخت.

1085
00:50:47,140 --> 00:50:51,389
بنابراین یک درخت پیشوندی دیگر جالب است
ملغمه ای از بسیاری از این ایده ها.

1086
00:50:51,389 --> 00:50:52,930
این یک درخت، که ما قبل از دیده ام.

1087
00:50:52,930 --> 00:50:54,180
این یک درخت جستجوی دودویی نیست.

1088
00:50:54,180 --> 00:50:58,410
این یک درخت با هر تعداد از کودکان،
اما هر یک از کودکان در یک درخت پیشوندی

1089
00:50:58,410 --> 00:51:00,090
یک آرایه است.

1090
00:51:00,090 --> 00:51:04,790
آرایه ای از اندازه، می گویند، 26 و یا شاید 27
اگر شما می خواهید برای پشتیبانی از نام hyphenated

1091
00:51:04,790 --> 00:51:06,790
و یا آپوستروف در نام مردم است.

1092
00:51:06,790 --> 00:51:08,280
>> و بنابراین این یک ساختار داده است.

1093
00:51:08,280 --> 00:51:10,290
و اگر شما از بالا نگاه
به پایین، مانند اگر شما

1094
00:51:10,290 --> 00:51:13,710
در گره بالا وجود دارد، M نگاه کنید،
با اشاره به سمت چپ چیز وجود دارد،

1095
00:51:13,710 --> 00:51:17,665
که سپس A، X، W، E، L، L. این است
فقط یک ساختار داده که خودسرانه

1096
00:51:17,665 --> 00:51:19,120
ذخیره سازی نام افراد.

1097
00:51:19,120 --> 00:51:25,720
و ماکسول است تنها با زیر ذخیره می شود
یک مسیر از آرایه به آرایه به آرایه.

1098
00:51:25,720 --> 00:51:30,050
اما آنچه شگفت انگیز در مورد یک درخت پیشوندی است
که، در حالی یک لیست پیوندی و حتی

1099
00:51:30,050 --> 00:51:34,520
یک آرایه، بهترین ما تا کنون بدست است
زمان خطی یا زمان لگاریتمی به دنبال

1100
00:51:34,520 --> 00:51:35,600
کسی که.

1101
00:51:35,600 --> 00:51:40,530
در این ساختار داده ها از یک درخت پیشوندی، اگر
ساختار داده ها من یک نام در آن

1102
00:51:40,530 --> 00:51:43,720
و من به دنبال ماکسول، من
رفتن به او را پیدا کنید خیلی سریع.

1103
00:51:43,720 --> 00:51:47,910
من فقط برای M-A-X-W-E-L-L است. اگر
این ساختار داده، در مقابل،

1104
00:51:47,910 --> 00:51:51,830
اگر n یک میلیون نفر است، اگر یک وجود دارد
میلیون نام در این ساختار داده ها،

1105
00:51:51,830 --> 00:51:57,100
ماکسول است که هنوز هم برای رفتن به
کشف تنها پس از M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
مراحل.

1107
00:51:58,090 --> 00:52:01,276
و مراحل David-- D-A-V-I-D.

1108
00:52:01,276 --> 00:52:03,400
به عبارت دیگر، با ساخت
یک ساختار داده که

1109
00:52:03,400 --> 00:52:07,240
کردم همه از این آرایه، همه از آن
خود حمایت از دسترسی تصادفی،

1110
00:52:07,240 --> 00:52:11,090
من می توانم شروع به دنبال کردن مردم
نام استفاده از مقدار زمان که

1111
00:52:11,090 --> 00:52:14,340
متناسب با تعداد نیست
از چیزهایی که در ساختار داده ها،

1112
00:52:14,340 --> 00:52:16,330
مانند یک میلیون نام موجود است.

1113
00:52:16,330 --> 00:52:20,135
مقدار زمان آن را به من طول می کشد تا
M-A-X-W-E-L-L در این ساختار داده است

1114
00:52:20,135 --> 00:52:22,260
متناسب نیست به
اندازه ساختار داده ها،

1115
00:52:22,260 --> 00:52:25,930
اما به طول نام.

1116
00:52:25,930 --> 00:52:28,440
و در واقع
نام ما به دنبال تا

1117
00:52:28,440 --> 00:52:29,970
هرگز به دیوانه طولانی باشد.

1118
00:52:29,970 --> 00:52:32,600
شاید کسی دارای یک شخصیت 10
نام، نام شخصیت 20.

1119
00:52:32,600 --> 00:52:33,900
این قطعا محدود، درست است؟

1120
00:52:33,900 --> 00:52:37,110
یک انسان بر روی زمین وجود دارد که
دارای طولانی ترین نام ممکن است،

1121
00:52:37,110 --> 00:52:39,920
اما که نام یک ثابت است
طول ارزش، درست است؟

1122
00:52:39,920 --> 00:52:41,980
این کار در هر حس تغییر نمی کند.

1123
00:52:41,980 --> 00:52:45,090
بنابراین در این روش، ما
به دست آورد یک ساختار داده

1124
00:52:45,090 --> 00:52:47,800
که زمان ثابت نگاه کردن است.

1125
00:52:47,800 --> 00:52:50,670
آن را می کند تعدادی از مراحل
بسته به طول ورودی،

1126
00:52:50,670 --> 00:52:54,250
اما نه تعداد نام
در ساختار داده ها.

1127
00:52:54,250 --> 00:52:58,700
بنابراین اگر ما تعدادی از نام های دو برابر
سال آینده از یک میلیارد به دو میلیارد،

1128
00:52:58,700 --> 00:53:03,720
یافته ماکسول می گذرد را به
به همان تعداد دقیق هفت مرحله

1129
00:53:03,720 --> 00:53:04,650
به او پیدا کنید.

1130
00:53:04,650 --> 00:53:08,810
و بنابراین ما به نظر می رسد به دست آورد
جام مقدس ما از زمان حال اجرا است.

1131
00:53:08,810 --> 00:53:10,860
>> بنابراین چند اطلاعیه ها سریع.

1132
00:53:10,860 --> 00:53:11,850
مسابقه صفر در حال آمدن است.

1133
00:53:11,850 --> 00:53:14,600
بیشتر در مورد که در وب سایت درس
در طی چند روز آینده.

1134
00:53:14,600 --> 00:53:17,120
روز دوشنبه lecture-- آن یک روز تعطیل است
در اینجا در دانشگاه هاروارد در روز دوشنبه.

1135
00:53:17,120 --> 00:53:18,850
آن را در نیوهیون نیست،
بنابراین ما در حال گرفتن کلاس

1136
00:53:18,850 --> 00:53:20,310
به پناهگاه جدید برای سخنرانی در روز دوشنبه.

1137
00:53:20,310 --> 00:53:22,550
همه چیز فیلم برداری خواهد
و جریان به طور معمول زندگی می کنند،

1138
00:53:22,550 --> 00:53:24,900
اما اجازه دهید امروز به پایان
با یک کلیپ 30 ثانیه

1139
00:53:24,900 --> 00:53:26,910
به نام "افکار عمیق"
توسط Daven فرنهام که

1140
00:53:26,910 --> 00:53:30,850
سال گذشته روز شنبه الهام گرفته شده بود
"افکار عمیق" شب زنده

1141
00:53:30,850 --> 00:53:35,700
توسط جک دستی، که
در حال حاضر باید حس.

1142
00:53:35,700 --> 00:53:38,810
>> فیلم: در حال حاضر، "عمیق
افکار "توسط Daven فرنهام.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
جدول هش.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SPEAKER 1: همه حق است، که آن را در حال حاضر.

1147
00:53:47,660 --> 00:53:48,805
ما شما را هفته آینده را ببینید.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> داگ: برای دیدن آن در عمل است.

1150
00:53:56,680 --> 00:53:58,304
بنابراین اجازه دهید نگاهی به که در حال حاضر.

1151
00:53:58,304 --> 00:53:59,890
بنابراین در اینجا، ما یک آرایه نامرتب.

1152
00:53:59,890 --> 00:54:04,860
>> ایان: داگ، می تواند شما را به جلو و راه اندازی مجدد
این فقط برای یک لحظه لطفا

1153
00:54:04,860 --> 00:54:08,562
همه حق است، دوربین دارن، بنابراین
عمل هر زمان که شما آماده، داگ هستید، خوب است؟

1154
00:54:08,562 --> 00:54:11,020
داگ: همه حق است، بنابراین آنچه که ما
در اینجا یک آرایه نامرتب است.

1155
00:54:11,020 --> 00:54:13,960
و من تمام عناصر رنگی ام
قرمز به نشان می دهد که در آن است، در واقع،

1156
00:54:13,960 --> 00:54:14,460
نامرتب.

1157
00:54:14,460 --> 00:54:17,960
پس به یاد آورید که اولین چیزی که ما انجام می دهیم
این است که ما در نیمه سمت چپ آرایه مرتب کردن.

1158
00:54:17,960 --> 00:54:20,630
سپس ما حق مرتب سازی بر اساس
نیمی از آرایه.

1159
00:54:20,630 --> 00:54:22,830
و بله، دا، بله، دا، بله، DA،
ما آنها را با هم ادغام خواهند شد.

1160
00:54:22,830 --> 00:54:24,520
و ما باید یک آرایه به طور کامل طبقه بندی شده اند.

1161
00:54:24,520 --> 00:54:25,360
بنابراین این که چگونه ادغام مرتب سازی بر کار می کند.

1162
00:54:25,360 --> 00:54:27,109
>> ایان: هی، هی، هی،
برش، برش، برش، برش.

1163
00:54:27,109 --> 00:54:30,130
داگ، شما نمی توانید فقط از ya-DA، بله، DA،
بله، DA، راه خود را از طریق مرتب سازی بر ادغام.

1164
00:54:30,130 --> 00:54:31,970
>> داگ: من فقط.

1165
00:54:31,970 --> 00:54:32,832
این خوبه.

1166
00:54:32,832 --> 00:54:33,540
ما خوب به آن بروید.

1167
00:54:33,540 --> 00:54:34,760
اجازه دهید فقط نورد نگه دارید.

1168
00:54:34,760 --> 00:54:35,380
پس به هر حال،

1169
00:54:35,380 --> 00:54:37,800
>> ایان: شما باید به توضیح
این به طور کامل بیشتر از آن.

1170
00:54:37,800 --> 00:54:39,999
که فقط کافی نیست.

1171
00:54:39,999 --> 00:54:41,790
داگ: ایان، ما نمی
نیاز به رفتن به یک است.

1172
00:54:41,790 --> 00:54:42,350
این خوبه.

1173
00:54:42,350 --> 00:54:45,690
پس به هر حال، اگر ما با merge-- ادامه
یان، ما در وسط فیلمبرداری است.

1174
00:54:45,690 --> 00:54:46,612
>> ایان: من می دانم.

1175
00:54:46,612 --> 00:54:49,320
و ما نمی توانیم فقط از ya-DA، بله، DA،
بله، DA، از طریق تمام مراحل.

1176
00:54:49,320 --> 00:54:52,200
شما باید برای توضیح دهد که چگونه
دو طرف از هم ادغام شدند.

1177
00:54:52,200 --> 00:54:53,570
>> داگ: اما ما در حال حاضر
چگونه دو sides-- توضیح داد

1178
00:54:53,570 --> 00:54:55,321
>> ایان: شما فقط نشان داده ایم
آنها یک آرایه ادغام.

1179
00:54:55,321 --> 00:54:56,486
داگ: آنها می دانند که این فرآیند است.

1180
00:54:56,486 --> 00:54:57,172
آنها خوب است.

1181
00:54:57,172 --> 00:54:58,380
ما بیش از ده بار رفته است.

1182
00:54:58,380 --> 00:55:00,330
>> ایان: شما فقط حق بر آن قلم.

1183
00:55:00,330 --> 00:55:03,360
ما در حال رفتن به یک، شما
می تواند به شما بله، دا، بله، دا بیش از آن.

1184
00:55:03,360 --> 00:55:05,480
همه حق است، به یکی.

1185
00:55:05,480 --> 00:55:07,833
>> داگ: من برای رفتن به عقب
از طریق تمام اسلاید؟

1186
00:55:07,833 --> 00:55:08,332
خدای من.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
آن را مانند ششمین بار، ایان است.

1189
00:55:13,004 --> 00:55:13,940
این خوبه.

1190
00:55:13,940 --> 00:55:15,200
>> ایان: بسیار خوب.

1191
00:55:15,200 --> 00:55:16,590
آماده ای؟

1192
00:55:16,590 --> 00:55:17,400
عالی.

1193
00:55:17,400 --> 00:55:18,950
عمل.