स्पीकर 1: ठीक है, तो यह है CS50 इस हफ्ते पांच का अंत है। और है कि पिछले समय को याद करते हैं हम शुरू कर दिया शौक़ीन डेटा को देख हल करने के लिए शुरू कर दिया है कि संरचनाओं लागू करने के लिए शुरू कर दिया है कि समस्याओं, नई समस्याओं, लेकिन इस के लिए महत्वपूर्ण सूत्रण की तरह था कि हम नोड से नोड के लिए करना शुरू कर दिया। तो निश्चित रूप से यह है एक अकेले लिंक सूची। और से अकेले, लिंक्ड मैं सिर्फ एक ही मतलब वहाँ उन नोड्स से प्रत्येक के बीच धागा। आप शौक़ीन कर सकते हैं पता चला है दोगुना लिंक सूचियों की तरह बातें आप एक तीर है जिससे दोनों दिशाओं में जा रहा है, जो निश्चित क्षमता के साथ कर सकते हैं। लेकिन इस समस्या का हल? यह क्या समस्या को हल किया? हम सोमवार को क्यों परवाह है? क्यों, सिद्धांत रूप में, हम सोमवार को परवाह है? वह क्या करता है? 

दर्शकों: हम गतिशील यह आकार बदल सकते हैं। 

स्पीकर 1: ठीक है, हम कर सकते हैं, इसलिए गतिशील इसे आकार। वैसे आप दोनों के लिए किया। तो आप गतिशील इस आकार बदल सकते हैं डेटा संरचना, एक सरणी, जबकि याद है, जब आप एक पता करने के लिए प्राथमिकताओं कितनी जगह आप चाहते हैं और आप एक छोटे से अधिक की जरूरत है अंतरिक्ष, तुम भाग्य से बाहर एक तरह से कर रहे हैं। तुम एक पूरी नई सरणी बनाने के लिए है। आप सभी को ले जाने के लिए अपने एक से दूसरे के डेटा, अंततः पुराने सरणी मुक्त आप कर सकते हैं, और फिर आगे बढ़ें। जो सिर्फ बहुत महंगा लगता है और बहुत अक्षम, और वास्तव में यह हो सकता है। लेकिन यह सब अच्छा नहीं है। हम एक कीमत चुकानी, एक क्या था और अधिक स्पष्ट की कीमतों में हम एक लिंक सूची का उपयोग करके भुगतान करते हैं? 

दर्शकों: हम का उपयोग किया है हर एक के लिए डबल अंतरिक्ष। स्पीकर 1: हाँ, तो हम की जरूरत है कम से कम दो बार ज्यादा जगह के रूप में। वास्तव में, मुझे एहसास हुआ कि इस तस्वीर के यहां तक ​​कि एक छोटे से भ्रामक, क्योंकि आधुनिक का एक बहुत में CS50 आईडीई पर कंप्यूटर, एक सूचक या एक पते तथ्य यह है कि चार बाइट्स में नहीं है। यह बहुत अक्सर इन है दिनों आठ बाइट्स, जो नीचे का अर्थ है सबसे वास्तविकता में वहाँ आयतों के रूप में दो बार तरह कर रहे हैं मैं खींचा है क्या के रूप में बड़ा, जो आप तीन बार के रूप में उपयोग कर रहे हैं इसका मतलब हम अन्यथा हो सकता है के रूप में ज्यादा जगह। अब एक ही समय में, हम कर रहे हैं अभी भी बाइट्स में बात कर रहा है, है ना? हम जरूरी बात नहीं कर रहे मेगाबाइट या गीगाबाइट, इन आंकड़ों जब तक संरचनाओं बड़ा मिलता है। 

और इसलिए आज हम पर विचार करने के लिए शुरू हम डेटा का पता लगाने कैसे हो सकता है अधिक कुशलता में यदि तथ्य यह है कि डेटा बड़ा हो जाता है। लेकिन canonicalize की कोशिश करते हैं पहले अभियान आप इन पर कर सकते हैं कि डाटा संरचनाओं की तरह। एक लिंक्ड तरह तो कुछ सूची आम तौर पर समर्थन संचालन हटाना चाहते, डालें, और खोज। और मुझे लगता है कि क्या मतलब है? यही कारण है कि बस, कि आम तौर पर मतलब लोगों लिंक सूची का उपयोग कर रहे हैं, वे या किसी और को लागू किया गया है हटाने, डालें की तरह काम करता है, और खोज, आप कर सकते हैं, इसलिए वास्तव में कुछ करना है डेटा संरचना के साथ उपयोगी है। तो चलो एक त्वरित नज़र रखना हम लागू कैसे हो सकता है पर एक लिंक सूची के लिए कुछ कोड के रूप में इस प्रकार है। 

तो यह सिर्फ कुछ सी कोड है, नहीं भी एक पूरा कार्यक्रम मैं सच में जल्दी से मार पड़ी है। यह वितरण में ऑनलाइन नहीं है कोड, यह वास्तव में नहीं चलेंगे क्योंकि। लेकिन मैं सिर्फ है नोटिस एक टिप्पणी के साथ कहा, डॉट डॉट डॉट, वहाँ कुछ है वहाँ, वहाँ, कुछ डॉट डॉट डॉट। और चलो बस को देखो रसदार भागों क्या कर रहे हैं। तो लाइन तीन पर, अब यह है कि याद हम पिछले एक नोड घोषित करने का प्रस्ताव समय, उन आयताकार वस्तुओं में से एक। यह हम एन फोन करता हूँ कि एक पूर्णांक है लेकिन हम कुछ भी कह सकते हैं, और फिर एक संरचना नोड स्टार अगले बुलाया। और बस, कि दूसरी स्पष्ट होना लाइन, लाइन छह पर, वो क्या है? यह हमारे लिए क्या कर रही है? यह निश्चित रूप से अधिक लग रहा है क्योंकि हमारे सामान्य चर से गुप्त। 

दर्शकों: यह एक से अधिक कदम बनाता है। 

स्पीकर 1: यह एक से अधिक कदम बनाता है। और अधिक सटीक होना करने के लिए यह पता स्टोर होगा होने का मतलब है कि नोड के शब्दार्थ यह अगले, है ना? तो यह करने के लिए नहीं जा रहा है जरूरी कुछ भी चलते हैं। यह सिर्फ करने के लिए जा रहा है जो है, एक मूल्य की दुकान पता होने जा रहा कुछ अन्य नोड के, हम संरचना कहा है कि क्यों नोड स्टार, स्टार denoting एक सूचक या एक पते। ठीक है, तो अब आप हम मान लेते हैं कि यदि हमारे पास उपलब्ध इस एन, और चलो किसी और है कि मान पूर्णांकों की एक पूरी गुच्छा डाला एक लिंक सूची में। और कहा कि लिंक सूची है कुछ बिंदु द्वारा उठाई है कि एक चर बुलाया सूची एक पैरामीटर के रूप में यहाँ से पारित कर दिया, कैसे मैं रेखा के बारे में जाना है 14 खोज लागू? दूसरे शब्दों में, मैं लागू कर रहा हूँ, तो जिसका उद्देश्य जीवन में समारोह तो एक int और लेने के लिए है एक लिंक की गई सूची की शुरुआत, उस लिंक की गई सूची के लिए एक संकेत है। पहले की तरह, मैं दाऊद कौन लगता है हमारे स्वयंसेवक सोमवार को था वह कम से इशारा कर रहा था पूरे लिंक सूची, हम गुजर रहे हैं के रूप में हालांकि यह है डेविड हमारे यहाँ तर्क के रूप में। हम कैसे इस सूची से गुजर जाने के बारे में? खैर, यह पता चला है कि भले ही संकेत, अब हमारे लिए अपेक्षाकृत नए हैं हम अपेक्षाकृत यह कर सकता है सीधी। 

मैं आगे जाने के लिए जा रहा हूँ और एक अस्थायी चर घोषित कि सम्मेलन द्वारा सिर्फ जा रहा है करने के लिए, पीटीआर सूचक कहा जाता है, या हो लेकिन क्या आप चाहते हैं कुछ भी कह सकते हैं। और मैं प्रारंभ करने के लिए जा रहा हूँ यह सूची की शुरुआत करने के लिए। तो अगर आप इस तरह की सोच सकते हैं मुझे शिक्षक के रूप में दूसरे दिन, एक तरह से किसी पर इशारा स्वयंसेवकों के रूप में हमारे इंसानों के बीच। इसलिए मुझे लगता है कि एक अस्थायी चर रहा हूँ बस एक ही बात पर इशारा हमारे संयोग कहा जाए कि स्वयंसेवक दाऊद भी इशारा कर रहा था। अब सूचक है, जबकि अशक्त नहीं, क्योंकि याद करते हैं कि अशक्त कुछ विशेष प्रहरी मूल्य है सूची के अंत सीमांकित मैं तरफ इशारा करते हुए नहीं कर रहा हूँ, इसलिए जब तक हमारे पिछले स्वयंसेवक की तरह जमीन था, चलो आगे चलते हैं और निम्नलिखित है। Pointer-- हैं और अब मैं एक तरह से करना चाहते हैं हम छात्र के साथ किया था कि क्या करना है structure-- सूचक डॉट अगले यदि बराबर होती सूचक डॉट एन, के बराबर होती है बल्कि यदि चर एन, के बराबर होती है में पारित कर दिया गया है कि तर्क, तो मैं आगे जाना चाहता हूँ और सच वापसी का कहना है। मैं अंदर की संख्या एन पाया है मेरा लिंक सूची के नोड्स में से एक। लेकिन डॉट नहीं रह गया है इस संदर्भ में काम करता है, सूचक, पीटीआर है, क्योंकि वास्तव में एक सूचक, एक पता, हम वास्तव में अद्भुत रूप से कर सकते हैं वाक्य रचना के अंत में एक टुकड़े का उपयोग बनाता है की उस तरह सहज ज्ञान युक्त भावना और वास्तव में से जाना है, जिसका अर्थ यहाँ एक तीर का उपयोग वहाँ में पूर्णांक के लिए कि पता। तो उस में बहुत समान है डॉट ऑपरेटर के लिए भावना, लेकिन सूचक एक सूचक नहीं है क्योंकि और नहीं एक वास्तविक संरचना ही है, हम सिर्फ तीर का उपयोग करें। 

तो अगर वर्तमान नोड कि मैं, अस्थायी चर, पर इशारा कर रहा हूँ एन, क्या मैं क्या करना चाहते हैं नहीं है? खैर, मेरे मानव स्वयंसेवकों के साथ हम दूसरे दिन यहां था कि, मेरा पहला मानव एक मैं नहीं है, तो चाहते हैं, और हो सकता है कि दूसरे इंसान नहीं है एक मैं चाहता हूँ, और तीसरा, मैं चलती शारीरिक रूप से रखने की जरूरत है। कैसे की तरह मैं एक सूची के माध्यम से कदम है? हम एक सरणी था, जब आप सिर्फ मैं प्लस प्लस की तरह था। लेकिन इस मामले में, यह करने के लिए काफ़ी है अगले, सूचक, हो जाता है, सूचक है। दूसरे शब्दों में, अगले क्षेत्र बाएँ हाथ के सभी तरह है कि सोमवार को हमारे मानव स्वयंसेवकों कुछ अन्य नोड पर बात करने के लिए उपयोग कर रहे थे। लोग अपने अगले पड़ोसी थे। 

मैं इस सूची के माध्यम से कदम चाहते हैं तो, मैं तो बस, अब और मैं क्या प्लस प्लस नहीं कर सकते मैं बजाय कहने के लिए है मैं, सूचक, जा रहा है अगले क्षेत्र है जो कुछ भी बराबर करने के लिए, अगले क्षेत्र, अगले क्षेत्र है, है उन बाएँ हाथ के सभी निम्न हम मंच की ओर इशारा करते पर था कि कुछ बाद में मूल्यों के लिए। और मैं के माध्यम से मिलता है कहा कि पूरे चलना, और अंत में, मैं नहीं होने अशक्त मारा पाया एन अभी तक, मैं सिर्फ झूठी वापसी। तो फिर, हम यहाँ क्या कर रहे हैं कि सभी, एक पल पहले चित्र के अनुसार, पर इशारा द्वारा शुरू कर रहा है संभवतः सूची की शुरुआत। और फिर मैं जाँच, मूल्य है मैं नौ के बराबर के लिए देख रहा हूँ? यदि हां, तो मैं वापसी सच है और मैं कर रहा हूँ। यदि नहीं, तो मैं अपने हाथ को अद्यतन, उर्फ सूचक, बात करने के लिए अगले तीर के स्थान पर, और फिर अगले तीर के स्थान, और अगले। मैं तो बस इस सरणी के माध्यम से चल रहा है। 

