डेविड मालन: सब ठीक है. CS50 के लिए वापस स्वागत है. इस सप्ताह 8 की शुरुआत है. और कहा कि समस्या को समाप्त 5 सेट याद एक चुनौती का एक छोटा सा के साथ. तो अगर आप अपने के सभी बरामद संभालने अध्येताओं और सीए की तस्वीरों शिक्षण card.raw फ़ाइल में, आप पात्र हैं अब उन लोगों में से सभी को खोजने के लिए, और एक भाग्यशाली विजेता को एक साथ घर चलना होगा इन बातों का, छलांग गति आप अंतिम के लिए उपयोग कर सकते हैं कि डिवाइस उदाहरण के लिए परियोजनाओं,. 

यह हर साल, की ओर जाता है creepiness का एक सा. और तो क्या मैं मैं क्या सोचा था कि शेयर है आप के साथ है कि नोटों में से कुछ पर आगे और पीछे चला गया देर से कर्मचारियों की सूची. उदाहरण के लिए, बस कल रात, भाव गंदें शब्द बोलना, कर्मचारियों में से एक से सदस्यों, "मैं सिर्फ एक छात्र दस्तक था मेरे दरवाजे पर मेरे साथ एक तस्वीर लेने के लिए. Stalkers, मैं आपको बता सकता. "शुरुआत काफी वर्णनात्मक और फिर हम चले गए पर, या तो एक घंटे बाद, "मैं था एक छात्र अनुभाग के बाद मेरे लिए इंतजार और वह हमारे नाम और फोटो के सभी था कागज के कुछ चादरें पर. "ठीक है. इसलिए संगठित, लेकिन नहीं अभी तक डरावना है कि सभी. 

फिर, "मैं शहर से बाहर इस सप्ताह के अंत में था जब मैं वापस मिल और एक में वहां गया था मेरे बेडरूम. "[हंसी] डेविड मालन: एक कर्मचारी से अगले बोली सदस्य, "एक छात्र पर मेरे घर आया था 04:00 पर Somerville आज सुबह. "अगला स्टाफ, "मैं सैन में अपने होटल के लिए मिला फ्रांसिस्को और एक छात्र के लिए इंतज़ार कर रहा था तीन DSLRs के साथ लॉबी में मुझे. " कैमरे के प्रकार. "मुझे लगता है, कर्मचारियों पर भी इस सत्र में नहीं हूँ लेकिन एक छात्र मेरे घर में तोड़ दिया इस सुबह और दर्ज की पूरी बात ,. गूगल ग्लास के साथ "और फिर अंत में "कम से कम 12 लोग बेसब्री से कर रहे थे मैं से बाहर हो गया, जब मेरे लिए इंतजार कर मेरे लिमो, और फिर मैं जाग उठा. "ठीक है. आप कर सकते हैं, जैसा कि तस्वीरों के बीच इतना याद है, तुम, जो यहां इस साथी हैं कौन रहता मिलो केले के रूप में जानते हो सकता है लॉरेन कार्वाल्हो, हमारे सिर के साथ बंदे अध्यापन. मिलो, मिलो, लड़का यहाँ आते हैं. मिलो. मिलो. ध्यान रहे, वह गूगल ग्लास पहने हुए है, तो हम के बाद आप यह सब दिखाता हूँ. आप करना चाहते हैं तो इस मिलो है बाद में उसके साथ एक तस्वीर ले लो. तुम बाहर देखने के लिए करना चाहते हैं वहाँ दर्शकों में. ठीक है. यह अच्छा दृश्य है. खैर, मिलो केले. ओह, ऐसा मत करो. 

[हंसी] 

ठीक है. तो फिर क्या आगे झूठ पर एक शब्द, हम संक्रमण के लिए शुरू के रूप में, क्योंकि इस सप्ताह विशेष रूप से, एक में सी से कमांड लाइन PHP के लिए पर्यावरण और जावास्क्रिप्ट और एसक्यूएल और HTML और सीएसएस एक वेब आधारित वातावरण, हम हो जाएगा सभी के साथ आप लैस के लिए और अधिक ज्ञान संभावित अंतिम परियोजनाओं. अंत की ओर है, बेशक एक है सेमिनार के आयोजन की परंपरा जो स्पर्शरेखा विषयों पर हैं कोर्स करने के लिए. बहुत ज्यादा प्रोग्रामिंग करने के लिए और से संबंधित एप्लिकेशन विकास और बहुत आगे है, लेकिन जरूरी द्वारा पता लगाया नहीं पाठ्यक्रम की अपनी ही पाठ्यक्रम. 

आप एक में रुचि हो सकती है तो या इस साल के सेमिनार से अधिक है, cs50.net/seminar पर रजिस्टर. पुराने सेमिनार कर रहे हैं cs50.net/seminars पर. और इस साल के लिए इस प्रकार अब तक रोस्टर पर रूबी के साथ अद्भुत वेब Apps पर हैं एक विकल्प है जो रेल, PHP के लिए भाषा. कम्प्यूटेशनल भाषाविज्ञान. जो IOS, का परिचय iPhone के लिए इस्तेमाल किया और है कि मंच iPad विकास. वेब ऐप्लिकेशन के लिए जावास्क्रिप्ट, हम कवर करेंगे यही नहीं, लेकिन इस संगोष्ठी में, तुम जाना होगा और अधिक विस्तार में. 

लीप मोशन, इसलिए हम वास्तव में कुछ करना होगा लीप मोशन से हमारे दोस्तों की, कंपनी ही, हमारे साथ. कल, वास्तव में, प्रदान करने के लिए एक हाथ पर संगोष्ठी, अगर आप के लिए ब्याज की. Meteor.js, के लिए एक वैकल्पिक तकनीक , एक ब्राउज़र में JavaScript नहीं का उपयोग लेकिन एक सर्वर पर. Node.js, जो बहुत ज्यादा है उस नस में के रूप में अच्छी तरह से. चिकना एंड्रॉयड डिजाइन. एंड्रॉयड एक बहुत ही लोकप्रिय विकल्प जा रहा है आईओएस और विंडोज फोन को और अन्य मोबाइल प्लेटफार्मों. और वेब सुरक्षा सक्रिय रक्षा. 

तो वास्तव में, यदि आप चाहेंगे इस में संलग्न करने के लिए, मुझे जाने इस बात का ध्यान करते हैं. हम कहते हैं कि करने के लिए बहुत खुश हैं लीप के हमारे मित्रों एक स्टार्टअप है जो गति, - इस डिवाइस वास्तव में सिर्फ आया कुछ महीने पहले बाहर - विनय से 30 तरह के उपकरणों का दान दिया है के रूप में कई छात्रों के लिए वर्ग के लिए, अगर आप हार्डवेयर के लिए उधार लेना चाहते हैं सेमेस्टर के अंत में और के लिए इसका इस्तेमाल करते हैं एक वास्तविक अंतिम परियोजना. वे भाषा के एक नंबर का समर्थन है. उनमें से कोई सी, उनमें से कोई भी पीएचपी, तो एहसास इन सेमिनारों में से एक या अधिक ब्याज की साबित हो सकता है. और उन सभी में फिल्माया जाएगा तुम नहीं कर पा रहे हैं कि घटना व्यक्ति में भाग लेने के लिए. अनुसूची के माध्यम से घोषणा की जा हम कमरे जमना के रूप में ईमेल. 

और अंत में, आप के लिए जाना है projects.cs.50.net, यह एक वेबसाइट है हम हम आमंत्रित करते हैं कि प्रत्येक वर्ष बनाए रखने के समुदाय, संकाय से लोगों को, विभागों, स्टाफ, और दोनों CS50 की एक बाहर करने में परियोजना के विचारों का प्रस्ताव. छात्र समूहों के हित की बातें. विभागों के लिए ब्याज की बातें. आप संघर्ष कर रहे हैं, तो वहाँ की बारी है क्या आप के रूप में अनिश्चितता के साथ अपने आप से निपटने के लिए करना चाहते हैं. 

हम एक यकीनन शुरू की तो पिछली बार अधिक जटिल डेटा संरचना हम चाहते हैं उससे सप्ताह अतीत में देखा. हम बहुत सरणियों का उपयोग कर रहा था खुशी से अगर एक उपयोगी रूप सरलीकृत डेटा संरचना. तो फिर हम इन, जो शुरू की बेशक सूचियों से जुड़े हुए हैं. और किस लिए की मंशा से एक था इस डेटा संरचना शुरू? हाँ? वह क्या है? 

दर्शक: गतिशील आकार. 

डेविड मालन: गतिशील आकार. सरणी में, आप हैं जबकि ऐसा करने के लिए अग्रिम में अपने आकार पता है जब आप इसे आवंटित. लिंक की गई सूची में, तुम नहीं करते कि पता है. आप अधिक आम तौर पर सिर्फ malloc, या कर सकते हैं एक अतिरिक्त आवंटित इतनी बात करने के लिए नोड, किसी भी समय आप अधिक डेटा सम्मिलित करना चाहते हैं. और नोड कोई अर्थ पूर्व निर्धारित किया गया है. यह वर्णन सिर्फ एक सामान्य शब्द है हम कर रहे हैं कि कंटेनर के कुछ प्रकार स्टोर करने के लिए हमारे डेटा संरचना में उपयोग करते हुए ब्याज की कुछ आइटम, इस में जो मामले पूर्णांकों होना होगा. 

लेकिन एक tradeoff हमेशा वहाँ है. इसलिए हम डेटा के गतिशील आकार मिलता है संरचना, लेकिन हम क्या कीमत अदा करते हैं? लिंक सूचियों का नकारात्मक पक्ष यह क्या है? हाँ? 

दर्शक: अधिक स्मृति की आवश्यकता है. 

डेविड मालन: यह अधिक की आवश्यकता स्मृति, बिल्कुल कैसे? 

दर्शक: [सुनाई]. 

डेविड मालन: बिल्कुल. तो अब हम संकेत को ले जा रहा है अतिरिक्त स्मृति कि हम पहले , की जरूरत नहीं थी, क्योंकि लाभ एक सरणी की, ज़ाहिर है, कि है सब कुछ सन्निहित, वापस , वापस वापस करने के लिए जो आप रैंडम एक्सेस देता है. क्योंकि सिर्फ वर्ग कोष्ठक का उपयोग करके अंकन, या अधिक तकनीकी रूप से सूचक गणित, बहुत सरल इसके अलावा, आप किसी भी उपयोग कर सकते हैं लगातार समय में तत्वों. और वास्तव में, उस तरह का इशारा है हम एक साथ भुगतान कर रहे हैं कि एक और मूल्य लिंक की गई सूची. 

