[Powered by Google Translate] [6 सप्ताह जारी रहेगा]
[डेविड जे Malan] [हार्वर्ड विश्वविद्यालय]
[यह CS50 है.] [CS50.TV]
इस CS50 है और यह 6 सप्ताह के अंत है.
तो CS50x, हार्वर्ड 1 EDX पहल में शामिल पाठ्यक्रम
वास्तव में यह पिछले सोमवार से शुरू हुआ.
यदि आप इंटरनेट पर क्या दूसरों की एक झलक पाने के लिए करना चाहते हैं
अब के साथ के बाद, आप x.cs50.net के लिए सिर कर सकते हैं.
कि आप edx.org पर उचित जगह अनुप्रेषित करेगा,
जो जहां इस और एमआईटी और बर्कले से अन्य पाठ्यक्रमों अब जीना है.
आप एक खाते के लिए साइन अप करना होगा, तो आप पाएंगे कि सामग्री बड़े पैमाने पर है ही
के रूप में आप इस सेमेस्टर लिया है, एक कुछ हफ्तों की देरी यद्यपि, जैसा कि हम सब कुछ तैयार हो जाओ.
लेकिन CS50x में छात्रों को अब देखते हैं कि क्या यह एक तरह काफी एक इंटरफेस है.
यह, उदाहरण के लिए, समस्या 0 सेट के लिए अग्रणी walkthrough Zamyla है.
पर edx.org में प्रवेश, एक CS50x छात्र चीजों की तरह देखता है
आप के लिए एक पाठ्यक्रम में देखने की उम्मीद करेंगे: सोमवार के लिए व्याख्यान
बुधवार, विभिन्न शॉर्ट्स, समस्या सेट, walkthroughs, PDFs के लिए व्याख्यान.
इसके अलावा, जैसा कि आप यहाँ देख सकते हैं, मशीन अनुवाद
अंग्रेजी, चीनी, जापानी, स्पेनिश, इतालवी में टेप की,
और अन्य भाषाओं की एक पूरी गुच्छा है कि निश्चित रूप से अपूर्ण होगा
के रूप में हम उन्हें बाहर रोल प्रोग्राम उपयोग एक एपीआई कहलाती,
गूगल से या एप्लीकेशन प्रोग्रामिंग इंटरफेस,
कि हमें इन अन्य भाषाओं के लिए अंग्रेजी कन्वर्ट करने के लिए अनुमति देता है.
लेकिन कुछ सौ से अधिक स्वयंसेवकों की अद्भुत भावना के लिए धन्यवाद,
इंटरनेट पर यादृच्छिक लोगों को जो कृपया शामिल करने के लिए पेशकश की है
इस परियोजना में, हम धीरे - धीरे उन अनुवादों की गुणवत्ता में सुधार हो जाएगा
मनुष्य गलतियों कि हमारे कंप्यूटर बना दिया है सही होने से.
>> तो यह मुड़ता बाहर हम कुछ अधिक छात्रों ने सोमवार को था पता चलता है की तुलना में हम शुरू में उम्मीद थी.
वास्तव में, अब CS50x 100.000 लोगों को घर पर साथ निम्नलिखित है.
एहसास तो आप कंप्यूटर विज्ञान के क्षेत्र में इस पाठ्यक्रम बनाने के इस उद्घाटन वर्ग के सभी भाग
आम तौर पर और अधिक शिक्षा, अधिक मोटे तौर पर, सुलभ.
और वास्तविकता अब इन बड़े पैमाने पर ऑनलाइन पाठ्यक्रम में से कुछ के साथ है,
वे सब ये बहुत उच्च संख्या के साथ शुरू करते हैं, के रूप में हम यहाँ किया है लगता है.
लेकिन लक्ष्य, अंततः, CS50x के लिए सच है संभव के रूप में खत्म लाइन के रूप में कई लोगों के लिए.
डिजाइन करके, CS50x यह पिछले सोमवार से की पेशकश की होने जा रहा है
15 अप्रैल, 2013 के माध्यम से सभी तरह, तो यह है कि लोगों को जो स्कूल प्रतिबद्धताओं कहीं और है,
काम, परिवार, अन्य संघर्ष और इस तरह, थोड़ा और अधिक लचीलापन है
जो के साथ इस पाठ्यक्रम में गोता लगाने के लिए है, जो यह कहने के लिए पर्याप्त है,
काफी ambitiously केवल अगर सिर्फ एक सामान्य सेमेस्टर के दौरान तीन महीने के पाठ्यक्रम से अधिक किया.
लेकिन इन छात्रों को एक ही समस्या सेट से निपटने जाएगा, एक ही सामग्री को देखने,
एक ही शॉर्ट्स और की तरह करने के लिए उपयोग कर रही है.
तो पता है कि हम सब एक साथ इस में वास्तव में कर रहे हैं.
और सिर्फ एक CS50x के अंत तक लक्ष्य के रूप में कई लोगों को पाने के लिए नहीं है
खत्म लाइन के लिए और उन्हें कंप्यूटर विज्ञान के इस newfound समझ दे
और, लेकिन यह भी प्रोग्रामिंग करने के लिए उन्हें इस साझा अनुभव है.
परिसर में परिभाषित 50 की विशेषताओं में से एक है, हमें उम्मीद है कि
सांप्रदायिक अनुभव के इस तरह किया गया है, के लिए बेहतर या बदतर के लिए, कभी कभी,
लेकिन इन लोगों को छोड़ दिया और सही करने के लिए बारी के लिए,
और कार्यालय घंटे और hackathon और निष्पक्ष.
यह थोड़ा कठिन है कि ऑनलाइन लोगों के साथ व्यक्ति में,
लेकिन CS50x अप्रैल में पहले कभी CS50 एक्सपो के साथ समाप्त होगा,
जो मेले के हमारे विचार की एक ऑनलाइन अनुकूलन होगा
जहां छात्रों के इन हजारों सभी 1 एक प्रस्तुत करने के लिए आमंत्रित किया जाएगा - 2 मिनट का वीडियो
या तो उनके अंतिम या उनमें से परियोजना वीडियो की एक screencast हैलो लहराते
और अपनी परियोजना के बारे में बात कर रही है और यह demoing,
अपने पूर्ववर्तियों की तरह बहुत यहाँ परिसर में मेले में किया है,
इतना है कि सेमेस्टर के अंत तक उम्मीद है के लिए एक वैश्विक प्रदर्शनी है
CS50x छात्रों के अंतिम परियोजनाओं की, कि बहुत पसंद है जो आप यहाँ परिसर में इस वर्ष दिसंबर में इंतजार कर रहा है.
तो उस पर आने वाले महीनों में अधिक है.
>> 100.000 छात्रों के साथ है, हालांकि, कुछ अधिक सीए के लिए एक की जरूरत है.
यह देखते हुए कि तुम लोगों को निशान प्रज्वलन कर रहे हैं यहाँ और ले जा रहा CS50
कई हफ्तों EDX पर लोगों के लिए इस सामग्री की रिहाई के अग्रिम में,
पता है हम इस पहल में संभव के रूप में हमारे अपने छात्रों के कई शामिल प्यार होता,
दोनों के रूप में के रूप में अच्छी तरह से इस सर्दियों सेमेस्टर के दौरान और इस आने वाले वसंत.
तो अगर आप CS50x में शामिल प्राप्त करना चाहते हैं,
CS50x चर्चा, चर्चा की CS50 EDX संस्करण पर विशेष रूप में शामिल होने,
जो आप में से कई के परिसर में उपयोग किया गया है, ऑनलाइन बुलेटिन बोर्ड,
कि यूआरएल के लिए सिर करना, हमें पता है कि आप कौन हैं,
क्योंकि हम छात्रों और कर्मचारियों की एक टीम और संकाय के समान बनाने के लिए प्यार करता हूँ
परिसर में जो बस के साथ खेल रहे हैं और बाहर की मदद करने.
और जब वे एक सवाल है कि उन से परिचित है,
आप कुछ बग कहीं बाहर वहाँ इंटरनेट पर कुछ देश में रिपोर्टिंग छात्र सुन,
और कि एक घंटी बजती है, क्योंकि तुम भी है कि एक ही मुद्दा था
अपने घ हॉल में कुछ समय पहले, तो उम्मीद है कि आप में खनकती है और अपने खुद के अनुभव को साझा कर सकते हैं.
हिस्सा लेना अगर आप चाहते हैं तो कृपया करते हैं.
>> हार्वर्ड में कंप्यूटर विज्ञान के पाठ्यक्रमों में एक परंपरा के एक सा है,
उनके बीच कुछ परिधान, कुछ कपड़े, कि आप गर्व से पहन सकते हैं होने के CS50
सेमेस्टर के अंत में, काफी गर्व से कह रही है कि आप समाप्त हो CS50
और CS50 और की तरह ले लिया है, और हम हमेशा के लिए छात्रों को शामिल करने की कोशिश
इस प्रक्रिया में जितना संभव हो सके, जिससे हम आमंत्रित,
सेमेस्टर के इस समय के आसपास, छात्रों को डिजाइन प्रस्तुत करने के लिए
फ़ोटोशॉप का उपयोग कर, या अपनी पसंद की जो भी उपकरण आप उपयोग करना चाहते हैं
यदि आप एक डिजाइनर रहे हैं, टी शर्ट और sweatshirts के लिए डिजाइन प्रस्तुत
और कुत्तों के लिए और छतरियों थोड़ा bandanas अब हम और पसंद है.
और सब कुछ है तो प्रत्येक वर्ष के विजेताओं का प्रदर्शन कर रहे हैं तो
store.cs50.net पर पाठ्यक्रम वेबसाइट पर.
सब कुछ वहाँ कीमत पर बेचा जाता है, लेकिन वेबसाइट सिर्फ खुद रन
और लोगों को रंगों और डिजाइनों है कि वे पसंद चुनने के लिए अनुमति देता है.
तो मैंने सोचा कि हम पिछले साल के डिजाइन का कुछ हिस्सा था
कि यह यहाँ एक के अलावा वेबसाइट पर थे, जो एक वार्षिक परंपरा है.
प्रस्तुतियाँ के "हर दिन मैं Faultn Seg रहा हूँ" पिछले वर्ष की थी,
जो अभी भी पूर्व छात्रों के लिए उपलब्ध है.
हम इस एक था, "CS50, 1989 में स्थापना की."
हमारे Bowdens में से एक, रोब, बहुत लोकप्रिय पिछले वर्ष की थी.
"टीम Bowden जन्म हुआ था, इस डिजाइन, शीर्ष विक्रेताओं के बीच पेश किया गया था.
के रूप में इस यहाँ एक था. कई लोगों को बिक्री लॉग के अनुसार "Bowden बुखार" था.
एहसास है कि कि अब वहाँ अपने डिजाइन हो सकता है, इंटरनेट पर.
इस पर अगले समस्या के बारे में अधिक जानकारी के लिए आने सेट है.
>> एक और उपकरण: आप कुछ जोखिम लिया है और अब उम्मीद है कि
GDB के साथ कुछ अनुभव हाथ पर,
जो कोर्स की है, एक debugger और आप में हेरफेर करने की अनुमति देता है
एक काफी कम स्तर पर अपने कार्यक्रम कर रहे हैं, क्या प्रकार की बातें?
GDB क्या है तुम करते हो?
हाँ? मुझे कुछ दे. [छात्र जवाब, unintelligible]
अच्छा है. समारोह में कदम है, तो आप बस चलाने के लिए टाइप नहीं है
और अपनी संपूर्णता के माध्यम से कार्यक्रम को झटका है, बाहर मुद्रण मानक आउटपुट में बातें.
इसके बजाय, आप लाइन से लाइन के माध्यम से यह कदम है, या तो अगले टाइप कर सकते हैं
लाइन या करने के लिए एक समारोह में गोता, आम तौर पर एक है कि आप ने लिखा कदम लाइन से लाइन जाने के लिए.
और क्या GDB देना नहीं है आप करते हैं? हाँ? [छात्र जवाब, unintelligible]
चर प्रिंट. तो अगर आप अपने कार्यक्रम के अंदर एक छोटे से आत्मनिरीक्षण करना चाहते हैं
सभी जगह पर printf बयान लिखने के लिए उपाय करने के लिए बिना,
आप सिर्फ एक चर मुद्रित कर सकते हैं या एक चर प्रदर्शित.
GDB तरह एक डिबगर के साथ आप और क्या कर सकते हैं?
[छात्र जवाब, unintelligible]
बिल्कुल सही. आप breakpoints सेट कर सकते हैं, आप को तोड़ने के निष्पादन कह सकते हैं
मुख्य समारोह या foo समारोह में.
आप 123 लाइन पर तोड़ निष्पादन कह सकते हैं.
और breakpoints एक बहुत शक्तिशाली तकनीक
क्योंकि अगर तुम जहां आपकी समस्या का एक सामान्य भावना है
शायद, आप है नहीं है समय बर्बाद करने के लिए कार्यक्रम सम्पूर्णता के माध्यम से कदम.
आप अनिवार्य रूप से सही कूद कर सकते हैं और फिर लिखना प्रारंभ करें -
कदम या अगले या जैसे के साथ के माध्यम से यह कदम.
लेकिन GDB की तरह कुछ के साथ पकड़ है कि यह आप में मदद करता है, मानव,
अपनी समस्याओं को खोजने के लिए और अपने कीड़े मिल.
यह जरूरी उन्हें नहीं मिल रहा है आप के लिए बहुत ज्यादा है.
>> तो हम दूसरे दिन style50 शुरू की है, जो एक छोटी कमांड लाइन उपकरण है
कि अपने कोड थोड़ा और अधिक की तुलना में आप सफाई stylize करने की कोशिश करता है, मानव, किया हो सकता है.
लेकिन यह है कि, भी, वास्तव में सिर्फ एक सौंदर्य बात है.
लेकिन यह निकलता है वहाँ यह अन्य वेलग्रिंड नामक उपकरण है कि एक छोटे से अधिक उपयोग करने के लिए रहस्यमय है.
इसका उत्पादन atrociously पहली नज़र में गुप्त है.
लेकिन यह शानदार उपयोगी है, विशेष रूप से अब है कि हम कार्यकाल के भाग में हो
जहां आप malloc और गतिशील स्मृति आवंटन का उपयोग शुरू कर रहे हैं.
हालात वास्तव में, वास्तव में गलत जल्दी से जा सकते हैं.
क्योंकि अगर आप अपनी स्मृति को मुक्त करने के लिए भूल जाते हैं, या आप कुछ NULL संकेतक भिन्नता,
या आप कुछ कचरा संकेतक भिन्नता है, जो आम तौर पर परिणाम है कि लक्षण है?
फॉल्ट. और तुम किलोबाइट्स या मेगाबाइट्स की कुछ संख्या के इस कोर फाइल
कि अपने कार्यक्रम की स्मृति के राज्य का प्रतिनिधित्व करता है जब यह दुर्घटनाग्रस्त हो गया,
लेकिन अपने कार्यक्रम के अंत में दोष seg, विभाजन गलती,
जिसका अर्थ है कि कुछ बुरा लगभग हमेशा संबंधित हुआ
स्मृति से संबंधित एक गलती है कि आप कहीं बनाया.
तो वेलग्रिंड आप इस तरह से चीजों को खोजने में मदद करता है.
यह एक उपकरण है कि आप चलाने, GDB तरह, के बाद आप अपने कार्यक्रम को संकलित किया है,
लेकिन बजाय सीधे अपने कार्यक्रम चलाने के लिए, आप चलाने के वेलग्रिंड
और आप इसे अपने कार्यक्रम के पास, बस तुम जैसे GDB के साथ करते हैं.
अब, उपयोग, उत्पादन की सबसे अच्छी तरह पाने के लिए,
थोड़ी देर तो स्क्रीन के ऊपर सही वहाँ आप वेलग्रिंड-V देखेंगे.
"V" लगभग सार्वभौमिक वाचाल मतलब है कि जब आप एक Linux कंप्यूटर पर कार्यक्रमों का उपयोग कर रहे हैं.
तो इसका मतलब है आप कर सकते हैं डिफ़ॉल्ट रूप से अधिक से अधिक डेटा थूक.
- = पूर्ण रिसाव की जाँच करें. " यह सिर्फ सभी संभव स्मृति लीक के लिए जांच को कह रहा है,
गलतियों कि मैं बना हो सकता है. यह भी, लिनक्स कार्यक्रमों के साथ एक आम प्रतिमान है.
आम तौर पर, यदि आप एक कमांड लाइन तर्क है कि एक "स्विच" है,
कि कार्यक्रम व्यवहार को बदलने के लिए माना जाता है, और यह एक पत्र है,
यह-V, लेकिन वह बंद है अगर सिर्फ प्रोग्रामर के डिजाइन,
एक पूर्ण शब्द या शब्द की श्रृंखला, कमांड लाइन तर्क के साथ शुरू होता है.
ये सिर्फ मानव सम्मेलनों, लेकिन आप उन्हें तेजी से देखेंगे.
और फिर, अंत में, इस विशिष्ट उदाहरण में कार्यक्रम के लिए मनमाने ढंग से नाम "a.out".
और यहाँ कुछ प्रतिनिधि उत्पादन है.
>> इससे पहले कि हम है कि क्या मतलब हो सकता है पर देखो, मुझे यहाँ पर कोड का एक टुकड़ा के खत्म हो जाने के.
और मुझे जिस तरह के इस बाहर ले जाने के लिए, जल्द ही आ रहा है,
और memory.c, जो इस छोटे से उदाहरण यहाँ पर एक नज़र रखना.
तो इस कार्यक्रम में, मुझे कार्यों और सवालों पर में ज़ूम.
हम एक मुख्य कार्य है, कि एक समारोह कॉल च,
और फिर च क्या थोड़ा तकनीकी अंग्रेजी में करते हैं, आगे बढ़ना है?
च क्या आगे बढ़ना नहीं करते हैं?
कैसे के बारे में मैं 20 लाइन के साथ शुरू करेंगे और स्टार के स्थान से कोई फर्क नहीं पड़ता,
लेकिन मैं सिर्फ लगातार पिछले व्याख्यान के साथ यहाँ हो जाएगा.
20 रेखा क्या है हमारे लिए करते हैं? बाएँ हाथ की तरफ. हम इसे तोड़ने के नीचे आगे हूँ.
Int * x: कि क्या करना है?
ठीक है. यह एक सूचक की घोषणा है, और अब हम और भी अधिक तकनीकी हो.
यह क्या करता है, बहुत concretely मतलब है, के लिए एक सूचक की घोषणा? किसी और ने?
हाँ? [छात्र जवाब, unintelligible] बहुत दूर है.
तो आप बराबर के चिह्न के दाएँ हाथ की ओर करने के लिए पढ़ रहे हैं.
बस बाईं तरफ चलो int * x बस पर ध्यान केंद्रित है.
यह एक सूचक "घोषित", लेकिन अब हम कि परिभाषा को गहरा गोता.
कि concretely तकनीकी, क्या मतलब है? हाँ?
[छात्र जवाब, unintelligible]
ठीक है. यह स्मृति में एक पते को बचाने की तैयारी है.
अच्छा है. और यह एक कदम आगे ले, यह एक चर, x, कि 32 बिट की घोषणा है.
और मुझे पता है कि यह क्योंकि 32 बिट है?
ऐसा नहीं है क्योंकि यह एक int है, क्योंकि यह इस मामले में एक सूचक है.
संयोग है कि यह एक और एक int के साथ एक ही है,
लेकिन तथ्य यह है कि वहाँ सितारा मतलब है कि यह एक संकेत है
उपकरण में कई कंप्यूटरों के साथ के रूप में, लेकिन सभी नहीं, संकेत 32 बिट कर रहे हैं.
नवीनतम एमएसीएस, नवीनतम पीसी की तरह अधिक आधुनिक हार्डवेयर पर, आप 64-bit संकेत हो सकता है,
लेकिन उपकरण में, इन बातों को 32 बिट कर रहे हैं.
तो हम उस पर मानकीकरण करेंगे. अधिक concretely, कहानी इस प्रकार के रूप में चला जाता है:
हम एक सूचक "घोषित", इसका क्या मतलब है?
हम एक स्मृति पते की दुकान करने के लिए तैयार है.
इसका क्या मतलब है?
हम एक चर बुलाया एक्स है कि 32 बिट लेता
कि जल्द ही एक पूर्णांक के पते की दुकान होगी.
और कहा कि शायद के बारे में के रूप में सटीक रूप में हम प्राप्त कर सकते है.
यह ठीक है आगे बढ़ने के लिए दुनिया सरल और बस का कहना है एक एक्स नामक सूचक की घोषणा.
एक सूचक एलान, लेकिन पता है और समझ में वास्तव में क्या हो रहा है
बस उन कुछ अक्षरों में भी.
>> अब, यह एक लगभग एक थोड़ा आसान है, हालांकि यह एक लंबी अभिव्यक्ति है.
तो यह क्या है, कर रही है कि अब डाला है: "malloc (10 * (int) sizeof)," हाँ?
[छात्र जवाब, unintelligible]
अच्छा है. और मैं यह वहाँ ले जाऊँगा. यह दस integers के लिए स्मृति का एक हिस्सा आवंटित है.
और अब चलो थोड़ा गहरा गोता, यह दस integers के लिए स्मृति का एक हिस्सा आवंटित है.
Malloc क्या फिर लौट रहा है?
कि हिस्सा के पते, या, अधिक concretely, उस हिस्सा की पहली बाइट के पते.
तो कैसे मैं कर रहा हूँ, प्रोग्रामर पता है, जहां स्मृति समाप्त होता है की है कि हिस्सा?
मुझे पता है कि यह सन्निहित है. Malloc, परिभाषा के द्वारा, आप स्मृति का एक सन्निहित हिस्सा दे देंगे.
यह में कोई अंतर. तुम कि हिस्सा में हर बाइट के लिए उपयोग किया है,
वापस वापस करने के लिए वापस करने के लिए, लेकिन मैं कैसे जानते हो, जहां स्मृति के इस हिस्सा का अंत है?
जब आप malloc का उपयोग करते हैं? [छात्र जवाब, unintelligible] अच्छा है.
तुम नहीं. तुम्हें याद है.
मैं याद करने के लिए है कि मैं 10 मूल्य का इस्तेमाल किया है, और मैं यह भी है कि यहाँ किया है नहीं लगता है.
लेकिन जिम्मेदारी मुझ पर पूरी तरह से है. Strlen, जो हम थोड़ा पर निर्भर तार के लिए बन गया है,
\ 0 होने के इस सम्मेलन की वजह से ही काम करता है
या इस विशेष nul चरित्र, एक स्ट्रिंग के अंत में नुल,.
यह सिर्फ मनमाना स्मृति की मात्रा के लिए पकड़ नहीं है.
यह आप पर निर्भर है. 20 लाइन तो, फिर, स्मृति का एक हिस्सा आवंटित
है कि दस integers स्टोर कर सकते हैं, और यह पहली बाइट के पते भंडार
चर x में स्मृति की कि हिस्सा.
फलस्वरूप, जो एक संकेत है. 21 लाइन तो, दुर्भाग्य से, एक गलती थी.
लेकिन पहले, यह क्या कर रहा है? यह स्थान 10, 0 अनुक्रमित में दुकान कह रहा है,
स्मृति का हिस्सा x मान 0 बुलाया.
>> तो नोटिस चीजों के एक जोड़े पर जा रहे हैं.
हालांकि x एक सूचक है, एक दो सप्ताह पहले से याद
कि तुम अब भी वर्ग सरणी शैली ब्रैकेट संकेतन का उपयोग कर सकते हैं.
वजह है कि वास्तव में अधिक गुप्त दिखने सूचक गणित के लिए लघु हाथ अंकन है.
जहां हम इस तरह कुछ करना होगा: पता एक्स ले लो, पर 10 स्थानों को स्थानांतरित करने के लिए,
तो पते जो कुछ भी उस स्थान पर संग्रहीत करने के लिए वहाँ जाओ.
लेकिन स्पष्ट रूप से, यह सिर्फ पापिष्ठ है पढ़ने के लिए और साथ आराम मिलता है.
तो आम तौर पर दुनिया वर्ग कोष्ठक का उपयोग करता है, सिर्फ इसलिए कि यह इतना अधिक मानव के अनुकूल को पढ़ने के लिए है.
लेकिन यह है कि क्या वास्तव में हुड के नीचे हो रहा है;
x एक पते, से प्रति एक सरणी नहीं है.
तो यह एक्स में 10 स्थान पर 0 भंडारण है.
यह क्यों बुरा है? हाँ?
[छात्र जवाब, unintelligible] बिल्कुल सही.
हम केवल दस ints आवंटित है, लेकिन हम 0 से गिनती जब सी में प्रोग्रामिंग,
तो आप 0 1 2 3 4 5 6 7 8 9, लेकिन नहीं 10 के लिए उपयोग किया है.
तो या तो कार्यक्रम seg गलती के लिए जा रहा है या यह नहीं है.
लेकिन हम वास्तव में नहीं पता नहीं है, यह एक nondeterministic व्यवहार की तरह है.
यह सच है कि हम भाग्यशाली मिल पर निर्भर करता है.
अगर यह पता चला है कि ऑपरेटिंग सिस्टम का मन नहीं करता है अगर मैं उस अतिरिक्त बाइट का उपयोग करें,
हालांकि यह मेरे लिए नहीं दिया है, मेरे कार्यक्रम दुर्घटना नहीं हो सकता है.
यह कच्चा है, यह छोटी गाड़ी है, लेकिन आपको लगता है कि लक्षण नहीं देख सकता है,
या आप इसे एक समय में केवल एक बार देख सकते हैं.
लेकिन वास्तविकता यह है कि बग वास्तव में है, वहाँ.
और यह वास्तव में समस्याग्रस्त है अगर आप एक प्रोग्राम है कि आप सही होना चाहता हूँ लिखा है,
कि आप इस कार्यक्रम को बेच दिया है कि लोगों का उपयोग कर रहे हैं कि हर बार एक समय में दुर्घटनाओं
क्योंकि, ज़ाहिर है, यह अच्छा नहीं है. वास्तव में, यदि आप एक Android फोन या एक iPhone है
और आप इन दिनों क्षुधा डाउनलोड, अगर तुम कभी एक app बस छोड़ दिया,
अचानक वह गायब हो जाता है, कि लगभग हमेशा स्मृति से संबंधित कुछ मुद्दे का परिणाम है,
जिससे प्रोग्रामर बँधा हुआ है और dereferenced एक सूचक
कि वह या वह नहीं होना चाहिए, और IOS या Android के परिणाम सिर्फ कार्यक्रम पूरी तरह मार रहा है
बजाय जोखिम अपरिभाषित व्यवहार या सुरक्षा समझौते के कुछ तरह से.
>> इस एक के अलावा इस कार्यक्रम में एक अन्य बग है.
और क्या मैं इस कार्यक्रम में बँधा हुआ है?
मैं अभ्यास नहीं है कि मैं क्या उपदेश है. हाँ?
[छात्र जवाब, unintelligible] अच्छा है.
मैं स्मृति मुक्त नहीं है. तो अब अंगूठे का नियम
हो सकता है किसी भी समय आप malloc कहते हैं, तो आप कॉल मुफ्त जब आप काम कर रहे हैं कि स्मृति का उपयोग करना चाहिए है.
अब, जब मैं इस स्मृति मुक्त करना चाहते हैं?
शायद, यह सोचते हैं यह पहली लाइन सही था, मैं इसे यहाँ क्या चाहते हो जाएगा.
क्योंकि मैं, उदाहरण के लिए नहीं है, यह कर सकता है यहाँ नीचे. क्यों?
बस के दायरे से बाहर है. तो भले ही हम संकेत के बारे में बात कर रहे हैं,
यह एक 2 या 3 सप्ताह मुद्दा है, जहां x घुंघराले ब्रेसिज़ जहां यह घोषित किया गया था के अंदर दायरे में ही है.
तो आप निश्चित रूप से यह वहाँ मुक्त नहीं कर सकते हैं. मेरी ही मौका इसे मुक्त लाइन 21 के बाद लगभग है.
यह एक काफी सरल कार्यक्रम है, यह काफी आसान था एक बार आप की तरह अपने मन लिपटे
क्या आसपास के कार्यक्रम कर रही है, जहां गलतियों थे.
और यहां तक ​​कि अगर आप इसे पहली बार में नहीं देखा था, उम्मीद है कि यह एक छोटे से स्पष्ट है अब
कि इन गलतियों को बहुत आसानी से हल कर रहे हैं और आसानी से बनाया है.
लेकिन जब एक कार्यक्रम में 12 से अधिक लाइनों लंबा है, यह 50 लाइनें लंबी, 100 लाइनें लंबी है,
लाइन द्वारा अपने कोड लाइन के माध्यम से चल रहा है, यह सोच के माध्यम से तार्किक,
संभव है, लेकिन करने के लिए विशेष रूप से कोई मजाक नहीं है, लगातार कीड़ों के लिए तलाश कर रहे हैं,
और यह भी मुश्किल है, और यही कारण है कि वेलग्रिंड तरह एक उपकरण मौजूद है.
मुझे आगे जाना है और इस कार्य करें: मुझे मेरे टर्मिनल विंडो खोलने,
और मुझे स्मृति बस नहीं चला, क्योंकि स्मृति ठीक हो रहा है.
मैं भाग्यशाली हो रही है. सरणी के अंत में है कि अतिरिक्त बाइट के लिए जा रहे
नहीं लगता भी समस्याग्रस्त हो.
लेकिन मुझे, फिर भी, एक मानसिक स्वास्थ्य की जांच, जो बस के लिए जांच का मतलब
चाहे या नहीं यह वास्तव में सही है.
>> तो चलो वेलग्रिंड-V - = पूर्ण रिसाव की जांच,
और फिर इस मामले में कार्यक्रम का नाम, a.out स्मृति नहीं है.
तो मुझे आगे जाना है और इस करते हैं. हिट दर्ज करें.
प्रिय भगवान. यह अपने उत्पादन है, और यह है कि मैं क्या पहले के लिए alluded.
लेकिन, अगर आप यहाँ बकवास के सभी के माध्यम से पढ़ने के लिए सीख है,
इस का सबसे नैदानिक ​​उत्पादन है कि दिलचस्प है कि नहीं है.
अपनी आंख सच के लिए देख रहे हो चाहता है क्या त्रुटि या अमान्य के किसी भी उल्लेख है.
शब्द है कि समस्याओं का सुझाव है.
और वास्तव में, चलो देखते हैं क्या गलत हो रहा है यहाँ नीचे.
मैं किसी तरह की एक सारांश, "प्रयोग में बाहर निकलने पर: 1 ब्लॉक में 40 बाइट्स"
मैं वास्तव में यकीन है कि एक ब्लॉक क्या है अभी तक नहीं कर रहा हूँ, लेकिन 40 बाइट्स
वास्तव में लगता है जैसे मैं बाहर आंकड़ा कहाँ से आ रहा है.
40 बाइट. बाहर निकलने पर उपयोग में 40 बाइट्स क्यों कर रहे हैं?
और अधिक विशेष रूप से, अगर हम यहाँ नीचे स्क्रॉल,
मैं निश्चित रूप से क्यों 40 बाइट्स खो गई है? हाँ?
[छात्र जवाब, unintelligible] परफेक्ट. हाँ, बिल्कुल.
वहाँ दस integers थे, और उन में से प्रत्येक 4, या 32 बिट के आकार है,
तो मैं ठीक 40 बाइट्स खो दिया है क्योंकि, जैसा कि आप का प्रस्ताव, मैं मुक्त नहीं बुलाया है.
यह एक बग है, और अब चलो थोड़ा आगे लग रही है और यह अगले देख,
"अवैध 4 आकार के लिखने के लिए." अब यह क्या है?
इस पते का क्या आधार संकेतन व्यक्त किया है, जाहिरा तौर पर?
यह षोडश आधारी है, और किसी भी समय आप एक संख्या 0x से शुरू,
यह षोडश आधारी का मतलब है, जो हम मुझे लगता है, सवालों के pset 0 अनुभाग में जिस तरह से वापस किया था,
जो सिर्फ एक warmup व्यायाम करने के लिए किया गया, द्विआधारी हेक्स दशमलव बदलने और इतना आगे.
हेक्साडेसिमल, मानव सम्मेलन द्वारा, आम तौर पर करने के लिए संकेत का प्रतिनिधित्व करने के लिए इस्तेमाल किया जाता है
या, और अधिक सामान्यतः पते,. यह सिर्फ एक सम्मेलन है,
क्योंकि यह थोड़ा आसान है पढ़ने के लिए, यह एक छोटे से अधिक दशमलव की तरह कुछ की तुलना में कॉम्पैक्ट है,
और बाइनरी बेकार है लिए सबसे मनुष्य का उपयोग करने के लिए.
तो अब इसका क्या मतलब है? खैर, यह लगता है कि वहाँ एक अवैध लिखने
memory.c के 21 लाइन पर 4 आकार के.
तो चलो 21 लाइन के लिए वापस जाना है, और वास्तव में, यहाँ कि अवैध लिखना.
तो वेलग्रिंड के लिए पूरी तरह से अपने हाथ पकड़ और मुझे बताओ कि ठीक है क्या नहीं जा रहा है,
लेकिन यह पता लगाने है कि मैं एक अवैध लिखने कर रहा हूँ.
मैं 4 बाइट्स छू रहा हूं कि मैं नहीं होना चाहिए, और जाहिर है कि वजह से है,
के रूप में आप ने कहा, मैं [9] [10] के बजाय कर रहा हूँ ज़्यादा से ज़्यादा
या [0] या बीच में कुछ.
वेलग्रिंड के साथ, किसी भी समय आप अब एक कार्यक्रम लिख रहे हैं का एहसास
कि संकेत का उपयोग करता है और स्मृति का उपयोग करता है, और अधिक विशेष रूप से malloc,
निश्चित रूप से यह लंबे समय तक चलने की आदत में मिलता है
लेकिन बहुत आसानी से कॉपी और चिपकाया वेलग्रिंड की कमान
देखने के लिए अगर वहाँ में कुछ त्रुटियाँ है.
और यह भारी हर बार जब आप देखते हैं उत्पादन हो जाएगा,
लेकिन बस के माध्यम से उत्पादन के सभी नेत्रहीन पार्स और देखते हैं कि यदि आप देखते हैं त्रुटियों का उल्लेख
या चेतावनी या अमान्य या खो दिया है.
कोई भी शब्द है कि ध्वनि की तरह आप कहीं खराब कर दिया है.
तो एहसास है कि अपने Toolkit में एक नया उपकरण है.
>> सोमवार को अब, हम लोगों की एक पूरी गुच्छा था यहाँ आने
और एक लिंक सूची की धारणा का प्रतिनिधित्व करते हैं.
और हम समस्या क्या करने के लिए एक समाधान के रूप में जुड़े हुए सूची शुरू की?
हाँ? [छात्र जवाब, unintelligible] अच्छा है.
Arrays स्मृति नहीं हो सकता है उन से कहा.
यदि आप 10 आकार की एक सरणी है, कि तुम सब मिल आवंटित.
आप realloc की तरह एक समारोह कॉल अगर आप शुरू में malloc कहा जा सकता है,
और कहा कि के लिए सरणी बढ़ने की कोशिश अगर वहाँ के अंत की ओर अंतरिक्ष है
कि कोई और नहीं एक का उपयोग कर रहा है, और अगर वहाँ नहीं है, यह सिर्फ एक बड़ा हिस्सा मिलेगा कहीं और.
लेकिन तब यह नई सरणी में उन बाइट्स की सभी कॉपी जाएगा.
यह एक बहुत ही सही समाधान की तरह लगता है.
इस बदसूरत क्यों है?
मेरा मतलब है कि यह काम करता है, मनुष्य इस समस्या को हल कर दिया है.
हम लिंक्ड सूचियों के साथ सोमवार को इसे सुलझाने के क्या ज़रूरत थी? हाँ?
[छात्र जवाब, unintelligible] यह एक लंबा समय लग सकता है.
वास्तव में, किसी भी समय आप malloc या realloc या calloc है, जो अभी तक एक और एक है बुला रहे हैं,
किसी भी समय आप, कार्यक्रम, ऑपरेटिंग सिस्टम के लिए बात कर रहे हैं,
आप कार्यक्रम धीमी गति से नीचे होते हैं.
और अगर आप loops में बातें की इन प्रकार के कर रहे हैं, तो आप वास्तव में बातें धीमा कर रहे हैं नीचे.
आप "हैलो दुनिया" प्रकार के कार्यक्रमों का सरलतम के लिए इस नोटिस के लिए नहीं जा रहे हैं,
लेकिन बहुत बड़े कार्यक्रमों में, स्मृति के लिए ऑपरेटिंग सिस्टम फिर से और फिर पूछ
या फिर और फिर इसे वापस देने के लिए एक अच्छी बात नहीं हो जाता है.
इसके अलावा, यह सिर्फ बौद्धिक की तरह है - यह समय की एक पूरी तरह से बेकार है.
क्यों अधिक से अधिक स्मृति आवंटित, जोखिम, नई सरणी में सब कुछ नकल
यदि आप एक विकल्प देता है कि आप केवल उतनी ही स्मृति को आबंटित करने के रूप में आप वास्तव में जरूरत है?
तो यहाँ में pluses और minuses है.
Pluses के एक अब है कि हम गतिशीलता है.
जहां स्मृति का हिस्सा हैं कि स्वतंत्र हैं कोई बात नहीं,
मैं सिर्फ बनाने के संकेत के माध्यम से इन रोटी के टुकड़ों को हल कर सकते हैं
मेरे पूरे लिंक सूची एक साथ स्ट्रिंग.
लेकिन मैं कम से कम एक मूल्य का भुगतान करते हैं.
>> मैं क्या लिंक सूचियों पाने में देना है?
हाँ? [छात्र जवाब, unintelligible] अच्छा है.
आप और अधिक स्मृति की जरूरत है. अब मैं ये संकेत के लिए जगह की जरूरत है,
और इस सुपर सरल लिंक सूची के मामले में
कि केवल integers, जो 4 बाइट्स की दुकान की कोशिश कर रहा है, हम कह रखना
अच्छी तरह से, एक सूचक 4 बाइट्स है, तो अब मैं सचमुच दोगुनी है
स्मृति की मात्रा मैं सिर्फ इस सूची की दुकान करने के लिए की जरूरत है.
लेकिन फिर, यह कंप्यूटर विज्ञान के क्षेत्र में एक निरंतर tradeoff
समय और स्थान और विकास के प्रयास, और अन्य संसाधनों के बीच.
एक लिंक सूची का उपयोग करने का एक और नकारात्मक पहलू क्या है? हाँ?
[छात्र जवाब, unintelligible]
अच्छा है. उपयोग के रूप में आसान नहीं है. हम अब और नहीं उत्तोलन कर सकते हैं
0 सिद्धांतों की तरह सप्ताह विभाजन और जीत.
और अधिक विशेष रूप से, द्विआधारी खोज. क्योंकि भले ही हम इंसानों
मोटे तौर पर देखने के लिए जहां इस सूची के बीच है,
कंप्यूटर ही जानता है कि इस लिंक सूची 1 बुलाया पते पर शुरू होता है.
और कहा कि 0x123 या उस तरह कुछ है.
और केवल कार्यक्रम जिस तरह से मध्य तत्व पा सकते हैं
वास्तव में पूरी सूची खोज है.
और फिर भी, यह सचमुच खोज पूरी सूची है, क्योंकि
यहां तक ​​कि एक बार आप संकेत के बाद से मध्य तत्व तक पहुँचने के लिए,
आप, कार्यक्रम, पता नहीं कितनी देर इस सूची में संभावित है,
जब तक आप इसे के अंत मारा, और आप प्रोग्राम कैसे जानते हो
कि आप एक लिंक सूची के अंत में कर रहे हैं?
वहाँ एक विशेष NULL संकेतक, तो फिर, एक सम्मेलन है.
इस सूचक का उपयोग के बजाय, हम निश्चित रूप से यह कुछ कचरा मूल्य होने के लिए नहीं करना चाहती
बंद की ओर इशारा करते हुए मंच कहीं, हम इसे हाथ होने के लिए बनाना चाहते हैं, अशक्त,
इतना है कि हम इस डेटा संरचना में इस टर्मिनस है तो हम जानते हैं कि जहां यह समाप्त हो जाती है.
>> क्या होगा अगर हम इस में हेरफेर करना चाहते हैं?
हम इस नेत्रहीन की सबसे किया, और मनुष्यों के साथ,
लेकिन क्या होगा अगर हम एक प्रविष्टि करने के लिए करना चाहते हैं?
तो मूल सूची 9, 17, 20, 22, 29, 34 था.
क्या होगा अगर हम तो 55 नंबर, इसके लिए एक नोड के लिए malloc अंतरिक्ष के लिए चाहता था,
और फिर हम सूची में डालने के 55 बस के रूप में हम सोमवार को किया था चाहते हैं?
हम यह कैसे करते हो? खैर, अनीता आया और वह सूची अनिवार्य रूप से चला गया.
वह पहली तत्व पर शुरू कर दिया है, तो अगले, अगले, अगले, अगले, अगले.
अंत में बाएं हाथ के सभी तरह मारा नीचे
और ओह एहसास, यह रिक्त है. तो क्या सूचक हेरफेर करने के लिए किया जाना चाहिए?
व्यक्ति जो अंत पर था, 34 नंबर की जरूरत है उसके बाएं हाथ उठाया
55 में बात करने के लिए, 55 को उनके बाएँ हाथ नीचे की ओर इशारा करते हुए नए रिक्त टर्मिनेटर की जरूरत है. हो गया.
बहुत आसान एक सॉर्ट की गई सूची में 55 डालने के लिए.
और यह कैसे लग सकता है?
>> मुझे आगे जाना है और कुछ कोड उदाहरण यहाँ खुला.
मैं जीएडिट खोलने के लिए, हूँ और मुझे दो फ़ाइलों 1 खोल.
एक list1.h है, और मुझे सिर्फ याद दिलाना है कि इस कोड का हिस्सा था
कि हम एक नोड का प्रतिनिधित्व करने के लिए इस्तेमाल किया.
एक नोड दोनों एक n बुलाया int और एक सूचक है कि बस अंक अगले सूची में अगले बात करने के लिए बुलाया है.
यह एक घंटे फ़ाइल में अब है. क्यों?
इस सम्मेलन है, और हम इस लाभ का एक विशाल राशि खुद नहीं ले लिया है,
लेकिन जो व्यक्ति printf और अन्य कार्यों लिखा
दुनिया के लिए एक उपहार के रूप में एक फ़ाइल stdio.h बुलाया लेखन के द्वारा उन सभी कार्यों का दिया.
और फिर वहाँ string.h है, और फिर वहाँ map.h है, और वहाँ इन सभी ज फ़ाइलें
है कि आप या देखा हो सकता है और अन्य लोगों के द्वारा लिखित अवधि के दौरान प्रयोग किया जाता है.
आम तौर पर उन में ज फ़ाइलें. Typedefs की तरह ही बातें कर रहे हैं
या कस्टम प्रकार या स्थिरांकों का घोषणाओं की घोषणाओं.
आप हेडर फाइल में 'कार्यों implementations मत डालो.
तुम डाल, बजाय, सिर्फ अपने प्रोटोटाइप.
आप दुनिया के साथ चीजों को वे क्या जरूरत है आप साझा करना चाहते
क्रम में अपने कोड संकलन करने के लिए. तो बस इस आदत में पाने के लिए,
हम एक ही बात करने का फैसला किया. वहाँ बहुत list1.h में नहीं है,
लेकिन हम दुनिया में कुछ है कि ब्याज की हो सकता है लोगों को डाल दिया है
जो हमारे लिंक सूची कार्यान्वयन का उपयोग करना चाहते हैं.
अब, list1.c में, मैं इस पूरी बात के माध्यम से नहीं जाना होगा
क्योंकि यह थोड़ा लंबा है, इस कार्यक्रम है, लेकिन यह असली शीघ्र पर जल्दी चला.
चलो मुझे List1 संकलन, मुझे तो List1 चलाने के, और आप क्या देखेंगे
हम नकली एक साधारण सा यहाँ कार्यक्रम है
कि मुझे जोड़ने और एक सूची को हटाने की अनुमति देता जा रहा है.
तो मुझे आगे जाना है और टाइप करें मेनू विकल्प 3 के लिए 3.
मैं संख्या सम्मिलित करना चाहते हैं - चलो पहली संख्या है, जो 9 था,
और अब मुझे बताया गया है कि सूची में अब 9.
मुझे आगे जाना है और एक अन्य प्रविष्टि करते हैं, तो मैं मेनू विकल्प 3 मारा.
मुझे किस नंबर सम्मिलित करने के लिए करना चाहते हैं? 17.
दर्ज करें. और मैं सिर्फ एक और करूँगा.
मुझे 22 नंबर डालने.
तो हम लिंक सूची है कि हम स्लाइड के रूप में एक पल पहले था की शुरुआत है.
कैसे इस प्रविष्टि को वास्तव में क्या हो रहा है?
दरअसल, 22 सूची के अंत में अब है.
कहानी तो हम सोमवार को मंच पर कहा था और अब सिर्फ recapped
वास्तव में कोड में हो जाना चाहिए.
चलो एक नज़र रखना. मुझे इस फाइल में नीचे स्क्रॉल.
हम पर कार्य के कुछ हाशिये या पंक्तियों के बीच लिखा हुआ मूल पाठ का अर्थ या व्याख्या करेंगे,
लेकिन हम नीचे जाना है, कहता हूँ, डालने समारोह.
>> चलो देखते हैं कि कैसे हम इस लिंक की गई सूची में एक नया नोड डालने के बारे में जाना.
कहाँ सूची घोषित किया जाता है? खैर, चलो शीर्ष पर सभी तरह पुस्तक,
और नोटिस कि मेरे लिंक सूची अनिवार्य रूप से एक ही सूचक है कि शुरू में नल है के रूप में घोषित किया जाता है.
तो मैं एक वैश्विक चर का उपयोग कर रहा हूँ यहाँ है, जो सामान्य रूप में हम के खिलाफ प्रचार किया है
क्योंकि यह अपने कोड बनाता है एक छोटी सी गड़बड़ करने के लिए बनाए रखने के लिए,
यह आलसी, आमतौर पर की तरह है, लेकिन यह आलसी नहीं है और यह गलत नहीं है और यह बुरा नहीं है
अगर अपने कार्यक्रम के जीवन में एकमात्र उद्देश्य के लिए एक लिंक सूची अनुकरण है.
जो वास्तव में हम क्या कर रहे हैं.
तो बजाय मुख्य में यह घोषित करने और फिर यह हर कार्य करने के लिए पारित किया है
हम इस कार्यक्रम में लिखा है, हम बजाय एहसास ओह, चलो बस यह वैश्विक बनाना
क्योंकि इस कार्यक्रम की पूरी उद्देश्य के लिए केवल एक और एक लिंक सूची प्रदर्शित करने के लिए है.
तो यह ठीक लगता है. यहाँ मेरे प्रोटोटाइप हैं, और हम इन सभी के माध्यम से नहीं जाना होगा,
लेकिन मैं एक को नष्ट समारोह, एक समारोह मिल, एक डालने समारोह और एक traverse समारोह लिखा था.
लेकिन अब डालने के कार्य करने के लिए वापस नीचे जाना
देखने के लिए और कैसे एक यह यहाँ काम करता है.
सम्मिलित लाइन पर है - यहाँ हम चले.
सम्मिलित करें. तो यह कोई तर्क नहीं ले, क्योंकि हम पूछने के लिए जा रहे हैं
संख्या में वे सम्मिलित करना चाहते हैं के लिए इस समारोह के अंदर उपयोगकर्ता.
लेकिन पहले, हम करने के लिए उन्हें कुछ जगह देने के लिए तैयार है.
यह और अन्य उदाहरण से कॉपी पेस्ट की तरह है.
उस मामले में, हम एक int आवंटन रहे थे, इस समय हम एक नोड का आवंटन कर रहे हैं.
मैं वास्तव में कितने बाइट्स एक नोड याद नहीं करते हैं, लेकिन वह ठीक है.
Sizeof कि मेरे लिए बाहर आंकड़ा कर सकते हैं.
और क्यों मैं 120 लाइन में नल के लिए जाँच कर रहा हूँ?
119 पंक्ति में क्या गलत हो सकता है? हाँ?
[छात्र जवाब, unintelligible]
अच्छा है. बस मामला है कि मैं बहुत अधिक स्मृति के लिए कहा है हो सकता है
या कुछ गड़बड़ है और ऑपरेटिंग सिस्टम के लिए पर्याप्त मुझे दे बाइट्स नहीं है,
तो यह नल के लौटने से के रूप में ज्यादा संकेत है, और अगर मैं उस के लिए जाँच नहीं
और मैं बस आँख बंद करके पते लौटे उपयोग करने के लिए आगे बढ़ना है, यह शून्य हो सकता है.
यह कुछ अज्ञात मूल्य हो सकता है, एक अच्छी बात नहीं है, जब तक मैं -
वास्तव में एक अज्ञात मूल्य नहीं होगा. यह शून्य हो सकता है तो, मैं नहीं चाहता
को यह दुरुपयोग करने और इसे dereferencing जोखिम.
अगर ऐसा होता है, मैं तो बस लौटने और हम जैसे मैं कोई स्मृति नहीं मिला सब पर नाटक करेंगे.
>> अन्यथा, मैं बता उपयोगकर्ता मुझे सम्मिलित करने के लिए एक नंबर दे, मैं अपने पुराने दोस्त GetInt कहते हैं,
और फिर इस नए सिंटैक्स हम सोमवार को पेश किया गया था.
'Newptr n> पते का अर्थ है कि आप malloc द्वारा दिए गए थे
जो एक नया नोड वस्तु की पहली बाइट का प्रतिनिधित्व करता है,
और फिर n क्षेत्र कहा जाता है.
एक छोटी मामूली बातों प्रश्न: यह क्या गुप्त कोड के अधिक लाइन के बराबर है?
और मैं यह कैसे लिखा जा सकता है? एक चाकू ले जाना चाहते हैं?
[छात्र जवाब, unintelligible]
अच्छा है. N का उपयोग करना है, लेकिन यह काफी के रूप में इस रूप में आसान नहीं है.
क्या मैं पहले की जरूरत के लिए करते हो? [छात्र जवाब, unintelligible]
अच्छा है. मैं * newptr.n करना की जरूरत है.
तो यह कह रहा है नया सूचक स्पष्ट रूप से पता है. क्यों?
क्योंकि यह malloc से लौट रहा था. * Newptr कह "वहाँ जाना है,"
और फिर एक बार तुम वहाँ हो, तो आप अधिक परिचित n का उपयोग कर सकते हैं,
लेकिन यह सिर्फ एक छोटे बदसूरत लग रहा है, खासकर अगर हम इंसानों के लिए जा रहे हैं
तीर के साथ हर समय संकेत आकर्षित, दुनिया इस तीर अंकन पर मानकीकृत है,
जो वास्तव में एक ही बात करता है.
अंकन> जब बाईं तरफ बात एक सूचक है - तो तुम ही उपयोग करें.
अन्यथा, अगर यह एक वास्तविक struct है, n. का उपयोग करें.
और फिर इस: मैं क्यों इनिशियलाइज़ newptr> अगले अशक्त करने के लिए?
हम चरण के अंत के एक झूलने बाएं हाथ बंद नहीं करना चाहती.
हम यह सीधे नीचे की ओर इशारा करते हुए करना चाहते हैं, जो इस सूची के अंत का मतलब
संभवतः इस नोड में हो सकता है, इसलिए हम बेहतर यकीन है कि यह रिक्त है.
और, सामान्य रूप में, अपने चर या अपने डेटा के सदस्यों और structs आरंभ
कुछ करने के लिए सिर्फ अच्छा अभ्यास है.
बस दे कचरा मौजूद हैं और आम तौर पर मौजूद रहेंगे आप मुसीबत में हो जाता है
अगर आप कुछ पर बाद में भूल जाते हैं.
>> यहाँ कुछ मामलों है. यह, फिर से, डालने समारोह है,
और पहली बात मैं के लिए की जाँच करें यदि चर पहले कहा,
कि वैश्विक चर नल है, इसका मतलब है कि वहाँ कोई लिंक सूची है.
हम किसी भी नंबर नहीं डाला है, तो यह तुच्छ है इस वर्तमान संख्या में डालने
सूची में, क्योंकि यह सिर्फ सूची के शुरू में है.
तो यह था जब Anita अभी तक था यहाँ अकेले खड़े, नाटक
यहाँ कोई और नहीं एक मंच पर जब तक हम एक नोड आवंटित किया गया था,
तो वह पहली बार के लिए उसके हाथ बढ़ा सकता है,
अगर हर कोई मंच पर आया था उसके बाद सोमवार को.
अब यहाँ है, यह एक छोटे से जांच जहां मैं कहना है अगर n के नए नोड के मूल्य
मौजूदा 1 नोड में n के मूल्य <
इसका मतलब है कि वहाँ एक लिंक सूची है कि शुरू कर दिया है.
सूची में कम से कम एक नोड है, लेकिन इस नए आदमी
अंतर्गत आता है पहले यह है, तो हम चीजों को चारों ओर ले जाने की जरूरत है.
दूसरे शब्दों में, यदि इस सूची में बस के साथ शुरू कर दिया है, चलो कहते हैं,
सिर्फ संख्या 17 है, कि - वास्तव में, हम यह अधिक स्पष्ट रूप से कर सकते हैं.
यदि हम यहाँ एक सूचक 1 कहा जाता है के साथ हमारी कहानी शुरू,
और शुरू में यह रिक्त है, और हम 9 नंबर डालने,
9 संख्या स्पष्ट रूप से सूची के शुरू में है.
तो चलो बहाना हम सिर्फ पता या संख्या 9 malloced और इसे यहाँ रखा है.
यदि 1 9 डिफ़ॉल्ट रूप से है, हम पर चर्चा की 1 परिदृश्य बस चलो बिंदु इस आदमी को यहाँ का मतलब है,
इस के रूप में रिक्त छोड़, अब हम संख्या 9 है.
अगले संख्या 17 है हम सम्मिलित करना चाहते हैं.
17 यहाँ अंतर्गत आता है, तो हम करने के लिए इस के माध्यम से कुछ तार्किक एक कदम के लिए जा रहे हैं.
तो बदले जाने से पहले हम करते हैं कि, चलो बहाना है कि हम 8 नंबर डालने चाहता था.
>> तो बस सुविधा के लिए, मैं यहाँ आकर्षित करने के लिए जा रहा हूँ.
लेकिन याद रखना, malloc यह सबसे कहीं भी रख सकते हैं.
लेकिन ड्राइंग खातिर के लिए, मैं इसे यहाँ डाल देता हूँ.
तो बहाना है मैं सिर्फ संख्या 8 के लिए एक नोड आवंटित है, यह डिफ़ॉल्ट रूप से रिक्त है.
अब क्या होता है? चीजों की एक जोड़ी.
हम मंच पर सोमवार को इस गलती जहां हम इस तरह एक सूचक को अद्यतन बनाया है,
तो यह किया है, और फिर हम ने दावा किया - हम इस मंच पर हर किसी अनाथ.
क्योंकि तुम can't यहाँ आपरेशनों के आदेश महत्वपूर्ण है,
क्योंकि अब हम इस नोड 9 कि सिर्फ अंतरिक्ष में तैर की तरह खो दिया है.
सोमवार को तो यह सही तरीका नहीं था.
हम पहले कुछ और करना है.
दुनिया की स्थिति इस तरह दिखता है. शुरू में, 8 आवंटित की गई है.
8 डालने का एक बेहतर तरीका क्या होगा?
1 इस सूचक को अद्यतन करने के बजाय, सिर्फ इस एक के बजाय अद्यतन करें.
तो हम कोड की एक पंक्ति है कि इस अशक्त चरित्र बारी करने के लिए जा रहा है की जरूरत है
में एक वास्तविक सूचक है कि 9 नोड पर इशारा कर रहा है,
और फिर हम सुरक्षित रूप से 1 को बदलने के लिए इस आदमी को यहाँ बात कर सकते हैं.
अब हम एक सूची है, दो तत्वों के एक लिंक सूची है.
और यह वास्तव में क्या करता है यहाँ की तरह लग रही हो?
यदि हम कोड को देखो, सूचना है कि मुझे लगता है कि वास्तव में किया है.
मैंने कहा है, newptr और इस कहानी में, newptr इस आदमी को इशारा कर रहा था.
>> तो मुझे एक और बात को आकर्षित करने के लिए, और मैं इस बात के लिए एक छोटे से अधिक कमरे में छोड़ दिया जाना चाहिए.
तो छोटे से ड्राइंग माफ कर दीजिए.
इस आदमी newptr कहा जाता है.
सिर्फ 25 से ऊपर है कि हम कुछ लाइनों लाइन में पहले घोषित चर है.
और यह 8 की ओर इशारा करते है. तो जब मैं newptr> अगले कहते हैं, इसका मतलब है कि struct करने के लिए जाना
कि newptr द्वारा किया जा रहा है पर बताया, तो यहाँ हम कर रहे हैं, वहाँ जाओ.
तब तीर कह रहा है अगले क्षेत्र पाने के लिए, और फिर = कह रहा है क्या मूल्य डाल वहाँ?
मूल्य है कि पहली बार में था, मूल्य 1 में क्या था?
पहले इस नोड पर इशारा कर रहा था, तो इसका मतलब है कि यह अब इस नोड पर बात करनी चाहिए.
दूसरे शब्दों में, क्या हालांकि मेरी लिखावट के साथ एक हास्यास्पद गड़बड़ लग रहा है,
बस के चारों ओर इन तीर हिल के एक साधारण विचार क्या है
सिर्फ इस एक लाइनर के साथ कोड के लिए अनुवाद.
स्टोर क्या अगले क्षेत्र में पहली बार में है और फिर अद्यतन 1 वास्तव में क्या है.
चलो इस में से कुछ के माध्यम से आगे और तेजी से आगे जाना है,
और इस पूंछ प्रविष्टि पर केवल अब के लिए देखो.
मान लीजिए कि मैं इस मुद्दे पर जहां मुझे लगता है कि कुछ नोड के अगले क्षेत्र रिक्त है करने के लिए.
और कहानी, एक विस्तार में इस बिंदु पर है कि मैं खत्म glossing रहा हूँ
यह है कि मैं एक और सूचक को पेश किया है 142 लाइन, पूर्ववर्ती सूचक में यहाँ.
मूलतः, कहानी में इस बिंदु पर, एक बार सूची लंबी हो जाता है,
मैं एक तरह से यह दो उंगलियों के साथ चलने की जरूरत है, क्योंकि अगर मैं बहुत दूर जाना है
एक एकल लंबाई सूची में याद है, तो आप पीछे की ओर नहीं जा सकते.
तो predptr के इस विचार मेरे बाएँ उंगली है, और newptr - newptr नहीं.
एक और सूचक है कि यहाँ मेरी अन्य उंगली है, और मैं बस सूची चलने की तरह कर रहा हूँ.
यही कारण है कि मौजूद है. लेकिन केवल एक सरल मामलों की विचार.
यदि कि सूचक अगले क्षेत्र रिक्त है, तार्किक निहितार्थ क्या है?
यदि आप इस सूची traversing कर रहे हैं और आप एक रिक्त सूचक मारा?
आप सूची के अंत में कर रहे हैं, और इसलिए कोड तो यह एक अतिरिक्त तत्व संलग्न करने के लिए
सहज ज्ञान युक्त की तरह कि नोड अगले जिसका सूचक रिक्त है ले जाएगा,
तो यह वर्तमान में रिक्त है, और इसे बदलने के लिए, हालांकि, नए नोड के पते.
तो हम सिर्फ कोड में तीर चित्रकारी कर रहे हैं कि हम किसी के बाएं हाथ को ऊपर उठाने के द्वारा मंच पर आकर्षित किया.
>> और मामला है कि मैं अब के लिए मेरे हाथ की लहर
, क्योंकि मुझे लगता है कि यह आसान है दफा हो जाओ जब हम यह पर्यावरण के इस प्रकार में
सूची के बीच में प्रविष्टि के लिए जाँच.
लेकिन बस intuitively, क्या होने की जरूरत है अगर आप यह पता लगाने चाहते हैं
जहां कुछ संख्या के बीच में आता है आप इसे चलना है
एक से अधिक उंगली के साथ, एक से अधिक सूचक,
तत्व बाहर आंकड़ा जहां यह की जाँच से संबंधित है <मौजूदा एक,
> वर्तमान एक है, और एक बार आप उस जगह मिल जाए,
तो आप खोल खेल के इस प्रकार कर सकते हैं जहाँ आप संकेत के आसपास बहुत सावधानी से कदम है.
और जवाब है कि, अगर आप इस के माध्यम से अपने दम पर घर पर कारण करने के लिए करना चाहते हैं,
बस कोड के इन दो लाइनों के लिए नीचे फोड़े, लेकिन उन पंक्तियों के आदेश सुपर महत्वपूर्ण है.
क्योंकि अगर आप किसी का हाथ छोड़ और बढ़ा किसी और गलत क्रम में है,
फिर, आप सूची orphaning अंत सकता है.
अधिक धारणात्मक संक्षेप में, पूंछ में प्रविष्टि अपेक्षाकृत सरल है.
सिर पर प्रविष्टि भी अपेक्षाकृत सरल है,
लेकिन आप के लिए एक अतिरिक्त सूचक इस समय अद्यतन करने की आवश्यकता
सूची में नंबर 5 यहाँ निचोड़
और फिर बीच में प्रविष्टि भी अधिक प्रयास शामिल है,
बहुत सावधानी से अपने सही स्थान में 20 नंबर डालने के लिए,
जो 17 और 22 के बीच है.
तो आप 22 के लिए नए नोड 20 बिंदु की तरह कुछ करने की जरूरत है,
और फिर, जो नोड सूचक पिछले अद्यतन की जरूरत है?
यह 17 है, वास्तव में इसे डालने.
तो फिर, मैं है कि विशेष रूप से लागू करने के लिए वास्तविक कोड स्थगित करेंगे.
>> पहली नज़र में, यह थोड़ा भारी है, लेकिन यह वास्तव में सिर्फ एक अनंत लूप
कि पाशन है, पाशन पाशन पाशन, और जैसे ही तोड़ने के रूप में आप नल सूचक मारा,
पर जो बात आप अपेक्षित प्रविष्टि कर सकते हैं.
यह है, फिर, प्रतिनिधि लिंक सूची प्रविष्टि कोड है.
यह एक बहुत की तरह था, और यह लगता है जैसे हम एक समस्या का हल है,
लेकिन हम एक दूसरे को पूरी एक शुरू की है. सच कहूँ तो, हम यह सब समय बिताया है
बड़ा हे और Ω और समय चल रहा है, समस्याओं को और अधिक तेजी से हल करने की कोशिश कर रहा है,
और यहाँ हम पीछे की ओर एक बड़ा कदम उठा रहे हैं, ऐसा लगता है.
और फिर भी, अगर लक्ष्य के लिए डेटा की दुकान है,
यह होली ग्रेल की तरह लगता है, जैसा कि हम सोमवार को कहा, वास्तव में होगा
चीजें तुरंत दुकान.
>> वास्तव में लगता है, कि हम डाल एक तरफ एक पल के लिए लिंक सूची
और हम बजाय एक मेज की धारणा की शुरुआत की.
और एक सरणी के रूप में एक पल के लिए जाने के लिए सिर्फ एक मेज के बारे में सोच.
इस सरणी और इस मामले यहाँ 26 कुछ तत्वों, 0 25 के माध्यम से है,
और लगता है कि आप नाम के लिए भंडारण की कुछ हिस्सा की जरूरत है:
एलिस और बॉब और चार्ली और इस तरह.
और आप कुछ डेटा संरचना की जरूरत है उन लोगों के नाम की दुकान है.
खैर, आप एक लिंक की गई सूची की तरह कुछ का उपयोग कर सकते हैं
और बॉब और बॉब के बाद चार्ली से पहले आप ऐलिस डालने सूची चलना और बहुत आगे है.
और, वास्तव में, यदि आप के रूप में एक अलग तरह है कि कोड को देखना चाहते हैं,
जानते हैं कि list2.h में, हम बिल्कुल नहीं.
हम इस कोड के माध्यम से जाना नहीं है, लेकिन यह पहला उदाहरण के एक संस्करण है
कि एक अन्य struct हम बुलाया छात्र पहले देखा है परिचय है,
तो और क्या यह वास्तव में लिंक्ड सूची में भंडार एक छात्र की संरचना करने के लिए एक सूचक है
बजाय एक साधारण सा पूर्णांक, n.
तो पता है वहाँ वहाँ कोड है कि वास्तविक तार शामिल है,
लेकिन अगर वास्तव में अब हाथ में लक्ष्य दक्षता समस्या का समाधान है,
यह अच्छा नहीं होगा अगर हम एक ऐलिस वस्तु बुलाया दिया हो,
हम उसे एक डेटा संरचना में सही स्थान में डाल करना चाहते हैं,
ऐसा लगता है जैसे यह वास्तव में अच्छा हो सकता है सिर्फ ऐलिस रखा था,
जिसका नाम पहले स्थान में एक साथ शुरू होता है.
और बॉब, जिसका नाम बी के साथ दूसरे स्थान में शुरू होता है.
एक सरणी के साथ करते हैं, या यह एक टेबल, उस पर एक हैश तालिका बुला शुरू,
हम बिल्कुल कर सकते हैं. अगर हम एलिस की तरह एक नाम दिया जाता है,
एलिस की तरह एक स्ट्रिंग, जहां आप A-L-i-c - ए रखा है?
हम एक hueristic की जरूरत है. हम एलिस की तरह कुछ इनपुट लेने के लिए एक समारोह की जरूरत
और, एक जवाब देते हैं, "इस स्थान पर ऐलिस रखो."
और इस समारोह में, इस काले बॉक्स, एक हैश समारोह बुलाया जा रहा है.
>> एक हैश समारोह कुछ है कि एक इनपुट लेता है, "ऐलिस" की तरह है,
और आप के लिए रिटर्न, आम तौर पर, कुछ डेटा संरचना में सांख्यिक स्थान जहां ऐलिस अंतर्गत आता है.
इस मामले में, हमारे हैश समारोह अपेक्षाकृत सरल होना चाहिए.
हमारे हैश समारोह का कहना है, यदि आप "ऐलिस" दिया जाता है, मैं जो चरित्र के बारे में ध्यान देना चाहिए?
पहले एक. तो मैं [0] को देखो, और फिर मैं कहता हूँ अगर [0] चरित्र है, 0 संख्या में वापसी.
अगर यह बी है, लौटने के 1. अगर यह सी, 2 लौटने के लिए, और बहुत आगे है.
सभी इंडेक्स 0, और जो मुझे एलिस और फिर बॉब और फिर चार्ली डालने के लिए अनुमति देते हैं और इतना आगे
इस डेटा संरचना में. लेकिन वहाँ एक समस्या है.
क्या अगर अनीता के साथ फिर से आता है?
हम कहाँ अनीता रखा है? उसका नाम, भी, एक पत्र के साथ शुरू होता है,
और ऐसा लगता है जैसे हम इस समस्या का एक बड़ा गड़बड़ कर दिया है.
हम अब एक डेटा संरचना में तत्काल प्रविष्टि, लगातार समय प्रविष्टि,
बदतर मामले बजाय रेखीय,
लेकिन क्या हम इस मामले में अनीता के साथ कर सकते हैं?
दो विकल्प वास्तव में क्या कर रहे हैं? हाँ?
[छात्र जवाब, unintelligible] ठीक है, तो हम एक और आयाम हो सकता है.
यह अच्छा है. तो हम चीजों को बनाने के बाहर 3 डी में कर सकते हैं जैसे हम के बारे में सोमवार को मौखिक रूप से बात की थी.
हम यहाँ एक और उपयोग जोड़ने के लिए, सकता है, लेकिन लगता है कि नहीं, मैं इस सरल रखने की कोशिश कर रहा हूँ.
पूरे यहाँ लक्ष्य के लिए लगातार समय तत्काल पहुँच है,
इतना है कि बहुत अधिक जटिलता जोड़ने से है.
क्या अन्य विकल्प हैं, जब यह आंकड़ा संरचना में अनीता प्रविष्ट करें की कोशिश कर रहे हैं? हाँ?
[छात्र जवाब, unintelligible] अच्छा है. तो हम हर किसी के नीचे स्थानांतरित कर सकता है,
बॉब और ऐलिस, नीचे चार्ली nudges और फिर जैसे हम अनीता डाल दिया, जहां वह वास्तव में होना चाहता है.
>> जाहिर है, अब, इस बात का एक पक्ष प्रभाव है.
इस डेटा संरचना शायद उपयोगी नहीं है क्योंकि हम के लिए लोगों को डालने के एक बार करना चाहते हैं
लेकिन क्योंकि हम जाँच करने के लिए यदि वे बाद में वहाँ हो चाहते हैं
अगर हम सभी डेटा संरचना में नाम मुद्रित करना चाहते हैं.
हम अंततः इस डेटा के साथ कुछ करने जा रहे हैं.
तो अब हम की तरह ऐलिस, जो अब नहीं है, जहां वह होना चाहिए पर दबाव डाला है.
न ही बॉब है, और न ही चार्ली है.
तो शायद इस तरह एक अच्छा विचार नहीं है.
लेकिन वास्तव में, यह एक विकल्प है. हम सभी को शिफ्ट करने के लिए नीचे कर सकता है,
या बिल्ली, अनीता खेल के लिए देर से आया, क्यों हम सिर्फ अनीता नहीं डाल कर
यहाँ नहीं, यहाँ नहीं, यहाँ नहीं, बस उसे सूची में एक छोटे से कम डाल.
लेकिन फिर इस समस्या को फिर से उतरना शुरू होता है.
आप ऐलिस खोजने के लिए सक्षम तुरन्त उसका पहला नाम के आधार पर हो सकता है,.
और तुरन्त बॉब, और चार्ली. लेकिन फिर आप अनीता के लिए देखो,
और आप देखते हैं, हम्म, ऐलिस के रास्ते में है.
खैर, मुझे ऐलिस नीचे जाँच. बॉब अनीता नहीं है.
चार्ली अनीता नहीं है. ओह, वहाँ अनीता है.
और अगर आप तर्क की कि ट्रेन सभी तरह जारी है,
सबसे ज्यादा मामले ढूँढने या इस नए डेटा संरचना में अनीता डालने का समय चल रहा है क्या है?
यह हे (एन), है ना?
क्योंकि सबसे ज्यादा मामले में, वहाँ ऐलिस, बॉब, चार्ली है. . .
"वाई" नाम किसी के लिए सभी तरह से नीचे है, तो वहाँ केवल एक ही जगह है छोड़ दिया है.
शुक्र है, हम कोई "Z" कहा जाता है, तो हम बहुत नीचे अनीता डाल.
>> हम सच है कि समस्या का हल नहीं है.
तो शायद हम इस तीसरे आयाम पेश करने की जरूरत नहीं है.
और यह पता चला है, अगर हम इस तीसरे आयाम परिचय,
हम यह पूरी तरह से नहीं करते हैं, कर सकते हैं, लेकिन होली ग्रेल हो रही हो जा रहा है
इतना है कि लगातार समय प्रविष्टि और गतिशील सम्मिलन
हम कड़ी मेहनत से कोड 26 आकार की एक सरणी के लिए नहीं है.
हम के रूप में कई नामों डालने के रूप में हम चाहते हैं कर सकते हैं, लेकिन हम हमारे यहाँ 5 मिनट का ब्रेक ले
और तो ठीक है कि नहीं.
सही सभी. मैं कहानी सेट अप सुंदर कृत्रिम
एलिस और बॉब और फिर तो चार्ली और फिर अनीता का चयन करके,
जिसका नाम जाहिर ऐलिस के साथ टकराने जा रहा था.
लेकिन सवाल के साथ हम सोमवार को समाप्त हो गया है बस कैसे यह संभावित है
कि आप इनमें से प्रकार collisions मिल जाएगा? दूसरे शब्दों में,
अगर हम इस सारणीबद्ध संरचना का उपयोग शुरू है, जो वास्तव में सिर्फ एक सरणी है,
26 स्थानों में से इस मामले में,
क्या अगर हमारे आदानों के बजाय समान रूप से वितरित कर रहे हैं?
यह कृत्रिम एलिस और बॉब और चार्ली और डेविड नहीं है और इसलिए आगे वर्णानुक्रम,
यह समान रूप से जेड के माध्यम से एक पर वितरित
>> शायद हम सिर्फ भाग्यशाली हो और हम दो एक या दो बी के लिए नहीं जा रहे हैं
बहुत अधिक संभावना के साथ के रूप में, लेकिन किसी ने कहा,
अगर हम सामान्यीकृत इस समस्या नहीं है और 0 से 25
लेकिन, कहते हैं, के माध्यम से 0 364 या 65, अक्सर एक ठेठ वर्ष में दिनों की संख्या,
, और सवाल पूछा, "संभावना है कि इस कमरे में हम दोनों एक ही जन्मदिन है क्या है?"
यह दूसरा रास्ता रखो, क्या संभावना है कि हम दोनों के एक साथ शुरू नाम है?
सवाल की तरह ही है, लेकिन यह पता स्थान
इस खोज को अंतरिक्ष, जन्मदिन के मामले में बड़ा है,
क्योंकि हम इतने सारे वर्णमाला के अक्षरों से अधिक वर्ष में दिनों है.
एक टक्कर की संभावना क्या है?
खैर, हम इस के बाहर गणित विपरीत रास्ता ढूँढ़ बारे में सोच सकते हैं.
क्या कोई टकराव की संभावना है?
खैर, यह अभिव्यक्ति का कहना है कि क्या संभावना है
अगर वहाँ सिर्फ इस कमरे में एक व्यक्ति, कि वे एक अद्वितीय जन्मदिन है?
यह 100% है. क्योंकि अगर कमरे में केवल एक ही व्यक्ति है,
उसके या उसके जन्मदिन के 365 दिनों के किसी भी वर्ष के बाहर हो सकता है.
तो 365/365 विकल्प मुझे 1 के एक मूल्य देता है.
तो पल में प्रश्न में संभावना सिर्फ 1 है.
लेकिन अगर वहाँ कमरे में एक दूसरे व्यक्ति है,
संभावना है कि उनके जन्मदिन अलग है क्या है?
364 केवल संभव दिनों, अनदेखा कर रहा है छलांग साल है,
उनके जन्मदिन के लिए टकराने के लिए अन्य लोगों के साथ नहीं है.
तो 364/365. यदि एक तीसरे व्यक्ति में आता है, यह 363/365 है, और बहुत आगे है.
तो हम एक साथ इन fractions गुणा रखना है, जो छोटे और छोटे हो रहे हैं,
पता लगाने की संभावना है कि हम सभी के अद्वितीय जन्मदिन है क्या है?
लेकिन फिर हम, निश्चित रूप से, बस कर सकते हैं कि जवाब लेने के लिए और इसे फ्लिप के आसपास
और 1 शून्य है कि सभी एक अभिव्यक्ति हम अंततः मिलेगा
अगर आप अपने गणित की पुस्तकों के पीछे याद है, यह इस तरह एक छोटे से कुछ लग रहा है,
जो और अधिक आसानी से रेखांकन में व्याख्या की है.
और यहाँ इस ग्राफिक एक्स अक्ष पर जन्मदिन की संख्या है,
या जन्मदिन के साथ लोगों को, और y अक्ष पर की संख्या एक मैच की संभावना है.
और यह कह रही है कि क्या यह है कि अगर आपके पास है, चलो कहते हैं, यहां तक ​​कि,
चलो 23 22 की तरह कुछ का चयन.
अगर कमरे में 22 या 23 लोगों को है,
संभावना है कि दो उन बहुत कम लोगों को ही जन्मदिन के लिए जा रहे हैं
वास्तव में सुपर उच्च है, combinatorially.
50% अंतर है कि सिर्फ 22 लोगों के लिए, एक संगोष्ठी, व्यावहारिक के एक वर्ग में,
उन लोगों में से 2 ही जन्मदिन के लिए जा रहे हैं.
क्योंकि वहाँ बहुत सारे तरीके हैं जिसमें आप एक ही जन्मदिन हो सकता है.
इससे भी बदतर है, अगर आप चार्ट के दाएँ हाथ की ओर देखो,
समय से आप यह में 58 छात्रों के साथ एक वर्ग है,
2 लोगों को एक जन्मदिन होने की संभावना सुपर, सुपर उच्च, लगभग 100% है.
अब, कि वास्तविक जीवन के बारे में एक मजेदार तथ्य की तरह है.
>> लेकिन निहितार्थ, अब डेटा संरचनाओं के लिए, और भंडारण जानकारी
मतलब है कि सिर्फ यह सोचते हैं आप एक अच्छी, साफ, डेटा का समान वितरण
और आप एक बड़ा पर्याप्त चीजों का एक गुच्छा फिट सरणी है
मतलब नहीं है कि आप अद्वितीय स्थानों में लोगों को ले जा रहे हैं.
आप collisions है करने के लिए जा रहे हैं. Hashing की इस धारणा तो, के रूप में यह कहा जाता है,
"ऐलिस" की तरह एक इनपुट ले और यह कुछ रास्ते में मालिश
और फिर वापस 0 या 1 या 2 की तरह एक जवाब हो रही है.
वापस कि समारोह से कुछ उत्पादन हो रही है टक्कर के इस संभावना से त्रस्त है.
तो हम कैसे उन collisions संभाल कर सकते हैं?
खैर, एक मामले पर हम विचार है कि सुझाव दिया गया था ले जा सकते हैं.
हम हर कोई बस शिफ्ट करने के लिए नीचे कर सकते हैं, या हो सकता है एक छोटे से अधिक बस,
बल्कि इस कदम हर किसी से, चलो बस उपलब्ध हाजिर के नीचे स्थानांतरित करने के लिए करने के लिए अनीता.
तो अगर ऐलिस 0 में है, बॉब 1 में, 2 में चार्ली है,
हम सिर्फ 3 स्थान पर अनीता डाल देता हूँ.
और इस डेटा संरचनाओं में एक रेखीय जांच कर रही तकनीक कहा जाता है.
रैखिक क्योंकि आप सिर्फ इस लाइन पर चल रहे हैं, और आप की जांच तरह कर रहे हैं
डेटा संरचना में उपलब्ध स्थानों के लिए.
बेशक, यह O (n) में devolves.
यदि डेटा संरचना वास्तव में पूर्ण है, इसमें 25 लोगों को पहले से ही है,
और तो अनीता के साथ आता है, वह क्या स्थान Z होगा समाप्त होता है, और वह ठीक है.
वह अभी भी फिट बैठता है, और हम उसे बाद में पता कर सकते हैं.
>> लेकिन यह बातें तेजी से ऊपर के लक्ष्य के विपरीत था.
तो क्या हुआ अगर हम बजाय यह तीसरा आयाम शुरू की?
तकनीक है कि आम तौर पर अलग श्रृंखलन कहा जाता है, या होने चेन.
और एक हैश तालिका अब क्या है, इस सारणीबद्ध संरचना,
अपनी मेज सिर्फ संकेत की एक सरणी है.
लेकिन क्या उन संकेत को इंगित करने के क्या अनुमान है?
एक लिंक सूची. तो क्या हुआ अगर हम इन दोनों को संसार का सबसे अच्छा ले लिया है?
हम प्रारंभिक indexes के लिए arrays का उपयोग
डेटा संरचना में तो हम तुरंत [0] [1], [30] या तो आगे जा सकते हैं,
लेकिन इतना है कि हम कुछ लचीलापन है और हम अनीता और एलिस और एडम फिट कर सकते हैं
और किसी भी अन्य एक नाम है,
हम बजाय अन्य धुरी मनमाने ढंग से हो जाना.
और हम अंत में सोमवार के रूप में, लिंक्ड सूची के साथ कि अर्थपूर्ण क्षमता है.
हम एक आंकड़ा संरचना मनमाने ढंग से विकसित कर सकते हैं.
वैकल्पिक रूप से, हम सिर्फ एक विशाल सरणी 2-dimensional कर सकता है,
लेकिन यह है कि एक भयानक स्थिति हो अगर जा रहा है एक 2 आयामी सरणी में पंक्तियों की
काफी बड़े अतिरिक्त व्यक्ति जिसका नाम ए के साथ शुरू होता है के लिए नहीं है
भगवान ना करे हम एक विशाल संरचना 2-dimensional reallocate
सिर्फ इसलिए कि वहाँ इतने सारे नाम पर लोगों को है,
खासकर जब वहाँ बहुत कुछ लोगों Z कुछ नाम है.
यह सिर्फ एक बहुत विरल डेटा संरचना होने जा रहा है.
तो यह किसी भी तरह से सही नहीं है, लेकिन अब हम कम से कम करने की क्षमता है
तुरन्त जहां ऐलिस या अनीता अंतर्गत आता है,
ऊर्ध्वाधर अक्ष के मामले में कम से कम,
और फिर हम सिर्फ तय करना है जहाँ अनीता या ऐलिस इस लिंक की गई सूची में डाल करने के लिए है.
अगर हम बातें छँटाई के बारे में परवाह नहीं है, कैसे जल्दी से हम इस तरह एक संरचना में ऐलिस डालने के सकता है?
यह लगातार समय है. हम [0] में सूचकांक, और अगर वहाँ कोई नहीं है,
ऐलिस कि लिंक की गई सूची के शुरू में चला जाता है.
लेकिन यह है कि एक बड़ा सौदा नहीं है. क्योंकि अगर अनीता फिर साथ आता है
कदम से कुछ नंबर बाद में, जहां अनीता हैं करता है?
खैर, [0]. OOP. ऐलिस कि लिंक सूची में पहले से ही है.
>> लेकिन अगर हम इन नामों छँटाई के बारे में परवाह नहीं है,
हम सिर्फ ऐलिस से अधिक है, डालने अनीता स्थानांतरित कर सकते हैं, लेकिन यह भी है कि लगातार समय है.
यहां तक ​​कि अगर वहाँ एलिस और एडम और इन सभी अन्य नामों एक है,
यह वास्तव में उन्हें शारीरिक रूप से नहीं जा रहा है. क्यों?
क्योंकि हम सिर्फ लिंक सूची है, कौन जानता है यहाँ इन नोड्स वैसे भी कर रहे थे?
सब तुम्हें क्या करना है है रोटी के टुकड़ों चाल.
चारों ओर तीर ले जाते हैं, आप शारीरिक रूप से किसी भी डेटा चारों ओर ले जाने के लिए नहीं है.
तो हम अनीता सम्मिलित करते हैं, तो उस मामले में तुरन्त. लगातार समय.
तो हम लगातार समय देखने, और अनीता की तरह किसी की लगातार समय प्रविष्टि है.
लेकिन दुनिया oversimplifying की तरह.
क्या होगा अगर हम बाद में ऐलिस खोजने के लिए करना चाहते हैं?
कितने कदम है कि करने के लिए ले जा रहा है?
[छात्र जवाब, unintelligible]
बिल्कुल सही. ऐलिस पहले लिंक की गई सूची में लोगों की संख्या.
तो यह काफी सही नहीं है, क्योंकि हमारे डेटा संरचना, फिर से, इस ऊर्ध्वाधर पहुँच गया है
और फिर इसे जुड़े इन फांसी सूची है - वास्तव में, यह एक सरणी एक आकर्षित नहीं करते हैं.
यह इन लिंक सूचियों में से एक है से लटका है कि इस तरह एक छोटे से कुछ दिखता है.
लेकिन समस्या यह है अगर एलिस और एडम और इन सभी अन्य एक नामों
वहाँ ऊपर और अधिक से अधिक समाप्त करने के लिए,
लग रहा है किसी को अंत कदम का एक गुच्छा ले जा सकता है,
bcause आप लिंक सूची पार है,
जो एक रेखीय ऑपरेशन है.
तो सच में, तो, प्रविष्टि समय अंततः हे (एन), जहाँ n सूची में तत्वों की संख्या है.
द्वारा विभाजित, मनमाने ढंग से यह मीटर है, जहां लिंक सूचियों की संख्या है फोन
कि हम इस ऊर्ध्वाधर अक्ष में है.
दूसरे शब्दों में, अगर हम वास्तव में नाम का एक समान वितरण मान,
पूरी तरह अवास्तविक. वहाँ स्पष्ट रूप से दूसरों की तुलना में कुछ पत्र के अधिक है.
>> लेकिन अगर हम एक पल के समान वितरण के लिए मान,
और हम कुल लोगों को, और मीटर के कुल जंजीरों n है
हमारे पास उपलब्ध है, तो इन जंजीरों में से प्रत्येक की लंबाई
काफी बस कुल n चेन की संख्या से विभाजित होने जा रहा है.
तो n / मीटर. लेकिन यहाँ है जहाँ हम सब गणितीय चालाक हो सकता है.
मीटर एक स्थिर है, क्योंकि इनमें से एक निश्चित संख्या है.
आप शुरुआत में अपने सरणी की घोषणा करने के लिए जा रहे हैं,
और हम ऊर्ध्वाधर अक्ष रीसाइज़िंग नहीं कर रहे हैं. परिभाषा के अनुसार, यह तय रहता है.
यह केवल क्षैतिज अक्ष है, तो बात है, कि बदल रहा है.
तो तकनीकी तौर पर, यह एक स्थिर है. अब तो, प्रविष्टि समय
बहुत ज्यादा हे (एन) है.
तो यह है कि कि सब बहुत अच्छा महसूस नहीं करता.
लेकिन सच क्या है? खैर, यह सब समय, सप्ताह के लिए,
हम कह रहा हूँ हे (एन ²). हे (एन), 2 x n ², n, 2 से विभाजित. . . ech.
यह सिर्फ n ² है. लेकिन अब, सेमेस्टर के इस भाग में,
हम वास्तविक दुनिया के बारे में फिर से बात शुरू कर सकते हैं.
और n / मीटर पूरी तरह से सिर्फ अकेले n की तुलना में तेजी है.
यदि आप एक हजार नाम है, और आप उन्हें कई बाल्टी में टूट
इतनी है कि आप इन जंजीरों में से प्रत्येक में केवल दस नाम है,
बिल्कुल दस बातें खोज करने के लिए एक हजार बातें की तुलना में तेजी से हो रहा है.
और इसलिए एक आगामी समस्या सेट के लिए आप को चुनौती देने के लिए जा रहा है
ठीक है कि के बारे में सोचते हैं हालांकि, हाँ,
asymptotically और गणितीय, यह अभी भी सिर्फ रेखीय,
जो सामान्य रूप में बेकार है जब चीजों को खोजने की कोशिश कर रहा है.
वास्तव में, यह है कि तेजी से होने जा रहा है
क्योंकि इस भाजक की.
और तो वहाँ फिर से इस व्यापार बंद होने जा रहा है
और सिद्धांत और वास्तविकता के बीच इस संघर्ष
और knobs के एक सेमेस्टर में इस बिंदु पर बदल शुरू कर देंगे
एक वास्तविकता के रूप में हम तरह के semster अंत के लिए तैयार है,
के रूप में हम वेब प्रोग्रामिंग की दुनिया शुरू,
वास्तव में, जहां, प्रदर्शन गिनती करने के लिए जा रहा है, क्योंकि अपने उपयोगकर्ताओं के लिए जा रहे हैं
शुरू करने के लिए लग रहा है और गरीब डिजाइन के फैसले की सराहना करते हैं.
>> तो कैसे आप एक लिंक्ड को लागू करने के बारे में जाना है - 31 तत्वों के साथ एक हैश तालिका?
और पिछले उदाहरण के जन्मदिन के बारे में मनमाने ढंग से किया गया था.
अगर किसी को 1 जनवरी या 1 फरवरी के एक जन्मदिन है, हम उन्हें इस बाल्टी में डाल देता हूँ.
यदि यह 2 जनवरी, 2 फरवरी, 2 मार्च है, हम उन्हें इस बाल्टी में डाल देता हूँ.
यही कारण है कि यह 31 था. आप कैसे एक हैश तालिका घोषणा करते हैं?
यह बहुत आसान हो सकता है, नोड * मेज इसके लिए मनमाने ढंग से नाम, [31] है.
यह मुझे देता नोड्स 31 संकेत,
और कहा कि मुझे लिंक सूचियों के लिए 31 संकेत है करने के लिए अनुमति देता है
यहां तक ​​कि अगर उन जंजीरों शुरू रिक्त हैं.
क्या मैं डाल करना चाहते हैं कि अगर मैं स्टोर करने के लिए करना चाहते हैं "," बॉब "चार्ली" "एलिस,"?
खैर, हम एक संरचना में उन चीजों को समाहित करने की आवश्यकता है
क्योंकि हम ऐलिस बॉब के लिए बात करने के लिए चार्ली को इंगित करने के लिए, और बहुत आगे है.
हम सिर्फ नाम अकेले नहीं हो सकता है, तो मैं एक नया नोड यहाँ बुलाया संरचना बना सकते हैं.
>> एक वास्तविक नोड क्या है? इस नए लिंक की गई सूची में एक नोड क्या है?
पहली बात, शब्द कहा जाता है, व्यक्ति के नाम के लिए है.
लंबाई, शायद, एक मानव के नाम की अधिकतम लंबाई से संबंधित है,
जो कुछ भी है, 20, 30, पागल कोने मामलों में 40 अक्षर
और एक के लिए क्या है? यह सिर्फ अतिरिक्त रिक्त चरित्र, \ 0 है.
तो इस नोड खुद के अंदर "कुछ" लपेटकर है,
लेकिन यह भी एक अगले बुलाया सूचक वाणी
इसलिए हम बॉब ऐलिस चार्ली चेन और इतना आगे कर सकते हैं कि.
रिक्त हो सकता है लेकिन करता है के लिए होना जरूरी नहीं है.
इन हैश तालिका पर कोई सवाल? हाँ?
[छात्र सवाल पूछ रही है, unintelligible] एक सरणी - अच्छा सवाल है.
एक के बजाय सिर्फ चार * सरणी में इस चार शब्द क्यों है?
यह कुछ हद तक मनमाना उदाहरण में, मैं करने के लिए सहारा नहीं करना चाहता था
मूल नाम में से प्रत्येक के लिए malloc.
मैं स्ट्रिंग के लिए स्मृति की अधिकतम राशि की घोषणा करना चाहता था
इतना है कि मैं संरचना में कॉपी ऐलिस \ 0 और नहीं malloc और मुक्त और इस तरह के साथ सौदा हो सकता है.
लेकिन मुझे लगता है कि अगर मैं अंतरिक्ष उपयोग के प्रति जागरूक होना चाहता था सकता है. अच्छा सवाल है.
तो चलो इस से दूर सामान्यीकरण की कोशिश
और डेटा संरचनाओं पर आज के शेष आम तौर पर और अधिक ध्यान केंद्रित
और अन्य समस्या है कि हम एक ही बुनियादी बातों का उपयोग कर हल कर सकते हैं
हालांकि डेटा संरचनाओं खुद अपने ब्यौरे में अलग हो सकता है.
>> तो यह कंप्यूटर विज्ञान में बदल जाता है, पेड़ बहुत आम हैं.
और तुम एक परिवार के पेड़ की तरह एक पेड़ की तरह के बारे में सोच सकते हैं,
जहां कुछ जड़ें, कुछ matriarch या कुलपति है,
दादी या दादा या वापस पहले,
जो नीचे माँ और पिताजी या विभिन्न भाई बहन या पसंद कर रहे हैं.
तो एक वृक्ष संरचना नोड्स है और यह बच्चों की है,
आमतौर पर प्रत्येक नोड के लिए 0 या अधिक बच्चों.
और शब्दजाल में से कुछ है कि आप यहाँ इस चित्र में देख
किनारों पर छोटे बच्चों या पोते के किसी भी
जो कोई तीर उन से निकलती है,
उन तथाकथित, पत्तियों और अंदर पर किसी को भी कर रहे हैं
एक आंतरिक नोड है, आप इसे उन पंक्तियों के साथ कुछ भी कॉल कर सकते हैं.
लेकिन इस संरचना बहुत आम है. यह एक एक छोटे से मनमाना है.
हम बाईं तरफ एक बच्चा है, हम सही पर तीन बच्चे हैं,
तल पर दो बच्चों को छोड़ दिया.
तो हम अलग आकार के पेड़ है, के रूप में अच्छी तरह से कर सकते हैं लेकिन अगर हम चीजों को प्रमाण के अनुसार करना शुरू,
और आप एक पिछले कम से द्विआधारी खोज पर पैट्रिक वीडियो से यह याद हो सकता है
ऑनलाइन, द्विआधारी खोज के लिए एक सरणी के साथ लागू होना जरूरी नहीं है
ब्लैकबोर्ड पर या कागज के टुकड़े.
मान लीजिए कि आप एक और अधिक परिष्कृत डेटा संरचना में अपने नंबर स्टोर करना चाहता था.
आप इस तरह एक पेड़ बना सकते हैं.
आप एक सी में घोषित नोड है, और हो सकता है कि नोड के अंदर कम से कम दो तत्व हो सकता है.
एक नंबर पर आप स्टोर करने के लिए करना चाहते हैं, और अन्य है - ठीक है, हम एक और अधिक की आवश्यकता है.
अन्य अपने बच्चों को है.
तो यहाँ एक और आंकड़ा संरचना है. इस समय, एक नोड एक संख्या के संचय के रूप में परिभाषित किया गया है n
और फिर दो संकेत, बाईं बच्चे और सही बच्चे.
और वे मनमाने ढंग से नहीं कर रहे हैं. इस पेड़ के बारे में दिलचस्प बात क्या है?
>> हम कैसे करते हैं यह रखी है बाहर या कैसे पैट्रिक उसके वीडियो में बाहर रखी पैटर्न क्या है?
यह किस तरह का है स्पष्ट है कि वहाँ कुछ छँटाई यहाँ पर जा रहा है,
लेकिन सरल नियम क्या है? हाँ?
[छात्र जवाब, unintelligible]
बिल्कुल सही. यदि आप इस पर नज़र, आप बाईं तरफ छोटी संख्या देखते हैं,
बाईं तरफ बड़ी संख्या है, लेकिन यह है कि प्रत्येक नोड के लिए सच है.
प्रत्येक नोड के लिए, अपनी बाईं बच्चे की तुलना में यह कम है, और इसकी सही बच्चे की तुलना में यह अधिक है.
अब यह क्या मतलब है अगर मैं, कहते हैं, 44 नंबर के लिए यह आंकड़ा संरचना की खोज करना चाहते हैं,
मैं रूट पर शुरू करने के रूप में, क्योंकि अब ये अधिक जटिल डेटा संरचनाओं के सभी के साथ है,
हम केवल एक ही बात करने के लिए एक सूचक है, शुरुआत.
और इस मामले में, शुरुआत जड़ है. यह बाएं अंत नहीं है,
यह इस संरचना की जड़ है. तो मैं देख रहा हूँ यहाँ 55 है, और मैं 44 के लिए देख रहा हूँ.
मैं किस दिशा जाना चाहते हो?
ठीक है, मैं करने के लिए छोड़ दिया करने के लिए जाना चाहते हैं, क्योंकि जाहिर है, सही करने के लिए बहुत बड़ा होने जा रहा है.
तो यहाँ नोटिस, तो आप धारणात्मक आधे में पेड़ काट की तरह कर रहे हैं
क्योंकि आप नीचे दाएँ हाथ की ओर करने के लिए कभी नहीं जा रहे हैं.
तो अब मैं 55 से 33 करने के लिए जाना. यह एक संख्या का बहुत छोटा है.
मैं 44 के लिए देख रहा हूँ, लेकिन अब मैं जानता हूँ कि अगर इस पेड़ में 44 है, मैं स्पष्ट रूप से सही करने के लिए जा सकते हैं.
तो फिर, मैं आधे में पेड़ pruning हूँ.
यह बहुत ज्यादा फोन की किताब धारणात्मक समान है.
यह करने के लिए समान है हम क्या ब्लैकबोर्ड पर कागजात के साथ किया था,
लेकिन यह एक और अधिक परिष्कृत संरचना है कि हमें वास्तव में करने की अनुमति देता है
इस विभाजन और एल्गोरिथ्म के डिजाइन को जीत के,
और वास्तव में, इस तरह एक संरचना traversing - वूप्स.
इस तरह एक संरचना Traversing, जहां यह केवल "इस तरह से जाना या उस रास्ते पर चलना है,"
कि सभी कोड का मतलब है कि पहली बार में तुला अपने मन जब यह अनुभाग में लागू
या के माध्यम से इसे घर पर चलने, द्विआधारी खोज के लिए, या चलना recursion का उपयोग,
यह गर्दन में दर्द है. बीच तत्व का पता लगाएं, तो अपने गोलाई या नीचे.
>> वहाँ इस के लिए एक सौंदर्य है क्योंकि अब हम recursion फिर से उपयोग कर सकते हैं,
लेकिन बहुत अधिक सफाई. दरअसल, अगर आप 55 नंबर पर कर रहे हैं और आप के लिए 44 करना चाहते हैं,
आप इस मामले में छोड़ दिया जाना है, तो आप क्या करते हैं? आप सटीक एक ही एल्गोरिथ्म चलाते हैं.
आप नोड के मूल्य की जाँच करें, तो आप छोड़ दिया है या सही जाना.
तो फिर तुम नोड के मूल्य की जाँच करने के लिए, जाना छोड़ दिया है या सही.
यह पूरी तरह से recursion के लिए अनुकूल है.
तो भले ही अतीत में हम काफी कुछ मनमाना उदाहरण recursion शामिल किया है
कि पुनरावर्ती डेटा stuctures साथ जरूरत नहीं थी,
विशेष रूप से पेड़, यह एक समस्या लेने के इस विचार का एक आदर्श आवेदन है,
यह सिकुड़ते, और तब के एक ही प्रकार है, लेकिन छोटे कार्यक्रम, को हल.
>> तो वहाँ एक डेटा संरचना है कि हम लागू कर सकते हैं.
यह एक पहले गुप्त देखना नज़र में बनाया गया है, लेकिन यह एक आश्चर्यजनक है.
तो यह एक डेटा संरचना एक trie, trie, जो शब्द पुनर्प्राप्ति से विरासत में मिली है बुलाया है,
जो फिर से कोशिश वैल स्पष्ट नहीं है, लेकिन है कि दुनिया क्या इन बातों को कहते हैं. कोशिश करता है. T-r-i-ए.
यह किसी प्रकार की एक वृक्ष संरचना है, लेकिन एक trie में नोड्स के प्रत्येक
क्या होना प्रतीत होता है? और यह एक भ्रामक सा है क्योंकि यह संक्षिप्त की तरह है.
लेकिन ऐसा लगता है इस trie में प्रत्येक नोड वास्तव में एक सरणी है.
और भले ही इस चित्र के लेखक यह नहीं दिखाया गया है,
इस मामले में, इस trie एक डेटा संरचना है जिसका उद्देश्य जीवन में करने के लिए शब्दों की दुकान है
A-L-i-c - ए या बी ओ ख की तरह.
और जिस तरह इस डेटा स्टोर एलिस और बॉब और चार्ली और अनीता और इतना आगे
यह एक सरणी का उपयोग करता है जिससे एक trie में ऐलिस स्टोर,
हम रूट नोड में जो एक सरणी की तरह लग रहा है शुरू,
और यह आशुलिपि संकेतन में लिखा गया है.
लेखक abcdefg छोड़े गए क्योंकि वहाँ उस के साथ कोई नाम नहीं थे.
वे केवल एम और पी टी से पता चला है, लेकिन इस मामले में,
चलो कुछ नाम है कि यहाँ हैं एलिस और बॉब और चार्ली से दूर ले जाने के.
मैक्सवेल ने इस चित्र में वास्तव में है.
तो कैसे लेखक दुकान M-x-डब्ल्यू ई - एल एल?
वह या वह रूट नोड में शुरू कर दिया है, और चला गया [एम], तो लगभग 13, सरणी में 13 वें स्थान.
वहाँ से फिर, वहाँ एक सूचक है.
सूचक एक सरणी के लिए अग्रणी.
वहाँ से लेखक एक स्थान पर उस सरणी में अनुक्रमित, के रूप में ऊपर छोड़ दिया पर वहाँ दर्शाया,
और फिर वह या वह एक सरणी कि सूचक के बाद,
और स्थान एक्स में सूचक के लिए चला गया
फिर अगले सरणी स्थान डब्ल्यू, ई, एल, एल, और बहुत आगे है,
और अंत में, हम वास्तव में इस के लिए एक तस्वीर डाल की कोशिश.
कोड में की तरह एक नोड देखो क्या होता है?
एक trie में एक नोड अधिक नोड्स के लिए संकेत की एक सरणी शामिल हैं.
लेकिन वहाँ भी बूलियन मान के कुछ प्रकार इस कार्यान्वयन में कम से कम हो गया है.
मैं यह is_word फोन करने के लिए होता है. क्यों?
क्योंकि जब आप मैक्सवेल डालने रहे हैं, तो आप नहीं डालने रहे हैं
इस डेटा संरचना में कुछ भी.
आप एम. नहीं लिख आप एक्स नहीं लिख रहे हैं कर रहे हैं
आप सब कर रहे हैं संकेत के बाद है.
सूचक है कि एम, तो सूचक है कि एक का प्रतिनिधित्व करता है का प्रतिनिधित्व करता है,
तो सूचक है कि एक्स, तो डब्ल्यू, ई, एल, एल का प्रतिनिधित्व करता है,
लेकिन क्या तुम अंत में करने की जरूरत है जाना है, की जांच तरह है, मैं इस स्थान पर पहुंच गया.
एक शब्द है जो डेटा संरचना में यहाँ समाप्त होता था.
>> तो क्या वास्तव में एक trie साथ भरा है और लेखक का प्रतिनिधित्व करने के लिए चुना
छोटे त्रिकोण के साथ इन terminuses.
यह बस का अर्थ है कि वास्तव में इस त्रिकोण यहाँ है, सच के इस बूलियन मान
मतलब है कि अगर आप पेड़ में पीछे की ओर जाना है,
कि मैक्सवेल इस में नाम है शब्द का मतलब है.
लेकिन शब्द foo, उदाहरण के लिए,
पेड़ में नहीं है, क्योंकि अगर मैं रूट नोड में शीर्ष पर यहाँ शुरू,
वहाँ कोई च सूचक, नहीं ओ सूचक, नहीं ओ सूचक है. फू इस शब्दकोश में एक नाम नहीं है.
लेकिन इसके विपरीत, ट्यूरिंग, टी U-r-i-N-जी. फिर, मैं टी या यू या r या मैं या n या जी की दुकान नहीं था.
लेकिन मैं इस डेटा संरचना में दुकान नीचे इस नोड में यहाँ सही रास्ते से एक मूल्य - पेड़ में
सच is_word के इस बूलियन मान सेटिंग के द्वारा.
तो एक trie यह बहुत दिलचस्प मेटा संरचना की तरह है,
जहाँ आप वास्तव में शब्द नहीं स्वयं भंडारण कर रहे हैं शब्दकोश के इस प्रकार के लिए.
स्पष्ट है, आप सिर्फ हाँ या नहीं भंडारण कर रहे हैं, एक शब्द है जो यहाँ समाप्त होता है.
>> अब निहितार्थ क्या है?
यदि आप एक शब्दकोश में 150.000 शब्दों है कि आप के लिए स्मृति में संग्रहीत करने के लिए कोशिश कर रहे हैं
एक लिंक की गई सूची की तरह कुछ का उपयोग कर,
आप अपने लिंक की गई सूची में 150.000 नोड्स के लिए जा रहे हैं.
उन शब्दों की एक और वर्णानुक्रम खोज हे समय (एन) ले सकता है.
रैखिक समय. लेकिन यहाँ एक trie के मामले में,
एक शब्द को खोजने का समय चल रहा है क्या है?
यह पता सुंदरता बदल जाता है यहाँ यह है कि अगर आप पहले से ही इस शब्दकोश में 149,999 शब्द हैं,
के रूप में इस डेटा संरचना के साथ लागू किया,
इसे खोजने के लिए या एक और व्यक्ति सम्मिलित कि में ऐलिस एलिस की तरह करने में कितना समय ले करता है?
खैर, यह केवल 5 है, शायद अनुगामी चरित्र के लिए 6 चरणों में से एक है.
क्योंकि संरचना में अन्य नामों की उपस्थिति
ऐलिस डालने के रास्ते में नहीं मिलता है.
इसके अलावा, ऐलिस खोजने के एक बार वहाँ इस शब्दकोश में 150,000 शब्द हैं
सब पर मिल ऐलिस ढूँढने के लिए अपने रास्ते में नहीं है,
क्योंकि ऐलिस है. . . . . यहाँ है, क्योंकि मैं एक बूलियन मान पाया.
और अगर वहाँ कोई बूलियन सच है, तो ऐलिस है शब्दों के इस डेटा संरचना में नहीं है.
दूसरे शब्दों में, चीजों को खोजने और इस नए डालने में बातें की समय चल रहा है
trie का आंकड़ा संरचना की हे - यह n नहीं है.
क्योंकि 150.000 लोगों की उपस्थिति ऐलिस पर कोई प्रभाव नहीं है, ऐसा लगता है.
इसलिए हम इसे कश्मीर, जहां कश्मीर में अंग्रेजी का एक शब्द की अधिकतम लंबाई है फोन
जो आम तौर पर अधिक नहीं वर्ण 20-कुछ से.
तो कश्मीर एक स्थिर है. होली ग्रेल तो हम अब मिल गया है लगता है
एक trie, आवेषण के लिए लगातार समय के विलोपन के लिए lookups के लिए, है.
क्योंकि संरचना में पहले से ही चीजों की संख्या,
जो भी शारीरिक रूप से वहाँ नहीं कर रहे हैं. फिर, वे बस की तरह से बंद की जाँच कर रहे हैं, हाँ या नहीं,
उसके भविष्य के समय चल रहा है पर कोई प्रभाव पड़ता है.
>> लेकिन वहाँ एक पकड़ हो गया है, अन्यथा हम इतना समय नहीं बर्बाद होगा
इन सभी अन्य डेटा संरचनाओं पर सिर्फ अंत में गुप्त एक है कि आश्चर्यजनक है पाने के लिए.
तो क्या कीमत हम यहाँ इस महानता को प्राप्त करने के लिए भुगतान कर रहे हैं? अंतरिक्ष.
इस बात को बड़े पैमाने पर है. और कारण यह है कि लेखक
यहाँ वर्तमान में यह सूचना नहीं है, कि इन बातों है कि arrays की तरह देखो,
वह पेड़, trie के बाकी के बाकी आकर्षित नहीं किया,
क्योंकि वे सिर्फ कहानी के लिए प्रासंगिक नहीं कर रहे हैं.
लेकिन इन नोड्स के सभी सुपर विस्तृत कर रहे हैं, और पेड़ में प्रत्येक नोड लेता है
26 या वास्तव में, 27 वर्ण, क्योंकि इस मामले में मैं अक्षर लोप या सम्बन्ध का चिह्न के लिए अंतरिक्ष सहित था हो सकता है
इतना है कि हम apostrophized शब्द हो सकता है.
इस मामले में, इन व्यापक arrays रहे हैं. तो भले ही वे नहीं picutured रहे हैं,
इस राम का एक विशाल राशि लेता है.
जो ठीक हो सकता है, आधुनिक हार्डवेयर में especilly सकता है,
लेकिन कि tradeoff है. हम और अधिक स्थान खर्च करके कम समय मिलता है.
कहाँ है यह सब हो रहा है?
खैर, चलो यहाँ देखते हैं.
इस आदमी को यहाँ एक कूद कर चलो.
>> मानो या न मानो, रूप में बहुत मज़ा के रूप में सी कुछ समय के लिए किया गया है अब,
हम सेमेस्टर जहां यह अधिक आधुनिक चीजों के लिए संक्रमण के लिए समय में बिंदु तक पहुंच रहे हैं.
एक उच्च स्तर पर हालात. और भी अगले कुछ हफ्तों के लिए हालांकि
हम अभी भी अपने आप को संकेत और स्मृति प्रबंधन की दुनिया में विसर्जित करने के लिए जारी होगा
करने के लिए कि आराम है जिसके साथ हम फिर पर निर्माण कर सकते हैं,
खेल के अंत अंततः है शुरू, विडंबना यह है कि इस भाषा को नहीं.
हम, 10 मिनट की तरह HTML के बारे में बात कर खर्च करते हैं.
सभी HTML है एक मार्कअप भाषा है, और एक मार्कअप भाषा क्या है
खुले कोष्ठक और बंद कोष्ठक का कहना है कि 'इस साहसिक' के इन श्रृंखला
'बनाने के लिए इस तिर्छा' इस केंद्रित कर सकते हैं. '
यह सब है कि बौद्धिक दिलचस्प नहीं है, लेकिन यह उपयोगी सुपर है.
और यह निश्चित रूप से इन दिनों सर्वव्यापी.
लेकिन क्या शक्तिशाली HTML की दुनिया के बारे में है, और वेब प्रोग्रामिंग अधिक आम तौर पर,
गतिशील बातें निर्माण PHP या अजगर या रूबी या जावा या सी # जैसी भाषाओं में कोड लिखने.
वास्तव में, जो कुछ भी अपनी पसंद की भाषा है, और HTML गतिशील पैदा.
सृजन सीएसएस कुछ गतिशील बुलाया.
कासकेडिंग स्टाइल शीट, जो सौंदर्यशास्त्र के बारे में भी है.
और इसलिए आज भले ही, अगर मैं परिचित Google.com जैसे कुछ वेबसाइट के लिए जाना है,
और मैं देखने के लिए, डेवलपर, देखने के स्रोत है, जो शायद आप पहले किया है जाना,
लेकिन स्रोत को देखने के लिए जा रहा है, यह सब शायद बहुत गुप्त लग रहा है.
लेकिन यह अंतर्निहित कोड है कि Google.com लागू करता है.
सामने के छोर पर. और वास्तव में यह सब शराबी सौंदर्यशास्त्र के सामान है.
इस सीएसएस यहाँ है. अगर मैं स्क्रॉल नीचे रखने के लिए हम कुछ रंग कोडित सामान मिल जाएगा.
यह HTML है. गूगल कोड एक गड़बड़ की तरह दिखता है, लेकिन अगर मैं वास्तव में एक अलग विंडो खोलने,
हम यह करने के लिए कुछ संरचना देख सकते हैं.
अगर मैं इस खोलते हैं, तो यहाँ नोटिस, यह थोड़ा और अधिक पठनीय है.
हम लंबे समय से पहले इस टैग को देखने के लिए जा रहे हैं, शब्द [] एक टैग है,
HTML, सिर, शरीर, div, स्क्रिप्ट, पाठ क्षेत्र, काल, केन्द्रित div.
और यह भी पहली नज़र में गुप्त दिखने की तरह,
लेकिन सभी इस झंझट से निश्चित पैटर्न, और repeatable पैटर्न इस प्रकार है,
इतना है कि एक बार हम मूल बातें नीचे उतरो, आप इस तरह कोड लिखने में सक्षम हो जाएगा
और फिर अभी तक कोई अन्य भाषा को है, जावास्क्रिप्ट कहा जाता है का उपयोग करते हुए इस तरह कोड में हेरफेर.
और जावास्क्रिप्ट एक ब्राउज़र की एक भाषा है कि अंदर चलाता है
ने आज कहा कि हम पाठ्यक्रम खरीदारी उपकरण है कि गूगल के नक्शे का उपयोग करता है के लिए हार्वर्ड पाठ्यक्रमों पर, उपयोग
आप गतिशीलता की एक पूरी गुच्छा दे, Facebook आपको देता है के लिए त्वरित स्थिति अद्यतन दिखाने,
चहचहाना का उपयोग करने के लिए आप tweets तुरन्त दिखा.
इस सब के सब हम खुद को विसर्जित कर देते हैं अंदर शुरू हो जाएगा.
लेकिन वहाँ पाने के लिए, हम इंटरनेट के बारे में एक छोटे से कुछ समझने की जरूरत है.
यहाँ यह क्लिप सिर्फ एक लंबे मिनट है, और चलो मान के लिए अब यह है, वास्तव में,
कैसे इंटरनेट क्या है बारे में आने के लिए एक नमूना के रूप में काम करता है. मैं तुम्हें दे "शुद्ध के योद्धाओं."
>> [♫ धीरे कोरस संगीत ♫]
[पुरुष बयान] वह एक संदेश के साथ आया था.
एक सब अपने ही प्रोटोकॉल के साथ.
[♫ तेज़ इलेक्ट्रॉनिक संगीत ♫]
वह शांत फायरवॉल की एक दुनिया के लिए आया था, routers uncaring,
और अभी तक मौत से भी बदतर खतरों.
वह तेजी से है. वह मजबूत है. वह टीसीपी / आईपी है, और वह अपना पता मिल गया है.
नेट के योद्धाओं.
[Malan] अगले हफ्ते, तो. इंटरनेट. वेब प्रोग्रामिंग. यह CS50 है.
[CS50.TV]