तो फिर, कौन परवाह करता है? इस तरह के लिए एक घटक क्या है? खैर, हम शुरू की है कि याद एक ढेर की धारणा है, जो यह है के रूप में एक सार डेटा insofar के प्रकार है नहीं एक सी बात है, यह एक CS50 बात नहीं है, यह एक अमूर्त विचार के इस विचार है एक दूसरे के शीर्ष पर बातें स्टैकिंग उस में लागू किया जा सकता अलग अलग तरीकों के गुच्छों। और हम प्रस्तावित एक तरह से साथ था एक सरणी, या एक लिंक सूची के साथ। और यह एक, कि शास्त्रीय विधि पता चला है ढेर में कम से कम दो आपरेशन का समर्थन करता है। और बज़ शब्द को धक्का कर रहे हैं ढेर पर कुछ धक्का, में एक नया ट्रे की तरह डायनिंग हॉल, या पॉप, जो सर्वोच्च दूर करने के लिए इसका मतलब है भोजन में ढेर से ट्रे हॉल, और तब शायद कुछ अन्य कार्यों के रूप में अच्छी तरह से। तो हम कैसे संरचना को परिभाषित कर सकता है हम अब एक ढेर बुला रहे हैं? 

खैर, हम अपेक्षित के सभी है मैं कहना है कि सी में हमारे निपटान पर वाक्य रचना, मुझे का एक प्रकार परिभाषा दे एक ढेर के अंदर एक संरचना, मैं एक के, एक सरणी है कहने जा रहा हूँ पूरी संख्या का गुच्छा और फिर आकार। तो दूसरे शब्दों में, अगर मैं चाहता हूँ कोड में इस लागू करने के लिए, मुझे जाना है और बस की तरह करते हैं यह कह रहा है क्या आकर्षित। यह कह रहा है तो, मुझे एक देना एक सरणी मिल गया है कि संरचना, और मैं, क्षमता क्या है पता नहीं है यह मैं कि जाहिरा तौर पर कुछ स्थिर है कहीं और परिभाषित है, और वह ठीक है। लेकिन, यह सिर्फ एक है लगता है दो, तीन, चार, पांच। तो क्षमता 5 है। के अंदर यह तत्व मेरी संरचना संख्या बुलाया जाएगा। और फिर मैं एक की जरूरत है अन्य चर जाहिरा तौर पर शुरू में मैं जा रहा हूँ कि बुलाया आकार शून्य करने के लिए प्रारंभ किया है निर्धारित करना। कुछ भी नहीं है कि अगर वहाँ ढेर, आकार, शून्य है और यह संख्या में कचरा मूल्यों है। मैं बस अभी तक वहाँ में क्या कोई पता नहीं है। 

मैं धक्का करना चाहते हैं तो ढेर पर कुछ है, मैं समारोह धक्का फोन लगता है, और मैं 50 नंबर की तरह, 50 धक्का कहना जहां आप का प्रस्ताव होगा मैं इस सरणी में यह आकर्षित? पांच अलग-अलग संभव जवाब नहीं है। तुम कहाँ संख्या 50 पुश करने के लिए करना चाहते हैं? यहाँ लक्ष्य है, तो फिर, फोन समारोह धक्का, एक बहस में पारित 50 साल की है, मैं उसे कहाँ रखा है? पांच possible-- 20% मौका का सही ढंग से अनुमान लगा। हाँ? 

दर्शकों: अभी तक सही। 

स्पीकर 1: सुदूर सही। एक 25% मौका अब नहीं है का सही ढंग से अनुमान लगा। तो यह है कि वास्तव में ठीक हो जाएगा। परंपरा के अनुसार, मैं एक सरणी के साथ कहता हूँ, हम आम तौर पर, बाएं से शुरू होगा लेकिन हम निश्चित रूप से कर सकता है सही में शुरू करो। तो यहाँ बिगाड़ने मैं कर रहा हूँ होगा शायद बाईं तरफ आकर्षित करने के लिए जा रहा है, सिर्फ एक सामान्य सरणी जहां में पसंद मैं सही करने के लिए छोड़ दिया जा रहा शुरू। लेकिन अगर आप फ्लिप कर सकते हैं, तो अंकगणित, ठीक है। यह सिर्फ पारंपरिक नहीं है। ठीक है, मैं एक बनाने की जरूरत हालांकि अधिक परिवर्तन। अब मैं कुछ धक्का दिया है कि ढेर पर, आगे क्या है? 

ठीक है, मैं आकार में वृद्धि करना है। तो मुझे आगे और अभी चलते हैं शून्य था, जो इस अद्यतन। और इसके बजाय, अब मैं जा रहा हूँ मूल्य एक में डाल दिया। और अब मैं एक और धक्का लगता है ढेर पर नंबर 51 की तरह। खैर, मैं एक और बनाने के लिए है आकार दो पर निर्भर है जो परिवर्तन,। और फिर मैं एक और धक्का लगता है 61 की तरह ढेर पर नंबर, अब मैं आकार को अपडेट करने की जरूरत है एक और समय, और आकार के रूप में मान 3 मिलता है। और अब मैं पॉप फोन लगता है। अब परंपरा से, पॉप, एक तर्क नहीं ले करता है। एक ढेर के साथ, पूरे ट्रे रूपक के बिंदु आप विवेक की जरूरत नहीं है कि है कि ट्रे मिल जाना, सब आप कर सकते हैं से सर्वोच्च एक पॉप है ढेर, सिर्फ इसलिए। यही कारण है कि इस डेटा संरचना क्या करता है। 

यदि उस तर्क से तो मैं पॉप, क्या उतर आता है कहते हैं? तो 61। तो सच में कंप्यूटर क्या है स्मृति में करने के लिए जा रहे हैं? क्या मेरे कोड क्या करना है? आप क्या प्रस्ताव होगा हम स्क्रीन पर बदल जाता है? क्या बदलना चाहिए? क्षमा करें? इसलिए हम 61 से छुटकारा मिलेगा। तो मैं निश्चित रूप से ऐसा कर सकते हैं। और मैं 61 से छुटकारा मिल सकता है। और फिर क्या अन्य परिवर्तन होने की जरूरत है? आकार शायद दो के लिए वापस जाना पड़ता है। और इसलिए वह ठीक है। लेकिन एक मिनट, आकार इंतजार एक पल पहले तीन साल का था। चलो बस एक त्वरित मानसिक स्वास्थ्य की जांच करते हैं। हम कैसे हम जानते हैं कि 61 से छुटकारा पाने के लिए चाहते थे? हम popping रहे हैं। और इसलिए मैं इस दूसरी संपत्ति के आकार है। 

मैं कर रहा हूँ, एक मिनट रुको दो सप्ताह के लिए वापस सोच हम के बारे में बात कर शुरू किया जब इस स्थान शून्य था जहां सरणियों, इस स्थान से एक था, इस स्थान था दो, इस स्थान पर तीन, चार है, ऐसा लग रहा है आकार के बीच संबंध और मैं चाहता हूँ कि तत्व को दूर करने के लिए सरणी से बस क्या हो गया लगता है? आकार शून्य से एक। और इतना है कि कैसे मनुष्य के रूप में है हम 61 पहले आता है। कैसे कंप्यूटर में पता करने के लिए हो रहा है? जब अपने कोड, जहां आप शायद आकार शून्य से एक करना चाहते हैं, इसलिए तीन शून्य से एक दो, और वह यह है कि हम 61 से छुटकारा चाहते हैं इसका मतलब है। और फिर हम वास्तव में अद्यतन कर सकते हैं कि आकार इतना आकार अब सिर्फ दो से तीन से चला जाता है। और बस पंडिताऊ हो, मैं जा रहा हूँ मैं सही काम कर रहा हूँ कि प्रस्ताव करने के लिए? तुम intuitively प्रस्तावित सही ढंग से मैं 61 से छुटकारा मिलना चाहिए। लेकिन नहीं मैं एक तरह से एक तरह से 61 से छुटकारा मिल गया? मैं प्रभावी भूल गए कि यह वास्तव में नहीं है। आप पढ़ा है और, अगर वापस PSET4 करने के लिए लगता है फोरेंसिक के बारे में लेख, पीडीएफ हम था कि तुम लोगों को पढ़ने के लिए, या आप PSET4 के लिए इस सप्ताह पढ़ा होगा। यह करने के लिए वास्तव में सार्थक है कि स्मरण करो कंप्यूटर फोरेंसिक के पूरे विचार। क्या एक कंप्यूटर आम तौर पर करता है कुछ ऐसा है जहां यह सिर्फ भूल जाता है लेकिन उस में जाने के लिए और की तरह नहीं है इसे बाहर या ओवरराइड खरोंच करने की कोशिश शून्य और लोगों के साथ उन बिट्स या कुछ अन्य यादृच्छिक पैटर्न जब तक आप अपने आप को इतना जानबूझ कर करते हैं। तो अपने अंतर्ज्ञान था ठीक है, चलो 61 से छुटकारा मिलता है। लेकिन वास्तविकता में, हम चिंता करने की जरूरत नहीं है। हम सिर्फ इतना है कि भूल की जरूरत यह हमारे आकार बदलने के द्वारा नहीं है। 

अब इस ढेर के साथ एक समस्या नहीं है। मैं चीजों को धक्का रखने हैं ढेर पर, क्या है जाहिर है कि क्या होने जा रहा बस कुछ ही क्षणों समय में? हम अंतरिक्ष के बाहर चलाने के लिए जा रहे हैं। और हम क्या करते हैं? हम किस तरह का खराब कर रहे हैं। इस कार्यान्वयन ऐसा नहीं करता है का उपयोग करते हुए, क्योंकि हमें, सरणी का आकार बदलने इस वाक्य रचना, अगर आप दो सप्ताह के लिए वापस लगता है, आप घोषित किए जाने के बाद एक सरणी के आकार, हम अभी तक जहां एक तंत्र नहीं देखा है आप सरणी के आकार को बदल सकते हैं। और वास्तव में सी कि सुविधा नहीं है। यदि आप कहते हैं मुझे पाँच देना Nths उन्हें फोन नंबर, कि आप इसे पाने के लिए जा रहे है। इसलिए हम सोमवार के रूप में अब क्या है, एक समाधान व्यक्त करने की क्षमता हालांकि, हम सिर्फ tweak करने की जरूरत है हमारे ढेर की परिभाषा कुछ हार्ड कोडित सरणी नहीं करने के लिए, लेकिन सिर्फ एक पते की दुकान है। 

अब ऐसा क्यों है? अब हम सिर्फ साथ सहज होना जरूरी तथ्य यह है कि अपने कार्यक्रम चलाता है जब कि, मैं संभवतः करने के लिए जा रहा हूँ मानव पूछना है, कितनी संख्या आप स्टोर करने के लिए करना चाहते हैं? तो इनपुट कहीं से आ गया है। लेकिन मुझे पता है कि एक बार नंबर है, तो मैं सिर्फ यह कर सकते हैं देने के लिए कार्य क्या उपयोग मुझे स्मृति का एक हिस्सा? मैं malloc उपयोग कर सकते हैं। और मुझे लगता है की किसी भी संख्या में कह सकते हैं बाइट्स मैं वापस इन Nths के लिए चाहते हैं। और यह सब मैं संख्या में स्टोर करने के लिए है इस संरचना के अंदर यहां चर क्या होना चाहिए? क्या वास्तव में चला जाता है इस परिदृश्य में संख्या? हाँ, पहले के लिए एक सूचक स्मृति की है कि हिस्सा की बाइट, या अधिक विशेष रूप से, पता उन बाइट्स के पहले की। यह एक है तो कोई बात नहीं बाइट या एक अरब बाइट्स, मैं सिर्फ पहली के बारे में परवाह करने की जरूरत है। क्योंकि क्या malloc गारंटी देता है और अपने ऑपरेटिंग सिस्टम की गारंटी देता है, है कि स्मृति मैं का हिस्सा मिलता है, यह सटे होने जा रहा है। अंतराल होने के लिए वहाँ नहीं जा रहा है। मैं 50 के लिए कहा है तो अगर बाइट या 1,000 बाइट्स, वे सब होने के लिए जा रहे हैं वापस वापस करने के लिए वापस करने के लिए। और इतने लंबे समय मैं, कैसे कैसे बड़ा याद के रूप में ज्यादा मुझे पता करने की जरूरत है, सभी के लिए कहा पहली बार इस तरह का पता है। 