क्या चलाने के समय के लिए होता है खोज की तरह कुछ, मैं करना चाहते हैं अंदर कुछ मूल्य लगता है और एक लिंक की गई सूची का? मेरे समय चल रहा है क्या हो जाता है? N की बड़ी हे. यह करने के लिए हल है, तो? क्या डेटा संरचना के आधार पर छाँटे गए तो क्या होगा? मैं बड़ा की तुलना में बेहतर कर सकते हैं खोज के लिए एन के हे? नहीं, क्योंकि सबसे खराब स्थिति में यह हो सकता है बहुत अच्छी तरह से हल है, लेकिन संख्या आप देख रहे हैं बड़ा हो सकता है. यह संख्या 100, जो हो सकता है सब हो हो सकता है अंत में जिस तरह से. और क्योंकि आप केवल एक लिंक किए उपयोग कर सकते हैं इस कार्यान्वयन में सूची से अपना पहला नोड की तरह, आप कर रहे हैं अभी भी तरह से भाग्य से बाहर. आप पूरी बात को पार करने के लिए है खोजने के क्रम में पहले से पिछले करने के लिए 100 की तरह है कि बड़ा मूल्य. अगर यह ज्ञात करने के लिए नहीं भी वहाँ. 

इसलिए हम ऐसा नहीं कर सकते एक डेटा में क्या एल्गोरिथ्म इस तरह लग रहा है कि संरचना? हम द्विआधारी खोज नहीं कर सकते क्योंकि द्विआधारी खोज हम था कि आवश्यक रैंडम एक्सेस. हम बस करने के स्थान से छलांग लगा सकता था का पालन करने के लिए बिना स्थान फॉर्म में इन रोटी के टुकड़ों इन सभी संकेत की. 

अब, हम यह कैसे लागू किया? खैर, हम यहाँ स्क्रीन करने के लिए जाना है, अगर हम जल्दी से इस डेटा reimplement कर सकते हैं संरचना - मेरी लिखावट सब नहीं है कि यहाँ महान है, लेकिन हम कोशिश करेंगे. तो typedef संरचना, और क्या मैंने किया यहाँ इस बात को कॉल करना चाहते हैं? नोड. इसलिए मुझे लगता है हमें शुरू कर देंगे. और अब, क्या के अंदर होने की जरूरत उस के लिए डेटा संरचना अकेले सूची जुड़े? कितने क्षेत्रों? 

तो दो. एक बहुत आसान है. तो पता int. और हम, कॉल मी हम चाहते हैं कुछ भी कर सकता है हम कर रहे हैं, लेकिन यह एक पूर्णांक होना चाहिए ints के लिए एक लिंक की गई सूची को लागू करने. और अब क्या दूसरी करता है क्षेत्र होना है? Struct node *. तो मैं संरचना नोड *, और फिर अगर मैं ऐसा मैं चाहता हूँ कि जो कुछ भी इस कॉल कर सकते हैं, लेकिन अभी मैं फोन करता हूँ स्पष्ट होना यह अगले, हम कर दिया गया है के रूप में. और फिर मैं अपने घुंघराले ब्रेसिज़ बंद कर देंगे. 

और अब, के रूप में पिछली बार, मैं यहाँ नोड नीचे डाल दिया. मैं घोषणा कर रहा हूँ लेकिन अगर यह है एक के रूप में नोड, मैं ऐसा क्यों किया जा रहा है परेशान किया वाचाल यहाँ संरचना की घोषणा में नोड * अगले, के रूप में विरोध बस नोड के लिए अगले? हाँ? 

दर्शक: [सुनाई]. 

डेविड मालन: बिल्कुल. बिल्कुल सही. सी वास्तव में सचमुच ले जाता है और इस वजह केवल नोड की परिभाषा देखता है जिस तरह यहाँ नीचे, तुम नहीं कर सकते यहाँ यह करने के लिए देखें. इसलिए हम रिक्तिपूर्व की इस प्रकार है बेशक है जो यहां घोषणा अधिक वाचाल. Struct node मतलब है कि, अब हम इसे उपयोग कर सकते हैं डेटा संरचना के अंदर. 

और एक अलग रूप में, यह है क्योंकि के रूप में अब एक छोटे से अधिक व्यक्तिपरक बनने सितारा तकनीकी रूप से यहां जा सकते हैं, यह यह कर सकते हैं, यहां जा सकते हैं यहां तक ​​कि बीच में जाना. हम के लिए शैली गाइड में, अपनाया है बेशक, डालने का सम्मेलन ठीक बगल में डेटा को सितारा लिखें, जो इस मामले में, संरचना नोड होगा. लेकिन और पाठ्यपुस्तकों का एक बहुत में एहसास ऑनलाइन संदर्भ, तुम वास्तव में हो सकता है दूसरी तरफ देखते हैं. लेकिन सिर्फ एहसास है कि दोनों होगा वास्तव में काम करते हैं और आप बस होना चाहिए संगत. 

ठीक है. इसलिए कि हमारे घोषणापत्र था संरचना नोड की. लेकिन फिर हम और अधिक कर रही शुरू परिष्कृत बातें. उदाहरण के लिए, हम शुरू करने का फैसला एक हैश तालिका की तरह कुछ. तो यहाँ आकार n के एक हैश तालिका है, n करने के लिए ऊपर छोड़ दिया पर 0 से अनुक्रमित शून्य से नीचे पर 1 छोड़ दिया. यह एक हैश हो सकता है कुछ के लिए तालिका. लेकिन चीजों की तरह हम बात किया एक हैश तालिका के लिए उपयोग के बारे में? क्या भंडारण के? 

नाम. हम जैसे नाम कर सकता है हम पिछली बार किया था. और वास्तव में, आप कुछ भी स्टोर कर सकते हैं. और हम में इस बार फिर देखेंगे PHP और जावास्क्रिप्ट में. एक हैश तालिका स्विस की एक अच्छी तरह है आप स्टोर करने के लिए अनुमति देता है कि सेना चाकू आप के अंदर जो चाहते हैं बहुत ज्यादा यह मूल्यों के साथ कुंजी जोड़ कर. मूल्यों के साथ कुंजी. 

अब इस सरल मामले में, हमारे चाबियाँ सिर्फ संख्या हैं. हम एक हैश को लागू कर रहे हैं एक सरणी के रूप में मेज. और तो चाबी, 0 हैं 1, 2, और बहुत आगे है. और इसलिए हम, मनुष्य के रूप में, पिछले फैसला किया आप जानते हैं कि सप्ताह हम कर रहे हैं क्या, नामों स्टोर करने के लिए जा रहा है, चलो बस मनमाने ढंग से, लेकिन बहुत हद तक, मान लेते हैं कि एलिस, एक एक नाम, अभी 0 में सूचीबद्ध किया जाएगा. और बॉब, एक बी नाम, अनुक्रमित किया जाएगा 1 में, और बहुत आगे है. इसलिए हम सूचनाओं के बीच एक मानचित्रण था हैश तार कर रहे हैं, और जो नंबर हैं जो स्थानों,. 

तो उस प्रक्रिया आम तौर पर के रूप में जाना जाता है एक हैश समारोह, और तुम सच में कर सकते हैं कोड में इसे लागू. मैं एक हैश समारोह को लागू करना चाहता था कि क्या वास्तव में हम अभी पिछले समय से वर्णित, मैं हो सकता है के रूप में लेता है कि एक समारोह की घोषणा उदाहरण के लिए इनपुट - और हम इस पर यह करते हैं यहाँ पर स्क्रीन. मैं एक हैश को लागू करना चाहता था समारोह, मैं कह सकते हैं कुछ इस तरह. 

यह एक पूर्णांक वापस जाने के लिए जा रहा है. यह हैश कहा जा रहा है, और यह बात है एक तर्क एक के रूप में स्वीकार करने के लिए जा रहा स्ट्रिंग, या हम अब और अधिक उचित हो सकता है और हम यह बात फोन करता हूँ, चार * कहते हैं. और फिर यह सब इस समारोह में क्या करना है, अंत में, एक int वापसी है. अब, यह कैसे करता है कि हो सकता है इतना स्पष्ट नहीं हो. मैं किसी भी बिना इस लागू करने के लिए जा रहा हूँ सही अब जाँच त्रुटि के रूप में. मैं बस आँख बंद करके कहने जा रहा हूँ, वापसी जो भी हो, एस ब्रैकेट 0 पर है, शून्य के, राजधानी अर्धविराम कहते हैं. 

पूरी तरह से टूट गया. यह सही नहीं है क्योंकि एक, एस शून्य है क्या? बुरी बातें होने जा रहे हैं. दो, क्या हुआ अगर इस में पहला पत्र नाम बड़े अक्षर नहीं है? बदले के लिए नहीं जा रहा है बाहर अच्छी तरह से या तो. यह एक छोटा अक्षर हो सकता है या बिल्कुल नहीं एक पत्र. यहाँ सुधार के लिए तो पूरी तरह से कमरे में, लेकिन यह मूल विचार है. 

हम मौखिक रूप से के रूप में पिछले सप्ताह वर्णित क्या मानचित्रण ऐलिस का सिर्फ एक प्रक्रिया करने के लिए 1 0 और बॉब व्यक्त किया जा सकता है निश्चित रूप से अधिक formulaically एक सी के रूप में यहां कार्य करते हैं. हैश फिर से बुलाया, के रूप में एक स्ट्रिंग लेता है इनपुट, और फिर किसी भी तरह कुछ भी करता है एक उत्पादन का उत्पादन करने के लिए कि इनपुट के साथ. नहीं हमारे ब्लैक बॉक्स वर्णन के विपरीत हम लंबे समय के लिए किया गया है. मैं यह कैसे हो सकता है पता नहीं है हुड के नीचे काम कर रहे. 

समस्या 6, चुनौतियों में से एक सेट के लिए आप तय करने के लिए क्या है अपने हैश समारोह होगा? उस काले के अंदर होने जा रहा है क्या बॉक्स, और शायद, यह एक हो जाएगा छोटे से इस से भी अधिक दिलचस्प है, और त्रुटि के लिए निश्चित रूप से अधिक होने का खतरा इस विशेष से जाँच कार्यान्वयन. 

