[संगीत खेल] डेविड Malan: यह CS50 है. और यह शुरुआत है और दोनों है literally-- लगभग अंत की तरह end-- सप्ताह छह की. 

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

दर्शक: [अश्राव्य] डेविड Malan: वास्तव में. और अधिक Amusingly, भगवान न करे, हम शुक्रवार को एक व्याख्यान पकड़ सत्र की शुरुआत में, कि हम हो क्या देखते है. तो आज, हम एक बिट में हिस्सा लेना डेटा संरचनाओं के बारे में अधिक. और अगर आप एक ठोस का अधिक देने के लिए पांच में समस्याओं के लिए मानसिक मॉडल, जो अब बाहर है. गलतियाँ, जिसमें, हम करेंगे आप एक पाठ फ़ाइल हाथ कुछ 100,000 प्लस अंग्रेजी शब्द, और आप के लिए जा रहे हैं चतुराई से उन्हें लोड करने के लिए बाहर निकालने के लिए स्मृति में, राम में, कुछ डेटा का उपयोग अपनी पसंद की संरचना. 

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

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

डेविड Malan: निवेशन. आपको लगता है कि क्या मतलब है? 

दर्शकों: कहीं भी साथ सूची [अश्राव्य]. 

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

और क्या फायदेमंद था एक लिंक की गई सूची के बारे में? हाँ? 

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

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

दर्शक: कोई रैंडम एक्सेस. 

डेविड Malan: नहीं रैंडम एक्सेस. लेकिन कौन परवाह करता है? रैंडम एक्सेस सम्मोहक आवाज नहीं करता है. 

दर्शक: [अश्राव्य] डेविड Malan: बिल्कुल. आप करना चाहते हैं एक निश्चित algorithm-- और मुझे वास्तव में प्रस्ताव विशेष रूप से बाइनरी खोज, जो हम काफी bit-- का उपयोग किया है एक है आप बिना सोचे समझे नहीं है, आपको लगता है कि सरल गणित नहीं कर सकते मध्य तत्व की तरह खोजने की और इसे ठीक करने के लिए कूद. आप के बजाय पहली बार में शुरू कर दिया है तत्व और रैखिक बाएं से खोज सही करने के लिए आप खोजना चाहते हैं मध्यम या किसी भी अन्य तत्व. 

दर्शक: यह शायद अधिक स्मृति लेता है. 

डेविड Malan: अधिक स्मृति ले जाता है. कहां कि अतिरिक्त है स्मृति में से आने वाले खर्च? 

दर्शक: [अश्राव्य] डेविड Malan: बिल्कुल. यहां इस मामले में, हम था पूर्णांकों के लिए एक लिंक की गई सूची, और अभी तक हम दोगुना कर रहे हैं स्मृति की राशि हम भी ये संकेत भंडारण के द्वारा की जरूरत है. के रूप में एक बड़ी बात के अब कम अपने structs बड़ा हो और तुम नहीं एक संख्या भंडारण कर रहे हैं लेकिन शायद एक छात्र या कोई अन्य वस्तु. लेकिन मुद्दा यह निश्चित रूप से बनी हुई है. और तो आपरेशनों के एक नंबर लिंक सूचियों पर बुलाया गया n-- रेखीय की बड़ी हे थे. प्रविष्टि या खोज जैसे हालात या मामला एक तत्व में विलोपन के बहुत अंत में होने का क्या हुआ इसे हल या नहीं है कि क्या सूची. 

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

ठीक है, तुम मुझे पसंद कर रहे हैं, तो आप इस मीटर है कि देख सकते हैं, इसलिए मुझे लगता है, की तरह में इस डाल करने के लिए जा रहा हूँ यह मेरी मेज या मेरी मंजिल जहां अगर मैं चीजों फैल रहा हूँ out-- या मेरे सरणी really-- मैं वहाँ में सुश्री के सभी डाल सकता है. ओह. यहाँ एक ए तो मैं हो सकता है यहाँ के रूप में डाल दिया. ओह. यहाँ मैं जा रहा हूँ एक और ए है यहाँ पर डाला कि. यहाँ एक जेड यहाँ एक और एम और इसलिए है मैं इस तरह की ढेर बनाना शुरू कर सकता है. और फिर शायद मैं बाद में जाना चाहते हैं और तरह की बहुत nitpicky-ly क्रमबद्ध व्यक्तिगत बवासीर. लेकिन बात मैं देखना होगा है मैं हाथ हूँ कि इनपुट पर और मैं कुछ गणना करना होगा कि इनपुट के आधार पर निर्णय. यह एक साथ शुरू होता है, वहाँ पर डाल दिया. यह जेड के साथ शुरू होता है, इस पर डाल बीच में वहाँ, और सब कुछ. 

