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

2
00:00:10,900 --> 00:00:15,860
>> स्पीकर 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
>> स्पीकर 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
स्पीकर 1: हाँ, तो हम की जरूरत है
कम से कम दो बार ज्यादा जगह के रूप में।

33
00:01:25,200 --> 00:01:27,700
वास्तव में, मुझे एहसास हुआ कि इस तस्वीर के
यहां तक ​​कि एक छोटे से भ्रामक,

34
00:01:27,700 --> 00:01:32,200
क्योंकि आधुनिक का एक बहुत में 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
लेकिन canonicalize की कोशिश करते हैं
पहले अभियान

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
>> तो यह सिर्फ कुछ सी कोड है,
नहीं भी एक पूरा कार्यक्रम

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
यह हम एन फोन करता हूँ कि एक पूर्णांक है
लेकिन हम कुछ भी कह सकते हैं,

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
>> स्पीकर 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
हम संरचना कहा है कि क्यों
नोड स्टार, स्टार denoting

77
00:03:20,810 --> 00:03:22,370
एक सूचक या एक पते।

78
00:03:22,370 --> 00:03:26,390
ठीक है, तो अब आप हम मान लेते हैं कि यदि
हमारे पास उपलब्ध इस एन, और चलो

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
सम्मेलन द्वारा सिर्फ जा रहा है
करने के लिए, पीटीआर सूचक कहा जाता है, या हो

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
कि अशक्त कुछ विशेष प्रहरी मूल्य है
सूची के अंत सीमांकित

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
Pointer-- हैं और अब मैं एक तरह से करना चाहते हैं
हम छात्र के साथ किया था कि क्या करना है

106
00:04:51,820 --> 00:04:57,410
structure-- सूचक डॉट अगले यदि
बराबर होती सूचक डॉट एन, के बराबर होती है बल्कि यदि

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
मैं अंदर की संख्या एन पाया है
मेरा लिंक सूची के नोड्स में से एक।

110
00:05:11,020 --> 00:05:13,500
लेकिन डॉट नहीं रह गया है
इस संदर्भ में काम करता है,

111
00:05:13,500 --> 00:05:17,260
सूचक, पीटीआर है, क्योंकि
वास्तव में एक सूचक, एक पता,

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
एन, क्या मैं क्या करना चाहते हैं नहीं है?

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
और अंत में, मैं नहीं होने अशक्त मारा
पाया एन अभी तक, मैं सिर्फ झूठी वापसी।

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
यदि नहीं, तो मैं अपने हाथ को अद्यतन,
उर्फ सूचक, बात करने के लिए

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
यह है के रूप में एक सार डेटा insofar के प्रकार है
नहीं एक सी बात है, यह एक 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
और यह एक, कि शास्त्रीय विधि पता चला है
ढेर में कम से कम दो आपरेशन का समर्थन करता है।

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
>> खैर, हम अपेक्षित के सभी है
मैं कहना है कि सी में हमारे निपटान पर वाक्य रचना,

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
>> स्पीकर 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
हम popping रहे हैं।

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
तुम intuitively प्रस्तावित
सही ढंग से मैं 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
और वास्तव में सी कि सुविधा नहीं है।

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
हालांकि, हम सिर्फ tweak करने की जरूरत है
हमारे ढेर की परिभाषा

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
हम अब तक कि स्मृति reallocate कर सकता है
सिर्फ वहाँ एक अलग पते के भंडारण

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
हम मैं क्या था करने के लिए समान कोड की जरूरत
बस एक पल पहले बाहर की पिटाई।

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
एन्क्यू या विपंक्ति, जोड़ने या हटाने की तरह है,
यह है, यह कहने का सिर्फ एक शौक़ीन रास्ता है

311
00:14:35,660 --> 00:14:38,100
एन्क्यू या विपंक्ति, के रूप में इस प्रकार है।

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--।

324
00:15:14,220 --> 00:15:20,150
अब मैं फिर 50 enqueue देंगे, और
51, और फिर 61, और डॉट डॉट डॉट।

325
00:15:20,150 --> 00:15:21,070
तो यह है कि एन्क्यू है।

326
00:15:21,070 --> 00:15:23,176
मैं तो 61, फिर 50, 51 कतारबद्ध।

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
मैं इस आकार को अपडेट करने की जरूरत है, तो मैं जाना
अब तीन to 1:59 शून्य से।

330
00:15:33,680 --> 00:15:35,760
मैं कैसे विपंक्ति है?

331
00:15:35,760 --> 00:15:36,890
क्या विपंक्ति के साथ क्या होता है?

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; जो
05:00 पर नहीं थी