लेकिन समस्याओं सही, पैदा कर सकते हैं? हम इस जैसे एक आंकड़ा संरचना है, तो एक, समस्याओं में से एक है क्या आप सम्मिलित रूप से आप समय के साथ में चला सकते हैं में अधिक से अधिक नाम तालिका हैश? तुम सही, टकराव मिलता है? क्या आप एलिस और हारून है, जिनके नाम हुआ दो लोग एक साथ शुरू करने के लिए? यही कारण है कि जहां आप, सवाल भी जन्म देती है दूसरा जैसे नाम रखा है? 

ठीक है, तुम भोलेपन से सिर्फ रख सकता है बॉब अंतर्गत आता है जहां, लेकिन फिर बॉब है आप करने की कोशिश एक तरह से खराब कर दिया है अगले उसका नाम डालने और उसके लिए कोई जगह नहीं है. तो तुम, चार्ली है जहां बॉब डाल सकते हैं और तुम बहुत जल्दी इस कल्पना कर सकते हैं एक मेस के एक बिट में devolving. अंत में रैखिक कुछ है, जहां आप अभी पूरी बात खोज करने के लिए ऐलिस या बॉब की तलाश में या हारून या चार्ली. 

तो बजाय हम बजाय बस की प्रस्तावित रैखिक खुले स्थान के लिए जांच और, वहाँ नामों plopping हम एक शौक़ीन दृष्टिकोण का प्रस्ताव रखा. एक हैश तालिका एक साथ अभी भी लागू सूचकांक की सरणी, लेकिन डेटा प्रकार की उन इंडेक्स संकेत दिए थे. क्या करने के लिए संकेत? लिंक सूचियों के लिए संकेत. 

क्योंकि एक लिंक सूची है कि याद वास्तव में सिर्फ एक एक नोड के लिए सूचक, और नोड नोड का एक अगली क्षेत्र है, और इसके आगे एक अगले क्षेत्र है, और. तो अब आप पर इस सरणी के बारे में सोच सकते हैं के रूप में एक हैश तालिका के बाएं हाथ की ओर एक लिंक की गई सूची के लिए अग्रणी. जो का लाभ यह है कि आप एक मिलता है एलिस और हारून के बीच टक्कर, तुम्हारे साथ क्या करते हो दूसरे ऐसे व्यक्ति? तुम बस उसे या उसके देते हैं अंत, या यहां तक ​​कि शुरुआत कि लिंक की गई सूची की. 

और वास्तव में, बस के माध्यम से नूडल जाने कि बस एक पल के लिए. जहां सबसे अधिक उपयुक्त होगा? मैं ऐलिस डालने और वह कम से समाप्त होता है पहला स्थान, तो मैं करने की कोशिश हारून का नाम डालें, और वहाँ जाहिर है एक टक्कर, मैं रखना चाहिए शुरुआत में उसे लिंक की गई सूची का? यही है, कि पहले स्थान पर है या अंत में? 

दर्शक: [सुनाई]. 

डेविड मालन: ठीक है. मैं शुरुआत में सुना है. क्यों शुरुआत में? 

दर्शक: [सुनाई]. 

डेविड मालन: ठीक है. यह वर्णमाला है, तो यह अच्छा है. यह एक अच्छा संपत्ति है. यह संभवतः मुझे कुछ समय की बचत होगी. यह मुझे द्विआधारी खोज करते हैं, लेकिन मैं नहीं होगा कम से कम बाहर तोड़ने के लिए सक्षम हो सकता है मुझे पता है कि अगर एक पाश की, ठीक है, मैं जिस तरह से कर रहा हूँ पिछले हारून इस में होगा थे लिंक की गई सूची के अनुसार क्रमबद्ध. मैं अपने समय देख बर्बाद करने के लिए नहीं है अंत करने के लिए सभी तरह. तो यह है कि उचित है. और क्यों आप सम्मिलित करना चाहते हो सकता है पर टकराने नाम सूची की शुरुआत? वह क्या है? 

दर्शक: [सुनाई]. 

डेविड मालन: यह एक लंबा समय लग सकता है सूची के अंत में मिलता है. और वास्तव में, अब और अब. आपको लगता है कि डालने अधिक नाम एक, अब उस के साथ शुरू श्रृंखला होने वाली है. अब उस लिंक किए गए सूची प्राप्त करने के लिए जा रहा है. तो क्या तुम सच में सिर्फ रहे हैं अपना समय बर्बाद कर. हो सकता है कि आप को बनाए रखने से बेहतर हो लगातार प्रविष्टि समय, 1 की बड़ी हे, हमेशा टकराने के नाम पर रख कर लिंक की गई सूची की शुरुआत और के रूप में ज्यादा चिंता नहीं छँटाई के बारे में. 

सबसे अच्छा जवाब क्या है? यह स्पष्ट नहीं है. यह एक तरह से पर निर्भर करता है क्या वितरण पैटर्न क्या है, है नामों का आप सम्मिलित कर रहे हैं. यह जरूरी नहीं है एक स्पष्ट जवाब. लेकिन यहाँ, फिर से, है करने के लिए एक डिजाइन अवसर. 

तो हम तो इस बात पर ध्यान दिया जो वास्तव में अन्य बड़ा अवसर है के लिए P-सेट 6. और एहसास है, आप पहले से ही नहीं है, Zamyla इन दोनों हैश में dives और अधिक विस्तार में टेबल और कोशिश करता है,. और वीडियो Walkthrough है पी सेट कल्पना में एम्बेडेड. यह एक Trie था - टी आर मैं ई. और क्या बारे में दिलचस्प था यह था कि समय चल रहा है के मैक्सवेल की तरह, एक नाम के लिए खोज पिछली बार, क्या की बड़ी हे था? वह क्या है? 

दर्शक: पत्रों की संख्या. 

डेविड मालन: पत्रों की संख्या. मैं दो बातें सुनी. पत्र और लगातार समय की संख्या. तो चलो पहले उस के साथ चलते हैं. पत्र की संख्या. खैर, यह आंकड़ा संरचना, याद है, एक पेड़, एक परिवार के पेड़, में से प्रत्येक की तरह जिसका नोड्स सरणियों के बने होते हैं. और उन सरणियों को संकेत दिए गए हैं अन्य ऐसे नोड्स, या अन्य ऐसे पेड़ में सरणियों. 

हम तो निर्धारित करने के लिए चाहता था तो अगर मैक्सवेल यहां है, चाहे मैं जाना हो सकता है के ऊपर से ही पहली सरणी, को पेड़, तथाकथित जड़, के ऊपर Trie, और तब, एम सूचक का पालन करें फिर एक सूचक है, तो एक्स, ई, एल, एल, डब्ल्यू. और फिर मैं कुछ विशेष प्रतीक को देखने जब एक त्रिकोण के रूप में यहाँ चिह्नित. कोड में आप हम प्रस्ताव देखेंगे आप कि बस हाँ कह, एक bool के रूप में कार्यान्वित या नहीं, एक शब्द यहाँ बंद हो जाता है. 

खैर, हम एम ए एक्स डब्ल्यू ई एल एल के लिए चला गया है एक बार, शायद, सात की तरह लगता है आठ हम यह पिछले एक जाना है, तो आठ मैक्सवेल को खोजने के लिए. या के लालकृष्ण इसे कहते हैं लेकिन पिछले याद करते हैं समय, मैं ने तर्क दिया कि अगर वहाँ एक पर एक वास्तविक अधिकतम लंबाई शब्द, 40 कुछ अजीब पात्रों की तरह, एक अधिकतम लंबाई का तात्पर्य एक स्थिर मूल्य. तो सच में, हाँ, यह तकनीकी रूप से बिग हे 8 या 7, या लालकृष्ण का वास्तव में बड़ी हे लेकिन क्या पर एक परिमित टोपी अगर वहाँ कश्मीर में हो सकता है, यह एक निरंतर है. और तो यह 1 से बड़ी हे पर है दिन के अंत. 

नहीं असली दुनिया में. आप वास्तव में देख शुरू नहीं जब अपने कार्यक्रम चल रहा है के रूप में अपनी घड़ी. यह बिल्कुल एक सा होने जा रहा है सही मायने में लगातार की तुलना में धीमी एक कदम के साथ समय. यह सात या आठ चरणों होने जा रहा है, लेकिन अभी भी है कि बहुत, बहुत बेहतर है n की बड़ी हे की तरह एक एल्गोरिथ्म से कि में क्या है के आकार पर निर्भर करता है डेटा संरचना. 

है हम सम्मिलित कर सकते हैं यहाँ उल्टा नोटिस इस मामले में एक लाख से अधिक नाम डेटा संरचना, लेकिन कितने कदम इसे खोजने के लिए हमें ले जा रहा है उस मामले में मैक्सवेल? नहीं. वह अप्रभावित है. और आज तक, मैं हमने देखा है नहीं लगता एक एक आंकड़ा संरचना का उदाहरण या एक पूरी तरह से था कि एल्गोरिथ्म बाह्य से अप्रभावित उस तरह व्यवहार. लेकिन यह आश्चर्यजनक नहीं हो सकता. यह एकमात्र समाधान नहीं हो सकता पी सेट के लिए 

और यह नहीं है. यह जरूरी डेटा नहीं है संरचना आप के लिए केंद्र की ओर झुकना चाहिए, जैसे हैश तालिकाओं, tradeoff है. आप यहाँ भुगतान की कीमत क्या है? मेमोरी. मेरा मतलब है, यह एक नृशंस है स्मृति की राशि. और आप काफी यहाँ यह नहीं देख सकते क्योंकि इस तस्वीर के लेखक जाहिर है, सरणियों के सभी छोटा कर दिया और हम एक है की बहुत सारी देखने और नहीं कर रहे हैं बी और सी और क्यू और वाई और इन सरणियों में जेड है. लेकिन वे वहाँ हैं. 

इन नोड्स में से प्रत्येक एक पूरी सरणी है कुछ 26 या अधिक बाइट्स, में से प्रत्येक के जो एक पत्र का प्रतिनिधित्व करता है. हमारे मामले में 27, हम समर्थन कर सकते हैं ताकि समस्या में apostrophes निर्धारित किया है. तो यह आंकड़ा संरचना, वास्तव में है वास्तव में घने और विस्तृत. और वह अकेले धीमा खत्म हो सकता है बातें नीचे, या कम से कम तुम एक लागत अंतरिक्ष बहुत अधिक. लेकिन फिर, हम आकर्षित कर सकते हैं यहाँ तुलना. 