तो यह है कि एक तकनीक है आम तौर पर hashing-- एच-ए-एस-H-- के रूप में जाना जो आम तौर पर के रूप में लेने का मतलब इनपुट और गणना करने के लिए है कि इनपुट का उपयोग एक मूल्य, आम तौर पर एक संख्या है, और है कि नंबर एक भंडारण में सूचकांक है कंटेनर, एक सरणी की तरह. तो दूसरे शब्दों में, मैं एक हो सकता है हैश समारोह, मैं अपने दिमाग में कर के रूप में, मैं किसी के देखते हैं कि एक साथ शुरू होता है जो नाम, मुझे लगता है कि नक्शा करने के लिए जा रहा हूँ मेरे सिर में शून्य करने के लिए. मैं जेड के साथ किसी को देखते हैं, मैं हूँ मेरे सिर में से 25 कि नक्शा करने के लिए जा रहा और फिर उस में डाल पिछले सबसे ढेर. 

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

दर्शक: माइनस ए 

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

तो क्या आप परिक्रमा की याद हो सकता है आपके कवर पर शिक्षण साथी का नाम. और TF के नाम का आयोजन किया गया वर्णानुक्रम इन स्तंभों में, खैर, यह विश्वास है या नहीं, जब हम में से सभी 80 प्लस , ग्रेड के लिए रात को एक साथ मिला हमारे ग्रेडिंग प्रक्रिया में अंतिम चरण एक बड़ा में क्विज़ हैश है [अश्राव्य] पर मंजिल की अंतरिक्ष और हर किसी की क्विज़ बाहर करना उनके TF के बिल्कुल क्रम में कवर पर नाम, क्योंकि तो यह हमारे लिए एक बहुत आसान है उस का उपयोग रैखिक के माध्यम से खोज करने के लिए खोज या चालाकी से किसी तरह एक TF खोजने के लिए अपने या उसे छात्रों के क्विज़. 

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

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

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

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

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

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

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

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

दर्शकों: एन. डेविड Malan: मैं n की बड़ी हे सुना. यह सही नहीं है. लेकिन हम अलग तंग करेंगे क्यों सिर्फ एक पल में. यह और क्या हो सकता है? 

दर्शक: [अश्राव्य] डेविड Malan: और मुझे नेत्रहीन करते हैं. इसलिए इस पत्र एस लगता है 

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

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

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

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

दर्शक: लिंक की गई सूची. 

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

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

अब यह एक छोटी सी है बेहतर तकनीकी क्योंकि अब मेरी जंजीरों में हो सकता है सबसे खराब स्थिति कब तक? मैं इस अधिक में एन लोग सम्मिलित हैं परिष्कृत डेटा संरचना, एन लोग, सबसे खराब स्थिति में यह पता होने जा रहा है. क्यों? 

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

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

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

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

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

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

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

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

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

अब विकास किया जाता है. अब ए डी-ए-वी-ई-एन लक्ष्य है. तो अब मैं क्या करने जा रहा हूँ क्या है. जैसे ही मैं डी नोटिस शुरू वहाँ कोई सूचक नहीं है. यह क्षण में कचरा मूल्यों है या मैं अशक्त करने के लिए यह को प्रारंभ हो सकता है. लेकिन मेरे साथ जा रहा रखने के चलो एक पेड़ के निर्माण के इस विचार. मुझे इनमें से एक दूसरे का आवंटन करते हैं इसमें 26 तत्व है कि नोड्स. 

और तुम जानते हो क्या? इस स्मृति में सिर्फ एक नोड है कि मैं एक संरचना का उपयोग, malloc के साथ बनाया हम जल्द ही देखेंगे के रूप में, मैं this-- क्या करने जा रहा हूँ मैं से एक तीर आकर्षित करने के लिए जा रहा हूँ नीचे डी प्रतिनिधित्व कि बात इस नए नोड के लिए. और, पहले अगले अब दावेन के नाम पत्र, V-- डी-ए-V-- मैं आगे जाने के लिए जा रहा हूँ और इस तरह एक और नोड आकर्षित, जिससे, यहाँ वी तत्व, जो हम instance-- वूप्स के लिए आकर्षित करेंगे. हम वहाँ आकर्षित नहीं होगा. यह यहां जाने के लिए जा रहा है. 

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

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

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

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

या हम होना चाहते हैं वास्तव में उचित अब, क्या किसी के नाम के रूप में अगर एक apostrophe, चलो प्रत्येक नोड वास्तव में है कि मान इसमें 27 सूचकांकों में न सिर्फ 26 की तरह. तो यह अब एक डेटा होने जा रहा है संरचना एक trie-- टी आर-मैं-ई बुलाया. माना जाता है कि जो एक Trie, एक पेड़ के लिए ऐतिहासिक एक चालाक नाम उस के लिए अनुकूलित है पुनः प्राप्ति, जो जाहिर है, यह Trie है तो एक मैं-ई के साथ वर्तनी है. लेकिन उस Trie का इतिहास है. 

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

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

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

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

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

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

