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

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

छात्र: [सुनाई]. 

स्पीकर 1: वह क्या है? 

छात्र: [सुनाई]. 

स्पीकर 1: निश्चित आकार. ठीक है, तो क्यों निश्चित आकार हालांकि अच्छा है? 

छात्र: [सुनाई]. 

स्पीकर 1: ठीक है, में यह कुशल है तो आप आवंटित कर सकते हैं कि भावना एक तय स्थान की मात्रा, जो उम्मीद ठीक के रूप में ज्यादा है आप चाहते हैं के रूप में अंतरिक्ष. तो यह है कि पूरी तरह से एक से अधिक हो सकता है. 

एक सरणी के एक और ऊपर की ओर हो रहा है? हाँ? 

छात्र: [सुनाई]. 

स्पीकर 1: सभी - क्षमा करें? 

छात्र: [सुनाई]. 

स्पीकर 1: स्मृति में सभी बक्से या एक दूसरे के बगल. और वह उपयोगी है - क्यों? यह काफी सच है. लेकिन हम कैसे है कि सच्चाई का दोहन कर सकते हैं? 

छात्र: [सुनाई]. 

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

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

लेकिन कुछ downsides हो गया है. क्या एक सरणी बहुत आसानी से कर नहीं? इसे अच्छा क्या नहीं है? 

छात्र: [सुनाई]. 

स्पीकर 1: वह क्या है? 

छात्र: [सुनाई]. 

स्पीकर 1: आकार में विस्तार. तो सरणी के downsides रहे हैं क्या ठीक विपरीत upsides हैं. तो downsides में से एक है यह एक निश्चित आकार है कि. तो आप वास्तव में इसे विकसित नहीं कर सकता. आप एक बड़ा हिस्सा के reallocate कर सकते हैं स्मृति, और फिर पुराने तत्व स्थानांतरित नई सरणी में. और फिर, पुराने सरणी मुक्त उदाहरण के लिए, malloc या इसी तरह का उपयोग करके realloc बुलाया समारोह, जो स्मृति reallocates. 

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

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

छात्र: [सुनाई]. 

स्पीकर 1: एक चर और एक सूचक, या अधिक विशेष रूप से, एक पूर्णांक, एन के लिए, और तल पर एक सूचक. उन दोनों में, 32 बिट्स होना होगा इस CS50 तरह एक कंप्यूटर पर कम से कम उपकरण, और इसलिए वे कर रहे हैं आकार में समान रूप से तैयार की गई. 

तो क्या सूचक का उपयोग कर रहे हैं जाहिरा तौर पर भले के लिए? सरणियों थे जब क्यों अब इस तीर जोड़ इतना अच्छा और साफ और सरल? के लिए कर रही सूचक क्या है इन नोड्स में से प्रत्येक में हमें? 

छात्र: [सुनाई]. 

स्पीकर 1: बिल्कुल. यह आप कह रही है जहां अगले एक है. तो मैं की तरह सादृश्य का उपयोग के आधार पर क्रमबद्ध धागे का उपयोग एक साथ इन नोड्स धागा. और कहा कि हम साथ कर रहे हैं कि वास्तव में क्या है संकेत दिए गए हैं क्योंकि इनमें से प्रत्येक स्मृति का हिस्सा है या नहीं हो सकता है वापस वापस करने के लिए वापस, सन्निहित , राम के अंदर क्योंकि हर बार जब आप malloc कहावत कहते हैं, मुझे पर्याप्त दे यह हो सकता है, एक नए नोड के लिए बाइट्स यहां हो सकता है या यह यहाँ हो सकता है. यह यहाँ हो सकता है. यह यहाँ हो सकता है. आप अभी पता नहीं है. 

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

तो नकारात्मक पहलू, फिर, एक लिंक की गई सूची क्या है? हम कर रहे हैं एक कीमत क्या है जाहिरा तौर पर भुगतान? 

छात्र: [सुनाई]. 

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

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

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

और फिर अंत में, आप सम्मिलित करना चाहते हैं सूची के अंत में कुछ है, यह है और भी आसान. यह मनमाना अंकन की तरह है लेकिन 34 के सूचक, एक अनुमान ले. अपने सूचक का मूल्य क्या है सबसे सामान्य प्रकार के एक पुराने तरह तैयार वहाँ स्कूल एंटीना? 