एक समय याद है, हम बहुत कुछ हासिल छँटाई में और अधिक रोमांचक समय चल रहा है हम मर्ज सॉर्ट, लेकिन कीमत का उपयोग करते समय हम मर्ज के लिए लॉग एन एन प्राप्त करने के लिए भुगतान किया सॉर्ट हम खर्च करते हैं कि आवश्यक अधिक क्या संसाधन? अधिक अंतरिक्ष. हम करने के लिए एक उच्च माध्यमिक सरणी की जरूरत बस की तरह, में लोगों को कॉपी हम मंच पर यहाँ था. तो फिर, कोई स्पष्ट विजेता लेकिन सिर्फ व्यक्तिपरक डिजाइन किए जाने के निर्णय. 

ठीक है. तो कैसे इस बारे में? किसी को भी, जो डी हॉल को पहचानते हैं? ठीक है. इसलिए हम तीनों करना. माथर हाउस. तो इस माथर के भोजन के लिए है. मैं सभी डाइनिंग हॉल है शर्त लगा सकता हूँ इस तरह की ट्रे के ढेर. और यह वास्तव में प्रतिनिधि है हम है कुछ की जाहिर है पहले से ही देखा. हम एक ढेर सचमुच यह कहा जाता है. और के संदर्भ में ढेर, अपने डेटा चला जाता है जहां कंप्यूटर की मेमोरी है, कार्यों बुलाया जा रहा है. 

उदाहरण के लिए, क्या बातें की तरह जाना के संबंध में ढेर पर हम चर्चा की है स्मृति लेआउट सप्ताह अतीत में? वह क्या है? 

दर्शक: कार्य करने के लिए कॉल. 

डेविड मालन: मैं माफी चाहता हूँ. 

दर्शक: कार्य करने के लिए कॉल. 

डेविड मालन: कार्य करने के लिए कहता है, लेकिन विशेष रूप से, क्या में से प्रत्येक के अंदर है उन तख्ते? क्या बातें की तरह? हाँ. इसलिए स्थानीय चर. जब भी हम कुछ स्थानीय भंडारण की जरूरत है, एक तर्क है, या मैं int, या INT तरह अस्थायी, या जो कुछ भी स्थानीय चर हम किया गया है, है ढेर पर कि लगा. और हम एक ढेर इसे कहते हैं क्योंकि कि layering विचार की. बस की तरह, वास्तविकता के साथ मैच उसके अवधारणा. 

लेकिन यह पता चला है कि एक ढेर भी कर सकते हैं एक आंकड़ा संरचना, एक के रूप में देखा जा एक सरणी के लिए वैकल्पिक, एक वैकल्पिक एक लिंक की गई सूची के लिए. धारणात्मक अधिक दिलचस्प कुछ कि अभी भी किया जा सकता है उन दोनों में से किसी का उपयोग कर कार्यान्वित बातें हैं, लेकिन यह एक अलग प्रकार की है समर्थन डेटा संरचना, वास्तव में, केवल दो ऑपरेशन. लेकिन आप शौक़ीन पर जोड़ सकते हैं इन से सुविधाओं. लेकिन इन बुनियादी बातें हैं - धक्का और पॉप. 

और एक ढेर के साथ विचार है कि अगर मैं Annenberg के साथ या बिना, यहाँ है यह जानते हुए, अगले दरवाजे से एक ट्रे उस पर नंबर 9 के साथ. तो बस एक पूर्णांक. और मैं डेटा पर इस पुश करना चाहते हैं वर्तमान में खाली है जो संरचना,. इस ढेर के नीचे करने पर विचार करें. मैं पर इस संख्या 9 धक्का होगा ढेर, और अब यह अभी भी वहीं है. 

लेकिन एक ढेर के बारे में दिलचस्प बात यह है कि है कि मैं अब पुश करना चाहते हैं कुछ अन्य 17 जैसे मूल्य, और मैं धक्का इस ढेर पर, मैं क्या करने जा रहा हूँ ही सहज ज्ञान युक्त बात, मैं अभी जा रहा हूँ इसे लगाने के लिए सही है, जहां हम इंसानों शीर्ष पर, यह डाल करने के लिए इच्छुक हो जाएगा. लेकिन क्या अब दिलचस्प है , कैसे मैं 9 पर मिलता है? तुम्हें पता है मैं कुछ प्रयास के बिना नहीं करते हैं, पता है. 

तो क्या हुआ के बारे में दिलचस्प है एक ढेर है कि डिजाइन द्वारा, है यह एक LIFO डेटा संरचना है. वर्णन करने की मूर्खतापूर्ण रास्ता बाहर पहले, में पिछले. इसलिए पिछले संख्या में इस समय 17 वर्ष के थे. तो मैं कुछ दूर पॉप करना चाहते हैं ढेर की, यह केवल 17 हो सकता है. तो की एक अनिवार्य आदेश नहीं है यहां आपरेशन, जहां पिछले आइटम में पहले एक बाहर हो गया है. इसलिए करा, LIFO. 

तो क्यों यह उपयोगी हो सकता है? उनके संदर्भों क्या आप चाहते हैं जो में इस तरह एक आंकड़ा संरचना चाहते हैं? खैर, यह निश्चित रूप से उपयोगी हो गया है एक कंप्यूटर के अंदर. तो ऑपरेटिंग सिस्टम स्पष्ट रूप से इस का उपयोग ढेर के लिए डेटा संरचना की तरह. हम भी एक ही विचार देखेंगे यह वेब पृष्ठों के लिए आता है. तो इस सप्ताह और परे अगले हफ्ते और, और आप वेब लागू करने शुरू के रूप में आप कर सकते हैं एचटीएमएल नामक एक भाषा, में लेख वास्तव में ऐसा एक डेटा संरचना का उपयोग यह निर्धारित करने के लिए अगर पेज सही ढंग से स्वरूपित है. हम सभी वेब पृष्ठों का पालन देखेंगे क्योंकि पदानुक्रम का एक तरह से, एक खरोज कि इच्छा, दिन के अंत में, एक हो हुड के नीचे वृक्ष संरचना. तो बस थोड़ा सा में उस पर और अधिक. 

लेकिन अभी के लिए, एक के लिए प्रस्ताव देना पल, हम कैसे के बारे में जा सकते हैं एक ढेर है प्रतिनिधित्व क्या? मुझे हम लागू प्रस्ताव है कि चलो इस तरह कोड के साथ एक ढेर. तो एक ढेर के अंदर किया जा रहा है दो बातें, ट्रे नामक एक सरणी,, सिर्फ डेमो के साथ लगातार हो. और उस सरणी में वस्तुओं में से प्रत्येक एक प्रकार int होने जा रहा है. और क्षमता संभवतः क्या है? मैं नहीं लिखा गया है क्योंकि यहां पूरी परिभाषा. 

यह शायद अधिकतम है सरणी के आकार. और यह शायद एक तेज के रूप में घोषित किया है , फ़ाइल के शीर्ष पर कुछ परिभाषित एक तरह से स्थिर से गर्भित रूप मात्र पूंजीकरण. तो कहीं क्षमता परिभाषित किया गया है अधिकतम संभव आकार के रूप में. इस बीच, डेटा संरचना के अंदर एक ढेर के रूप में जाना जाता है वहाँ होगा बस में जाना एक पूर्णांक होना बस आकार के रूप में. 

मैं अब इस का प्रतिनिधित्व करने के लिए गए थे तो अगर सचित्र रूप से, चलो चलो लगता है कि इस पूरे ब्लैक बॉक्स मेरी ढेर का प्रतिनिधित्व करता है. के अंदर दो चर है. तो क्या मैं आकर्षित करने जा रहा हूँ आकार के रूप में पहली बार एक. और मैं जा रहा हूँ दूसरा एक एक सरणी के रूप में आकर्षित करने के लिए. 

लेकिन सिर्फ चीजें व्यवस्थित रखने के लिए, सामान्य रूप से मैं की तरह एक सरणी आकर्षित करेगा यही नहीं, लेकिन यह एक तरह से अच्छा है हम वास्तविकता से मेल, या अगर मानसिक मॉडल मेल खाते हैं. तो मुझे बजाय सरणी आकर्षित खड़ी, जो बस, फिर से है, कलाकार के गायन. वास्तव में क्या यह बात नहीं है हुड के नीचे है. है और हम डिफ़ॉल्ट रूप से, कहता हूँ कि, क्षमता तीन होने जा रहा है. तो यह यह स्थान 0 होगा स्थान 1, यह हो जाएगा स्थान 2 हो जाएगा. 

मैं एक तनाव गेंद के साथ रिश्वत, तो होगा किसी को आने और चलाने की तरह बस एक पल के लिए यहाँ बोर्ड? ठीक है, पहली बार अपने हाथ को देखा. ऊपर आओ. ठीक है. इसलिए मैं यह स्टीवन मानना ​​है. ऊपर आओ. ठीक है. 

लेकिन लगता है अब हम प्रारंभिक के लिए उल्टा दुनिया का राज्य है जहां मैं सिर्फ एक ढेर घोषित, और यह है क्षमता तीन से होने जा रहा. लेकिन आकार अभी तक निर्धारित नहीं किया गया है. ट्रे अभी तक निर्धारित नहीं किया गया है. तो सवालों की एक जोड़ी पहले. और मुझे तुम आप कर सकते हैं ताकि mic दे इस में अधिक सक्रिय रूप से हिस्सा लेना. 

तो क्या इस पल में आकार के अंदर है समय में मैंने किया है अगर एक ढेर के साथ घोषित कोड की एक पंक्ति? 

स्टीवन: बहुत ज्यादा नहीं है. 

डेविड मालन: ठीक है, ज्यादा नहीं. हम आकार के अंदर क्या जानते हैं हम अन्दर क्या पता चलेगा यहाँ इस सरणी की? 

स्टीवन: बस यादृच्छिक कोड, है ना? बस - 

डेविड मालन: हाँ, मैं जा रहा हूँ कोड को बुलाओ, लेकिन यादृच्छिक - 

स्टीवन: चीजें. 

डेविड मालन: रैंडम जैसे हालात 

स्टीवन: बिट्स. 

डेविड मालन: बिट्स, सही? तो कचरा मूल्यों, है ना? तो 0 और 1 के क्रमपरिवर्तन. पिछले प्रयोगों के अवशेष इस स्मृति की. है और हम वास्तव में नहीं जानता कि क्या मानों कर रहे हैं, तो हम आम तौर पर उन्हें आकर्षित प्रश्न चिह्न के रूप में. 