339
00:15:55,030 --> 00:15:56,790
के लिए अप लाइन के लिए
नए iPhone या whatnot।

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
जिसका प्रारंभिक Nth सामने,
मूल्य क्या होना चाहिए था?

354
00:16:33,729 --> 00:16:35,270
शून्य, सूची की शुरुआत।

355
00:16:35,270 --> 00:16:40,876
लेकिन अब अलावा decrementing के लिए
आकार, हम बस सामने वेतन वृद्धि।

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, और फिर, dammit

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
मैं यहाँ एक और नंबर डाल करना चाहते हैं,
लेकिन, Dammit, मैं अंतरिक्ष से बाहर हूँ।

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 overwriting शुरू करते हैं।

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
और वास्तव में, क्या ऑपरेटर
सी में शायद की सुविधा देता है

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
इस तरह के सीधे लाइनों के रूप में, अगर आप
प्रकार के curving के रूप में इस बारे में सोचते हैं

383
00:17:56,520 --> 00:18:00,341
चारों ओर एक चक्र के रूप में, तो बस
intuitively यह एक तरह से मानसिक रूप से काम करता है

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
स्पीकर 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
आईडी, स्मृति या राम के एक गीगाबाइट है

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
आपका ऑपरेटिंग सिस्टम
विंडोज या मैक ओएस या लिनक्स,

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
तो अगर आप इस राम के दो gigs था
कंप्यूटर इसके बारे में सोच सकते हैं कि कैसे है।

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
ए और बी और की तरह है और दो स्थानीय चर
हम एक और दो से उन मूल्यों को बदलने

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
वास्तव में, यह अभी भी है
वहाँ अपीलें।

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
और तो मुख्य काम के किसी भी पता नहीं है
कि, कि स्वैप समारोह में किया गया था

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
यह एक ही रैम है।

511
00:23:44,285 --> 00:23:45,160
यह एक ही स्मृति है।

512
00:23:45,160 --> 00:23:49,080
यह हो रहा है कि सिर्फ रैम है
वहाँ के बजाय यहाँ नीचे।

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
विशेष रूप से सी में कंप्यूटर की मेमोरी,
तो यह एक बहुत ही मनमाने ढंग से कार्यक्रम है,

537
00:24:53,120 --> 00:24:55,130
लेकिन नीचे से ऊपर इसे पढ़ा करते हैं।

538
00:24:55,130 --> 00:24:57,650
Argc चार स्टार argv में मुख्य।

539
00:24:57,650 --> 00:24:59,830
ऐसा लगता है कि एक कार्यक्रम है
कमांड लाइन तर्क।

540
00:24:59,830 --> 00:25:03,620
और सभी मुख्य जाहिरा तौर पर कॉल करता है
एक समारोह सादगी के लिए एफ कहते हैं।

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
तो यह एफ में गुजरता है जो कुछ भी
शब्द उपयोगकर्ता द्वारा लिखा गया है

544
00:25:09,320 --> 00:25:11,500
बाद प्रॉम्प्ट पर
कार्यक्रम के नाम पर सब।

545
00:25:11,500 --> 00:25:15,730
इतना तो है कि सीजर या Vigenere, जैसे जो
आप argv के साथ क्या कर याद हो सकता है।

546
00:25:15,730 --> 00:25:16,680
>> तो एफ क्या है?

547
00:25:16,680 --> 00:25:19,760
एफ एक स्ट्रिंग में ले जाता है
इसकी एकमात्र तर्क के रूप में,

548
00:25:19,760 --> 00:25:22,100
उर्फ एक चार सितारा, एक ही
बात है, एक स्ट्रिंग के रूप में।

549
00:25:22,100 --> 00:25:24,920
और यह मनमाने ढंग से कहा जाता है
इस उदाहरण में पट्टी।

550
00:25:24,920 --> 00:25:27,710
और फिर चार सी 12,
सिर्फ आम आदमी की दृष्टि में,

551
00:25:27,710 --> 00:25:31,750
हमारे लिए क्या कर रही चार ग ब्रैकेट 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
स्मृति में नकल सी पर पर बताया

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
पते में सी लेकिन सी में बताया
केवल preemptively 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
ऊपर छोड़ दिया एक सी ब्रैकेट शून्य और है
नीचे सही एक सी ब्रैकेट 11 है।

588
00:27:10,690 --> 00:27:12,870
यही कारण है कि बस कैसे कंप्यूटर है
इसे बाहर रखना करने के लिए जा रहा है।

589
00:27:12,870 --> 00:27:18,300
तो बस intuitively, बार अधिक है
सहित कुल 12 अक्षर, से