छात्र: [सुनाई]. 

स्पीकर 1: यह शायद अशक्त है. और वास्तव में है कि एक लेखक की है अशक्त का प्रतिनिधित्व. और यह आप की वजह से पूरी तरह से अशक्त है एक के अंत जुड़ा हुआ जहां पता करने की जरूरत सूची आप निम्नलिखित रखना ऐसा न हो, और इन तीरों निम्न और निम्न कुछ कचरा मूल्य के लिए. तो अशक्त नहीं है कि वहाँ सूचित करेंगे संख्या 34 का सही करने के लिए अधिक नोड्स, इस मामले में. 

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

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

मुझे यहाँ के उपकरण करने पर चलते हैं. मुझे नामक एक फाइल खोल दो. शून्य डॉट घंटे की सूची. और कहा कि केवल परिभाषा हम शामिल सिर्फ इस डेटा के लिए एक पल पहले देखा था प्रकार एक नोड कहा जाता है. तो हम एक डॉट घंटे फाइल में डाल दिया है. 

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

मैं अब सूची शून्य डॉट ऊपर खुला सी, कुछ बातों पर ध्यान. यह कुछ हैडर फ़ाइलें शामिल अधिकांश जिनमें से हम पहले देखा है. यह अपने हैडर फ़ाइल शामिल है. 

और एक अलग रूप में, यही कारण है कि डबल है कोण करने के लिए विरोध के रूप में, यहाँ उद्धरण लाइन पर कोष्ठक कि मैं वहाँ पर प्रकाश डाला है? 

छात्र: [सुनाई]. 

स्पीकर 1: हाँ तो यह एक स्थानीय फाइल है. तो यह अपने खुद के एक स्थानीय फ़ाइल है अगर लाइन 15 पर, उदाहरण के लिए, आप का उपयोग दोहरे उद्धरण बजाय angled कोष्ठक की. 

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

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

अब मैं यहाँ कुछ प्रोटोटाइप मिल गया है. मैं जैसी सुविधाओं को लागू करने का निर्णय लिया विलोपन, सम्मिलन, खोज, और चंक्रमण - भर में पिछले अभी की जा रही पैदल दूरी सूची अपने तत्व बाहर मुद्रण. और अब यहाँ मेरे मुख्य दिनचर्या है. और हम पर बहुत अधिक समय खर्च नहीं होगा ये इस तरह की है, उम्मीद है क्योंकि अब तक पुरानी टोपी. 

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

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

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

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

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

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

के तेजी से आगे, तो, चलो हम पर नजर है कि समारोह एक नमूना के रूप में सोमवार को. इसलिए इस समारोह, मैं दावा है, के लिए खोज करता है पहले से सूची में एक तत्व एक, बुला तो उपयोगकर्ता उत्साह और एक वास्तविक INT पाने के लिए GetInt आप के लिए खोज करना चाहते हैं. 

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

तो अब वापस कोड में, आगे क्या होता है - पुनरावृति जब यह एक आम प्रतिमान है एक तरह से एक संरचना पर लिंक की गई सूची. मैं निम्नलिखित जबकि क्या करने जा रहा हूँ सूचक तो है, जबकि रिक्त करने के बराबर नहीं है मेरी उंगली कुछ अशक्त पर इंगित नहीं किया गया है मूल्य, सूचक तीर एन के बराबर होती है. हम n है कि पहले नोटिस हूँ क्या GetInts प्रति में टाइप उपयोगकर्ता यहां कहते हैं. 

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

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

छात्र: [सुनाई]. 

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

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

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

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

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

तो हम अन्य पर ध्यान केन्द्रित करना नहीं होगा डालने के कार्यान्वयन और हटाना और चंक्रमण, के पहले दो काफी शामिल हैं जो. और मैं इसे पाने के लिए काफी आसान लगता है मौखिक रूप से यह कर जब खो दिया है. लेकिन क्या हम यहाँ क्या कर सकता है कैसे निर्धारित करने की कोशिश नेत्रहीन ऐसा करने के लिए सबसे अच्छा. मैं प्रस्ताव करता हूं क्योंकि कि अगर हम इस मामले में तत्व सम्मिलित करना चाहते हैं मौजूदा सूची, जो पांच तत्व है - 9, 17, 22, 26, और 33 - मैं में इस लागू करने के लिए जा रहे थे कोड, मैं जाने के लिए विचार करने की जरूरत इस बारे में क्या कर रही. 

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

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

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