हम संभवतः हो तो पहली बात यहाँ क्या करना चाहते करने के लिए जा रहा - और मेरे अंदर इस क्षेत्र दे वहाँ एक नाम - ट्रे. हम संभवतः क्या आरंभीकृत आकार हम करना चाहते हैं के लिए इस ढेर का उपयोग शुरू कर दिया? 

स्टीवन: ट्रे 3 उप है. 

डेविड मालन: तो, ठीक है. स्पष्ट है, क्षमता घोषित किया जाता है कहीं तीन के रूप में. और कहा कि मैं का उपयोग किया है क्या है सरणी आवंटित करने के लिए. साइज का उल्लेख करने के लिए जा रहा है कि कितने ट्रे ढेर पर वर्तमान में कर रहे हैं. 

स्टीवन: शून्य. 

डेविड मालन: तो यह शून्य होना चाहिए. तो आगे चलते हैं, और किसी भी उंगली के साथ, आकार में एक शून्य आकर्षित. ठीक है. तो अब, क्या इस के अंदर है यहाँ, हम नहीं जानते. ये वास्तव में सिर्फ कचरा मान रहे हैं. इसलिए हम प्रश्न चिह्न खींचना, लेकिन हो सकता है चलो अब के लिए स्वच्छ बोर्ड रखते हैं यह बात नहीं है क्योंकि वहाँ क्या हो रहा है. हम सरणी को प्रारंभ करने की जरूरत नहीं है कुछ भी करने के लिए, क्योंकि हम जानते हैं कि अगर ढेर के आकार शून्य, ठीक है, हम है कुछ में पर लग जाना नहीं चाहिए वैसे भी इस सरणी समय में इस बिंदु. 

तो अब मैं धक्का लगता है कि ढेर पर नंबर 9. हम कैसे डेटा संरचना अद्यतन करना चाहिए इस ब्लैक बॉक्स के अंदर? क्या मूल्यों को बदलने की जरूरत है? 

स्टीवन: भीतर - आकार? 

डेविड मालन: ठीक है. आकार क्या हो जाना चाहिए? 

स्टीवन: आकार एक होगा. 

डेविड मालन: ठीक है. तो आकार एक हो जाना चाहिए. तो तुम एक दो तरीके से कर सकते हैं. मुझे अब, आप दे दो. अपने उंगली एक रबड़ है. ठीक है. तो अब अपनी उंगली एक ब्रश है. ठीक है. और अब और क्या बदल गया है, जाहिर है, डेटा संरचना में? 

स्टीवन: हम से जा रहे हैं 9 अप करने के लिए नीचे. 

डेविड मालन: 9. अच्छा, ठीक है. इसलिए अभी भी कम है क्या फर्क नहीं पड़ता स्थान एक या दो वे कर रहे हैं, क्योंकि कचरा मूल्यों, लेकिन हम परेशान नहीं करना चाहिए आकार है क्योंकि वहाँ देख हमें बता रहा है कि केवल पहला तत्व वास्तव में वैध है. तो अब मैं इस सूची पर 17 धक्का. क्या इस तस्वीर के लिए होता है? 

स्टीवन: तो आकार दो पर जाने के लिए जा रहा है. 

डेविड मालन: ठीक है. रबड़ कर रहे हैं - उफ़. आप एक रबड़ कर रहे हैं. 

स्टीवन: रबड़. 

डेविड मालन: आप एक ब्रश कर रहे हैं. 

स्टीवन: ब्रश. 

डेविड मालन: ठीक है. और क्या? 

स्टीवन: और फिर हम - 

डेविड मालन: हम 17 से धक्का दे दिया. 

स्टीवन: हम तो, शीर्ष पर 17 छड़ी - 

डेविड मालन: ठीक है, अच्छा है. 

स्टीवन: - नीचे ड्रॉप. 

डेविड मालन: सब ठीक है. यह आसान हो रही है. मैं आपको इस समय में मदद करने के लिए नहीं जा रहा हूँ. 22 पुश. 

स्टीवन: क्या किया. एक रबड़ बनना. मैं एक ब्रश होता जा रहा हूँ. और फिर मैं 22 डाल रहा हूँ. 

डेविड मालन: 22. बहुत बढ़िया. तो एक बार. मैं अब पुश करने के लिए जा रहा हूँ ढेर 26 पर. 

स्टीवन: ऊह. हे भगवान. तुम सच में मुझे गार्ड से पकड़ा. 

डेविड मालन: तुम नहीं किया इस आ देखते हैं? 

स्टीवन: मैं यह आभास नहीं था. हम फिर से प्रारंभिक क्षमता सकता है? 

डेविड मालन: यह एक अच्छा सवाल है. तो हम किस तरह की खुद को चित्रित किया यहाँ एक कोने में. वास्तव में स्टीवन के लिए बाहर अच्छा नहीं है हम इस सरणी आवंटित कर दिया है क्योंकि स्थिर रुप से, तो अंदर, बात करने के लिए डेटा संरचना की. और हम अनिवार्य रूप से कठिन कोडित है यह आकार तीन में से किया जाना है. इसलिए हम वास्तव में यह reallocate नहीं कर सकते हैं. 

हम में वापस चला सकता है, हम एक सूचक होने के लिए नए सिरे से परिभाषित ट्रे कि हम तब तक हाथ स्मृति को malloc का उपयोग करें. क्योंकि हम से स्मृति मिला malloc के माध्यम से ढेर, हम फिर इसे मुक्त कर सकता. लेकिन यह मुक्त कराने से पहले, हम कर सकते थे स्मृति का एक बड़ा हिस्सा reallocate, इसके आगे सूचक अद्यतन, और. लेकिन अब के लिए, यह सच है हम यही कर सकते हैं. पुश और पॉप संभवतः जा रहे हैं कुछ त्रुटि संकेत करने के लिए है. 

तो उदाहरण के लिए, हमारे कार्यान्वयन की धक्का एक bool लौट सकता है जो पहले सच, सच, सच लौट आए. लेकिन चौथी बार, यह किया जा रहा है उदाहरण के लिए, झूठी वापस जाने के लिए. ठीक है. बहुत अच्छी तरह से किया. बधाई हो. आज आप अपने तनाव गेंद अर्जित किया है. 

[वाहवाही] 

स्टीवन: धन्यवाद. 

डेविड मालन: धन्यवाद. ठीक है, तो यह बहुत ज्यादा नहीं हो रहा है एक कदम आगे की है, है ना? हम इस डेटा संरचना का वर्णन किया. यह सही है, सम्मोहक हो गया है? यह जैसे ऑपरेटिंग सिस्टम. जाहिरा तौर पर वेब इस का उपयोग कर सकते हैं, और अन्य अनुप्रयोगों अभी भी. लेकिन हम कर रहे हैं कि क्या एक बेवकूफ सीमा वापस सप्ताह की तरह दो सीमाओं को हम आकार सरणियों तय कर दी है, जहां. 

तो एक जोड़ी की वास्तव में कर रहे हैं हम इस को हल कर सकता तरीके. हम गतिशील सरणी आवंटित कर सकता है, मैं रूप से मुश्किल यह कोडिंग नहीं यहाँ किया, लेकिन बजाय फिर से की घोषणा इस बस के रूप में, स्पष्ट होना कुछ इस तरह. Int * ट्रे, निर्णय लेने से नहीं अभी तक एक क्षमता पर. लेकिन मैं कहीं और ढेर घोषित मेरे कोड में, मैं तो malloc कह सकते हैं, का एक हिस्सा का पता मिलता है स्मृति, और मैं आवंटित कर सकते हैं ट्रे के उस पते. 

यह सिर्फ एक हिस्सा की है और फिर, क्योंकि स्मृति, मैं वर्ग का उपयोग करने के लिए जारी रख सकता है हमेशा की तरह ब्रैकेट अंकन. फिर, की तरह इस क्योंकि वहाँ कार्यात्मक सरणियों के बराबर और आया है कि स्मृति की मात्रा वापस malloc से. हम अन्य के रूप में एक का इलाज कर सकते हैं सूचक गणित या का उपयोग वर्ग कोष्ठक अंकन. तो है कि एक दृष्टिकोण है. 

लेकिन कैसे और क्या हम यह लागू हो सकता है संभवतः एक ही डेटा संरचना,? है ना? हम सिर्फ इस हल मुझे लगता है जैसे एक सप्ताह पहले की तरह समस्या. इस समस्या का हल क्या था स्टीवन में भाग गया है? तो लिंक सूचियों, सही. 

समस्या हम चित्रकारी कर रहे हैं कि यदि आवंटन द्वारा एक कोने में खुद को अग्रिम बहुत कम स्मृति में है कि हम तो किसी भी तरह के साथ सौदा किया है, अच्छी तरह से, क्यों नहीं बस से बचने नहीं है कि कुल मिलाकर मुद्दा? क्यों सिर्फ ट्रे एक होने की घोषणा नहीं एक नोड के लिए सूचक, एक लिंक सूची फलस्वरूप और फिर बस नए नोड्स आवंटित स्टीवन एक फिट करने के लिए आवश्यक हर समय डेटा संरचना में संख्या. 

तो तस्वीर बदलने के लिए होगा. यह रूप में स्वच्छ और के रूप में नहीं किया जा रहा है तीन ints की सिर्फ एक सरणी के रूप में सरल. अब यह एक करने के लिए एक सूचक होने जा रहा है संरचना, और उस संरचना करने जा रहा है एक पूर्णांक और एक अगले सूचक है. ऐसा लगता है कि सूचक के माध्यम से नेतृत्व करने के लिए जा रहा है एक और ऐसी संरचना करने के लिए एक और ऐसी संरचना. तो तस्वीर वास्तव में होगा एक बिट मेसियर मिलता है. और हम बांधने तीर होगा सब कुछ एक साथ. 

लेकिन यह ठीक है, ठीक है क्योंकि हम यह कैसे करना है देखा है. और आप आराम से मिल एक बार किसी लिंक किए गए तरह कुछ को लागू आपको करना होगा जो सूची, तुम अगर के साथ एक हैश तालिका को लागू करने के लिए चयन पी सेट 6, आप कर सकते हैं के लिए अलग श्रृंखलन एक बिल्डिंग ब्लॉक, या एक के रूप में उपयोग घटक, या खरोंच में बोलते हैं, एक प्रक्रिया, तुम डाल कुछ है कि, आप अपनी खुद की पहेली टुकड़ा बनाया आप तो पुन: उपयोग कर सकते हैं. तो tradeoffs, लेकिन संभावित समाधान हम वास्तव में पहले देखा है कि. 