590
00:27:18,300 --> 00:27:25,790
जहां बैकस्लैश शून्य,
12 या सी ब्रैकेट 12 जाने के लिए जा रहे हैं?

591
00:27:25,790 --> 00:27:28,440
या यों कहें कि जहां 12 वीं है
चरित्र या 13 वीं चरित्र,

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
एच-ई-एल-एल-ओ बैकस्लैश शून्य, भीतर समाप्त होता है
उन 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
>> सी एक बहुत कम स्तर की भाषा है।

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
आज, अगर आप इस तरह है कि अंत
कि लाल खंड overwriting,

640
00:29:59,470 --> 00:30:01,580
बाइट्स के अनुक्रम कि नोटिस।

641
00:30:01,580 --> 00:30:05,020
हे 835 सी शून्य आठ शून्य।

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 सी 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
सी में हम वास्तव में क्या करना है वह यह है कि
स्मृति में कहीं भी करने के लिए उपयोग।

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
या whatnot शीर्ष, कुलपति पर और
परिवार की कुलमाता, सिर्फ एक

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
और यह दो तर्क लेता है,
एक पूर्णांक एन और एक सूचक

757
00:35:36,980 --> 00:35:41,400
पेड़ के लिए एक नोड, तो एक संकेतक के लिए
या एक पेड़ की जड़ के लिए एक सूचक,

758
00:35:41,400 --> 00:35:43,482
कैसे मैं एन के लिए खोज के बारे में जाना है?

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
पेड़ बराबरी बातिल के बराबर होती है, तो एन है
इस पेड़ में है या नहीं इस पेड़ में?

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
क्या आप मुझे कुछ भी नहीं देते हैं, मैं निश्चित रूप से नहीं कर सकते
किसी भी नंबर एन मिल बाकी तो क्या मैं हो सकता है

766
00:36:04,050 --> 00:36:04,750
अब जांचें?

767
00:36:04,750 --> 00:36:12,830
मैं अच्छी तरह से किसी और एन है, तो कहने जा रहा हूँ
पेड़ नोड में जो कुछ भी है, कम से कम

768
00:36:12,830 --> 00:36:16,300
मैं एन मूल्य सौंप दिया गया है कि।

769
00:36:16,300 --> 00:36:20,270
दूसरे शब्दों में, संख्या मैं कर रहा हूँ
एन, के लिए लग रही है, नोड से कम है

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
एन पेड़ तीर से कम है तो अगर
एन, मैं धारणात्मक बाईं जाना चाहता हूँ।

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-- मैं माँ नहीं say-- नहीं कर सकते
या पिता, कि अजीब होगा।

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
मैं पेड़ तीर बाएँ में एन के लिए खोज
एन मूल्य से अधिक है और अगर

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
एन इस गुजरती हैं और बारी बारी से खोज
उप पेड़ और सिर्फ वापसी

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
एक डेटा संरचना के साथ यहाँ एन करने के लिए
खुद को बारी बारी है कि

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, या एक जेपीईजी, या बिटमैप, या एक पिंग,

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
कैसे intuitively तुम होगा
जर्मन झंडा सेक

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
यहाँ एक मधुमक्खी bumble पर है
फूलों का एक गुच्छा के शीर्ष।

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
केवल insofar मधुमक्खी है जहां के रूप में भिन्न होते हैं।

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
कैसे आप पाठ compressing के बारे में जाना है?

905
00:42:40,450 --> 00:42:45,410
खैर, पात्रों में से प्रत्येक में
आस्की एक बाइट, या आठ बिट है।

906
00:42:45,410 --> 00:42:47,360
और उस तरह का गूंगा, सही है?

907
00:42:47,360 --> 00:42:51,160
आप शायद एक टाइप क्योंकि
और ई और मैं और ओ और यू एक बहुत

908
00:42:51,160 --> 00:42:55,270
अधिक बार डब्ल्यू या क्यू या जेड की तरह से,
भाषा के आधार पर जिसमें

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
ई की तरह, बातें आप अनुमान लगा
पहले फॉर्च्यून की व्हील में,

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
शायद यह सिर्फ दो ई सही था?

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
ई एक एकल डॉट है, इसलिए अगर आप
दो डॉट्स देख या दो डॉट्स सुना है,

938
00:44:08,640 --> 00:44:11,254
हो सकता है यह दो ई है या हो सकता है कि यह एक आई है

939
00:44:11,254 --> 00:44:13,670
तो हम एक बात है कि एक प्रणाली की जरूरत है
कि अधिक से अधिक चतुर थोड़ा।