और अंत में, स्पष्ट बीच का मामला है दरअसल, बीच में, मैं करना चाहते हैं 23 ऐसा कुछ कहो डालें, कि चला जाता है 23 और 26 है, लेकिन बीच में अब चीजें एक छोटे से अधिक मिल शामिल वजह क्या संकेत परिवर्तित करने की जरूरत है? इसलिए 22 स्पष्ट रूप से बदलने की जरूरत वह अब 26 को इंगित नहीं कर सकते हैं. उन्होंने कहा कि नए नोड के लिए बात करने की जरूरत है कि मैं फोन करके आवंटित करने के लिए होगा malloc या कुछ बराबर. 

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

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

छात्र: [सुनाई]. 

स्पीकर 1: बिल्कुल. 26 पर इशारा करते हुए. मैं पहले से ही अद्यतन नहीं किया है लेकिन dammit 22 के इस आदमी को बात करने के लिए सूचक, और अब मैं आराम, अनाथों है सूची की, तो बात करो. आपरेशन के तो आदेश यहाँ महत्वपूर्ण होने जा रहा है. 

ऐसा करने के लिए मैं चुरा सकता है, छह स्वयंसेवकों का कहना है. और हम ऐसा नहीं कर सकते, तो चलो देखते हैं नेत्रहीन बजाय कोड के लिहाज से. और हम कुछ सुंदर तनाव है आप के लिए गेंदों आज. ठीक है, कैसे में एक, दो, के बारे में पीछे - वहाँ अंत पर. तीन, चार, तुम दोनों अंत पर लोग. और पांच, छह. ज़रूर. पांच और छह. सब ठीक है और हम आने देंगे तुम लोगों के लिए अगली बार. सब ठीक है, ऊपर की ओर आते हैं. 

आप यहाँ पहली बार कर रहे हैं के बाद से सब ठीक है,, आप awkwardly एक होना चाहते हैं यहाँ गूगल ग्लास में? ठीक है, तो, ठीक है, ग्लास, एक वीडियो रिकॉर्ड. ठीक है, तुम जाने के लिए अच्छे हैं. 

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

छात्र: बेन. 

स्पीकर 1: बेन? ठीक है, बेन, तुम सचमुच, पहले किया जाएगा. इसलिए हम आपके द्वारा भेजे जा रहे हैं चरण के अंत में. सब ठीक है, और आपका नाम? 

छात्र: जेसन. 

स्पीकर 1: जेसन, ठीक है तुम हूँ संख्या नौ हो. तो तुम बेन कि जिस तरह से पालन करना चाहते हैं. 

छात्र: जिल. 

स्पीकर 1: जिल, तुम हो जा रहे हैं 17, जो मैं इस अधिक किया था अगर समझदारी से, मैं होता दूसरे छोर पर शुरू कर दिया. तुम उस तरह से जाना. 22. और आप कर रहे हैं? 

छात्र: मरियम. 

स्पीकर 1: मैरी, आप 22 हो जाएगा. और तुम्हारा नाम क्या है? 

छात्र: क्रिस. 

स्पीकर 1: क्रिस, आप 26 हो जाएगा. और फिर अंत में. 

छात्र: डायना. 

स्पीकर 1: डायना, आप 34 हो जाएगा. तो आप यहाँ पर आते हैं. 

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

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

ऐसा लगता है, सबसे पहले, मैं बंद बांधना चाहते हैं डालने का है कि पहले उदाहरण कहते हैं, 20, सूची में. इसलिए मैं किसी की जरूरत के लिए जा रहा हूँ हमारे लिए नंबर 20 अवतार लेना. इसलिए मैं किसी malloc करने की जरूरत है दर्शकों से. ऊपर आओ. तुम्हारा नाम क्या है? 

छात्र: ब्रायन. 