तो अक्सर, आप हर यह देखना एप्पल विज्ञप्ति जब या दो साल कुछ नया, और सब पागल लोग एप्पल के बाहर लाइन अप उनके सीमांत खरीदने के लिए स्टोर हार्डवेयर पर उन्नयन. मैं, यह ठीक है, यह कहना है क्योंकि मैं उन लोगों में से एक हूं. तो डेटा संरचना किस तरह इस वास्तविकता का प्रतिनिधित्व हो सकता? 

ठीक है, चलो यह एक पंक्ति, एक लाइन कहते हैं. इसलिए ब्रिटिश आम तौर पर यह फोन होगा एक वैसे भी कतार में है, तो यह एक अच्छा नाम है. और दो ऑपरेशन है कि एक कतार हम एक enqueue फोन करता हूँ समर्थन करेगा आपरेशन और एक विपंक्ति आपरेशन, में जो समान हैं धक्का और पॉप करने के लिए भावना. यह बस की तरह अलग में है सम्मेलन, क्या हम इन बुला रहे हैं. लेकिन कुछ enqueue को जोड़ने का मतलब या डेटा संरचना को डालें. इसे दूर करने के साधन विपंक्ति करें. लेकिन एक ढेर एक LIFO डेटा था जबकि संरचना, एक पंक्ति, एक प्रथम में है पहले बाहर आंकड़ा संरचना. 

आप लाइन में पहले व्यक्ति हैं, तुम्हें पाने के लिए पहले व्यक्ति होंगे रेखा के बाहर और अपने नए उपकरण खरीदने. इन लोगों को होगा कैसे परेशान कल्पना कीजिए एप्पल के बजाय के लिए, एक ढेर अगर इस्तेमाल उदाहरण के लिए, उठा लागू करने के लिए अपना नया खिलौना के ऊपर. इसलिए कतारों निश्चित रूप से, समझ कर, और हम के सभी प्रकार के बारे में सोच सकते हैं अनुप्रयोगों, शायद, कतारों के लिए, आप निष्पक्षता चाहते हैं, खासकर जब. तो हम कैसे इन लागू हो सकता है एक आंकड़ा संरचना के रूप में? 

खैर, मैं प्रस्ताव है कि हम हो सकता है इसे इस तरह से करना चाहते हैं. इसलिए मैं अब नंबर के लिए जा रहा हूँ. इसलिए हम नहीं इसे सरल रखने और हूँ जरूरी ट्रे के संदर्भ में बात करते हैं. के लोगों को मिल गया है कि सिर्फ संख्या. क्षमता, फिर, ठीक करने के लिए जा रहा है में हो सकता है कि लोगों की कुल संख्या इस लाइन के रूप में तीन या अन्य जो भी मूल्य. 

लेकिन मुझे लगता है मैं ट्रैक रखने की जरूरत है कि प्रस्ताव न केवल आकार का यह कर रहे हैं कितनी बातें, कतार. तो आकार वर्तमान आकार, क्षमता है अधिकतम आकार है. बस फिर, नामकरण सम्मेलन द्वारा. क्यों मैं अंदर एक अतिरिक्त INT जरूरत है में कौन है का ट्रैक रखने के लिए एक कतार में लाइन के सामने? क्यों मैं इस मामले में ऐसा करने की जरूरत है? 

खैर, यह कैसे तस्वीर है बदलने जा रहा? मैं शायद सबसे पुन: उपयोग कर सकते हैं इस तस्वीर की. मुझे आगे जाना है और यहां क्या मिटा दें. हम थोड़ा इस एक देता हूँ यहां अलग नाम. के 17 से छुटकारा पाने के चलो, चलो छुटकारा मिलता है 9 से, 3 से छुटकारा मिलता है. और चलो एक और बात जोड़ने. मैं मैं का ट्रैक रखने की जरूरत है कि प्रस्ताव बस है जो सूची के सामने साथ ही एक पूर्णांक होने जा रहा. और हम इसे सरल रखने के लिए जा रहे हैं. कोई अब के लिए सूची जुड़े. 

हम करने जा रहे हैं कि मानता हूँ इस सीमा के खिलाफ टक्कर. लेकिन मैं क्या देखना चाहते हैं इस बार क्या? तो मैं आगे जाना है और पहले लगता है व्यक्ति लाइन में आता है, और यह संख्या 9 है. हम तनाव की गेंद है. मैं दो या तीन लोगों का कहना है, चोरी कर सकता है? एक, दो, तीन? ऊपर आओ. ठीक सामने से, क्योंकि हम इस एक त्वरित बनाती हूँ. 

आप में से हर अब होने जा रहा है एप्पल पर लाइन में एक प्रशंसक लड़का. आप एप्पल हार्डवेयर प्राप्त नहीं किया जाएगा हालांकि इस के अंत में. ठीक है. आप संख्या 9 हो तो, आप कर रहे हैं 17 नंबर, 22 नंबर. ये मनमाना संख्या हैं, जैसे छात्र आईडी या whatnot. और बस एक पल में, चलो शुरू करें चीजें जोड़ने शुरू करने के लिए. और मैं यहाँ बोर्ड इस समय चलने देंगे. 

तो इस मामले में, मैं initialized किया है सामने होने के लिए - मैं वास्तव में वास्तव में परवाह नहीं है क्या आकार शून्य है क्योंकि सामने है. तो यह हो सकता है साथ ही बस एक प्रश्न चिह्न हो. ये सब सवाल के निशान हैं. तो अब हम वास्तव में कुछ देखना शुरू कर देंगे लोग दुकान पर परत. 

तो संख्या 9 है, तो आप पहले से एक रहे हैं सुबह 5 बजे, वहां से आगे जाने के लिए और अप लाइन या पहले रात. ठीक है. तो अब 9 यहाँ है. तो 9 सूची के सामने है. तो मैं आगे जाना है और अद्यतन करने के लिए जा रहा हूँ इस मौजूदा डेटा का आकार संरचना अब और 0 हो नहीं करने के लिए, लेकिन 1 हो. मैं कम से 9 डाला जा रहा हूँ सूची के सामने. मुझे आगे जाना है और स्क्रीन को चालू करते हैं तो हम यहाँ हमें अतीत देख सकते हैं. 

और अब मैं क्या चाहते हो मोर्चे पर डाल करने के लिए? मैं ट्रैक रखने के लिए जा रहा हूँ कि लाइन के सामने सही अब स्थान 0 पर है. आगे क्या होने वाला है क्योंकि? खैर, मैं enqueue अब लगता है 17 के रूप में अच्छी तरह से. तो वहाँ लाइन में हॉप. और फिर, के लिए दरवाजे की तरह दुकान यहाँ होने जा रहा है. तो अब मैं 17 जोड़ दिया है. और इन लोगों को अवरुद्ध कर रहे हैं, भले ही स्क्रीन, वह ठीक है, हम इसे यहाँ देख सकते हैं. माफ़ कीजिए. 

दर्शक: हम स्थानांतरित कर सकते हैं - 

डेविड मालन: नहीं, यह ठीक है. वहाँ यह बहुत बड़ा है. इसलिए 17 कतार के अंदर अब है. मैं अद्यतन करने की आवश्यकता है जो क्षेत्रों हालांकि अब? ठीक है, निश्चित रूप से आकार. और कैसे सामने के बारे में? ठीक है, नहीं. मोर्चा, नहीं बदलना चाहिए क्योंकि एक ढेर के विपरीत, हम निष्पक्षता बनाए रखना चाहते हैं. 9 में पहली बार आया था तो, अगर हम 9 चाहते हैं रेखा का पहली बार बाहर होने के लिए और दुकान में. 

वास्तव में, हम देखते हैं कि चलो. हम 22 सम्मिलित करने से पहले, चलो आगे बढ़ो और 9 विपंक्ति. आपका नाम फिर क्या है? 

दर्शक: जेक. 

डेविड मालन: जेक जा रहा है अब dequeued किया जाना है. तो तुम दुकान में चलने के लिए मिलता है. और बहाना है कि दुकान वहाँ पर है. तो अब क्या जरूरत है - सूचना प्रौद्योगिकी विभाग, सूचना प्रौद्योगिकी विभाग, सूचना प्रौद्योगिकी विभाग! अब क्या करने की जरूरत है? डिजाइन निर्णय. इसलिए नहीं एक बुरा वृत्ति, लेकिन - आपका नाम फिर क्या है? 

दर्शक: डेविड. 

डेविड मालन: डेविड. तब दाऊद ने क्या किया? उन्होंने कहा कि एक तरह से डेटा को ठीक करने की कोशिश कर रहा था उसके स्थान से संरचना और कदम जेक पूर्व स्थान में. हम तैयार हैं और वह ठीक है एक के रूप में स्वीकार करते हैं कि कार्यान्वयन विस्तार. लेकिन पहले, चलो डेटा अद्यतन करते हैं हम ऐसा संरचना से पहले. मैं सभी के विचार पसंद नहीं कर रहा हूँ क्योंकि लोगों को इस लाइन में स्थानांतरण. 

दाऊद के साथ करता है, तो यह कोई बड़ी बात नहीं है एक कदम है, लेकिन फिर वापस करने के लिए लगता है हम पर आठ स्वयंसेवकों को मिला है जब स्टेज और हम प्रविष्टि की तरह किया है सॉर्ट, हम था, जहां शुरू करने के लिए हर किसी के आसपास घूम रहा है. यह सही, महंगा मिल गया? यही कारण है कि मुझे बड़ा ओ के बारे में चापलूसी करता है n के, एन की बड़ी हे फिर चुकता. यह की तरह महसूस नहीं कर रहा है एक आदर्श परिणाम. 

तो चलो बस यह अद्यतन करते हैं. तो कतार का आकार अब कोई 2 है. यह अब केवल 1 है. लेकिन अब मैं कुछ अद्यतन कर सकते हैं मैं, पहले अद्यतन नहीं किया सूची के सामने. मैं सिर्फ कह सकते हैं, उस स्थान को 1 है? तो अब हम यहां कचरा मूल्य है कचरा यहां मूल्य, और दाऊद में इस कचरे के बीच. लेकिन डेटा संरचना अभी भी बरकरार है. 

और वास्तव में, मैं भी करने की जरूरत नहीं है जेक के पूर्व नंबर बदलने 9, कौन परवाह करता है. मैं में अब पर्याप्त जानकारी मैं एक व्यक्ति में जानते हैं कि वहाँ कि आकार इस कतार. और मुझे पता है कि उस व्यक्ति स्थान 1, नहीं 0 पर है. मैं गिनती नहीं कर रहा हूँ. तो 1 के रूप में अच्छी तरह से. तो डेटा संरचना अभी भी ठीक है. 