तो अब हम कोड में क्षमता है। हालांकि, यह हमें ले जा रहा है अधिक समय, यह लिखने के लिए हम अब तक कि स्मृति reallocate कर सकता है सिर्फ वहाँ एक अलग पते के भंडारण हम भी एक बड़ा या करना चाहते हैं स्मृति का एक छोटा हिस्सा। तो यहाँ एक व्यापार बंद करने के लिए। अब हम गतिशीलता मिलता है। हमारे पास अब भी यह है contiguousness मैं दावा कर रहा हूँ। Malloc हमें दे देंगे क्योंकि स्मृति का एक सन्निहित हिस्सा। लेकिन इस में दर्द होने जा रहा है हमारे लिए गर्दन, प्रोग्रामर, वास्तव में ऊपर कोड के लिए। यह सिर्फ अधिक काम है। हम मैं क्या था करने के लिए समान कोड की जरूरत बस एक पल पहले बाहर की पिटाई। बहुत मुमकिन है, लेकिन यह जटिलता कहते हैं। और तो डेवलपर समय, प्रोग्रामर समय अभी तक एक संसाधन है हम खर्च करने की आवश्यकता हो सकती है कि कुछ समय के लिए नई सुविधाओं को पाने के लिए। और फिर बेशक एक कतार है। हम इस में नहीं जाना होगा ज्यादा विस्तार में से एक है। लेकिन यह भावना में बहुत समान है। मैं एक कतार लागू करने, और कर सकता है अपनी इसी संचालन, एन्क्यू या विपंक्ति, जोड़ने या हटाने की तरह है, यह है, यह कहने का सिर्फ एक शौक़ीन रास्ता है एन्क्यू या विपंक्ति, के रूप में इस प्रकार है। मैं सिर्फ अपने आप को एक संरचना दे सकते हैं कि फिर से एक नंबर की सरणी है, कि फिर से एक आकार है, लेकिन अब मैं क्यों की ज़रूरत है एक कतार के सामने का ट्रैक रखने के लिए? मुझे पता है की जरूरत नहीं थी मेरी ढेर के सामने। खैर, अगर मैं फिर से एक queue-- सिर्फ मुश्किल चलो पाँच की तरह होने के रूप में यह कोड यहां संभवतः में पूर्णांकों। तो यह शून्य, एक, दो, तीन, चार है। यह होने जा रहा है फिर से बुलाया संख्या। और इस आकार बुलाया जाएगा। 

क्यों यह पर्याप्त नहीं है सिर्फ आकार के लिए? ठीक है, चलो उन पर एक ही नंबर धक्का। इसलिए मुझे लगता है कि मैं कतारबद्ध, या धक्का दिया pushed--। अब मैं फिर 50 enqueue देंगे, और 51, और फिर 61, और डॉट डॉट डॉट। तो यह है कि एन्क्यू है। मैं तो 61, फिर 50, 51 कतारबद्ध। और कहा कि समान दिखता है इस प्रकार अब तक एक ढेर करने के लिए, सिवाय मैं एक परिवर्तन करने की आवश्यकता है। मैं इस आकार को अपडेट करने की जरूरत है, तो मैं जाना अब तीन to 1:59 शून्य से। मैं कैसे विपंक्ति है? क्या विपंक्ति के साथ क्या होता है? कौन पहले इस सूची से आना चाहिए यह एप्पल की दुकान पर लाइन है तो क्या होगा? तो 50। तो यह एक तरह से पेचीदा मामला इस समय है। पिछली बार जबकि यह सुपर था आसान बस, आकार शून्य से एक करने की मैं प्रभावी ढंग से अपने सरणी के अंत करने के लिए मिलता है संख्या रहे हैं, जहां यह 61 निकालता है। लेकिन मैं 61 को दूर नहीं करना चाहते हैं। मैं 50; जो 05:00 पर नहीं थी के लिए अप लाइन के लिए नए iPhone या whatnot। और इसलिए मैं 50 से छुटकारा पाने के लिए सिर्फ सही, यह नहीं कर सकते? मैं 50 से बाहर पार कर सकते हैं। लेकिन हम सिर्फ हम कहा इसलिए गुदा होने की जरूरत नहीं है के रूप में बाहर खरोंच या डेटा को छिपाने के लिए। यह वह जगह है जहाँ हम सिर्फ भूल सकता है। 

लेकिन मैं अब अपने आकार को बदलते हैं दो, यह पर्याप्त जानकारी है मेरी कतार में क्या हो रहा है पता करने के लिए? ज़रूरी नहीं। अपने आकार, दो की तरह है लेकिन कतार कहाँ से शुरू होता है, विशेष रूप से मैं अब भी है, तो स्मृति में वे एक ही नंबर। 50, 51, 61। तो मैं याद करने की जरूरत अब सामने है, जहां। और इसलिए मैं ऊपर प्रस्तावित वहाँ, हम सिर्फ बुलाया होगा जिसका प्रारंभिक Nth सामने, मूल्य क्या होना चाहिए था? शून्य, सूची की शुरुआत। लेकिन अब अलावा decrementing के लिए आकार, हम बस सामने वेतन वृद्धि। अब यहाँ एक और समस्या है। इसलिए मैं जा रहा रखने के लिए एक बार। इस की संख्या है मान लीजिए जैसे 121, 124, और फिर, dammit मैं अंतरिक्ष से बाहर हूँ। लेकिन मैं नहीं कर रहा हूँ, एक मिनट रुको। कहानी में इस बिंदु पर तो, आकार एक, दो है कि लगता है, तीन, चार, तो लगता है कि आकार, सामने से एक है, चार है इसलिए 51 मोर्चे पर है। मैं यहाँ एक और नंबर डाल करना चाहते हैं, लेकिन, Dammit, मैं अंतरिक्ष से बाहर हूँ। लेकिन मैं ठीक है, वास्तव में नहीं हूँ? मैं कुछ कहाँ डाल सकता है 171 की तरह अतिरिक्त मूल्य,? हाँ, मैं कर सकता बस की तरह ठीक है, वापस वहाँ पर जाना है? और फिर 50 पार, या सिर्फ 171 के साथ अधिलेखित। और अगर आप सोच रहे हैं क्यों हमारी संख्या है, इसलिए यादृच्छिक मिला ये आमतौर पर कंप्यूटर ले रहे हैं CS50 के बाद हार्वर्ड में विज्ञान के पाठ्यक्रमों। लेकिन यह एक अच्छा अनुकूलन था, अब क्योंकि मैं अंतरिक्ष बर्बाद नहीं कर रहा हूँ। मुझे अब भी याद करने की जरूरत कितना बड़ा इस बात की कुल है। यह पांच कुल है। क्योंकि मैं नहीं चाहता 51 overwriting शुरू करते हैं। तो अब मैं अभी भी अंतरिक्ष से बाहर हूँ, इसलिए एक ही समस्या के रूप में पहले। लेकिन अगर आप अब कैसे देख सकते हैं अपने कोड में, आप शायद एक छोटे से अधिक लिखने के लिए है जटिलता है कि ऐसा करने के लिए। और वास्तव में, क्या ऑपरेटर सी में शायद की सुविधा देता है आप जादुई इस घेरा करते हैं? हाँ सापेक्ष ऑपरेटर, प्रतिशत चिह्न। तो एक कतार के बारे में एक तरह से शांत है क्या, हम ड्राइंग सरणियों रखने के लिए भले ही इस तरह के सीधे लाइनों के रूप में, अगर आप प्रकार के curving के रूप में इस बारे में सोचते हैं चारों ओर एक चक्र के रूप में, तो बस intuitively यह एक तरह से मानसिक रूप से काम करता है मैं और अधिक सफाई से थोड़ा सा लगता है। तुम अब भी लागू करने के लिए होता है कोड में है कि मानसिक मॉडल। इसलिए नहीं कि मुश्किल है, अंत में, लागू करने के लिए लेकिन हम अभी भी बल्कि, size-- खोना हम ऐसा करते हैं, जब तक की क्षमता, आकार बदलने के लिए। 

हम सरणी से छुटकारा पाने के लिए है, हम एक भी सूचक के साथ की जगह, और तब कहीं अपने कोड में मुझे मिल गया है एक वास्तव में बनाने के लिए कार्य क्या कॉल सरणी कहा जाता संख्या? Malloc, या कुछ इसी तरह समारोह, बिल्कुल। ढेर या कतारों पर कोई सवाल नहीं। हाँ? अच्छा प्रश्न। क्या सापेक्ष आप यहाँ का प्रयोग करेंगे। तो आम तौर पर, का उपयोग करते समय रक्षा मंत्रालय, आपको यह करना होगा के आकार के साथ पूरे डेटा संरचना। तो कुछ पांच या क्षमता, जैसे अगर यह निरंतर है, शायद शामिल है। लेकिन सिर्फ सापेक्ष पांच कर शायद पर्याप्त नहीं है, हम पता करने की जरूरत है क्योंकि हम करते हैं यहाँ या यहाँ या यहाँ के आसपास लपेटो। तो आप शायद यह भी हो शामिल करना चाहते करने जा बात का आकार, या के रूप में अच्छी तरह से सामने चर। तो यह सिर्फ इस अपेक्षाकृत है सरल गणित अभिव्यक्ति, लेकिन सापेक्ष प्रमुख घटक होगा। 

तो लघु फिल्म अगर तुम जाएगा। एक एनीमेशन है कि कुछ एक और विश्वविद्यालय में लोगों को हम है कि एक साथ रखा इस चर्चा के लिए अनुकूलित। यह जैक सीखने शामिल कतारों और आँकड़ों के बारे में तथ्यों। 

फिल्म: एक समय पर एक बार, जैक एक आदमी का नाम नहीं था। यह दोस्त बनाने के लिए आया था, जैक एक आदत नहीं थी। तो जैक करने के लिए बात करने के लिए चला गया सबसे लोकप्रिय आदमी वह जानता था। उन्होंने कहा कि लो करने के लिए चला गया और मैं क्या करूँ, पूछा? लो उसके दोस्त ने देखा कि वास्तव में परेशान था। खैर, वह तो बस, शुरू किया आप तैयार कर रहे हैं कि कैसे लग रही है। आप किसी भी कपड़े नहीं है एक अलग लुक के साथ? हाँ, जैक ने कहा। मुझे वाकई है। मेरे घर आओ और मैं तुम्हें करने के लिए उन्हें दिखा देंगे। इसलिए वे जैक के लिए रवाना हो गए। और जैक लो बॉक्स से पता चला जहां वह, उसके सारे शर्ट रखा और उसकी पैंट, और उसके मोजे। लो मैं तुम्हारे पास देखते हैं, ने कहा कि एक ढेर में अपने सारे कपड़े। क्यों तुम कुछ नहीं पहनती थोड़ी देर में एक बार दूसरों? 

जैक ने कहा, ठीक है, जब मैं , कपड़े और मोजे हटाने मैं उन्हें धोने और डाल उन्हें दूर बॉक्स में। फिर अगले आता है सुबह, और मैं हॉप। मैं बॉक्स के लिए जाना और मिल ऊपर से मेरे कपड़े। लो जल्दी से पता चला जैक के साथ समस्या है। उन्होंने कहा, कपड़े, सीडी रखा और ढेर में किताबें। वह के लिए पहुंचे तो कुछ पढ़ने के लिए या पहनने के लिए, वह शीर्ष किताब या अंडरवियर का चयन होता। तब उसने किया था, जब वह यह सही वापस रखा जाएगा। इसे वापस ढेर के शीर्ष पर, जाना होगा। मैं हल पता है, विजयी जोर से कहा। आप को जानने की जरूरत है एक कतार का उपयोग शुरू। लो जैक के कपड़े ले लिया और उन्हें कोठरी में लटका दिया। और वह खाली कर दिया था जब बॉक्स, वह सिर्फ यह फेंक दिया। 