स्पीकर 1: ब्रायन, ठीक है, तो आप 20 युक्त नोड होगा. सब ठीक है, यहाँ पर आते हैं. और जाहिर है, जहां ब्रायन का है? तो, के बीच में - वास्तव में, एक मिनट रुको. हम आदेश से बाहर यह कर रहे हैं. हम एक बहुत कठिन यह कर रहे हैं यह पहली बार में होने की जरूरत की तुलना में. ठीक है, हम ब्रायन मुक्त करने के लिए जा रहे हैं और के रूप में पांच realloc ब्रायन. 

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

छात्र: जेसन. 

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

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

सब ठीक है, तुम हो तो कुछ उम्मीदवारों. बेन या मैं या ब्रायन या जेसन या तो वरना हर कोई है, जो संकेत बदलने की जरूरत है? कुल कितने? 

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

कौन किसके में बताया जाता है? 

छात्र: [सुनाई]. 

स्पीकर 1: ठीक है तो ब्रायन है जेसन पर बात करने के लिए. लेकिन मुझे लगता है कि सूचक का ट्रैक खो दिया है? जेसन है जहाँ मैं पता है? 

छात्र: [सुनाई]. 

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

ठीक है, तो बहुत सीधा. हम लगभग कर रहे हैं वास्तव में, लगता है यह बहुत जटिल बना रही है. तो चलो अब अंत बंद बांधना जाने सूची की, और देखो, जहां जटिलता शुरू होता है. अब तो, अगर मैं दर्शकों से alloc. किसी को 55 खेलना चाहते हैं? ठीक है, मैं पहली बार अपने हाथ को देखा. ऊपर आओ. हाँ. तुम्हारा नाम क्या है? 

छात्र: [सुनाई]. 

स्पीकर 1: Habata. ठीक है, ऊपर की ओर आते हैं. आप संख्या 55 हो जाएगी. तो आप, बेशक, संबंधित सूची के अंत में. तो चलो मेरे साथ अनुकरण ही पुन: चलो बस एक पल के लिए पीटीआर जा रहा है. तो मैं पहली बार में बात करने के लिए जा रहा हूँ जो कुछ भी है बेन तरफ इशारा करते हुए. हम दोनों ब्रायन पर अब इशारा कर रहे हैं. इसलिए 55 पांच से भी कम नहीं है. इसलिए मैं अपने आप को अद्यतन करने के लिए जा रहा हूँ ब्रायन के अगले सूचक, की ओर इशारा करते हैं, जो अब कोर्स जेसन की है. 55 तो, कम से कम नौ नहीं है मैं पीटीआर अद्यतन करने के लिए जा रहा हूँ. मैं पीटीआर अद्यतन करने के लिए जा रहा हूँ. मैं अद्यतन करने के लिए जा रहा हूँ पीटीआर मैं पीटीआर अद्यतन करने के लिए जा रहा है. हम्म, क्या है - और मैं जा रहा हूँ अपना नाम फिर से? 

छात्र: डायना. 

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

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

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

छात्र: [सुनाई]. 

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

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

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

छात्र: [सुनाई]. 

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

चलो यहाँ अंतिम उदाहरण करते हैं और डाल उनके दुख से बाहर इन लोगों को. 20 तो malloc. वहाँ गलियारे से चलो. सब ठीक है, तुम्हारा नाम क्या है? 

छात्र: [सुनाई]. 

स्पीकर 1: क्षमा करें? 

छात्र: [सुनाई]. 

स्पीकर 1: Demeron? ठीक ऊपर की ओर आते हैं. आप 20 हो जाएगी. आप स्पष्ट रूप से लिए जा रहे हैं 17 और 22 के बीच के हैं. तो मुझे मेरे सबक सीखते हैं. मैं सूचक शुरू करने जा रहा हूँ ब्रायन तरफ इशारा करते हुए. और मैं अपने बाएँ हाथ के लिए जा रहा हूँ मैं करने के लिए कदम के रूप में केवल ब्रायन करने के लिए अद्यतन जेसन, चेकिंग नौ से 20 कम करता है? नहीं. 17 से 20 कम है? नहीं. 22 से 20 कम है? हां. तो क्या संकेत या हाथ को बदलने की जरूरत जहां वे अब इशारा कर रहे हैं? 