खैर, आगे क्या होता है? के enqueue करते हैं - आपका नाम क्या है? 

दर्शक: Callen. 

डेविड मालन: Callen. चलो एक Callen enqueue करते हैं, और 22 कतार में अब है. तो अब क्या यहाँ बदलने के लिए है? फ्रंट के लिए नहीं जा रहा है जाहिर है, बदल जाते हैं. साइज फिर 2 होने के लिए बदलने जा रहा है. और 22, यहाँ, 9 अभी भी मौजूद है समाप्त होता है लेकिन यह प्रभावी है एक कचरा मूल्य अब. यह जेक अतीत की सिर्फ एक अवशेष है. 

तो अब क्या होता है अगर मैं दाऊद विपंक्ति? पिछले एक आपरेशन, विपंक्ति डेविड. हम बदलाव कर सकता है, लेकिन मैं जाने के प्रस्ताव जितना संभव हो कम काम करते हैं. अब मेरे डेटा संरचना चला जाता है वापस आकार में 2-1. लेकिन लाइन के सामने अब 2 हो जाता है. मैं इन नंबरों को बदलने की जरूरत नहीं है बस अभी तक, वे कर रहे हैं, क्योंकि सिर्फ कचरा मूल्यों. 

लेकिन अब क्या होता है? मैं, 26 अपने आप enqueue तो? मैं यहाँ पर संबंधित की तरह लग रहा है. इसलिए मैं कतारबद्ध किया जा रहा हूँ. तो मैं एक तरह से यहां के हैं. और आप काफी नहीं करते हैं, भले ही मंच पर नेत्रहीन इस सराहना करते हैं, हम कमरे के पास बहुत है, क्योंकि मुझे ऐसा करना चाहिए यहाँ खड़ा नहीं किया, क्यों? 

दर्शक: आप सीमा से बाहर रहे हैं. 

डेविड मालन: ठीक है. मैं सीमा से बाहर हूँ. मैं परे अनुक्रमित किया है इस सरणी की सीमा. मैं वास्तव में से एक में होना चाहिए तीन संभावित स्थानों. अब, जहां जाने के लिए सबसे स्वाभाविक है? मुझे लगता है हम leveraged का प्रस्ताव एक सप्ताह में एक चाल. माड आपरेटर, प्रतिशत. मैं तकनीकी रूप में खड़ा हूँ क्योंकि स्थान 3, लेकिन मैं कर 3 माड क्षमता, इसलिए 3, एक प्रतिशत चिह्न, 3 - क्षमता के 3. वह क्या है? जब शेष क्या है आप 3 से 3 विभाजित? 0. 

इसलिए कि मुझे जेक था थे डालता है, जो वास्तव में अच्छा है. तो अब कार्यान्वयन इस बात के लिए हो रहा है की एक सिर दर्द का एक सा हो. यह वास्तव में सिर्फ एक लाइन है संहिता की, सिरदर्द. लेकिन कम से कम अब कचरा नहीं है यहां मूल्य है, लेकिन दो वहाँ यहां वैध ints. और मैं अब हम किया है कि दावा हम इतने लंबे समय के रूप में करने की जरूरत है कि क्या वास्तव में हम क्या जेक बदल मूल्य 26 हो गया था. 

अब हम अभी भी पर्याप्त जानकारी अखंडता बनाए रखने के लिए इस डेटा संरचना की. हम किस तरह के भाग्य से बाहर अब भी कर रहे हैं जब हम चार या अधिक कुल सम्मिलित करना चाहते हैं तत्वों, लेकिन मैं कम से कम कर सकते हैं बहुत यह निरंतर के कुशल उपयोग समय, वास्तव में. मैं स्थानांतरण के बारे में चिंता करने की ज़रूरत नहीं है दाऊद के झुकाव के रूप में हर कोई था. 

ढेर पर कोई प्रश्न, या इस कतार? 

दर्शक: कारण है कि आप जानते हैं तो आप आकार की जरूरत एक व्यक्ति के लिए है कहाँ? 

डेविड मालन: बिल्कुल. मैं सरणी के आकार पता करने की जरूरत मैं वास्तव में कैसे पता करने की जरूरत है क्योंकि इन मूल्यों के कई वैध हैं और इसलिए मैं जहां डाल करने के लिए मिल सकते हैं कि अगले व्यक्ति. बिल्कुल सही. आकार है - वास्तव में, हम अभी तक यह अद्यतन नहीं किया. मैं 26 पर खुद को जोड़ा. आकार, अब नहीं 1, लेकिन 2 है. तो अब यह वास्तव में मुझे लगता है में मदद करता है , 0 नहीं नहीं है जो सूची के सिर, 1, लेकिन 2 है. सूची के सामने वास्तव में संख्या 22 है. वह पहली बार में आया था, तो वह चाहिए, क्योंकि मुझे पहले की दुकान में अनुमति दी जानी नेत्रहीन मैं खड़ा हूँ, भले ही दुकान के करीब. 

सब ठीक है? इन लोगों के लिए प्रशंसा का एक दौर और हम वहाँ से बाहर उन्हें बता दूँगा. 

[वाहवाही] 

डेविड मालन: मैं दे सकता है आप ट्रे रखना. हम क्या होता है अगर देख सकता था आप चाहते हैं, लेकिन शायद नहीं. ठीक है. तो अब क्या है कि हमें छोड़ करता है? खैर, मुझे एक यह है कि वहाँ का प्रस्ताव करते हैं हम कर सकते थे कुछ अन्य डेटा संरचनाओं शुरू हमारे टूल किट के लिए उनका कहना है कि होगा वास्तव में काफी, काफी प्रासंगिक हो हम वेब सामान में गोता. फिर, कनेक्शन किसी तरह का है, जो फार्म के पेड़ को डोम में कुछ कहा, दस्तावेज़ ऑब्जेक्ट मॉडल. लेकिन हम में से अधिक देखेंगे कि लंबे समय से पहले. 

मुझे definitionally का प्रस्ताव करते हैं कि हम आप के रूप में जानते हो सकता है क्या अब पेड़ कॉल एक परिवार के पेड़ से अधिक है, जहां आप पर कुछ पूर्वज है पेड़ की जड़ों. पर एक पितृसत्तात्मक या एक कुलमाता पेड़ के ऊपर से ही. उनके पति के बिना, इस मामले में. लेकिन हम अब हम फोन करता हूँ क्या है हैंग कि नोड्स रहे हैं जो बच्चों को, बाईं बच्चे या सही बच्चे को, यहां दर्शाया के रूप में तीर. 

दूसरे शब्दों में, एक पेड़ आंकड़ा संरचना में कंप्यूटर में, एक पेड़ शून्य है या अधिक नोड्स. यह कम से कम एक नोड है, तो उस जड़ कहा जाता है. यह नेत्रहीन चीजें है कि हम शीर्ष पर आकर्षित. और उस नोड, किसी भी अन्य नोड की तरह कर सकते हैं है शून्य, एक या दो, या तीन, या फिर भी कई बच्चे डेटा संरचना का समर्थन करता है. इस मामले में, जड़, भंडारण एक मान, दो बच्चों, 2 और 3 है, तो हम आम तौर पर छोड़ दिया 2 कॉल बच्चे और 3 सही बच्चे. 

और फिर हम 5, 6 के लिए नीचे उतरो, और जब 7, 6 बच्चे के बीच कहा जा सकता है. आप चार बच्चे हैं, यह भ्रमित हो जाता है. तो हम उस तरह का उपयोग बंद की मौखिक रूप से शॉर्टकट. लेकिन यह सच में सिर्फ एक परिवार के पेड़ है. और पत्तियों यहाँ नोड्स रहे हैं कि खुद को कोई संतान नहीं है. वे पेड़ के नीचे बंद रखती. 

तो कैसे हम एक पेड़ को लागू हो सकता है कि ज़्यादा से ज़्यादा सिर्फ दो बच्चों की है? हम एक द्विआधारी पेड़ फोन करता हूँ. द्विपक्षीय फिर इस में, दो अर्थ बाइनरी साथ जैसे मामले,. और इसलिए यह शून्य, एक हो सकता है या दो बच्चों को ज़्यादा से ज़्यादा. 

मुझे लगता है हम नोड लागू प्रस्ताव करेंगे कि एक int n के साथ कि संरचना के लिए, और फिर दो संकेत, एक बुलाया छोड़ दिया, एक सही कहा जाता है. लेकिन उन सिर्फ अच्छे हैं मनमाना सम्मेलनों. और तुम, खासकर अगर अब अच्छा क्या है तरह के साथ धारणात्मक संघर्ष प्रत्यावर्तन, या यह नहीं सोचा था कि वास्तव में एक कुछ भी करने के लिए समाधान, विशेष रूप से अगर तुम सकता है स्मृति से बाहर चला. हम डेटा के बारे में बात कर रहे हैं अब कि अनुमति देते हैं कि संरचनाओं और एल्गोरिदम हमें उन्हें पार और हेरफेर करने के लिए, प्रत्यावर्तन में वापस आता है पता चला है कि एक अधिक सम्मोहक सुंदर तरीका नहीं है. 

इसलिए मैं प्रस्ताव इस कार्यान्वयन है एक खोज समारोह का. दो आदानों दिया - तो एक ब्लैक बॉक्स के रूप में इस के बारे में सोच. दो आदानों, एन, एक पूर्णांक, और एक दिया एक पेड़, एक के लिए एक सूचक को सूचक एक पेड़ के नोड, या वास्तव में जड़, मैं इस समारोह में वापसी कर सकते हैं कि दावा सही है या गलत, कि मूल्य n इस पेड़ के अंदर है. 

इस ब्लैक बॉक्स के अंदर क्या है? खैर, चार शाखाएं हैं. पहले बस की जाँच करता है. पेड़ रिक्त है, तो सिर्फ झूठी वापसी. कोई नोड है, तो कोई पता नहीं है, कोई संख्या नहीं है, सिर्फ झूठी वापसी. हालांकि अगर, एन, मूल्य आप देख रहे हैं के लिए, पेड़ तीर n से भी कम है, और बस स्पष्ट होना, इसका मतलब क्या है जब मैं पेड़ और तब तीर लिखना अंकन, एन? बिल्कुल सही. ऐसा लगता है कि भिन्नता का मतलब सूचक पेड़ कहा जाता है. वहाँ जाओ, और फिर उस के अंदर मिल अपने क्षेत्र n नोड और कहा जाता हो. और तो था कि वास्तविक n तुलना इसके खिलाफ खोज में पारित कर दिया. 