अब, ओह प्रश्न Meanwhile--. 

दर्शक: bool शब्द क्या है? 

डेविड Malan: bool शब्द है सिर्फ इस सी अवतार मैं क्या वर्णित की यहाँ, जब इस बॉक्स में मैं के प्रत्येक बंटवारे शुरू दो टुकड़ों में सरणी के तत्वों. एक अगले नोड के लिए एक संकेत है. अन्य हो गया है एक चेक बॉक्स की तरह कुछ एक वहाँ है, हाँ कहने के लिए यहाँ समाप्त होती है कि दावेन शब्द, , हम नहीं चाहते क्योंकि पल, डेव पर. 

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

कोशिश करता है पर कोई अन्य प्रश्न? हाँ. 

दर्शक: ओवरलैप क्या है? क्या आप एक डेव और एक दावेन है तो क्या होगा? डेविड Malan: बिल्कुल सही. क्या आप एक डेव और एक दावेन है तो क्या होगा? हम डालें तो, अगर, एक उपनाम का कहना है David-- Dave-- डी-ए-वी-ई के लिए? यह वास्तव में सुपर सरल है. इसलिए हम केवल चार कदम उठाने जा रहे हैं. डी-ए-वी-ई. और मैं करने के लिए क्या है मुझे लगता है कि चौथे नोड मारा एक बार करते हैं? बस की जांच करने जा रही है. हम पहले से ही जाने के लिए अच्छे हैं. डन. चार चरणों. Asymptotically लगातार समय. और अब हम कि दोनों दवे ने संकेत दिया है और दावेन संरचना में तार कर रहे हैं. तो कोई समस्या नहीं है. और कैसे उपस्थिति नोटिस दावेन का नहीं बना था किसी भी अधिक समय या उससे कम ले समय डेव के लिए और इसके विपरीत. 

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

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

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

अब एक पंक्ति बहुत जानबूझ नाम पर है. क्योंकि वहाँ यह एक रेखा है यह करने के लिए कुछ निष्पक्षता. है ना? आप है, तो यह एक तरह से चूसा होगा एप्पल स्टोर पर वहाँ पहले मिला लेकिन आप को प्रभावी ढंग से नीचा कर रहे हैं ट्रे तो एप्पल कर्मचारियों क्योंकि अंतिम व्यक्ति पॉप कौन वास्तव में लाइन में मिला है. ढेर और कतार, भले ही तो कार्यात्मक वे same-- की तरह कर रहे हैं यह सिर्फ इस संग्रह है संसाधनों की है कि वहाँ है shrink-- बढ़ती जा रही है और यह करने के लिए इस निष्पक्षता पहलू, असली दुनिया में कम से कम, जहां आपरेशन आप व्यायाम मौलिक रूप से अलग हैं. एक कतार एक stack-- rather-- है कहा जाता है दो ऑपरेशन: N कतार और डी कतार. या आप उन्हें कॉल कर सकते हैं चीजों के किसी भी संख्या. लेकिन तुम सिर्फ कब्जा करना चाहते हैं एक जोड़ने का है कि धारणा और एक अंत में घटाकर है. 

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

दर्शक: एक कतार. डेविड Malan: ठीक है, एक कतार. ज़रूर. और क्या? 

दर्शक: एक लिंक सूची. 

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

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

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

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

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

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

दर्शक: बाईं तरफ के छोटे वाले. 

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

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

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

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

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

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

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

[वीडियो प्लेबैक] 

-वह, एक संदेश के साथ आया था सब अपने ही एक प्रोटोकॉल के साथ. वह क्रूर की एक दुनिया के लिए आया था फायरवॉल, बेपरवाह राउटर, और खतरों मौत से भी बदतर. वह तेजी से है. वह मजबूत है. उन्होंने कहा कि टीसीपी / आईपी है, और वह अपना पता मिल गया है. "नेट के योद्धाओं." [अंत वीडियो प्लेबैक] डेविड Malan: अगले हफ्ते आ रहा है. हम आपको फिर देखेंगे. [वीडियो प्लेबैक] -और अब, "गहरे विचार" दावेन Farnham द्वारा. -David हमेशा शुरू होता है साथ व्याख्यान "ठीक है." क्यों नहीं, "यहाँ समाधान है इस हफ्ते की समस्या सेट करने के लिए " या "हम एक ए आप सब दे रहे हैं?" [हंसते हुए] [अंत वीडियो प्लेबैक]