940
00:44:13,670 --> 00:44:16,851
तो एक आदमी का नाम दिया Huffman साल
पहले वास्तव में इस के साथ आया था।

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
सिर्फ ए, बी की रचना की, सी डी एस और ई,
लेकिन अतिरेक का एक बहुत यहाँ नहीं है।

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
आप वास्तव में बाहर गिनती तो अगर सब
एक है, बी, सी, डी एस, ई और के, यहाँ है

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
ई, और तीन अन्य आवृत्तियों रहे हैं।

952
00:44:39,660 --> 00:44:41,960
हम स्वयं वहाँ ऊपर गिना
और सिर्फ गणित किया।

953
00:44:41,960 --> 00:44:44,579
>> तो यह पता चला है कि
Huffman, कुछ समय पहले,

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
एक चल बिन्दु के रूप में आवृत्तियों
मूल्य हैं, या आप भी, एक एन इसे इस्तेमाल कर सकते

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
>> और तो हॉफमैन, प्रस्तावित क्या
आप एक बी का प्रतिनिधित्व करना चाहते हैं,

985
00:46:05,070 --> 00:46:10,080
के रूप में नंबर 66 का प्रतिनिधित्व करने के बजाय
आठ पूरे बिट्स है जो एक ASCII,

986
00:46:10,080 --> 00:46:13,360
आप क्या, सिर्फ दुकान में पता
पैटर्न शून्य, शून्य, शून्य,

987
00:46:13,360 --> 00:46:17,030
शून्य कि रास्ता है, क्योंकि
मेरे पेड़ से, श्री Huffman का पेड़,

988
00:46:17,030 --> 00:46:18,600
जड़ से पत्ती को।

989
00:46:18,600 --> 00:46:20,970
आप एक स्टोर करना चाहते हैं
ई, इसके विपरीत, नहीं करते

990
00:46:20,970 --> 00:46:26,290
एक ई प्रतिनिधित्व करते हैं कि आठ बिट्स भेजने
इसके बजाय, बिट्स की क्या पैटर्न भेज सकते हैं?

991
00:46:26,290 --> 00:46:26,890
एक।

992
00:46:26,890 --> 00:46:30,410
और यह है के बारे में क्या अच्छा है
कि ई सबसे लोकप्रिय पत्र है,

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
ए था और इसलिए कितने बिट्स
वह उस के लिए उपयोग कर का प्रस्ताव किया?

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
यह है- और मैं लहर हूँ
इस पर मेरे हाथ कैसे आप

1003
00:46:52,538 --> 00:46:55,570
एक सी संरचना के रूप में यह लागू हो सकता है।

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 उधार ले जाने के लिए नहीं करना चाहता था
बाहर [से बातें? Annenberg?], इसलिए

1027
00:47:57,950 --> 00:48:00,289
यहां का प्रतिनिधित्व करते हैं कि पांच है
एक जेड के माध्यम से और यदि मैं

1028
00:48:00,289 --> 00:48:03,580
जिसका नाम एक साथ शुरू होता है एक छात्र को देखने
मैं वहां अपने या अपने प्रश्नोत्तरी डाल करने के लिए जा रहा हूँ।

1029
00:48:03,580 --> 00:48:08,850
किसी सी के साथ शुरू होता है, वहाँ पर,
एक-- वास्तव में, ऐसा करने के लिए नहीं चाहता था।

1030
00:48:08,850 --> 00:48:10,060
बी यहाँ पर चला जाता है।

1031
00:48:10,060 --> 00:48:13,390
तो मुझे मिल गया है एक और बी और सी और
अब यहाँ एक और एक छात्र की।

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
>> इसलिए मैं इस का समाधान कर सकते हैं एक ही रास्ता है, सब है
सही, एक सी में व्यस्त है, बी व्यस्त है, व्यस्त है।

1036
00:48:24,380 --> 00:48:28,880
मैं तो डी में उसे डाल करने के लिए जा रहा हूँ
सबसे पहले, मैं यादृच्छिक त्वरित पहुँच है

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
लेकिन यह एक नहीं है, तो
मेरी चाहत छात्र,

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
और, इतनी बात करने के लिए एक योजना बी के रूप में डाल दिया
या इस मामले में योजना डी, मूल्य

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
नाम क्यू या जेड, या कुछ और तरह के साथ
कि, कम से कम आप जगह का उपयोग कर रहे हैं।

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
दो लोगों को है, तो
नाम ए, क्या होगा

1051
00:49:06,670 --> 00:49:09,160
एक चालाक या अधिक कर दिया गया है
बस से सहज ज्ञान युक्त समाधान

1052
00:49:09,160 --> 00:49:12,840
डी माना जाता है जहां एक डाल?