फिर वह जैक के अंत में, अब कहा, दिन, बाईं तरफ अपने कपड़े डाल आप उन्हें दूर रखा है। तो फिर कल सुबह जब आप अपने कपड़े मिलता है, धूप देखना पंक्ति के अंत से ही सही, पर। आप देख नहीं है? लो कहा। यह तो अच्छा होगा। आप एक बार सब कुछ पहनूंगी इससे पहले कि आप दो बार कुछ पहनते हैं। और कतार में सब कुछ के साथ उसकी कोठरी और शेल्फ में, जैक महसूस करने के लिए शुरू कर दिया खुद की काफी यकीन है। लो के लिए सभी धन्यवाद और अपने अद्भुत कतार। स्पीकर 1: ठीक है, यह आराध्य है। तो सच में चल रहा है क्या अब हुड के नीचे? हम संकेत है कि, हम malloc है, हम बनाने की क्षमता है कि खुद के लिए स्मृति का हिस्सा गतिशील। तो यह एक तस्वीर हम है सिर्फ दूसरे दिन झलक। हम वास्तव में ध्यान केन्द्रित करना नहीं था उस पर है, लेकिन इस तस्वीर नीचे है पर जा रहा अब सप्ताह के लिए हुड। और इसलिए इस बस का प्रतिनिधित्व करता है हम खींचा है कि एक आयत, आपके कंप्यूटर की मेमोरी। और हो सकता है आपके कंप्यूटर, या CS50 आईडी, स्मृति या राम के एक गीगाबाइट है या दो गीगाबाइट या चार। यह वास्तव में कोई फर्क नहीं पड़ता। आपका ऑपरेटिंग सिस्टम विंडोज या मैक ओएस या लिनक्स, अनिवार्य रूप से अपने कार्यक्रम की अनुमति देता है यह पहुँच गया है कि लगता है कि करने के लिए की सम्पूर्णता के लिए आपके कंप्यूटर की मेमोरी, यहां तक ​​कि आप चल रहा हो सकता है, हालांकि एक बार में कई कार्यक्रम। तो वास्तव में, कि वास्तव में काम नहीं करता है। लेकिन यह एक भ्रम की तरह है अपने सभी कार्यक्रमों के लिए दिए गए। तो अगर आप इस राम के दो gigs था कंप्यूटर इसके बारे में सोच सकते हैं कि कैसे है। 

अब संयोग से, इन में से एक बातें, स्मृति के इन क्षेत्रों में से एक, एक ढेर कहा जाता है। और वास्तव में किसी भी समय इस प्रकार अब तक लेखन कोड में तुम्हें बुलाया है कि एक उदाहरण के मुख्य के लिए समारोह,। किसी भी समय मैं याद है कि तैयार कंप्यूटर की मेमोरी, मैं हमेशा की तरह आकर्षित यहां एक आयत का आधा और बात कर परेशान नहीं करते ऊपर क्या है के बारे में। मुख्य कहा जाता है, जब मैं दावा आप स्मृति के इस ज़ुल्फ़ मिलता है कि लगता है कि यहाँ नीचे चला जाता है। मुख्य और अगर एक समारोह में बुलाया स्वैप की तरह, अच्छी तरह से स्वैप यहाँ जाता है। और यह है कि पता चला है, जहां इसे समाप्त है। एक ढेर बुलाया कुछ पर आपके कंप्यूटर की मेमोरी के अंदर। अब दिन के अंत में, इस बस को संबोधित है। यह बाइट शून्य की तरह है बाइट एक, बाइट 2 अरब। लेकिन अगर आप इसके बारे में सोचो इस आयताकार वस्तु के रूप में, सब हम हर कार्य कर रहे हैं समय हम एक समारोह है फोन स्मृति का एक नया टुकड़ा लेयरिंग। हम एक टुकड़ा है कि समारोह में दे रहे हैं अपनी खुद की स्मृति के साथ काम करने के लिए। 

और यह महत्वपूर्ण है कि अब याद करते हैं। हम क्या करना है क्योंकि अगर स्वैप की तरह कुछ ए और बी और की तरह है और दो स्थानीय चर हम एक और दो से उन मूल्यों को बदलने दो और एक, याद करने के लिए स्वैप देता है जब कि, यह इस टुकड़ा के रूप में यद्यपि है स्मृति की बस चला गया है। वास्तव में, यह अभी भी है वहाँ अपीलें। और कुछ वास्तव में अभी भी वहाँ है। लेकिन धारणा, यह के रूप में है हालांकि यह पूरी तरह से चला गया है। और तो मुख्य काम के किसी भी पता नहीं है कि, कि स्वैप समारोह में किया गया था यह वास्तव में उन लोगों में पारित कर दिया है, जब तक सूचक द्वारा या संदर्भ से तर्क। अब, मौलिक समाधान स्वैप के साथ समस्या यह है कि करने के लिए पता द्वारा में बातें गुजर रहा है। लेकिन यह भी है, क्या है, पता चला है उस भाग को ऊपर चल रहा आयत की यह सब समय है अभी तक अधिक स्मृति को वहाँ नहीं है। और जब आप गतिशील स्मृति का आवंटन, यह GetString के अंदर है, चाहे जो हम CS50 में आप के लिए कर दिया गया है पुस्तकालय, या आप लोग यदि malloc कॉल और पूछना का एक हिस्सा के लिए ऑपरेटिंग सिस्टम स्मृति, यह ढेर से नहीं आती है। यह एक और जगह से आता है अपने कंप्यूटर की स्मृति में कि ढेर कहा जाता है। और कहा कि किसी भी अलग नहीं है। यह एक ही रैम है। यह एक ही स्मृति है। यह हो रहा है कि सिर्फ रैम है वहाँ के बजाय यहाँ नीचे। 

और तो इसका क्या मतलब है? खैर, अपने कंप्यूटर है, तो स्मृति की एक निश्चित राशि और ढेर तो, आगे बढ़ रही है बात करते हैं, और ढेर अनुसार करने के लिए इस तीर को, नीचे से बढ़ रहा है। दूसरे शब्दों में, हर बार जब आप malloc कहते हैं, आप एक टुकड़ा दिया जा रहा है स्मृति के ऊपर से, एक छोटी सी है, तो कम तो शायद एक छोटे से कम है, तो आप malloc फोन हर बार, ढेर, यह प्रयोग, एक तरह से बढ़ रही है, क्या करने के लिए करीब है और करीब बढ़ रही है? ढेर। तो यह एक अच्छा विचार की तरह लग रहे हो? यह वास्तव में स्पष्ट नहीं है जहां मेरा मतलब है, आप और क्या आप केवल यदि ऐसा कर सकते हैं स्मृति की एक निश्चित राशि है। लेकिन यह निश्चित रूप से खराब है। उन दो तीर एक पर हैं एक दूसरे के लिए पाठ्यक्रम दुर्घटना। 

और यह है कि बुरा आदमी है, लोग हैं, जो पता चला है , प्रोग्रामिंग के साथ विशेष रूप से अच्छे हैं और कंप्यूटर में हैक करने की कोशिश कर रहा, इस वास्तविकता का दोहन कर सकते हैं। वास्तव में, चलो पर विचार करते हैं एक छोटा सा टुकड़ा। तो यह है कि आप पढ़ सकते हैं एक उदाहरण है के बारे में विकिपीडिया पर और अधिक विस्तार में। हम कम से बात करेंगे लेख यदि उत्सुक। लेकिन एक हमले आम तौर पर देखते है बफर अतिप्रवाह के रूप में जाना जाता है कि मनुष्य के रूप में के रूप में लंबे समय के लिए ही अस्तित्व में है हेरफेर करने की क्षमता पड़ा है विशेष रूप से सी में कंप्यूटर की मेमोरी, तो यह एक बहुत ही मनमाने ढंग से कार्यक्रम है, लेकिन नीचे से ऊपर इसे पढ़ा करते हैं। Argc चार स्टार argv में मुख्य। ऐसा लगता है कि एक कार्यक्रम है कमांड लाइन तर्क। और सभी मुख्य जाहिरा तौर पर कॉल करता है एक समारोह सादगी के लिए एफ कहते हैं। और यह क्या में गुजरता है? एक के argv। तो यह एफ में गुजरता है जो कुछ भी शब्द उपयोगकर्ता द्वारा लिखा गया है बाद प्रॉम्प्ट पर कार्यक्रम के नाम पर सब। इतना तो है कि सीजर या Vigenere, जैसे जो आप argv के साथ क्या कर याद हो सकता है। 

तो एफ क्या है? एफ एक स्ट्रिंग में ले जाता है इसकी एकमात्र तर्क के रूप में, उर्फ एक चार सितारा, एक ही बात है, एक स्ट्रिंग के रूप में। और यह मनमाने ढंग से कहा जाता है इस उदाहरण में पट्टी। और फिर चार सी 12, सिर्फ आम आदमी की दृष्टि में, हमारे लिए क्या कर रही चार ग ब्रैकेट 12 क्या है? यह क्या है? विशेष रूप से, स्मृति का आवंटन 12 वर्ण के लिए 12 बाइट्स। बिल्कुल सही। और फिर अंतिम पंक्ति, हलचल और प्रतिलिपि, तो आप शायद नहीं देखा है। यह एक स्ट्रिंग की नकल है जिसका उद्देश्य जीवन में समारोह इसका दूसरा तर्क की नकल है अपनी पहली बहस में, लेकिन केवल एक करने के लिए ऊपर बाइट्स की निश्चित संख्या। तो तीसरा तर्क कहते हैं, आप कितने बाइट्स कॉपी करना चाहिए? पट्टी की लंबाई, जो कुछ में टाइप उपयोगकर्ता। की और सामग्री कर रहे हैं, कि स्ट्रिंग पट्टी स्मृति में नकल सी पर पर बताया 

तो इस बेवकूफ की तरह लगता है, और यह है। यह एक काल्पनिक उदाहरण है, लेकिन यह प्रतिनिधि है हमले वैक्टर के एक वर्ग की, एक कार्यक्रम पर हमला करने का एक तरीका है। सब ठीक है और उपयोगकर्ता है, तो अच्छा है 11 अक्षर है कि एक शब्द में प्रकार कम, प्लस बैकस्लैश शून्य या। क्या तुलना में उपयोगकर्ता प्रकार तो और अधिक 11 या 12 या 20 या 50 अक्षर? क्या करने जा रहा यह कार्यक्रम क्या है? संभावित SEG गलती है। ये जा रहा है आँख बंद करके ऊपर के बार में सब कुछ नकल जो है इसकी लंबाई, करने के लिए सचमुच बार में सब कुछ है, पते में सी लेकिन सी में बताया केवल preemptively 12 बाइट्स के रूप में दिया गया है। लेकिन कोई अतिरिक्त चेक नहीं है। स्थितियों में अगर कोई भी नहीं है। यहाँ की जाँच के कोई त्रुटि नहीं है। 

और इसलिए इस कार्यक्रम क्या है ऐसा करने के लिए जा रही बस आँख बंद करके है दूसरे के लिए एक बात यह है कि नकल। और इसलिए हम इस आकर्षित करता है, तो एक तस्वीर के रूप में, यहाँ है स्मृति अंतरिक्ष का सिर्फ एक मुट्ठी भर लोगों। इसलिए हम, तल पर नोटिस स्थानीय चर बार है। Store-- जा रहा है कि कि सूचक तो है कि कि स्थानीय तर्क बल्कि स्ट्रिंग बार स्टोर करने के लिए जा रहा है। और फिर बस को नोटिस यह ऊपर एक ढेर में, क्योंकि आप से पूछना हर बार ढेर पर स्मृति के लिए, यह एक छोटा सा चला जाता है pictorially यह ऊपर, हम वहाँ 12 बाइट्स मिल गया है कि नोटिस। ऊपर छोड़ दिया एक सी ब्रैकेट शून्य और है नीचे सही एक सी ब्रैकेट 11 है। यही कारण है कि बस कैसे कंप्यूटर है इसे बाहर रखना करने के लिए जा रहा है। तो बस intuitively, बार अधिक है सहित कुल 12 अक्षर, से जहां बैकस्लैश शून्य, 12 या सी ब्रैकेट 12 जाने के लिए जा रहे हैं? या यों कहें कि जहां 12 वीं है चरित्र या 13 वीं चरित्र, जा रहा सौवां चरित्र चित्र में खत्म करने के लिए? ऊपर या नीचे? 

