>> [संगीत बजाना]
>> ANDI PENG: खंड के 6 सप्ताह के लिए आपका स्वागत है।
हम अपने मानक से भटक मंगलवार की धारा समय
इस सुंदर रविवार की सुबह को दोपहर।
हर किसी के लिए धन्यवाद कि , आज, लेकिन मुझे गंभीरता से शामिल हो गए
प्रशंसा का एक दौर।
>> यह एक बहुत बड़ा प्रयास है।
मैं लगभग भी नहीं बना था समय में है, लेकिन यह ठीक था।
इसलिए मैं आप की है कि सभी जानते हैं सिर्फ प्रश्नोत्तरी में जगह बनाई है।
सब से पहले, आपका स्वागत है उस का दूसरा पहलू।
>> दूसरे, हम इस बारे में बात करेंगे।
हम प्रश्नोत्तरी के बारे में बात करेंगे।
हम कैसे के बारे में बात करेंगे आप कक्षा में क्या कर रहे हैं।
आप ठीक होगे।
मैं अपने परीक्षाएँ के लिए है यहाँ के अंत में आप,
तो तुम लोग लेना चाहते हैं एक, उस पर पूरी तरह से ठीक लग रही है।
>> तो जल्दी से हम शुरू करने से पहले इस प्रकार के रूप में आज के लिए एजेंडा है।
आप देख सकते हैं, हम कर रहे हैं मूल रूप से तेजी से गोलीबारी
डाटा संरचनाओं की एक पूरी गुच्छा के माध्यम से सच में, सच, सच में जल्दी।
जैसे तो, यह नहीं होगा सुपर इंटरैक्टिव आज।
यह सिर्फ मुझे एक तरह से चिल्ला हो जाएगा बातें है कि आप, और मैं आप को भ्रमित करते हैं,
मैं भी तेजी से जा रहा हूँ, मुझे पता है।
वे सिर्फ विभिन्न डेटा रहे संरचनाओं, और भाग के रूप में
इस के लिए अपने pset की आगामी सप्ताह, तुम हूँ
उनमें से एक को लागू करने के लिए कहा, शायद उनमें से दो them-- दो की
अपने pset में।
ठीक है, तो मैं बस करने के लिए जा रहा हूँ कुछ घोषणाओं के साथ शुरू करते हैं।
हम ढेर और अधिक में कतारों पर जायेंगे हम प्रश्नोत्तरी पहले किया था से अधिक गहराई।
हम खत्म हो जाने से जुड़ा हुआ हूँ , फिर से, एक बार फिर से सूची
से अधिक गहराई में क्या हम प्रश्नोत्तरी पहले था।
और फिर हम हैश के बारे में बात करेंगे टेबल, पेड़ और कोशिश करता है, जो
अपने सभी pset के लिए बहुत जरूरी हैं।
और फिर हम कुछ पर जायेंगे pset5 के लिए उपयोगी टिप्स।
>> ठीक है, तो प्रश्नोत्तरी 0।
औसत एक 58% थी।
यह बहुत कम था, और इसलिए आप लोग सब अनुसार बहुत, बहुत अच्छा प्रदर्शन किया था
उस के साथ।
>> अगर आप बहुत ज्यादा, अंगूठे का नियम है मतलब की एक मानक विचलन के भीतर
हम एक कम समय में कर रहे हैं, खासकर जब से आराम अनुभाग में, आप पूरी तरह से ठीक हो रहे हैं।
आप रास्ते पर हैं।
जीवन अच्छा है।
>> मैं यह लगता है कि डरावना है पता मैं इस प्रश्नोत्तरी पर एक 40% की तरह हो गया।
मैं इस वर्ग विफल करने के लिए जा रहा हूँ।
मैं तुमसे वादा करता हूँ, तुम नहीं हो वर्ग विफल करने के लिए जा रहा है।
तुम पूरी तरह से ठीक हैं।
>> खत्म हो गया जो आप में से उन लोगों के लिए मतलब, प्रभावशाली, प्रभावशाली,
जैसे, गंभीरता से अच्छी तरह से किया।
मैं उन्हें मेरे साथ है।
उन्हें पाने के लिए आने के लिए स्वतंत्र महसूस अनुभाग के अंत में।
अगर आप किसी भी मुझे पता है मुद्दों, उनके साथ सवाल।
हम अपने स्कोर को जोड़ अगर गलत, हमें पता है।
>> ठीक है, pset5 तो, यह एक सच है इस अर्थ में येल के लिए अजीब सप्ताह
हमारे pset कारण है कि सहित दोपहर में बुधवार को
देर दिन है, तो यह वास्तव में है मंगलवार दोपहर में सैद्धांतिक रूप से की वजह से।
शायद कोई भी समाप्त दोपहर में मंगलवार को।
यही कारण है कि पूरी तरह से ठीक है।
हम कार्यालय समय के लिए जा रहे हैं आज रात के साथ ही सोमवार रात।
और वर्गों के सभी इस सप्ताह होगा वास्तव में कार्यशालाओं में तब्दील किया जा,
इतने में पॉप करने के लिए स्वतंत्र महसूस आप चाहते हैं किसी भी वर्ग,
और वे एक तरह से मिनी pset हो जाएगा उस पर मदद के लिए कार्यशालाओं।
तो इस तरह के रूप में, यह केवल अनुभाग है जहां हम सामग्री अध्यापन कर रहे हैं।
अन्य सभी वर्गों ध्यान केंद्रित किया जाएगा विशेष रूप से pset के लिए मदद पर।
हाँ?
>> दर्शकों: जहां कार्यालय घंटे रहे हैं?
>> ANDI PENG: ऑफिस का समय , ओह अच्छा सवाल tonight--।
मुझे लगता है कि कार्यालय समय आज रात चैती में या कॉमन्स पर हैं।
आप ऑनलाइन CS50 जाँच हैं और आप, कार्यालय समय के लिए जाना
एक कार्यक्रम होना चाहिए कि उनमें से सभी कर रहे हैं, जहां आपको बताता है।
>> मैं आज रात या तो पता या कल चैती, है
और मुझे लगता है कि हम हो सकता है लगता है उस रात के लिए कॉमन्स।
मुझे यकीन नहीं है।
अच्छा प्रश्न।
CS50 पर जाँच करें।
>> के बारे में अच्छा है, किसी भी सवाल तीन दिनों की तरह अगले के लिए अनुसूची?
मैं दाऊद की तरह तुम लोगों को वादा इस पहाड़ी के ऊपर है, ने कहा।
तुम लोग लगभग देखते हैं।
बस तीन दिन।
वहाँ जाओ, और फिर हम सब नीचे आ जाएगा।
हम एक अच्छा सीएस मुक्त तोड़ने के लिए होगा।
फिर स्वागत है।
हम वेब में डुबकी हूँ प्रोग्रामिंग और विकास,
बहुत मज़ा कर रहे हैं कि चीजों की तुलना अन्य psets से कुछ के लिए।
और यह ठंडा हो जाएगा, और करेंगे हम बहुत मज़ा आता होगा।
हम और अधिक कैंडी होगा।
कैंडी के लिए क्षमा करें।
मैं कैंडी भूल गया।
यह एक किसी न किसी तरह सुबह थी।
तो तुम लोग, लगभग देखते हैं और मैं तुम लोगों की वास्तव में गर्व कर रहा हूँ।
>> ठीक है, तो ढेर।
कौन जैक के बारे में सवाल प्यार करता था और प्रश्नोत्तरी पर अपने कपड़े?
कोई नहीं?
ठीक है ठीक है।
>> तो अनिवार्य रूप से आप कर सकते हैं चित्र जैक, यहाँ इस आदमी,
कपड़े लेने के लिए प्यार करता है ढेर के ऊपर से बाहर,
और वह पर इसे वापस डालता वह बाद ढेर हो चुका है।
तो इस तरह से, वह कभी नहीं हो रही लगती है
की तह तक उसके कपड़ों में हो चुकी है।
तो इस तरह का वर्णन करता है बुनियादी डेटा संरचना
एक ढेर कार्यान्वित किया जाता है कैसे की।
>> मूलतः, एक के बारे में सोच वस्तुओं के किसी भी ढेर के रूप में ढेर
आप शीर्ष पर बातें करना, और जहां तो आप ऊपर से उन्हें बाहर पॉप।
तो LIFO हम चाहते परिचित करा रहा है अंत में, सबसे पहले आउट use-- करने के लिए।
और हां के शीर्ष करने में पिछले ढेर बाहर आता है कि पहले से एक है।
और तो दो शब्दों हम सहयोगी की तरह
उस के साथ धक्का और पॉप कहा जाता है।
जब आप पर कुछ धक्का ढेर, और आप इसे वापस पॉप।
>> और इसलिए मैं इस एक की तरह लगता है आप उन लोगों के लिए अमूर्त अवधारणा
जो एक तरह से देखना चाहते हैं इस के वास्तविक क्रियान्वयन
असली दुनिया में।
आप में से कितने एक निबंध लिखा है शायद एक घंटे की तरह यह कारण था पहले
और अगर आप गलती से एक विशाल हटाए गए गलती तरह की यह हिस्सा?
और फिर क्या नियंत्रण करना हम इसे वापस डाल करने के लिए प्रयोग करते हैं?
नियंत्रण-जेड, हाँ?
नियंत्रण-जेड, इसलिए समय की राशि नियंत्रण-जेड मेरी जान बचाई है कि,
हर बार मेरे गधे को बचाया गया है कि एक ढेर के माध्यम से लागू किया है।
>> अनिवार्य रूप से सभी जानकारी कि, अपने वर्ड दस्तावेज़ पर है
यह धक्का दिया और इच्छा पर popped हो जाता है।
और तो अनिवार्य रूप से जब भी आप कुछ भी हटाने के लिए, आप इसे वापस पॉप।
और फिर आप इसे वापस की जरूरत है, तो आप नियंत्रण सी क्या करता है, जो इसे धक्का।
और तो असली दुनिया समारोह कैसे सरल डेटा संरचना की
अपनी रोजमर्रा की जिंदगी के साथ मदद कर सकते हैं।
>> तो एक संरचना तरीका है कि हम वास्तव में एक ढेर बना सकते हैं।
हम तो संरचना को परिभाषित टाइप करें, और हम यह नीचे में ढेर कहते हैं।
और ढेर भीतर, हम दो मापदंडों है
, हम अनिवार्य रूप से हेरफेर कर सकते हैं इसलिए हम चार स्टार तार की क्षमता है।
>> यह क्या कर रही है कि सभी एक सरणी पैदा कर रही है
हम चाहते हैं जो कुछ भी स्टोर कर सकते हैं जो हम अपनी क्षमता का निर्धारण कर सकते हैं।
क्षमता का सिर्फ अधिकतम राशि है आइटम हम इस सरणी में डाल सकते हैं।
पूर्णांक आकार रहता है कि काउंटर है कितने आइटम का ट्रैक वर्तमान में कर रहे हैं
ढेर में।
तो फिर हम एक के ट्रैक रख सकते हैं दोनों वास्तविक ढेर है कि कैसे बड़े,
और, बी, कैसे है कि ढेर के ज्यादा हम नहीं चाहते हैं क्योंकि हम भरा
हमारी क्षमता है पर अतिप्रवाह के लिए।
>> उदाहरण के लिए, इस सुंदर तो सवाल अपने प्रश्नोत्तरी पर था।
मूलतः कैसे हम धक्का करना एक ढेर के शीर्ष पर।
बहुत साधारण।
तुम इसे देखो तो, हम इस के माध्यम से चलना होगा।
[अश्राव्य] size-- हैं जब भी आपको याद
किसी भी उपयोग करना चाहते हैं एक संरचना के भीतर पैरामीटर,
आप struct.parameter के नाम से करते हैं।
>> इस मामले में, s है हमारे ढेर के नाम।
हम आकार का उपयोग करना चाहते हैं इसके बारे में है, तो हम s.size करते हैं।
आकार नहीं है तो के रूप में के रूप में लंबे समय तक क्षमता या के रूप में लंबे समय के बराबर
यह क्षमता से भी कम है, के रूप में यहाँ या तो काम करेगा।
>> तुम अंदर उपयोग करना चाहते हैं अपने ढेर की, s.strings तो,
और आपको लगता है कि नया नंबर डाल करने के लिए जा रहे हैं तुम वहाँ में सम्मिलित करना चाहते हैं।
चलो बस हम करना चाहते हैं जाएगा हम कहते हैं ढेर पर int n डालें,
हम s.strings कर सकता है कोष्ठक, s.size एन के बराबर होती है।
आकार जहां है, क्योंकि हम वर्तमान में ढेर में हैं
हम पुश करने के लिए जा रहे हैं उस पर, हम बस का उपयोग
आकार है, जहाँ कहीं भी ढेर की वर्तमान परिपूर्णता,
और हम इसे पर int n धक्का।
और फिर हम उस बनाना चाहते हम भी, एन के आकार बढ़ाने रहे
हम है की तो हम ट्रैक रख सकते हैं ढेर करने के लिए एक अतिरिक्त बात गयी।
अब हम एक बड़ा आकार है।
यहाँ यह समझ बनाने के लिए करता है हर कोई, कैसे तार्किक यह काम करता है?
यह एक तरह से जल्दी गया था।
दर्शकों: आप पर जा सकते हैं s.stringss.strings [s.size] फिर से?
ANDI PENG: यकीन है, तो क्या करता है हमें दे वर्तमान में s.size?
दर्शकों: यह वर्तमान आकार है।
ANDI PENG: बिल्कुल, इसलिए हमारे आकार में है कि मौजूदा सूचकांक,
और इसलिए हम नए पूर्णांक डाल करना चाहते हैं हम s.size में सम्मिलित करना चाहते हैं।
समझ आया?
S.strings क्योंकि, यह सब है सरणी का नाम है।
सभी यह है तक पहुँचने है हमारे संरचना के भीतर सरणी,
और इसलिए हम करना चाहते हैं कि सूचकांक में एन जगह है,
हम सिर्फ यह उपयोग कर सकते हैं का उपयोग कर कोष्ठक s.size।
कूल।
>> ठीक है, पॉप, मैं इसे बाहर pseudocode तुम लोगों को है, लेकिन इसी तरह की अवधारणा के लिए।
समझ आया?
आकार बड़ा है तो फिर शून्य, की तुलना में आप
आप कुछ लेने के लिए चाहते हैं कि पता बाहर आकार नहीं है क्योंकि अगर
शून्य से अधिक है, तो आप ढेर में कुछ भी नहीं है।
>> तो तुम ही अमल करना चाहते हैं इस कोड है, यह केवल कर सकते हैं
पॉप करने के लिए कुछ न कुछ है, तो पॉप।
आकार बड़ा है तो अगर 0 से, हम शून्य आकार।
हम आकार घटती और फिर वापस क्योंकि इसके अंदर जो कुछ भी है
popping द्वारा, हम करना चाहते हैं भंडारित किया जाता है जो कुछ भी पहुँच
ढेर के शीर्ष के सूचकांक में।
सब कुछ समझ बनाने के लिए?
मैंने बनाया है, तो आप दोस्तों, यह लिखने के बाहर आप लोग इसे बाहर लिखने में सक्षम हो सकता है?
ठीक है, तुम लोगों को यह आसपास के साथ खेल सकते हैं।
कोई चिंता नहीं है कि आप इसे नहीं मिलता है।
हम कोड के लिए समय नहीं है इसे बाहर आज हम है क्योंकि
इन संरचनाओं की एक बहुत कुछ मिला के माध्यम से जाना है, लेकिन अनिवार्य रूप से करने के लिए
स्यूडोकोड, बहुत, बहुत समान पुश करने के लिए।
बस तर्क के साथ पालन करें।
आप सभी तक पहुँच रहे हैं सुनिश्चित करें सही ढंग से अपनी संरचना की सुविधाओं।
हाँ?
>> दर्शकों: इन स्लाइड और इस पूरी बात को आज-ish हो सकता है?
ANDI PENG: हमेशा की तरह, हां।
मैं डाल करने की कोशिश करने के लिए जा रहा हूँ इस अप के बाद एक घंटे की तरह।
मैं दाऊद ईमेल करेंगे, डेविड करने की कोशिश करेंगे इस के बाद एक घंटे की तरह यह ऊपर डाल दिया।
>> ठीक है, तो फिर हम इस दूसरे में स्थानांतरित सुंदर डेटा संरचना एक कतार बुलाया।
तुम लोग यहाँ देख सकते हैं, एक कतार, हमारे बीच ब्रिटिश लिए,
यह सब एक पंक्ति है।
के विपरीत क्या आप एक ढेर है लगता है
एक कतार में वास्तव में क्या है तार्किक रूप से आपको लगता है कि।
यह फीफो के नियमों से आयोजित किया है जो पहले में, सबसे पहले आउट है।
जब आप पहली बार कर रहे हैं लाइन में से एक है, आप कर रहे हैं
पहले एक है कि रेखा के बाहर आता है।
>> इसलिए हम इस कॉल की तरह dequeueing और enqueueing है।
हम कुछ जोड़ना चाहते हैं हमारे कतार में, हम enqueue।
हम चाहते हैं विपंक्ति, या लेने के लिए कुछ दूर, हम विपंक्ति।
>> हम किस तरह का हो तो यह है कि एक ही अर्थ निश्चित आकार तत्वों बनाने कि हम
कुछ स्टोर कर सकते हैं बातें करते हैं, लेकिन हम भी कर सकते हैं
हम दे रहे हैं जहां बदल उनमें से अंदर मानकों को
किस प्रकार पर आधारित कार्यक्षमता हम चाहते हैं।
ढेर तो, हम पिछले चाहता था एक, एन पहले एक बाहर होने के लिए।
कतार हम पहले बात करना चाहते है में बाहर पहली बात हो।
>> संरचना प्रकार तो आप देख सकते हैं, को परिभाषित है,
यह एक छोटा सा अलग है ढेर क्या था से
केवल हम रख दिया है, क्योंकि न आकार वर्तमान में है, जहां का ट्रैक,
हम भी सिर पर नज़र रखने के लिए चाहते हैं साथ ही जहां हम वर्तमान में कर रहे हैं।
इसलिए मुझे लगता है कि यह आसान लगता है मैं यह आकर्षित किया है।
तो चलो हम एक कतार मिल गया है कल्पना करते हैं, तो चलो सिर यहीं है कहते हैं।
लाइन के सिर, चलो सिर्फ इतना है कि वहाँ वर्तमान में है कहना
और हम सम्मिलित करना चाहते हैं कतार में कुछ और।
मैं अनिवार्य रूप आकार को फोन करने के लिए जा रहा हूँ पूंछ के रूप में एक ही बात है,
अपने कतार है जहाँ के अंत।
चलो बस आकार यहीं है और कहते हैं।
>> तो कैसे एक feasibly करता है एक कतार में कुछ डालने?
क्या सूचकांक हम जगह करना चाहते हैं जहां हम में सम्मिलित करना चाहते हैं।
इस की शुरुआत है, तो आपके क़तार और यह इसे का अंत है
या इसका आकार, जहां हम करते हैं अगले वस्तु जोड़ना चाहते हैं?
>> दर्शकों: [अश्राव्य]
ANDI PENG: बिल्कुल, आप जोड़ना चाहते हैं के आधार पर आप इसे लिखा है।
या तो यह रिक्त है या कि रिक्त है।
तो आप शायद यह जोड़ना चाहते हैं क्योंकि यहाँ आकार है- यदि
इन सभी भरे हुए हैं, अगर आप चाहते हैं ठीक है, यहीं इसे जोड़ने के लिए?
>> और इतना है कि है, बहुत, बहुत, जबकि सरल, काफी नहीं है हमेशा सही
मुख्य अंतर यह है क्योंकि एक कतार और एक ढेर के बीच
कि कतार कर सकते है वास्तव में हेरफेर किया
इतना है कि सिर में परिवर्तन जहां आप चाहते हैं पर निर्भर करता है
अपने क्यू की शुरुआत शुरू करने के लिए।
और एक परिणाम के रूप में, अपनी पूँछ यह भी बदलने जा रहा है।
और हां पर एक नज़र रखना अभी इस कोड।
तुम लोगों को भी करने को कहा गया के रूप में एन्क्यू, प्रश्नोत्तरी पर लिखें।
हो सकता है कि हम क्यों के माध्यम से बात करेंगे जवाब था कि वह क्या था।
>> मैं काफी, एक पर इस लाइन फिट नहीं कर सका कोड की लेकिन अनिवार्य रूप से यह टुकड़ा
एक पंक्ति पर होना चाहिए।
30 सेकंड की तरह खर्च करते हैं।
एक नज़र डालें, और क्यों देखते हैं यह बात है कि जिस तरह से है।
>> बहुत, बहुत समान संरचना, बहुत, बहुत पिछले के रूप में इसी तरह की संरचना
शायद के लिए छोड़कर ढेर कोड की एक पंक्ति।
और कोड की एक पंक्ति है कि कार्यक्षमता को निर्धारित करता है।
और यह वास्तव में differentiates एक ढेर से एक कतार।
>> किसी को भी एक चाकू ले जाना चाहते हैं आप है यही कारण है समझाने में
यहाँ इस जटिल काम मिला?
हम की वापसी देखना हमारे अद्भुत दोस्त मापांक।
तुम लोगों को जल्द ही आ जाएगा के रूप में प्रोग्रामिंग में पहचान करने के लिए,
लगभग किसी भी समय आप कुछ की जरूरत है कुछ भी चारों ओर लपेट,
मापांक करने का तरीका ऐसा होने जा रहा है।
इसलिए, यह जानकर कि किसी को चाहता है कोड की है कि लाइन समझा कोशिश करने के लिए?
हाँ, सारे सवालों के जवाब हैं स्वीकार किए जाते हैं और आपका स्वागत है।
दर्शकों: तुम मुझे करने के लिए बात कर रहे हैं?
ANDI PENG: हाँ।
दर्शकों: ओह, नहीं खेद है।
ANDI PENG: ठीक है, तो चलो इस कोड के माध्यम से चलते हैं।
तो जब आप करने की कोशिश कर रहे हैं एक कतार पर कुछ जोड़ने,
सिर होता है कि सुंदर मामले में यहीं होना है, यह हमारे लिए बहुत आसान है
बस अंत में जाने के लिए कुछ सही डालने?
लेकिन एक कतार की सारी बात है कर सकते हैं कि वास्तव में गतिशील सिर
जहां के आधार पर बदल हम हमारे क्यू की शुरुआत होना चाहते हैं,
और इस तरह, पूंछ के रूप में यह भी बदलने जा रहा है।
>> और इसलिए यह नहीं था कि कल्पना कतार, बल्कि इस कतार थी।
के सिर यहीं है और कहते हैं।
चलो हमारे कतार इस तरह से देखा कहते हैं।
हम जहां शिफ्ट करना चाहता था लाइन की शुरुआत है,
हम सिर स्थानांतरित कर हम कहते हैं इस तरह से और यहाँ आकार।
>> अब हम कुछ जोड़ना चाहते हैं इस कतार, लेकिन तुम लोगों को देख सकते हैं,
यह सिर्फ इतनी के रूप में सरल नहीं है आकार के बाद जो कुछ भी जोड़ने
फिर हम से बाहर चला क्योंकि हमारी वास्तविक सरणी की सीमा।
हम वास्तव में जोड़ना चाहते हैं, जहां यहाँ है।
यही कारण है कि एक कतार की खूबसूरती है कि यह नेत्रहीन, हमारे पास है
रेखा इस तरह से चला जाता है, जैसे लग रहा है लेकिन एक डेटा संरचना में संग्रहीत करते हैं,
वे एक चक्र की तरह के रूप में दे।
यह एक तरह से चारों ओर लपेटता सामने एक ही रास्ता करने के लिए
एक लाइन भी लपेट कर सकते हैं कि चारों ओर जहां भी आप पर निर्भर करता है
होने के लिए लाइन की शुरुआत करना चाहते हैं।
और इसलिए हम एक लेते हैं यहाँ नीचे देखो, चलो
हम एक बनाना चाहता था कहना समारोह एन्क्यू बुलाया।
हम जानते हैं कि क्यू में int n जोड़ना चाहते थे।
Q.size हम अपने डेटा कि फोन करता हूँ q-- हैं हमारे queue.size नहीं करता है तो structure--
क्षमता के लिए या यदि बराबर यह क्षमता से भी कम है
q.strings हमारे क्यू भीतर सरणी है।
हम स्थापित करने के लिए जा रहे हैं कि q.heads के बराबर है,
जो यहीं है, प्लस q.size क्षमता, द्वारा मापांक जो
यहाँ के आसपास हमें वापस लपेटो।
>> इस उदाहरण, सूचकांक में तो सिर के 1, सही है?
आकार के सूचकांक 0, 1, 2, 3, 4 है।
इसलिए हम एक प्लस 4 मापांक क्या कर सकते हैं 5 है जो हमारी क्षमता से।
क्या है कि हमें देता है?
सूचकांक क्या है कि इस से बाहर आता है?
>> दर्शकों: 0।
>> ANDI PENG: 0, जो यहीं होना होता है,
और इसलिए हम सक्षम होना चाहता हूँ यहीं में डालने के लिए।
और इसलिए इस समीकरण यहाँ प्रकार की बस किसी भी संख्या के साथ काम करता है
जहां पर निर्भर करता है आपके सिर और अपने आकार के होते हैं।
आप क्या उन जानते हैं चीजों को आप जानते हैं, कर रहे हैं
वास्तव में आप सम्मिलित करना चाहते हैं जहां जो कुछ भी अपने कतार के बाद है।
कि हर किसी के लिए मतलब?
>> मैं एक मस्तिष्क की तरह पता टीज़र खासकर के बाद से इस
अपने प्रश्नोत्तरी के बाद में आया था।
लेकिन उम्मीद है कि हर कोई अब समझ सकते हैं
यही कारण है कि यह समाधान या इस समारोह में यह है कि जिस तरह से है।
किसी को भी एक सा उस पर स्पष्ट नहीं?
ठीक।
>> और अब तो, अगर आप , इस विपंक्ति करना चाहता था
हमारे सिर स्थानांतरण होगा जहां है हम विपंक्ति रहे थे, क्योंकि
हम क्यू के अंत से नहीं लेते।
हम सही, सिर से दूर रखना चाहते हैं?
तो एक परिणाम के रूप में, सिर बदलने जा रहा है, आप enqueue जब क्यों और वह यह है कि
आप का ट्रैक रखने के लिए मिल गया है जहां अपने सिर और अपने आकार
सम्मिलित करने में सक्षम हो रहे हैं सही स्थिति में।
>> और तो आप विपंक्ति जब, मैं भी इसे बाहर pseudocode।
अगर आप चाहते हैं करने के लिए स्वतंत्र महसूस इस बाहर कोडिंग प्रयास करने के लिए।
आप सही हैं, सिर ले जाना चाहते हैं?
मैं विपंक्ति करना चाहता था, मैं सिर पर ले जाया जाएगा।
यह सिर होगा।
>> और हमारे मौजूदा आकार होगा घटाना है क्योंकि हम अब और नहीं
सरणी में चार तत्वों है।
हम केवल तीन है, और फिर हम चाहते हैं अंदर जमा हो गया था जो कुछ भी वापस करने के लिए
सिर की हम इस लेना चाहते हैं, क्योंकि ढेर करने के लिए तो बहुत समान मूल्य बाहर।
बस आप ले जा रहे हैं एक अलग जगह से,
और आप अपने सूचक को पुन: असाइन करने के लिए है एक परिणाम के रूप में अलग-अलग जगह पर।
तार्किक रूप से, हर किसी का पालन करें?
अच्छा है।
>> ठीक है, तो हम थोड़ा बात करने के लिए जा रहे हैं लिंक सूचियों के बारे में अधिक गहराई में
वे बहुत, बहुत मूल्यवान हो जाएगा क्योंकि इस सप्ताह के पाठ्यक्रम में आप के लिए
psets।
लिंक सूचियों, के रूप में आप लोग वे सभी कर रहे हैं, याद कर सकते हैं
कुछ के नोड्स हैं कि नोड्स रहे हैं एक मूल्य और एक सूचक दोनों के मूल्यों
कि एक साथ जुड़े हुए हैं उन संकेत द्वारा।
कैसे पर और इतने संरचना हम यहाँ एक नोड हम है बनाने
जो है, पूर्णांक n है जो कुछ भी एक दुकान या स्ट्रिंग n में मूल्य
या आप करना चाहते हैं जो कुछ भी चार स्टार एन, इसे कहते हैं।
सूचक है जो संरचना नोड स्टार, आप प्रत्येक नोड में है चाहता हूँ कि,
आपको लगता है कि करने के लिए जा रहे हैं अगले ओर सूचक बिंदु।
आप सिर होगा है कि एक लिंक सूची की
के आराम करने के लिए बात करने के लिए जा रहा इतने पर और आगे मूल्यों
आप अंततः अंत तक पहुँचते हैं जब तक।
और यह पिछले नोड बस है एक सूचक है नहीं जा रहा है।
यह करने के लिए बात करने के लिए जा रहा है अशक्त, और कहा कि जब है
क्या आप मारा गया है पता अपने लिंक सूची के अंत
जब अपने अंतिम सूचक कुछ भी करने के लिए बात नहीं है।
>> तो हम और अधिक में एक बिट जाने के लिए जा रहे हैं के बारे में गहराई से कैसे एक संभवतः होगा
एक लिंक सूची खोज।
कुछ कर रहे हैं क्या याद रखें लिंक सूचियों की खामियों
खोजें के बारे में एक सरणी छंद।
एक सरणी आप कर सकते हैं द्विआधारी खोज, लेकिन क्यों आप एक लिंक सूची में ऐसा नहीं कर सकते?
>> दर्शकों: वे सब जुड़े रहे हैं, इसलिए लेकिन आप काफी पता नहीं कहाँ
[अश्राव्य]।
>> ANDI PENG: हाँ, वास्तव में ऐसा याद कि एक सरणी की प्रतिभा
हम था कि तथ्य था रैंडम एक्सेस मेमोरी जहां
मैं सूचकांक से मूल्य अगर चाहता था छह, मैं सिर्फ सूचकांक छह कह सकते हैं
मुझे लगता है कि मूल्य दे।
सरणियों हल कर रहे हैं क्योंकि और है कि स्मृति का एक सन्निहित अंतरिक्ष में
एक ही स्थान पर, जबकि लिंक सूचियों की तरह
हैं बेतरतीब ढंग से, चारों ओर सब interspersed और एक ही रास्ता तुम एक पा सकते हैं
आपको बताता है कि एक सूचक के माध्यम से है कि अगले नोड है जहां के पते।
>> और हां एक परिणाम के रूप में, एक ही रास्ता एक लिंक सूची के माध्यम से खोज करने के लिए
रैखिक खोज है।
मैं वास्तव में, जहां पता नहीं है क्योंकि लिंक सूची में 12 वें मूल्य है,
मैं पूरी तरह पार करने के लिए है उस लिंक की गई सूची में से एक की
प्रथम नोड के लिए सिर से एक एक करके, दूसरे नोड के लिए, तीसरे नोड के लिए,
मैं अंत में मिलता है जब तक सभी तरह से नीचे मैं देख रहा हूँ कि नोड है, जहां के लिए।
और इसलिए इस अर्थ में, खोज एक लिंक सूची पर हमेशा n है।
यह हमेशा N है।
यह रैखिक समय में हमेशा है।
>> और तो कोड जिसमें हम यह लागू है, और इस
आप के बाद से आप लोगों के लिए एक नया सा है लोग वास्तव में के बारे में या कभी बात नहीं की है
करने के लिए कैसे में देखा संकेत संकेत के माध्यम से खोज,
इसलिए हम के माध्यम से चलना होगा यह बहुत, बहुत धीरे-धीरे।
तो बूल खोज, ठीक है, हम चाहते हैं कल्पना करते हैं
कहा जाता है एक समारोह बनाने के लिए सच है कि रिटर्न खोज
आप लिंक के अंदर एक मूल्य अगर मिल सूची है, और इसे अन्यथा गलत देता है।
नोड स्टार सूची है वर्तमान में सिर्फ सूचक
अपने लिंक सूची में पहले आइटम के लिए।
int n आप कर रहे हैं कि मूल्य है उस सूची में के लिए खोज।
>> तो नोड स्टार सूचक सूची के बराबर होती है।
यही कारण है कि हम स्थापित कर रहे हैं इसका मतलब और एक सूचक बनाने
सूची के अंदर पहली बार है कि नोड के लिए।
मेरे साथ सब लोग?
हम जा रहे थे तो अगर यहाँ वापस, मैं होता
को इंगित करता है एक सूचक initialized सिर जो कुछ भी की है कि सूची है।
>> और फिर तुम, यहाँ नीचे लाने के लिए एक बार सूचक बराबर अशक्त नहीं करता है,
इसलिए कि हम जो कर रहे हैं में पाश है गुजर बाद में होने जा रहा
क्या क्योंकि हमारी सूची के बाकी सूचक बातिल के बराबर होती है, जब ऐसा होता है?
हम have-- जानते हैं कि
>> दर्शकों: [अश्राव्य]
>> ANDI PENG: बिल्कुल, इसलिए हम जानते हैं कि हम सही सूची के अंत में पहुँच गए हैं?
आप यहाँ वापस जाओ, प्रत्येक नोड अन्य नोड के लिए इशारा किया जाना चाहिए
इत्यादि इत्यादि आप अंततः मारा जब तक
अपने लिंक सूची की पूंछ, जो एक सूचक है कि बस
कोई तुलना में कहीं भी अन्य बिंदु नहीं है।
और तो आप मूल रूप से जानते हैं कि अपनी सूची में अभी भी वहाँ है
सूचक बराबर नहीं है जब तक अशक्त यह शून्य के बराबर होती है क्योंकि एक बार,
आप कोई और अधिक सामान पता है कि वहाँ।
>> तो यह है कि हम कर रहे हैं जिसमें पाश है वास्तविक खोज है जा रहा।
और pointer-- आप देख नहीं है वहाँ तीर समारोह के उस तरह?
तो सूचक अंक यदि n करने के लिए, यदि n बराबर n पर सूचक,
तो इसका मतलब है कि अगर आप कर रहे हैं कि सूचक
प्रत्येक के अंत पर के लिए खोज नोड मूल्य के लिए वास्तव में बराबर है
यदि आप के लिए देख रहे हैं आप सच वापसी करना चाहते हैं।
तो बुनियादी तौर पर, आप एक नोड पर कर रहे हैं कि आप के लिए देख रहे हैं कि मूल्य नहीं है
क्या आप से किया गया है कि पता है सफलतापूर्वक खोज करने में सक्षम।
>> अन्यथा, आप सेट करना चाहते हैं अगले नोड के लिए अपने सूचक।
यही कारण है कि यहां कि रेखा क्या कर रहा है है।
सूचक अगले सूचक के बराबर होती है।
कि काम कर रहा है कि कैसे हर कोई देख रहे हो?
>> और अनिवार्य रूप से आप जा रहे हैं, बस सूची के संपूर्णता पार
अपने सूचक हर बार जब तक resetting आप अंततः सूची के अंत मारा।
और आप कोई पता है कि वहाँ अधिक नोड्स, के माध्यम से खोज करने के लिए
और फिर आप गलत लौट सकते हैं क्योंकि आप जानते हैं, कि अच्छी तरह से, ओह,
मैं खोज करने में सक्षम किया गया है सूची की सम्पूर्णता के माध्यम से।
इस उदाहरण में, तो मैं चाहता था कि अगर 10 के मूल्य के लिए देखने के लिए,
और मैं सिर से शुरू, और मैं सभी तरह से नीचे खोज
और मैं अंत में, यह करने के लिए मिला है, जो अशक्त करने के लिए बताते हैं कि एक सूचक,
मैं में नहीं है, बकवास, मैं 10 लगता है कि पता है इस सूची में मैं यह नहीं मिल सकता है।
और मैं सूची के अंत में हूँ।
और जो मामले में आप जानते हैं मैं झूठी वापस करने के लिए जा रहा हूँ।
>> कि एक छोटा सा के लिए में लेना।
इस सुंदर हो जाएगा अपने pset के लिए महत्वपूर्ण है।
इसके बारे में तर्क शायद बहुत आसान है, वाक्य रचना से सिर्फ इसे लागू।
तुम लोग बनाना चाहते आप समझते हैं कि सुनिश्चित करें।
कूल।
>> ठीक है, तो हम कैसे होगा ठीक है, नोड्स डालने,
एक सूची में क्योंकि याद क्या लाभ में से क्या कर रहे हैं
का एक लिंक सूची बनाम होने भंडारण के मामले में एक सरणी?
>> दर्शकों: यह गतिशील है, इसलिए यह आसान है है--
>> ANDI PENG: वास्तव में, इसलिए यह गतिशील है जो
यह विस्तार और सिकुड़ कर सकते हैं कि इसका मतलब है उपयोगकर्ता की जरूरतों पर निर्भर करता है।
और हां, इस अर्थ में, हम की जरूरत नहीं है अनावश्यक स्मृति बर्बाद करने के लिए मैं क्योंकि
मैं चाहता हूँ कि कितने मूल्यों अगर तुम नहीं जानते स्टोर करने के लिए, यह मेरे लिए मतलब नहीं है
एक सरणी क्योंकि बनाने के लिए मैं 10 मूल्यों स्टोर करना चाहते हैं
और मैं 1000 की एक सरणी, कि बनाने व्यर्थ स्मृति का एक बहुत आवंटित।
हम एक लिंक का उपयोग करना चाहते हैं यही कारण है कि सूची गतिशील करने के लिए सक्षम होने के लिए
बदलने के लिए या हमारे आकार हटना।
>> और इतना है कि प्रविष्टि बनाता है थोड़ा और अधिक जटिल।
हम बेतरतीब ढंग से तत्वों का उपयोग नहीं कर सकते हम एक सरणी का होता है कि जिस तरह से।
मैं एक तत्व सम्मिलित करना चाहते हैं सातवें सूचकांक में,
मैं सिर्फ यह सम्मिलित कर सकते हैं सातवें सूचकांक में।
एक लिंक सूची पर, यदि ऐसा नहीं होता काफी के रूप में आसानी से काम करते हैं,
और इसलिए हम डालने के लिए चाहते थे कि अगर लिंक सूची में यहां से एक है,
नेत्रहीन, यह देखने के लिए बहुत आसान है।
हम सिर्फ यह ठीक है वहाँ सम्मिलित करना चाहते हैं सही सूची की शुरुआत में,
सही सिर के बाद।
>> लेकिन हम जिस तरह के फिरसेआबंटितकरें संकेत एक सा जटिल है
या, तार्किक रूप से, यह समझ में आता है लेकिन क्या आप यह है कि यह सुनिश्चित करना चाहते हैं
पूरी तरह से नीचे क्योंकि आखिरी बात आप चाहते
एक सूचक पुन: असाइन करने के लिए है हम यहाँ क्या कर रहे हैं कि जिस तरह से।
आप तो भिन्नता 1 सिर से सूचक,
उसके बाद अचानक से सब अपने लिंक सूची के बाकी
आप वास्तव में नहीं है, क्योंकि खो दिया है एक अस्थायी कुछ भी बनाया।
यही कारण है कि 2 की ओर इशारा किया है।
तुम तो सूचक, पुन: असाइन हैं अपनी सूची के बाकी पूरी तरह से खो दिया है।
तो आप बनना चाहते हैं यहाँ बहुत, बहुत सावधान
पहले आवंटित करने के लिए आप जो कुछ भी सूचक
जहाँ भी में सम्मिलित करना चाहते हैं आप चाहते हैं, और फिर आप
अपनी सूची के बाकी भिन्नता कर सकते हैं।
>> तो यह जहाँ भी लिए लागू होता है आप में सम्मिलित करने की कोशिश कर रहे हैं।
आप में सम्मिलित करना चाहते हैं सिर, आप यहाँ जवाब देना चाहते हैं, तो
आप में सम्मिलित करना चाहते हैं, तो अंत में, खैर, अंत मैं
लगता है कि तुम सिर्फ होगा कोई सूचक है, लेकिन आप
यदि आप नहीं करते कि यह सुनिश्चित करना चाहते हैं अपनी सूची के बाकी खो देते हैं।
तुम हमेशा सुनिश्चित करना चाहते हैं अपने नए नोड इशारा कर रहा है
जो कुछ भी आप की ओर में सम्मिलित करना चाहते हैं,
और फिर तुम पर श्रृंखलन जोड़ सकते हैं।
हर कोई स्पष्ट?
>> यह होने जा रहा है असली मुद्दों में से एक।
सबसे प्रमुख मुद्दों में से एक आप अपने pset पर लिए जा रहे हैं
आप बनाने के लिए प्रयास करने के लिए जा रहे हैं एक लिंक सूची और डालने बातें
लेकिन तब सिर्फ खोना अपने लिंक सूची के बाकी।
और आप की तरह होने जा रहे हैं, मैं क्यों हो रहा है पता नहीं है?
और इसके माध्यम से जाने के लिए एक दर्द है और अपने संकेत के सभी खोज।
>> और मैं इस pset पर तुम्हें गारंटी है, इन नोड्स बाहर लेखन और ड्राइंग
बहुत, बहुत मददगार होगा।
तो आप पूरी तरह से नज़र रख सकते हैं अपने सभी संकेत दिए गए हैं, जहां की,
क्या गलत हो रहा है अपने सभी नोड्स रहे हैं, जहां
आप का उपयोग करने के लिए क्या करने की जरूरत या डालने या हटा सकते हैं या उनमें से किसी को।
उस के साथ अच्छे सब लोग?
कूल।
>> हम कोड को देखने के लिए करना चाहता था तो अगर?
ओह, मैं नहीं जानता कि यदि हम इसलिए, the-- ठीक से देख सकते हैं
शीर्ष पर यह सब एक समारोह है हम चाहते हैं जहां नामित डालने
लिंक सूची में int n डालने के लिए।
हम इस के माध्यम से चलने के लिए जा रहे हैं।
यह कोड का एक बहुत, नई वाक्य रचना के लिए बहुत कुछ है।
हम ठीक हो जाएगा।
>> शीर्ष, जब भी पर तो हम कुछ भी बनाना चाहते हैं
हम क्या करने की जरूरत है, खासकर अगर आप यह ढेर पर संग्रहीत किया जा नहीं करना चाहते
लेकिन ढेर में?
हम सही, एक malloc के लिए जाना है?
इसलिए हम एक सूचक बनाने के लिए जा रहे हैं।
नोड, सूचक, नई बराबरी एक नोड के आकार malloc
हम चाहते हैं कि क्योंकि नोड बनाया जाना है।
हम की राशि चाहते हैं एक नोड तक ले जाता है कि स्मृति
के लिए आवंटित किया जाना है नए नोड का निर्माण।
>> और फिर हम करने के लिए जाँच करने के लिए जा रहे हैं नई बराबरी बातिल के बराबर होती है देखते हैं।
हमने कहा क्या याद है?
Malloc तुम जो भी, आप हमेशा क्या करना चाहिए?
आप हमेशा यह देखने के लिए की जांच होगी चाहे या नहीं कि रिक्त है।
>> उदाहरण के लिए, यदि आपके ऑपरेटिंग प्रणाली है, पूरी तरह से भरा हुआ था
आप में कोई और अधिक स्मृति था कि अगर सब और आप malloc करने की कोशिश,
यह आप के लिए अशक्त वापस कर देगा।
और तो आप इसका इस्तेमाल करने की कोशिश करता है, तो यह शून्य की ओर इशारा किया गया था,
आप सक्षम करने के लिए नहीं जा रहे हैं कि जानकारी का उपयोग करने के लिए।
और इसलिए इस तरह के रूप में, हम बनाना चाहते थे जब भी आप mallocing रहे हैं कि यकीन है,
आप हमेशा देखने के लिए अगर जाँच कर रहे हैं आप के लिए दिया है कि स्मृति रिक्त है।
अगर ऐसा नहीं है, तो हम स्थानांतरित कर सकते हैं हमारे कोड के बाकी के साथ पर।
>> तो हम करने जा रहे हैं नए नोड प्रारंभ।
हम नए एन के बराबर होती है क्या करने जा रहे हैं।
और फिर हम क्या करने जा रहे हैं नई पर नए सूचक सेट
अशक्त करने के लिए ठीक है अब हम नहीं करते क्योंकि यह करने के लिए बात करने के लिए कुछ भी करना चाहते हैं।
हमें पता नहीं है, जहां है यह डाल करने के लिए जा रहा है
और फिर हम करना चाहते हैं सिर पर डालें,
उसके बाद हम पुन: असाइन कर सकते हैं सिर करने के लिए सूचक।
हर कोई तर्क का पालन करता है जहां की है कि क्या हो रहा है?
>> हम सब कर रहे हैं एक नए पैदा कर रही है नोड, अशक्त करने के लिए सूचक की स्थापना,
और उसके बाद फिर नियत यह सिर करने के लिए अगर हम
हम सिर पर डालने के लिए चाहते हैं।
और फिर सिर जा रहा है कि नए नोड की ओर इशारा करते हैं।
उस के साथ ठीक सब लोग?
>> तो यह एक दो कदम प्रक्रिया है।
तुम पहले आवंटित करने के लिए मिल गया है जो कुछ भी आप बना रहे हैं।
करने के लिए कि सूचक सेट आप संदर्भ, और उसके बाद
कर सकते हैं भिन्नता की तरह पहले सूचक
और नए नोड की दिशा में यह इंगित करते हैं।
आप इसे डालने के लिए चाहते हैं, तर्क है कि सच का आयोजन करने जा रहा है।
>> यह बताए की तरह की तरह है अस्थायी चर।
याद रखें, आप मिल गया है सुनिश्चित करने के लिए आपको लगता है कि
आप स्वैपिंग रहे हैं का ट्रैक खोना नहीं है।
क्या आप एक है कि यह सुनिश्चित करना चाहते हैं तरह का रहता है कि अस्थायी चर
जहां कि बात का ट्रैक इतना है कि संग्रहीत है आप
पाठ्यक्रम में किसी भी मूल्य नहीं खोना है के चारों ओर के साथ खिलवाड़ की तरह।
>> ठीक है, तो कोड यहाँ होगा।
तुम लोग अनुभाग के बाद एक नज़र रखना।
यह हो जाएगा।
>> तो मैं कैसे करता है लगता है हम चाहते थे कि अगर यह अलग
मध्य या अंत में सम्मिलित करने के लिए?
किसी को भी क्या है की एक विचार है तार्किक संदर्भ के रूप में स्यूडोकोड
हम चाहते थे कि अगर हम ले जाएगा बीच में इसे सम्मिलित करने के लिए?
तो अगर हम पर डालने के लिए करना चाहता था सिर, हम सब एक नए नोड बनाने के लिए है।
हम इस बात का सूचक सेट जो कुछ भी सिर पर नए नोड,
और फिर हम सिर सेट नए नोड के लिए, है ना?
हम बीच में इसे सम्मिलित करना चाहता था सूची की, हमें क्या करना होगा?
>> दर्शकों: यह अभी भी होगा इसी तरह की एक प्रक्रिया हो
का सूचक बताए की तरह है और तो, कि सूचक बताए
लेकिन हम वहाँ का पता लगाने के लिए होगा।
>> ANDI PENG: वास्तव में, वास्तव में ऐसा आप को छोड़कर एक ही प्रक्रिया
वास्तव में, जहां पता लगाने के लिए आप कि नई सूचक में जाना चाहते हैं,
मैं में सम्मिलित करना चाहते हैं तो ठीक list-- लिंक्ड के बीच,
का है कि हमारे लिंक सूची चलो कहते हैं।
हम इसे यहीं सम्मिलित करना चाहते हैं, तो हम एक नए नोड बनाने के लिए जा रहे हैं।
हम malloc के लिए जा रहे हैं।
हम एक नए नोड बनाने के लिए जा रहे हैं।
हम आवंटित करने के लिए जा रहे हैं यहाँ इस नोड का सूचक।
>> लेकिन समस्या यह है कि अलग है सिर है, जहां से
हम बिल्कुल पता था कि है जहां सिर है।
यह ठीक है, पहली बार में सही था?
लेकिन यहाँ हम ट्रैक रखने के लिए मिल गया है जहां से हम इसे में डालने जा रहे हैं।
हम डालने रहे हैं, तो हमारे यहां नोड, हमें मिल गया है
यह सुनिश्चित करना है कि इस नोड के लिए पिछले एक
सूचक reassigns कि एक है।
तो फिर आप की तरह करने की जरूरत दो चीजों का ट्रैक रखने के लिए।
आप जहां इस पर नज़र रखने के लिए नोड वर्तमान में डालने है।
तुम भी जहां का ट्रैक रखने के लिए है आप देख रहे हैं कि पिछले नोड
वहाँ भी था।
उस के साथ अच्छे सब लोग?
ठीक।
>> कैसे अंत में डालने के बारे में?
मैं चाहता था कि अगर मैं here-- इसे जोड़ने के लिए चाहता था एक सूची के अंत में एक नया नोड जोड़ने के लिए,
मुझे लगता है कि ऐसा करने के बारे में कैसे जा सकता है?
दर्शकों: तो वर्तमान में, पिछले एक अशक्त की ओर इशारा किया।
ANDI PENG: हाँ।
बिल्कुल सही है, तो यह एक वर्तमान में पता करने की ओर इशारा किया है,
और इसलिए मैं इस अर्थ में, यह है, लगता है एक सूची के अंत में जोड़ने के लिए बहुत आसान नहीं है।
आप सब करना है यह तय है अशक्त और फिर बूम के बराबर है।
वहीं, बहुत आसान है।
बहुत आसान।
>> करने के लिए बहुत समान आप सिर, लेकिन तार्किक
कदम है कि बनाना चाहते आप इस के किसी भी कर रही है की दिशा में ले
आप के साथ पीछा कर रहे हैं।
यह बीच में, बहुत आसान है अपने कोड की, पर पकड़े गए
ओह, मैं इतने सारे संकेत मिल गया है।
मैं नहीं जानता कि जहां कुछ भी करने के लिए इशारा कर रहा है।
मैं भी मैं कर रहा हूँ जो नोड पता नहीं है।
क्या चल रहा है?
>> एक गहरी साँस ले, शांत हो जाओ, आराम करो।
अपने लिंक सूची से बाहर ड्रा।
यदि आप कहते हैं, मैं वास्तव में, जहां पता है मैं इस में डालने की जरूरत है
और मैं अपने पुन: असाइन करने के लिए कैसे ठीक से पता संकेत, बहुत, बहुत आसान तस्वीर के लिए
out-- बहुत, बहुत आसान करने के लिए नहीं अपने कोड के कीड़े में खो जाते हैं।
उस के साथ ठीक सब लोग?
ठीक।
>> इसलिए मुझे लगता है कि हम नहीं है एक अवधारणा है कि लगता है वास्तव में, अब से पहले के बारे में बात की थी
और मैं शायद आप अनुमान लगा ज्यादा yet-- सामना नहीं करेंगे
यह एक उन्नत concept-- की तरह है हम वास्तव में एक डेटा के लिए किया है
संरचना एक दोगुना लिंक सूची बुलाया।
तुम लोगों को देख सकते हैं, हम सभी कर रहे हैं पैदा कर रही है
एक वास्तविक मूल्य, एक अतिरिक्त हमारे नोड्स में से प्रत्येक पर सूचक
यह भी कहा कि पिछले नोड के लिए अंक।
इतना ही नहीं, हम हमारे लिए क्या है नोड्स अगले एक को इंगित करते हैं।
उन्होंने यह भी पिछले एक के लिए इशारा करते हैं।
मैं अभी इन दो अनदेखी करने के लिए जा रहा हूँ।
>> तो फिर आप एक श्रृंखला है कि दोनों तरीकों से स्थानांतरित कर सकते हैं,
और फिर यह थोड़ा आसान है तार्किक रूप से साथ पालन करने के लिए।
यहाँ की तरह, के बजाय ओह, का ट्रैक रखने, मैं
इस नोड है कि पता करने के लिए मैं पुन: असाइन करने के लिए है कि एक,
मैं बस यहाँ जाने के लिए और कर सकते हैं सिर्फ पिछले खींच।
तब मैं वास्तव में पता है, जहां वह यह है कि, और फिर आप
पार करने के लिए नहीं है लिंक सूची की सम्पूर्णता।
यह थोड़ा आसान है।
>> लेकिन इस तरह के रूप में, आप दोगुना है संकेत की राशि,
कि स्मृति की मात्रा दोगुनी है।
इसे का ट्रैक रखने के लिए संकेत के एक बहुत कुछ है।
यह थोड़ा और अधिक जटिल है, लेकिन यह है उपयोगकर्ता के अनुकूल आधार पर थोड़ा और अधिक
आप क्या हासिल करने की कोशिश कर रहे हैं पर।
>> तो डेटा के इस प्रकार के संरचना पूरी तरह से मौजूद है,
और के लिए संरचना बहुत, बहुत है आप कर रहे हैं सब है सिवाय सरल,
बजाय अगले करने के लिए सिर्फ एक सूचक की, आप भी पिछले करने के लिए एक सूचक है।
यही कारण है कि सभी फर्क था।
उस के साथ अच्छे सब लोग?
कूल।
>> ठीक है, तो अब मैं कर रहा हूँ वास्तव में शायद खर्च करने के लिए
15 से 20 मिनट या थोक की तरह अनुभाग में समय के आराम की
हैश टेबल के बारे में बात कर रही है।
कैसे तुम लोगों के कई pset5 कल्पना पढ़ा है?
ठीक है, अच्छा है।
यही कारण है कि सामान्य रूप से 50% से अधिक है।
यह ठीक है।
>> तुम लोगों को देखेंगे तो, आप pset5 में चुनौती हो
एक शब्दकोश को लागू करने के लिए किया जाएगा आप 140,000 शब्दों पर लोड जहां
हम और जादू की जांच दे कि आप पाठ के सभी के खिलाफ यह।
हम आपको यादृच्छिक दे दूँगा साहित्य के टुकड़े।
हम आपको ओडिसी दे दूँगा।
हम आपको इलियड दे दूँगा।
हम आपको ऑस्टिन पॉवर्स दे दूँगा।
>> और अपनी चुनौती वर्तनी जांच के लिए किया जाएगा
सभी में हर एक शब्द उन शब्दकोशों की
अनिवार्य रूप से हमारे जादू चेकर के साथ।
और तो कुछ भागों रहे है इस pset बनाने की,
पहले आप होना चाहते हैं वास्तव में लोड करने में सक्षम
में सभी शब्दों को अपने शब्दकोश, और फिर आप
करने के लिए सक्षम होना चाहता हूँ उन सभी को जांच जादू।
और इसलिए इस तरह के रूप में, आप की आवश्यकता के लिए जा रहे हैं इस तेजी से कर सकते हैं कि एक डेटा संरचना
और कुशलता से और गतिशील।
>> इसलिए मैं सबसे आसान लगता है यह करने के लिए इस तरह, आप
शायद सही, एक सरणी पैदा होगा?
भंडारण के लिए सबसे आसान तरीका है कि आप है 140,000 शब्दों की एक सरणी बना सकते हैं
और सिर्फ उन्हें वहाँ सब जगह है और तो द्विआधारी खोज करके उन्हें पार
या चयन के द्वारा या not-- खेद है कि छँटाई है।
आप उन्हें तरह और फिर उन्हें पार कर सकते हैं द्विआधारी खोज या सिर्फ रैखिक खोज से
और सिर्फ अंतिम शब्द, लेकिन लगता है कि , स्मृति की एक बड़ी राशि लेता है
और यह बहुत ही कुशल नहीं है।
>> और इसलिए हम शुरू करने के लिए जा रहे हैं बनाने के तरीके के बारे में बात कर रही है
हमारे समय चल रहा है और अधिक कुशल है।
और हमारे लक्ष्य को पाने के लिए है लगातार समय जहां
यह लगभग सरणियों, जहां की तरह है आप तात्कालिक उपयोग किया है।
मैं कुछ के लिए खोज करने के लिए चाहता था, मैं सिर्फ करने के लिए सक्षम होना चाहता हूँ
बूम, वास्तव में यह मिल जाए, और इसे बाहर खींच।
और इसलिए एक संरचना में जो हम बहुत करीब होते जा रहे होंगे
लगातार उपयोग करने में सक्षम होने के लिए समय, इस होली ग्रेल
निरंतर की प्रोग्रामिंग में समय एक हैश तालिका कहा जाता है।
और तो डेविड पहले उल्लेख [अश्राव्य] व्याख्यान में एक छोटा सा है,
लेकिन हम वास्तव में करने के लिए जा रहे हैं गहरी इस सप्ताह में गोता
के बारे में है कि एक टुकड़े पर कैसे एक हैश तालिका काम करता है।
>> उस तरह से तो एक हैश तालिका काम करता है, उदाहरण के लिए,
मैं शब्दों का एक गुच्छा स्टोर करने के लिए चाहते थे, एक अंग्रेजी भाषा में शब्दों का गुच्छा,
मैं सैद्धांतिक डाल सकता है केला, सेब, कीवी, आम, जोड़ी,
और सब सिर्फ एक सरणी पर खरबूजा।
वे सब में फिट सकता है और मिल जा।
यह करने के लिए एक दर्द की तरह होगा और उपयोग के माध्यम से खोज,
लेकिन ऐसा करने का आसान तरीका है हम एक संरचना वास्तव में बना सकते हैं
हम हैश जहां एक हैश तालिका कहा जाता है।
हम के माध्यम से हमारे कुंजी के सभी चलाने एक हैश समारोह, एक समीकरण,
उस में उन सब बदल जाता है एक मूल्य के कुछ प्रकार
फिर हम पर स्टोर कर सकते हैं लिंक सूची का अनिवार्य रूप से एक सरणी।
>> और तो यहाँ हम चाहते थे कि अगर अंग्रेजी शब्दों स्टोर करने के लिए,
हम संभावित सिर्फ सकता है, मैं नहीं करना पता है, सब पहले पत्र की बारी
एक नंबर के कुछ प्रकार में।
और इसलिए, उदाहरण के लिए, यदि मैं चाहता था एक apple-- का पर्याय माना
या 0 के सूचकांक के साथ, और बी, 1 का पर्याय माना
हम 26 प्रविष्टियों में हो सकता है कि सिर्फ स्टोर कर सकते हैं
के पत्र के सभी हम साथ शुरू करेंगे कि वर्णमाला।
और फिर हम कर सकते हैं 0 से सूचकांक में सेब।
हम के सूचकांक में केला हो सकता है 1, 2 के सूचकांक में खरबूजा,
इत्यादि इत्यादि।
और इस तरह मैं खोज करना चाहता था मेरी हैश तालिका और पहुँच सेब,
मैं एप्पल के साथ शुरू होता है पता है एक एक, और मैं ठीक से पता
यह हो सकता है और हैश चाहिए कि सूचकांक 0 क्योंकि पर तालिका
समारोह के पहले सौंपा।
>> मैं नहीं जानता तो, हम कर रहे हैं एक उपयोगकर्ता के कार्यक्रम जहां
आप के साथ शुल्क लिया जाएगा मनमाने ढंग से नहीं arbitrarily--,
सोच समझकर करने की कोशिश के साथ अच्छा समीकरणों के बारे में सोच
प्रसार करने के लिए सक्षम होने के लिए अपने मूल्यों के सभी बाहर
एक तरह से वे आसानी से उपयोग कर सकते हैं यह बाद में साथ एक समीकरण की तरह
आपको लगता है कि, अपने आप को पता है।
मैं करने के लिए जाना चाहता था, तो इस अर्थ में तो आम, मैं ओह, यह मीटर के साथ शुरू होता है, पता है।
यह 12 के सूचकांक पर होना चाहिए।
मैं कुछ भी माध्यम से खोज करने की जरूरत नहीं है।
मैं तो बस तक जा सकता है exactly-- मुझे पता है और 12 के सूचकांक कि बाहर खींच।
>> कैसे एक पर हर कोई स्पष्ट हैश तालिका के समारोह से काम करता है?
यह सिर्फ एक अधिक जटिल सरणी की तरह है।
यही कारण है कि यह सब है।
ठीक।
>> इसलिए मुझे लगता है कि हम में चलाने लगता है के इस मुद्दे क्या
अगर आप कई बातें हैं, तो क्या होता है कि आप एक ही सूचकांक दे?
तो, यह हमारी समारोह का कहना है किया था कि पहले अक्षर को लेकर था
और एक में है कि बारी 0 सूचकांक 25 के माध्यम से संबंधित।
यही कारण है कि यदि पूरी तरह से ठीक है आप केवल एक में से एक है।
लेकिन दूसरे आप शुरू अधिक हो रही है, आप कर रहे हैं
एक टक्कर कहा जाता है के लिए जा रहा है।
>> मैं सम्मिलित करने का प्रयास करता है, तो एक हैश में दफनाने तो पहले से ही उस पर केले है कि मेज,
क्या जब होने जा रहा है आपको लगता है कि सम्मिलित करने का प्रयास?
बुरी बातें क्योंकि केला पहले से ही सूचकांक के भीतर मौजूद है
आप में स्टोर करना चाहते हैं।
बेरी तरह का मैं क्या करूँ, आह, की तरह है?
मैं जहां जाने के लिए पता नहीं है।
मैं इसका कैसे समाधान करूं?
>> और इसलिए तुम लोग इस विल तरह का हम इस मुश्किल बात करते देखना
जहां हम एक तरह से वास्तव में कर सकते हैं हमारे सरणियों में लिंक सूची बनाने के लिए।
और तो सबसे आसान तरीका इस बारे में सोचने के लिए,
सभी हैश तालिका है एक लिंक सूचियों की सरणी।
और हां, तो उस अर्थ में, आपके पास संकेत के इस खूबसूरत सरणी,
और फिर प्रत्येक सूचक में कि मूल्य, कि सूचकांक में,
वास्तव में अन्य बातों के लिए बात कर सकते हैं।
और तो आप इन सभी अलग है एक बड़ा सरणी के बाहर आने जंजीरों।
>> और यहाँ तो, मैं अगर बेरी डालने के लिए करना चाहता था,
मैं ठीक है, मैं निवेश करने के लिए जा रहा हूँ, पता है यह मेरी हैश समारोह के माध्यम से।
मैं के सूचकांक के साथ खत्म करने के लिए जा रहा हूँ 1, और फिर मैं करने के लिए सक्षम होने के लिए जा रहा हूँ
इस बात का सिर्फ एक छोटे सबसेट विशाल 140000-शब्द शब्दकोश।
और फिर मैं सिर्फ देख सकते हैं इस बात का 1/26 के माध्यम से।
>> और इतना तो मैं सिर्फ सम्मिलित कर सकते हैं पहले या केले के बाद या तो बेरी
इस मामले में?
के बाद, है ना?
और इसलिए आप चाहते करने के लिए जा रहे हैं केले के बाद इस नोड डालें,
और इसलिए आप डालने के लिए जा रहे हैं उस लिंक की गई सूची की पूंछ पर।
मैं वापस जाने के लिए जा रहा हूँ इस पिछली स्लाइड पर,
तो तुम लोग कैसे देख सकते हैं हैश समारोह काम करता है।
>> तो हैश समारोह इस समीकरण है आप अपने इनपुट की तरह चला रहे हैं कि
पाने के लिए जो कुछ भी सूचकांक के माध्यम से आप की दिशा में यह प्रदान करना चाहते हैं।
और हां, इस उदाहरण में, हम सब चाहते थे ऐसा करने के लिए, पहले अक्षर को लेकर था
हम तो एक सूचकांक में है कि बारी हमारे हैश समारोह में उस स्टोर कर सकते हैं।
हम यहाँ क्या कर रहे हैं सभी हम कर रहे है पहले अक्षर परिवर्तित।
तो keykey [0] है सिर्फ पहला पत्र जो कुछ भी स्ट्रिंग की हम कर रहे हैं,
हम में से गुजर रहे हैं।
हम ऊपरी करने के लिए कि परिवर्तित करने, और कर रहे हैं हम अपरकेस A से घटाकर रहे
तो कर रही है कि सभी हमें एक नंबर दे रहा है
जिसमें हम अपने मूल्यों पर हैश कर सकते हैं।
>> और फिर हम करने जा रहे हैं हैश मापांक आकार वापसी।
बहुत, बहुत सावधान रहें सैद्धांतिक रूप से, यहाँ, क्योंकि
अपने हैश मूल्य अनंत हो सकता है।
यह सिर्फ पर और पर और पर जा सकते हैं।
यह वास्तव में कुछ हो सकता है वास्तव में बड़े मूल्य,
लेकिन अपने हैश तालिका वजह यह है कि आपके द्वारा बनाया गया केवल 26 अनुक्रमित है,
आपको यह सुनिश्चित करना चाहते हैं कि आपके modulusing इतना है कि आप
यह वैसा ही है run-- नहीं है अपने queue-- के रूप में बात
इसलिए आप से दूर नहीं चला है कि अपने हैश समारोह के नीचे।
>> आप इसे चारों ओर वापस लपेट करना चाहते हैं [अश्राव्य] जब में एक ही रास्ता
आप एक बहुत की तरह था बहुत बड़े पत्र, आप
करने के लिए नहीं चाहता था कि बस अंत से दूर चला।
यहाँ भी वही बात, आपको यह सुनिश्चित करना चाहते हैं लपेटकर द्वारा अंत बंद नहीं चला है
चारों ओर तालिका के शीर्ष करने के लिए।
तो यह सिर्फ एक बहुत सरल हैश समारोह।
किया था कि सभी ले लिए पहली बार था जो कुछ भी हमारे इनपुट का पत्र था
और एक सूचकांक में है कि बारी है कि हम अपने हैश तालिका में डाल सकता है।
>> हाँ, और इसलिए मैं पहले कहा हम टक्करों को हल कि रास्ता
हमारे हैश में टेबल कर रहे हैं, हम श्रृंखलन, क्या कहते हैं।
अगर आप कई सम्मिलित करने का प्रयास तो अगर एक ही बात के साथ शुरू है कि शब्द,
आप एक हैश मान लिए जा रहे हैं।
Avocados और सेब, आप है, तो हमारे हैश समारोह के माध्यम से इसे चलाने के लिए,
तुम्हें देने के लिए जा रहे हैं एक ही नंबर, 0 की संख्या।
और तो जिस तरह से हम यह है कि हल हम वास्तव में एक तरह से उन्हें लिंक कर सकते हैं कि
एक साथ लिंक सूचियों के माध्यम से।
>> और इसलिए इस अर्थ में, तुम लोगों को तरह देख सकते हैं
की कैसे डाटा संरचनाओं कि हम पहले से स्थापित कर दिया गया है
एक किशमिश लिंक सूची तरह की तरह में से एक में एक साथ आ सकते हैं।
और फिर तुम अब तक बना सकते हैं अधिक कुशल डेटा संरचनाओं
इस बात का बड़ी मात्रा में संभाल कर सकते हैं डेटा, कि गतिशील आधार पर आकार बदलने के
अपनी आवश्यकताओं पर।
हर कोई स्पष्ट?
स्पष्ट की हर कोई तरह यहाँ क्या होता है?
>> मैं insert-- चाहता था, तो एक क्या है मैं नहीं जानता, के साथ शुरू होता है कि फल,
बेरी के अलावा अन्य बी, केला।
>> दर्शकों: ब्लैकबेरी।
>> ANDI PENG: ब्लैकबेरी, ब्लैकबेरी।
कहाँ ब्लैकबेरी यहां जाना है?
खैर, हम वास्तव में हल नहीं किया है यह अभी तक है, लेकिन सैद्धांतिक रूप से
हम इस संबंध के लिए करना चाहता था, तो वर्णमाला क्रम में,
जहां जाने ब्लैकबेरी चाहिए?
>> दर्शकों: [अश्राव्य]
>> ANDI PENG: वास्तव में, यहाँ के बाद, है ना?
लेकिन यह बहुत मुश्किल है के बाद से reorder-- मैं यह आप लोगों के लिए हो रहा है लगता है।
तुम लोग पूरी तरह से कर सकते हैं आप जो चाहते हैं को लागू करने।
अधिक कारगर तरीका शायद यह कर
अपने लिंक से हल करने के लिए किया जाएगा वर्णमाला के क्रम में सूची
और इसलिए आप कर रहे हैं जब चीजों को डालने, आप चाहते हैं
उन्हें सम्मिलित करने के लिए सुनिश्चित किया जाना है वर्णमाला के क्रम में
इसलिए कि तब जब आप कर रहे उन्हें खोज करने के लिए कोशिश कर रहा है,
आप सब कुछ पार करने के लिए नहीं है।
आप वास्तव में पता है, जहां यह है, और यह आसान है।
>> लेकिन आप की तरह है, तो चीजों को बेतरतीब ढंग से बीच-बीच में
आप अभी भी लिए जा रहे हैं वैसे भी यह पार करने के लिए।
और इसलिए मैं चाहता था कि बस ब्लैकबेरी यहां डालें
और मैं के लिए खोज करने के लिए करना चाहता था यह, मैं ओह, पता, ब्लैकबेरी
1 के सूचकांक के साथ शुरू करते हैं, तो मैं चाहिए तत्क्षण सिर्फ 1 पर खोज पता है।
और फिर मैं एक तरह से कर सकते हैं लिंक्ड सूची पार
मैं ब्लैकबेरी को मिलता है, जब तक और हाँ then--?
>> दर्शकों: आप create-- करने की कोशिश कर रहे हैं यह एक बहुत ही सरल हैश है की तरह मुझे लगता है
समारोह।
और हम करना चाहते थे, तो लगता है कि जैसे की कई परतें,
ठीक है, हम में अलग करना चाहते हैं सभी वर्णमाला के अक्षरों की तरह
और उसके बाद फिर एक और सेट पसंद करने के लिए कि भीतर वर्णमाला के अक्षरों की,
हम एक हैश की तरह लगा रहे हैं एक हैश तालिका के अंदर मेज,
या एक समारोह के भीतर एक समारोह की तरह?
या that-- है
>> ANDI PENG: अपने हैश तो अपने हैश तालिका function--
आप यह चाहते हैं के रूप में बड़ा हो सकता है।
तो इस अर्थ में, मैंने सोचा था यह बहुत, बहुत आसान था
मेरे लिए सरल बस की तरह आधारित करने के लिए पहला शब्द के अक्षरों पर।
और तो केवल 26 विकल्प नहीं है।
मैं केवल 26 विकल्प मिल सकता है 0-25, क्योंकि वे ही कर सकते हैं
एक से जेड के लिए शुरू है, लेकिन अगर तुम चाहते थे , शायद, और अधिक जटिलता को जोड़ने के लिए
या तेज करने के लिए समय चलाने के लिए अपने हैश तालिका, तुम बिल्कुल
हर तरह की बातें कर सकते हैं।
आप अपने खुद के लिए कर सकते हैं आप देता है कि समीकरण
में अधिक वितरण अपने शब्द, तो आप खोज, जब
यह तेजी से हो रहा है।
>> यह पूरी तरह आप लोगों पर निर्भर है कैसे आपको लगता है कि लागू करना चाहते हैं।
सिर्फ बाल्टी के रूप में सोचो।
मैं करना चाहता था, तो 26 बाल्टी, मैं जा रहा हूँ
उन बाल्टियों में चीजों को सुलझाने के लिए।
लेकिन मैं एक गुच्छा के लिए जा रहा हूँ प्रत्येक बाल्टी में सामान की,
आप इसे बनाने के लिए चाहते हैं तो तेजी से और अधिक कुशल,
मुझे एक सौ बाल्टी करते हैं।
>> लेकिन फिर आप एक पता लगाने की है वे कर रहे हैं तो यह है कि जिस तरह से चीजें सुलझाने के लिए
उचित बाल्टी में वे में होना चाहिए।
लेकिन तब जब वास्तव में आप कि बाल्टी में देखना चाहता हूँ,
वहाँ है, क्योंकि यह एक बहुत तेज है प्रत्येक बाल्टी में कम सामान।
और हां, तो हाँ, यह वास्तव में है pset5 में आप लोगों के लिए चाल
आप हो जाएगा कि है सिर्फ बनाने के लिए चुनौती
सबसे कुशल जो कुछ भी है आप सोच सकते हैं समारोह होने के लिए
दुकान है और इन मूल्यों की जांच करने में सक्षम।
>> पूरी तरह से तुम लोगों के लिए ऊपर लेकिन आप यह करना चाहते हैं,
लेकिन लगता है कि वास्तव में एक अच्छी बात है।
उस तर्क की तरह आप के बारे में सोचना शुरू करना चाहते
खैर, मैं क्यों अधिक बाल्टी बनाने के लिए नहीं है।
और फिर मैं खोज करने के लिए कम बातें करते हैं, और तब शायद मैं
एक अलग हैश समारोह है।
>> हाँ, यह करने के लिए तरीके का एक बहुत कुछ है pset, कुछ दूसरों की तुलना में तेजी से कर रहे हैं।
मैं पूरी तरह से बस कैसे देखने के लिए जा रहा हूँ तेजी से सबसे तेजी से आप लोग जाएगा था
अपने कार्यों को काम करने के लिए प्राप्त करने में सक्षम हो।
ठीक है, हर किसी को अच्छा पर श्रृंखलन और हैश तालिकाओं?
यह एक बहुत ही सरल की तरह वास्तव में है आप इसके बारे में अवधारणा अगर आपको लगता।
यह है सभी को अलग है जो कुछ भी आपकी जानकारी बाल्टी में कर रहे हैं,
उन्हें छँटाई, और फिर खोज वहाँ के साथ संबद्ध है कि सूचीबद्ध करता है।
>> कूल।
ठीक है, अब हम एक अलग प्रकार का है डेटा संरचना का एक पेड़ कहा जाता है कि।
चलो पर चलते हैं और कोशिश करता है के बारे में बात है, जो अलग अलग हैं
लेकिन एक ही श्रेणी में।
अनिवार्य रूप से, सभी एक पेड़ के बजाय है के रैखिक तरह से डेटा के आयोजन
एक हैश तालिका आप does-- कि , यह एक ऊपर और एक नीचे मिला है पता
और फिर आप की तरह it-- एक के बंद लिंक पेड़, आप जड़ है जो एक फोन ऊपर है
और फिर यह सब उसके चारों ओर पत्तियों की है।
>> और तो सब तुम यहाँ है सिर्फ शीर्ष नोड है
कि अन्य नोड्स के लिए, अंक कि अंक अधिक नोड्स के लिए, और इतने पर और आगे।
और तो आप सिर्फ बंटवारे शाखाएं हैं।
यह आयोजन का सिर्फ एक अलग तरीका है डेटा, और हम इसे एक पेड़ फोन क्योंकि,
आप लोग इसे सिर्फ just-- एक पेड़ की तरह देखने के लिए बाहर मॉडलिंग की।
हम पेड़ों इसे कहते हैं यही कारण है कि।
>> हैश तालिका एक मेज की तरह लग रहा है।
एक पेड़ सिर्फ एक पेड़ की तरह लग रहा है।
यह सब एक अलग है नोड्स के आयोजन का रास्ता
अपनी आवश्यकताओं क्या कर रहे हैं पर निर्भर करता है।
>> तो अगर आप एक जड़ है और तो आप छोड़ दिया है।
तरीका यह है कि हम विशेष रूप से कर सकते हैं यह एक द्विआधारी पेड़ है के बारे में सोचना,
एक द्विआधारी पेड़ सिर्फ एक है एक पेड़ के विशिष्ट प्रकार
जहां प्रत्येक नोड केवल अंक करने के लिए, अधिकतम पर, दो अन्य नोड्स।
और यहाँ तो आप अलग है अपने पेड़ में समरूपता
कि यह आसान एक तरह से देखने के लिए बनाता है क्या मान पर आप तो आप कर रहे हैं क्योंकि
हमेशा एक छोड़ दिया है या एक अधिकार है।
से एक बाएं तीसरे जैसे वहाँ कभी नहीं छोड़ दिया है या बाएं से एक चौथाई।
इसे आप एक को छोड़ दिया और एक सही है बस बात और आप उन दोनों में से किसी को खोज सकते हैं।
और तो क्यों यह उपयोगी है?
यह है कि जिस तरह से आप देख रहे हैं उपयोगी है
ठीक है, मूल्यों के माध्यम से खोज करने के लिए?
बल्कि द्विआधारी को लागू करने से एक त्रुटि सरणी में खोज,
आप नोड्स सम्मिलित करने में सक्षम होना चाहता था और इच्छा पर है और यह भी नोड्स दूर ले
खोज की रक्षा द्विआधारी खोज की क्षमता।
तो इस तरह से, हम किस तरह का हो जब हम याद tricking--
लिंक सूचियों द्विआधारी खोज कर सकते हैं नहीं कहा?
हम किस तरह के एक डेटा संरचना का निर्माण कर रहे हैं तरकीबें काम करने में वह है।
>> और इसलिए क्योंकि लिंक सूचियों, रैखिक हैं वे केवल एक के बाद एक कड़ी।
हम किस तरह का हो सकता है संकेत के विभिन्न प्रकार
अलग नोड्स के लिए उस बिंदु कि खोज के साथ हमारी मदद कर सकते हैं।
और यहाँ तो, यदि मैं चाहता था एक द्विआधारी खोज वृक्ष है,
मैं जानता हूँ कि मेरे बीच कि 55 यदि।
मैं सिर्फ इतना है कि बनाने के लिए जा रहा हूँ मेरे बीच के रूप में, अपने रूट के रूप में,
और फिर मैं जा रहा हूँ मूल्यों इसे दूर स्पिन।
>> यहाँ तो, मैं के लिए खोज करने के लिए जा रहा हूँ अगर 66 का मूल्य है, मैं 55 में शुरू कर सकते हैं।
यह 55 से 66 अधिक है?
हाँ, यह है, इसलिए मुझे लगता है मैं खोज mus जानते मैं n इस पेड़ का सही सूचक।
मैं 77 के पास जाओ।
ठीक है, कम से कम या 77 से अधिक से अधिक 66 है?
ओह, यह तुलना में कम है, तो आप जानते हैं, छोड़ दिया है कि नोड हो गया है।
>> और यहाँ तो हम किस तरह का संरक्षण कर रहे हैं सरणियों के बारे में महान चीजों के सभी,
इतना गतिशील आकार की तरह वस्तुओं की जा रही है,
डालने और अपनी मर्जी से नष्ट करने में सक्षम, निश्चित बारे में चिंता करने के लिए बिना
अंतरिक्ष की राशि।
हम अभी से सभी की रक्षा उन अद्भुत बातें
यह भी रक्षा करने में सक्षम किया जा रहा है, जबकि लॉग इन करें और द्विआधारी खोज के समय खोज
हम पहले से ही थे कि एक वाक्यांश प्राप्त करने में सक्षम।
>> कूल डेटा संरचना, की तरह जटिल, नोड को लागू करने के लिए।
आप यह सब देख सकते हैं नोड की संरचना है
आप एक छोड़ दिया है कि और एक सही सूचक।
यही कारण है कि यह सब है।
तो बजाय बस से एक एक्स या पिछले एक कर रही है।
तुम तो एक छोड़ दिया है या एक अधिकार है, और है आप की तरह उन्हें एक साथ लिंक कर सकते हैं
लेकिन आप इतनी चुनें।
>> ठीक है, हम वास्तव में जा रहे हैं बस कुछ मिनट लग।
तो हम यहाँ वापस जाने के लिए जा रहे हैं।
जैसा कि मैंने पहले कहा था, मैं एक तरह से समझाया
हम कैसे पीछे तर्क इस खोज के माध्यम से होगा।
हम कोशिश करने के लिए जा रहे हैं इस बाहर pseudocoding देखने के लिए
हम किस तरह का आवेदन कर सकते हैं, तो द्विआधारी खोज का एक ही तर्क
डेटा संरचना का एक अलग प्रकार के।
तुम लोगों के एक जोड़े की तरह लेना चाहते हैं मिनटों अभी इस बारे में सोचने के लिए।
ठीक।
ठीक है, मैं जा रहा हूँ वास्तव में सिर्फ आप कोई the-- दे,
हम पहले स्यूडोकोड के बारे में बात करेंगे।
तो किसी को चाहता है पर एक वार देने के लिए क्या
आप जब ऐसा करना चाहते हैं, पहली बात आप खोज कर रहा है बाहर शुरू कर रहे हैं?
हम देख रहे हैं 66 का मूल्य क्या है
अगर हम क्या करना चाहते पहली बात हम इस पेड़ खोज द्विआधारी करने के लिए करना चाहते हैं?
>> दर्शकों: आप सही देखना चाहता हूँ और [अश्राव्य] बाईं देखो और देखो
अधिक से अधिक संख्या।
>> ANDI PENG: हाँ, बिल्कुल।
तो अगर आप अपने रूट को देखने के लिए जा रहे हैं।
आप कह सकते हैं तरीके के बहुत सारे है यह अपने माता पिता के नोड लोगों का कहना है।
मैं क्योंकि जड़ कहना पसंद उस पेड़ की जड़ की तरह है।
आप को देखने के लिए जा रहे हैं अपने रूट नोड, और आप कर रहे हैं
देखने जा रहे 66 से अधिक है अधिक या कम से कम 55।
और यह ठीक है, यह है, की तुलना में अधिक है, तो की तुलना में अधिक है, जहां हम देखना चाहते हैं?
हम कहाँ सही, अब खोज करने के लिए करना चाहते हैं?
हम खोज करना चाहते हैं इस पेड़ के ठीक आधे।
>> तो हमारे पास है, आसानी से, एक सही करने के लिए बताते हैं कि सूचक।
और इतना तो हम सेट कर सकते हैं हमारे नए रूट 77 किया जाना है।
हम सिर्फ जहाँ भी लिए जा सकते हैं सूचक इशारा कर रहा है।
खैर, ओह, यहाँ हम शुरू कर रहे हैं 77 में, और हम सिर्फ यह कर सकते हैं
बारी बारी से फिर से और फिर से ऐसा करते हैं।
इस तरह, आप की तरह का एक समारोह है।
आप आपको लगता है कि खोज का एक तरीका है बस और अधिक और अधिक से अधिक दोहरा सकते हैं,
आप देखने के लिए चाहते हैं, जहां पर निर्भर करता है आप अंततः मूल्य के लिए मिलता है जब तक
आप के लिए खोज रहे हैं।
सही बात?
>> मैं आप वास्तविक दिखाने के बारे में हूँ कोड, और यह कोड का एक बहुत कुछ है।
कोई ज़रूरत नहीं है बाहर बेकार करने के लिए।
हम इसके माध्यम से बात करेंगे।
>> दरअसल नहीं।
वह सिर्फ स्यूडोकोड था।
ठीक है, कि सिर्फ स्यूडोकोड था, जो थोड़ा जटिल है,
लेकिन यह पूरी तरह से ठीक है।
यहाँ हर कोई साथ निम्नलिखित?
जड़ रिक्त है, तो वापसी झूठी क्योंकि इसका मतलब है
आप भी वहाँ कुछ भी नहीं है।
>> जड़ एन इसलिए यदि मूल्य है, तो यह आप देख रहे हैं एक होता है,
तो आप सच वापसी करने जा रहे हैं क्योंकि आप जानते हैं कि आप इसे पाया।
लेकिन मूल्य कम है तो n का जड़ से, आप कर रहे हैं
बाएं खोज करने के लिए जा रहा बच्चे या बाईं पत्ती,
जो कुछ भी तुम इसे पुकारना करना चाहते हो।
और मूल्य जड़ से अधिक है, आप सही पेड़ खोज करने के लिए जा रहे हैं,
फिर बस समारोह चलाने खोज के माध्यम से फिर से।
>> और रूट, अशक्त है कि कि यदि आप अंत में पहुँच गए हैं इसका मतलब है?
यही नहीं, आप इसका मतलब है अधिक से अधिक पत्तियों खोज करने के लिए,
तब तुम्हें मैं, ओह, पता है यह यहाँ नहीं है लगता है
मैं माध्यम से देखा है क्योंकि के बाद और यह यहाँ नहीं है पूरी बात,
यह सिर्फ यहाँ नहीं हो सकता है।
>> कि हर किसी के लिए मतलब?
तो यह संरक्षण द्विआधारी खोज की तरह है लिंक सूचियों की क्षमताओं।
कूल, और इसलिए दूसरे प्रकार डेटा संरचना आप लोगों में से
अपने pset पर लागू करने की कोशिश कर सकते हैं, आप केवल एक ही विधि का चयन करना है।
लेकिन शायद एक वैकल्पिक तरीका करने के लिए हैश तालिका हम एक Trie कहते हैं।
>> सभी एक Trie है एक पेड़ के विशिष्ट प्रकार है कि
अन्य मूल्यों के लिए जाना है कि मूल्यों है।
तो बजाय एक द्विआधारी होने इस अर्थ में पेड़ केवल एक ही है कि
बात करने के लिए दो बात कर सकते हैं, आप कर सकते हैं बहुत, बहुत से बातें करने के लिए एक बात बिंदु।
आप अनिवार्य सरणियों है जिसमें से आप की दुकान के अंदर
अन्य सरणियों को इंगित कि संकेत।
>> तो हम कैसे की नोड एक Trie परिभाषित करेगा
हम एक है चाहता हूँ है बूलियन, ग पद, है ना?
तो नोड बूलियन है सही है या गलत तरह
के सिर पर सब से पहले उस सरणी, इस एक शब्द है?
दूसरे, आप संकेत है चाहता हूँ जो कुछ भी करने के लिए उनमें से आराम कर रहे हैं।
थोड़ा जटिल, थोड़ी संक्षिप्त है, लेकिन मैं क्या है कि सभी साधन समझा जाएगा।
>> यहाँ तो, शीर्ष पर है, अगर आप एक सरणी पहले ही घोषित कर दिया है,
आप एक बूलियन है, जहां एक नोड मोर्चे पर संग्रहीत मूल्य
कि आप इस एक शब्द है कहता है?
इस एक शब्द भी नहीं है?
और फिर आप हैं अपने सरणी के बाकी है कि
वास्तव में भंडार सभी यह हो सकता है की संभावनाओं।
तो, उदाहरण के लिए, की तरह शीर्ष पर आपके पास
सच है या कहते हैं कि पहली बात यह है झूठी, हाँ या नहीं, इस एक शब्द है।
>> और फिर आप के माध्यम से 26 0 है आप स्टोर कर सकते हैं कि पत्र।
मैं यहाँ खोज करना चाहता था बल्लेबाजी के लिए, मैं ऊपर से जाना
और मैं मैं में बी मिल बी के लिए लग रही है मेरी सरणी, और इसलिए मुझे पता है, ठीक है, बी एक शब्द है?
बी इसलिए इस प्रकार, एक शब्द भी नहीं है मैं खोज रखना चाहिए।
मैं बी से जाना है, और मैं करने के लिए देखो बी की ओर इशारा करती है कि सूचक
और मुझे लगता है, जानकारी का एक और सरणी देखना हम पहले था कि एक ही संरचना।
>> और, ओह अगले here-- [अश्राव्य] में अक्षर ए है
तो हम उस सरणी में देखो।
हम आठवें मूल्य मिल जाए, और फिर हम, ओह, यह देखने के लिए देखो
अरे, यह है कि एक शब्द, बी-एक शब्द है?
यह एक शब्द नहीं है।
हम देख रखने के लिए मिल गया है।
>> और इतना तो हम करने के लिए जहां देखो एक अंक के सूचक,
और यह किसी अन्य तरीके से करने के लिए अंक जो हम और अधिक मूल्य संग्रहीत है।
और अंत में, हम करने के लिए मिलता है एक शब्द है, जो बी-ए-टी,।
और तो अगली बार तुम देखो, आप जा रहे हैं
हाँ, कि जांच करने के लिए, इस बूलियन समारोह सच है।
और इसलिए इस अर्थ में हम किस तरह कर रहे हैं की सरणियों के साथ एक पेड़ खा रहे हैं।
>> तो फिर आप की तरह नीचे खोज सकते हैं।
बल्कि एक समारोह hashing से और लिंक सूची से मान निर्दिष्ट
आप सिर्फ एक को लागू कर सकते हैं downwords खोज करता है कि Trie।
सच में, सच सामान जटिल।
मैं जैसा हूँ क्योंकि बारे में सोचने के लिए आसान नहीं इतने सारे डाटा संरचनाओं बाहर थूकना
आप पर है, लेकिन एक तरह से हर कोई करता है इस बात का तर्क समझ कैसे काम करता?
>> अच्छा ठीक है।
तो बी-ए-टी, और उसके बाद आप खोज करने के लिए जा रहे हैं।
आप जा रहे हैं अगली बार ओह, अरे, यह सच है, यह देखने के लिए,
इस तरह मैं इस एक शब्द होना चाहिए पता है।
>> चिड़ियाघर के लिए एक ही बात है।
यहाँ तो बात करते हैं, तो ठीक है अब है हम अब ठीक है, चिड़ियाघर के लिए खोज करने के लिए चाहता था,
वर्तमान में चिड़ियाघर एक नहीं है हमारे शब्दकोश में शब्द
क्योंकि, तुम लोगों को देख सकते हैं, के रूप में हम एक बूलियन है कि पहले स्थान पर
लौटने के सच्चे ज़ूम के अंत में है।
हम Z-ओ-ओ-एम है।
>> और यहाँ तो, हम वास्तव में नहीं है हमारे शब्दकोश में शब्द, चिड़ियाघर,
इस चेक बॉक्स की जाँच नहीं है।
तो कंप्यूटर नहीं करता है चिड़ियाघर में एक शब्द भी पता है कि
क्योंकि हम है कि रास्ता केवल एक ज़ूम यहाँ, यह संग्रहीत
वास्तव में एक बूलियन मान है सच है कि निष्क्रिय कर दिया है।
हम सम्मिलित करना चाहते हैं तो अगर शब्द, चिड़ियाघर, हमारे शब्दकोश में,
हम चाहते हैं कि करने के बारे में कैसे जाना होगा?
हम यह सुनिश्चित करने के लिए क्या करना है क्या हमारे कंप्यूटर जेड-ओ-ओ एक शब्द भी जानता है कि
और न पहला शब्द जेड-ओ-ओ-एम है?
>> दर्शकों: [अश्राव्य]
>> ANDI PENG: वास्तव में, हम मतलब यह है कि बनाना चाहते
यहाँ, कि बूलियन मान है यह सच है कि बंद की जाँच की।
जेड-ओ-ओ, तो हम उस जाँच करने के लिए जा रहे हैं, इसलिए हम वास्तव में, हे, चिड़ियाघर में एक शब्द है।
मैं बताने जा रहा हूँ यह एक शब्द भी ऐसा है कि कंप्यूटर
, जब कंप्यूटर की जाँच करता है कि यह चिड़ियाघर एक शब्द है कि जानता है।
>> इन सभी डेटा क्योंकि याद है संरचनाओं, यह हमारे लिए बहुत आसान है
ओह, बल्ला एक शब्द है, कहने के लिए।
चिड़ियाघर में एक शब्द है।
ज़ूम एक शब्द है।
लेकिन आप इसे बना रहे हैं जब, कंप्यूटर कोई जानकारी नहीं है।
>> तो अगर आप वास्तव में यह बताने के लिए है क्या बिंदु पर इस एक शब्द है?
किस बिंदु पर यह एक शब्द नहीं है?
और किस बिंदु पर मुझे क्या करना है चीजों को खोज करने की जरूरत है,
और किस बिंदु पर मैं अगले जाने की जरूरत है?
इस बात का स्पष्ट सब लोग?
कूल।
>> और इतना तो आता है की समस्या को कैसे हम करेंगे
कुछ डालने के बारे में जाना कि वहाँ वास्तव में नहीं है?
तो चलो बस हम सम्मिलित करना चाहते हैं, हम कहते हैं हमारे Trie में शब्द, स्नान,।
तुम लोगों को वर्तमान की तरह देख सकते हैं अब हम सब, बी-ए-टी है
और इस नए डेटा संरचना एक पिंट वहाँ था कि
हम यह मान क्योंकि बातिल की ओर इशारा किया ओह, बी-ए-टी के बाद कोई शब्द नहीं है, कि,
यही कारण है कि हम रखने की जरूरत है कि टी के बाद होने बातें
>> हम यदि आप करते हैं लेकिन समस्या पैदा होती है बाद आता है कि एक शब्द है चाहता हूँ
टी।
आप स्नान है, तो आप कर रहे हैं एक एच सही चाहते करने के लिए जा रहा है।
और इसलिए हम ऐसा करने जा रहे हैं जिस तरह है हम एक अलग नोड बनाने के लिए जा रहे हैं।
हम जो भी राशि आवंटित नहीं कर रहे हैं इस नई सरणी के लिए स्मृति की,
और हम संकेत पुन: असाइन करने के लिए जा रहे हैं।
>> हम आवंटित करने के लिए जा रहे हैं एच, सब से पहले, इस अशक्त,
हम से छुटकारा पाने के लिए जा रहे हैं।
हम करने के लिए जा रहे हैं एच बिंदु नीचे की ओर।
हम एक एच देखते हैं, तो हम यह चाहते हैं कहीं और जाने के लिए।
>> यहाँ में, हम तो हाँ बंद की जांच कर सकते हैं।
हम टी के बाद एक एच मारा, ओह, फिर हम इस एक शब्द है कि पता है।
बूलियन सच वापसी करने जा रहा है।
सब जानते हैं कि कैसे हुआ पर स्पष्ट?
ठीक।
>> तो अनिवार्य रूप से, सभी की इन आंकड़ों संरचनाओं
हम आज के ऊपर चला गया है कि, मैं वास्तव में, वास्तव में उन्हें जल्दी से ऊपर चला गया है
और बहुत ज्यादा नहीं करने में विस्तार, और वह ठीक है।
आप खिलवाड़ शुरू करने के बाद इसके साथ, आप हो जाएगा
जहां का ट्रैक रखने सभी संकेत दिए गए हैं,
क्या में चल रहा है आपके डाटा संरचनाओं, वगैरह।
वे बहुत उपयोगी हो जाएगा और यह आप पर निर्भर है
लोग पूरी तरह से कैसे बाहर निकालने के लिए आप चीजों को लागू करना चाहते हैं।
>> और तो pset4 के 5-- ओह, यह गलत है।
Pset5 गलत वर्तनी है।
जैसा कि मैंने पहले कहा, आप एक बार, करने के लिए जा रहे हैं फिर, हम से स्रोत कोड डाउनलोड करें।
तीन मुख्य होना करने के लिए वहाँ जा रहा है चीजों को आप डाउनलोड कर दिया जाएगा।
आप शब्दकोशों डाउनलोड करेंगे KERS, और ग्रंथों।
>> उन सभी बातें कर रहे हैं या तो शब्दों का शब्दकोशों
हम आप की जाँच करना चाहते हैं कि या जानकारी का परीक्षण
हम आप चेक जादू करने के लिए चाहते हैं।
और हां शब्दकोशों हम आप जा रहे हैं देना
आप हम चाहते हैं कि वास्तविक शब्द देने के लिए आप है कि एक तरह से किसी भी तरह की दुकान के लिए
एक सरणी से ज्यादा कुशल है।
और फिर ग्रंथों हैं हम क्या कर रहे हैं होने जा रहा
आप पूछ सुनिश्चित करने के लिए जाँच करने के लिए जादू शब्दों के सभी वास्तविक शब्द नहीं हैं।
>> की और इसलिए तीन ब्लाकों हम आपको दे देंगे कि कार्यक्रमों
dictionary.c कहा जाता है, dictionary.h, और speller.c।
और इतना सब dictionary.c है करता है क्या आप को लागू करने के लिए कहा।
यह शब्द लोड करता है।
यह चेक उन्हें जादू, और यह सुनिश्चित करती है कि सब कुछ ठीक से डाला जाता है।
>> diction.h सिर्फ एक पुस्तकालय फ़ाइल है कि उन सभी कार्यों की घोषणा की।
और speller.c, हम तुम्हें देने के लिए जा रहे हैं।
आप इसे किसी भी संशोधित करने की जरूरत नहीं है।
सभी speller.c है कि ले करता है, यह भार है, यह की गति की जांच करता है,
कैसे तरह का बेंचमार्क परीक्षण जल्दी से आप काम करने में सक्षम हो।
>> यह एक स्पेलर है।
बस के साथ गड़बड़ नहीं है, लेकिन कर सुनिश्चित करें कि आप यह क्या कर रहा है समझते हैं।
हम एक समारोह में कहा जाता getrusage का उपयोग करने वाले अपने जादू के प्रदर्शन का परीक्षण करती है
चेकर।
सभी यह मूल रूप से परीक्षण है करता है अपने शब्दकोश में सब कुछ के समय,
इसलिए यदि आप इसे समझते हैं सुनिश्चित करें।
इसके साथ गड़बड़ नहीं करने के लिए सावधान रहना या बाकी चीजें ठीक से नहीं चलेंगे।
>> और इस चुनौती से निपटने के थोक के लिए है तुम लोग वास्तव में dictionary.c को संशोधित करने के लिए।
हम तुम्हें देने के लिए जा रहे हैं एक शब्दकोश में 140,000 शब्द।
हम आपको एक पाठ देने के लिए जा रहे हैं उन शब्दों है कि फ़ाइल,
और हम आप को संगठित करने के लिए सक्षम होना चाहता हूँ एक हैश तालिका या एक Trie में उन्हें
हम जादू करने के लिए जब आप से पूछना है क्योंकि आप जादू कर रहे हैं तो कल्पना check--
होमर ओडिसी तरह की जाँच।
यह इस विशाल, विशाल परीक्षण की तरह है।
>> हर एक कल्पना कीजिए कि अगर शब्द आप देखने के लिए था
140,000 मूल्यों की एक सरणी के माध्यम से।
यही कारण है कि हमेशा के लिए ले जाएगा अपनी मशीन को चलाने के लिए।
हम अपने को व्यवस्थित करना चाहते यही कारण है कि अधिक कुशल डेटा संरचनाओं में डेटा
इस तरह के एक हैश तालिका या एक Trie के रूप में।
और फिर आप लोग तरह कर सकते हैं आप पहुँच खोज जब की
चीजों को और अधिक आसानी से और अधिक तेजी से।
>> और तो टक्करों को हल करने के लिए सावधान रहना होगा।
आप एक गुच्छा पाने के लिए जा रहे हैं ए के साथ कि शुरू के शब्दों का
आप एक गुच्छा शब्द पाने के लिए जा रहे हैं यह आप पर निर्भर बी के साथ शुरू
आप चाहते हैं कि कैसे लोग इसे हल करने के लिए।
शायद और भी है कुशल हैश समारोह
के सिर्फ पहले अक्षर से कुछ है, और इतनी है कि आप पर निर्भर है
लोग एक तरह से आप चाहते हैं जो कुछ करना है।
>> हो सकता है कि आप जोड़ना चाहते हैं एक साथ सभी पत्र।
हो सकता है कि आप अजीब बातें करते हैं पसंद करना चाहते हैं पत्रों की संख्या खाते में,
जो भी हो।
आप क्या करना चाहते कैसे तुम लोगों के लिए ऊपर।
क्या आप हैं, तो एक हैश तालिका करना चाहते हैं पूरी तरह से आप पर निर्भर है, एक Trie की कोशिश करना चाहते हैं।
मैं उस समय के आगे चेतावनी दी जाएगी Trie आम तौर पर थोड़ा और अधिक मुश्किल है
वहाँ एक बहुत सिर्फ इसलिए अधिक संकेतों का ट्रैक रखने के लिए।
लेकिन पूरी तरह से तुम लोगों के लिए ऊपर।
यह कहीं अधिक कुशल है ज्यादातर मामलों में।
आप वास्तव में रखने के लिए सक्षम होना चाहता हूँ अपने संकेत के सभी का ट्रैक।
की तरह ही काम करते हैं मैं यहाँ क्या कर रहा था।
जब आप सम्मिलित करने के लिए कोशिश कर रहे हैं एक हैश तालिका में मूल्यों या हटाने के लिए,
आप कर रहे हैं कि यह सुनिश्चित कर लें वास्तव में ट्रैक रखने
सब कुछ है, क्योंकि जहां की यह मैं हूँ तो के लिए वास्तव में आसान है
शब्द, एंडी तरह डालने की कोशिश कर।
बस उस एक चलो का कहना है असली शब्द, शब्द, एंडी,
एक शब्द की एक विशाल सूची में।
>> मैं तो बस पुन: असाइन होता है एक सूचक गलत, ओह,
की सम्पूर्णता वहाँ चला जाता है मेरा लिंक सूची के बाकी।
अब केवल शब्द मैं है एंडी है, और अब
दूसरे शब्दों के सभी शब्दकोश खो गया है।
और तो आप बनाना चाहते अपने संकेत के सभी का ट्रैक रखने
वरना तुम्हें पाने के लिए जा रहे हैं अपने कोड में भारी समस्याओं।
कदम से कदम बातें ध्यान से बाहर ड्रा।
यह सोचने के लिए यह एक बहुत आसान बना देता है।
>> और अंत में, आप करने के लिए सक्षम होना चाहता हूँ अपने कार्यक्रम के अपने प्रदर्शन का परीक्षण
बड़े बोर्ड पर।
तुम लोगों को ले, तो एक अब ठीक है CS50 को देखो,
हम बड़े बोर्ड कहा जाता है।
यह सबसे तेजी से स्कोर शीट है CS50 के सभी भर में जाँच बार जादू
अब ठीक है, मैं 10 की तरह शीर्ष लगता है कई बार मैं उनमें से आठ कर्मचारी हैं लगता है।
हम वास्तव में आप लोग हमें हरा करना चाहते हैं।
>> हम सब को लागू करने की कोशिश कर रहे थे संभव के रूप में सबसे तेजी से कोड।
हम तुम लोगों को चुनौती देने की कोशिश करना चाहते हैं हमें और हम सभी से अधिक तेजी से लागू
कर सकते हैं।
और हां यह सच है हम कर रहे हैं कि पहली बार
आप लोग पूछ pset कि क्या करना आप वास्तव में जो कुछ भी विधि में कर सकते हैं
आप चाहते हैं।
>> मैं हमेशा इस जैसा है, का कहना है एक वास्तविक जीवन समाधान करने के लिए, है ना?
मैं अरे, मैं तुम्हें यह करने की जरूरत है, कहते हैं।
मेरे लिए इस करता है कि एक कार्यक्रम का निर्माण।
लेकिन आप चाहते हैं कि यह क्या है।
मैं सिर्फ मैं तेजी से करना चाहते हैं कि पता है।
यही कारण है कि इस सप्ताह के लिए अपनी चुनौती है।
तुम लोग, हम जा रहे हैं आप एक काम देने के लिए।
हम आपको एक चुनौती देने के लिए जा रहे हैं।
और फिर यह आप लोगों के लिए हो रहा है पूरी तरह से सिर्फ यह पता लगाने के लिए
तेज और सबसे क्या है कारगर तरीका यह लागू करने के लिए।
हाँ?
>> दर्शकों: अगर हम करने के लिए अनुमति दी जाती है तेज तरीके से अनुसंधान करने के लिए करना चाहता था
हम क्या कर सकते हैं, ऑनलाइन हैश टेबल ऐसा करने के लिए कि और किसी और के कोड का हवाला देते हैं?
ANDI PENG: हाँ, पूरी तरह से ठीक है।
तो तुम लोग पढ़ें कल्पना, एक लाइन भी नहीं है
आप लोग कहते हैं कि कल्पना में हैश अनुसंधान करने के लिए पूरी तरह से स्वतंत्र हैं
क्या कर रहे हैं कुछ पर कार्य तेज हैश कार्यों की
के रूप में चीजों के माध्यम से चलाने के लिए आपको लगता है कि कोड का हवाला देते रूप में लंबे समय।
तो कुछ लोगों को पहले से ही है तेजी से तरीकों का पता लगा
की तेजी के, जादू चेकर्स कर रही है जानकारी के भंडारण के तरीके।
पूरी तरह से तुम लोगों के लिए आप पर निर्भर है, तो ठीक है, सिर्फ इतना है कि लेने के लिए करना चाहते हैं?
आप हवाला रहे हैं सुनिश्चित करें।
चुनौती वास्तव में यहाँ हम परीक्षण करने के लिए कोशिश कर रहे हैं कि
क्या आप जानते हैं कि यकीन कर रहा है अपने तरह के आसपास संकेत दिए।
जहाँ तक आप को लागू करने के रूप में वास्तविक हैश समारोह
और इस तरह के साथ आ रहा है गणित है कि ऐसा करने के लिए,
तुम लोगों को अनुसंधान कर सकते हैं जो कुछ भी तरीकों ऑनलाइन आप लोग चाहते हैं।
हाँ?
>> दर्शकों: हम बस का हवाला देते हैं [अश्राव्य] का उपयोग करके?
>> ANDI PENG: हाँ।
आप कर सकते हैं बस, अपनी टिप्पणी में, आप, ओह, जैसे तलब कर सकते हैं
बेकार से लिया, बेकार, बेकार, हैश समारोह।
किसी को भी किसी भी सवाल है?
हम वास्तव में breezed आज अनुभाग के माध्यम से।
मैं करने के लिए यहाँ तक हो जाएगा के रूप में अच्छी तरह से सवालों के जवाब।
>> इसके अलावा, जैसा कि मैंने कहा, कार्यालय घंटों आज रात और कल।
इस सप्ताह वास्तव में है कल्पना सुपर आसान और पढ़ने के लिए सुपर कम।
मैं तो बस, एक नज़र लेने का सुझाव होगा यह की सम्पूर्णता के माध्यम से पढ़ा।
>> और Zamyla वास्तव में आप चलता है कार्यों में से प्रत्येक के माध्यम से
आप को लागू करने की जरूरत है, और इसलिए यह है सब कुछ कैसे करना है बहुत, बहुत साफ है।
सिर्फ यकीन है कि आप कर रहे हैं बनाने के लिए संकेत का ट्रैक रखने।
यह एक बहुत ही चुनौतीपूर्ण pset है।
>> यह की तरह है क्योंकि चुनौतीपूर्ण नहीं है ओह, अवधारणाओं इतना अधिक कर रहे हैं
मुश्किल है, या आप सीखने के लिए है रास्ता इतना नई वाक्य रचना
आप पिछले pset के लिए किया था।
इस pset मुश्किल है क्योंकि इतने सारे संकेत कर रहे हैं,
और फिर इसे एक बार करने के लिए बहुत, बहुत आसान है आप नहीं सक्षम हो अपने कोड में एक बग है
उस बग है जहां खोजने के लिए।
>> और तो पूर्ण और आप में बोलना विश्वास लोग हमारे [अश्राव्य] हरा करने के लिए सक्षम होने के लिए
वर्तनी।
मैं वास्तव में कोई नहीं लिखा मेरा है अभी तक, लेकिन मुझे लगता है मेरा लिखने के बारे में हूँ।
आप लिख रहे हैं तो तुम्हारा है, मैं मेरा लिख ​​सकता हूँ।
मैं बनाने के लिए प्रयास करने के लिए जा रहा हूँ मेरा तेजी से तुम्हारा से।
हम सबसे तेजी से एक है जो देखेंगे।
>> और हाँ, मुझे के सभी देखेंगे यहां मंगलवार को तुम लोग।
मैं एक pset कार्यशाला की तरह एक तरह से चलाया जाएगा।
वर्गों की यह सब सप्ताह, pset कार्यशालाओं हैं
तो तुम लोग अवसरों के बहुत सारे है मदद के लिए कार्यालय समय के रूप में हमेशा की तरह,
और मैं वास्तव में करने के लिए तत्पर हैं अपने लोग 'कोड के सभी पढ़ रहे हैं।
मैं यहाँ आप यदि क्विज़ ऊपर है लोग उन मिलता आना चाहते हैं।
बस इतना ही।