तो एन एन मूल्य से कम है, तो वृक्ष नोड ही में, अच्छी तरह से, इसका क्या मतलब है? यही कारण है कि पहली नज़र में कोई मतलब नहीं है. है ना? आप में से एक सरणी है जैसे जब मूल्यों, आप द्विआधारी आवेदन करना चाहते हो सकता है विभाजन के एक फार्म के रूप में खोज और जीत. लेकिन हमें करना क्या धारणा जरूरत थी द्विआधारी खोज सब पर काम करने के लिए फोन की किताब में और पहले उदाहरण? 

हल हो कैसे. तो चलो पेड़ की परिभाषा को परिष्कृत करते हैं यहां सिर्फ एक पेड़ है, जो हो सकता है के लिए नहीं बच्चों के किसी भी नंबर है. इतना ही नहीं एक द्विआधारी पेड़, जो कर सकते हैं ज़्यादा से ज़्यादा 0, 1, या 2 है. लेकिन एक द्विआधारी खोज पेड़, या BST रूप में, कहने का सिर्फ एक अच्छा तरीका है जो एक बाइनरी पेड़ ऐसी है कि हर नोड के बाईं बच्चे, अगर मौजूद है नोड की तुलना में कम. और हर नोड के सही बच्चे, अगर मौजूद है, अधिक से अधिक है नोड खुद से भी. 

तो दूसरे शब्दों में, अगर तुम थे आकर्षित करने के लिए पेड़ बाहर, संख्या के सभी कर रहे हैं ध्यान से इस तरह से संतुलित है, ताकि अगर आप रूट के रूप में 55 है, 33 जा सकते हैं यह 55 से भी कम है क्योंकि इसके बाईं ओर. 77 इसकी सही वजह के लिए जा सकते हैं यह 55 से अधिक है. लेकिन अब, एक ही परिभाषा नोटिस यह मौखिक रूप से एक पुनरावर्ती परिभाषा है 33 के लिए आवेदन करना पड़ता है. 33 के बाएं बच्चे से कम होना चाहिए, और 33 का सही बच्चे, 44, होना चाहिए यह से भी बड़ा. 

तो यह एक द्विआधारी खोज वृक्ष है, और मैं एक छोटा सा का उपयोग कर, प्रस्ताव प्रत्यावर्तन, हम अब पता लगा सकते हैं. तो पता है कि मूल्य एन से कम है तो वर्तमान नोड, मैं जा रहा हूँ आगे और बाज़ी, तो बात है, और अभी तक जवाब में जो कुछ भी लौटने पर N के लिए खोज पेड़ के बाईं बच्चे. फिर सूचना है, इस समारोह बस एक नोड सितारा, एक उम्मीद एक नोड के लिए सूचक. तो निश्चित रूप से मैं बस पेड़ से कर सकते हैं नेतृत्व करेंगे, जो बाएँ तीर अन्य नोड के लिए मुझे. लेकिन उस नोड क्या है? 

खैर, इस घोषणा के अनुसार, बाएँ, सिर्फ एक सूचक है कि इतना बस मैं खोज समारोह के लिए जा रहा हूँ इसका मतलब एक अलग सूचक, अर्थात् का प्रतिनिधित्व करता है कि एक मेरी बाईं बच्चे के पेड़. तो इस मामले में, 33 को सूचक, अगर यह हमारी नमूना इनपुट इस बीच, अगर है n पर मूल्य एन से अधिक है पेड़ में मौजूदा नोड, तो मैं कर रहा हूँ आगे बढ़ो और अन्य में बाज़ी के लिए जा रहा दिशा और बस का कहना है, मुझे नहीं पता इस मूल्य n पेड़ में पता है अगर, लेकिन मैं यह है, तो यह नीचे है पता मेरी सही शाखा, तो बात करो. तो मुझे खोज बारी बारी से फोन करते हैं, फिर एक एन गुजर रहा है, लेकिन एक में गुजर मेरा अधिकार बच्चे के लिए सूचक. 

दूसरे शब्दों में, मैं वर्तमान में हूँ अगर 55 पर और मैं 99 के लिए देख रहा हूँ, मुझे पता है कि 99 55 से अधिक है, तो मैं फाड़े बस की तरह फोन की किताब पहले सप्ताह और हम सही चला गया, इसी तरह हम कर रहे हैं यहीं से जाना जा रहा. यह मेरे अधिकार में है और अगर मैं नहीं जानता बच्चे, और यह 77 है, नहीं है, लेकिन मैं यह उस दिशा में पता है. इसलिए मैं अपने सही बच्चे पर खोज कॉल 77, और से खोज आंकड़ा बाहर जाने वहाँ अगर यह मनमाना में 99 उदाहरण वहाँ वास्तव में है. 

वरना, अंतिम मामला क्या है? पेड़ रिक्त है, तो एक मामला है. N मौजूदा नोड से कम है मूल्य एक और मामला है. N वर्तमान से अधिक है नोड के मूल्य एक तिहाई मामला है. चौथे और अंतिम मामला क्या है? मुझे लगता है हम मामलों से बाहर रहे हैं लगता है, है ना? यह एन में है कि होना चाहिए मैं कर रहा हूँ कि वर्तमान नोड. 

मैं इस बिंदु पर 55 के लिए खोज कर रहा हूँ तो अगर कहानी में, उस शाखा पेड़ सच लौटेंगे. तो क्या यहां दिलचस्प बात यह है कि हम दरअसल, सप्ताह के अतीत के विपरीत, हम प्रकार के दो आधार मामलों है. और वे की जरूरत नहीं है सभी शीर्ष पर हो. शीर्ष एक आधार मामला है क्योंकि अगर पेड़ क्या करने के लिए कुछ भी नहीं है, अशक्त है. बस एक कठिन कोडित लौटने झूठे का मूल्य. 

नीचे शाखा की तरह है Default, हम के लिए जाँच की है अगर जिससे यह होना चाहिए अगर अशक्त, हम जाँच की है छोड़ दिया है, लेकिन यह नहीं होना चाहिए, हम है यह यह सही होना चाहिए अगर जाँच की, लेकिन नहीं होना चाहिए, स्पष्ट रूप से यह हो गया है सही है कि हम कहाँ हैं. एक आधार है कि मामला है. तो दो पुनरावर्ती मामलों रहे है बीच में वहाँ बैठा. लेकिन मैं लिखा हो सकता है यह किसी भी क्रम में. मैं सिर्फ यह एक तरह से प्राकृतिक लगा सोचा पहले एक संभावित त्रुटि के लिए जाँच करने के लिए, फिर छोड़ दिया जाँच, तो फिर, सही जाँच आप नोड पर रहे हैं मान आप वास्तव में के लिए देख रहे हैं. 

तो क्यों यह उपयोगी हो सकता है? तो यह पता चला है - और मुझे एक नमूना करने के लिए कूद यहाँ कि वेब में है. हम नहीं एक का उपयोग शुरू करने जा रहे हैं प्रोग्रामिंग पहली बार में भाषा, लेकिन एक मार्कअप भाषा. है कि एक मार्कअप भाषा होने के नाते एक प्रोग्रामिंग करने के लिए भावना में समान भाषा, लेकिन यह आपको देना नहीं है तार्किक रूप से अपने आप को व्यक्त करने की क्षमता. यह केवल करने के लिए आप की क्षमता देता है संरचनात्मक रूप से अपने आप को व्यक्त करते हैं. 

आप कुछ करना चाहते हैं कहां पृष्ठ पर, वेब पेज? आप इसे बनाने के लिए क्या रंग चाहते हैं? क्या फ़ॉन्ट आकार आप इसे बनाने के लिए करना चाहते हैं? क्या शब्द जो आप वास्तव में क्या वेब पेज पर चाहते हैं? इसलिए कि एक मार्कअप भाषा है. लेकिन तब हम बहुत जल्दी से मिलवाता हूँ एक पूर्ण है जो जावास्क्रिप्ट, प्रोग्रामिंग भाषा. दिखने में बहुत समान वाक्य रचना सी करने के लिए, लेकिन यह कुछ होगा अच्छा, अधिक शक्तिशाली, अधिक उपयोगकर्ता के अनुकूल सुविधाओं. 

और इस पर कुंठा में से एक सेमेस्टर में बिंदु है हम हूँ कि जल्द ही अब तक कम में स्पेलर लागू अन्य भाषाओं का प्रयोग कोड की लाइनों सी ही अनुमति देता है की तुलना में, लेकिन कारण के लिए हम जल्द ही समझ में आ जाएगा. यह इस तरह की पहली वेब पेज होगी. यह पूरी तरह से underwhelming हो जाएगा, हम बनाने के लिए सबसे पहले एक. यह बस दुनिया नमस्ते, कहेंगे. लेकिन आप यह कभी नहीं देखा है इससे पहले, इस HTML है, हाइपरटेक्स्ट मार्कअप लैंग्वेज. 

आप में एक निश्चित मेनू विकल्प के लिए जाना है पर किसी भी वेब पेज पर सबसे अधिक किसी भी ब्राउज़र, इंटरनेट, आप HTML देख सकते हैं कुछ लोगों के लिए लिखा था कि उस वेब पेज बना सकते हैं. और यह शायद के रूप में नहीं लगती है संक्षिप्त या इस रूप में साफ. लेकिन यह इन के पैटर्न का पालन करेंगे खुले कोष्ठक और स्लैश और पत्र और संभावित संख्या. 

मुझे लगता है मैं तुम्हें एक नमूना देने लगा आप ऐसा करने में सक्षम हो जाएगा के CS50 लेने के बाद. मुझे / लूटने cs.harvard.edu के लिए चलते हैं, हमारे अपने रोब बोडेन के मुखपृष्ठ. उन्होंने कहा कि हमारे लिए यह कर दिया. तो आप जल्द ही ऐसा करने में सक्षम हो जाएगा. और यह भी, क्या तुमने सुना आज सुबह - आप इस सुबह क्या सुना - 

[हैम्स्टर नृत्य संगीत] 

- You'll इस बनाने में सक्षम हो. यही कारण है कि बुधवार को हमें इंतजार कर रहा है. हम आपको फिर देखेंगे. 

[हैम्स्टर नृत्य संगीत] डेविड मालन: अगले CS50 पर -