ठीक है, क्योंकि भले ही ढेर ही है, ऊपर की ओर बढ़ता है आप में सामान रख दिया है एक बार यह, यह डिजाइन कारणों के लिए, ऊपर से नीचे तक स्मृति डालता है। आप अधिक से अधिक 12 बाइट्स मिल गया है तो, आप बार अधिलेखित करने के लिए शुरू करने के लिए जा रहे हैं। अब जब कि एक बग है, लेकिन यह है नहीं वास्तव में एक बड़ा सौदा है। क्योंकि वहाँ लेकिन यह एक बड़ा सौदा है, स्मृति में चल रहा है और अधिक सामान। यहाँ तो हम कैसे हो सकता है स्पष्ट होना, हैलो डाल दिया। मैं प्रॉम्प्ट पर हैलो में टाइप हैं। एच-ई-एल-एल-ओ बैकस्लैश शून्य, भीतर समाप्त होता है उन 12 बाइट्स, और हम सुपर सुरक्षित हो। सब ठीक है। लेकिन मैं कुछ टाइप करते हैं अब, संभवतः यह है बार अंतरिक्ष में उभरा जा रहा है। लेकिन इससे भी बदतर अभी तक, यह बदल जाता है यह सब समय के बाहर, हम के बारे में कभी बात नहीं की है, भले ही यह ढेर अन्य सामान के लिए प्रयोग किया जाता है। यह सिर्फ स्थानीय चर नहीं है। 

सी एक बहुत कम स्तर की भाषा है। और यह एक तरह से गुप्त रूप से यह भी ढेर का उपयोग करता है याद है जब एक समारोह, क्या कहा जाता है पता है, पिछले समारोह का है इसलिए इसे वापस उस समारोह के लिए कूद कर सकते हैं। तो मुख्य कॉल के बीच स्वैप जब बातों के ढेर पर धकेल दिया बस, स्थानीय चर स्वैप नहीं या उसके तर्कों को भी चुपके से धक्का दिया ढेर पर प्रतिनिधित्व के रूप में यहां लाल टुकड़ा द्वारा, मुख्य का पता शारीरिक रूप से है अपने कंप्यूटर की स्मृति में, इतना है कि स्वैप किया जाता है, जब कंप्यूटर मैं मुख्य करने के लिए वापस जाने की जरूरत है जानता है और मुख्य समारोह को क्रियान्वित खत्म। तो यह है, अब खतरनाक है, क्योंकि अगर नमस्ते की तुलना में अच्छी तरह से अधिक में उपयोगकर्ता प्रकार, उपयोगकर्ता के इनपुट clobbers कि इस तरह या, कि लाल खंड लिख देगा तार्किक रूप से, अगर कंप्यूटर की बस आँख बंद करके मान जा कि लाल टुकड़ा में बाइट्स हैं कि यह वापस आ जाना चाहिए, जो करने के लिए पता, विरोधी क्या है, तो काफी होशियार या बाइट्स के एक दृश्य डालने के लिए काफी भाग्यशाली वहाँ एक पते की तरह लग रहा है कि, लेकिन यह कोड का पता है वह या वह कंप्यूटर चाहता है कि बजाय मुख्य निष्पादित करने के लिए? 

दूसरे शब्दों में, क्या हुआ अगर उपयोगकर्ता, शीघ्र पर टाइपिंग है अभी कुछ नहीं है हैलो अहानिकर की तरह लेकिन यह बराबर है कि कोड वास्तव में है यह सब प्रयोक्ता की फाइलों को नष्ट करने के लिए? या मेरे लिए उनके पासवर्ड ईमेल? या प्रवेश शुरू उनकी कीस्ट्रोक्स, है ना? एक ही रास्ता है, चलो आज बंधेज जाने वे हैलो नहीं, बस में टाइप कर सकता है कि दुनिया या उनके नाम, वे अनिवार्य रूप से कर सकता है कोड, शून्य में प्रवेश करते हैं और लोगों को, कि कंप्यूटर कोड और एक पते के लिए दोनों गलतियों। यद्यपि तो कुछ हद तक सूक्ष्म रूप में, यदि पर्याप्त विरोधात्मक कोड में उपयोगकर्ता प्रकार हम यहाँ के रूप में सामान्यीकरण हूँ कि ए एक हमले या द्रोहियों है। तो बस बुरी चीज है। हम के बारे में परवाह नहीं है नंबर या शून्य या लोगों आज, अगर आप इस तरह है कि अंत कि लाल खंड overwriting, बाइट्स के अनुक्रम कि नोटिस। हे 835 सी शून्य आठ शून्य। और अब यहाँ विकिपीडिया के लेख के रूप में अब आप वास्तव में शुरू, प्रस्ताव किया है आपके कंप्यूटर में बाइट्स लेबलिंग स्मृति, विकिपीडिया लेख क्या है प्रस्ताव है, कि क्या पता है, तो कि ऊपर छोड़ दिया बाइट के 80 सी 0 3508 है। 

दूसरे शब्दों में, बुरा आदमी है, तो अपने या अपने कोड के साथ काफी होशियार वास्तव में यहाँ एक नंबर डालने के लिए कि कोड का पता करने के लिए संगत वह या वह इंजेक्ट कंप्यूटर में है, तो आप कंप्यूटर चाल कर सकते हैं कुछ भी करने में। , फ़ाइलों को हटाने ईमेल बातें, अपने यातायात सूँघने सचमुच कुछ भी हो सकता है कंप्यूटर में इंजेक्शन। और हां एक बफर अतिप्रवाह इसके मूल में हमले सिर्फ एक बेवकूफ, बेवकूफ है एक सरणी का सर्वोपरि कि अपनी सीमाओं की जाँच की ज़रूरत नहीं थी। और इस सुपर खतरनाक है क्या है और इसके साथ ही सुपर शक्तिशाली सी में हम वास्तव में क्या करना है वह यह है कि स्मृति में कहीं भी करने के लिए उपयोग। यह हम पर निर्भर है, प्रोग्रामर, जो मूल कोड लिखने किसी भी रफ़ू लंबाई की जांच करने के लिए हम जोड़ तोड़ कर रहे हैं कि सरणियों। तो स्पष्ट हो, तय क्या है? हम यह करने के लिए वापस रोल कोड, मैं नहीं करना चाहिए बस पट्टी की लंबाई को बदलने, क्या वरना मैं जाँच की जानी चाहिए? मैं और क्या कर किया जाना चाहिए पूरी तरह से इस हमले को रोकने? मैं बस आँख बंद करके कहने के लिए नहीं करना चाहते हैं आप के रूप में कई बाइट्स कॉपी चाहिए कि के रूप में पट्टी की लंबाई है। मैं के रूप में कॉपी कहना चाहता हूँ, के रूप में कई बाइट्स बार में कर रहे हैं आवंटित करने के लिए ऊपर स्मृति, या ज़्यादा से ज़्यादा 12। इसलिए मैं हालत में अगर किसी तरह की जरूरत कि बार की लंबाई की जांच करता है, लेकिन यह 12 है, हम सिर्फ कड़ी मेहनत कोड से अधिक है अधिकतम संभव दूरी के रूप में 12। अन्यथा तथाकथित बफर अतिप्रवाह हमले हो सकता है। उन स्लाइड के तल में, आप और अधिक पढ़ने के लिए उत्सुक हैं वास्तविक मूल लेख है आप एक बार देख लेने के लिए चाहते हैं। 

लेकिन अब, कीमतों के बीच अक्षमताओं यहाँ था भुगतान किया। तो यह है कि एक त्वरित था पर निम्न स्तर देखो क्या समस्या यह है कि हम अब पैदा कर सकते हैं कंप्यूटर की स्मृति के लिए उपयोग किया है। लेकिन एक और समस्या है, हम पहले से ही सोमवार को ठोकर खाई सिर्फ अक्षमता था एक लिंक सूची की। हम वापस रैखिक समय के लिए कर रहे हैं। हम अब एक सन्निहित सरणी है। हम यादृच्छिक पहुँच नहीं है। हम वर्ग कोष्ठक संकेतन का उपयोग नहीं कर सकते हैं। हम सचमुच एक जबकि पाश का उपयोग किया है एक तरह से मैं एक पल पहले लिखा था। लेकिन सोमवार को, हम कर सकते हैं हम दावा किया है कि दक्षता के दायरे में वापस रेंगना कुछ है कि प्राप्त करने लघुगणक हो सकता है, या सबसे अच्छा अभी तक, है कि शायद यह भी कुछ लगातार समय तथाकथित। इसलिए हम इन नए का उपयोग करते हुए कि कैसे कर सकते हैं उपकरण, इन पतों, ये संकेत, और हमारी खुद की चीजों के सूत्रण? खैर, लगता है कि यहाँ, ये एक गुच्छा रहे हैं हम एक में स्टोर करना चाहते है कि संख्या की कुशलता से डेटा संरचना और खोज। हम पूरी तरह से सप्ताह के लिए उल्टा कर सकते हैं दो, एक सरणी में इन फेंक और द्विआधारी खोज का उपयोग कर उन्हें खोज। फूट डालो और राज करो। और वास्तव में आप ने लिखा PSET3 में द्विआधारी खोज, तुम कहाँ मिलेंगे कार्यक्रम लागू किया है। लेकिन क्या आप जानते हैं। एक और अधिक की तरह नहीं है इस कर के चालाक रास्ता। यह एक छोटे से अधिक है परिष्कृत और यह शायद हमें क्यों बाइनरी देखने की अनुमति देता खोज बहुत तेजी से ऐसा है। पहले, चलो परिचय एक पेड़ की धारणा। जो भी में यद्यपि वास्तविकता के पेड़ की तरह है कंप्यूटर की दुनिया में, इस तरह विकसित वे एक तरह से नीचे की ओर बढ़ने विज्ञान तुम्हारे पास है, जहां एक परिवार के पेड़ की तरह, अपने दादा-दादी या महान दादा-दादी या whatnot शीर्ष, कुलपति पर और परिवार की कुलमाता, सिर्फ एक जड़, नोड, नीचे तथाकथित अपने बच्चों को जो कर रहे हैं, जो नीचे अपने बच्चों को कर रहे हैं, या उसके वंश अधिक आम तौर पर। और किसी को भी फांसी परिवार के नीचे पेड़, होने के अलावा परिवार में सबसे छोटा, यह भी सिर्फ सामान्य रूप से किया जा सकता है पेड़ की पत्तियों का आह्वान किया। 

तो यह सिर्फ एक गुच्छा है शब्दों और परिभाषाओं की कुछ के लिए कंप्यूटर में एक पेड़ बुलाया विज्ञान, एक परिवार के पेड़ की तरह ज्यादा। लेकिन शौक़ीन अवतारों वहाँ पेड़ों की, जिनमें से एक एक द्विआधारी खोज वृक्ष कहा जाता है। और आप कर सकते हैं चिढ़ाने की तरह इस बात करता है के अलावा क्या। खैर, यह क्या अर्थ में द्विआधारी है? कहाँ द्विआधारी यहाँ से आया है? क्षमा करें? यह इतना एक या तो है या नहीं। यह नोड्स के प्रत्येक कोई है कि अधिक है दो से अधिक बच्चे हैं, हम यहां देखने के रूप में। सामान्य, एक tree-- में और अपने माता-पिता और दादा-दादी के रूप में कई बच्चे हैं, कर सकते हैं या पोते वे वास्तव में चाहते हैं के रूप में, और तो उदाहरण के लिए वहाँ हम तीन हैं कि दाहिने हाथ नोड बंद बच्चों, लेकिन एक द्विआधारी पेड़ में एक नोड है ज़्यादा से ज़्यादा शून्य, एक या दो बच्चे। और वह है, एक अच्छा संपत्ति है यह दो से छाया हुआ है, क्योंकि अगर हम करने के लिए सक्षम होने के लिए जा रहे हैं एक छोटी सी लॉग आधार मिलता दो कार्रवाई यहाँ अंततः चल रहा है। इसलिए हम लघुगणक कुछ है। लेकिन एक पल में उस पर और अधिक। खोज वृक्ष संख्या रहे हैं कि इसका मतलब है व्यवस्था की है कि इस तरह बाएं बच्चे की मूल्य जड़ से अधिक है। और इसकी सही बच्चा है जड़ से बड़ा। दूसरे शब्दों में, आप में से किसी भी लेते हैं नोड्स, इस तस्वीर में हलकों, और बायीं पर लग रहा है बच्चे और उसके सही बच्चे, पहले की तुलना में कम होना चाहिए दूसरे से अधिक होना चाहिए। तो विवेक 55 की जाँच करें। यह बच्चे छोड़ दिया है 33 है। की तुलना में यह कम है। 55, इसकी सही बच्चे 77 है। यह अधिक से अधिक है। और कहा कि एक पुनरावर्ती परिभाषा है। हम उन लोगों में से हर एक की जांच कर सकता नोड्स और आयोजित करेंगे एक ही पैटर्न। 