इसलिए हम 20 में 17 इशारा कर सकते हैं. तो यह ठीक है. कहां हम बात करना चाहते हैं अपने सूचक अब? 22 पर. 22 फिर, धन्यवाद और जहां हम जानते हैं मेरे अस्थायी सूचक है. इसलिए हम वहाँ ठीक हो. तो इस वजह से अस्थायी भंडारण की मैं हर किसी को है, जहां का ट्रैक रखा है. और अब आप नेत्रहीन जहां में जा सकते हैं आप हैं, और अब हम 1 आवश्यकता, 2, 3, 4, 5, 6, 7, 8, 9 तनाव गेंदों, और के लिए प्रशंसा का एक दौर इन लोगों को, हम कर सकते हैं. अच्छी तरह से किया. 

[वाहवाही] 

स्पीकर 1: सब ठीक है. और तुम टुकड़े रख सकते हैं स्मृति चिन्ह के रूप में कागज की. 

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

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

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

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

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

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

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

इसलिए हम कुल आकार 26 के एक सरणी है अगर इस 25 वें स्थान इतना है कि तल में, और मैं ऐलिस का दावा है कि के शब्दकोश में पहला शब्द मैं राम में सम्मिलित करना चाहते हैं कि नाम, इस डेटा संरचना में, जहां हैं आप कह रही प्रवृत्ति है कि ऐलिस नाम इस सरणी में जाना चाहिए? 

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

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

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

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

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

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

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

तो ठीक है, मैं इसे ठीक कर देंगे. यहाँ समस्या है कि मैं था है इस सरणी में 26 तत्वों. मुझे इसे बदल दे. वूप्स. मेरे होने का इतना है कि बजाय इसे बदल दो. कुल आकार 26, नीचे नोटिस सूचकांक एन शून्य से 1 के लिए बदलने जा रहा है. 26 मनुष्यों के लिए स्पष्ट रूप से 'बहुत छोटा है नाम, क्योंकि वहाँ हजारों की दुनिया का नाम, चलो बस कर देना 100 या 1000 या 10,000 में. बस एक बहुत अधिक जगह आवंटित करते हैं. 

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

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

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

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

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

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

छात्र: [सुनाई]. 

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

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

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

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

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

तो पता CS50 छात्रों के एक कमरे में, क्या हो रहा है संभावना है कि कम से कम कमरे में दो छात्रों एक ही जन्मदिन है? तो क्या हुआ नहीं है. कुछ Hund - यहाँ और कई 200, 300 लोग घर पर सौ लोगों को आज. तुम क्या अपने आप से पूछना चाहता था तो अगर दो लोगों की संभावना इस कमरे में एक ही जन्मदिन होने, हम यह समझ सकते हैं. और मैं वास्तव में वहाँ दो हैं दावा एक ही जन्मदिन के साथ लोगों को. 

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

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

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

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

और इस वक्र से takeaway है कि जैसे ही आप 40 की तरह करने के लिए मिल के रूप में छात्रों, आप एक 90% संभावना पर रहे दो की combinatorically लोग या अधिक होने एक ही जन्मदिन. और अगर आप इसे 58 लोगों को पसंद करने के लिए एक बार एक मौका दो के लगभग 100% कमरे में लोगों के पास जा रहे हैं एक ही जन्मदिन, भले ही वहाँ 365 या 366 संभव बाल्टी, और कमरे में केवल 58 लोग हैं. बस सांख्यिकीय आप की संभावना हो टक्कर मिल जो संक्षेप में इस चर्चा को प्रेरित. यही कारण है कि हम यहाँ कल्पना, और यहां तक ​​कि अगर इन जंजीरों होने शुरू, हम अभी भी कर रहे हैं collisions के लिए किया जा रहा. 

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

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

