[Powered by Google Translate] [धारा 6: कम आरामदायक]
[नैट Hardison] [हार्वर्ड विश्वविद्यालय]
[यह CS50 है.] [CS50.TV]
सही सभी. धारा 6 के लिए आपका स्वागत है.
इस हफ्ते, हम अनुभाग में डेटा संरचना के बारे में बात कर रही हो जा रहे हैं,
इसका मुख्य कारण इस सप्ताह के समस्या spellr पर सेट
अलग डेटा संरचना अन्वेषण की एक पूरी गुच्छा करता है.
वहाँ विभिन्न तरीकों से आप समस्या सेट के साथ जा सकते हैं की एक गुच्छा रहे हैं,
और अधिक डेटा संरचनाओं आप के बारे में पता है, अधिक ठंडी चीजें आप कर सकते हैं.
>> तो चलो शुरू हो. पहले हम ढेर के बारे में बात करने जा रहे हैं,
ढेर और कतार डेटा संरचना है कि हम के बारे में बात करने जा रहे हैं.
ढेर और कतार वास्तव में सहायक होते हैं जब हम रेखांकन के बारे में बात कर शुरू,
जो हम अब इतना सही की करने के लिए नहीं जा रहे हैं.
लेकिन वे वास्तव में एक बड़ा सीएस के मौलिक डेटा संरचनाओं की समझ के लिए अच्छा कर रहे हैं.
समस्या सेट विनिर्देश में वर्णन,
अगर आप इसे हटा सदृश करने के लिए के रूप में, पोट के बारे में वार्ता
भोजन ट्रे के ढेर है कि आप डाइनिंग हॉल में कैफेटेरिया में
जहां जब भोजन स्टाफ आता है और खाने की ट्रे डालता है के बाद वे उन्हें साफ कर दिया है,
वे उन्हें एक दूसरे के शीर्ष पर हो चुकी है.
और फिर जब बच्चों को भोजन प्राप्त करने में आते हैं,
वे ट्रे पुल से दूर, एक शीर्ष 1, तो यह नीचे एक है, तो है कि नीचे एक.
तो, प्रभाव में, 1 ट्रे कि भोजन स्टाफ नीचे डाल पिछले एक है कि दूर ले जाया जाता है.
पिछले एक है कि खाने के कर्मचारियों पर डाल दिया 1 एक है कि रात के खाने के लिए ले जाया जाता है.
समस्या सेट की कल्पना में है, जो आप डाउनलोड कर सकते हैं अगर आप पहले से ही नहीं है,
हम एक ढेर डेटा संरचना का उपयोग करते हुए इस तरह के struct मॉडलिंग के बारे में बात करते हैं.
>> तो क्या हम यहाँ मिल गया है, यह क्या व्याख्यान में प्रस्तुत किया गया था के लिए इसी तरह की है,
व्याख्यान में छोड़कर हम ints के रूप में चार * विरोध के साथ प्रस्तुत किया.
यह एक ढेर है कि स्टोर क्या होने जा रहा है?
डेनियल? क्या हम इस ढेर में भंडारण कर रहे हैं?
[डैनियल] स्ट्रिंग्स? >> हम इस ढेर में तार भंडारण कर रहे हैं वास्तव में,.
आप सभी की जरूरत है क्रम में एक ढेर बनाने के एक सरणी है
एक विशेष क्षमता का है, जो इस मामले में,
क्षमता सभी टोपियां में हो सकता है क्योंकि यह एक निरंतर की जा रही है.
और फिर सरणी के अलावा, हम सब ट्रैक करने की आवश्यकता है सरणी के मौजूदा आकार है.
एक बात यहाँ ध्यान दें कि शांत की तरह है
यह है कि हम एक और आंकड़ा संरचना, सरणी के शीर्ष पर खड़ी डेटा संरचना का निर्माण कर रहे हैं.
वहाँ ढेर को लागू करने के लिए अलग अलग तरीके हैं.
हम इसे काफी अभी तक नहीं, लेकिन उम्मीद है कि लिंक्ड सूची समस्याओं को करने के बाद क्या करेंगे,
आप देखेंगे कि कैसे आप आसानी से एक लिंक सूची के शीर्ष पर एक ढेर के रूप में अच्छी तरह से लागू कर सकते हैं.
लेकिन अब के लिए, हम arrays के लिए रहना होगा.
तो फिर, हम सभी की जरूरत है एक सरणी है और हम सिर्फ सरणी के आकार को ट्रैक करने के लिए की जरूरत है.
[सैम] क्षमा करें, ऐसा क्यों है कि आप ने कहा कि ढेर तार के शीर्ष पर है?
मेरे लिए यह लगता है जैसे तार ढेर के भीतर हैं.
[Hardison] हाँ. हम पैदा कर रहे हैं, हम हमारे सरणी डेटा संरचना ले जा रहे हैं -
कि एक बड़ा सवाल है. तो सवाल यह है कि जो लोग इस ऑनलाइन देख रहे हैं के लिए है,
हम क्यों कह रहे हैं कि ढेर तार के शीर्ष पर है,
क्योंकि यह यहाँ की तरह तार ढेर के अंदर लग रहा है?
जो पूरी तरह से मामला है.
मैं बात कर रहा था क्या था कि हम एक सरणी डेटा संरचना मिल गया है.
हम चार * की एक सरणी, तारों के इस सरणी मिल गया है,
और हम उस को जोड़ने के क्रम में स्टैक्ड डेटा संरचना बनाने के लिए जा रहे हैं.
>> तो एक ढेर थोड़ा एक सरणी से अधिक जटिल है.
एक ढेर बनाने के लिए हम एक सरणी का उपयोग कर सकते हैं.
इतना है कि जहां हम कहते हैं कि ढेर एक सरणी के शीर्ष पर बनाया गया है.
इसी तरह, जैसे कि मैंने पहले कहा, हम एक लिंक सूची के शीर्ष पर एक ढेर का निर्माण कर सकते हैं.
हमारे तत्वों को पकड़ने के लिए एक सरणी का उपयोग करने के बजाय,
हम एक लिंक सूची का उपयोग करने के लिए हमारे तत्वों को पकड़ सकता है और है कि चारों ओर ढेर का निर्माण.
चलो उदाहरण के एक जोड़े के माध्यम से चलते हैं, कुछ कोड को देख,
देखने के लिए क्या वास्तव में यहाँ क्या हो रहा है.
बाएँ पर, मैं नीचे फेंक दिया है कि ढेर struct किस तरह स्मृति में देखना होगा
अगर क्षमता से चार में परिभाषित किया गया है.
हम हमारे चार तत्व चार * सरणी मिल गया है.
हम तार [0], तार [1], तार [2] तार, [3], मिल गया है
और फिर हमारे आकार पूर्णांक के लिए है कि पिछले अंतरिक्ष.
क्या इसका मतलब है? ठीक है.
यह क्या होता है अगर मैं सही पर क्या करते हैं,
जो मेरे कोड होगा, सिर्फ एक संरचना है, कहा जाता है एक खड़ी struct की घोषणा की है.
यह है कि हम क्या हो. यह नीचे स्मृति में इस पदचिह्न देता है.
पहले यहाँ सवाल यह है कि इस ढेर struct की सामग्री क्या कर रहे हैं?
अभी वे कुछ भी नहीं कर रहे हैं, लेकिन वे पूरी तरह से कुछ भी नहीं कर रहे हैं.
वे कचरे के इस तरह कर रहे हैं. हम कोई विचार नहीं है जो उन में है.
जब हम ढेर एस की घोषणा करने के लिए, हम सिर्फ इतना है कि फेंक रहे हैं स्मृति के शीर्ष पर नीचे.
यह int i घोषित करने और आरंभ करने के दौरान यह नहीं की तरह की तरह है.
तुम नहीं जानता कि क्या वहाँ में है. आप पढ़ सकते हैं क्या वहाँ में है,
लेकिन यह सुपर मददगार नहीं हो सकता है.
एक बात आप हमेशा के लिए याद रखना चाहते हैं इनिशियलाइज़ जो कुछ भी प्रारंभीकृत किया जाना चाहिए.
इस मामले में, हम के आकार को प्रारंभ करने के लिए शून्य हो जा रहे हैं,
क्योंकि कि बाहर बारी के लिए हमारे लिए बहुत महत्वपूर्ण हो जा रहा है.
हम आगे जाना है और संकेत के सभी, सभी चार * s शुरू नहीं कर पाया है,
कुछ समझ मूल्य, शायद अशक्त हो.
लेकिन यह पूरी तरह से जरूरी है कि हम ऐसा कर नहीं है.
>> अब, दो ढेर पर मुख्य संचालन कर रहे हैं?
किसी से व्याख्यान याद आप ढेर के साथ क्या करना है? हाँ?
[स्टेला] धक्का और popping? वास्तव में. >>
धक्का और popping ढेर पर दो मुख्य संचालन कर रहे हैं.
धक्का और क्या करता है? >> यह शीर्ष पर कुछ कहते हैं
ढेर की, और फिर popping यह दूर ले जाता है.
[Hardison] बिल्कुल सही. तो ढेर के शीर्ष पर कुछ धक्का धक्का.
यह भोजन एक खाने की ट्रे काउंटर पर नीचे डाल कर्मचारियों की तरह है.
और popping एक खाने की ट्रे ढेर से दूर ले जा रहा है.
चलो क्या होता है उदाहरण के एक जोड़े के माध्यम से चलना
जब हम ढेर में बातें धक्का.
यदि हम हमारे ढेर पर 'हैलो' स्ट्रिंग धक्का थे
यह है कि क्या हमारे आरेख की तरह अब देखना होगा.
देखें क्या होता है?
हम हमारे तार सरणी के पहले तत्व में धकेल दिया
और हम हमारे आकार गिनती बढ़ी 1 हो.
तो अगर हम दो स्लाइडों के बीच अंतर को देखो, यहाँ 0 था, यहाँ धक्का से पहले है.
यहाँ धक्का के बाद है.
धक्का से पहले, धक्का के बाद.
और अब हम हमारे ढेर में एक तत्व है.
यह स्ट्रिंग "नमस्ते" है, और यह बात है.
सरणी में बाकी सब कुछ, हमारे तार सरणी में, अभी भी कचरा.
हम इसे प्रारंभ नहीं किया है.
हम कहते हैं कि हम हमारे ढेर पर एक स्ट्रिंग धक्का.
हम इस समय पर "दुनिया" धक्का करने के लिए जा रहे हैं.
तो आप देख सकते हैं कि "दुनिया" यहाँ "हैलो" के शीर्ष पर चला जाता है,
और आकार गिनती 2 करने के लिए चला जाता है.
अब हम "CS50" धक्का कर सकते हैं, और कहा कि शीर्ष पर फिर से जाना होगा.
अगर हम वापस जाओ, आप देख सकते हैं कि कैसे हम ढेर के शीर्ष पर बातें जोर दे रहे हैं.
और अब हम पॉप करने के लिए मिलता है.
जब हम ढेर के बंद कुछ popped, क्या हुआ?
कोई भी अंतर देख रहे हो? यह बहुत सूक्ष्म है.
[छात्र] आकार. >> हाँ, आकार बदल दिया है.
>> और क्या आप बदलाव की उम्मीद होता है?
[छात्र] भी तार,. >> ठीक है. भी तार.
यह पता चला है कि जब आप इसे इस तरह से कर रहे हैं,
क्योंकि हम तत्वों हमारे ढेर में नहीं की नकल कर रहे हैं,
हम वास्तव में कुछ भी नहीं है, हम सिर्फ आकार का उपयोग कर सकते हैं
चीजों की संख्या के हमारे सरणी में ट्रैक रखने
इतना है कि जब हम फिर से पॉप, फिर हम सिर्फ 1 आकार के लिए हमारे नीचे घटती.
वहाँ नहीं करने के लिए वास्तव में जाओ और कुछ को अधिलेखित करने की आवश्यकता है.
कायरता की तरह.
यह पता चला है कि हम आम तौर पर सिर्फ बातें अकेले छोड़ क्योंकि यह कम काम के लिए हमें करने के लिए.
अगर हम वापस जाओ और कुछ को अधिलेखित नहीं है, तो यह क्यों करते हो?
तो जब हम ढेर की दो बार बंद पॉप, सब करता है कि आकार समय की एक जोड़ी घटती.
और फिर, यह केवल क्योंकि हम बातें हमारे ढेर में नहीं की नकल कर रहे हैं.
हाँ? आगे बढ़ो.
[छात्र, unintelligible] >> और फिर क्या होता है जब आप कुछ फिर से धक्का?
जब आप कुछ फिर से धक्का, जहां यह जाना है?
यह, तुलसी जाना कहाँ है? [1] तार में? >> >> ठीक है.
[3] तार में क्यों नहीं जाती है?
[तुलसी] क्योंकि यह भूल गया है कि तार में कुछ भी थी [1] और [2]?
[Hardison] बिल्कुल सही. हमारे ढेर, अनिवार्य रूप से, "भूल" कि यह कुछ भी करने के लिए जोत रहा था
तार में [1] या तार [2], इसलिए जब हम "धक्का" woot
यह सिर्फ तत्व में [1] तार पर डालता है.
यह कैसे काम करता है पर किसी भी सवाल का एक बुनियादी स्तर पर कर रहे हैं?
[सैम] तो यह किसी भी तरह से एक गतिशील राशि के मामले में नहीं है,
या ढेर के आकार के मामले में?
[Hardison] बिल्कुल सही. यह है - बात यह थी कि यह एक गतिशील growning ढेर नहीं था.
यह एक ढेर है कि सबसे अधिक है, चार चार * सबसे चार चीजों को पकड़ कर सकते हैं.
अगर हम कोशिश करते हैं और एक पांचवीं बात धक्का थे, तुम्हें क्या लगता है चाहिए होता है?
[छात्रों, unintelligible]
[Hardison] बिल्कुल सही. वहाँ चीज़ें है कि हो सकता है की एक संख्या हैं.
यह संभवतः फॉल्ट सकता है पर निर्भर करता है कि हम क्या कर रहे थे -
वास्तव में हम कैसे पीछे के अंत से लागू करने गए थे.
यह परिवर्तन कर सकता है. यह है कि बफर अतिप्रवाह कि हम वर्ग के बारे में बात हो सकता है.
सबसे महत्वपूर्ण बात यह है कि लिखा हो सकता है क्या होगा
अगर हम हमारे ढेर पर एक अतिरिक्त बात धक्का करने की कोशिश की है?
तो तुम एक बफर अतिप्रवाह का उल्लेख किया.
क्या बात है कि पर लिखा मिल जाएगा या पर stomped हो सकता है
अगर हम एक अतिरिक्त बात को पुश करने की कोशिश कर गलती overflowed?
[डैनियल, unintelligible] >> संभव है.
लेकिन शुरू में, क्या हो सकता है? क्या होगा अगर हम एक चौथी बात धक्का करने की कोशिश की?
यह इस स्मृति चित्र मिल गया है कि हम कम से कम आकार में परिवर्तन कर सकता है.
>> समस्या सेट विनिर्देश में, जो कि हम क्या करने के लिए लागू किया जा रहे हैं आज,
क्या हम करना चाहते हैं बस वापसी झूठी है.
हमारे धक्का विधि किसी बुलियन मान वापस जा रहा है,
और कि बूलियन मान सच हो सकता है अगर धक्का सफल
और अगर गलत है, हम और अधिक कुछ भी धक्का नहीं कर सकते हैं क्योंकि ढेर भरा है.
चलो कि कोड का एक छोटा सा के माध्यम से अभी चलना.
यहाँ हमारे धक्का समारोह है.
हमारे एक ढेर के लिए धक्का समारोह स्ट्रिंग में लेने के लिए ढेर पर डाल दिया जा रहा है.
यह सही वापस जा रहा है यदि स्ट्रिंग सफलतापूर्वक धक्का दिया था
पर ढेर और गलत अन्यथा.
क्या पर कोई सुझाव एक अच्छा पहला यहाँ बात हो सकती है?
[सैम] अगर आकार क्षमता के बराबर होती है तो वापसी झूठी?
[Hardison] बिंगो. अच्छा काम है.
अगर आकार क्षमता है, हम झूठी वापसी के लिए जा रहे हैं.
हम हमारे ढेर में अधिक कुछ भी नहीं डाल सकता.
अन्यथा, हम ढेर के शीर्ष पर कुछ डाल करना चाहते हैं.
"ढेर के शीर्ष," शुरू में क्या है?
[डैनियल] साइज 0? >> 0 आकार.
ढेर के शीर्ष के बाद वहाँ ढेर में एक बात है क्या है? Missy, तुम जानते हो?
[Missy]. >> साइज ठीक है. आप आकार करने के लिए जोड़ने के रखने के लिए,
और हर बार जब आप सरणी में सूचकांक आकार में नए तत्व में डाल रहे हैं.
हम इसे एक जहाज के उस तरह के साथ क्या कर सकते हैं, कि अगर समझ में आता है.
इसलिए हम अपने तार सरणी मिल गया है, हम इसे आकार सूचकांक में प्रवेश करने जा रहे हैं,
और हम सिर्फ वहाँ में हमारे चार * की दुकान करने के लिए जा रहे हैं.
सूचना कैसे कोई स्ट्रिंग नकल यहाँ पर जा रहा है,
स्मृति का कोई गतिशील आवंटन?
तो और Missy लाया अब हम क्या करना है,
क्योंकि हम स्ट्रिंग सरणी में उपयुक्त जगह में संग्रहित किया है,
और उसने कहा है कि हम एक आकार वेतन वृद्धि के लिए इतना है कि हम अगले धक्का के लिए तैयार कर रहे हैं.
तो हम s.size के साथ कर सकते हैं कि + +.
इस बिंदु पर, हम हमारे सरणी में धकेल दिया है. आखिरी बात हमें क्या करना है क्या है?
[छात्र] सच लौटें. >> सच लौटें.
तो यह बहुत आसान है, एक बहुत आसान कोड. बहुत ज्यादा नहीं है.
एक बार जब आप कैसे काम करता है ढेर के चारों ओर अपने सिर को लपेटा है,
इस सुंदर को लागू करने के लिए सरल है.
>> अब, इस के अगले भाग के ढेर के एक स्ट्रिंग बंद popping है.
मैं तुम लोगों को कुछ समय के लिए यह एक छोटा सा पर काम देने के लिए जा रहा हूँ.
यह लगभग अनिवार्य रूप से धक्का में क्या हम यहाँ किया है के विपरीत है.
मैंने किया है कि वास्तव में क्या है - उफ़.
मैं यहाँ पर, और उपकरण में एक उपकरण को हटा दिया गया है,
मैं खींच लिया है समस्या 5 विनिर्देश सेट.
यदि हम यहाँ में ज़ूम, हम देख सकते मैं cdn.cs50.net/2012/fall/psets/pset5.pdf पर हूँ.
क्या आप लोग इस कोड है कि यहाँ स्थित है, section6.zip डाउनलोड?
सही सभी. अगर तुम नहीं किया है कि, कि अभी क्या करना है, बहुत जल्दी.
मैं इसे अपने टर्मिनल विंडो में करूँगा.
मैं वास्तव में यह यहाँ था. हाँ.
हाँ, सैम? >> मैं आप आकार की है s.string कोष्ठक क्यों कहा str = के बारे में एक सवाल है?
Str क्या है? है कि इससे पहले कहीं परिभाषित किया गया है, या - ओह, चार * str में?
[Hardison] हाँ, बिल्कुल. यही तर्क था. >> ओह, ठीक है. माफ़ कीजिए.
[Hardison] हम अंदर धक्का स्ट्रिंग निर्दिष्ट कर रहे हैं
अन्य प्रश्न है कि आया है कि हम वास्तव में यहाँ के बारे में बात नहीं हो सकता है
हम ले के लिए दी गई है कि हम इस चर कहा जाता था
कि गुंजाइश है और हमारे लिए सुलभ था.
हमने ले लिया है के लिए दी गई है कि इस ढेर struct था.
तो इस धक्का कोड में पीछे मुड़कर देखें,
आप देख सकते हैं कि हम इस स्ट्रिंग में पारित कर दिया गया साथ सामान कर रहे हैं
लेकिन फिर अचानक, हम s.size पहुँच रहे हैं, जैसे, कहाँ से आए हो?
कोड कि हम अनुभाग संग्रह में लग जा रहे हैं में
और फिर सामान है कि आप अपनी समस्या में कर रही हो जाएगा सेट,
हम बनाया है हमारे ढेर एक वैश्विक चर struct
इतना है कि हम हमारे सभी विभिन्न कार्यों में इसे करने के लिए उपयोग कर सकते हैं
स्वयं इसे पास के आसपास है और यह संदर्भ द्वारा पारित करने के लिए बिना,
यह करने के लिए सामान की है कि सभी तरह करते हैं.
हम सिर्फ एक छोटा सा धोखा दे रहे हैं, अगर तुम जाएगा, को अच्छे चीजों को बनाने के लिए.
और है कि कुछ हम यहाँ कर रहे हैं क्योंकि यह मनोरंजन के लिए है, यह आसान है.
अक्सर, आप लोगों को यह नहीं देख अगर वे एक बड़ा डेटा संरचना है
है कि उनके कार्यक्रम के भीतर पर संचालित किया जा रहा है.
>> उपकरण को वापस जाने के लिए.
क्या सबको सफलतापूर्वक section6.zip मिलता है?
हर कोई इसे खोलना खोलना section6.zip का उपयोग?
यदि आप अनुभाग 6 निर्देशिका में जाना -
आह, सभी जगह
और आप सूची में यहाँ क्या है, आप देखते हैं कि आप तीन अलग अलग ग. फ़ाइलें मिली है.
आप एक पंक्ति, एक sll, जो अकेले लिंक सूची है और एक ढेर मिल गया है.
यदि आप stack.c खोलते हैं,
आप देख सकते हैं कि हम यह हमारे लिए परिभाषित struct मिल गया है,
सटीक struct है कि हम सिर्फ स्लाइड में के बारे में बात की थी.
हम ढेर के लिए हमारे वैश्विक चर मिल गया है,
हम हमारे धक्का समारोह मिल गया है,
और फिर हम अपने पॉप समारोह मिल गया है.
मैं कोड डाल करने के लिए वापस धक्का स्लाइड पर यहाँ हूँ,
लेकिन मैं आप लोगों को करने के लिए करना चाहते हैं जो अपनी क्षमता का सबसे अच्छा करने के लिए है,
जाओ और पॉप समारोह को लागू करने.
एक बार जब आप इसे लागू किया है, तो आप ढेर बनाने के साथ इस संकलन कर सकते हैं,
और फिर परिणामी ढेर निष्पादन योग्य चलाने,
और कहा कि इस परीक्षण कोड का सब यहाँ नीचे है कि मुख्य चलेंगे.
और मुख्य वास्तव में धक्का और पॉप कॉल बनाने का ख्याल रखता है
और यकीन है कि सब कुछ सही माध्यम से चला जाता है.
यह भी आकार धुआँरा सही यहाँ initializes
ताकि आप कि आरंभ करने के दौरान के बारे में चिंता करने की ज़रूरत नहीं है.
आप मान सकते हैं कि यह ठीक से किया गया initialized है
जब तक कि आप यह पॉप समारोह में उपयोग.
क्या इसका यह मतलब है?
तो यहाँ हम चले. वहाँ धक्का कोड है.
मैं तुम्हें 5 लोग या 10 मिनट दे देंगे.
और अगर आप अंतरिम में किसी भी सवाल है जब आप कोडिंग कर रहे हैं,
कृपया उन्हें पूछना ज़ोर से.
तो अगर आप एक चिपके बिंदु को मिलता है, बस पूछो.
मुझे पता है, बाकी सब लोग जानते हैं.
अपने पड़ोसी के साथ भी काम करते हैं.
[डैनियल] हम सिर्फ पॉप रहे हैं अभी लागू करने? >> पॉप.
हालांकि आप धक्का के कार्यान्वयन की नकल यदि आप चाहें तो कर सकते हैं
इतना है कि परीक्षण के काम करेंगे.
क्योंकि यह मुश्किल है में हो रही बातों का परीक्षण
या, यह मुश्किल है popping चीजों का परीक्षण एक ढेर से बाहर अगर वहाँ ढेर में के साथ शुरू करने के लिए कुछ भी नहीं है.
>> लौटने होना चाहिए पॉप क्या है? ढेर के ऊपर से तत्व.
यह ढेर के शीर्ष के तत्व प्राप्त करने के लिए माना जाता है
और फिर ढेर के आकार घटती,
और अब आप शीर्ष पर तत्व खो दिया है.
और फिर आप शीर्ष पर तत्व वापस.
[छात्र, unintelligible]
[Hardison] तो क्या होता है अगर आपको लगता है कि? [छात्र, unintelligible]
क्या समाप्त होता है हो रहा है तो आप शायद या तो पहुँच रहे हैं
एक तत्व है कि अभी तक प्रारंभ नहीं किया गया है, ताकि अपनी गणना
जहां पिछले तत्व है बंद है.
तो यहाँ है, अगर तुम नोटिस, धक्का हम s.size तत्व पर तार पहुँच रहे हैं
क्योंकि यह एक नया सूचकांक है.
यह ढेर के नए शीर्ष है.
पॉप में जबकि, s.size अगले अंतरिक्ष होने जा रहा है,
अंतरिक्ष कि आपके ढेर में सभी तत्वों के शीर्ष पर है.
तो तत्व सर्वोच्च s.size पर नहीं है,
बल्कि, यह नीचे है.
>> अन्य बात करने के लिए आप जब पॉप में,
आप आकार घटती है.
यदि आप हमारे छोटे चित्र वापस सही यहाँ याद है,
वास्तव में, एक ही बात है कि हम हो देखा जब हम पॉप बुलाया
था कि इस आकार के पहले 2 से गिरा दिया, तो 1 के लिए,.
फिर जब हम पर एक नए तत्व को धक्का दे दिया, यह उचित स्थान पर जाना होगा.
[तुलसी] यदि s.size 2 है, तो यह 2 तत्व को नहीं जाना होगा,
और फिर आप उस तत्व पॉप बंद करना चाहते हैं?
तो अगर हम करने के लिए चला गया - >> तो हम इस पर फिर से देखो.
यदि यह इस बिंदु पर हमारे ढेर
और हम पॉप कहते हैं,
जिस पर सर्वोच्च तत्व सूचकांक है?
[2] में तुलसी, लेकिन यह 3 पॉप जा रहा है. >> ठीक है.
तो यह है कि जहां हमारे आकार 3 है, लेकिन हम 2 सूचकांक में तत्व पॉप चाहते हैं.
यह एक है कि आप शून्य arrays के अनुक्रमण के साथ है कि बंद के एक विशिष्ट प्रकार है.
तो आप 3 तत्व पॉप करना चाहते हैं, लेकिन 3 तत्व सूचकांक 3 में नहीं है.
और कारण है कि हम नहीं है कि शून्य से 1 जब हम जोर दे रहे हैं
क्योंकि अभी, तुम नोटिस कि सर्वोच्च तत्व,
, अगर हम इस बिंदु पर ढेर पर कुछ और धक्का थे
हम यह 3 सूचकांक में धक्का चाहते हैं.
और यह सिर्फ इतना होता है कि आकार और सूचकांक अप लाइन जब आप जोर दे रहे हैं.
>> एक काम ढेर कार्यान्वयन कौन मिल गया है?
आप एक काम ढेर मिला है. क्या आप पॉप अभी तक काम कर रहा है?
[डैनियल] हाँ. एसा मुझे मालूम होता हैं
>> कार्यक्रम चल रहा है और seg दोषयुक्त नहीं, यह बाहर मुद्रण है?
क्या यह "सफलता" प्रिंट जब आप इसे चलाते?
हाँ. धुआँरा बनाओ, इसे चलाते हैं, अगर यह बाहर प्रिंट "सफलता" और बूम नहीं,
तो सब अच्छा है.
सही सभी. चलो उपकरण को बहुत जल्दी जाना,
और हम इस माध्यम से चलना होगा.
यदि हम क्या हो रहा है पॉप के साथ यहाँ पर देखो,
डैनियल, पहली बात है कि तुमने क्या था?
[डैनियल] यदि s.size 0 से अधिक है.
[Hardison] ठीक है. और तुमने ऐसा क्यों किया?
[डैनियल] यकीन है कि वहाँ ढेर अंदर कुछ था.
[Hardison] सही है. आप करने के लिए सुनिश्चित करें कि s.size 0 से अधिक है परीक्षण करना चाहते हैं;
अन्यथा, आप क्या चाहते हो?
[डैनियल] रिटर्न अशक्त? >> रिटर्न अशक्त, बिल्कुल.
तो अगर s.size 0 से अधिक है. तो हम क्या करने जा रहे हैं?
हम क्या अगर ढेर खाली नहीं है क्या करते हो?
[स्टेला] आप आकार घटती? >> आप आकार घटती है, ठीक है.
तो आपको लगता है कि कैसे क्या किया? >> S.size -.
[Hardison] ग्रेट. और फिर तुमने क्या किया?
[स्टेला] और फिर मैं वापस s.string कहा [s.size]
[Hardison] ग्रेट.
अन्यथा आप अशक्त लौटने के लिए. हाँ, सैम?
[सैम] यह क्यों की आवश्यकता नहीं करता है s.size 1 +?
[Hardison] 1 प्लस? >> हाँ. >> समझे.
[सैम] मैंने सोचा था कि क्योंकि आप 1 बाहर ले जा रहे हैं,
तो आप एक के लिए कहा है कि वे नहीं लौट जा रहे हैं.
[Hardison] और यह सिर्फ हम क्या बारे में 0 सूचकांक के इस पूरे मुद्दे के साथ बात कर रहे थे.
तो अगर हम यहाँ पर वापस ज़ूम.
अगर हम इस आदमी को सही लग रही है, आप देख सकते हैं कि जब हम पॉप,
हम 2 सूचकांक में तत्व popping रहे हैं.
>> इसलिए हम अपने आकार 1 कमी है, तो हमारे आकार हमारे सूचकांक से मेल खाता है.
अगर हम आकार 1 घटती नहीं है, तो हम आकार -1 और तब घटती है.
बढ़िया है. सब अच्छा है?
इस पर कोई सवाल?
वहाँ अलग तरीके की एक संख्या के रूप में अच्छी तरह से यह लिखने के हैं.
वास्तव में, हम कुछ भी कर सकते हैं - हम एक एक लाइनर कर सकते हैं.
हम एक एक लाइन वापसी कर सकते हैं.
तो हम वास्तव में इससे पहले कि हम कर रही है कि वापस घटती कर सकते हैं.
S.size पहले तो डाल.
वह लाइन वास्तव में घने बनाता है.
कहाँ के बीच अंतर - आकार और s.size -
है कि यह पोस्टफिक्स - वे यह पोस्टफिक्स फोन वजह से आता है के बाद s.size -
मतलब है कि s.size सूचकांक ढूँढने के प्रयोजनों के लिए मूल्यांकन किया जाता है
के रूप में यह वर्तमान में है जब इस लाइन को मार डाला है,
और तो यह होता है के बाद रेखा को मार डाला जाता है.
है बाद सूचकांक s.size में तत्व पहुँचा है.
और है कि हम क्या चाहते हैं नहीं है, क्योंकि हम घटती 1 ऐसा करना चाहते हैं.
Othewise, हम करने के लिए सरणी तक पहुँचने के होने जा रहे हैं, प्रभावी ढंग से, सीमा के बाहर है.
हम एक है कि हम वास्तव में उपयोग करना चाहते ऊपर तत्व तक पहुँचने हो जा रहे हैं.
हाँ, सैम? >> यह तेजी से या कम रैम का उपयोग करने के लिए एक लाइन या नहीं में है?
[Hardison] ईमानदारी से, यह वास्तव में निर्भर करता है.
[सैम, unintelligible] >> हाँ, यह निर्भर करता है. आप संकलक चाल हो सकती है
संकलक पाने के लिए है कि पहचान के लिए, आम तौर पर, मैं कल्पना.
>> तो हम इस संकलक अनुकूलन सामान के बारे में एक छोटा सा उल्लेख किया है
कि आप संकलन कर सकते हैं,
और कहा कि बात की तरह है कि एक संकलक पता लगाने में सक्षम हो सकता है,
तरह ओह, हे, हो सकता है मैं एक ऑपरेशन में यह सब कर सकते हैं,
के रूप में राम से आकार चर में लोड करने के लिए विरोध किया है,
यह decrementing, इसे वापस भंडारण के बाहर, और फिर इसे वापस में फिर से लोड हो रहा है
इस आपरेशन के बाकी प्रक्रिया.
लेकिन आम तौर पर, नहीं, इस तरह की बात नहीं है
कि काफी तेजी से अपने कार्यक्रम बनाने जा रहा है.
ढेर पर कोई और सवाल?
>> तो धक्का और popping. अगर आप लोग बाहर हैकर संस्करण की कोशिश करना चाहते हैं,
हम हैकर संस्करण में किया है क्या वास्तव में चला गया है
बनाया है और इस स्टैक गतिशील हो जाना.
चुनौती है वहाँ मुख्य रूप से धक्का समारोह में यहाँ है,
पता लगाने की कैसे बनाने के लिए है कि सरणी बढ़ने
के रूप में आप पर ढेर करने के लिए अधिक से अधिक तत्वों को धक्का रखने.
यह वास्तव में बहुत ज्यादा अतिरिक्त कोड नहीं है.
आप वहाँ में malloc कॉल ठीक से याद है, बस एक फोन
और फिर बाहर आंकड़ा जब आप realloc कॉल करने के लिए जा रहे हैं.
यह एक मजेदार चुनौती है अगर आप रुचि रखते हैं.
>> लेकिन कुछ समय के लिए है, पर स्थानांतरित करने, और हम पंक्तिज के बारे में बात करते हैं.
यहाँ के माध्यम से स्क्रॉल.
कतार ढेर के एक करीबी भाई है.
तो ढेर में, चीजें हैं जो पिछले में डाल रहे थे
पहले तो पुनः प्राप्त किया जा बातें कर रहे थे.
हम इस में पिछले, बाहर पहली, या LIFO, आदेश मिल गया है.
जबकि कतार में है, के रूप में आप जब आप लाइन में खड़े कर रहे हैं से उम्मीद थी,
1 व्यक्ति लाइन में, 1 बात करने के लिए कतार में लाने के,
पहली बात यह है कि कतार से लिया जाता है.
कतार भी अक्सर इस्तेमाल किया जाता है जब हम रेखांकन के साथ काम कर रहे हैं,
जैसे हम के बारे में संक्षेप में बात के ढेर के साथ
और कतार भी अन्य चीजों की एक गुच्छा के लिए काम कर रहे हैं.
एक बात है कि अक्सर आता है को बनाए रखने की कोशिश कर रहा है, उदाहरण के लिए,
तत्वों का एक क्रमबद्ध सूची.
और तुम एक सरणी के साथ कर सकते हैं. आप एक सरणी में एक चीजों की क्रमबद्ध सूची बनाए रख सकते हैं,
लेकिन जहां मुश्किल हो जाता है कि है तो आप हमेशा के लिए खोजने के लिए है
अगली बात डालने के लिए उपयुक्त जगह है.
तो अगर आप 10 के माध्यम से संख्या की एक सरणी, 1,
और तब आप 100 के माध्यम से सभी नंबर 1 का विस्तार करना चाहते हैं,
और आप इन नंबरों यादृच्छिक क्रम में हो रही है और सब कुछ रखने की कोशिश कर रहा
क्रमबद्ध रूप में आप के माध्यम से जाना है, तो आप अंत में स्थानांतरण की एक बहुत कुछ कर रहा है.
कतारों और अंतर्निहित डेटा संरचनाओं के कुछ प्रकार के कुछ प्रकार के साथ,
आप वास्तव में यह काफी आसान रख सकते हैं.
आप कुछ जोड़ सकते हैं और फिर पूरी बात हर बार फेरबदल नहीं है.
और न ही आप आंतरिक तत्व के आसपास के स्थानांतरण के एक बहुत कुछ करना है.
जब हम एक कतार में लग रही है, तो आपको लगता है कि देख - भी queue.c में अनुभाग कोड में -
struct है कि हम तुम्हें दे दिया है वास्तव में struct है कि हम आप के लिए दिया एक ढेर के लिए इसी तरह की है.
>> इसका एक अपवाद है कि और एक अपवाद
यह है कि हम इस अतिरिक्त सिर बुलाया पूर्णांक है,
और यहाँ सिर कतार के सिर का ट्रैक रखने के लिए है,
या कतार में पहला तत्व है.
एक ढेर के साथ, हम तत्व का ट्रैक रखने के लिए है कि हम पुनः प्राप्त करने के बारे में थे करने में सक्षम थे,
या ढेर के शीर्ष, सिर्फ आकार का उपयोग,
जबकि एक कतार के साथ, हम विपरीत छोर के साथ सौदा कर रहे हैं.
हम अंत में बातें हमले करने की कोशिश कर रहे हैं, लेकिन तो सामने से चीजों वापसी.
बहुत प्रभावी ढंग से सिर के साथ, हम लाइन की शुरुआत के सूचकांक है,
और आकार हमें कतार के अंत के सूचकांक देता है
इतना है कि हम सिर से चीजों को पुनः प्राप्त करने और पूंछ को चीजों को जोड़ने के कर सकते हैं.
जबकि ढेर के साथ, हम केवल कभी ढेर के शीर्ष के साथ काम कर रहे थे.
हम ढेर के नीचे का उपयोग कभी नहीं था.
हम केवल शीर्ष पर चीजों को जोड़ा और बातें शीर्ष से दूर ले गया
तो हम हमारे struct के अंदर है कि अतिरिक्त क्षेत्र जरूरत नहीं थी.
यह नहीं है कि आम तौर पर समझ बनाने के?
सही सभी. हाँ, Charlotte? [Charlotte, unintelligible]
[Hardison] यह एक बड़ा सवाल है, और कहा कि एक कि व्याख्यान में आया था.
शायद कुछ उदाहरण के माध्यम से चलने समझाना होगा क्यों
हम तार कतार के सिर के रूप में [0] का उपयोग नहीं करना चाहती.
>> तो कल्पना कि हम हमारे कतार है, हम यह कतार कॉल करने के लिए जा रहे हैं.
शुरुआत में, जब हम सिर्फ यह instantiated है,
जब हम सिर्फ यह घोषित किया है, हम कुछ भी प्रारंभ नहीं किया है.
यह सब कचरा है. तो निश्चित रूप से हम यकीन है कि हम इनिशियलाइज़ बनाना चाहते हैं
दोनों आकार और सिर क्षेत्रों 0, उचित कुछ हो.
हम भी आगे जा सकते हैं और हमारे कतार में तत्वों अशक्त.
और इस चित्र फिट कर, सूचना है कि अब हमारे कतार केवल तीन तत्वों को पकड़ कर सकते हैं;
जबकि हमारे ढेर चार पकड़ सकता है, हमारे कतार केवल तीन पकड़ सकते हैं.
और कहा कि सिर्फ आरेख फिट कर.
पहली बात यह है कि यहाँ क्या होता है हम स्ट्रिंग enqueue "हाय".
और जैसे हम ढेर के साथ किया था, बहुत अलग यहाँ कुछ भी नहीं है,
हम तार पर [0] और 1 से हमारे आकार वेतन वृद्धि पर स्ट्रिंग फेंक देते हैं.
हम enqueue "अलविदा", उस पर डाल दिया जाता है.
तो यह सबसे अधिक भाग के लिए एक ढेर की तरह लग रहा है.
हम यहाँ से शुरू कर दिया है, नए तत्व, नए तत्व, आकार ऊपर जा रहा रखता है.
इस बिंदु पर क्या होता है जब हम कुछ विपंक्ति करना चाहते हैं?
जब हम विपंक्ति चाहते हैं, जो तत्व कि हम विपंक्ति करना चाहते है?
[तुलसी] स्ट्रिंग्स [0]. शून्य. >> बिल्कुल सही, तुलसी,.
हम पहली स्ट्रिंग, इस एक, "नमस्ते" से छुटकारा प्राप्त करना चाहते हैं.
तो दूसरी बात है कि बदल क्या था?
सूचना जब हम stack के कुछ बंद popped, हम सिर्फ आकार बदल गया है,
लेकिन यहाँ, हम चीजों को बदलने कि एक जोड़े को मिल गया है.
न केवल आकार बदलने के लिए, लेकिन सिर में परिवर्तन करता है.
यह Charlotte पहले बात करने के लिए वापस जा रहा है:
हम क्यों इस सिर के रूप में अच्छी तरह से है?
क्या अब यह समझ में आता है, Charlotte? >> तरह.
[Hardison] की तरह? तो क्या हुआ जब हम dequeued?
सिर क्या किया है कि अब दिलचस्प है?
[Charlotte] ओह, क्योंकि यह बदल - ठीक है. अच्छा.
क्योंकि सिर - जहां सिर स्थान के संदर्भ में परिवर्तन करने के लिए इशारा कर रहा है.
यह अब हमेशा शून्य सूचकांक एक है. >> हाँ, बिल्कुल.
क्या हुआ अगर उच्च तत्व dequeueing
किया गया था और हम इस सिर क्षेत्र नहीं था
क्योंकि हम हमेशा 0 सूचकांक हमारे कतार के सिर पर इस स्ट्रिंग बुला थे,
तो हम नीचे कतार के बाकी बदलाव करना चाहते हैं.
हम से "अलविदा" तार से [1] तार [0] को शिफ्ट करना चाहते हैं.
और तार [2] नीचे करने के लिए तार [1].
और हम तत्वों की पूरी सूची के लिए यह करना होगा,
तत्वों के पूरे सरणी.
और जब हम एक सरणी के साथ कर रहे हैं, जो वास्तव में महंगा हो जाता है.
तो यहाँ, यह एक बड़ा सौदा नहीं है. हम सिर्फ हमारे सरणी में तीन तत्व है.
लेकिन अगर हम एक हजार तत्वों या एक लाख तत्वों की एक कतार थी,
और फिर अचानक, हम विपंक्ति का एक गुच्छा बनाने शुरू एक पाश में कहता है,
बातें सच धीमा करने के लिए के रूप में यह सब कुछ बदलाव लगातार नीचे जा रहे हैं.
तुम्हें पता है, 1 से पाली, 1 से 1 पाली, पाली, 1 से बदलाव.
इसके बजाय, हम इस सिर का उपयोग करें, हम इसे एक "सूचक" कहते हैं भले ही यह वास्तव में एक सूचक नहीं है
सख्त अर्थ में, यह एक सूचक प्रकार नहीं है.
यह एक int * या एक चार * या ऐसा कुछ नहीं है.
लेकिन यह ओर इशारा करते हुए या हमारे कतार के सिर का संकेत है. हाँ?
>> [छात्र] विपंक्ति बस बंद पॉप जो भी सिर पर है कैसे पता है?
[Hardison] विपंक्ति कैसे पता है कि कैसे पॉप करने के लिए जो कुछ भी सिर पर है? >> ठीक है, हाँ.
>> पर लग रहा है क्या है सिर्फ सिर जो क्षेत्र के लिए सेट कर दिया जाता है.
तो इस पहले मामले में, अगर हम सही यहाँ देखो,
हमारे सिर 0 0, सूचकांक है. >> ठीक है.
[Hardison] तो यह सिर्फ ठीक है, अच्छी तरह से, सूचकांक में 0 तत्व, स्ट्रिंग "हाय" कहते हैं,
हमारे कतार के सिर पर तत्व है.
तो हम उस आदमी को विपंक्ति करने के लिए जा रहे हैं.
और उस तत्व है कि फोन करने के लिए वापस आ जाता होगा.
हाँ, साद? >> सिर तो मूल रूप से सेट जहाँ आप यह सूचकांक करने के लिए जा रहे हैं?
कि यह की शुरुआत है? >> हाँ. ठीक है. >>
[Hardison] कि हमारे सरणी के लिए नई शुरुआत बनने है.
तो जब आप कुछ विपंक्ति, सूचकांक q.head पर तत्व का उपयोग करने के लिए सब तुम्हें क्या करना है है,
और उस तत्व कि आप विपंक्ति चाहते हो जाएगा.
तुम भी आकार घटती है.
हम एक बिट में देख सकते हैं जहां चीजें इस के साथ एक छोटे से मुश्किल हो जाएगा.
हम विपंक्ति, और अब, अगर हम फिर enqueue,
जहाँ हम enqueue करते?
अगले तत्व हमारे कतार में कहां जाना है?
कहते हैं कि हम "सीएस" स्ट्रिंग enqueue चाहते.
जो सूचकांक में जाना होगा? [छात्र] स्ट्रिंग्स [2]. दो. >>
क्यों नहीं 2 और 0?
[तुलसी] क्योंकि अब सिर 1 है तो, है कि सूची के शुरुआत की तरह है?
[Hardison] सही है. और क्या सूची के अंत अर्थ?
हम क्या हमारे कतार के अंत को निरूपित करने के लिए इस्तेमाल कर रहे थे?
सिर हमारे कतार के सिर, हमारे कतार की शुरुआत है.
हमारी कतार के अंत क्या है? साइज [छात्र]. >> आकार, बिल्कुल.
इसलिए हमारे नए तत्व आकार में जाओ, और तत्व है कि हम ले बंद सिर पर उतर आते हैं.
जब हम अगले तत्व enqueue, हम यह आकार में डाल रहे हैं.
इससे पहले कि आप [छात्र] डाल दिया है कि हालांकि, आकार 1 था, सही?
[Hardison] सही है. तो आकार में काफी नहीं है. +, साइज, लेकिन नहीं +1 + सिर.
क्योंकि हम सब कुछ सिर राशि से स्थानांतरित कर दिया.
यहाँ तो, अब हम 1 आकार की एक कतार है कि 1 सूचकांक में शुरू होता है मिल गया है.
पूंछ के सूचकांक में 2 है. हाँ?
>> [छात्र] क्या होता है जब आप विपंक्ति तार [0], और स्मृति में तार 'स्लॉट
अभी खाली है, पाने के मूल रूप से, या बस भूल?
[Hardison] हाँ. इस अर्थ में, हम सिर्फ उन्हें भूल रहे हो.
अगर हम उन की प्रतियां के लिए भंडारण कर रहे थे -
कई डेटा संरचनाओं अक्सर तत्वों के अपने प्रतियां स्टोर
इतना है कि डेटा संरचना के प्रबंधन के व्यक्ति को चिंता नहीं है
जहां उन सभी संकेत जा रहे हैं के बारे में.
डेटा संरचना करने के लिए सब कुछ करने के लिए पर धारण, सभी प्रतियां करने के लिए पर रखती है,
लगता है कि सब कुछ उचित बनी रहती है.
हालांकि, इस मामले में, इन आंकड़ा संरचना सिर्फ सादगी के लिए,
नहीं बना है कि हम उन्हें में भंडारण कर रहे हैं कुछ की प्रतियां.
[छात्र] तो यह एक निरंतर सरणी है? हाँ. >>
अगर हम परिभाषा क्या इस संरचना का था पर वापस देखो, यह है.
यह सिर्फ एक मानक सरणी है आप की तरह देखा है,
चार * ओं की एक सरणी.
कि क्या? >> हाँ, मैं सोच रहा था
अगर तुम अंततः स्मृति से बाहर चलने देंगे, एक निश्चित सीमा तक,
अगर आप अपने सरणी में इन खाली स्थानों है?
[Hardison] हाँ, यह एक अच्छी बात है.
>> यदि हम क्या हुआ है पर अब इस बिंदु पर देखो,
हम हमारे कतार भर दिया है, ऐसा लगता है.
लेकिन हम वास्तव में हमारे कतार नहीं भर दिया है
क्योंकि हम एक कतार है कि 2 आकार है, लेकिन यह 1 सूचकांक में शुरू होता है,
कारण है कि जहां हमारे सिर सूचक है.
जैसे आप कह रहे थे कि, तार पर तत्व [0], 0 सूचकांक में, वास्तव में वहाँ नहीं है.
यह हमारे कतार में अब और नहीं है.
हम बस में जाना है और इसे अधिलेखित जब हम यह dequeued जहमत नहीं उठाई.
तो भले ही यह लग रहा है जैसे हम स्मृति से बाहर चलाने की है, हम वास्तव में नहीं है.
जगह है कि हमें का उपयोग करने के लिए उपलब्ध है.
उचित व्यवहार, अगर हम कोशिश करते हैं और पहले विपंक्ति कुछ थे
"अलविदा" की तरह, कि अलविदा पॉप बंद होगा.
अब हमारे कतार 2 सूचकांक में शुरू होता है और 1 आकार की है.
और अब अगर हम कोशिश करते हैं और कुछ enqueue फिर, 50 कहते हैं,
50 0 सूचकांक में इस जगह में जाना चाहिए
क्योंकि यह अभी भी हमारे लिए उपलब्ध है. हाँ, साद?
[साद] कि स्वचालित रूप से होता है?
[Hardison] यह काफी स्वतः नहीं होता है. आप गणित करने के लिए है
बनाने के लिए यह काम करते हैं, लेकिन अनिवार्य रूप से हम क्या किया है हम सिर्फ चारों ओर लपेटा है.
[Saad] और यह ठीक है अगर यह इसे के बीच में एक छेद है?
[Hardison] यह है कि अगर हम गणित ठीक से काम कर सकते हैं.
>> और यह पता चला कि है कि वास्तव में माड आपरेटर के साथ करने के लिए मुश्किल नहीं है.
तो बस जैसे हम सीज़र और क्रिप्टो सामान के साथ किया था,
आधुनिक का उपयोग करते हुए, हम चीजों के आसपास लपेटो करने के लिए मिलता है और जा रहा रख सकते
के आसपास है और आसपास और चारों ओर के साथ हमारे कतार
है कि सिर सूचक के चारों ओर बढ़ रखने.
सूचना है कि आकार हमेशा तत्वों की संख्या वास्तव में सम्मान कतार के भीतर.
और यह सिर्फ सिर सूचक है कि माध्यम से साइकिल रहता है.
यदि हम यहाँ क्या हुआ है पर देखो, अगर हम शुरू करने के लिए वापस जाओ,
और तुम बस देखो क्या सिर करने के लिए होता है
जब हम कुछ enqueue, सिर करने के लिए कुछ भी नहीं हुआ.
जब हम कुछ और कतारबद्ध, सिर करने के लिए कुछ भी नहीं हुआ.
ही हम कुछ dequeued, एक सिर से ऊपर चला जाता है.
हम कुछ कतारबद्ध, सिर करने के लिए कुछ भी नहीं होता है.
जब हम कुछ विपंक्ति, अचानक सिर incremented हो जाता है.
जब हम कुछ enqueue, सिर करने के लिए कुछ भी नहीं होता है.
>> इस बिंदु पर क्या होगा अगर हम कुछ फिर विपंक्ति थे?
किसी भी विचार? सिर करने के लिए क्या होगा?
क्या सिर करने के लिए नहीं होना चाहिए
अगर हम कुछ विपंक्ति थे?
सिर सही अब 2 सूचकांक में है,
जिसका अर्थ है कि कतार के सिर तार [2].
[छात्र] जो 0 देता है? >> यह 0 से लौट जाना चाहिए. यह पीठ के आसपास लपेटो, बिल्कुल चाहिए.
अब तक, हर बार हम विपंक्ति बुलाया, हम सिर करने के लिए किया गया है उनका कहना है,
सिर करने के लिए एक जोड़ने के लिए, सिर के लिए एक जोड़ने के लिए, सिर के लिए एक जोड़ने.
जैसे ही सिर सूचक हमारे सरणी में अंतिम सूचकांक के लिए हो जाता है,
तो हम इसे लपेटो वापस शुरू करने के लिए चारों ओर है, 0 से वापस जाओ.
[Charlotte] एक ढेर में कतार की क्षमता निर्धारित करता है?
[Hardison] इस मामले में, हम सिर्फ एक # परिभाषित निरंतर है का उपयोग किया गया है. ठीक है. >>
[Hardison] वास्तविक ग फ़ाइल में, आप यह एक छोटा सा के साथ में और गंदगी जा सकते हैं
और यह बड़ा या के रूप में थोड़ा के रूप में आप चाहते हैं के रूप में कर सकते हैं.
[Charlotte] तो जब आप इसे एक कतार बना रहे हैं, कैसे तुम बनाने के कंप्यूटर पता है
आप कितना बड़ा ढेर होने के लिए करना चाहते हैं?
[Hardison] यह एक बड़ा सवाल है.
वहाँ तरीके के एक जोड़े हैं. बस इसे परिभाषित सामने है
और यह कहने के लिए एक पंक्ति है कि 4 तत्वों या 50 तत्वों या 10,000 है होने जा रहा है.
अन्य तरीका हैकर संस्करण लोग क्या कर रहे हैं
और कार्यों के लिए अपनी कतार गतिशील बढ़ने के रूप में अधिक चीजें अंदर शामिल हो
>> [Charlotte] तो पहले विकल्प के साथ जाना है, क्या वाक्यविन्यास आप का उपयोग करते हैं
कार्यक्रम बता कतार के आकार क्या है?
[Hardison] आह. तो चलो इस से बाहर निकलने के लिए.
मैं अभी भी यहाँ stack.c में हूँ, इसलिए मैं सिर्फ ऊपर करने के लिए यहाँ स्क्रॉल करने जा रहा हूँ.
आप यह सही देख सकते हैं यहाँ? यह # 10 क्षमता को परिभाषित.
और यह लगभग उसी वाक्यविन्यास कि हम कतार के लिए है.
कतार में छोड़कर, हम यहाँ कि अतिरिक्त struct क्षेत्र मिल गया है.
[Charlotte] ओह, मैंने सोचा क्षमता स्ट्रिंग के लिए क्षमता का मतलब है.
[Hardison] आह. >> है कि यह शब्द की अधिकतम लंबाई है. >> समझे.
हाँ. यहाँ क्षमता है कि एक बड़ा मुद्दा है.
और यह कुछ है कि मुश्किल है
क्योंकि हम यहाँ घोषित किया है जो चार * s की एक सरणी है.
संकेत की एक सरणी.
यह वर्ण की एक सरणी है.
शायद यह है कि आप क्या करते हैं जब आप फ़ाइल के लिए किया गया है अपने buffers की घोषणा देखा है मैं / हे,
जब तुम तार किया गया है मैन्युअल बनाने के ढेर पर.
हालांकि, हम यहाँ मिल गया है क्या * चार की एक सरणी है.
तो यह संकेत की एक सरणी है.
वास्तव में, अगर हम वापस बाहर ज़ूम और को हम देखते हैं यहाँ क्या हो रहा है
प्रस्तुति में, आपको लगता है कि वास्तविक तत्वों, चरित्र डेटा
सरणी के भीतर ही जमा नहीं है.
हमारे सरणी के भीतर यहाँ संग्रहीत क्या चरित्र डेटा के संकेत दिए गए हैं.
ठीक है. तो हमने देखा है कि कतार के आकार ढेर के साथ की तरह है,
आकार हमेशा तत्वों की संख्या वर्तमान का सम्मान कतार में.
2 enqueues करने के बाद, आकार 2 है.
एक विपंक्ति करने के बाद आकार अब है 1.
एक और enqueue करने के बाद आकार 2 के लिए वापस है.
तो आकार निश्चित रूप से कतार में तत्वों की संख्या का सम्मान करता है,
और फिर सिर सिर्फ साइकिल चालन रहता है.
यह 0-1-2, 0-1-2 0-1-2 से चला जाता है.
और हर बार हम विपंक्ति कॉल, सिर सूचक अगले सूचकांक incremented हो जाता है.
और अगर सिर खत्म हो जाने के बारे में है, यह चारों ओर 0 से वापस loops.
तो उस के साथ, हम विपंक्ति समारोह लिख सकते हैं.
और हम enqueue समारोह छोड़ने के बजाय के लिए आप लोगों को लागू करने के लिए जा रहे हैं.
>> जब हम हमारे कतार के एक तत्व बाहर विपंक्ति
पहली बात यह है कि डैनियल किया था जब हम ढेर के लिए पॉप समारोह लेखन शुरू कर दिया था?
मुझे कोई है जो अभी तक बात नहीं की है से सुना है.
चलो देखते हैं, साद, तुम्हें याद है डैनियल क्या पहली बात है जब वह पॉप लिखा है के रूप में किया था?
[साद] वहाँ है, यह था - >> वह कुछ के लिए परीक्षण किया गया.
साद] यदि आकार 0 से अधिक है. वास्तव में. >>
और के लिए कि परीक्षण क्या था?
[साद] यह देखने के लिए अगर वहाँ सरणी के अंदर कुछ भी परीक्षण किया गया.
[Hardison] हाँ. बिल्कुल सही. तो आप ढेर से बाहर कुछ भी नहीं पॉप अगर यह खाली है.
इसी तरह, आप एक कतार से कुछ भी नहीं विपंक्ति अगर यह खाली है सकते हैं.
पहली बात हम हमारे विपंक्ति समारोह में यहाँ क्या करना चाहिए क्या है, क्या लगता है?
साद] यदि आकार 0 से अधिक है? >> हाँ.
इस मामले में, मैं वास्तव में सिर्फ देखने के लिए अगर यह 0 है परीक्षण किया गया.
यदि यह 0 है, हम अशक्त लौट सकते हैं.
लेकिन सटीक एक ही तर्क है.
और इस के साथ जारी रखने के.
यदि आकार नहीं 0 है, जहां तत्व कि हम विपंक्ति करना चाहते है?
[साद] सिर? वास्तव में. >>
हम सिर्फ हमारे कतार में पहला तत्व खींच कर सकते हैं
सिर पर तत्व तक पहुँचने के द्वारा.
पागल कुछ भी नहीं है.
उसके बाद, हमें क्या करना चाहिए? क्या होता है?
दूसरी बात यह है कि हम विपंक्ति में के बारे में बात की थी क्या था?
दो बातें करने के लिए होता है, क्योंकि हमारे कतार बदल गया है.
[डैनियल] आकार को कम करें. >> हम आकार को कम करने के लिए, और सिर में वृद्धि करने के लिए है? बिल्कुल सही.
सिर को बढ़ाने के लिए, हम बस आँख बंद करके सिर में वृद्धि नहीं कर सकते हैं, याद है.
सिर्फ हम नहीं कर सकते हैं queue.head करना + +.
हम भी क्षमता से इस आधुनिक शामिल है.
और क्यों हम क्षमता द्वारा आधुनिक करते हैं, स्टैला?
स्टेला] क्योंकि यह चारों ओर लपेटो है. वास्तव में. >>
हम क्षमता द्वारा आधुनिक क्योंकि यह 0 से चारों ओर वापस लपेटो है.
तो अब, इस बिंदु पर, हम कर सकते हैं डैनियल ने क्या कहा है.
हम आकार घटती कर सकते हैं.
और फिर हम सिर्फ तत्व है कि कतार के शीर्ष पर था लौट सकते हैं.
यह किस तरह का ऐंठा हुआ लगता है पहली बार. आप एक सवाल हो सकता है. क्षमा करें?
>> [सैम] 1 पंक्ति के शीर्ष पर क्यों है? कि कहां जाना है?
[Hardison] यह नीचे से चौथी लाइन से आता है.
के बाद हम यह सुनिश्चित करना है कि हमारे कतार खाली नहीं है परीक्षण,
हम चार * 1 खींच, हम बाहर तत्व कि सिर सूचकांक पर बैठा है खींच
हमारे सरणी के, हमारे तार सरणी >>, और पहली बार है कि कॉल के?
[Hardison] और हम यह पहली बार कहते हैं. हाँ.
बस उस पर पालन करने के लिए, तुम क्यों लगता है कि हम ऐसा करने के लिए किया था?
[सैम] प्रत्येक 1 बस q.strings लौट रहा है [q.head?] >> हाँ.
>> क्योंकि हम आधुनिक समारोह के साथ q.head के इस बदलते कर रहे हैं,
और वहाँ कोई वापसी लाइन के भीतर भी है कि ऐसा करने के लिए एक रास्ता है.
[Hardison] बिल्कुल सही. आप मौके पर ही कर रहे हैं. सैम पर पूरी तरह से जगह है.
कारण है कि हम हमारे कतार में पहला तत्व खींचने के लिए और यह एक चर में संग्रहीत था
क्योंकि इस लाइन जहाँ हम सिर्फ q.head था,
वहाँ में माड आपरेटर कुछ है कि हम क्या कर सकते है नहीं है
एक पंक्ति में यह बिना सिर पर प्रभाव ले.
तो हम वास्तव में पहला तत्व खींच है, तो सिर को समायोजित करने के लिए,
आकार को समायोजित करने के लिए, और फिर लौटने के तत्व है कि हम बाहर खींच लिया.
और यह कुछ है कि हम आ देखेंगे के साथ बाद में
जुडी हुई सूचियों, के रूप में हम उनके साथ खेलने के आसपास.
अक्सर जब तुम मुक्त कर रहे हैं या लिंक सूचियों का निपटान
आप अगले तत्व, एक लिंक सूची के अगले सूचक को याद करने की जरूरत है
मौजूदा एक के निपटान से पहले.
क्योंकि अन्यथा आप क्या सूची में छोड़ दिया है की जानकारी दूर फेंक देते हैं.
अब, अगर आप अपने उपकरण के लिए जाना है, तो आप इस queue.c-x खुला बाहर.
तो अगर मैं queue.c खोलते हैं, तो यहाँ मुझे ज़ूम, चलो
आप देखेंगे कि आप एक समान दिखने वाले फ़ाइल है.
समान दिखने फ़ाइल क्या हम stack.c साथ पहले था.
हम बस के रूप में परिभाषित हम स्लाइड्स पर देखा कतार के लिए हमारे struct मिल गया है.
>> हम हमारे enqueue समारोह है जो आप करने के लिए है.
और हम विपंक्ति समारोह यहाँ है.
फ़ाइल में विपंक्ति समारोह लागू नहीं किया गया है,
लेकिन मैं इसे वापस डाल देंगे PowerPoint पर इतना है कि आप इसे में टाइप करें, यदि आप चाहें तो कर सकते हैं.
तो अगले 5 मिनट या ऐसा करने के लिए, आप लोग enqueue पर काम
जो लगभग सिर्फ विपंक्ति के विपरीत है.
आप सिर समायोजित जब आप enqueueing रहे हैं नहीं है, लेकिन क्या आप को समायोजित करने के लिए है?
आकार. तो जब आप enqueue, सिर अछूता रहता है, आकार में परिवर्तित हो जाता है.
लेकिन यह एक छोटा सा ले करता है - आप उस आधुनिक के साथ खेलने के आसपास होगा
बाहर ठीक आंकड़ा क्या सूचकांक नए तत्व में डाला जाना चाहिए.
तो मैं तुम लोगों को एक छोटा सा दे देंगे, स्लाइड पर वापस विपंक्ति डाल दिया,
और के रूप में आप लोगों को सवाल है, उन्हें चिल्लाओ बाहर इतना है कि हम कर सकते हैं
एक समूह के रूप में उनके बारे में सभी बात करते हैं.
इसके अलावा, आप नहींं आकार के साथ - जब आप के आकार को समायोजित करने के लिए, आप हमेशा ही कर सकते हैं -
आप आकार कभी आधुनिक है? [डैनियल] नहीं >> तुम आकार आधुनिक नहीं है, सही है.
क्योंकि आकार हमेशा, अगर तुम जाएगा - संभालने आप बातें कर रहे हैं उचित प्रबंध,
आकार हमेशा 0 और 3 के बीच होगा.
आप आधुनिक जब आप कर रहे हैं enqueue कहाँ है?
केवल सिर के लिए [छात्र]. सिर के लिए केवल >> बिल्कुल.
और आप सब पर enqueue में आधुनिक क्यों है?
जब ऐसी स्थिति में आप आधुनिक चाहते है?
[छात्र] यदि आप रिक्त स्थान पर सामान है, रिक्त स्थान 1 और 2 में करना चाहते हैं,
और फिर तुम 0 में कुछ जोड़ने की जरूरत है.
[Hardison] हाँ, बिल्कुल. तो अगर आपके सिर सूचक बहुत अंत में है,
या अगर अपने आकार प्लस अपने सिर बड़ा है या बल्कि, कतार के आसपास लपेटो करने के लिए जा रहा है.
>> तो इस स्थिति में है कि हम मिल गया है यहाँ स्लाइड पर अब सही,
अगर मैं अभी कुछ enqueue चाहते हैं,
हम 0 सूचकांक में कुछ enqueue चाहते हैं.
तो अगर आप जहां 50 चला जाता है पर देखो, और मैं enqueue 50 कहते हैं,
यह वहाँ नीचे चला जाता है नीचे. यह सूचकांक 0 में चला जाता है.
यह जगह 'हाय' है कि पहले से ही dequeued था.
[डैनियल] इस बात का ख्याल नहीं ले आप विपंक्ति में पहले से ही?
यह enqueue में सिर के साथ क्यों करता है कुछ भी करते हैं?
[Hardison] ओह, तो आप सिर नहीं संशोधित कर रहे हैं, माफ करना.
लेकिन आप माड आपरेटर के उपयोग जब आप पहुँच रहे हैं
तत्व है कि आप जब आप तक पहुँचने रहे हैं enqueue चाहते
अपनी कतार में अगले तत्व.
[तुलसी] मैं ऐसा नहीं था, और मैं वहाँ पर "सफलता" मिला.
[डैनियल] ओह, मैं समझता हूँ कि तुम क्या कह रहे हैं.
[Hardison] तो आप फ्लॉप - आप सिर्फ q.size में किया था?
[तुलसी] हाँ. मैं सिर्फ पक्षों बदल गया है, मैं सिर के साथ कुछ भी नहीं था.
[] Hardison आप वास्तव में सिर को पुनर्स्थापित करने के लिए कुछ भी हो सकता है नहीं है,
लेकिन तार सरणी में आप जब सूचकांक,
आप वास्तव में आगे जाना है और गणना के लिए जहां अगले तत्व है,
क्योंकि ढेर withe, अपने ढेर में अगले तत्व हमेशा था
आकार के लिए इसी सूचकांक में.
यदि हम हमारे ढेर धक्का समारोह में वापस देखो,
हम हमेशा सही सूचकांक आकार में हमारे नए तत्व में फेंकना सकता है.
जबकि कतार के साथ, हम ऐसा नहीं कर सकते
क्योंकि अगर हम इस स्थिति में हैं,
अगर हम 50 कतारबद्ध हमारे नए स्ट्रिंग सही [1] तार पर जाना होगा
जो हमें नहीं करना चाहती.
हम नए स्ट्रिंग 0 सूचकांक में जाना चाहते हैं.
>> किसी को भी - हाँ? [छात्र] मैं एक सवाल है, लेकिन यह वास्तव में संबंधित नहीं है.
यह क्या होता है जब किसी को सिर्फ कॉल pred सूचक की तरह कुछ मतलब है?
कि नाम क्या है के लिए कम? मुझे पता है कि यह सिर्फ एक नाम है.
[Hardison] Pred सूचक है? चलो देखते हैं. किस संदर्भ में?
[छात्र] यह डालने के लिए किया गया था. मैं तुम्हें पूछने के बाद अगर आप चाहते हैं
क्योंकि यह वास्तव में संबंधित नहीं है, लेकिन मैं सिर्फ -
[Hardison] दाऊद के व्याख्यान से डालने के कोड से?
हम जानते हैं कि खींच कर सकते हैं और इस बारे में बात.
हम कि अगले, एक बार हम लिंक सूचियों को पाने के बारे में बात करेंगे.
>> तो सच में जल्दी चलो enqueue समारोह की तरह लग रहा है पर देखो.
पहली बात यह है कि लोगों को अपने enqueue लाइन में करने की कोशिश की क्या था? इस कतार में?
तुम क्या धकेलने के ढेर के लिए किया था के लिए भी इसी तरह.
आप क्या किया, स्टेला?
[स्टैला, unintelligible]
[Hardison] बिल्कुल सही. यदि (== क्षमता q.size)
मैं सही जगह में मेरी ब्रेसिज़ डाल की जरूरत है - वापसी झूठी.
एक छोटा सा में ज़ूम. ठीक है.
अब अगली बात यह है कि हम करना पड़ा है?
बस ढेर के साथ करना चाहते हैं, और सही जगह पर डाला.
और इसलिए सही है कि डालने के जगह क्या था?
ढेर के साथ यह सूचकांक आकार का था, इस के साथ यह नहीं है कि काफी है.
[डैनियल] मैं q.head या - >> q.strings? >> हाँ.
q.strings [q.head q.size + आधुनिक क्षमता]?
[Hardison] हम शायद इस के आसपास कोष्ठक डाल करना चाहते हैं
ताकि हम उपयुक्त पूर्वता हो रही है और इसलिए है कि हर किसी के लिए cleart है.
सेट और कहा कि बराबर है? Str करने के लिए? >> Str करने के लिए. >> बढ़िया है.
और अब आखिरी बात यह है कि हमें क्या करना है क्या है?
वैसे ही जैसे हम ढेर में किया था. >> आकार बढ़त? >> आकार बढ़त.
बूम. और फिर, स्टार्टर कोड के बाद से बस डिफ़ॉल्ट रूप से झूठी लौटे,
हम सच करने के लिए इस बदल सकता है अगर सभी के माध्यम से चला जाता है और सब कुछ अच्छी तरह से चला जाता है चाहता हूँ.
सही सभी. अनुभाग के लिए जानकारी का एक बहुत कुछ है.
हम काफी खत्म नहीं कर रहे हैं. हम अकेले लिंक सूचियों के बारे में वास्तव में जल्दी से बात करना चाहता हूँ.
मैं इस डाल तो हम इसे वापस करने के बाद जा सकते हैं.
लेकिन हमारे प्रस्तुति के लिए अभी कुछ और स्लाइड के लिए वापस जाना.
तो enqueue TODO है, अब हम इसे किया है.
>> अब चलो अकेले लिंक सूचियों पर एक नज़र रखना.
हम व्याख्यान में ये एक छोटा सा के बारे में अधिक बात की थी.
तुम लोगों में से कितने डेमो देखा जहां हम लोग थे
awkwardly एक दूसरे को और होल्डिंग संख्या की ओर इशारा करते हैं? >> मैं उस में था.
>> तुम लोगों को क्या लगता है? किया है कि, उम्मीद है कि ये एक छोटा सा demystify?
एक सूची के साथ, यह पता चला है कि हम इस प्रकार के साथ सौदा है कि हम एक नोड फोन करने के लिए जा रहे हैं.
जबकि कतार और ढेर के साथ हम structs कि हम ढेर में कतार फोन था था,
हम ढेर प्रकार में इन नए कतार थी,
यहाँ एक सूची वास्तव में सिर्फ नोड्स के एक गुच्छा के ऊपर बनाया है.
एक ही तरीका है कि तार सिर्फ वर्ण की एक गुच्छा रहे हैं सभी एक दूसरे के बगल में खड़े हैं.
एक लिंक की गई सूची में सिर्फ एक नोड और एक अन्य नोड और अन्य नोड और किसी अन्य नोड है.
और नहीं बल्कि सभी नोड्स के साथ मुंहतोड़ और उन्हें contiguously से भंडारण की तुलना में
सही स्मृति में सभी एक दूसरे के बगल में,
यह अगले सूचक होने के हमें जहाँ भी नोड्स के स्टोर करने के लिए यादृच्छिक पर, की अनुमति देता है.
और फिर तार की तरह उन सब को एक साथ करने के लिए एक से दूसरे बात करने के लिए.
>> और क्या बड़ा लाभ यह है कि यह एक सरणी पर था?
भंडारण सब कुछ खत्म contiguously सिर्फ एक दूसरे के बगल में फंस रहे हैं?
तुम्हें याद है? हाँ? >> गतिशील स्मृति आवंटन?
>> गतिशील स्मृति आवंटन में क्या अर्थ है?
[छात्र] है कि आप यह बड़ा है और आप अपने पूरे सरणी कदम नहीं है बनाने रखने के लिए कर सकते हैं?
[Hardison] बिल्कुल सही. तो एक सरणी के साथ, जब आप इसे के बीच में एक नए तत्व डाल करना चाहते हैं
आप के लिए सब कुछ बदलाव करने के लिए जगह बनाने के है.
और जैसे हम कतार के साथ के बारे में बात की थी,
यही कारण है कि हम है कि सिर सूचक रखने,
इतना है कि हम लगातार बातें नहीं जा रहे हैं.
क्योंकि महंगा हो जाता है कि अगर आप एक बड़ा सरणी मिल गया है
और आप लगातार इन बेतरतीब सम्मिलन कर रहे हैं.
जबकि एक सूची के साथ, सब तुम्हें क्या करना है यह एक नया नोड पर फेंक देते हैं,
संकेत को समायोजित करने के लिए, और आप कर रहे हैं.
क्या इस बारे में बेकार है?
अलावा तथ्य यह है कि यह आसान के रूप में एक सरणी के रूप में साथ काम नहीं? हाँ?
[डैनियल] खैर, मुझे लगता है कि यह बहुत कठिन है लिंक की गई सूची में एक विशिष्ट तत्व का उपयोग?
[Hardison] तुम सिर्फ अपने लिंक सूची के बीच में एक मनमाना तत्व नहीं कूद कर सकते हैं.
बजाय आप इसे कैसे करना है? >> आप पूरी बात के माध्यम से कदम है.
[Hardison] हाँ. आप एक समय में, एक एक समय में एक के माध्यम से जाना है.
यह एक बहुत बड़ा है - यह एक दर्द है.
अन्य क्या है - वहाँ इस के लिए एक पतन है.
[तुलसी] आप आगे और पीछे की ओर नहीं जा सकते? आप एक दिशा में जाने के लिए है?
[Hardison] हाँ. तो कैसे हम कभी कभी को हल करने के लिए,?
[तुलसी] सूचियों दोगुना से जुड़े? वास्तव में. >> दोगुना से जुड़े सूचियों हैं.
वहाँ भी कर रहे हैं - खेद?
>> [सैम] कि pred बात यह है कि का उपयोग कर के रूप में एक ही है -
मुझे अभी याद नहीं है कि pred बात के लिए क्या है?
में दोगुना और अकेले के बीच नहीं है?
वास्तव में वह क्या कर रहा था पर [Hardison] चलो देखो.
तो यहाँ हम चले. यहाँ सूची कोड है.
हम यहाँ predptr यहाँ है. यह है कि आप किस बारे में बात कर रहे थे?
तो यह था - वह मुक्त एक सूची है और वह इसे करने के लिए एक सूचक की दुकान की कोशिश कर रहा है.
यह दोगुना अकेले, लिंक सूची नहीं है.
हम इस बारे में और अधिक सूची को मुक्त कराने के बारे में बाद में बात कर सकते हैं, के बाद से यह बात कर रही है
और मैं कुछ अन्य सामान पहले दिखाना चाहते हैं.
लेकिन यह सिर्फ यह ptr के मूल्य याद है
[छात्र] ओह, यह पूर्ववर्ती सूचक है? >> हाँ.
तो है कि हम तो पहले हम तो मुक्त predptr क्या है ptr ही वेतन वृद्धि कर सकते हैं.
क्योंकि हम मुक्त ptr और फिर ptr = ptr अगले, है ना? फोन नहीं कर सकते
यह बुरा होगा.
तो देखते हैं, इस आदमी के लिए वापस.
>> सूचियों के बारे में अन्य बुरी बात यह है कि जबकि एक सरणी के साथ
हम सिर्फ सभी तत्वों को खुद को एक दूसरे के बगल में stacked है,
यहाँ हम भी यह सूचक पेश किया है.
तो वहाँ स्मृति के एक अतिरिक्त हिस्सा है कि हम का उपयोग कर रहे हैं
हर तत्व है कि हम हमारी सूची में भंडारण कर रहे हैं के लिए.
हम लचीलापन मिलता है, लेकिन यह एक कीमत पर आता है.
यह इस समय और लागत के साथ आता है,
और यह इस स्मृति लागत के साथ भी आता है.
भावना में समय है कि हम अब सरणी में प्रत्येक तत्व के माध्यम से जाना है
10 सूचकांक में एक, या 10 सूचकांक एक सरणी में होता है कि लगता है.
>> सिर्फ सच में जल्दी से, जब हम बाहर इन सूचियों आरेख,
आम तौर पर हम सूची के सिर या सूची की पहली सूचक पर पकड़
और ध्यान दें कि यह एक सच सूचक है.
यह सिर्फ 4 बाइट्स है. यह एक वास्तविक नोड ही नहीं है.
तो आप देखते हैं कि यह उस में नहीं int मूल्य में कोई अगली सूचक है.
यह सचमुच सिर्फ एक सूचक है.
यह करने के लिए कुछ है कि एक वास्तविक नोड struct है इंगित करने के लिए जा रहा है.
[सैम] एक नोड बुलाया सूचक है? >> यह है - नहीं. इस प्रकार नोड के कुछ करने के लिए एक सूचक है.
यह एक नोड struct एक सूचक है. >> ओह, ठीक है.
सही पर छोड़ दिया कोड, पर आरेख.
हम यह अशक्त है, जो एक अच्छा तरीका शुरू करने के लिए सेट कर सकते हैं.
जब आप इसे आरेख, आप या तो यह शून्य के रूप में लिखने के लिए या आप इसे माध्यम से एक लाइन डाल की तरह है कि.
>> एक सूची के साथ काम करने के लिए सबसे आसान तरीकों में से एक है,
और हम तुम दोनों प्रीपेंड पूछना है और दोनों के बीच मतभेद को देखने के परिशिष्ट के रूप में लगाना,
लेकिन prepending निश्चित रूप से आसान है.
जब आप prepend, यह तुम कहाँ है - जब आप प्रीपेंड (7),
तुम जाओ और नोड struct बनाने
और आप पहली बार यह बात है, क्योंकि अब, जब से हम इसे सम्पन्न
यह करने के लिए सूची की शुरुआत में होने जा रहा है.
यदि हम प्रीपेंड (3), कि एक और नोड बनाता है, लेकिन अब 3 7 से पहले आता है.
तो हम हमारी सूची पर अनिवार्य रूप से कर रहे हैं बातें धक्का.
अब, आप देख सकते हैं कि प्रीपेंड, कभी कभी लोगों को फोन इसे धक्का,
क्योंकि आप अपनी सूची पर जोर दे रहे हैं एक नए तत्व.
यह भी एक सूची के मोर्चे पर हटाना आसान नहीं है.
तो लोगों को अक्सर है कि पॉप कहते हैं जाएगा.
और उस रास्ते में, आप एक ढेर एक लिंक सूची का उपयोग का अनुकरण कर सकते हैं.
वूप्स. क्षमा करें, अब हम संलग्न में हो रही है. यहाँ तो हम (7) सम्पन्न, अब हम प्रीपेंड (3).
यदि हम इस सूची पर सब कुछ सम्पन्न, अगर हम सम्पन्न (4),
तो हम 4 है और फिर 3 और फिर 7.
तो फिर हम पॉप और 4 को निकालने के लिए, 3 हटायें, 7 को हटा दें.
अक्सर इस बारे में सोचने के लिए अधिक सहज तरीका संलग्न के साथ है.
तो मैं बाहर diagrammed है कि यह क्या साथ यहाँ परिशिष्ट के रूप में लगाना तरह लग रही होगी.
यहाँ, संलग्न (7) कोई अलग नहीं लगती है
क्योंकि वहाँ केवल सूची में एक तत्व है.
और appending (3) यह अंत में डालता है.
शायद तुम सही अब संलग्न के साथ चाल देख सकते हैं
वह यह है कि जब से हम सिर्फ इतना पता है कि जहां सूची की शुरुआत है,
एक सूची आप सूची के माध्यम से सभी तरह चलना है संलग्न
अंत करने के लिए, बंद करो, तो अपने नोड और खनखनाहट नीचे सब कुछ का निर्माण.
सब सामान तार.
तो प्रीपेंड साथ, के रूप में हम सिर्फ इस के माध्यम से बहुत जल्दी फट,
जब आप एक सूची से जोड़ें, यह काफी आसान है.
>> आप अपने नए नोड बनाने के लिए, कुछ गतिशील स्मृति आवंटन शामिल है.
तो यहाँ हम एक नोड struct बनाने malloc का उपयोग कर रहे हैं.
Malloc तो हम क्योंकि है कि एक तरफ के लिए बाद में हमारे लिए स्मृति सेट का उपयोग कर रहे हैं
- हम इस स्मृति एक लंबे समय के लिए जारी रहती है क्योंकि हम यह नहीं चाहता चाहते हैं.
और हम है कि हम सिर्फ आवंटित स्मृति में अंतरिक्ष के लिए एक सूचक मिलता है.
हम नोड के आकार का उपयोग करें, हम इस क्षेत्र की राशि नहीं है.
हम स्वयं बाइट्स की संख्या उत्पन्न नहीं करते हैं,
बजाय हम sizeof इतना है कि हम जानते हैं कि हम बाइट्स की उचित संख्या में हो रही है का उपयोग करें.
हम कि हमारे malloc कॉल सफल परीक्षण करने के लिए सुनिश्चित कर लें.
यह कुछ आप सामान्य रूप में करना चाहते हैं.
आधुनिक मशीनों पर स्मृति से बाहर चल रहे कुछ है कि आसान नहीं है
जब तक आप सामान की एक टन का आवंटन कर रहे हैं और एक विशाल सूची बनाने,
लेकिन अगर आप एक iPhone या एक Android की तरह का निर्माण कर रहे हैं, कहते हैं, के लिए सामान,
आप सीमित स्मृति संसाधन है, खासकर यदि आप तीव्र कुछ कर रहे हैं.
तो यह अच्छी बात है कि व्यवहार में लाने के.
>> सूचना है कि मैं कुछ अलग कार्यों का उपयोग किया है यहाँ
कि तुम्हें देखा है कि नई की तरह कर रहे हैं.
तो fprintf सिर्फ printf की तरह है
अपनी पहली तर्क को छोड़कर स्ट्रीम करने के लिए जो आप मुद्रित करना चाहते है.
इस मामले में, हम मानक त्रुटि स्ट्रिंग मुद्रित करना चाहते हैं
है जो मानक outstream से अलग है.
मूलभूत रूप से यह एक ही स्थान में पता चलता है.
यह भी टर्मिनल से बाहर प्रिंट, लेकिन आप यह कर सकते हैं -
उन आदेशों का उपयोग आप के बारे में, redirection तकनीक सीखा
आप टॉमी वीडियो में के बारे में समस्या 4 सेट के लिए सीखा है, तो आप यह प्रत्यक्ष कर सकते हैं
विभिन्न क्षेत्रों के लिए, तो बाहर निकलने के लिए, यहीं, अपने कार्यक्रम से बाहर निकालता है.
यह मुख्य से लौटने की तरह अनिवार्य है,
छोड़कर हम बाहर निकलें का उपयोग करें, क्योंकि यहां वापसी कुछ नहीं करेंगे.
हम मुख्य में नहीं कर रहे हैं, तो कार्यक्रम की तरह हम चाहते लौटने से बाहर नहीं निकलते है.
तो हम बाहर निकलें समारोह का उपयोग करें और यह एक त्रुटि कोड दे.
यहाँ तो हम नए नोड मान फ़ील्ड, मैं अपने क्षेत्र की स्थापना की मैं बराबर हो सकता है, और फिर हम इसे तार.
हम नए नोड अगले सूचक सेट करने के लिए पहली बात है,
और फिर 1 अब नए नोड के लिए बात करेंगे.
कोड की ये पहली लाइनों, हम वास्तव में नए नोड का निर्माण कर रहे हैं.
इस समारोह के पिछले दो लाइनें लेकिन पहले वाले.
आप वास्तव में एक समारोह में बाहर खींच सकते हैं, एक सहायक समारोह में.
यह अक्सर है कि मुझे क्या करना है, मैं इसे एक समारोह में बाहर खींच,
मैं यह निर्माण नोड की तरह कुछ कहते हैं,
और कहा कि प्रीपेंड समारोह बहुत छोटा रहता है, यह सिर्फ 3 लाइनों है तो.
मैं मेरी नोड समारोह का निर्माण करने के लिए एक फोन बनाने के लिए, और फिर मैं तार को सब कुछ.
>> अंतिम बात मैं तुम्हें दिखाने के लिए करना चाहते हैं,
और मैं हूँ आप अपने दम पर संलग्न और कहा कि सभी करते हैं,
कैसे एक सूची पुनरावृति को.
वहाँ एक सूची पुनरावृति अलग तरीके का एक गुच्छा रहे हैं.
इस मामले में, हम एक सूची की लंबाई को खोजने के लिए जा रहे हैं.
तो हम = 0 लंबाई के साथ शुरू करते हैं.
यह बहुत एक स्ट्रिंग के लिए strlen लेखन के लिए इसी तरह की है.
यह है कि क्या मैं तुम्हें दिखाने के लिए, यह सही यहाँ पाश के लिए चाहते हैं.
यह थोड़े कायरता लग रहा है, यह सामान्य नहीं है int i = 0, मैं जो कुछ भी <, मैं + +.
इसके बजाय यह हमारे चर n आरंभ करने के लिए सूची की शुरुआत हो.
और फिर, जबकि हमारे iterator चर रिक्त नहीं है, हम रख रहा है.
इस वजह से, सम्मेलन द्वारा हमारी सूची के अंत रिक्त हो जाएगा.
और फिर, + + करने के बजाय वेतन वृद्धि करने के लिए,
जुड़े + की सूची बराबर + n n => अगले है.
>> मैं आप यहाँ अंतराल में भर जाने के कारण हम समय से बाहर हो जाएगा.
लेकिन यह ध्यान में रखना के रूप में आप अपने spellr psets पर काम.
लिंक सूचियों, अगर आप एक हैश तालिका को लागू कर रहे हैं,
निश्चित रूप से बहुत काम में आ जाएगा.
और इस मुहावरा होने बातों पर पाशन के लिए एक जीवन बहुत आसान बनाने के लिए, उम्मीद है.
कोई प्रश्न, जल्दी?
[सैम] पूरा sll और सुप्रीम कोर्ट भेज देंगे?
[Hardison] हाँ. मैं पूरा स्लाइड और पूरा sll ढेर और queue.cs भेज देंगे.
[CS50.TV]