तो एक में अच्छा क्या है द्विआधारी खोज वृक्ष है, एक है कि, हम इसे लागू कर सकते हैं एक संरचना के साथ, बस यह पसंद है। और हम फेंक रहे हैं, भले ही अपने पर संरचनाओं के बहुत सारे, वे कुछ हद तक कर रहे हैं सहज ज्ञान युक्त अब उम्मीद है कि। वाक्य रचना, अभी भी यकीन के लिए रहस्यमय है लेकिन इस में एक नोड की सामग्री context-- और हम रखना शब्द नोड का उपयोग, यह एक आयत है कि क्या स्क्रीन या एक चक्र पर, यह सिर्फ कुछ सामान्य कंटेनर है एक तरह एक पेड़ के इस मामले में हम एक पूर्णांक की जरूरत है, देखा नोड्स में से प्रत्येक में और फिर मैं दो संकेत इशारा करते हुए की जरूरत है बाएं बच्चे और सही बच्चे को, क्रमशः। इतना है कि हम कैसे हो सकता है एक संरचना में है कि लागू करने। और कैसे मैं कोड में यह लागू हो सकता है? ठीक है, चलो एक त्वरित ले चलो इस छोटे से उदाहरण देखो। यह कार्यात्मक नहीं है, लेकिन मैं नकल की और संरचना है कि चिपकाया। और अगर एक द्विआधारी के लिए मेरे समारोह खोज पेड़, खोज कहा जाता है और यह दो तर्क लेता है, एक पूर्णांक एन और एक सूचक पेड़ के लिए एक नोड, तो एक संकेतक के लिए या एक पेड़ की जड़ के लिए एक सूचक, कैसे मैं एन के लिए खोज के बारे में जाना है? खैर, सबसे पहले, मैं कर रहा हूँ क्योंकि संकेत के साथ काम कर रहे हैं, मैं एक मानसिक स्वास्थ्य की जांच करने जा रहा हूँ। पेड़ बराबरी बातिल के बराबर होती है, तो एन है इस पेड़ में है या नहीं इस पेड़ में? यह ठीक है, नहीं हो सकता? मैं अशक्त अतीत हूँ, यहां तो कुछ नहीं। मैं शायद के रूप में अच्छी तरह से बस आँख बंद करके वापसी झूठी कहते हैं। क्या आप मुझे कुछ भी नहीं देते हैं, मैं निश्चित रूप से नहीं कर सकते किसी भी नंबर एन मिल बाकी तो क्या मैं हो सकता है अब जांचें? मैं अच्छी तरह से किसी और एन है, तो कहने जा रहा हूँ पेड़ नोड में जो कुछ भी है, कम से कम मैं एन मूल्य सौंप दिया गया है कि। दूसरे शब्दों में, संख्या मैं कर रहा हूँ एन, के लिए लग रही है, नोड से कम है मैं देख रहा हूँ कि। और नोड मैं देख रहा हूँ पेड़ कहा जाता है पर, और पिछले उदाहरण से याद करते हैं एक सूचक में मूल्य पर पाने के लिए, मैं तीर संकेतन का उपयोग करें। एन पेड़ तीर से कम है तो अगर एन, मैं धारणात्मक बाईं जाना चाहता हूँ। मैं कैसे छोड़ दिया सर्च कर रहे हैं व्यक्त करते हैं? अगर यह होता है, स्पष्ट होना प्रश्न में चित्र, और मैं पारित किया गया है सर्वोच्च कि कि नीचे की ओर इशारा करते के तीर। यही कारण है कि मेरी पेड़ सूचक है। मैं पेड़ की जड़ में इशारा कर रहा हूँ। और मैं के लिए, कहते हैं देख रहा हूँ मनमाने ढंग से नंबर 44,। है 44 से कम या जाहिर है कि 55 से अधिक से अधिक? तो यह की तुलना में कम है। और इसलिए अगर यह शर्त लागू होती है। तो धारणात्मक, मैं करने के लिए क्या करना चाहते हैं मैं 44 के लिए देख रहा हूँ कि अगर अगले खोज? हाँ? 

वास्तव में, मैं चाहता हूँ बाएं बच्चे, खोज या इस तस्वीर की बाईं उप पेड़। और वास्तव में, मुझे के माध्यम से जाने यहाँ नीचे चित्र बस एक पल के लिए, के बाद से मैं इस बाहर खरोंच नहीं कर सकते हैं। मैं 55 से यहाँ शुरू, और तो मुझे पता है कि मूल्य 44 करने के लिए है के लिए मैं देख रहा हूँ छोड़ दिया, यह एक तरह है की में फोन की किताब फाड़ की तरह आधा या आधे में पेड़ फाड़। मैं अब और नहीं के बारे में परवाह है पेड़ के इस पूरे आधा। और फिर भी, मजे की बात है के मामले में संरचना, कि यहाँ पर इस बात 33 के साथ शुरू होता ही है कि एक द्विआधारी खोज वृक्ष है। मैं क्योंकि पहले शब्द पुनरावर्ती कहा वास्तव में यह एक आंकड़ा संरचना है कि परिभाषा के द्वारा पुनरावर्ती है। आप इस बात है कि एक पेड़ के लिए हो सकता है बड़ा है, लेकिन अपने बच्चों की हर एक छोटे सिर्फ एक छोटे से एक पेड़ का प्रतिनिधित्व करता है। इसके बजाय यह की दादा जा रहा है या दादी, अब यह सिर्फ माँ है or-- मैं माँ नहीं say-- नहीं कर सकते या पिता, कि अजीब होगा। वहाँ के बजाय दो बच्चे भाई और भाई की तरह होगा। परिवार के पेड़ की एक नई पीढ़ी। लेकिन संरचनात्मक रूप से, यह एक ही विचार है। उस समय मैं एक समारोह है पता चला है जिसके साथ मैं एक द्विआधारी खोज खोज कर सकते हैं पेड़। यह खोज कहा जाता है। मैं पेड़ तीर बाएँ में एन के लिए खोज एन मूल्य से अधिक है और अगर कि मैं वर्तमान में हूँ। एक पल पहले कहानी में 55। मैं एक समारोह है खोज है कि मैं सिर्फ यह कर सकते हैं एन इस गुजरती हैं और बारी बारी से खोज उप पेड़ और सिर्फ वापसी कि जो कुछ भी जवाब नहीं। वरना मैं यहाँ कुछ अंतिम आधार के मामले मिल गया है। 

अंतिम मामला क्या है? ट्री या तो रिक्त है। मैं किसी के लिए देख रहा हूँ मूल्य है इसके अलावा भी यह कम से कम या अधिक से अधिक या इसे करने के बराबर है। और मैं बराबर कह सकते हैं बराबर है, लेकिन यह तार्किक है बस यहाँ कुछ और कह रही करने के लिए बराबर है। तो सच है कि मैं कुछ मिल रहा है। इसलिए उम्मीद है कि यह एक है और भी अधिक सम्मोहक उदाहरण बेवकूफ सिग्मा समारोह से हम वापस कुछ व्याख्यान किया जहां यह एक पाश का उपयोग करने के लिए बस के रूप में आसान था एक से सभी नंबरों तक गिनती एक डेटा संरचना के साथ यहाँ एन करने के लिए खुद को बारी बारी है कि अब हम परिभाषित और बारी बारी से खींचा अपने आप को व्यक्त करने की क्षमता है कोड में ही पुनरावर्ती है। तो यह यहाँ ठीक उसी कोड है। 

तो हम क्या अन्य समस्याओं को हल कर सकते हैं? दूर से तो एक त्वरित कदम बस एक पल के लिए पेड़। यहाँ है, जर्मन झंडा कहते हैं। और स्पष्ट रूप से वहाँ एक इस ध्वज को पैटर्न। और वहाँ बहुत सारे दुनिया में झंडे कि मामले में यह रूप में सरल कर रहे हैं उनके रंग और पैटर्न की। लेकिन इस एक के रूप में जमा है, लगता है कि .GIF, या एक जेपीईजी, या बिटमैप, या एक पिंग, किसी भी ग्राफिकल फ़ाइल स्वरूप जिसके साथ आप परिचित हैं हम कर रहे हैं, जिनमें से कुछ PSET4 में साथ खेल रहा है। इस स्टोर करने के लिए सार्थक प्रतीत नहीं होता काला पिक्सेल, काले पिक्सेल, काले पिक्सेल, दूरसंचार विभाग, दूरसंचार विभाग, दूरसंचार विभाग, की एक पूरी गुच्छा पहली scanline के लिए काले पिक्सल, या पंक्ति है, तो एक पूरी गुच्छा एक ही है, तो एक पूरी गुच्छा तो एक ही है, और की लाल पिक्सल की पूरी गुच्छा, लाल पिक्सल, लाल पिक्सल, तो एक पूरे पीले रंग पीला पिक्सल का गुच्छा, है ना? 

ऐसी अक्षमता यहाँ है। कैसे intuitively तुम होगा जर्मन झंडा सेक एक फ़ाइल के रूप में इसे लागू तो क्या होगा? क्या जानकारी की तरह हम नहीं कर सकते आदेश में डिस्क पर भंडारण के लिए परेशान तरह से हमारे फ़ाइल आकार को कम करने के लिए एक किलोबाइट, कुछ करने के लिए एक मेगाबाइट छोटे? जिसमें अतिरेक निहित है यहाँ स्पष्ट हो सकता है? आप क्या कर सकते थे? हाँ? बिल्कुल सही। क्यों नहीं बजाय याद हर रफ़ू पिक्सेल का रंग बस आप PSET4 में क्या कर रहे हैं बिटमैप फ़ाइल स्वरूप के साथ, क्यों तुम सिर्फ प्रतिनिधित्व नहीं करते उदाहरण के लिए पिक्सल के सबसे बाएँ स्तंभ, काले पिक्सल का एक गुच्छा, एक गुच्छा लाल रंग का है, और पीले रंग का एक गुच्छा, और फिर बस किसी भी तरह सांकेतिक शब्दों में बदलना दोहराने का विचार इस 100 बार या यह 1,000 बार दोहराने? जहां 100 या 1,000 है सिर्फ एक पूर्णांक, तुम इतनी सिर्फ एक ही नंबर के साथ भाग ले सकते हैं बजाय सैकड़ों या हजारों की के अतिरिक्त पिक्सल। और वास्तव में, कि हम कैसे है जर्मन झंडा सेक कर सकता है। और फ्रांसीसी ध्वज के बारे में अब क्या? किसी प्रकार की और एक छोटे से मानसिक व्यायाम, जो झंडा डिस्क पर अधिक संकुचित किया जा सकता है? जर्मन झंडा या फ्रेंच झंडा, हम उस दृष्टिकोण रखना तो क्या होगा? जर्मन झंडा, क्योंकि वहाँ अधिक क्षैतिज अतिरेक। और डिजाइन के द्वारा, कई चित्रमय फ़ाइल स्वरूपों वास्तव में के रूप में लाइनों स्कैन काम करते हो क्षैतिज। वे काम कर सकता था खड़ी, बस मानवता निर्णय लिया साल पहले कि हम करेंगे आम तौर पर चीजों पंक्ति के बारे में सोच स्तंभ से पंक्ति की बजाय स्तंभ द्वारा। तो वास्तव में अगर तुम थे फ़ाइल को देखने के लिए एक जर्मन झंडा और एक फ्रेंच का आकार झंडा, इतने लंबे समय के संकल्प के रूप में है एक ही, एक ही चौड़ाई और ऊंचाई, यह एक यहाँ, बड़ा होने जा रहा है आप क्योंकि अपने आप को तीन बार दोहराने के लिए है। आप नीले, दोहराने निर्दिष्ट करने के लिए अपने आप को, सफेद, लाल, अपने आप को दोहराना अपने आप को दोहराना। तुम बस सब नहीं जा सकते सही करने के लिए तरीका है। और एक अलग रूप में, बनाने के लिए संपीड़न स्पष्ट इन कर रहे हैं, तो हर जगह है एक video-- से चार फ्रेम आप एक फिल्म याद है कि हो सकता है या वीडियो आम तौर पर है प्रति सेकंड 29 या 30 फ्रेम की तरह। यह एक छोटे से फ्लिप किताब की तरह है, जहां आप बस छवि, छवि, छवि, छवि देखते हैं, छवि सिर्फ सुपर फास्ट इसलिए ऐसा लग रहा है स्क्रीन पर अभिनेताओं से आगे बढ़ रहे हैं। यहाँ एक मधुमक्खी bumble पर है फूलों का एक गुच्छा के शीर्ष। और यह किस तरह की हो सकती है, हालांकि पहली नज़र में देखने के लिए मुश्किल है, में आगे बढ़ ही बात इस फिल्म मधुमक्खी है। 

