[संगीत खेल]
डेविड जे Malan: सब ठीक है.
इस CS50 है.
इस हफ्ते पांच जारी रखा है, और हम कुछ अच्छी खबर है और कुछ बुरी खबर है.
तो अच्छी खबर यह है कि CS50 है इस शुक्रवार की शुरूआत.
आप हमारे साथ शामिल करना चाहते हैं, यहां सामान्य यूआरएल के लिए सिर.
इससे भी अच्छी खबर है, कोई व्याख्यान इस 13 वीं सोमवार आ रहा है.
थोड़ा कम बेहतर खबर है, प्रश्नोत्तरी शून्य अगले बुधवार है.
अधिक जानकारी के लिए किया जा सकता है यहाँ इस URL पर पाया.
और अगले कुछ दिनों में हम रिक्त स्थान को भरने हो जाएगा
कमरे के संबंध में हम आरक्षित होगा.
बेहतर खबर है हूँ एक पाठ्यक्रम में व्यापक समीक्षा हो
सत्र इस आ शाम में सोमवार.
पाठ्यक्रम के लिए देखते रहो स्थान और जानकारी के लिए वेबसाइट.
यह एक है, भले ही धारा, छुट्टी, भी रूप में अच्छी तरह से पूरा करेगा.
सबसे अच्छी खबर, अगले शुक्रवार को व्याख्यान.
तो यह एक परंपरा है कि हम है पाठ्यक्रम के अनुरूप है.
Just-- यह अद्भुत होने जा रहा है.
आप की तरह बातें देखेंगे लगातार समय डेटा संरचनाओं
और हैश तालिकाओं और पेड़ों और कोशिश करता है.
और हम जन्मदिन की समस्याओं के बारे में बात करेंगे.
सामान की एक पूरी गुच्छा अगले शुक्रवार इंतजार कर रहा है.
ठीक.
किसी भी तरह.
>> इसलिए हम किया गया है कि याद क्या है की इस तस्वीर पर ध्यान केंद्रित
हमारे कंप्यूटर की मेमोरी के अंदर.
तो स्मृति या राम जहां कार्यक्रमों है आप उन्हें चला रहे हैं, जबकि मौजूद हैं.
आप एक डबल क्लिक करें आइकन कुछ कार्यक्रम चलाने के लिए
या एक डबल क्लिक करें कुछ फ़ाइल को खोलने के लिए चिह्न
यह आपके कठिन से भरी हुई है ड्राइव या ठोस राज्य ड्राइव
राम, रैंडम एक्सेस मेमोरी, जहां में सत्ता से दूर चला जाता है जब तक यह रहता है
लैपटॉप ढक्कन बंद कर देता है या आप प्रोग्राम से बाहर निकलें.
>> अब जब कि स्मृति की जो आप शायद
1 गीगाबाइट इन दिनों, 2 गीगाबाइट, या और भी अधिक,
आम तौर पर बाहर रखी है किसी दिए गए कार्यक्रम के लिए
आयताकार के इस प्रकार में वैचारिक मॉडल
हम तल पर ढेर है जिससे और शीर्ष पर अन्य सामान का एक गुच्छा.
बहुत शीर्ष पर बात हम इस तस्वीर को देखा है
लेकिन इससे पहले कभी नहीं के बारे में बात की थी तथाकथित पाठ खंड है.
पाठ खंड सिर्फ एक अच्छा तरीका है शून्य और लोगों कह के कि
अपने वास्तविक संकलित कार्यक्रम रचना.
>> तो जब आप डबल क्लिक करें अपने मैक या पीसी पर माइक्रोसॉफ्ट वर्ड,
आप डॉट चलाते समय या एक पर मारियो स्लेश अपने टर्मिनल विंडो में लिनक्स कंप्यूटर,
रचना कि शून्य और लोगों पद या मारियो अस्थायी रूप से जमा हो जाती है
तथाकथित में अपने कंप्यूटर की रैम में एक विशेष कार्यक्रम के लिए पाठ खंड.
जाता है कि नीचे initialized और गई डेटा.
इस वैश्विक चर सामान की तरह है, हम में से कई का प्रयोग नहीं किया गया है कि,
लेकिन इस अवसर पर हम है वैश्विक चर था
या स्थिर रुप से तार परिभाषित कि कठिन "नमस्ते" जैसे शब्दों कोडित है
उपयोगकर्ता से नहीं ले रहे हैं कि कि अपने कार्यक्रम में हार्ड कोडित रहे हैं.
>> अब, नीचे तल पर हम तथाकथित ढेर है.
और ढेर, इस प्रकार अब तक, हम किया गया है उद्देश्यों की क्या प्रकार के लिए इस्तेमाल नहीं करते?
ढेर क्या के लिए इस्तेमाल किया गया है?
हाँ?
>> दर्शक: कार्य.
>> डेविड जे Malan: कार्यों के लिए?
कार्यों के लिए क्या मायने में?
>> दर्शक: तुम एक समारोह कहते हैं, तर्क ढेर पर नकल कर रहे हैं.
>> डेविड जे Malan: बिल्कुल.
आप एक समारोह कॉल करते हैं, तो अपने तर्क ढेर पर नकल कर रहे हैं.
इसलिए किसी भी एक्स या वाई या एक या बी आप एक समारोह में गुजर रहे हैं कि
अस्थायी रूप से पर डाल रहे हैं तथाकथित ढेर,
बस Annenberg में से एक की तरह डायनिंग हॉल ट्रे, और भी बातें
स्थानीय चर की तरह.
यदि आपके foo समारोह या अपने स्वैप समारोह स्थानीय चर है,
अस्थायी तरह, उन दो ढेर पर खत्म होता है.
अब, हम के बारे में बहुत ज्यादा बात नहीं करेंगे उन्हें, लेकिन इन वातावरण चर
तल पर हम कुछ समय पहले जब देखा मैं कुंजीपटल एक दिन में futzing था
और मैं चीजों पहुँचने शुरू argv 100 या argv 1000 की तरह,
बस elements-- मैं भूल जाते हैं numbers-- लेकिन उस
मेरे द्वारा पहुँचा जा नहीं करने वाले थे.
हम कुछ देखना शुरू किया स्क्रीन पर कायरता चिह्न.
उन तथाकथित थे पर्यावरण चर
के लिए वैश्विक सेटिंग की तरह मेरे कार्यक्रम या मेरे कंप्यूटर, नहीं करने के लिए
हाल के लिए असंबंधित हम चर्चा है कि बग,
SHELLSHOCK, कि हो गया है काफी कुछ कंप्यूटर नाक में दम.
>> अब अंत में, आज के फोकस में हम अंततः ढेर पर हो जाएगा.
यह स्मृति का एक और हिस्सा है.
और मौलिक यह सब स्मृति में एक ही बात है.
यह एक ही हार्डवेयर है.
हम की तरह बस रहे हैं विभिन्न समूहों के इलाज
के विभिन्न प्रयोजनों के लिए बाइट्स.
ढेर भी जहां होने जा रहा है आपसे अनुरोध है कि चर और स्मृति
ऑपरेटिंग सिस्टम से अस्थायी रूप से संग्रहीत किया जाता है.
>> लेकिन एक समस्या की तरह नहीं है यहाँ, चित्र के रूप में निकलता.
हम की तरह दो के बारे में जहाजों के टकराने के लिए.
आप अधिक से अधिक उपयोग के रूप में, क्योंकि आज हम देख ढेर के रूप में, और
आगे, आप का अधिक से अधिक उपयोग के रूप में ढेर, निश्चित रूप से बुरी बातें हो सकता है.
और वास्तव में, हम है कि पैदा कर सकते हैं जानबूझकर या अनजाने में.
पिछले cliffhanger तो समय इस कार्यक्रम था,
किसी भी कार्य की सेवा नहीं था जो प्रदर्शित करने के अलावा अन्य उद्देश्य
कैसे आप एक बुरा आदमी वास्तव में ले जा सकते हैं किसी कार्यक्रम में कीड़े का लाभ
और यहां तक ​​कि एक एक कार्यक्रम या पर ले पूरे कंप्यूटर सिस्टम या सर्वर.
तो बस नज़र को संक्षेप में, आप तल पर कि मुख्य नोटिस
आदेश पंक्ति में ले जाता है argv अनुसार तर्क,.
और यह एक समारोह च के लिए एक फोन है, अनिवार्य रूप से एक बेनाम समारोह बुलाया
एफ, और यह argv में गुजर रहा है [1].
>> तो कम में जो भी शब्द उपयोगकर्ता प्रकार इस कार्यक्रम के नाम के बाद शीघ्र,
और फिर यह मनमाना समारोह अप शीर्ष, एफ, एक स्ट्रिंग में लेता है, उर्फ ​​* चार,
हम चर्चा करने के लिए शुरू कर दिया है, के रूप में और यह सिर्फ "बार." यह कॉल
लेकिन हम कुछ भी कह सकते हैं.
और फिर इसके अंदर, वाणी एफ, वर्णों की एक सरणी की
12 ऐसे पात्रों c-- बुलाया.
>> अब, कहानी से मैं कह रहा था एक पल पहले, जहां स्मृति में
सी है, या उन 12 हैं खत्म हो जा घर का काम?
अभी स्पष्ट होना करने के लिए.
हाँ?
>> दर्शक: ढेर पर.
>> डेविड जे Malan: ढेर पर.
तो सी एक स्थानीय चर रहा है.
हम 12 वर्ण या 12 बाइट्स के लिए पूछ रहे हैं.
उन समाप्त करने के लिए जा रहे हैं तथाकथित ढेर पर.
अब अंत में यह अन्य समारोह है कि वास्तव में बहुत उपयोगी है
लेकिन हम वास्तव में इस्तेमाल नहीं किया है यह अपने आप को, strncopy.
यह स्ट्रिंग प्रतिलिपि मतलब है, लेकिन केवल अक्षर, एन अक्षर N.
तो एन अक्षर हो जाएगा सी में बार से नकल.
और कितने?
पट्टी की लंबाई.
तो दूसरे शब्दों में, कि एक लाइन, strncopy,
कॉपी करने के लिए जा रहा है प्रभावी ढंग से करने के लिए ग में पट्टी.
>> अब, बस की तरह का अनुमान लगाने इस कहानी का नैतिक,
क्या यहाँ संभावित समस्याग्रस्त है?
हम लंबाई जाँच कर रहे हैं भले ही बार की और strncopy में इसे पारित,
क्या आप अपने पेट है कह रही है अभी भी इस कार्यक्रम के बारे में टूट?
हाँ?
>> दर्शक: शामिल नहीं है अशक्त चरित्र के लिए कमरे.
डेविड जे Malan: शामिल नहीं है अशक्त चरित्र के लिए कमरे.
में संभावित विपरीत पिछले अभ्यास हम भी नहीं करते
एक प्लस 1 के रूप में इतनी ज्यादा कि अशक्त चरित्र को समायोजित.
लेकिन यह उससे भी बदतर है.
और क्या हम ऐसा करने में विफल रहे हैं?
हाँ?
>> दर्शक: [अश्राव्य]
डेविड जे Malan: बिल्कुल सही.
हम कड़ी मेहनत बहुत मनमाने ढंग से 12 कोडित किया है.
यह इतना नहीं है समस्या है, लेकिन तथ्य
हम भले ही जाँच नहीं कर रहे हैं कि पट्टी की लंबाई कम से कम 12 है
जो मामले में यह होने जा रहा है स्मृति में डाल करने के लिए सुरक्षित
हम आवंटित किया है कि कहा जाता सी.
दरअसल, बार की तरह अगर लंबे 20 वर्ण,
इस समारोह नकल प्रतीत होता है जिससे सी में बार से 20 वर्ण
कम से कम 8 बाइट्स लेने यह नहीं होना चाहिए कि.
यही कारण है कि यहां निहितार्थ है.
>> संक्षेप में, टूटा कार्यक्रम में तो.
एक बड़ी बात ऐसी नहीं है.
शायद तुम विखंडन दोष मिलता है.
हम सभी कार्यक्रमों में कीड़े लिया है.
हम सभी कीड़े हो सकता है सही अब कार्यक्रमों में.
लेकिन निहितार्थ क्या है?
वैसे, यहाँ की एक तेजी से बढ़ी में संस्करण अपने कंप्यूटर की मेमोरी की उस तस्वीर.
यह मेरी ढेर के नीचे है.
और वास्तव में, बहुत नीचे क्या है कहा जाता है माता पिता दिनचर्या पर ढेर, फैंसी तरीका
की है कि मुख्य कह.
समारोह में कहा कि जो कोई भी तो हम के बारे में बात कर रहे हैं कि एफ.
तो इस ढेर के नीचे है.
वापसी पता कुछ नया है.
यह हमेशा वहाँ गया है हमेशा लगता है कि तस्वीर में किया गया.
हम यह करने के लिए ध्यान बुलाया बस कभी नहीं.
यह पता चला है क्योंकि सी तरह काम करता है एक समारोह में एक और कहता है कि जब,
इतना ही नहीं करने के लिए तर्क करना समारोह ढेर पर धकेल दिया हो,
न केवल समारोह के स्थानीय करना चर ढेर पर धकेल दिया हो,
कुछ एक वापसी पता बुलाया भी ढेर पर डाल दिया जाता है.
विशेष रूप से, मुख्य कॉल फू अगर, मुख्य है स्मृति में स्वयं के पते, बैल कुछ,
प्रभावी ढंग से ढेर पर डाल दिया जाता है इतना है कि च इसे क्रियान्वित किया जाता है जब
पाठ में वापस करने के लिए कूद करने के लिए जानता है, जहां क्रियान्वित जारी रखने के लिए खंड.
>> हम धारणा यहाँ कर रहे हैं तो, मुख्य में, तो च बुलाया जाता है.
च पता कैसे करता है जो वापस हाथ नियंत्रण करने के लिए?
खैर, इस छोटे से यहाँ लाल में ब्रेडक्रम्ब,
वापसी पता कहा जाता है, यह सिर्फ चेक, कि वापसी पता क्या है?
ओह, मुझे यहाँ वापस मुख्य करने के लिए कूद करते हैं.
और कहा कि एक छोटा सा है एक अति सरलीकरण की,
शून्य और लोगों क्योंकि मुख्य लिए तकनीकी रूप से कर रहे हैं
यहाँ तकनीक खंड में.
लेकिन उस विचार है. च बस पता है क्या करना है
जहां तक ​​नियंत्रण अंततः वापस चला जाता है.
>> लेकिन जिस तरह से कंप्यूटर लंबी बातें बाहर रखी है
स्थानीय चर की तरह और तर्क इस तरह है.
इस तस्वीर के ऊपर में तो नीले इतना सब, च के लिए ढेर फ्रेम है
स्मृति की कि च विशेष रूप से उपयोग कर रहा है.
तो तदनुसार, कि नोटिस बार इस तस्वीर में है.
बार अपने तर्क था.
और हम ने दावा किया तर्क को कि कार्यों ढेर पर धकेल दिया हो.
और सी, ज़ाहिर है, इस तस्वीर में.
>> और सिर्फ सांकेतिक प्रयोजनों के लिए, शीर्ष बाएँ हाथ के कोने पर नोटिस
ब्रैकेट 0 सी क्या होगा और तो थोड़ा सही करने के लिए नीचे
सी ब्रैकेट 11 है.
तो दूसरे शब्दों में, आप कल्पना कर सकते हैं बाइट्स की एक ग्रिड है कि वहाँ
वहाँ है, जो पहले के ऊपर छोड़ दिया, नीचे जो की
उन 12 बाइट्स के अंतिम है.
>> लेकिन अब तेजी से आगे बढ़ाने के लिए प्रयास करें.
क्या हम पास अगर होने वाला है सी की तुलना में अब है कि एक स्ट्रिंग बार में?
और हम अगर जाँच नहीं कर रहे हैं यह वास्तव में लंबे समय तक 12 से अधिक है.
इस तस्वीर के किस हिस्से में जा रहा है बाइट्स 0, 1, 2, 3 द्वारा ओवरराइट हो,
डॉट डॉट डॉट, 11, और उसके बाद बुरा, 12, 19 के माध्यम से 13?
क्या, यहाँ होने जा रहा है आप आदेश से अनुमान अगर
कि सी ब्रैकेट 0 शीर्ष पर है और सी ब्रैकेट 11 के नीचे तरह है
सही करने के लिए?
हाँ?
>> दर्शक: खैर, यह जा रहा है * चार बार अधिलेखित करने के लिए.
>> डेविड जे Malan: हाँ, ऐसा लग रहा है आप * चार बार अधिलेखित करने के लिए जा रहे हैं.
और भी बुरा है, आप एक बहुत लंबे समय में भेज स्ट्रिंग, आप भी क्या ऊपर लिख सकता है?
वापसी पता.
कौन सा फिर से, बस एक तरह है कार्यक्रम जहां बताने के लिए ब्रेडक्रम्ब
जब एफ के लिए वापस जाने के लिए कहा जा रहा से किया जाता है.
>> तो बुरे लोगों को आम तौर पर क्या करते हैं वे एक कार्यक्रम भर आया है
वे चाहे वह उत्सुक हैं कि इस तरह से दोहन, छोटी गाड़ी
वह या वह ले जा सकते हैं उस बग का लाभ,
आम तौर पर वे नहीं मिलता यह सही पहली बार.
वे सिर्फ उदाहरण के लिए, भेजने शुरू, अपने कार्यक्रम में यादृच्छिक तार,
कीबोर्ड पर कि क्या, या स्पष्ट रूप से वे शायद
एक छोटे से कार्यक्रम के लिए लिखने बस स्वचालित रूप से तार उत्पन्न,
और के द्वारा अपने कार्यक्रम पर पीटना शुरू विभिन्न आदानों की बहुत सारी में भेज
अलग लंबाई में.
>> जैसे ही अपने कार्यक्रम दुर्घटनाओं के रूप में, कि एक अद्भुत बात है.
यह वह अर्थ है क्योंकि या वह की खोज की है
क्या वास्तव में शायद एक बग है.
और फिर वे अधिक चतुर प्राप्त कर सकते हैं और शुरू अधिक बाल बाल केंद्रित थी
उस बग का फायदा उठाने के लिए पर.
विशेष रूप से, क्या वह या वह हो सकता है ऐसा नमस्कार, सबसे अच्छा मामले में, भेज रहा है.
कोई बड़ी बात नहीं.
यह पर्याप्त छोटा है कि एक स्ट्रिंग है.
लेकिन क्या वह या वह भेजता है, और हम, के रूप में यह सामान्यीकरण हूँ
हमले शून्य तो code-- और है कि लोगों को बातें करते हैं
RM-आरएफ तरह, सब कुछ हटा दें कि हार्ड ड्राइव से या स्पैम भेजने
या किसी भी तरह की मशीन पर हमला?
>> इनमें से प्रत्येक तो अगर पत्र एक बस का प्रतिनिधित्व करता है
धारणा, हमले, हमले, हमले, हमले, कुछ बुरा कोड
किसी और ने लिखा है कि, लेकिन उस व्यक्ति को काफी चालाक है
न केवल सभी शामिल उन RM-RFS की, लेकिन यह भी
उसके या उसके पिछले कुछ बाइट्स है मेल खाती है कि एक नंबर हो
का पता करने के लिए अपने या अपने हमले कोड
वह या वह बस में पारित शीघ्र इसे उपलब्ध कराने के द्वारा,
आप प्रभावी रूप से कंप्यूटर चाल कर सकते हैं च क्रियान्वित किया जाता है जब देख में,
ओह, यह मेरे लिए कूद करने के लिए समय है वापस लाल भेजने वाले का पता करने के लिए.
लेकिन वह या वह किसी न किसी तरह है क्योंकि कि वापसी पता छा
उनकी खुद की संख्या के साथ, और वे काफी समझदार हो
कि विन्यस्त किया है करने के लिए नंबर के रूप में, का उल्लेख करने के लिए
सुपर ऊपर देखना वहाँ बाएं हाथ के कोने,
कंप्यूटर के वास्तविक पते उनके हमले कोड में से कुछ की स्मृति,
एक बुरा आदमी कंप्यूटर चाल कर सकते हैं अपने या अपने खुद के कोड को क्रियान्वित करने में.
>> और उस कोड, फिर से, कुछ भी हो सकता है.
यह आम तौर पर कहा जाता है बस जो खोल कोड,
ऐसा नहीं है कि कहने का एक तरीका RM-आरएफ के रूप में सरल आम तौर पर कुछ.
यह वास्तव में बैश की तरह कुछ है या एक वास्तविक कार्यक्रम उसे देता है
या उसे प्रोग्रामेटिक नियंत्रण निष्पादित करने के लिए वे चाहते हैं कि कुछ और.
तो संक्षेप में, यह सब साधारण तथ्य से निकला
शामिल इस बग जाँच नहीं कि अपने सरणी की सीमाओं.
और वैसे भी, क्योंकि कंप्यूटर काम है कि वे
से ढेर उपयोग प्रभावी ढंग से, धारणा,
ऊपर की ओर नीचे, लेकिन फिर तत्वों आप नीचे ऊपर बढ़ने ढेर पर धक्का
यह अविश्वसनीय रूप से समस्याग्रस्त है.
अब, इस के आसपास काम करने के तरीके हैं.
और सच कहूँ तो, भाषाएं हैं जिसके साथ इस के आसपास काम करने के लिए.
जावा, उदाहरण के लिए, प्रतिरक्षा है इस विशेष मुद्दे को.
वे आपको संकेत नहीं देते हैं.
वे तुम्हें नहीं देते प्रत्यक्ष स्मृति पते.
हम हैं कि इस शक्ति के साथ तो स्मृति में कुछ भी छूने के लिए
हम मानते, महान जोखिम, आता चाहते हैं.
>> तो एक आंख बाहर रखने के लिए.
सच में, अगर, महीने में या साल कभी भी आने के लिए
आप कुछ शोषण के बारे में पढ़ा एक कार्यक्रम या एक सर्वर की,
क्या तुमने कभी कुछ का एक संकेत देखते हैं एक बफर अतिप्रवाह हमले की तरह,
या पोट अतिप्रवाह एक और प्रकार है हमले की आत्मा में भी इसी तरह,
वेबसाइट के लिए प्रेरित करती है के रूप में ज्यादा आप यह जानते हैं, नाम,
यह सब बस के बारे में बात कर रहा है कुछ चरित्र का आकार ढेर
सरणी या अधिक आम तौर पर कुछ सरणी.
इस पर तो कोई प्रश्न,,?
घर पर इस कोशिश मत करो.
>> ठीक है.
तो malloc इस प्रकार अब तक हमारे नए कर दिया गया है हम स्मृति आवंटित कर सकते हैं कि में दोस्त
हम जरूरी में पता नहीं है कि इसलिए हम नहीं चाहते कि अग्रिम
में हार्ड कोड के लिए हमारे 12 जैसे कार्यक्रम संख्या.
उपयोगकर्ता हमें कितना कहता है एक बार वह या वह इनपुट के लिए करना चाहता डेटा,
हम चाहते हैं कि ज्यादा स्मृति malloc कर सकते हैं.
>> तो malloc यह तक पता चला है, हम यह प्रयोग कर रहे थे हद तक,
स्पष्ट रूप से पिछली बार, और उसके बाद आप लोग इसे प्रयोग कर रहे हैं
के लिए अनजाने getstring के लिए कई सप्ताह, malloc स्मृति के सभी
तथाकथित ढेर से आता है.
और यह, उदाहरण के लिए, क्यों getstring है गतिशील स्मृति आवंटित कर सकते हैं
आप क्या कर रहे हैं जानने के बिना अग्रिम में टाइप करने के लिए जा रहा है,
उस स्मृति को वापस एक सूचक आप हाथ, और कहा कि स्मृति रखने के लिए तुम्हारा अब भी है,
यहां तक ​​कि रिटर्न getstring के बाद.
क्योंकि याद सब के बाद कि ढेर लगातार ऊपर और नीचे जा रहा है
ऊपर और नीचे.
और जैसे ही यह हो जाता है नीचे, कि किसी भी स्मृति का मतलब
इस्तेमाल किया यह कार्य करना चाहिए किसी और के द्वारा प्रयोग नहीं किया जा.
अब यह कचरा मूल्यों है.
>> लेकिन ढेर यहां तक ​​है.
और malloc है के बारे में अच्छा क्या है malloc यहां स्मृति का आवंटन करते हैं,
इसके लिए, प्रभावित नहीं कर रहा है ढेर से अधिकांश भाग,.
और इसलिए किसी भी समारोह का उपयोग कर सकते हैं malloc'd गया है कि स्मृति,
यहां तक ​​कि getstring तरह एक समारोह से, के बाद भी यह वापस आ रहा है.
>> अब, malloc की बातचीत के लिए स्वतंत्र है.
और वास्तव में, नियम है कि आप गोद लेने शुरू करने की जरूरत
किसी भी, किसी भी, आप malloc का उपयोग किसी भी समय है तुम अपने आप को, अंत में, नि: शुल्क का उपयोग करना चाहिए
कि एक ही सूचक पर.
हम लिख दिया गया है यह सब समय छोटी गाड़ी, कई कारणों के लिए छोटी गाड़ी कोड,.
लेकिन जो की गई है CS50 पुस्तकालय, का उपयोग कर जो
खुद को जानबूझ है छोटी गाड़ी है, यह स्मृति लीक.
आप getstring बुलाया है किसी भी समय पिछले कुछ सप्ताह से अधिक
हम ऑपरेटिंग पूछ रहे हैं प्रणाली, लिनक्स, स्मृति के लिए.
और अगर आप एक बार इसे वापस कभी नहीं दिया है.
और इस में, नहीं है एक अच्छी बात का अभ्यास करेंगे.
>> और वेलग्रिंड, में से एक Pset 4 में पेश उपकरण,
आप मदद करने के बारे में सब है अब कि जैसे कीड़े हैं.
लेकिन शुक्र Pset 4 के लिए आप की जरूरत नहीं CS50 पुस्तकालय या getstring उपयोग करने के लिए.
तो स्मृति से संबंधित किसी भी कीड़े हैं अंत में अपने स्वयं के होने जा रहा.
>> तो malloc बस की तुलना में अधिक है इस उद्देश्य के लिए सुविधाजनक है.
हम वास्तव में अब हल कर सकते हैं मौलिक रूप से अलग समस्याओं,
और मौलिक अधिक समस्याओं का समाधान प्रभावी रूप से सप्ताह शून्य का वादा के अनुसार.
इस प्रकार अब तक इस कामुक है डेटा संरचना हम लिया है.
और डेटा संरचना से मैं सिर्फ मतलब conceptualizing स्मृति का एक तरीका
सिर्फ इतना कह परे चला जाता है कि एक तरह से, यह इस एक चार है, एक पूर्णांक है.
हम एक साथ क्लस्टर बातें करने के लिए शुरू कर सकते हैं.
>> तो एक सरणी इस तरह से देखा.
और के बारे में महत्वपूर्ण क्या था सरणी यह ​​आपको देता है
वापस करने वाली पीठ का हिस्सा स्मृति, जिनमें से प्रत्येक की
एक ही प्रकार का होने जा रहा है, पूर्णांक, पूर्णांक, पूर्णांक, पूर्णांक, या चार, चार, चार,
चार.
लेकिन कुछ downsides है.
इस उदाहरण के लिए, है छह आकार की एक सरणी.
आप छह से इस सरणी भरने मान लीजिए संख्या और फिर, जो कुछ कारणों के लिए,
अपने उपयोगकर्ता देना चाहता है आप एक सातवें नंबर.
जहां आप इसे रखा है?
>> अगर आपके पास क्या समाधान है ढेर पर एक सरणी बनाया,
उदाहरण के लिए, बस सप्ताह के साथ हम शुरू की है कि दो अंकन,
अंदर एक नंबर के साथ वर्ग कोष्ठक की?
खैर, आप छह मिल गया है इन बक्सों में संख्या.
अपने सहज ज्ञान क्या होगा?
आप कहाँ रखा करने के लिए चाहता है?
>> दर्शक: [अश्राव्य]
>> डेविड जे Malan: क्षमा करें?
>> दर्शक: अंत पर रखो.
>> डेविड जे Malan: अंत पर रखो.
तो बस सही करने के लिए, इस बॉक्स के बाहर.
कौन सा अच्छा होगा, लेकिन यह होगा आप ऐसा नहीं कर सकते पता चला है.
आप से पूछा नहीं गया है क्योंकि अगर स्मृति के इस टुकड़ा के लिए,
यह यह है कि संयोग से हो सकता है कुछ अन्य चर द्वारा इस्तेमाल किया जा रहा है
कुल मिलाकर.
हम रखी तो जब एक सप्ताह वापस लगता है कि या Zamyla और Davin और Gabe के नाम बाहर
स्मृति में.
सचमुच में वे थे वापस वापस करने के लिए वापस करने के लिए.
तो हम जरूरी नहीं कर सकते कि जो कुछ भी ट्रस्ट
यहाँ पर मुझे का उपयोग करने के लिए उपलब्ध है.
>> तो आप और क्या कर सकता है?
खैर, एक बार आप साकार , आकार सात की एक सरणी की जरूरत
आप सिर्फ एक बना सकता है आकार सात की सरणी तो उपयोग
एक पाश या एक जबकि पाश के लिए, नई सरणी में इसे कॉपी,
और फिर किसी तरह बस से छुटकारा पाने के इस सरणी या बस इसे का उपयोग बंद.
लेकिन यह है कि विशेष रूप से कुशल नहीं है.
संक्षेप में, सरणियों न दें आप गतिशील आकार.
>> तो एक तरफ आप मिल जो आश्चर्यजनक है रैंडम एक्सेस,.
यह सुविधा देता है क्योंकि हम बातें करते हैं विभाजन और जीत की तरह,
हम सब जो की द्विआधारी खोज, यहाँ स्क्रीन पर के बारे में बात की थी.
लेकिन अगर आप एक कोने में खुद को रंग.
जैसे ही आप हिट अपने सरणी के अंत,
आप एक बहुत क्या करना है महंगा ऑपरेशन
या कोड की एक पूरी गुच्छा लिखने अब लगता है कि समस्या से निपटने के लिए.
>> तो बजाय अगर हम क्या था कुछ एक सूची कहा जाता है,
या एक विशेष सूची में जुड़े?
क्या होगा अगर बजाय वाले आयतों, वापस वापस करने के लिए वापस
हम एक छोटे से छोड़ कि आयतों है उन दोनों के बीच में wiggle कमरा के सा?
भले ही और मैं इस खींचा है चित्र या इस तस्वीर अनुकूलित
ग्रंथों में से एक से यहां वापस करने के लिए होने के लिए वापस वास्तविकता में, बहुत व्यवस्थित वापस करने के लिए,
उन आयतों में से एक यहाँ स्मृति में हो सकता है.
उनमें से एक यहां तक ​​हो सकता है.
उनमें से एक, यहाँ तक हो सकता है यहाँ, और आगे अधिक.
>> लेकिन हम आकर्षित क्या अगर इस मामले में, तीर
किसी भी तरह इन जुडे हुए एक साथ rectangles?
दरअसल, हम एक तकनीकी देखा है एक तीर से अवतार.
क्या हम हाल ही में इस्तेमाल किया है दिन है कि, हुड के नीचे,
एक तीर की प्रतिनिधि है?
एक सूचक, है ना?
>> तो क्या हुआ अगर, बजाय बस संख्या भंडारण,
जैसे 9, 17, 22, 26, 34, क्या हम नहीं संग्रहीत अगर
केवल एक संख्या है लेकिन एक सूचक ऐसे प्रत्येक संख्या के बगल में?
इसलिए कि ज्यादा आप एक धागा होता है जैसे कपड़े की एक पूरी गुच्छा के माध्यम से सुई,
किसी भी तरह बांधने बातें एक साथ, इसी तरह कर सकते हैं
संकेत के रूप में साथ हम यहां तीर से अवतीर्ण,
एक तरह से एक साथ बुनाई इन व्यक्तिगत आयतों
प्रभावी रूप से एक सूचक का उपयोग करके प्रत्येक संख्या के बगल में है कि
कि, कुछ अगले संख्या के लिए अंक बदले में, कुछ अगले संख्या को इंगित करता?
तो दूसरे शब्दों में, क्या हम वास्तव में चाहते थे
कुछ इस तरह लागू करने के लिए?
वैसे दुर्भाग्य से, इन आयतों, 9 के साथ कम से कम एक, 17, 22 में,
और बहुत आगे है, ये अब नहीं रहे एकल संख्या के साथ अच्छा वर्गों.
नीचे, आयत 9 नीचे, उदाहरण के लिए,
का प्रतिनिधित्व करता है क्या करना चाहिए एक सूचक, 32 बिट हो.
अब, मैं अभी तक किसी भी डेटा प्रकार के बारे में पता नहीं कर रहा हूँ सी में है कि आप न केवल एक पूर्णांक देता है
लेकिन एक सूचक कुल मिलाकर.
>> हम चाहते हैं, तो समाधान क्या है इस के लिए अपने स्वयं के जवाब आविष्कार करने के लिए?
हाँ?
>> दर्शक: [अश्राव्य]
>> डेविड जे Malan: वह क्या है?
>> दर्शक: नई संरचना.
>> डेविड जे Malan: हाँ, क्यों इतना हम एक नई संरचना का निर्माण नहीं किया है,
या सी, एक संरचना में?
हम अगर संक्षेप में, पहले structs देखा है हम एक छात्र संरचना के साथ पेश किया जहां
इस तरह, एक नाम और एक घर था जो.
Pset में 3 ब्रेकआउट आप एक पूरे इस्तेमाल किया structs-- GRect और GOvals का गुच्छा
स्टैनफोर्ड के लिए बनाए गए एक साथ क्लस्टर जानकारी.
तो क्या हम इस एक ही विचार ले कीवर्ड "typedef" और "संरचना"
और फिर कुछ छात्र विशेष सामान, और बाद में यह विकसित:
typedef संरचना node-- और नोड है सिर्फ एक बहुत ही सामान्य कंप्यूटर विज्ञान
एक आंकड़ा संरचना में कुछ के लिए अवधि, एक आंकड़ा संरचना में एक कंटेनर.
मैं दावा एक नोड किया जा रहा है पूरी तरह से सीधा एक पूर्णांक N,,
और तो और अधिक cryptically एक छोटी सी, इस दूसरी लाइन, संरचना नोड * अगले.
लेकिन कम तकनीकी शब्दों में, कि दूसरी पंक्ति क्या है
घुंघराले ब्रेसिज़ के अंदर कोड का?
हाँ?
>> दर्शक: [अश्राव्य]
डेविड जे Malan: एक दूसरे नोड के लिए संकेतक.
तो बेशक, एक छोटे से गुप्त सिंटेक्स.
लेकिन अगर आप सचमुच इसे पढ़ा, तो अगले एक चर का नाम है.
अपने डेटा प्रकार क्या है?
यह इस समय एक छोटी सी वाचाल है लेकिन यह * प्रकार संरचना नोड की है.
हम कुछ सितारा देखा है किसी भी समय है कि, यह उस डेटा प्रकार के लिए एक संकेत है इसका मतलब है.
तो अगली जाहिरा तौर पर एक है एक struct नोड के लिए संकेतक.
>> अब, एक struct नोड क्या है?
खैर, आप उन देखना नोटिस शीर्ष सही पर एक ही शब्द.
और वास्तव में, आप भी शब्द देख यहाँ नीचे बाईं तल पर "नोड".
और यह वास्तव में सिर्फ एक सुविधा है.
हमारे छात्र परिभाषा में सूचना है कि केवल एक बार शब्द "छात्र" है.
और कहा कि एक छात्र वजह है वस्तु आत्म referential नहीं था.
एक छात्र के अंदर कुछ भी नहीं है कि एक अन्य छात्र को इंगित करने की जरूरत है,
persay.
उस तरह का होगा वास्तविक दुनिया में अजीब.
>> लेकिन एक में एक नोड के साथ जुड़ा हुआ सूची, हम एक नोड चाहते हैं
एक समान उद्देश्य के लिए referential हो.
और तो यहाँ बदलाव नहीं है नोटिस बस क्या घुंघराले ब्रेसिज़ के अंदर है.
लेकिन हम "नोड" शब्द जोड़ शीर्ष पर और साथ ही
सबसे अंत में के एवज में "छात्र."
और यह केवल एक तकनीकी विस्तार है ताकि, फिर से, आपके डेटा संरचना
आत्म referential हो सकता है एक तो यह है कि नोड एक और ऐसी नोड के लिए बात कर सकते हैं.
>> तो यह अंततः क्या है हमारे लिए मतलब करने के लिए जा रहे हैं?
खैर, एक, इस सामान अंदर हमारे नोड की सामग्री है.
यहाँ यह बात, शीर्ष सही, बस इतना है
कि, फिर से, हम अपने आप उल्लेख कर सकते हैं.
और फिर सबसे बाहरी सामान, नोड एक नया शब्द है, भले ही
शायद, यह अभी भी है छात्र और क्या रूप में एक ही
एसपीएल में हुड के नीचे था.
>> इसलिए हम अब शुरू करना चाहता था इस लिंक की गई सूची को लागू करने,
हम कैसे अनुवाद हो सकता है कुछ इस तरह कोड के लिए?
खैर, चलो बस एक देखते हैं एक कार्यक्रम के उदाहरण है कि
वास्तव में एक लिंक सूची का उपयोग करता है.
आज के वितरण कोड के बीच सूची शून्य नामक एक कार्यक्रम है.
मैं इस दौड़ और अगर मैं एक सुपर बनाया सरल जीयूआई, ग्राफिकल यूजर इंटरफेस,
लेकिन यह सच में सिर्फ printf है.
और अब मैं अपने आप को कुछ मेनू दिया है options-- हटाएँ, सम्मिलित करें, खोज,
और Traverse.
और छोड़ दिया.
ये एक पर सिर्फ आम संचालन कर रहे हैं एक लिंक सूची के रूप में जाना जाता है डेटा संरचना.
>> अब, जा रहा है हटाएं सूची में से एक नंबर हटा दें.
सम्मिलित जोड़ने के लिए जा रहा है सूची में एक संख्या.
खोज लग रहा है सूची में संख्या के लिए.
और पार सिर्फ एक अच्छा तरीका है कहने का, सूची के माध्यम से चलना,
इसे बाहर प्रिंट, लेकिन यह बात है.
किसी भी तरह से इसे बदल नहीं है.
>> तो चलो इस कोशिश करते हैं.
आगे जाने के लिए और 2 प्रकार करते हैं.
और फिर मैं जा रहा हूँ नंबर डालें, 9 कहना.
लिखें.
और अब मेरे कार्यक्रम बस है कहने के लिए प्रोग्राम किया, सूची अब 9.
अब, मुझे आगे जाना है और अगर फिर डालने हो, चलो
मुझे आगे जाना है और बाहर ज़ूम और 17 में लिखें.
अब मेरी सूची में तो, 17 9.
मैं फिर से डालने हो तो, चलो एक को छोड़ दें.
इसके बजाय 22 के, चित्र के अनुसार हम है यहां पर लग गया, मुझे आगे कूद जाने
और अगले 26 डालें.
तो मैं 26 टाइप करने के लिए जा रहा हूँ.
मैं उम्मीद के रूप में सूची है.
लेकिन अब, बस इस कोड को देखने के लिए अगर लचीला होने जा रहा है, अब मुझे जाने
प्रकार 22, जो कम से कम धारणा, हम कर रहे हैं
यह वास्तव में है, जो क्रमबद्ध रखने सही अब एक और गोल होने जा रहा,
17 और 26 के बीच में जाना चाहिए.
इसलिए मैं हिट दर्ज करें.
दरअसल, वह काम करता है.
और इसलिए अब मुझे सम्मिलित करते हैं पिछले, तस्वीर, 34 प्रति.
>> ठीक है.
तो अब के लिए मुझे लगता है कि निर्धारित करते हैं हटाएँ और जिओ और खोज करते हैं,
वास्तव में, काम करते हैं.
मैं खोज चला है वास्तव में, अगर, चलो लिखें, संख्या 22 के लिए खोज.
यह 22 पाया.
तो यह है कि क्या यह है कार्यक्रम सूची शून्य करता है.
>> लेकिन वास्तव में क्या हो रहा है पर कि इस लागू?
खैर, सबसे पहले मेरे पास है, और वास्तव में हो सकता है मैं एक फ़ाइल list0.h कहा जाता है, क्या करना है.
और यह वहाँ कहीं में रेखा, typedef, संरचना नोड,
फिर मैं अपने घुंघराले ब्रेसिज़ n है int, और तो परिभाषा क्या था struct--?
Struct नोड अगले.
तो हम स्टार की जरूरत है.
अब तकनीकी रूप से हम में मिलता है यहाँ यह ड्राइंग की आदत.
आप पाठ्यपुस्तकों देख सकते हैं और ऑनलाइन संदर्भ इसे करते हैं.
यह कार्यात्मक रूप समकक्ष है.
वास्तव में, यह एक छोटे से अधिक विशिष्ट है.
लेकिन मैं क्या साथ संगत हो जाएगा हम पिछली बार किया था और यह करते हैं.
और फिर अंत में, मैं यह करने के लिए जा रहा हूँ.
>> एक हेडर फाइल में तो कहीं न कहीं, list0.h में
आज इस संरचना परिभाषा है, और शायद कुछ अन्य सामान.
इस बीच list0c में वहाँ कुछ चीजें होने जा रहा.
लेकिन हम करने जा रहे हैं बस शुरू करने और इसे खत्म नहीं.
List0.h मैं चाहता हूँ कि एक फ़ाइल है मेरी सी फाइल में शामिल करने के लिए.
और फिर कुछ बिंदु पर मैं हूँ , मुख्य, पूर्णांक है शून्य करने के लिए जा रहा है.
और फिर मैं जा रहा हूँ करने के लिए करते कुछ यहाँ है है.
मैं भी एक के लिए जा रहा हूँ प्रोटोटाइप, शून्य, खोज, पूर्णांक जैसे,
एन, जीवन में जिसका उद्देश्य है एक तत्व के लिए खोज करने के लिए.
और फिर यहाँ नीचे मैं में दावा आज के कोड, शून्य, खोज, पूर्णांक, एन,
कोई अर्धविराम लेकिन खुले घुंघराले ब्रेसिज़.
और अब मैं किसी भी तरह खोज करना चाहते हैं इस सूची में एक तत्व के लिए.
लेकिन हम पर्याप्त नहीं है अभी तक स्क्रीन पर जानकारी.
मैं वास्तव में नहीं है सूची ही प्रतिनिधित्व किया.
तो एक तरह से हम लागू कर सकता है एक कार्यक्रम में एक लिंक सूची
मैं एक तरह से कुछ करना चाहते है जैसे यहाँ सूची जोड़ा घोषणा.
सादगी के लिए, मैं करने जा रहा हूँ यह भी सामान्य हम में हालांकि, वैश्विक
यह बहुत ज्यादा नहीं करना चाहिए.
लेकिन यह इस उदाहरण सरल होगा.
इसलिए मैं घोषणा करना चाहते हैं यहाँ एक लिंक सूची अप.
अब, मैं ऐसा कैसे कर सकता है?
>> यहाँ एक लिंक की गई सूची की तस्वीर है.
और मैं वास्तव में नहीं है कैसे पल में पता
मैं प्रतिनिधित्व करने के बारे में जाने के लिए जा रहा हूँ सिर्फ एक साथ इतनी सारी चीज़ें
स्मृति में चर.
लेकिन वापस एक पल लगता है.
हम लिया है यह सब समय तार, फिर जो हम
सरणियों होने का पता चला वर्ण, तो जो हम
सिर्फ एक सूचक होने का पता चला पहले प्रकार
वर्णों की एक सरणी में कि अशक्त समाप्त है.
उस तर्क से, और इस के साथ तो अपने विचारों को बोने की तस्वीर तरह,
हम वास्तव में क्या में लिखने की जरूरत है हमारे कोड एक लिंक सूची का प्रतिनिधित्व करने के लिए?
कितना इस जानकारी की जरूरत है कि हम करते हैं सी कोड में कब्जा करने के लिए, आप कहेंगे?
हाँ?
>> दर्शक: हम एक नोड के लिए एक संकेत की जरूरत है.
डेविड जे Malan: एक नोड के लिए एक सूचक.
विशेष रूप से, जो नोड अपनी होगा सहज ज्ञान के लिए एक सूचक रखने के लिए हो सकता है?
>> दर्शक: पहला नोड.
>> डेविड जे Malan: हाँ, शायद ही पहले.
और, पहले नोटिस नोड एक अलग आकार है.
यह संरचना के केवल आधे आकार है, क्योंकि यह वास्तव में केवल एक सूचक है.
तो आप वास्तव में क्या कर सकते हैं की घोषणा है एक लिंक सूची * प्रकार नोड का हो.
और चलो बस पहले यह कहते हैं और अशक्त करने के लिए यह इनिशियलाइज़.
तो अशक्त, फिर आ रहा है, यहां तस्वीर में.
इतना ही नहीं अशक्त एक विशेष तरह के रूप में प्रयोग किया जाता है getstring जैसी चीजों के लिए मान
और malloc, शून्य भी शून्य है सूचक, एक सूचक की कमी,
अगर तुम जाएगा.
यह बस कुछ भी नहीं यहाँ अभी तक है इसका मतलब है.
अब सबसे पहले, मैं कर सकता यह कुछ भी कहा जाता है.
मैं "सूची" यह कहा जाता हो सकता था या अन्य चीजों के किसी भी संख्या.
लेकिन मैं इतना है कि "पहला" यह बुला रहा हूँ इस तस्वीर के साथ यह लाइनें.
तो सिर्फ एक स्ट्रिंग की तरह दर्शाया जा सकता है अपनी पहली बाइट के पते के साथ,
इसलिए एक लिंक सूचीबद्ध कर सकते हैं.
और हम अन्य डेटा देखेंगे संरचनाओं प्रतिनिधित्व किया
सिर्फ एक सूचक के साथ, एक 32 बिट तीर, ओर इशारा करते हुए
संरचना में बहुत पहले नोड पर.
>> लेकिन अब की एक समस्या की आशा करते हैं.
मैं केवल याद कर रहा हूँ तो मेरे कार्यक्रम पते में
पहला नोड की, पहले इस डेटा संरचना में आयत,
बेहतर था के बारे में भी मामला हो क्या मेरी सूची में से बाकी के कार्यान्वयन?
जा रहा है कि एक महत्वपूर्ण विस्तार क्या है यह वास्तव में काम करता है यह सुनिश्चित करने के लिए?
और मैं "वास्तव में काम करता है" ज्यादा एक स्ट्रिंग की तरह, मतलब,
हमें पहले चरित्र से जाने की सुविधा देता है दूसरे को Davin के नाम पर,
तीसरे करने के लिए, करने के लिए चौथा, बहुत अंत करने के लिए,
हम अंत में कर रहे हैं जब हम जानते हैं कि कैसे इस तरह दिखता है कि एक लिंक की गई सूची की?
जब यह शून्य है.
और मैं के रूप में इस तरह की प्रतिनिधित्व किया है एक बिजली इंजीनियर सकता है,
थोड़ा ग्राउंडिंग के साथ प्रतीक, एक तरह की.
लेकिन यह सिर्फ इस मामले में शून्य का मतलब है.
आप इसे किसी भी संख्या को आकर्षित कर सकते हैं तरीके की है, लेकिन इस लेखक
यहाँ इस प्रतीक का उपयोग करने के लिए हुआ.
>> हम stringing रहे हैं के रूप में इतने लंबे समय एक साथ इन नोड्स के सभी,
केवल जहां को याद पहले एक, इतने लंबे समय है
हम पर एक विशेष प्रतीक के रूप सूची में बहुत पिछले नोड,
क्योंकि है कि और हम अशक्त उपयोग करेंगे हमारे पास उपलब्ध क्या हम हैं,
इस सूची में पूरा हो गया है.
और यहां तक ​​कि मैं केवल यदि आप के लिए एक संकेत दे पहला तत्व है, तुम, प्रोग्रामर,
निश्चित रूप से इसे आराम का उपयोग कर सकते हैं.
लेकिन हम अपने मन चलो एक छोटा सा घूमना,
वे पहले से ही नहीं कर रहे हैं काफी क्या wandered--
चलाने के समय होने जा रहा इस सूची में कुछ भी खोजने?
अरे नहीं, यह n के बिग हे, जो निष्पक्षता में, बुरा नहीं है.
लेकिन यह रेखीय है.
हम क्या सुविधा दे दिया है अधिक ले जाकर सरणियों की
गतिशील की इस तस्वीर की ओर एक साथ बुना या नोड्स जुड़े?
हम रैंडम एक्सेस छोड़ दिया है.
एक सरणी क्योंकि अच्छा है गणितीय सब कुछ
वापस करने के लिए वापस करने के लिए वापस करने के लिए वापस आ गया है.
यहां तक ​​कि इस तस्वीर हालांकि सुंदर लग रहा है, और यहां तक ​​कि
यह इन नोड्स की तरह दिखता है, हालांकि अच्छी तरह से वास्तविकता में, अलग स्थान दिया गया है
वे कहीं भी हो सकता है.
OX1, Ox50, Ox123, Ox99, इन नोड्स कहीं भी हो सकता है.
Malloc स्मृति आवंटित करता है क्योंकि ढेर से, लेकिन कहीं भी ढेर में.
तुम जरूरी यह है कि पता नहीं है वापस होने जा रहा वापस करने के लिए वापस करने के लिए.
और वास्तविकता में तो यह तस्वीर काफी इस सुंदर नहीं होने जा रहा.
>> इसलिए इसके बारे में एक बिट ले जा रहा है इस समारोह को लागू करने के लिए काम करते हैं.
तो चलो अब खोज को लागू करते हैं.
और हम एक की तरह देखेंगे इस कर के चालाक रास्ता.
मैं एक खोज समारोह हूँ तो अगर और मैं एक चर, पूर्णांक n दिया हूँ
के लिए देखने के लिए, मैं पता करने की जरूरत अंदर तलाश के लिए नए वाक्यविन्यास
है कि एक संरचना की , एन लगता है की ओर इशारा किया.
तो चलो यह करते हैं.
>> तो सबसे पहले मैं जा रहा हूँ आगे और * एक नोड की घोषणा.
और मैं यह कॉल करने के लिए जा रहा हूँ बस कन्वेंशन द्वारा सूचक,.
और मैं पहली बार के लिए यह को प्रारंभ करने जा रहा हूँ.
और अब मैं ऐसा कर सकते हैं तरीकों की एक संख्या में.
लेकिन मैं एक आम दृष्टिकोण लेने के लिए जा रहा हूँ.
सूचक के बराबर नहीं है अशक्त, और कि वैध वाक्यविन्यास है.
और यह सिर्फ इतना, निम्न कार्य का मतलब लंबे समय से आप कुछ भी नहीं है पर इंगित नहीं कर रहे हैं.
मुझे क्या करना चाहते हैं?
>> सूचक डॉट n, तो मुझे वापस आने दो उस के लिए, equals-- क्या बराबर होती है?
क्या मूल्य के लिए मैं देख रहा हूँ?
में पारित किया गया था कि वास्तविक एन.
तो यहाँ एक और विशेषता है सी और कई भाषाओं की.
यहां तक ​​कि संरचना बुलाया नोड हालांकि एक मूल्य के एन, पूरी तरह से वैध है
यह भी एक स्थानीय तर्क है की या चर n बुलाया.
यहां तक ​​कि हम साथ क्योंकि मानव आंख, भेद कर सकते हैं
इस n संभवतः है कि इस n से अलग.
वाक्यविन्यास अलग है.
आप एक डॉट और एक सूचक मिल गया है, यह एक जबकि ऐसी कोई बात नहीं है.
तो यह ठीक है.
वही बातें कि उन्हें फोन करने के लिए ठीक है.
>> मैं आपको यह पता है, तो मैं कर रहा हूँ कुछ करना चाहते हो जा
जैसे हम n पाया कि घोषणा.
और हम एक के रूप में छोड़ दूँगा टिप्पणी या pseudocode कोड.
वरना, और यहाँ है दिलचस्प बात यह है, क्या
मैं वर्तमान नोड अगर ऐसा करना चाहते हैं मैं के बारे में परवाह है कि एन युक्त नहीं है?
कैसे मैं निम्नलिखित हासिल करते हैं?
यदि मेरी उंगली पल पीटीआर है, और यह बात है
जो भी तरफ इशारा करते हुए पहला, पर इशारा कर रहा है
मैं अपनी उंगली आगे? कैसे कोड में अगले नोड के लिए?
ठीक है, हम कर रहे हैं ब्रेडक्रम्ब क्या है इस मामले में पालन करने के लिए जा रहे हैं?
दर्शक: [अश्राव्य].
डेविड जे Malan: हाँ, तो अगले.
मैं करने के लिए वापस जाना है तो मेरा यहाँ कोड है, वास्तव में, मैं हूँ
, सूचक आगे जाना है और कहा जा रहा है, जो यह सिर्फ एक अस्थायी variable-- है
एक अजीब नाम, पीटीआर, लेकिन यह सिर्फ temp-- की तरह है
मैं सूचक सेट करने के लिए जा रहा हूँ जो भी सूचक is-- के बराबर
और फिर, यह एक होने जा रहा है अगले एक moment-- डॉट के लिए छोटी छोटी गाड़ी.
दूसरे शब्दों में, मैं ले जा रहा हूँ मेरे इस नोड पर इशारा कर रहा है कि उंगली
यहाँ और मैं तुम्हें पता है, कहने के लिए जा रहा हूँ क्या, अगले क्षेत्र पर एक नज़र रखना
और अपनी उंगली को स्थानांतरित जो भी इसे ओर इशारा करते है.
और इस के लिए जा रहा है , दोहराने, दोहराने दोहराने.
लेकिन जब मेरी उंगली करता है सभी में कुछ भी करने से रोक?
जैसे ही क्या कोड kicks की लाइन में हैं?
दर्शक: [अश्राव्य]
डेविड जे Malan: यदि बिंदु जबकि सूचक रिक्त करने के बराबर नहीं है.
कुछ बिंदु मेरी उंगली है पर शून्य पर इंगित किया जा रहा
और मैं महसूस करने के लिए जा रहा हूँ कि इस सूची के अंत में है.
अब, यह एक छोटी सी है सादगी के लिए सफेद झूठ.
यह पता चला है कि भले ही हम बस इस डॉट संकेतन सीखा
संरचनाओं के लिए, सूचक एक संरचना नहीं है.
पीटीआर क्या है?
बस अधिक nitpicky हो.
यह एक नोड के लिए एक संकेत है.
यह एक नोड ही नहीं है.
मैं यहाँ कोई सितारा था, सूचक absolutely-- यह एक नोड है.
इस सप्ताह एक की तरह है एक चर की घोषणा,
यहां तक ​​कि शब्द "नोड" नया है, हालांकि.
>> लेकिन हम एक परिचय के रूप में जल्द ही के रूप में सितारा, यह अब एक नोड के लिए एक संकेत है.
और दुर्भाग्य से आप उपयोग नहीं कर सकते एक संकेतक के लिए डॉट संकेतन.
आप तीर का उपयोग करने के लिए है अंकन, जो, ऊँची,
पहली बार किसी भी टुकड़ा है वाक्यविन्यास का सहज लग रहा है.
यह सचमुच एक तीर की तरह लग रहा है.
और इसलिए है कि एक अच्छी बात है.
और यहाँ नीचे सचमुच एक तीर की तरह लग रहा है.
इसलिए मुझे लगता है कि मैं नहीं कर la-- लगता है मैं here-- अधिक-प्रतिबद्ध हूँ मैं
कि पिछले नया टुकड़ा लगता है वाक्य रचना की हम देखने जा रहे हैं.
और शुक्र है, यह वास्तव में है एक छोटे से अधिक सहज ज्ञान युक्त.
>> अब, आप में से जो लोग पुराना तरीका पसंद हो सकता है,
आप अभी भी डॉट संकेतन का उपयोग कर सकते हैं.
लेकिन सोमवार की प्रति के रूप में बातचीत, हम पहली बार
उस के लिए जाना है, वहाँ जाने की जरूरत पता है, और फिर क्षेत्र का उपयोग.
तो यह भी सही है.
और सच कहूँ तो, यह है एक अधिक पंडिताऊ थोड़ा.
तुम सचमुच कह रहे हैं, भिन्नता सूचक और वहाँ जाओ.
फिर एन हड़पने, क्षेत्र n बुलाया.
लेकिन सच कहूँ तो, कोई नहीं चाहता टाइप करें, या इस पढ़ने के लिए.
और इसलिए दुनिया का आविष्कार तीर अंकन, जो
, समान, बराबर है यह सिर्फ वाक्यात्मक चीनी है.
यह कह के तो एक अच्छा तरीका बेहतर लग रहा है, या सरल लग रहा है.
>> तो अब मैं एक और बात करने के लिए जा रहा हूँ.
मैं मैं एक बार "तोड़" कहने जा रहा हूँ यह तो मैं यह देखने के लिए नहीं रख पाया.
लेकिन इस सार है एक खोज समारोह का.
लेकिन उस में, एक बहुत आसान है अंत, कोड के माध्यम से चलने के लिए नहीं.
यह वास्तव में औपचारिक कार्यान्वयन है आज के वितरण कोड में खोज की.
मुझे लगता है कि सम्मिलित नहीं है कहने की हिम्मत के माध्यम से चलने के लिए विशेष रूप से मज़ा
नेत्रहीन, और न ही है भी, हटाना दिन के अंत में, हालांकि
वे काफी नीचे फोड़ा सरल heuristics.
>> तो चलो यह करते हैं.
आप यहाँ मुझे हास्य हूँ, मैंने किया तनाव गेंदों का एक गुच्छा ले आओ.
मैं संख्या का एक गुच्छा लाया.
और हम बस कुछ स्वयंसेवकों मिल सकता है 9, 17, 20, 22, 29, और 34 का प्रतिनिधित्व करने के लिए?
तो अनिवार्य रूप से हर कोई यहाँ जो आज है.
यही है, एक, दो, तीन साल का था चार, पांच, छह लोग.
और मैं नहीं, देखना go-- लिए कहा गया है पीठ में एक उनके हाथ उठाती है.
ठीक है, एक, दो, तीन, चार, five-- मुझे छह balance-- लोड करते हैं.
ठीक है, आप छह ऊपर की ओर आते हैं.
हम अन्य लोगों की आवश्यकता होगी.
हम अतिरिक्त तनाव गेंदों लाया.
और अगर तुम सकता है, के लिए बस एक पल, लाइन
अपने आप को सिर्फ यहाँ इस तस्वीर की तरह.
>> ठीक है.
आपका नाम क्या है, चलो देखते हैं?
>> दर्शक: एंड्रयू.
>> डेविड जे Malan: एंड्रयू, आप संख्या 9 कर रहे हैं.
आपसे मिलकर अच्छा लगा.
हेयर यू गो.
दर्शक: जेन.
डेविड जे Malan: जेन.
डेविड.
संख्या 17.
हाँ?
>> दर्शक: मैं जूलिया हूँ.
>> डेविड जे Malan: जूलिया, डेविड.
संख्या 20.
दर्शक: ईसाई.
डेविड जे Malan: ईसाई, डेविड.
संख्या 22.
और?
>> दर्शक: जेपी.
डेविड जे Malan: जेपी.
संख्या 29.
तो उह ओह आगे जाना है और in-- मिलता है.
उह ओह.
स्टैंडबाय.
20.
किसी को भी एक मार्कर है?
दर्शक: मैं एक Sharpie मिल गया है.
डेविड जे Malan: आप एक Sharpie मिला?
ठीक.
और किसी को भी एक कागज का टुकड़ा है?
व्याख्यान बचाओ.
चलो.
दर्शक: हम यह मिल गया है.
डेविड जे Malan: हम यह मिल गया?
सब ठीक है, धन्यवाद.
ये रहा.
इस लिए आप से था?
तुम सिर्फ दिन बचा लिया.
तो 29.
ठीक है.
मैं 29 गलत वर्तनी, लेकिन ठीक है.
आगे बढ़ें.
सब ठीक है, मैं तुम्हें दे दूँगा अपनी कलम वापस क्षण भर के.
इसलिए हम यहां इन लोगों की है.
दूसरे एक करते हैं.
Gabe, आप खेलना चाहते हैं यहां पहला तत्व?
हम बात करने के लिए आप की आवश्यकता होगी इन ठीक लोगों पर.
तो 9, 17, 20, 22, की तरह 29, और फिर 34 का.
हम किसी को खो दिया?
मैं एक 34 है.
कहां चाहता है, जो did-- ठीक है, 34 हो सकता है?
ठीक है, 34, ऊपर की ओर आते हैं.
ठीक है, यह हो जाएगा चरमोत्कर्ष के लायक भी.
आपका नाम क्या है?
>> दर्शक: पीटर.
>> डेविड जे Malan: पीटर, ऊपर पर आ गए.
ठीक है, तो यहाँ है एक नोड्स की पूरी गुच्छा.
तुम लोगों में से प्रत्येक का प्रतिनिधित्व करता है इन आयतों में से एक.
और Gabe, थोड़ा अजीब बाहर यार, पहले का प्रतिनिधित्व करता है.
तो उसका सूचक एक छोटे से छोटा होता है हर किसी से स्क्रीन पर.
और इस मामले में, अपने में से प्रत्येक के लिए छोड़ दिया हाथ, नीचे बात करने के लिए या तो जा रहा है
जिससे इसलिए, शून्य का प्रतिनिधित्व सिर्फ एक सूचक के अभाव,
या यह इशारा किया जा रहा है आप के बगल में एक नोड पर.
>> इसलिए अभी आप सजाना अगर तस्वीर की तरह अपने आप को
यहाँ, आगे बढ़ो और बिंदु Gabe साथ, एक दूसरे पर
पर विशेष इशारा में संख्या 9 सूची प्रतिनिधित्व करने के लिए.
ठीक है, और संख्या 34, अपने बाएँ हाथ सिर्फ मंजिल पर इंगित किया जाना चाहिए.
>> ठीक है, तो इस लिंक सूची है.
तो इस सवाल में मामला नहीं है.
और वास्तव में, इस प्रतिनिधि है समस्याओं का एक वर्ग की
आप कोड के साथ हल करने की कोशिश हो सकती है.
आप अंततः सम्मिलित करना चाहते हैं सूची में एक नया तत्व.
इस मामले में, हम करने जा रहे हैं संख्या 55 डालने की कोशिश.
लेकिन वहाँ जा रहा है विभिन्न मामलों पर विचार करने के लिए.
और वास्तव में, यह एक होने जा रहा है बड़ी तस्वीर यहाँ takeaways की है,
विभिन्न मामलों में क्या कर रहे हैं.
स्थितियां अगर या अलग क्या हैं अपने कार्यक्रम के लिए हो सकता है कि शाखाओं?
>> खैर, नंबर करने की कोशिश कर रहे हैं हम 55 होने के लिए अब जो पता डालें,,
लेकिन आपको पता नहीं था अगर अग्रिम में, मैं हिम्मत करना
कम से कम तीन में गिर जाता है संभव स्थितियों.
जहां एक नया तत्व हो सकता है?
दर्शक: और अंत या मध्य.
डेविड जे Malan: अंत में, में मध्यम, या शुरुआत में.
तो मैं कम से कम वहाँ का दावा तीन समस्याओं हम हल करने की जरूरत है.
की शायद क्या चुनने दें यकीनन सरलतम
एक, जहां नए तत्व शुरुआत में अंतर्गत आता है.
तो मैं काफी कोड के लिए जा रहा हूँ जैसे मैं सिर्फ लिखा था, जो खोज.
और मैं, पीटीआर किया जा रहा हूँ जो मैं, मेरी उंगली के साथ यहां का प्रतिनिधित्व करेंगे
हमेशा की तरह.
>> और, क्या मूल्य याद हम करने के लिए पीटीआर को प्रारंभ किया था?
इसलिए हम शुरू में रिक्त करने के लिए यह initialized.
लेकिन तब हम एक बार में क्या किया हमारी खोज समारोह के अंदर थे?
हम पहले तक यह बराबर सेट इस काम को करने का मतलब यह नहीं है.
मैं पहले के बराबर पीटीआर में तय किया है, क्या मेरे हाथ वास्तव में इशारा करते हुए होना चाहिए?
ठीक है.
Gabe और मैं जा रहे हैं यहाँ बराबर मूल्यों होने के लिए,
हम संख्या 9 पर दोनों बात करने के लिए जरूरत है.
>> तो यह हमारी कहानी की शुरुआत थी.
और अब यह सिर्फ सीधा है भले ही वाक्यविन्यास नया है.
धारणा यह सिर्फ रैखिक खोज है.
9 के बराबर 55 है?
या यों कहें, 9 से कम हम कहते हैं.
मैं कोशिश कर रहा हूँ क्योंकि 55 डाल करने के लिए जहां यह पता लगाने.
9 से कम से कम 17, कम 20 से कम से कम 22 से कम 29,
कम से कम 34, नहीं.
तो अब हम इस मामले में कर रहे हैं कम से कम तीन में से एक.
>> मैं यहाँ पर 55 सम्मिलित करना चाहते हैं, क्या कोड की जरूरत की तर्ज निष्पादित करने के लिए?
कैसे की इस तस्वीर से करता है मनुष्य को बदलने की जरूरत है?
मैं अपने बाएँ हाथ के साथ क्या करते हैं?
यह शुरू में शून्य होना चाहिए मैं इस सूची के अंत में कर रहा हूँ क्योंकि.
और क्या होना चाहिए यहाँ पीटर के साथ, यह था?
वह स्पष्ट रूप से मेरे लिए बात करने के लिए जा रहा है.
तो मैं कम से कम दो लाइनों का दावा आज से नमूना कोड में कोड की
कि इस लागू करने के लिए जा रहा है पूंछ में 55 जोड़ने का परिदृश्य.
और मैं किसी हॉप हो सकता था अप और सिर्फ 55 का प्रतिनिधित्व करते हैं?
सब ठीक है, आप नए 55 हैं.
>> तो अब आगे क्या अगर परिदृश्य, के साथ आता है
और हम में सम्मिलित करना चाहते हैं शुरुआत या इस सूची के सिर?
और अपना नाम, संख्या 55 है?
>> दर्शक: जैक.
>> डेविड जे Malan: जैक?
ठीक है, आपसे मिलकर अच्छा लगा.
नाव पर स्वागत.
तो अब हम जा रहे हैं कहते हैं, संख्या 5 डालें.
यहाँ का दूसरा मामला है तीन हम पहले साथ आया था.
तो 5 शुरुआत में ही होते है, हम पता लगाना है कि कैसे देखते हैं.
मैं अपने पीटीआर को प्रारंभ फिर नंबर 9 के लिए संकेतक.
और मैं 5 से कम 9, ओह, मुझे एहसास हुआ.
इसलिए हमारे लिए इस तस्वीर को ठीक.
जिनके हाथ, Gabe है या दाऊद के or-- संख्या 9 का नाम क्या है?
>> दर्शक: जेन.
>> डेविड जे Malan: जेन hands-- हमारे हाथ की जो बदलने की जरूरत है?
ठीक है, तो Gabe अब क्या पर अंक?
मुझ पर.
मैं नए नोड हूँ.
इसलिए मैं इस कदम की तरह ही होगा यहाँ नेत्रहीन यह देखने के लिए.
और इस बीच क्या मैं उस बिंदु है?
फिर भी, जहां मैं इशारा कर रहा हूँ.
तो यह बात है.
कोड सुधारों की तो सिर्फ सच में एक पंक्ति इस विशेष मुद्दे, यह प्रतीत होता है.
ठीक है, तो यह अच्छी बात है.
और अगर कोई 5 के लिए एक प्लेसहोल्डर हो सकता है?
ऊपर आओ.
हम आपको अगली बार मिल जाएगा.
>> ठीक है, तो now-- और एक तरफ, नाम के रूप में
मैं सही का स्पष्ट उल्लेख नहीं कर रहा हूँ अब, pred सूचक, पूर्ववर्ती सूचक
और नए सूचक है, कि सिर्फ नाम दिया
संकेत के लिए नमूना कोड में या एक तरह से चारों ओर इशारा कर रहा है कि मेरे हाथ.
आपका नाम क्या है?
>> दर्शक: क्रिस्टीन.
>> डेविड जे Malan: क्रिस्टीन.
नाव पर स्वागत.
सब ठीक है, तो चलो अब विचार करें एक से थोड़ा अधिक कष्टप्रद परिदृश्य,
मैं सम्मिलित करना चाहते हैं जिससे इस मामले में 26 तरह कुछ.
20?
क्या?
ये हम इस कलम है अच्छी बात are--.
सब ठीक है, 20.
किसी का एक और टुकड़ा मिल सकता है पेपर अभी सब ठीक case-- में, तैयार है.
ओह, दिलचस्प.
वैसे यह एक उदाहरण है एक व्याख्यान बग की.
ठीक है तो अपना नाम फिर क्या है?
दर्शक: जूलिया.
डेविड जे Malan: जूलिया, आप पॉप कर सकते हैं बाहर और ढोंग आप कभी नहीं थे?
ठीक है, यह कभी नहीं हुआ.
धन्यवाद.
इसलिए हम सम्मिलित चाहते हैं इस लिंक की गई सूची में जूलिया.
वह संख्या 20 है.
और निश्चित रूप से वह है पर सदस्य बनने के लिए जा रहा
begin-- अभी तक कुछ भी बात नहीं है.
तो अपने हाथ तरह के हो सकते हैं नीचे अशक्त या कुछ कचरा मूल्य.
त्वरित कहानी बताओ.
मैं संख्या 5 इस समय इशारा कर रहा हूँ.
तब मैं 9 की जाँच करें.
तब मैं 17 की जाँच करें.
तब मैं 22 की जाँच करें.
और मैं, उह, जूलिया एहसास 22 से पहले जाने की जरूरत है.
तो क्या होने की जरूरत है?
जिनके हाथों में बदलने की जरूरत है?
जूलिया, मेरा, or-- अपना नाम फिर क्या है?
>> दर्शक: ईसाई.
>> डेविड जे Malan: ईसाई या?
>> दर्शक: एंडी.
>> डेविड जे Malan: एंडी.
ईसाई या एंडी?
एंडी पर बात करने की जरूरत है?
जूलिया.
ठीक है.
तो एंडी, आप जूलिया पर बात करना चाहते हैं?
लेकिन एक मिनट रुको.
इस प्रकार अब तक कहानी में, मैं एक की तरह कर रहा हूँ
भावना में आरोप में कि सूचक है कि बात है
सूची के माध्यम से घूम रहा है.
हम एंडी के लिए एक नाम है, लेकिन हो सकता है एंडी बुलाया कोई चर है.
हम केवल अन्य चर रहा है पहला, Gabe द्वारा प्रतिनिधित्व कौन.
>> तो यह क्यों इस तरह वास्तव में है अब तक हम यह आवश्यक नहीं है.
लेकिन अब स्क्रीन पर है pred सूचक की फिर से उल्लेख.
तो मुझे और अधिक स्पष्ट हो.
इस सूचक है, तो मैं बेहतर था एक छोटे से अधिक बुद्धिमान मिल
मेरी यात्रा के बारे में.
आप मेरे यहां से गुजर रही मन नहीं है फिर, यहाँ ओर इशारा करते हुए यहां इशारा करते हुए.
लेकिन मुझे एक pred सूचक करते हैं, पूर्ववर्ती सूचक है, कि
तरह की तरफ इशारा करते हुए तत्व मैं बस में था.
इसलिए मैं यहाँ जाना है, अब मेरे बाएँ हाथ अद्यतन.
मैं यहाँ अपने बाएँ हाथ के अपडेट जाओ.
और अब मैं के लिए एक संकेत नहीं ही है जूलिया के बाद चला जाता है कि तत्व,
मैं अभी भी एक संकेतक के लिए है एंडी, पहले तत्व.
तो तुम, अनिवार्य रूप से, उपयोग कर सकते है ब्रेडक्रंब, अगर तुम जाएगा,
अपेक्षित संकेत के सभी के लिए.
>> मैं कम से इशारा कर रहा हूँ तो अगर एंडी और मैं भी इशारा कर रहा हूँ
जिनके हाथों में ईसाई, पर अब कहीं और कहा जाना चाहिए?
एंडी तो अब जूलिया पर बात कर सकते हैं.
जूलिया अब ईसाई पर बात कर सकते हैं.
वह कॉपी कर सकते हैं क्योंकि मेरे दाहिने हाथ का सूचक.
और कहा कि प्रभावी ढंग डालता वापस यहाँ इस जगह में.
तो संक्षेप में, यहां तक ​​कि हालांकि इस हमेशा के लिए तरह हमें ले जा रहा है
वास्तव में अद्यतन करने के लिए एक सूची जुड़े एहसास
आपरेशन कि अपेक्षाकृत आसान है.
यह, दो, एक से तीन है अंत में कोड की लाइनों.
लेकिन उन के चारों ओर लिपटा शायद कोड की लाइनों
तर्क का एक सा है कि प्रभावी ढंग से है सवाल है, हम जहां हैं पूछता है?
हम शुरुआत में हैं, मध्य या अंत?
>> अब, निश्चित रूप से कुछ अन्य कर रहे हैं हम लागू हो सकता है आपरेशनों.
और यहाँ इन चित्रों को सिर्फ दर्शाती क्या हम सिर्फ इंसानों के साथ किया था.
क्या हटाने के बारे में?
मैं चाहते हैं, उदाहरण के लिए, नंबर हटाने के 34 या 55,
मैं, कोड की ही तरह हो सकता है लेकिन मैं एक या दो कदम की जरूरत के लिए जा रहा हूँ.
नया क्या है वजह?
मैं अंत में किसी को निकालते हैं, संख्या की तरह 55 और फिर 34,
क्या यह भी मुझे लगता है कि कर के रूप में बदल गया है?
मैं evict-- नहीं करने के लिए है अपना नाम फिर क्या है?
>> दर्शक: जैक.
>> डेविड जे Malan: जैक.
मैं, evict-- मुक्त जैक न केवल करने के लिए है तो सचमुच कम से कम मुक्त जैक कहते हैं, या
वहाँ सूचक भी है, लेकिन अब क्या पीटर के साथ बदलने की जरूरत है?
उसका हाथ बेहतर नीचे ओर इशारा करते हुए शुरू करते हैं.
जैसे ही मैं आज़ाद से भेंट के रूप में, क्योंकि जैक, पीटर अभी भी जैक तरफ इशारा करते हुए अगर
और मैं इसलिए गुजर रखना सूची और पहुँच इस सूचक,
कि जब हमारे पुराने दोस्त विभाजन है वास्तव में लात हो सकता है गलती.
हम दिया है क्योंकि जैक को स्मृति वापस.
>> तुम वहाँ रह सकते हैं awkwardly बस एक पल के लिए.
हम सिर्फ एक जोड़ी है क्योंकि अंतिम संचालन पर विचार करने के लिए.
सूची के सिर निकाल रहा है, beginning-- और यह एक या
एक छोटे से परेशान.
हम जानते हैं कि करने के लिए है क्योंकि Gabe तरह की विशेष इस कार्यक्रम में है.
क्योंकि वास्तव में, वह अपने ही सूचक है.
वह सिर्फ, पर बताया जा रहा है यहां लगभग हर किसी के रूप में है.
>> तो सूची का सिर है जब , जिनके हाथ अब बदलने की जरूरत है हटाया?
अपना नाम फिर क्या है?
>> दर्शक: क्रिस्टीन.
>> डेविड जे Malan: मैं भयानक रहा हूँ नामों पर, जाहिरा तौर पर.
तो क्रिस्टीन और Gabe, जिनके हाथों में बदलने की जरूरत है
हम क्रिस्टीन को दूर करने का प्रयास करते, तस्वीर से नंबर 5,?
ठीक है, तो चलो Gabe करते हैं.
Gabe बात करने के लिए जा रहा है, शायद, संख्या 9 पर.
लेकिन आगे क्या होना चाहिए?
दर्शक: क्रिस्टीन चाहिए [अश्राव्य] अशक्त हो.
डेविड जे Malan: ठीक है, हम शायद चाहिए make-- मैं कहीं "शून्य" सुना.
दर्शक: अशक्त और उसे मुक्त.
डेविड जे Malan: क्या अशक्त?
दर्शक: अशक्त और उसे मुक्त.
डेविड जे Malan: अशक्त और उसे मुक्त.
तो यह बहुत आसान है.
और यह आप अब तरह कर रहे हैं कि सही है के संबंधित, वहाँ नहीं खड़ी है.
आप से किया गया है क्योंकि सूची से decoupled.
आप को प्रभावी ढंग से किया गया है सूची से अनाथ.
और इसलिए हम बेहतर पर अब नि: शुल्क फोन किया था क्रिस्टीन कि स्मृति वापस देने के लिए.
अन्यथा हर बार हम सूची में से एक नोड हटाना
हम सूची बना रही हो सकता है छोटे, लेकिन वास्तव में कम नहीं
स्मृति में आकार.
और इसलिए हम जोड़कर रखना और अगर उनका कहना है, की सूची पर बातें जोड़ने,
मेरे कंप्यूटर धीमी हो सकती है और धीमी और धीमी,
मैं खत्म हो रहा है, क्योंकि स्मृति, मैं वास्तव में नहीं हूँ, भले ही
क्रिस्टीन बाइट्स का उपयोग स्मृति की अब और नहीं.
>> तो अंत में वहाँ अन्य रहे हैं course-- हटाने के परिदृश्यों,
मध्य, हटाने में अंत में, के रूप में हमने देखा.
लेकिन अधिक दिलचस्प अब चुनौती है
जा रहा वास्तव में विचार करने के लिए होने के लिए समय चल रहा है क्या.
इतना ही नहीं, आप रख सकते हैं अपने कागज के टुकड़े, Gabe, अगर,
आप दे मन नहीं होता हर कोई एक तनाव गेंद.
हमारे लिंक की गई सूची के लिए बहुत बहुत धन्यवाद यहां स्वयंसेवकों की, अगर तुम सकता है.
>> [वाहवाही]
>> डेविड जे Malan: सब ठीक है.
विश्लेषणात्मक की तो एक जोड़ी तो सवाल है, अगर मैं कर सकता.
हम पहले इस अंकन देखा है, बड़ी हे और ओमेगा, ऊपरी सीमा
और पर कम सीमा कुछ एल्गोरिथ्म का समय चल रहा है.
तो चलो बस पर विचार करें सवालों के एक जोड़े.
>> एक, और हम यह कहा इससे पहले, चल रहा है क्या हो रहा है
एक के लिए खोज का समय बड़ी हे के मामले में सूची?
क्या चल रहा है पर एक ऊपरी ही है एक लिंक सूची खोज का समय
यहाँ हमारे स्वयंसेवकों द्वारा कार्यान्वित के रूप में?
यह n की बड़ी हे, रैखिक है.
सबसे खराब स्थिति में है क्योंकि तत्व, 55 की तरह,
हम जहां के लिए हो सकता है लग रही हो सकता जैक, अंत में सभी तरह था.
और दुर्भाग्य से, एक सरणी के विपरीत हम इस समय कल्पना नहीं कर सकते.
हमारे मनुष्य के सभी थे हालांकि छोटे तत्वों, 5 से हल,
बड़ा तत्व अप करने के लिए सभी तरह से, 55, कि आम तौर पर एक अच्छी बात है.
लेकिन इस धारणा है कि क्या करता है अब हमारे पास करने के लिए अनुमति देते हैं?
दर्शक: [अश्राव्य]
डेविड जे Malan: फिर से कहो?
दर्शक: रैंडम एक्सेस.
डेविड जे Malan: रैंडम एक्सेस.
और बदले में कि कोई हम कर सकते हैं इसका मतलब अब, कमजोर शून्य, अंतर्ज्ञान का उपयोग
द्विआधारी का उपयोग कर के और प्रत्यक्षता खोज और विभाजन और जीत.
क्योंकि भले ही हम मनुष्य जाहिर कर सकता
एंडी या ईसाई थे कि देखना मोटे तौर पर इस सूची के मध्य में,
हम केवल एक के रूप में जानते हैं कि सूची उड़े द्वारा कंप्यूटर
शुरू से ही.
इसलिए हम चाहते हैं कि बिना सोचे समझे छोड़ दिया है.
>> N की तो बड़ी हे अब ऊपरी है हमारे खोज समय पर बाध्य.
क्या हमारे खोज की ओमेगा के बारे में?
कम बाध्य खोज पर क्या है इस सूची में कुछ संख्या के लिए?
दर्शक: [अश्राव्य]
डेविड जे Malan: फिर से कहो?
दर्शक: एक.
डेविड जे Malan: एक.
तो लगातार समय.
सबसे अच्छा मामले में, क्रिस्टीन है वास्तव में सूची की शुरुआत में.
और हम देख रहे हैं संख्या 5 है, तो हम उसे मिल गया.
तो कोई बड़ी बात नहीं.
लेकिन वह कम हो गया है इस मामले में सूची की शुरुआत.
की तरह कुछ के बारे में क्या हटाएं?
आप एक तत्व को नष्ट करने के लिए क्या चाहते हैं?
क्या ऊपरी बाध्य और कम ही है एक लिंक से कुछ को हटाने पर
सूची?
दर्शक: [अश्राव्य]
डेविड जे Malan: फिर से कहो?
दर्शक: एन.
डेविड जे Malan: n है बाध्य वास्तव में ऊपरी.
सबसे खराब स्थिति में हम कोशिश क्योंकि हम बस किया था, जैक नष्ट करने के लिए.
उन्होंने अंत में सभी तरह है.
हमेशा के लिए हमें ले जाता है, या n चरणों उसे खोजने के लिए.
इसलिए कि एक ऊपरी बाध्य है.
यह सुनिश्चित करें कि, रैखिक है.
और सबसे अच्छी मामले समय से चल रहा है, या सबसे अच्छा मामले में निचली सीमा
लगातार समय होगा.
शायद हम नष्ट करने की कोशिश की वजह क्रिस्टीन, और हम सिर्फ भाग्यशाली हो
वह शुरुआत में है.
अब एक मिनट रुको.
Gabe, शुरुआत में भी था और हम भी Gabe अद्यतन करने के लिए किया था.
इसलिए कि सिर्फ एक कदम नहीं था.
तो यह वास्तव में स्थिर है समय, सबसे अच्छा मामले में,
छोटी तत्व हटाने के लिए?
यह दो हो सकता है, भले ही यह है कोड के तीन, या यहां तक ​​कि 100 लाइनों,
यह की एक ही नंबर है अगर नहीं कुछ पाश में लाइनों,,
और आकार के स्वतंत्र सूची की, बिल्कुल.
तत्व को हटाया जा रहा है सूची की शुरुआत
हम साथ सौदा किया है, भले ही Gabe, अभी भी स्थिर समय है.
>> तो यह एक तरह लगता है पीछे की ओर से बड़े पैमाने पर कदम.
और समय की बर्बादी , अगर सप्ताह एक और सप्ताह में
शून्य हम न केवल था pseudocode कोड लेकिन वास्तविक कोड
लॉग है कि कुछ को लागू करने के लिए आधार एन, या लॉग इन, बल्कि, एन के, आधार 2,
अपने समय चल रहा है के संदर्भ में.
तो बिल्ली हम शुरू क्यों करना चाहते हैं एक लिंक की गई सूची की तरह कुछ का उपयोग कर?
हाँ.
>> दर्शक: तो आप जोड़ सकते हैं सरणी के तत्वों.
डेविड जे Malan: तो आप कर सकते हैं सरणी के तत्वों को जोड़ने.
और यह भी विषयगत है.
और हम देखना जारी रखेंगे यह इस व्यापार बंद, ज्यादा
जैसे हमने देखा है एक मर्ज प्रकार के साथ व्यापार बंद.
हम वास्तव में तेजी लाने सकता है बल्कि, खोज या छँटाई,
हम थोड़ा और अधिक अंतरिक्ष खर्च और एक स्मृति का एक और हिस्सा है
या मर्ज तरह के लिए एक सरणी.
लेकिन हम अधिक खर्च अंतरिक्ष, लेकिन हम समय बचाने के लिए.
इस मामले में, हम कर रहे हैं समय दे रही है लेकिन हम कर रहे हैं
लचीलापन पाने, गतिशीलता अगर तुम जाएगा,
जो यकीनन एक सकारात्मक विशेषता है.
>> हम भी अंतरिक्ष खर्च कर रहे हैं.
क्या अर्थ में एक लिंक किया गया है अधिक महंगी की सूची
एक सरणी से अंतरिक्ष के संदर्भ में?
जहां अतिरिक्त जगह से आ रही है?
हाँ?
>> दर्शक: [अश्राव्य] सूचक.
>> डेविड जे Malan: हाँ, हम भी सूचक है.
तो इस minorly गुस्सा आ रहा है उस में नहीं रह गया हूँ
मैं सिर्फ एक पूर्णांक के भंडारण एक पूर्णांक प्रतिनिधित्व करने के लिए.
मैं एक पूर्णांक और एक भंडारण कर रहा हूँ भी 32 बिट है जो सूचक,.
तो मैं सचमुच दोहरीकरण हूँ अंतरिक्ष की राशि शामिल है.
इसलिए कि एक व्यापार बंद है, लेकिन कि पूर्णांक के मामले में है.
, आप पूर्णांक भंडारण नहीं कर रहे हैं कि मान लीजिए लेकिन इन आयतों के प्रत्येक लगता है
या ये मनुष्य की प्रत्येक प्रतिनिधित्व था एक शब्द, एक अंग्रेजी शब्द है कि
पांच अक्षर, 10 हो सकती है वर्ण, शायद उससे भी ज्यादा.
तब सिर्फ 32 अधिक बिट जोड़ने एक बड़ी बात की कम हो सकता है.
>> क्या छात्रों में से प्रत्येक अगर प्रदर्शन में
थे सचमुच छात्र structs कि शायद नाम और घरों और है
फोन नंबर और ट्विटर संभालती है और पसंद है.
इसलिए सभी क्षेत्रों में हम शुरू दूसरे दिन के बारे में बात कर,
के रूप में एक बड़ी बात की बहुत कम हमारे नोड्स अधिक दिलचस्प हो
और बड़ा है, हां, एक अतिरिक्त खर्च करने के लिए सूचक सिर्फ एक साथ उन्हें जोड़ने के लिए.
लेकिन वास्तव में, यह एक व्यापार बंद है.
और वास्तव में, कोड है अधिक जटिल है, के रूप में आप हूँ
के माध्यम से उड़े से देखना उस विशेष उदाहरण.
लेकिन क्या अगर वहाँ थे यहां कुछ पवित्र कंघी.
हम एक कदम नहीं लेते तो क्या पीछे की ओर, लेकिन एक विशाल कदम आगे
और एक डेटा लागू संरचना जो के माध्यम से हम
जैक या जैसे तत्वों पा सकते हैं क्रिस्टीन या किसी अन्य तत्वों
सच निरंतर समय में इस श्रेणी में?
खोज स्थिर है.
हटाएं स्थिर है.
सम्मिलित स्थिर है.
इन कार्यों के सभी लगातार कर रहे हैं.
यही कारण है कि हमारे पवित्र कंघी होगा.
और वह है, जहां हम अगली बार ले जाएगा.
फिर मिलते हैं.