सरणियाँ, स्टैक, कतारें व संबद्ध सूचियाँ
सरणी संबोधन, दोनों प्रकार से
int A[10][20] लें, पता 1000 पर आधारित, 4-बाइट अवयवों सहित, और 0-आधारित अनुक्रमण में A[5][7] का पता पूछें। पंक्ति-प्रधान प्रत्येक पंक्ति संलग्न रखता है, अतः 20 अवयवों की 5 पूरी पंक्तियाँ लक्ष्य से पहले आती हैं: 1000 + 4 × (5 × 20 + 7) = 1000 + 428 = 1428। स्तंभ-प्रधान प्रत्येक स्तंभ संलग्न रखता है, अतः 10 अवयवों के 7 पूरे स्तंभ उससे पहले: 1000 + 4 × (7 × 10 + 5) = 1000 + 300 = 1300। वही सरणी, वही अवयव, 128 बाइट दूर पते।
A[1..10][1..20] — और तब गुणा करने से पूर्व अनुक्रमणिका से निम्न सीमा घटानी पड़ती है। उसी 1000-आधारित सरणी में वही A[5][7] बनता है 1000 + 4 × ((5 − 1) × 20 + (7 − 1)) = 1344, 1428 नहीं। सामान्य पंक्ति-प्रधान सूत्र है आधार + w × ((i − lo₁) × (hi₂ − lo₂ + 1) + (j − lo₂)), और सर्वाधिक बार छूटता अंश यह है कि पंक्ति की लंबाई भी सीमाओं से निकाली जाती है, मानी नहीं जाती। अंकगणित छूने से पूर्व घोषणा को उसकी सीमाओं हेतु पढ़ना ही यहाँ सम्पूर्ण अनुशासन है।स्टैक: मूल्यांकन, रूपांतरण, तथा गहराई मापन
| टोकन | क्रिया | पश्चात् स्टैक |
|---|---|---|
| 5, 3, 2 | प्रत्येक पुश | 5, 3, 2 |
| * | 2 व 3 पॉप, 3 × 2 पुश | 5, 6 |
| + | 6 व 5 पॉप, 11 पुश | 11 |
| 8, 4 | प्रत्येक पुश | 11, 8, 4 |
| / | 4 व 8 पॉप, 8 / 4 पुश | 11, 2 |
| − | 2 व 11 पॉप, 11 − 2 पुश | 9 |
8 4 / देखकर 8 / 4 के बजाय 4 / 8 निकालना पश्च-संकेतन मूल्यांकन की एकमात्र सर्वाधिक सामान्य त्रुटि है, और वह उत्तर में अदृश्य है क्योंकि दोनों संख्या ही देते हैं। योग व गुणन त्रुटि को पूर्णतः छिपा देते हैं, इसीलिए प्रश्न सदा घटाव या भाग सम्मिलित करते हैं। वही उलटाव पूर्व-संकेतन मूल्यांकन को शासित करता है, जो दाएँ से बाएँ पढ़ा जाता है, जहाँ पहला पॉप किया मान बायाँ प्रचालक है — अतः दोनों संकेतनों को विपरीत आदतें चाहिए और उन्हें एक विषय के बजाय पृथक् अभ्यास करना उपयोगी है।वर्तुल कतारें, तथा संबद्ध सूची किस तक नहीं पहुँच सकती
| संक्रिया | एक-पार्श्वी, head + tail संकेतक | द्वि-पार्श्वी, head + tail |
|---|---|---|
| आगे सम्मिलित | O(1) | O(1) |
| अंत में सम्मिलित | O(1) — tail संकेतक पर्याप्त | O(1) |
| आगे से हटाना | O(1) | O(1) |
| अंत से हटाना | O(n) — पूर्ववर्ती शीर्ष अगम्य | O(1) |
| दिए संकेतक से शीर्ष हटाना | सामान्यतः O(n) | O(1) |
उस तालिका का प्रतिरूप पंक्ति-दर-पंक्ति कंठस्थ करने के बजाय नियम के रूप में कहने योग्य है: कोई संक्रिया ठीक तब O(1) है जब उसे बदलने योग्य प्रत्येक संकेतक अचर समय में गम्य हो। अंत से हटाने हेतु अंतिम से पूर्व वाले शीर्ष का next क्षेत्र लिखना पड़ता है, और एक-पार्श्वी सूची tail से उस शीर्ष तक कोई मार्ग नहीं देती — इसीलिए tail संकेतक सहायता नहीं करता, और यह तथ्य निश्चित रखने योग्य है क्योंकि लगता है कि उसे करनी चाहिए।
मुख्य बिंदु
- पंक्ति-प्रधान: आधार + w × (i × स्तंभ + j)। स्तंभ-प्रधान: आधार + w × (j × पंक्ति + i)। वही अवयव, भिन्न पते।
- स्पष्ट निम्न सीमाओं सहित उन्हें दोनों अनुक्रमणिकाओं से घटाएँ — और पंक्ति-लंबाई भी सीमाओं से निकालें।
- पश्च-संकेतन मूल्यांकन में दूसरा पॉप किया मान बायाँ प्रचालक है — + व × हेतु त्रुटि अदृश्य है।
- आकार n की सरणी में वर्तुल कतार n − 1 अवयव रखती है; पूर्ण है (rear + 1) mod n == front।
- कोई संक्रिया ठीक तब O(1) है जब उसे बदलने योग्य प्रत्येक संकेतक अचर समय में गम्य हो।
- एक-पार्श्वी सूची का अंतिम शीर्ष हटाना tail संकेतक सहित भी O(n) है — उससे पूर्व वाला शीर्ष चाहिए।
- एक-पार्श्वी सूची के किसी भी सिरे पर सम्मिलन O(1) है यदि head व tail दोनों संकेतक रखे जाएँ।
अभ्यास प्रश्न (8)
उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।
सरणी int A[10][20] पंक्ति-प्रधान क्रम में पता 1000 से संचित है, प्रति अवयव 4 बाइट व 0-आधारित अनुक्रमणिकाओं सहित। A[5][7] का पता क्या है?
संख्यात्मक उत्तर — मान टाइप करें।
उत्तर देखें
उत्तर: 1428
पंक्ति-प्रधान का अर्थ है कि पूरी पंक्तियाँ अवयव से पहले आती हैं: 20 की पाँच पूरी पंक्तियाँ, फिर सात अवयव। 1000 + 4 × (5 × 20 + 7) = 1000 + 4 × 107 = 1428। दो जाँचें। उसी सरणी पर स्तंभ-प्रधान 1000 + 4 × (7 × 10 + 5) = 1300 देता है, अतः यदि आपका उत्तर उससे मिला तो आपने गलत परिपाटी प्रयोग की। और यदि घोषणा A[1..10][1..20] होती, तो दोनों अनुक्रमणिकाएँ एक-एक घटतीं और उत्तर 1344 होता — इसीलिए सीमाएँ सर्वप्रथम पढ़ने योग्य हैं।पूर्णांक अंकगणित से पश्च-संकेतन व्यंजक 5 3 2 * + 8 4 / − का मूल्यांकन करें।
संख्यात्मक उत्तर — मान टाइप करें।
उत्तर देखें
उत्तर: 9
5, 3, 2 पुश करें।*पर 2 फिर 3 पॉप कर 6 पुश करें, शेष 5, 6।+पर 11 पुश। 8, 4 पुश।/पर 4 फिर 8 पॉप कर 8/4 = 2 पुश।−पर 2 फिर 11 पॉप कर 11 − 2 = 9 पुश। जो दो संकारक गलत हो सकते हैं वे/व−हैं, क्योंकि दूसरा पॉप किया मान बायाँ प्रचालक है: 4/8 = 0 और फिर 2 − 11 = −9 निकालना मानक विफलता है, और वह विश्वसनीय दिखती संख्या देती है। मध्य-संकेतन में व्यंजक 5 + 3 × 2 − 8 / 4 है, जो 5 + 6 − 2 = 9 है — जाँच के रूप में करने योग्य, क्योंकि वापस रूपांतरण शीघ्र है और प्रचालक-क्रम की चूक तुरंत पकड़ता है।वर्तुल कतार आकार 10 की सरणी में केवल front व rear अनुक्रमणिकाओं से, बिना पृथक् गणक, कार्यान्वित है। उसकी अधिकतम क्षमता है:
उत्तर देखें
उत्तर: B — 9
केवल दो अनुक्रमणिकाओं के साथ "रिक्त" व "पूर्णतः भरा" दोनों front == rear देते हैं, अतः दोनों अवस्थाएँ अपृथक्करणीय हैं। एक स्थान बलिदान करना उन्हें पृथक् करता है: पूर्ण बनता है (rear + 1) mod 10 == front, रिक्त रहता है rear == front, और क्षमता 9 है। प्रश्न में "बिना पृथक् गणक" वाक्यांश इसी परिपाटी के प्रयोग का निर्देश है — गणक या पूर्ण-ध्वजा के साथ दसवाँ स्थान प्रयोज्य है और उत्तर 10 होता। कौन-सी परिपाटी पूछी जा रही है यह पढ़ना यहाँ अंकगणित से अधिक महत्व रखता है।ऐसी एक-पार्श्वी संबद्ध सूची में जिसमें head व tail दोनों के संकेतक रखे हों, कौन-सी संक्रिया फिर भी O(n) समय लेती है?
उत्तर देखें
उत्तर: C — अंतिम शीर्ष हटाना
अंतिम शीर्ष हटाने का अर्थ है अंतिम से पूर्व वाले शीर्ष काnext, NULL करना, और एक-पार्श्वी सूची में tail से उस शीर्ष तक कोई मार्ग नहीं — अतः उसे head से चलकर ढूँढ़ना पड़ता है, जो O(n) है। tail संकेतक आपको अंतिम शीर्ष तक O(1) में पहुँचाता है, उससे पूर्व वाले तक नहीं, और वही अंतर सम्पूर्ण उत्तर है; यह निश्चित रखने योग्य है, क्योंकि अंतर्ज्ञान कहता है कि tail संकेतक को सूची-अंत की प्रत्येक समस्या हल करनी चाहिए। अंत में सम्मिलन ठीक है (B) क्योंकि वह केवल वर्तमान tail काnextलिखता है, जिस तक tail संकेतक सीधे पहुँचता है। सूची को द्वि-पार्श्वी बनाना उस विलोपन को O(1) कर देता है।4-बाइट अवयवों की सरणी A[1..10][1..20] पंक्ति-प्रधान क्रम में आधार पता 1000 सहित संचित है। A[5][7] का पता क्या है?
संख्यात्मक उत्तर — मान टाइप करें।
उत्तर देखें
उत्तर: 1344
निम्न सीमा 1 है, अतः प्रयोग से पूर्व दोनों अनुक्रमणिकाएँ एक-एक घटती हैं: 1000 + 4 × ((5 − 1) × 20 + (7 − 1)) = 1000 + 4 × 86 = 1344। उसी सरणी के 0-आधारित संस्करण से तुलना करें, जो 1428 देता है — 84 बाइट का अंतर पूर्णतः घोषणा से उत्पन्न, और इसीलिए अंकगणित आरंभ होने से पूर्व सीमाएँ पढ़नी चाहिए। यहाँ दोनों स्थितियों में पंक्ति-लंबाई 20 है, परंतु सामान्यतः वह भी सीमाओं से hi₂ − lo₂ + 1 के रूप में आती है, और उसे निकालने के बजाय मान लेना इस प्रश्न को खोने का दूसरा तरीका है।दोनों सिरों के संकेतक रखती द्वि-पार्श्वी संबद्ध सूची में निम्नलिखित में कौन O(1) हैं? (एक से अधिक सही हो सकते हैं।)
उत्तर देखें
उत्तर: A — अंतिम शीर्ष हटाना; B — केवल उस शीर्ष का संकेतक दिए जाने पर उसे हटाना; D — दिए संकेतक वाले शीर्ष से पूर्व सम्मिलित करना
A, B व D, और वे एक ही गुण तीन बार हैं: द्वि-पार्श्वी शीर्ष अपने दोनों पड़ोसियों तक पहुँचता है, अतः इनमें से किसी भी संक्रिया को पुनर्लिखित करने योग्य प्रत्येक संकेतक तुरंत उपलब्ध है। ठीक वही एक-पार्श्वी सूची नहीं कर सकती — वहाँ B व D, O(n) हैं, क्योंकि पूर्ववर्ती शीर्ष तक पहुँचने हेतु चलना पड़ता है। C दोनों में O(n) है, और वही संबद्ध सूचियों की ईमानदार सीमा है: वे अनुक्रमित पहुँच छोड़ देती हैं, और सरणी उसी हेतु है। संबद्ध-सूची संक्रियाओं में "k-वाँ अवयव ढूँढ़ें" देता प्रश्न यंत्र-विधि के बजाय यह जाँच रहा है कि सौदा समझा गया है या नहीं।कोष्ठकों की माला संतुलित है या नहीं यह जाँचने हेतु स्टैक प्रयुक्त है। स्टैक अपनी अधिकतम गहराई तब पहुँचता है जब:
उत्तर देखें
उत्तर: B — अंतःस्थापन सबसे गहरा हो
प्रत्येक अ-मिलान खुला कोष्ठक अपने साथी के आने तक स्टैक पर रहता है, अतः किसी क्षण गहराई वर्तमान अंतःस्थापन स्तर है और अधिकतम सबसे गहरा अंतःस्थापन। लंबाई अप्रासंगिक है:()()()()()दस अक्षर हैं जिनकी अधिकतम गहराई एक है, जबकि((((()))))उतनी ही लंबाई है गहराई पाँच सहित। वही भेद प्रश्न का अभिप्राय है, और वही तर्क व्यंजक-मूल्यांकन का मानक परिणाम देता है — आवश्यक स्टैक गहराई व्यंजक-वृक्ष की गहराई है, टोकनों की संख्या नहीं।1000 पर आधारित int A[10][20] के उसी अवयव A[5][7] का पंक्ति-प्रधान पता 1428 है। उसका स्तंभ-प्रधान पता है:
उत्तर देखें
उत्तर: B — 1300
स्तंभ-प्रधान स्तंभों को संलग्न रखता है, अतः 10 अवयवों के सात पूरे स्तंभ लक्ष्य से पहले आते हैं, फिर पाँच और: 1000 + 4 × (7 × 10 + 5) = 1000 + 300 = 1300। ध्यान दें कि कौन-सा विमा गुणा होता है: पंक्ति-प्रधान पंक्ति-अनुक्रमणिका को स्तंभों की संख्या से गुणा करता है, स्तंभ-प्रधान स्तंभ-अनुक्रमणिका को पंक्तियों की संख्या से, और उन दोनों को बदल देना वही त्रुटि है जिसे पकड़ने हेतु प्रश्न बना है। विकल्प C, 1-आधारित पंक्ति-प्रधान उत्तर है, जो इसलिए सम्मिलित है कि ये तीन संख्याएँ — 1428, 1344, 1300 — परिपाटी व सीमाओं के अनुसार उसी अवयव को संबोधित करने के तीन तरीके हैं।