क्या भंडारण के बारे में गूंगा है वीडियो असम्पीडित? यह वीडियो स्टोर करने के लिए एक कचरे की तरह है चार लगभग समान छवियों के रूप में है कि केवल insofar मधुमक्खी है जहां के रूप में भिन्न होते हैं। आप दूर फेंक कर सकते हैं सबसे कि सूचना के और केवल याद है, उदाहरण के लिए, पहला फ्रेम और अंतिम फ्रेम, आप है, तो मुख्य फ्रेम कभी, शब्द सुना और बस में स्टोर मधुमक्खी है जहां मध्य। और आप की जरूरत नहीं है गुलाबी रंग के सभी स्टोर नीले, और और हरी मूल्यों के रूप में अच्छी तरह से। तो यह है कि केवल कहने के लिए है संपीड़न हर जगह है। यह हम अक्सर उपयोग एक तकनीक है इन दिनों के लिए दी है या ले। 

लेकिन आप कैसे पाठ सेक है? कैसे आप पाठ compressing के बारे में जाना है? खैर, पात्रों में से प्रत्येक में आस्की एक बाइट, या आठ बिट है। और उस तरह का गूंगा, सही है? आप शायद एक टाइप क्योंकि और ई और मैं और ओ और यू एक बहुत अधिक बार डब्ल्यू या क्यू या जेड की तरह से, भाषा के आधार पर जिसमें आप निश्चित रूप से लिख रहे हैं। और तो क्यों हम प्रयोग कर रहे हैं हर पत्र के लिए आठ बिट, कम से कम सहित लोकप्रिय पत्र, है ना? क्यों के लिए कम बिट्स का उपयोग नहीं सुपर लोकप्रिय पत्र, ई की तरह, बातें आप अनुमान लगा पहले फॉर्च्यून की व्हील में, और के लिए और अधिक बिट का उपयोग कम लोकप्रिय पत्र? क्यों? हम सिर्फ करने के लिए जा रहे हैं, क्योंकि कम बार उन्हें इस्तेमाल करते हैं। 

खैर, यह वहाँ पता चला है कि यह करने के लिए किए गए प्रयासों के लिए किया गया। और अगर आप कक्षा से याद करते हैं स्कूल या हाई स्कूल, मोर्स कोड। मोर्स कोड डॉट्स है और डैश हो सकता है कि एक तार के रूप में साथ प्रेषित लगता है या किसी तरह के संकेत है। लेकिन मोर्स कोड एक सुपर साफ है। आईटी में एक बाइनरी सिस्टम की तरह है कि आप डॉट्स या डैश है। लेकिन तुम, उदाहरण के लिए, दो डॉट्स देखते हैं। या फिर आप ऑपरेटर के लिए वापस अगर आपको लगता कौन, बीप, बीप, बीप की तरह चला जाता है बीप, एक छोटे से ट्रिगर मार एक संकेत है कि पहुंचाता है, अगर तुम, प्राप्तकर्ता, दो को प्राप्त करता है डॉट्स, क्या संदेश आप प्राप्त हुआ है? पूरी तरह से मनमाना। 

मैं? मैं? या फिर क्या about-- या मैं? शायद यह सिर्फ दो ई सही था? तो यह समस्या नहीं है मोर्स के साथ decodability की कोड, जिसके तहत जब तक आप संदेश भेजने के व्यक्ति वास्तव में ऐसा है तो आप की तरह कर सकते हैं रुक जाता है देखते हैं या अक्षरों के बीच अंतराल को सुना है, यह सिर्फ करने के लिए पर्याप्त नहीं है शून्य और लोगों की एक धारा भेजने, या डॉट्स और डैश, अस्पष्टता है क्योंकि वहाँ। ई एक एकल डॉट है, इसलिए अगर आप दो डॉट्स देख या दो डॉट्स सुना है, हो सकता है यह दो ई है या हो सकता है कि यह एक आई है तो हम एक बात है कि एक प्रणाली की जरूरत है कि अधिक से अधिक चतुर थोड़ा। तो एक आदमी का नाम दिया Huffman साल पहले वास्तव में इस के साथ आया था। तो हम बस जा रहे हैं एक नज़र लेने के लिए कैसे पर पेड़ इस के लिए सार्थक कर रहे हैं। यह कुछ है कि मान लीजिए आप भेजना चाहते हैं बेवकूफ संदेश, सिर्फ ए, बी की रचना की, सी डी एस और ई, लेकिन अतिरेक का एक बहुत यहाँ नहीं है। यह अंग्रेजी होने का मतलब नहीं है। यह एन्क्रिप्टेड नहीं है। यह सिर्फ एक बेवकूफ संदेश है पुनरावृत्ति के बहुत से। आप वास्तव में बाहर गिनती तो अगर सब एक है, बी, सी, डी एस, ई और के, यहाँ है आवृत्ति। पत्र की 20% कर रहे हैं एक है, पत्र के 45% ई, और तीन अन्य आवृत्तियों रहे हैं। हम स्वयं वहाँ ऊपर गिना और सिर्फ गणित किया। 

तो यह पता चला है कि Huffman, कुछ समय पहले, तुम्हें पता है, कि मुझे एहसास हुआ क्या, मैं निर्माण शुरू करता है, तो एक पेड़, या पेड़ों के जंगल, अगर तुम जाएगा, इस प्रकार के रूप में, मैं निम्न कर सकते हैं। मैं प्रत्येक के लिए एक नोड देने जा रहा हूँ मैं के बारे में परवाह है कि पत्र की और मैं स्टोर करने के लिए जा रहा हूँ उस नोड के अंदर एक चल बिन्दु के रूप में आवृत्तियों मूल्य हैं, या आप भी, एक एन इसे इस्तेमाल कर सकते लेकिन हम यहाँ सिर्फ एक नाव का उपयोग करेंगे। और एल्गोरिथ्म कि उन्होंने कहा कि आप यह है कि प्रस्तावित एकल नोड के इस जंगल में लेने पेड़, इसलिए सुपर छोटे पेड़, और उन्हें अपने साथ जोड़ने के लिए शुरू नए समूहों, नए माता-पिता, अगर तुम जाएगा। और आप का चयन करके इस करते हैं एक समय में दो छोटी से छोटी आवृत्तियों। इसलिए मुझे लगता है 10% और 10% ले लिया। मैं एक नया नोड बनाने। और मैं नए नोड 20% कहते हैं। 

जो दो नोड्स मैं अगले गठबंधन? यह एक छोटे से अस्पष्ट है। तो किसी कोने मामलों रहे है विचार है, लेकिन बहुत सी बातें रखने के लिए, मैं 20% का चयन करने के लिए जा रहा हूँ - मैं अब बच्चों की उपेक्षा। मैं 20% का चयन करने के लिए जा रहा हूँ और 15% और दो नए किनारों आकर्षित। और अब जो दो नोड्स मैं तार्किक गठबंधन करते हैं? सभी बच्चों, सब पर ध्यान न दें पोते, बस जड़ों को देखो अब। जो दो नोड्स मैं एक साथ टाई हो? बिंदु दो और 0.35। तो मुझे दो नए किनारों आकर्षित करते हैं। और फिर मैं एक ही छोड़ दिया गया है। तो यहाँ एक पेड़ है। और यह जानबूझ कर तैयार की गई है एक तरह से सुंदर लग रही करने के लिए, लेकिन किनारों है कि नोटिस यह भी शून्य और एक चिह्नित किया गया। इसलिए छोड़ दिया किनारों के सभी शून्य हैं मनमाने ढंग से है, लेकिन लगातार। सभी अधिकार किनारों वाले हैं। 

और तो हॉफमैन, प्रस्तावित क्या आप एक बी का प्रतिनिधित्व करना चाहते हैं, के रूप में नंबर 66 का प्रतिनिधित्व करने के बजाय आठ पूरे बिट्स है जो एक ASCII, आप क्या, सिर्फ दुकान में पता पैटर्न शून्य, शून्य, शून्य, शून्य कि रास्ता है, क्योंकि मेरे पेड़ से, श्री Huffman का पेड़, जड़ से पत्ती को। आप एक स्टोर करना चाहते हैं ई, इसके विपरीत, नहीं करते एक ई प्रतिनिधित्व करते हैं कि आठ बिट्स भेजने इसके बजाय, बिट्स की क्या पैटर्न भेज सकते हैं? एक। और यह है के बारे में क्या अच्छा है कि ई सबसे लोकप्रिय पत्र है, और आप उपयोग कर रहे हैं इसके लिए कम से कम कोड। अगले सबसे लोकप्रिय पत्र ऐसा लग रहा है ए था और इसलिए कितने बिट्स वह उस के लिए उपयोग कर का प्रस्ताव किया? शून्य से एक। 

और इसे लागू किया है, क्योंकि इस पेड़ के रूप में, अब के लिए मुझे वहाँ बंधेज जाने मोर्स के रूप में कोई अस्पष्टता कोड, क्योंकि सारी आप के बारे में परवाह पत्र इन किनारों के अंत में कर रहे हैं। तो यह है कि सिर्फ एक ही है एक पेड़ के आवेदन। यह है- और मैं लहर हूँ इस पर मेरे हाथ कैसे आप एक सी संरचना के रूप में यह लागू हो सकता है। हम सिर्फ गठबंधन की जरूरत है एक प्रतीक है, एक चार तरह, और आवृत्ति में छोड़ दिया और सही। लेकिन दो को देखो अंतिम उदाहरण है कि आप हूँ के बाद से काफी परिचित मिल समस्या में प्रश्नोत्तरी शून्य से पांच सेट। 

तो डेटा संरचना है एक हैश तालिका के रूप में जाना जाता है। और एक हैश तालिका तरह का है यह बाल्टी है कि में ठंडा। और चार बाल्टी लगता है कि वहाँ यहां सिर्फ चार रिक्त स्थान। यहाँ यहाँ है ताश के पत्तों की एक डेक है, और क्लब, कुदाल, क्लब, हीरे, क्लब, हीरे, क्लब, हीरे, clubs-- तो यह यादृच्छिक है। दिल, hearts-- तो मैं कर रहा हूँ यहां आदानों की सभी bucketizing। और एक हैश तालिका की जरूरत है अपने इनपुट को देखने के लिए, और फिर एक निश्चित में डाल दिया आप देखते हैं, उसके आधार पर जगह है। यह एक एल्गोरिथ्म है। और मैं एक सुपर उपयोग कर रहा था साधारण दृश्य एल्गोरिथ्म। जिनमें से सबसे कठिन हिस्सा था चित्रों थे याद क्या। और फिर चार कुल बातें की। 

अब ढेर, बढ़ रहे थे, जो यहाँ एक विचार डिजाइन बात है। लेकिन मैं और क्या कर सकता है? तो वास्तव में यहाँ हम एक पुराने स्कूल परीक्षा पुस्तकों का गुच्छा। का एक गुच्छा है कि मान लीजिए छात्रों के नाम यहां पर हैं। यहाँ एक बड़ा हैश तालिका है। इसके बजाय चार बाल्टी की, मैं 26 हम कहते हैं कि है। और हम 26 उधार ले जाने के लिए नहीं करना चाहता था बाहर [से बातें? Annenberg?], इसलिए यहां का प्रतिनिधित्व करते हैं कि पांच है एक जेड के माध्यम से और यदि मैं जिसका नाम एक साथ शुरू होता है एक छात्र को देखने मैं वहां अपने या अपने प्रश्नोत्तरी डाल करने के लिए जा रहा हूँ। किसी सी के साथ शुरू होता है, वहाँ पर, एक-- वास्तव में, ऐसा करने के लिए नहीं चाहता था। बी यहाँ पर चला जाता है। तो मुझे मिल गया है एक और बी और सी और अब यहाँ एक और एक छात्र की। लेकिन इस हैश तालिका है यदि एक सरणी के साथ लागू किया, मैं एक तरह से खराब कर दिया हूँ इस बिंदु पर, है ना? मैं एक तरह से इस कहीं डाल दिया है। 