में से प्रत्येक की संभावना लंबाई क्या है उन सूचियों हम एक अच्छा साफ मान जेड के माध्यम से नाम किसी का वितरण पूरे डेटा संरचना के पार? डेटा संरचना में पता लोगों को नहीं है वे अच्छी तरह से कर रहे हैं, 26 से विभाजित पूरे पर फैलाए डेटा संरचना. इसलिए इनमें से प्रत्येक की लंबाई चेन एन 26 से विभाजित है. लेकिन बड़ी हे संकेतन में, वो क्या है? कि वास्तव में क्या है? तो यह ठीक है, अभी पता सच है? हम अतीत में कहा है, क्योंकि कि आप 26 से विभाजित ऊ. हाँ, वास्तविकता में यह तेजी से होता है. लेकिन सिद्धांत रूप में, यह मौलिक नहीं है तेजी से लगता है कि सभी. 

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

छात्र: [सुनाई]. 

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

छात्र: [सुनाई]. 

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

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

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

मुझे एक अलग प्रस्ताव दो. पूरी तरह समाधान. और यह आपके दिमाग उड़ा नहीं करता है, हम डेटा संरचनाओं से बाहर रहे हैं. तो यह है कि यह एक Trie है - एक बेवकूफ नाम की तरह. यह retrievals से आता है, और शब्द Trie, T-R-I-ई, क्योंकि की वर्तनी है बेशक पुनर्प्राप्ति Trie की तरह लगता है. लेकिन वह इतिहास है शब्द Trie की. 

तो एक Trie वास्तव में पेड़ के कुछ प्रकार है, और यह भी कि शब्द पर एक नाटक है. और आप काफी यह नहीं देख सकते हैं, भले ही इस दृश्य के साथ, एक Trie एक है पेड़ के साथ एक परिवार के पेड़ की तरह, संरचित शीर्ष और बहुत कम एक पूर्वज पोते और महान पोते की तल पर छोड़ देता है. लेकिन एक Trie में प्रत्येक नोड एक सरणी है. और यह एक सरणी में है - और चलो एक पल के लिए oversimplify - यह एक है सरणी, इस मामले में, आकार 26 की, जहां प्रत्येक नोड फिर से आकार की एक सरणी है 26, जहां कि में zeroth तत्व सरणी का प्रतिनिधित्व करता है, और पिछले ऐसे प्रत्येक में तत्व सरणी जेड का प्रतिनिधित्व करता है 

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

छात्र: [सुनाई]. 

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

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

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

के रूप में निम्नानुसार तो हम ऐसा कर सकते हैं. चित्र में नोड्स में से प्रत्येक हम बस देखा एक, आकार 27 की एक सरणी है. पी में छह सेट और क्योंकि यह अब 27 है हम वास्तव में आप एक apostrophe देता हूँ, इसलिए हम ओ रेली जैसे नाम हो सकता है और apostrophes के साथ अन्य. लेकिन एक ही विचार है. में उन तत्वों के प्रत्येक एक संरचना करने के लिए सरणी अंक नोड, तो बस एक नोड. तो यह बहुत याद ताजा करती है हमारे लिंक की गई सूची की. 

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

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

छात्र: [सुनाई]. 

स्पीकर 1: हाँ, यह लंबाई नाम की, है ना? तो एम एक-X-W-E-L-L यह इस तरह लगता है तो एल्गोरिथ्म सात की बड़ी हे है. अब, ज़ाहिर है, के नाम लंबाई में अलग अलग होंगे. हो सकता है कि यह एक छोटा नाम है. हो सकता है कि यह एक लंबे समय तक नाम है. लेकिन क्या यहां महत्वपूर्ण यह है कि यह एक निरंतर संख्या है. और हो सकता है यह, वास्तव में स्थिर नहीं है लेकिन भगवान, वास्तविक हैं, में एक , कुछ सीमा शायद शब्दकोश वहाँ एक में पत्र की संख्या पर किसी विशेष देश में व्यक्ति का नाम. 

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

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

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

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

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

वह एक संदेश के साथ आया था. एक प्रोटोकॉल सभी अपने स्वयं के साथ. वह क्रूर फायरवॉल की दुनिया के लिए आया था, बेपरवाह रूटर, और खतरों दूर मौत से भी बदतर. वह तेजी से है. वह मजबूत है. उन्होंने TCPIP है. और उसने अपना पता मिल गया है. नेट के योद्धाओं. 

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

स्पीकर 1: यह है कि कैसे इंटरनेट है अगले सप्ताह के रूप में काम करेगा.