1053
00:49:12,840 --> 00:49:14,810
क्यों मैं बस जाना नहीं है
बाहर [? Annenberg?],

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
यहाँ भी वही, एक यहाँ जाता है,
डी बी यहाँ जाता है, यहाँ जाता है।

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
>> तो एक मूर्ख की इस तरह,
पहले geeky मजाक साल।

1073
00:50:16,880 --> 00:50:19,590
CS50 हैक एक thon में
छात्रों की जांच में जब,

1074
00:50:19,590 --> 00:50:22,040
कुछ टीएफ या सीए हर साल
सोचता है कि इसे डाल अजीब बात है

1075
00:50:22,040 --> 00:50:27,772
इस तरह से एक संकेत है, जहां यह सिर्फ
आपके नाम एक एक के साथ शुरू होता है, तो इसका मतलब है,

1076
00:50:27,772 --> 00:50:28,870
इस तरफ से जाएं।

1077
00:50:28,870 --> 00:50:31,110
आपके नाम शुरू होता है
एक बी के साथ है- ठीक है जाओ,

1078
00:50:31,110 --> 00:50:33,290
यह हो सकता है बाद में सेमेस्टर में हास्यास्पद है।

1079
00:50:33,290 --> 00:50:36,420
लेकिन वहाँ एक और है
भी, ऐसा करने का तरीका है।

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
जो एक Trie कहा जाता है।

1084
00:50:42,400 --> 00:50:47,140
किसी कारण के लिए कम है जो टी आर-मैं-ई,
पुनः प्राप्ति के लिए, लेकिन यह Trie कहा जाता है।

1085
00:50:47,140 --> 00:50:51,389
तो एक Trie एक और दिलचस्प है
इन विचारों का एक बहुत का मिश्रण।

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
यह बच्चों के किसी भी संख्या के साथ एक पेड़ है
लेकिन एक Trie में बच्चों में से प्रत्येक

1089
00:50:58,410 --> 00:51:00,090
एक सरणी है।

1090
00:51:00,090 --> 00:51:04,790
आकार की एक सरणी, 26 या शायद 27 का कहना है
आप बंटे नामों का समर्थन करना चाहते हैं

1091
00:51:04,790 --> 00:51:06,790
या लोगों के नाम में apostrophes।

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
है, वहाँ शीर्ष नोड, एम को देखो
वहाँ सबसे बाएँ बात की ओर इशारा करते,

1095
00:51:13,710 --> 00:51:17,665
जो फिर एक, एक्स, डब्ल्यू, ई, एल, एल यह है
सिर्फ एक आंकड़ा संरचना है कि मनमाने ढंग से

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
एक Trie है के बारे में लेकिन आश्चर्यजनक क्या है
, कि एक लिंक सूची जबकि और भी

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
एक Trie के इस डेटा संरचना, यदि में
मेरे डेटा संरचना उस में एक नाम है

1102
00:51:40,530 --> 00:51:43,720
और मैं मैक्सवेल के लिए देख रहा हूँ, मैं हूँ
बहुत जल्दी उसे खोजने के लिए जा रहा है।

1103
00:51:43,720 --> 00:51:47,910
मैं सिर्फ एम-ए-एक्स डब्ल्यू ई एल-एल के लिए देखो। यदि
इस डेटा संरचना, इसके विपरीत,

1104
00:51:47,910 --> 00:51:51,830
एक है कि अगर वहाँ एन, एक लाख है, तो
इस डेटा संरचना में दस लाख के नाम,

1105
00:51:51,830 --> 00:51:57,100
मैक्सवेल अभी भी होने जा रहा है
खोज योग्य सिर्फ एम-ए-एक्स डब्ल्यू ई एल-एल के बाद

1106
00:51:57,100 --> 00:51:58,090
कदम।

1107
00:51:58,090 --> 00:52:01,276
और David-- डी-ए-वी-मैं-डी कदम।

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
इसे खोजने के लिए मुझे लगता है समय की राशि
एम-ए-एक्स डब्ल्यू ई एल एल इस डेटा संरचना में है

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 Farnham, द्वारा जो

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 Farnham द्वारा विचार "।

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
>> स्पीकर 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
और फिर डा, फिर-दा, हां-दा,
हम उन्हें एक साथ विलय।

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
डौग, आप बस फिर दा नहीं कर सकते, हां-दा,
हां- दा, मर्ज प्रकार के माध्यम से अपना रास्ता।

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
और हम बस फिर-दा नहीं कर सकते, हां-दा,
पूरी प्रक्रिया के माध्यम से फिर-दा,।

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
कार्रवाई।