इसलिए मैं इस का समाधान कर सकते हैं एक ही रास्ता है, सब है सही, एक सी में व्यस्त है, बी व्यस्त है, व्यस्त है। मैं तो डी में उसे डाल करने के लिए जा रहा हूँ सबसे पहले, मैं यादृच्छिक त्वरित पहुँच है छात्रों के लिए बाल्टियों में से प्रत्येक के लिए। लेकिन अब यह एक तरह से न्यागत है कुछ रैखिक में, मैं किसी के लिए खोज करना चाहते हैं, क्योंकि जिसका नाम एक साथ शुरू होता है, मैं यहाँ की जाँच करें। लेकिन यह एक नहीं है, तो मेरी चाहत छात्र, मैं एक तरह से जाँच शुरू कर दिया है बाल्टी, मैंने क्या किया है क्योंकि के रैखिक प्रकार का था डेटा संरचना की जांच। बस देखो कहने का एक बेवकूफ तरीका पहली उपलब्ध खोलने के लिए, और, इतनी बात करने के लिए एक योजना बी के रूप में डाल दिया या इस मामले में योजना डी, मूल्य बजाय उस स्थान में। मतलब यह है कि आप है, तो बस इतना है 26 स्थानों और कोई छात्र मिला नाम क्यू या जेड, या कुछ और तरह के साथ कि, कम से कम आप जगह का उपयोग कर रहे हैं। 

लेकिन हम पहले से अधिक देखा है यहां चतुर समाधान, है ना? आप के बजाय क्या होगा आप एक टकराव है तो क्या होगा? दो लोगों को है, तो नाम ए, क्या होगा एक चालाक या अधिक कर दिया गया है बस से सहज ज्ञान युक्त समाधान डी माना जाता है जहां एक डाल? क्यों मैं बस जाना नहीं है बाहर [? Annenberg?], malloc, अन्य नोड की तरह, यह डाल यहां, और फिर एक छात्र यहाँ कि डाल दिया। मैं अनिवार्य रूप से इतना है कि एक सरणी में किसी तरह का, या हम कर रहे हैं के रूप में हो सकता है और अधिक सुंदर ढंग से एक लिंक सूची देखने के लिए शुरू। 

और हां एक हैश तालिका एक संरचना है कि, बस इस तरह लग सकता है लेकिन अधिक बड़ी चतुराई से, आप कुछ कहा अलग श्रृंखलन, जिससे एक हैश तालिका काफी बस एक सरणी के प्रत्येक है, जिसका तत्वों एक नंबर नहीं है, एक लिंक सूची ही है। आप सुपर फास्ट उपयोग हो तो जहां के लिए अपने मूल्य हैश करने के लिए निर्णय लेने से। ज्यादा कार्ड उदाहरण के साथ की तरह, मैं सुपर त्वरित निर्णय किया। दिल हीरे यहाँ जाता है, यहाँ जाता है। यहाँ भी वही, एक यहाँ जाता है, डी बी यहाँ जाता है, यहाँ जाता है। तो सुपर फास्ट लुक-अप, और यदि आप एक मामले में चलाने के लिए होता है जहां तुम मिल गया टकराव, दो एक ही नाम के साथ लोगों को अच्छी तरह से तो तुम सिर्फ उन्हें एक साथ जोड़ने के लिए शुरू। और शायद आप उन्हें हल रखना वर्णानुक्रम, शायद तुम नहीं। लेकिन कम से कम अब हम गतिशीलता है। इसलिए एक ओर हम सुपर फास्ट है लगातार समय, और रैखिक समय की तरह इन लिंक सूचियों यदि शामिल एक छोटे से लंबे समय पाने के लिए शुरू करते हैं। 

तो एक मूर्ख की इस तरह, पहले geeky मजाक साल। CS50 हैक एक thon में छात्रों की जांच में जब, कुछ टीएफ या सीए हर साल सोचता है कि इसे डाल अजीब बात है इस तरह से एक संकेत है, जहां यह सिर्फ आपके नाम एक एक के साथ शुरू होता है, तो इसका मतलब है, इस तरफ से जाएं। आपके नाम शुरू होता है एक बी के साथ है- ठीक है जाओ, यह हो सकता है बाद में सेमेस्टर में हास्यास्पद है। लेकिन वहाँ एक और है भी, ऐसा करने का तरीका है। वापस करने के लिए आते हैं। 

तो इस संरचना नहीं है। और यह हमारे पिछले है आज के लिए संरचना, जो एक Trie कहा जाता है। किसी कारण के लिए कम है जो टी आर-मैं-ई, पुनः प्राप्ति के लिए, लेकिन यह Trie कहा जाता है। तो एक Trie एक और दिलचस्प है इन विचारों का एक बहुत का मिश्रण। यह हम पहले देखा है जो एक पेड़ है। यह एक द्विआधारी खोज वृक्ष नहीं है। यह बच्चों के किसी भी संख्या के साथ एक पेड़ है लेकिन एक Trie में बच्चों में से प्रत्येक एक सरणी है। आकार की एक सरणी, 26 या शायद 27 का कहना है आप बंटे नामों का समर्थन करना चाहते हैं या लोगों के नाम में apostrophes। 

और इसलिए यह एक आंकड़ा संरचना है। और अगर आप ऊपर से देखें तो नीचे करने के लिए, पसंद है तो है, वहाँ शीर्ष नोड, एम को देखो वहाँ सबसे बाएँ बात की ओर इशारा करते, जो फिर एक, एक्स, डब्ल्यू, ई, एल, एल यह है सिर्फ एक आंकड़ा संरचना है कि मनमाने ढंग से लोगों के नाम भंडारण है। और मैक्सवेल सिर्फ निम्न द्वारा संग्रहित है सरणी के लिए सरणी के लिए सरणी के एक पथ। एक Trie है के बारे में लेकिन आश्चर्यजनक क्या है , कि एक लिंक सूची जबकि और भी एक सरणी, हम कभी भी मिल गया है सबसे अच्छा है रैखिक समय या लघुगणक समय देख किसी के ऊपर। एक Trie के इस डेटा संरचना, यदि में मेरे डेटा संरचना उस में एक नाम है और मैं मैक्सवेल के लिए देख रहा हूँ, मैं हूँ बहुत जल्दी उसे खोजने के लिए जा रहा है। मैं सिर्फ एम-ए-एक्स डब्ल्यू ई एल-एल के लिए देखो। यदि इस डेटा संरचना, इसके विपरीत, एक है कि अगर वहाँ एन, एक लाख है, तो इस डेटा संरचना में दस लाख के नाम, मैक्सवेल अभी भी होने जा रहा है खोज योग्य सिर्फ एम-ए-एक्स डब्ल्यू ई एल-एल के बाद कदम। और David-- डी-ए-वी-मैं-डी कदम। दूसरे शब्दों में, निर्माण से है कि एक डेटा संरचना मिला इन सरणियों के सभी, जो सभी के लिए खुद को, रैंडम एक्सेस का समर्थन मैं लोगों के ऊपर की तलाश शुरू कर सकते हैं है कि समय की राशि का उपयोग कर नाम नहीं संख्या के अनुपात डेटा संरचना में बातें की, जैसे एक लाख मौजूदा नाम। इसे खोजने के लिए मुझे लगता है समय की राशि एम-ए-एक्स डब्ल्यू ई एल एल इस डेटा संरचना में है आनुपातिक नहीं करने के लिए डेटा संरचना के आकार, लेकिन नाम की लंबाई के लिए। और वास्तविक नाम हम ऊपर देख रहे हैं कभी नहीं लंबे समय से पागल हो जा रहे हैं। शायद किसी को एक 10 चरित्र है 20 चरित्र का नाम नाम है। यह ठीक है, निश्चित रूप से परिमित है? पृथ्वी पर एक मानव से कौन है जो सबसे लंबे समय तक संभव नाम है, लेकिन लगता है कि नाम एक स्थिर है मूल्य लंबाई, है ना? यह किसी भी मायने में भिन्न नहीं है। तो इस तरह से, हम है एक आंकड़ा संरचना हासिल की कि लगातार समय लुक-अप है। यह कदम के एक नंबर ले करता है इनपुट की लंबाई पर निर्भर करता है, नाम की नहीं बल्कि नंबर डेटा संरचना में। हम नामों की संख्या दोगुनी तो अगर एक अरब दो अरब से अगले साल निष्कर्ष मैक्सवेल ले जा रहा है सात चरणों की सटीक एक ही नंबर उसे खोजने के लिए। और इसलिए हम हासिल करने के लिए लग रहे हो समय चल रहा है के बारे में हमारी होली ग्रेल। 

इतनी जल्दी घोषणाओं के एक जोड़े। प्रश्नोत्तरी शून्य आ रहा है। पाठ्यक्रम की वेबसाइट पर उस पर और अधिक अगले कुछ दिनों से अधिक। सोमवार को यह एक छुट्टी है lecture-- यहां हार्वर्ड में सोमवार को। यह न्यू हेवन में नहीं है तो हम क्लास ले जा रहे हैं सोमवार को व्याख्यान के लिए न्यू हेवन के लिए। सब कुछ फिल्माया जाएगा और, हमेशा की तरह जीना प्रदर्शित लेकिन आज खत्म हो जाने एक 30 सेकंड क्लिप के साथ कहा जाता है "गहरे विचार" Daven Farnham, द्वारा जो शनिवार को पिछले वर्ष प्रेरित था नाइट लाइव की 'गहरे विचार " जैक काम, द्वारा जो अब समझ में बनाना चाहिए। 

फिल्म: और अब, "दीप Daven Farnham द्वारा विचार "। हैश तालिका। 

स्पीकर 1: ठीक है, कि अभी के लिए है। हम अगले सप्ताह आप देखेंगे। 

डौग: यह कार्रवाई में देखने के लिए। तो चलो ठीक है अब उस पर एक नजर डालते हैं। यहाँ तो, हम एक अवर्गीकृत सरणी है। 

इयान: डौग, आप आगे और पुनः आरंभ जा सकते हैं बस एक पल के लिए यह, कृपया। ठीक है, कैमरों तो, चल रहे हैं कार्रवाई आप डौग, तैयार कर रहे हैं, जब भी ठीक है? डौग: ठीक है, तो क्या हम यहाँ है एक अवर्गीकृत सरणी है। और मैं तत्वों के सभी रंग है यह वास्तव में है कि इंगित करने के लिए लाल, अवर्गीकृत। तो पहली बात है कि हम क्या याद हम सरणी के बाईं आधा तरह है। तो फिर हम सही तरह सरणी का आधा। और फिर डा, फिर-दा, हां-दा, हम उन्हें एक साथ विलय। और हम एक पूरी तरह से सॉर्ट सरणी है। तो यह है कि काम करता है प्रकार विलय कैसे करना है। 

इयान: वाह, वाह, वाह, कटौती, कटौती, कटौती, कटौती। डौग, आप बस फिर दा नहीं कर सकते, हां-दा, हां- दा, मर्ज प्रकार के माध्यम से अपना रास्ता। 

डौग: मैं बस किया। यह ठीक है। हम जाने के लिए अच्छे हैं। चलो बस रोलिंग रख दें। तो खैर, 

इयान: आप को समझाने की है यह पूरी तरह से अधिक से अधिक है कि। यही कारण है कि अभी पर्याप्त नहीं है। डौग: इयान, हम नहीं करते एक के लिए वापस जाने की जरूरत है। यह ठीक है। तो वैसे भी, हम merge-- के साथ जारी है, तो इयान, हम फिल्म के बीच में हैं। 

इयान: मुझे पता है। और हम बस फिर-दा नहीं कर सकते, हां-दा, पूरी प्रक्रिया के माध्यम से फिर-दा,। आप कैसे समझाने के लिए है दोनों पक्षों ने एक साथ विलय हो। 

डौग: लेकिन हम पहले से ही है विस्तार से बताया कि कैसे दो sides-- 

इयान: तुम सिर्फ दिखाया है उन्हें एक मर्ज सरणी। डौग: वे इस प्रक्रिया को पता है। वे ठीक हैं। हम इसे दस बार से अधिक चले गए हैं। 

इयान: आप बस इसे सही पर छोड़ दिया। हम एक के लिए वापस जा रहे हैं, तो आप इस पर आप हां- दा, हां-दा नहीं कर सकते। वापस करने के लिए सभी अधिकार,। 

डौग: मैं वापस जाने के लिए स्लाइड्स के माध्यम से सभी? हे भगवान। यह छठी बार, इयान की तरह है। यह ठीक है। 

इयान: ठीक है। आप तैयार हैं? अच्छा है। कार्रवाई।