>> [संगीत बजाना]
>> डौग लॉयड: ठीक है, पर ऐसा पाठ्यक्रम में इस बिंदु पर,
हम सी के मूल के एक बहुत कुछ शामिल है हम, चर, सरणियों के बारे में बहुत कुछ पता
संकेत दिए गए, यह सब अच्छी चीजें।
उन सभी तरह के निर्माण कर रहे हैं में, बुनियादी बातों के रूप में देखने के लिए
लेकिन हम सही, अधिक कर सकते हैं?
हम चीजों को जोड़ सकते हैं एक साथ रोचक तरीके से।
>> और तो चलो शुरू करते हैं, चलो करते हैं सी हमें देता है क्या से बाहर शाखा करने के लिए,
और हमारे अपने डेटा बनाने के लिए शुरू इन इमारत का उपयोग संरचनाओं
एक साथ ब्लॉकों कुछ करने के लिए उपयोगी है, वास्तव में मूल्यवान।
हम यह कर सकते एक ही रास्ता है संग्रह के बारे में बात करने के लिए।
इसलिए अब तक हम डेटा की एक तरह लिया है संग्रहों का प्रतिनिधित्व करने के लिए संरचना
के मूल्यों, समान मूल्यों पसंद है।
यही कारण है कि एक सरणी होगा।
हम पूर्णांकों का संग्रह है, या इतने पर अक्षर और का संग्रह।
>> संरचनाएं भी एक डेटा की तरह कर रहे हैं जानकारी इकट्ठा करने के लिए संरचना,
लेकिन यह मूल्यों की तरह इकट्ठा करने के लिए नहीं है।
यह आमतौर पर विभिन्न प्रकार के डेटा घोला जा सकता है एक साथ एक बॉक्स के अंदर।
लेकिन यह अपने आप में नहीं है एक साथ श्रृंखला के लिए इस्तेमाल किया
या एक साथ इसी तरह कनेक्ट एक सरणी की तरह आइटम,।
सारणियों के लिए महान हैं तत्व को देखने, लेकिन याद
यह बहुत मुश्किल है कि एक सरणी में सम्मिलित करने के लिए,
हम पर डालने रहे हैं जब तक उस सरणी के बहुत अंत।
>> और सबसे अच्छा उदाहरण मेरे पास है उस के लिए प्रविष्टि तरह है।
आप हमारे वीडियो को याद करते हैं प्रविष्टि प्रकार पर,
इसकी बड़ी मात्रा मौजूद थी व्यय होने में शामिल
तत्व उठा, और उन्हें शिफ्ट करने के लिए कुछ फिट करने के लिए जिस तरह से बाहर
अपने सरणी के बीच में।
सारणियों भी दूसरे से पीड़ित समस्या यह है कि जो दृढ़ता है।
हम एक सरणी की घोषणा करते हैं, हम इसे एक शॉट मिलता है।
हम मैं चाहता हूँ, कहने के लिए मिल यह कई तत्वों।
100 हो सकता है, यह हो सकता है 1,000 हो सकता है, यह हो सकता है
X उपयोगकर्ता है कि एक संख्या है, जहां एक्स होना एक प्रॉम्प्ट पर या आदेश पर हमें दिया
लाइन।
>> लेकिन हम केवल इसे एक शॉट मिलता है, हम मैं वास्तव में, तो ओह कहने के लिए नहीं मिलता
101 की जरूरत है, या मैं एक्स प्लस 20 की जरूरत है।
बहुत देर हो गई है, हम पहले से ही घोषित कर दिया है सरणी, और हम 101 या प्राप्त करना चाहते हैं एक्स
प्लस 20, हम घोषणा की है एक पूरी तरह से अलग सरणी,
सरणी के सभी तत्वों को कॉपी से अधिक है, और फिर हम पर्याप्त है।
और हम फिर से गलत कर रहे हैं तो क्या, क्या हम वास्तव में 102, या एक्स प्लस 40 की जरूरत है,
हम फिर से ऐसा करने के लिए है।
इसलिए वे बहुत कड़ा हो हमारे डेटा का आकार बदलने के लिए,
लेकिन हम एक साथ कुछ गठबंधन हम पहले से ही है कि मूल के
संकेत और संरचना के बारे में सीखा है, विशेष रूप से गतिशील स्मृति का उपयोग
malloc साथ आवंटन, हम एक साथ इन टुकड़ों को डाल सकते हैं
एक नए डेटा structure-- एक बनाने के लिए अकेले हम say-- सकता सूची से जुड़े
कि हमें विकसित करने के लिए अनुमति देता है और मूल्यों का एक संग्रह हटना
और हम किसी भी बर्बाद अंतरिक्ष की जरूरत नहीं होगी।
>> तो फिर, हम इस विचार को कहते हैं, इस धारणा, एक लिंक सूची।
विशेष रूप से, इस वीडियो में हम कर रहे हैं अकेले लिंक सूची के बारे में बात कर रही है,
और फिर एक और वीडियो हम बात करेंगे के बारे में दोगुना लिंक सूचियों, जो
यहाँ एक विषय पर सिर्फ एक भिन्नता है।
लेकिन एक अकेले लिंक सूची नोड्स के शामिल है,
नोड्स सिर्फ एक सार term-- किया जा रहा है यह मैं बोल रहा हूँ बस कुछ है
इस बात का एक प्रकार है संरचना, मूल रूप से, मैं कर रहा हूँ?
बस इसे एक node-- और इस फोन करने वाला नोड दो सदस्यों, या दो क्षेत्रों है।
यह आमतौर पर एक डेटा है, पूर्णांक, एक चरित्र नाव,
या कुछ अन्य डेटा प्रकार हो सकता है आप एक प्रकार डेफ के साथ परिभाषित किया है।
और यह करने के लिए एक सूचक होता है एक ही प्रकार के अन्य नोड।
>> इसलिए हम के अंदर दो बातें हैं इस नोड, डेटा और एक सूचक
अन्य नोड के लिए।
और अगर आप कल्पना करने के लिए शुरू करते हैं यही नहीं, आप इसके बारे में सोच सकते हैं
नोड्स की एक श्रृंखला की तरह है कि एक साथ जुड़े हुए हैं।
हम पहला नोड है, यह डेटा, और एक सूचक होता है
शामिल है जो दूसरे नोड के लिए डेटा, और तीसरे नोड के लिए एक सूचक।
और इतना है कि हम इसे एक फोन क्यों है लिंक सूची, वे एक साथ जुड़े रहे हैं।
>> इस खास क्या करता है नोड संरचना की तरह लग रही है?
ठीक है, तुम पर हमारे वीडियो से याद करते हैं प्रकार डेफ के साथ कस्टम प्रकार परिभाषित करने,
हम एक structure-- परिभाषित कर सकते हैं और इस तरह एक संरचना को परिभाषित लिखें।
संरचना sllist tyepdef, और फिर मैं कर रहा हूँ मनमाने ढंग से यहाँ शब्द मूल्य का उपयोग
वास्तव में किसी भी डेटा प्रकार का संकेत।
तुम्हें पता है, एक पूर्णांक या नाव पर पारित कर सकता है आप जो चाहे कर सकता था।
यह सिर्फ तक ही सीमित नहीं है पूर्णांकों, या ऐसा कुछ।
तो मूल्य सिर्फ एक मनमाना है फिर डेटा प्रकार, और एक सूचक
एक ही प्रकार के अन्य नोड के लिए।
>> अब, एक छोटे से पकड़ है यहां एक संरचना को परिभाषित करने के साथ
जब यह एक आत्म referential संरचना है।
मैं एक अस्थायी के लिए है मेरी संरचना के लिए नाम है।
दिन के अंत में यह स्पष्ट रूप से फोन करना चाहते हैं
SLL नोड, कि अंततः नया है मेरी तरह परिभाषा के भाग का नाम,
लेकिन मैं SLL नोड का उपयोग नहीं कर सकते इस के बीच में।
कारण किया जा रहा है, मैं नहीं है एक प्रकार कहा जाता SLL नोड बनाया
मैं यहाँ इस अंतिम बिंदु मारा जब तक।
उस बिंदु तक, मैं करने के लिए है एक और तरीका यह डेटा प्रकार का उल्लेख करने के लिए।
>> और यह एक आत्म है निर्देशात्मक डेटा प्रकार।
यह एक के एक डेटा प्रकार है एक डेटा वाली संरचना,
और एक अन्य के लिए एक सूचक एक ही प्रकार की संरचना।
इसलिए मैं उल्लेख करने के लिए सक्षम होने की जरूरत इस डेटा प्रकार कम से कम अस्थायी रूप से,
इसलिए यह एक अस्थायी दे रही है संरचना sllist के नाम
मुझे तो लगता है मैं एक चाहते कहने के लिए अनुमति देता है एक और संरचना sllist करने के लिए सूचक,
एक संरचना sllist स्टार, और उसके बाद मैं परिभाषा पूरा करने के बाद,
मैं अब इस प्रकार के एक SLL नोड कॉल कर सकते हैं।
>> आप देख वहाँ इतना है कि क्यों यहां एक अस्थायी नाम,
लेकिन यहाँ एक स्थायी नाम।
कभी-कभी आप देख सकते हैं संरचना की परिभाषा
उदाहरण के लिए, कि नहीं कर रहे हैं आत्म referential, कि
यहां एक विनिर्देशक नाम नहीं है।
यह सिर्फ typedef struct कहेंगे घुंघराले ब्रेस खोलने के लिए और फिर इसे परिभाषित करते हैं।
आप कर रहे हैं लेकिन अगर संरचना आत्म है निर्देशात्मक, यह एक है, के रूप में
आप एक निर्दिष्ट करने की आवश्यकता अस्थायी प्रकार का नाम।
लेकिन अंततः, अब हम इस किया है कि,
हम सिर्फ उल्लेख कर सकते हैं इन नोड्स, इन इकाइयों,
प्रयोजनों के लिए SLL नोड्स के रूप में इस वीडियो के बाकी की।
>> ठीक है, तो हम कैसे पता एक लिंक सूची नोड बनाने।
हम परिभाषित करने के लिए पता एक लिंक सूची नोड।
अब, हम शुरू करने के लिए जा रहे हैं जानकारी इकट्ठा करने के लिए उन्हें का उपयोग कर,
आपरेशनों की एक जोड़ी है हम समझने के लिए और के साथ काम करने की जरूरत है।
हम बनाने के लिए पता करने की जरूरत है पतली हवा से बाहर एक लिंक सूची।
कोई सूची पहले से ही नहीं है, हम एक शुरू करने के लिए चाहते हैं।
तो हम सक्षम होने की जरूरत एक लिंक सूची बनाने के लिए,
हम शायद खोज करने की जरूरत लिंक सूची के माध्यम से
हम देख रहे हैं एक तत्व खोजने के लिए।
हम सम्मिलित करने में सक्षम होने की जरूरत है सूची में नई चीजों की,
हम हमारी सूची में विकसित करने के लिए सक्षम होना चाहता हूँ।
और इसी तरह, हम सक्षम होना चाहता हूँ हमारी सूची से चीजों को नष्ट करने,
हम हमारी सूची हटना करने में सक्षम होना चाहता हूँ।
और अंत में हमारे कार्यक्रम, विशेष रूप से
आप हम कर रहे हैं कि याद करते हैं गतिशील स्मृति आवंटन
आम तौर पर इन सूचियों का निर्माण करने के लिए, हम चाहते हैं कि स्मृति के सभी मुक्त करना चाहते हैं
हम उसके साथ काम कर रहे हैं जब।
और इसलिए हम एक नष्ट करने में सक्षम होने की जरूरत है एक में पूरे लिंक सूची झपट्टा असफल।
तो चलो के माध्यम से चलते हैं इन कार्यों में से कुछ
और हम उन्हें कल्पना कैसे हो सकता है, विशेष रूप से स्यूडोकोड कोड में बात कर रही है।
तो हम एक बनाना चाहते हैं सूची से जुड़ा हुआ है, तो शायद हम
एक समारोह को परिभाषित करना चाहते हैं इस प्रोटोटाइप के साथ।
SLL नोड स्टार, बनाते हैं, और मैं गुजर रहा हूँ एक तर्क में, कुछ मनमाने ढंग से डेटा
कुछ मनमाने ढंग से डेटा प्रकार की, फिर से लिखें।
लेकिन मैं इस समारोह चाहिए returning-- रहा हूँ एक अकेले करने के लिए, मेरे लिए एक सूचक लौटने
लिंक सूची नोड।
फिर, हम बनाने की कोशिश कर रहे हैं पतली हवा से बाहर एक लिंक सूची,
इसलिए मुझे लगता है के लिए एक संकेत की जरूरत है मैं कर रहा हूँ कि जब सूची।
>> यहाँ तो शामिल कदम क्या कर रहे हैं?
खैर, जब मैं पहली बार बात कर रहा हूँ क्या करने जा गतिशील है
एक नए नोड के लिए जगह आवंटित।
फिर, हम पतली से बाहर बना रहे हैं हवा, इसलिए हम इसके लिए malloc अंतरिक्ष की जरूरत है।
और जाहिर है, तुरंत हम malloc के बाद,
हम हमेशा यकीन है कि बनाने के लिए जाँच हमारी pointer-- हम वापस अशक्त नहीं मिला।
हम कोशिश करते हैं क्योंकि अगर और एक शून्य सूचक सम्मान में,
हम एक पीड़ित करने के लिए जा रहे हैं SEGFAULT और हम नहीं चाहते कि।
>> तो फिर हम इस क्षेत्र में भरना चाहते हैं, हम मूल्य क्षेत्र को प्रारंभ करना चाहते हैं
और अगले क्षेत्र को प्रारंभ।
और फिर हम अंततः के रूप है-- चाहते हैं हम चाहते हैं indicates-- समारोह प्रोटोटाइप
एक SLL नोड के लिए एक सूचक लौटने के लिए।
तो क्या इस नेत्रहीन तरह लग रही है?
खैर, सबसे पहले हम गतिशील करने के लिए जा रहे हैं एक नए SLL नोड के लिए जगह आवंटित,
इसलिए हम यह है कि malloc-- एक दृश्य प्रतिनिधित्व
नोड के हम अभी बनाया।
और हम सुनिश्चित करने के लिए जाँच यह इस मामले में null-- नहीं है
तस्वीर नहीं होता यह शून्य था, तो ऊपर दिखाया गया है,
हम स्मृति से बाहर चला जाएगा इसलिए हम वहाँ जाने के लिए अच्छे हैं।
तो अब हम सी कदम पर कर रहे हैं, नोड्स मूल्य क्षेत्र को प्रारंभ।
खैर, इस समारोह पर आधारित , मैं यहाँ का उपयोग कर रहा हूँ फोन
मैं 6 में पारित करने के लिए चाहता हूँ की तरह लग रहा है, इसलिए मैं मान क्षेत्र में 6 हूँ।
अब, अगले क्षेत्र को प्रारंभ।
खैर, क्या मैं वहां क्या करने जा रहा हूँ, कुछ भी नहीं है, ठीक बगल में है,
इस सूची में केवल एक ही चीज़ है।
तो सूची में अगले बात क्या है?
>> यह ठीक है, कुछ भी करने के लिए बात नहीं करना चाहिए।
कुछ नहीं तो क्या है, और वहाँ नहीं है हम इस बात का पता है अवधारणा nothing-- है
कुछ भी नहीं करने के संकेत?
यह हो सकता है कि हम चाहते हैं होना चाहिए वहाँ एक शून्य सूचक डाल करने के लिए,
और मैं अशक्त प्रतिनिधित्व करेंगे , के रूप में सिर्फ एक लाल बॉक्स सूचक
हम किसी भी आगे नहीं जा सकते।
हम बाद में एक छोटे से देखेंगे, हम अंततः चेन होगा
तीरों के जोड़ने एक साथ इन नोड्स,
लेकिन आप जब मारा लाल बॉक्स, कि, अशक्त है
हम किसी भी आगे नहीं जा सकते उस सूची के अंत में है।
>> और अंत में, हम सिर्फ करना चाहते हैं इस नोड के लिए एक सूचक लौट आते हैं।
इसलिए हम नए फोन करता हूँ, और नए वापस आ जाएगी
तो यह किया जा सकता है जो कुछ भी समारोह इसे बनाया।
इसलिए हम वहाँ जाते हैं, हम एक अकेले बना लिया है पतली हवा से बाहर लिंक सूची नोड,
और अब हम साथ काम कर सकते हैं एक सूची है।
>> अब, हम पहले से ही हम हम कहते हैं एक बड़ी श्रृंखला है,
और हम उस में कुछ खोजने के लिए चाहते हैं।
और हम जा रहा है कि एक समारोह चाहते हैं सही है या गलत लौटने के आधार पर करने के लिए
एक मूल्य है कि सूची में मौजूद है पर।
एक समारोह प्रोटोटाइप, या उस समारोह के लिए घोषणा,
है- मिल बूल की तरह लग रही है, और हो सकता है फिर हम दो तर्क में पारित करने के लिए चाहते हैं।
>> सबसे पहले, के लिए एक संकेत है लिंक सूची के पहले तत्व।
यह आपको हूँ वास्तव में कुछ है हमेशा की ट्रैक रखना चाहते हैं,
और वास्तव में कुछ हो सकता है कि आप भी एक वैश्विक चर में डाल दिया है।
आप एक सूची बना लेते हैं, हमेशा हमेशा के लिए आप,
बहुत का ट्रैक रखने के लिए चाहते हैं सूची में सबसे पहला तत्व।
आप अन्य सभी का उल्लेख कर सकते हैं इस तरह सिर्फ श्रृंखला का पालन करके तत्वों,
संकेत रखने के बिना हर एक तत्व को बरकरार।
आप केवल पहले का ट्रैक रखने की जरूरत है एक वे सब एक साथ जंजीर कर रहे हैं।
>> और फिर दूसरी बात हम फिर से गुजर रहे हैं
मनमाने ढंग से some-- है जो कुछ डेटा प्रकार हम कर रहे हैं
वहाँ के लिए देख के अंदर है उम्मीद है कि सूची में नोड्स में से एक।
तो कदम क्या हैं?
खैर, हम ऐसा पहली बात है हम एक आड़ा सूचक बनाने
सूचियों के सिर की ओर इशारा करते।
खैर, यही वजह है कि हम पहले से ही हम क्या करें सूचियों के सिर पर एक सूचक है,
यही कारण है कि हम बस के आसपास है कि एक कदम नहीं है?
खैर, मैं सिर्फ इतना कहा की तरह, यह हमारे लिए वास्तव में महत्वपूर्ण है
हमेशा का ट्रैक रखने के लिए सूची में बहुत पहले तत्व।
और इसलिए यह वास्तव में बेहतर है इस बात का एक डुप्लिकेट बनाने के लिए,
और इसलिए हम कभी नहीं चारों ओर ले जाने के लिए उपयोग गलती से दूर ले जाते हैं, या हमेशा की तरह हम
है कि कुछ बिंदु पर एक सूचक है सही सूची के पहले तत्व पर।
तो यह एक बनाने के लिए बेहतर है हम स्थानांतरित करने के लिए उपयोग किए जाने वाले दूसरे एक।
>> तो हम बस कि क्या तुलना उस नोड पर मूल्य क्षेत्र
अगर यह हम देख रहे हैं, और क्या है नहीं, हम सिर्फ अगले नोड के लिए कदम।
और हम कर रखना है और अधिक से अधिक और अधिक से अधिक,
हम या तो लगता है जब तक तत्व है, या हम मारा
null-- हम अंत में पहुँच गए हैं और सूची की यह वहाँ नहीं है।
यह उम्मीद है कि एक घंटी की अंगूठी चाहिए आप बस के रूप में रैखिक खोज,
हम बस में नकल कर रहे हैं एक अकेले लिंक सूची संरचना
इसके बजाय यह करने के लिए एक सरणी का उपयोग करने का।
>> तो यहाँ का एक उदाहरण है एक अकेले लिंक सूची।
यह एक के होते हैं पाँच नोड्स, और हम
के सिर के लिए एक सूचक सूची कहा जाता है जो सूची।
हम क्या करना चाहते पहली बात यह है फिर, कि चंक्रमण सूचक पैदा करते हैं।
तो क्या अब हम दो संकेत है एक ही बात करने के लिए उस बिंदु।
>> अब भी यहां नोटिस मैं नहीं था सफर के लिए किसी भी स्थान malloc के लिए है।
मैं Trav malloc के बराबर होती है यह नहीं कहा कुछ है, उस नोड पहले से ही मौजूद है,
स्मृति में है कि अंतरिक्ष में पहले से ही मौजूद है।
इसलिए मैं वास्तव में क्या कर रहा हूँ सब है यह करने के लिए एक और सूचक बनाने।
मैं एक अतिरिक्त mallocing नहीं कर रहा हूँ अंतरिक्ष, बस अब दो संकेत है
एक ही बात की ओर इशारा करते।
>> तो 2 के लिए मैं देख रहा हूँ क्या है?
नहीं, ठीक है, तो बजाय मैं कर रहा हूँ अगले एक को स्थानांतरित करने के लिए जा रहा है।
तो बुनियादी तौर पर मैं कहना चाहूँगा Trav अगले सफर के बराबर होती है।
मैं नहीं, क्या देख रहा हूँ 3 है।
तो मैं जाने के लिए जारी के माध्यम से, अंततः जब तक
मैं देख रहा हूँ जो है, जो 6 के लिए मिलता है समारोह कॉल के आधार पर करने के लिए
मैं शीर्ष पर है वहाँ है, और इसलिए मैं कर रहा हूँ।
>> अब, तत्व मैं क्या कर रहा हूँ के लिए लग रही है, सूची में नहीं है
यह अभी भी काम करने के लिए जा रहा है?
खैर, इस सूची में है कि नोटिस यहाँ, आसानी से अलग है
और यह है कि एक और बात है लिंक सूचियों के साथ महत्वपूर्ण है,
आप को बनाए रखने की जरूरत नहीं है उन्हें किसी विशेष क्रम में।
अगर आप चाहते हैं, कर सकते हैं लेकिन आप पहले से ही देखा हो सकता है
हम का ट्रैक रखने नहीं कर रहे हैं कि हम क्या नंबर तत्व पर हैं।
>> और कहा कि एक व्यापार की तरह है कि हम सरणियों छंद लिंक सूची के साथ है,
यह हम नहीं है अब रैंडम एक्सेस।
हम सिर्फ मैं चाहता हूँ, यह नहीं कह सकते 0 तत्व करने के लिए जाने के लिए,
या अपने सरणी के 6 तत्व, जो मैं एक सरणी में कर सकते हैं।
मैं मैं करने के लिए जाना चाहता हूँ नहीं कह सकता 0 तत्व, या 6 तत्व,
या मेरे लिंक सूची की 25 वीं तत्व, कोई उनके साथ जुड़े सूचकांक है।
और तो यह वास्तव में कोई फर्क नहीं पड़ता हम क्रम में हमारे सूची की रक्षा करते हैं।
क्या आप चाहते हैं निश्चित रूप से यह कर सकते हैं, लेकिन वहाँ
वे की जरूरत है तो कोई वजह किसी भी क्रम में संरक्षित किया।
तो फिर, चलो कोशिश करते हैं और इस सूची में 6 पाते हैं।
खैर, हम पर शुरू शुरुआत में, हम, 6 नहीं मिल रहा है
और फिर हम नहीं मिल जारी 6, हम अंत में यहाँ करने के लिए मिलता है जब तक।
नोड के लिए तो अभी Trav अंक 8 से युक्त है, और छह वहाँ में नहीं है।
>> तो अगले कदम होगा अगले सूचक पर जाने के लिए,
इसलिए Trav अगले सफर के बराबर होती है कहना।
खैर, सफर बगल में है, ने संकेत दिया वहाँ लाल बॉक्स, रिक्त है।
तो कहीं और वहाँ तो इस बिंदु पर जाना है, और
हम पहुँच गए हैं कि निष्कर्ष निकाल सकते हैं लिंक सूची के अंत में,
और 6 वहाँ में नहीं है।
और इसे लौटा दिया जाएगा इस मामले में झूठा।
>> ठीक है, कैसे हम एक नए डालने हो लिंक सूची में नोड?
इसलिए हम बनाने के लिए सक्षम किया गया है कहीं से भी बाहर एक लिंक सूची,
लेकिन हम शायद करना चाहते हैं एक श्रृंखला का निर्माण और नहीं
अलग सूचियों का एक गुच्छा बना।
हम एक सूची है चाहता हूँ कि , उस में नोड्स का एक गुच्छा है
एक नोड के साथ सूची की एक गुच्छा नहीं है।
तो हम बस बनाने का उपयोग कर नहीं रख सकते समारोह अब हम पहले परिभाषित हम
एक में सम्मिलित करना चाहते हैं पहले से ही मौजूद है कि सूची।
>> इस मामले तो, हम जा रहे हैं दो तर्क में पारित करने के लिए,
उस के सिर करने के लिए सूचक हम में जोड़ना चाहते हैं कि सूची में जुड़े।
यह इसलिए है क्यों फिर, वह है, महत्वपूर्ण हमेशा हम उस
क्योंकि, इसे का ट्रैक रखने यह वास्तव में एक ही तरीका है कि हम है
पूरी सूची है उल्लेख करने के लिए है सिर्फ पहला तत्व के लिए एक संकेत है।
तो हम एक में पास करना चाहते हैं कि पहले तत्व के लिए सूचक,
और जो कुछ भी मूल्य हम सूची में जोड़ना चाहते हैं।
और अंत में इस समारोह एक सूचक वापस करने के लिए जा रहा है
एक लिंक सूची के नए प्रमुख के लिए।
>> यहाँ शामिल कदम क्या हैं?
ठीक है, बस बनाने के साथ की तरह, हम गतिशील आवंटित की जरूरत
एक नए नोड के लिए जगह है, और बनाने की जांच यकीन है कि हम स्मृति से बाहर नहीं चला है, फिर से,
हम malloc का उपयोग कर रहे हैं, क्योंकि।
तो फिर हम आबाद करना चाहते हैं और, नोड सम्मिलित
इतनी संख्या में डाल दिया, जो कुछ भी वैल नोड में है।
हम कम से नोड सम्मिलित करना चाहते हैं लिंक सूची की शुरुआत।
>> एक कारण है कि मैं ऐसा करना चाहते हैं, और यह
एक दूसरे लेने लायक हो सकता है यहाँ वीडियो को थामने के लिए,
और मैं क्यों करना चाहते हैं के बारे में सोचते एक लिंक्ड की शुरुआत में डालने
सूची।
फिर, जैसा कि मैंने पहले उल्लेख किया यह सच नहीं है कि
हम किसी में इसे संरक्षित करता है, तो कोई फर्क आदेश है, इसलिए हो सकता है कि एक संकेत है।
और तुम हम तो क्या होगा देखा चाहता था है-- या सिर्फ एक दूसरे से
पहले जब हम जा रहे थे खोज के माध्यम से आप
क्या हो सकता है देख सकता है हम कोशिश कर रहे थे तो क्या
सूची के अंत में डालने के लिए।
हम एक नहीं है, क्योंकि सूची के अंत करने के लिए सूचक।
>> तो कारण है कि मैं चाहता हूँ होगा कि शुरुआत में डालने के लिए,
मैं तुरंत इसे कर सकते हैं क्योंकि है।
मैं शुरुआत में एक सूचक है, और हम एक दूसरे में एक दृश्य में यह देखेंगे।
लेकिन मैं अंत में सम्मिलित करना चाहते हैं, तो मैं शुरुआत में शुरू करना है
करने के लिए सभी तरह से पार अंत में, और फिर उस पर हमले।
तो यह है कि इसका मतलब यह होगा सूची के अंत में डालने
n के एक ओ बन जाएगा आपरेशन, वापस जा रहा
के बारे में हमारी चर्चा करने के लिए अभिकलनात्मक जटिलता।
यह n आपरेशन, जहां की एक ओ हो गया था सूची बड़ा है, और बड़ा हो गया, के रूप में
और बड़ा है, यह और अधिक हो जाएगा और कुछ हमले के लिए अधिक मुश्किल
अंत में पर।
लेकिन यह हमेशा के लिए वास्तव में आसान है शुरुआत में पर कुछ हमले,
आप शुरुआत में हमेशा से रहे हैं।
>> और हम फिर से इस का एक दृश्य देखेंगे।
और फिर हम एक बार, कर रहे हैं एक बार हम नए नोड डाला है,
हम करने के लिए हमारे सूचक वापसी करना चाहते हैं एक लिंक सूची के नए प्रमुख, जो
हम पर डालने रहे हैं के बाद शुरुआत, वास्तव में किया जाएगा
हम अभी बनाया नोड के लिए एक सूचक।
है, चलो इस कल्पना करते हैं क्योंकि मैं इसे मदद करेंगे।
>> यहाँ तो हमारी सूची है, इसके बारे में होते हैं चार तत्वों, एक नोड, 15 से युक्त
जो एक नोड के लिए अंक 9 युक्त जो
13 से युक्त एक नोड के लिए अंक, जो युक्त एक नोड के लिए अंक
अशक्त है जो 10, अपनी अगली सूचक के रूप में सूचक
इसलिए उस सूची के अंत में है।
तो हम एक सम्मिलित करना चाहते हैं मूल्य के साथ 12 नए नोड
इस की शुरुआत में सूची, हम क्या करें?
खैर, सबसे पहले हम के लिए अंतरिक्ष malloc नोड, और फिर हम वहाँ में 12 डाल दिया।
>> तो अब हम पहुँच गए एक निर्णय बिंदु, है ना?
हम की एक जोड़ी है संकेत है कि हम कर सकते थे
हम पहले जो एक बढ़ना चाहिए, ले जाने के लिए?
हम 12 बिंदु के लिए करना चाहिए list-- के नए प्रमुख
या मुझे माफ करना, हम 12 बनाना चाहिए सूची के पुराने सिर को इंगित?
या फिर हम कहना चाहिए कि सूची में अब 12 से शुरू होता है।
एक अंतर है वहाँ, और हम देख लेंगे
साथ दोनों एक दूसरे में क्या होता है।
>> लेकिन यह एक करने के लिए सुराग साइडबार के लिए बड़ा विषय,
जिनमें से एक यह है कि लिंक सूचियों के साथ trickiest बातें
संकेत व्यवस्था करने के लिए किया जाता है सही क्रम में।
आप आदेश की बातें बाहर ले जाते हैं, अगर आप गलती से समाप्त कर सकते हैं
सूची के बाकी orphaning।
और यहाँ इस बात का एक उदाहरण है।
तो चलो इस विचार के साथ चलते हैं of-- खैर, हम सिर्फ 12 बना लिया है।
हम 12 होने जा रहा है पता है सूची के नए प्रमुख,
और तो क्यों हम सिर्फ कदम नहीं है सूची सूचक वहाँ बात करने के लिए।
>> ठीक है, तो यह अच्छी बात है।
तो अब जहां 12 अगले अंक करता है?
मैं नेत्रहीन हम देख सकते हैं, मतलब यह 15 के लिए बात करेंगे कि,
मनुष्य के रूप में यह हमारे लिए वास्तव में स्पष्ट है।
कैसे कंप्यूटर पता है?
हम कुछ भी नहीं है अब 15 की ओर इशारा करते, है ना?
>> हम 15 का उल्लेख करने के लिए किसी भी क्षमता खो दिया है।
हम नए तीर अगले बराबरी नहीं कह सकता वहाँ कुछ भी नहीं है।
वास्तव में, हम अनाथ कर दिया है सूची के बाकी
ऐसा करके, हम है गलती से चेन टूटी हुई है।
और हम निश्चित रूप से ऐसा करने के लिए नहीं करना चाहती।
>> तो चलो वापस जाने के लिए और फिर से इस कोशिश करते हैं।
हो सकता है कि सही बात करना 12 की अगली सूचक स्थापित करने के लिए है
पहली सूची के पुराने सिर करने के लिए, फिर हम सूची पर स्थानांतरित कर सकते हैं।
और वास्तव में, यह है कि सही क्रम हम उस
हम कर रहे हैं जब पालन करने की आवश्यकता अकेले लिंक सूची के साथ काम कर रहे हैं।
हम हमेशा कनेक्ट करना चाहते हैं सूची में नए तत्व,
हम उस तरह लेने से पहले बदलने की दिशा में महत्वपूर्ण कदम
जहां लिंक सूची के सिर है।
फिर, कि इस तरह के एक बुनियादी बात है, हम इसे का ट्रैक खोना नहीं चाहते हैं।
>> तो हम उस बनाना चाहते सब कुछ एक साथ जंजीर है
हम चाहते हैं कि सूचक ले जाने से पहले।
और हां यह सही आदेश होगा, जो सूची के लिए 12 से कनेक्ट करने के लिए है,
तब सूची एक 12 शुरू होता है कि कहते हैं।
हम सूची 12 में शुरू होता है कहा कि अगर और तो, इस सूची के लिए 12 से कनेक्ट करने की कोशिश की
हम पहले से ही क्या होता है देखा है।
हम गलती से सूची खो देते हैं।
>> ठीक है, तो एक और बात के बारे में बात करने के लिए।
क्या हम से छुटकारा पाने के लिए चाहते हैं एक पूरे पर एक बार सूची से जुड़ा हुआ?
फिर, हम mallocing रहे यह सब जगह है, और इसलिए हम
हम कर रहे हैं जब यह मुक्त करने की जरूरत है।
तो अब हम को हटाना चाहते हैं पूरे लिंक सूची।
खैर, हम क्या करना चाहते हैं?
>> हम शून्य सूचक पहुँच गए हैं, तो हम अन्यथा, बस नष्ट, बंद करना चाहते हैं
तब सूची के बाकी है और मुझे मुक्त।
सूची के बाकी को हटाएँ, और फिर वर्तमान नोड मुक्त।
जैसे कि ध्वनि करता है, क्या तकनीक हम बात की है
के बारे में पहले से है जैसे कि ध्वनि करता है?
तो, बाकी सब मिटायें वापस आते हैं और मुझे हटा दें।
>> यही कारण है कि प्रत्यावर्तन है, हम कर दिया है थोड़ा छोटा समस्या,
हम हर किसी को नष्ट कह रहे हैं वरना, तो आप मुझे हटा सकते हैं।
और आगे सड़क के नीचे, उस नोड बाकी सब को नष्ट, कहेगा।
लेकिन अंत में हम के लिए मिल जाएगा सूची रिक्त है बिंदु है, जहां
और कहा कि अपने बेस मामला है।
>> तो चलो इस पर एक नजर डालते हैं, और यह काम कैसे हो सकता है।
यहाँ तो हमारी सूची है, यह वैसा ही है , हम बस के बारे में बात कर रहे थे की सूची
और कदम है।
पाठ का एक बहुत यहाँ है, लेकिन उम्मीद है कि दृश्य में मदद मिलेगी।
>> इसलिए हम have-- और मैं भी खींच लिया हमारे ढेर फ्रेम उदाहरण अप
कॉल के ढेर पर हमारे वीडियो से, और उम्मीद है कि इस सब के
एक साथ क्या हो रहा है आपको दिखाई देगा।
तो यहाँ हमारे स्यूडोकोड कोड है।
हम एक अशक्त तक पहुँच जाते हैं सूचक, अन्यथा, बंद करो
सूची के बाकी को नष्ट, तो वर्तमान नोड मुक्त।
इसलिए अभी, list-- हम कर रहे हैं कि सूचक
में गुजर से 12 अंक नष्ट करने के लिए।
12 एक शून्य सूचक नहीं है, इसलिए हम कर रहे हैं सूची के बाकी को नष्ट करने के लिए जा रहा है।
>> क्या हटा रहा है हम में से बाकी शामिल?
खैर, यह एक बनाने का मतलब कह रही है, को नष्ट करने के लिए कॉल
15 कि की शुरुआत है हम नष्ट करना चाहते हैं सूची के बाकी।
और तो कॉल को नष्ट करने के लिए 12 पकड़ पर किस तरह का है।
इसके लिए इंतज़ार कर, वहां जमे हुए है अपना काम खत्म करने के लिए, 15 को नष्ट करने के लिए कहते हैं।
>> खैर, 15 एक शून्य सूचक नहीं है, और इसलिए यह कहने जा रहा है, सब ठीक है,
खैर, सूची के बाकी को हटा दें।
सूची के बाकी शुरू होता है 9 में, और इसलिए हम सिर्फ हूँ
आप सभी को हटा रुको जब तक कि सामान, फिर वापस आ गया और मुझे हटा दें।
खैर 9 अच्छी तरह से कहने जा रहा है, मैं एक शून्य सूचक नहीं हूँ
इसलिए यहां से बाकी सूची को हटा दें।
और इसलिए कोशिश करते हैं और 13 को नष्ट कर।
13, मैं शून्य सूचक नहीं हूँ, कहते हैं एक ही बात है, यह हिरन गुजरता है।
10, 10 शून्य सूचक नहीं है एक शून्य सूचक होता है,
लेकिन 10 नहीं अपने आप में एक है अशक्त सही अब सूचक,
और इसलिए यह भी हिरन गुजरता है।
>> और अब, वहाँ यह अंक सूची वास्तव में some-- से बात करेंगे
मैं छवि में और अधिक स्थान था, यह कुछ बेतरतीब अंतरिक्ष से बात करेंगे
हम यह क्या है पता नहीं है।
हालांकि यह शून्य सूचक है, सूची सचमुच अब यह नल मान है सेट किया जाता है।
यह सही है कि लाल बॉक्स के अंदर इशारा कर रहा है।
हम तो, एक शून्य सूचक पहुंच गया हम रोक सकते हैं, और हम कर रहे हैं।
>> और इतना है कि बैंगनी रंग के फ्रेम पर now-- है सक्रिय फ्रेम है कि stack-- के ऊपर,
लेकिन यह हो चुका है।
हम एक शून्य सूचक पर पहुंच गया है, बंद करो।
हम कुछ नहीं करते हम एक शून्य सूचक मुक्त नहीं कर सकते हैं,
हम किसी भी malloc नहीं किया अंतरिक्ष, और इसलिए हम कर रहे हैं।
उस समारोह फ्रेम तो नष्ट कर दिया है, और हम है
हम छोड़ दिया, जहां resume-- हम उठाओ उच्चतम अगले एक, साथ बंद जो
यहां यह गहरे नीले रंग की फ्रेम है।
तो हम कहाँ दूर छोड़ दिया सही उठाओ।
हम में से बाकी के हटाए गए सूची में पहले से ही है, तो अब हम कर रहे हैं
वर्तमान नोड्स मुक्त करने के लिए जा रहा है।
तो अब हम अब इस नोड मुक्त कर सकते हैं, और हम समारोह के अंत में पहुँच गए हैं।
और इतना है कि समारोह फ्रेम, नष्ट हो जाता है और हम हल्के नीले रंग की एक में उठा।
>> तो यह है कि मैं पहले से ही done-- किया है says-- सूची के बाकी को हटाने इसलिए
वर्तमान नोड मुक्त।
और अब पीला फ्रेम है वापस ढेर के शीर्ष पर।
जैसा कि आप देख और हां, तो हम अब कर रहे हैं सही से सूची को नष्ट करने के लिए छोड़ दिया।
>> क्या है, हालांकि, क्या हुआ होगा हम चीजों को गलत तरीके से किया था?
बस हम कोशिश की, जब की तरह एक तत्व जोड़ने के लिए।
हम यदि चेन, गड़बड़ तो हम संकेत कनेक्ट नहीं किया
सही क्रम में, अगर हम सिर्फ पहला तत्व मुक्त कर दिया,
हम सिर्फ मुक्त कर दिया है, तो सूची के सिर, अब हम
उल्लेख करने के लिए कोई रास्ता नहीं है सूची के बाकी।
और इसलिए हम होगा अनाथ सब कुछ,
हम क्या होता था एक स्मृति रिसाव बुलाया।
आप हमारे वीडियो से याद करते हैं गतिशील स्मृति आवंटन पर,
कि बहुत अच्छी बात नहीं है।
>> तो जैसा कि मैं ने कहा, कई संचालन कर रहे हैं
हम काम करने के लिए उपयोग करने की आवश्यकता है कि साथ प्रभावी ढंग से सूची से जोड़ा।
और तुम, मैं एक लोप देखा हो सकता है एक लिंक्ड से एक भी तत्व को हटाने
सूची।
मैंने किया है कि कारण यह वास्तव में किस तरह की है है
को नष्ट करने के बारे में सोचने के लिए मुश्किल एक अकेले से एक ही तत्व
लिंक्ड सूची।
हम पर छोड़ करने में सक्षम होने की जरूरत है सूची में कुछ जो
हम एक point-- हम करने के लिए मिल का मतलब इस node-- हटाना चाहते हैं
लेकिन क्रम में हम ऐसा करने के लिए किसी भी जानकारी को खोना नहीं है,
हम इस को जोड़ने की जरूरत यहाँ यहाँ पर नोड।
>> इसलिए मुझे लगता है कि शायद गलत नहीं किया एक दृश्य के नजरिए से।
इसलिए हम की शुरुआत में हो हमारी सूची में, हम के माध्यम से आगे बढ़ने से कर रहे हैं
हम इस नोड को नष्ट करना चाहते हैं।
, हम सिर्फ यह हटाते हैं हम श्रृंखला टूट गए हैं।
यहीं इस नोड बाकी सब को दर्शाता है,
यह यहाँ पर बाहर से श्रृंखला में शामिल है।
>> इसलिए हम वास्तव में क्या करने की जरूरत हम इस बात के लिए प्राप्त करने के बाद,
हम एक कदम वापस करने की जरूरत है, और है इस नोड के लिए इस नोड पर कनेक्ट,
इसलिए हम तो नष्ट कर सकते हैं बीच में एक।
लेकिन अकेले लिंक सूचियों नहीं करते हमें पीछे की ओर जाने के लिए एक तरीका प्रदान करते हैं।
तो हम या तो रखने की जरूरत दो संकेत है, और उन्हें स्थानांतरित
बंद कदम की तरह है, पीछे से एक अन्य हमें जाना है, या एक बात करने के लिए मिल के रूप में
और उसके बाद के माध्यम से एक और सूचक भेजें।
और आप इसे देख सकते हैं एक छोटी सी गड़बड़ हो सकता है।
सौभाग्य से, हमारे पास एक और तरीका है कि हल करने के लिए,
जब हम दोगुना लिंक सूचियों के बारे में बात करते हैं।
>> मैं डौग लॉयड हूँ, इस CS50 है।