अमूर्त डेटा प्रकार: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(4 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{short description|Mathematical model for data types}}[[कंप्यूटर विज्ञान]] में '''अमूर्त डेटा प्रकार''' (एडीटी) डेटा प्रकारों के लिए एक गणितीय मॉडल है। '''अमूर्त डेटा प्रकार''' को उसके व्यवहार (सिमेंटिक्स (कंप्यूटर विज्ञान)) द्वारा परिभाषित किया जाता है। डेटा के'' [[उपयोगकर्ता (कंप्यूटिंग)]]'' के दृष्टिकोण से विशेष रूप से संभावित मूल्यों के संदर्भ में इस प्रकार के डेटा पर संभावित संचालन और इन परिचालनों का व्यवहार गणितीय मॉडल [[डेटा संरचना]]ओं के विपरीत है। जो डेटा के ठोस प्रतिनिधित्व हैं और एक कार्यान्वयनकर्ता के दृष्टिकोण हैं, परन्तु उपयोगकर्ता नहीं है।
{{short description|Mathematical model for data types}}[[कंप्यूटर विज्ञान]] में '''अमूर्त डेटा प्रकार''' (एडीटी) डेटा प्रकारों के लिए एक गणितीय मॉडल है। '''अमूर्त डेटा प्रकार''' को उसके व्यवहार (सिमेंटिक्स (कंप्यूटर विज्ञान)) द्वारा परिभाषित किया जाता है। डेटा के'' [[उपयोगकर्ता (कंप्यूटिंग)]]'' के दृष्टिकोण से विशेष रूप से संभावित मूल्यों के संदर्भ में इस प्रकार के डेटा पर संभावित संचालन और इन परिचालनों का व्यवहार गणितीय मॉडल [[डेटा संरचना]]ओं के विपरीत है। जो डेटा के ठोस प्रतिनिधित्व हैं और एक कार्यान्वयनकर्ता के दृष्टिकोण हैं, परन्तु उपयोगकर्ता नहीं है।


औपचारिक रूप से एडीटी को वस्तुओं के एक वर्ग के रूप में परिभाषित किया जा सकता है। जिसका तार्कपूर्ण व्यवहार मूल्यों के एक समुच्चय और संचालन के समुच्चय द्वारा परिभाषित किया गया है।{{sfn|Dale|Walker|1996|p=3}} यह गणित में [[बीजगणितीय संरचना]] के अनुरूप है। व्यवहार से क्या अभिप्राय लेखक द्वारा भिन्न होता है। व्यवहार दो मुख्य प्रकार के औपचारिक विनिर्देशों के साथ स्वयंसिद्ध (बीजगणितीय) विनिर्देश और अमूर्त मॉडल होता है।{{sfn|Dale|Walker|1996|p=4}} ये क्रमशः [[अमूर्त मशीन]] के [[स्वयंसिद्ध शब्दार्थ]] और [[परिचालन शब्दार्थ]] के अनुरूप हैं। कुछ लेखकों में समय (कंप्यूटिंग संचालन के लिए) और स्थान (मूल्यों का प्रतिनिधित्व करने के लिए) दोनों के संदर्भ में [[कम्प्यूटेशनल जटिलता सिद्धांत]] (क्रय मूल्य) भी सम्मिलित है। व्यवहार में कई सामान्य डेटा प्रकार एडीटीएस नहीं हैं क्योंकि अमूर्तता सही नहीं है और उपयोगकर्ताओं को [[अंकगणितीय अतिप्रवाह]] जैसे विषयों के बारे में पता होना चाहिए। जो प्रतिनिधित्व के कारण होते हैं। उदाप्रत्येकण के लिए पूर्णांकों को प्रायः निश्चित-चौड़ाई मान (32-बिट या 64-बिट बाइनरी संख्या) के रूप में संग्रहीत किया जाता है और इस प्रकार अधिकतम मान पार होने पर पूर्णांक अतिप्रवाह का अनुभव होता है।
औपचारिक रूप से एडीटी को वस्तुओं के एक वर्ग के रूप में परिभाषित किया जा सकता है। जिसका तार्कपूर्ण व्यवहार मूल्यों के एक समुच्चय और संचालन के समुच्चय द्वारा परिभाषित किया गया है।{{sfn|Dale|Walker|1996|p=3}} यह गणित में [[बीजगणितीय संरचना]] के अनुरूप है। व्यवहार से क्या अभिप्राय लेखक द्वारा भिन्न होता है। व्यवहार दो मुख्य प्रकार के औपचारिक विनिर्देशों के साथ स्वयंसिद्ध (बीजगणितीय) विनिर्देश और अमूर्त मॉडल होता है।{{sfn|Dale|Walker|1996|p=4}} ये क्रमशः [[अमूर्त मशीन]] के [[स्वयंसिद्ध शब्दार्थ]] और [[परिचालन शब्दार्थ]] के अनुरूप हैं। कुछ लेखकों में समय (कंप्यूटिंग संचालन के लिए) और स्थान (मूल्यों का प्रतिनिधित्व करने के लिए) दोनों के संदर्भ में [[कम्प्यूटेशनल जटिलता सिद्धांत]] (क्रय मूल्य) भी सम्मिलित है। व्यवहार में कई सामान्य डेटा प्रकार एडीटीएस नहीं हैं क्योंकि अमूर्तता सही नहीं है और उपयोगकर्ताओं को [[अंकगणितीय अतिप्रवाह]] जैसे विषयों के बारे में पता होना चाहिए। जो प्रतिनिधित्व के कारण होते हैं। उदाहरण के लिए पूर्णांकों को प्रायः निश्चित-चौड़ाई मान (32-बिट या 64-बिट बाइनरी संख्या) के रूप में संग्रहीत किया जाता है और इस प्रकार अधिकतम मान पार होने पर पूर्णांक अतिप्रवाह का अनुभव होता है।


एडीटी एक सैद्धांतिक अवधारणा है। कंप्यूटर विज्ञान में [[कलन विधि]], डेटा संरचना और [[सॉफ्टवेयर सिस्टम|सॉफ्टवेयर तन्त्र]] के प्रारूप और विश्लेषण में उपयोग किया जाता है और [[कंप्यूटर भाषा]]ओं की विशिष्ट विशेषताओं के अनुरूप नहीं है। कंप्यूटर की मुख्य भाषाएँ सीधे औपचारिक रूप से निर्दिष्ट एडीटी का समर्थन नहीं करती हैं। चूंकि विभिन्न भाषा सुविधाएँ एडीटी के कुछ नियमों के अनुरूप हैं और एडीटी के साथ सरलता से भ्रमित हो जाती हैं। इनमें अमूर्त प्रकार, [[अपारदर्शी डेटा प्रकार]], [[प्रोटोकॉल (ऑब्जेक्ट-ओरिएंटेड प्रोग्रामिंग)]] और अनुबंध द्वारा प्रारूप सम्मिलित हैं। सीएलयू (प्रोग्रामिंग लैंग्वेज) भाषा के विकास के भाग के रूप में एडीटी को पहली बार 1974 में [[बारबरा लिस्कोव]] और स्टीफन एन ज़िल्स द्वारा प्रस्तावित किया गया था।{{sfn|Liskov|Zilles|1974}}
एडीटी एक सैद्धांतिक अवधारणा है। कंप्यूटर विज्ञान में [[कलन विधि]], डेटा संरचना और [[सॉफ्टवेयर सिस्टम|सॉफ्टवेयर तन्त्र]] के प्रारूप और विश्लेषण में उपयोग किया जाता है और [[कंप्यूटर भाषा]]ओं की विशिष्ट विशेषताओं के अनुरूप नहीं है। कंप्यूटर की मुख्य भाषाएँ सीधे औपचारिक रूप से निर्दिष्ट एडीटी का समर्थन नहीं करती हैं। चूंकि विभिन्न भाषा सुविधाएँ एडीटी के कुछ नियमों के अनुरूप हैं और एडीटी के साथ सरलता से भ्रमित हो जाती हैं। इनमें अमूर्त प्रकार, [[अपारदर्शी डेटा प्रकार]], [[प्रोटोकॉल (ऑब्जेक्ट-ओरिएंटेड प्रोग्रामिंग)]] और अनुबंध द्वारा प्रारूप सम्मिलित हैं। सीएलयू (प्रोग्रामिंग लैंग्वेज) भाषा के विकास के भाग के रूप में एडीटी को पहली बार 1974 में [[बारबरा लिस्कोव]] और स्टीफन एन ज़िल्स द्वारा प्रस्तावित किया गया था।{{sfn|Liskov|Zilles|1974}}
Line 7: Line 7:


== अमूर्त डेटा प्रकार ==
== अमूर्त डेटा प्रकार ==
उदाप्रत्येकण के लिए [[पूर्णांक]] एक एडीटी होते हैं। जिन्हें मान ..., -2, -1, 0, 1, 2, ... के रूप में परिभाषित किया जाता है और जोड़, घटाव, गुणा और भाग की संक्रियाओं के साथ-साथ से अधिक के रूप में परिभाषित किया जाता है। जो परिचित गणित के अनुअमूर्त व्यवहार करते हैं। [[पूर्णांक विभाजन]] की देखभाल के साथ, कम, आदि स्वतंत्र रूप से कंप्यूटर द्वारा पूर्णांकों का प्रतिनिधित्व कैसे किया जाता है। {{efn|Compare to the characterization of integers in abstract algebra.}} स्पष्ट रूप से व्यवहार में विभिन्न स्वयंसिद्धों (संबद्धता और जोड़ की क्रमविनिमेयता आदि) का पालन करना और संचालन पर पूर्व नियम (शून्य से विभाजित नहीं किया जा सकता) सम्मिलित है। सामान्यतः पूर्णांकों को डेटा संरचना में [[बाइनरी संख्या]] के रूप प्रायः दो के पूरक के रूप में दर्शाया जाता है। किन्तु [[बाइनरी-कोडित दशमलव]] या एक के पूरक में हो सकता है। किन्तु अधिकांश उद्देश्यों के लिए उपयोगकर्ता प्रतिनिधित्व के ठोस विकल्प के अतिरिक्त अमूर्तता के साथ काम कर सकता है और केवल डेटा का उपयोग कर सकते हैं। जैसे कि प्रकार वास्तव में अमूर्त थे।
उदाहरण के लिए [[पूर्णांक]] एक एडीटी होते हैं। जिन्हें मान ..., -2, -1, 0, 1, 2, ... के रूप में परिभाषित किया जाता है और जोड़, घटाव, गुणा और भाग की संक्रियाओं के साथ-साथ से अधिक के रूप में परिभाषित किया जाता है। जो परिचित गणित के अनुअमूर्त व्यवहार करते हैं। [[पूर्णांक विभाजन]] की देखभाल के साथ, कम, आदि स्वतंत्र रूप से कंप्यूटर द्वारा पूर्णांकों का प्रतिनिधित्व कैसे किया जाता है। {{efn|Compare to the characterization of integers in abstract algebra.}} स्पष्ट रूप से व्यवहार में विभिन्न स्वयंसिद्धों (संबद्धता और जोड़ की क्रमविनिमेयता आदि) का पालन करना और संचालन पर पूर्व नियम (शून्य से विभाजित नहीं किया जा सकता) सम्मिलित है। सामान्यतः पूर्णांकों को डेटा संरचना में [[बाइनरी संख्या]] के रूप प्रायः दो के पूरक के रूप में दर्शाया जाता है। किन्तु [[बाइनरी-कोडित दशमलव]] या एक के पूरक में हो सकता है। किन्तु अधिकांश उद्देश्यों के लिए उपयोगकर्ता प्रतिनिधित्व के ठोस विकल्प के अतिरिक्त अमूर्तता के साथ काम कर सकता है और केवल डेटा का उपयोग कर सकते हैं। जैसे कि प्रकार वास्तव में अमूर्त थे।


एडीटी में न केवल संचालन होते हैं। बल्कि मूल्यों का डोमेन भी होता है और परिभाषित संचालन पर बाधाएं होती हैं। इंटरफ़ेस सामान्यतः केवल संचालन को संदर्भित करता है और संचालन पर कुछ बाधाएं जैसे कि पूर्व-नियम और पश्च-नियम। किन्तु संचालन के बीच संबंध जैसी अन्य बाधाओं के लिए नहीं हैं।
एडीटी में न केवल संचालन होते हैं। बल्कि मूल्यों का डोमेन भी होता है और परिभाषित संचालन पर बाधाएं होती हैं। इंटरफ़ेस सामान्यतः केवल संचालन को संदर्भित करता है और संचालन पर कुछ बाधाएं जैसे कि पूर्व-नियम और पश्च-नियम। किन्तु संचालन के बीच संबंध जैसी अन्य बाधाओं के लिए नहीं हैं।


उदाप्रत्येकण के लिए अमूर्त स्टैक (अमूर्त डेटा प्रकार), जो एक लास्ट-इन-फर्स्ट-आउट संरचना है, को तीन ऑपरेशनों द्वारा परिभाषित किया जा सकता है: पुस, जो स्टैक पर डेटा आइटम सम्मिलित करता है और <kbd>पॉप</kbd>, जो डेटा आइटम को इससे हटा देता है और पीक या टॉप, जो स्टैक के शीर्ष पर डेटा आइटम को बिना हटाए एक्सेस करता है। एक अमूर्त पंक्ति (अमूर्त डेटा प्रकार), जो पहले-में-पहले-आउट संरचना है, में भी तीन ऑपरेशन होंगे: <kbd>पंक्तिबद्ध करें</kbd>, जो पंक्ति में डेटा आइटम सम्मिलित करता है; <kbd>विपंक्ति</kbd>, जो इसमें से पहला डेटा आइटम हटा देता है और <kbd>सामने</kbd>, जो क्यू में पहले डेटा आइटम को एक्सेस और सर्व करता है। यदि ये संपूर्ण परिभाषाएँ होतीं। तो इन दो डेटा प्रकारों और उनके बहुत भिन्न अपेक्षित क्रम व्यवहार में अंतर करने का कोई उपाय नहीं होता। इस प्रकार एक बाधा प्रस्तुत की जाती है कि स्टैक के लिए यह निर्दिष्ट करता है कि प्रत्येक पॉप सदैव सबसे वर्तमान में धकेले गए आइटम को लौटाता है (और हटाता है)। जो अभी तक पॉप नहीं किया गया है और पंक्ति के लिए (इसके विपरीत) निर्दिष्ट करता है कि पॉप कम से कम वर्तमान में धकेले गए आइटम पर काम करता है।
उदाहरण के लिए अमूर्त स्टैक (अमूर्त डेटा प्रकार), जो एक लास्ट-इन-फर्स्ट-आउट संरचना है, को तीन ऑपरेशनों द्वारा परिभाषित किया जा सकता है: पुस, जो स्टैक पर डेटा आइटम सम्मिलित करता है और <kbd>पॉप</kbd>, जो डेटा आइटम को इससे हटा देता है और पीक या टॉप, जो स्टैक के शीर्ष पर डेटा आइटम को बिना हटाए एक्सेस करता है। एक अमूर्त पंक्ति (अमूर्त डेटा प्रकार), जो पहले-में-पहले-आउट संरचना है, में भी तीन ऑपरेशन होंगे: <kbd>पंक्तिबद्ध करें</kbd>, जो पंक्ति में डेटा आइटम सम्मिलित करता है; <kbd>विपंक्ति</kbd>, जो इसमें से पहला डेटा आइटम हटा देता है और <kbd>सामने</kbd>, जो क्यू में पहले डेटा आइटम को एक्सेस और सर्व करता है। यदि ये संपूर्ण परिभाषाएँ होतीं। तो इन दो डेटा प्रकारों और उनके बहुत भिन्न अपेक्षित क्रम व्यवहार में अंतर करने का कोई उपाय नहीं होता। इस प्रकार एक बाधा प्रस्तुत की जाती है कि स्टैक के लिए यह निर्दिष्ट करता है कि प्रत्येक पॉप सदैव सबसे वर्तमान में धकेले गए आइटम को लौटाता है (और हटाता है)। जो अभी तक पॉप नहीं किया गया है और पंक्ति के लिए (इसके विपरीत) निर्दिष्ट करता है कि पॉप कम से कम वर्तमान में धकेले गए आइटम पर काम करता है।


एल्गोरिदम के [[एल्गोरिदम का विश्लेषण]] करते समय यह भी निर्दिष्ट किया जा सकता है कि सभी ऑपरेशन एक ही समय लेते हैं। तथापि कितने डेटा आइटम समूह में धकेल दिए गए हों और यह कि स्टैक प्रत्येक तत्व के लिए भंडारण की निरंतर मात्रा का उपयोग करता है। चूंकि समय सीमा को सदैव एडीटी की परिभाषा का भाग नहीं माना जाता है।
एल्गोरिदम के [[एल्गोरिदम का विश्लेषण]] करते समय यह भी निर्दिष्ट किया जा सकता है कि सभी ऑपरेशन एक ही समय लेते हैं। तथापि कितने डेटा आइटम समूह में धकेल दिए गए हों और यह कि स्टैक प्रत्येक तत्व के लिए भंडारण की निरंतर मात्रा का उपयोग करता है। चूंकि समय सीमा को सदैव एडीटी की परिभाषा का भाग नहीं माना जाता है।
Line 37: Line 37:
भंडारण से पहले लाने की अनुमति नहीं दी जा सकती है। एक निश्चित परिणाम के लिए परिभाषित किया गया है या (कम वांछनीय रूप से) व्यवहार को अनिर्दिष्ट छोड़ दें।
भंडारण से पहले लाने की अनुमति नहीं दी जा सकती है। एक निश्चित परिणाम के लिए परिभाषित किया गया है या (कम वांछनीय रूप से) व्यवहार को अनिर्दिष्ट छोड़ दें।


कई प्रोग्रामिंग भाषाओं की प्रकार ऑपरेशन <kbd>store</kbd>(V, x) को प्रायः V ← x (या कुछ समान अंकन) लिखा जाता है और <kbd>fetch</kbd>(V) निहित होता है। जब कोई चर V का उपयोग उस संदर्भ में किया जाता है। जहाँ मान की आवश्यकता होती है। इस प्रकार उदाप्रत्येकण के लिए V ← V + 1 को सामान्यतः <kbd>store</kbd>(V,<kbd>fetch</kbd>(V) + 1) के लिए शॉर्टहैंड समझा जाता है।
कई प्रोग्रामिंग भाषाओं की प्रकार ऑपरेशन <kbd>store</kbd>(V, x) को प्रायः V ← x (या कुछ समान अंकन) लिखा जाता है और <kbd>fetch</kbd>(V) निहित होता है। जब कोई चर V का उपयोग उस संदर्भ में किया जाता है। जहाँ मान की आवश्यकता होती है। इस प्रकार उदाहरण के लिए V ← V + 1 को सामान्यतः <kbd>store</kbd>(V,<kbd>fetch</kbd>(V) + 1) के लिए शॉर्टहैंड समझा जाता है।


इस परिभाषा में यह स्पष्ट रूप से माना जाता है कि नाम सदैव अलग होते हैं: एक चर U में मान संग्रहीत करने से एक अलग चर V की स्थिति पर कोई प्रभाव नहीं पड़ता है। इस धारणा को स्पष्ट करने के लिए कोई बाधा जोड़ सकता है। जो
इस परिभाषा में यह स्पष्ट रूप से माना जाता है कि नाम सदैव अलग होते हैं: एक चर U में मान संग्रहीत करने से एक अलग चर V की स्थिति पर कोई प्रभाव नहीं पड़ता है। इस धारणा को स्पष्ट करने के लिए कोई बाधा जोड़ सकता है। जो
* यदि U और V भिन्न चर हैं। तो अनुक्रम {<kbd>store</kbd>(U, x); <kbd>store</kbd>(V, y) } { <kbd>store</kbd>(V, y) <kbd>स्टोर</kbd>(यू, एक्स)} के बराबर है।
* यदि U और V भिन्न चर हैं। तो अनुक्रम {<kbd>store</kbd>(U, x); <kbd>store</kbd>(V, y) } { <kbd>store</kbd>(V, y) <kbd>स्टोर</kbd>(यू, एक्स)} के बराबर है।


सामान्यतः एडीटी परिभाषाएँ प्रायः मानती हैं कि कोई भी ऑपरेशन, जो एक एडीटी उदाप्रत्येकण की स्थिति को बदलता है, उसी एडीटी के किसी अन्य उदाप्रत्येकण की स्थिति पर कोई प्रभाव नहीं पड़ता है। जब तक कि एडीटी स्वयंसिद्ध कुछ उदाप्रत्येकणों को कनेक्टेड के रूप में परिभाषित नहीं करता है ([[अलियासिंग (कंप्यूटिंग)]] देखें)। विशिष्ट उपाय सबसे सामान्य ऐसे कनेक्शनों में सम्मिलित हैं:
सामान्यतः एडीटी परिभाषाएँ प्रायः मानती हैं कि कोई भी ऑपरेशन, जो एक एडीटी उदाहरण की स्थिति को बदलता है, उसी एडीटी के किसी अन्य उदाहरण की स्थिति पर कोई प्रभाव नहीं पड़ता है। जब तक कि एडीटी स्वयंसिद्ध कुछ उदाहरणों को कनेक्टेड के रूप में परिभाषित नहीं करता है ([[अलियासिंग (कंप्यूटिंग)]] देखें)। विशिष्ट उपाय सबसे सामान्य ऐसे कनेक्शनों में सम्मिलित हैं:


* अलियासिंग, जिसमें दो या दो से अधिक नाम एक ही डेटा ऑब्जेक्ट को स्पष्ट रूप से संदर्भित करते हैं।
* अलियासिंग, जिसमें दो या दो से अधिक नाम एक ही डेटा ऑब्जेक्ट को स्पष्ट रूप से संदर्भित करते हैं।
* रचना, जिसमें एडीटी को (समान या अन्य) एडीटी के उदाप्रत्येकण सम्मिलित करने के लिए परिभाषित किया गया है।
* रचना, जिसमें एडीटी को (समान या अन्य) एडीटी के उदाहरण सम्मिलित करने के लिए परिभाषित किया गया है।
* संदर्भ, जिसमें एडीटी को (समान या अन्य) एडीटी के उदाप्रत्येकण के संदर्भ में परिभाषित किया गया है।
* संदर्भ, जिसमें एडीटी को (समान या अन्य) एडीटी के उदाहरण के संदर्भ में परिभाषित किया गया है।


उदाप्रत्येकण के लिए अमूर्त [[रिकॉर्ड (कंप्यूटर विज्ञान)]] को सम्मिलित करने के लिए अमूर्त चर की परिभाषा का विस्तार करते समय रिकॉर्ड चर आर के क्षेत्र एफ पर संचालन, स्पष्ट रूप से एफ को सम्मिलित करता है। जो आर से अलग है। किन्तु इसका एक भाग भी है।
उदाहरण के लिए अमूर्त [[रिकॉर्ड (कंप्यूटर विज्ञान)]] को सम्मिलित करने के लिए अमूर्त चर की परिभाषा का विस्तार करते समय रिकॉर्ड चर आर के क्षेत्र एफ पर संचालन, स्पष्ट रूप से एफ को सम्मिलित करता है। जो आर से अलग है। किन्तु इसका एक भाग भी है।


एडीटी की परिभाषा अपने उदाप्रत्येकणों के लिए संग्रहीत मूल्य (एस) को एक विशिष्ट समुच्चय एक्स के सदस्यों तक सीमित कर सकती है। जिसे उन चरों की श्रेणी कहा जाता है। उदाप्रत्येकण के लिए एक समूह या पंक्ति जैसे समुच्चय के लिए एडीटी पंक्ति में सभी वस्तुओं को पूर्णांक होने के लिए बाध्य कर सकता है या कम से कम सभी एक ही प्रकार के हो सकते हैं। (देखें एकरूपता_और_विषमता_(आँकड़े))। प्रोग्रामिंग भाषाओं की प्रकार ऐसे प्रतिबंध एल्गोरिदम के विवरण और विश्लेषण को सरल बना सकते हैं और इसकी पठनीयता में सुधार कर सकते हैं।
एडीटी की परिभाषा अपने उदाहरणों के लिए संग्रहीत मूल्य (एस) को एक विशिष्ट समुच्चय एक्स के सदस्यों तक सीमित कर सकती है। जिसे उन चरों की श्रेणी कहा जाता है। उदाहरण के लिए एक समूह या पंक्ति जैसे समुच्चय के लिए एडीटी पंक्ति में सभी वस्तुओं को पूर्णांक होने के लिए बाध्य कर सकता है या कम से कम सभी एक ही प्रकार के हो सकते हैं। (देखें एकरूपता_और_विषमता_(आँकड़े))। प्रोग्रामिंग भाषाओं की प्रकार ऐसे प्रतिबंध एल्गोरिदम के विवरण और विश्लेषण को सरल बना सकते हैं और इसकी पठनीयता में सुधार कर सकते हैं।


ध्यान दें कि यह परिभाषा <kbd>fetch</kbd>(V) के मूल्यांकन के परिणाम के बारे में कुछ भी नहीं बताती है। जब V प्रारंभिक नहीं है अर्थात V पर कोई <kbd>store</kbd> ऑपरेशन करने से पहले An एल्गोरिथम, जो ऐसा करता है, उसे अमान्य माना जा सकता है या तो (ए) क्योंकि एडीटी इस प्रकार के ऑपरेशन को प्रतिबंधित करता है या (बी) केवल इसलिए कि इसका प्रभाव एडीटी द्वारा परिभाषित नहीं किया गया है। चूंकि कुछ महत्वपूर्ण एल्गोरिदम हैं। जिनकी दक्षता दृढ़ता से इस धारणा पर निर्भर करती है कि ऐसा <kbd>fetch</kbd> नियमानुअमूर्त है और वेरिएबल की सीमा में कुछ अनावश्यक मान देता है।
ध्यान दें कि यह परिभाषा <kbd>fetch</kbd>(V) के मूल्यांकन के परिणाम के बारे में कुछ भी नहीं बताती है। जब V प्रारंभिक नहीं है अर्थात V पर कोई <kbd>store</kbd> ऑपरेशन करने से पहले An एल्गोरिथम, जो ऐसा करता है, उसे अमान्य माना जा सकता है या तो (ए) क्योंकि एडीटी इस प्रकार के ऑपरेशन को प्रतिबंधित करता है या (बी) केवल इसलिए कि इसका प्रभाव एडीटी द्वारा परिभाषित नहीं किया गया है। चूंकि कुछ महत्वपूर्ण एल्गोरिदम हैं। जिनकी दक्षता दृढ़ता से इस धारणा पर निर्भर करती है कि ऐसा <kbd>fetch</kbd> नियमानुअमूर्त है और वेरिएबल की सीमा में कुछ अनावश्यक मान देता है।


==== उदाप्रत्येकण निर्माण ====
==== उदाहरण निर्माण ====
कुछ एल्गोरिदम को कुछ एडीटी (जैसे नए चर, या नए समूह) के नए उदाप्रत्येकण बनाने की आवश्यकता होती है। इस प्रकार के एल्गोरिदम का वर्णन करने के लिए सामान्यतः एडीटी परिभाषा में <kbd>create</kbd>() ऑपरेशन सम्मिलित होता है। जो एडीटी का सामान्यतः स्वयंसिद्धों के बराबर उदाप्रत्येकण देता है।  
कुछ एल्गोरिदम को कुछ एडीटी (जैसे नए चर, या नए समूह) के नए उदाहरण बनाने की आवश्यकता होती है। इस प्रकार के एल्गोरिदम का वर्णन करने के लिए सामान्यतः एडीटी परिभाषा में <kbd>create</kbd>() ऑपरेशन सम्मिलित होता है। जो एडीटी का सामान्यतः स्वयंसिद्धों के बराबर उदाहरण देता है।  
* <kbd>create</kbd>() का परिणाम एल्गोरिथम द्वारा पहले से उपयोग किए जा रहे किसी भी उदाप्रत्येकण से अलग है।
* <kbd>create</kbd>() का परिणाम एल्गोरिथम द्वारा पहले से उपयोग किए जा रहे किसी भी उदाहरण से अलग है।
अन्य उदाप्रत्येकणों के साथ आंशिक अलियासिंग को भी बाप्रत्येक करने के लिए इस स्वयंसिद्ध को शक्तिशाली किया जा सकता है। व्यावहारिक उपयोग के लिए, जैसे स्वयंसिद्ध अभी भी <kbd>create</kbd>() के कार्यान्वयन की अनुमति दे सकता है, जो पहले से बनाए गए उदाप्रत्येकण को प्राप्त करने के लिए प्रोग्राम के लिए दुर्गम हो गया है। चूंकि परिभाषित करना कि ऐसा उदाप्रत्येकण भी समान है। विशेष रूप से अमूर्त में (चूंकि स्मृति का एक पुन: उपयोग किया गया। ब्लॉक भी कुछ इंद्रियों में केवल एक ही वस्तु है।
अन्य उदाहरणों के साथ आंशिक अलियासिंग को भी बाप्रत्येक करने के लिए इस स्वयंसिद्ध को शक्तिशाली किया जा सकता है। व्यावहारिक उपयोग के लिए, जैसे स्वयंसिद्ध अभी भी <kbd>create</kbd>() के कार्यान्वयन की अनुमति दे सकता है, जो पहले से बनाए गए उदाहरण को प्राप्त करने के लिए प्रोग्राम के लिए दुर्गम हो गया है। चूंकि परिभाषित करना कि ऐसा उदाहरण भी समान है। विशेष रूप से अमूर्त में (चूंकि स्मृति का एक पुन: उपयोग किया गया। ब्लॉक भी कुछ इंद्रियों में केवल एक ही वस्तु है।


==== उदाप्रत्येकण: अमूर्त समूह (अनिवार्य) ====
==== उदाहरण: अमूर्त समूह (अनिवार्य) ====
एक अन्य उदाप्रत्येकण के रूप में अमूर्त स्टैक की अनिवार्य-शैली की परिभाषा निर्दिष्ट कर सकती है कि स्टैक S की स्थिति को केवल संचालन द्वारा संशोधित किया जा सकता है।
एक अन्य उदाहरण के रूप में अमूर्त स्टैक की अनिवार्य-शैली की परिभाषा निर्दिष्ट कर सकती है कि स्टैक S की स्थिति को केवल संचालन द्वारा संशोधित किया जा सकता है।
* <kbd>push</kbd>(S, x), जहाँ x अनिर्दिष्ट प्रकृति का कुछ मान है।
* <kbd>push</kbd>(S, x), जहाँ x अनिर्दिष्ट प्रकृति का कुछ मान है।
* <kbd>pop</kbd>(S), जो परिणाम के रूप में मूल्य देता है।
* <kbd>pop</kbd>(S), जो परिणाम के रूप में मूल्य देता है।
Line 66: Line 66:
* किसी भी मान x और किसी अमूर्त चर V के लिए संचालन का क्रम {<kbd>push</kbd>(S, x); ''V'' ← <kbd>pop</kbd>(S) }, V ← x के बराबर है।
* किसी भी मान x और किसी अमूर्त चर V के लिए संचालन का क्रम {<kbd>push</kbd>(S, x); ''V'' ← <kbd>pop</kbd>(S) }, V ← x के बराबर है।


चूँकि असाइनमेंट V ← x, परिभाषा के अनुअमूर्त S की स्थिति को नहीं बदल सकता है। इस स्थिति का तात्पर्य है कि V ← <kbd>pop</kbd>(S) S को उस स्थिति में पुनर्स्थापित करता है। जो <kbd>push</kbd से पहले थी >(''S'', ''x'')। इस स्थिति से अमूर्त चर के गुणों से यह इस प्रकार है। उदाप्रत्येकण के लिए अनुक्रम
चूँकि असाइनमेंट V ← x, परिभाषा के अनुअमूर्त S की स्थिति को नहीं बदल सकता है। इस स्थिति का तात्पर्य है कि V ← <kbd>pop</kbd>(S) S को उस स्थिति में पुनर्स्थापित करता है। जो <kbd>push</kbd से पहले थी >(''S'', ''x'')। इस स्थिति से अमूर्त चर के गुणों से यह इस प्रकार है। उदाहरण के लिए अनुक्रम
: { <kbd>push</kbd>(''S'', ''x''); <kbd>push</kbd>(''S'', ''y''); ''U'' ← <kbd>pop</kbd>(''S''); <kbd>push</kbd>(''S'', ''z''); ''V'' ← <kbd>pop</kbd>(''S''); ''W'' ← <kbd>pop</kbd>(''S'') }
: { <kbd>push</kbd>(''S'', ''x''); <kbd>push</kbd>(''S'', ''y''); ''U'' ← <kbd>pop</kbd>(''S''); <kbd>push</kbd>(''S'', ''z''); ''V'' ← <kbd>pop</kbd>(''S''); ''W'' ← <kbd>pop</kbd>(''S'') }
जहां x, y, और z कोई मान हैं, और U, V, W जोड़ीदार विशिष्ट चर हैं, के समतुल्य है
जहां x, y, और z कोई मान हैं, और U, V, W जोड़ीदार विशिष्ट चर हैं, के समतुल्य है
Line 74: Line 74:
* किसी भी मान x, y और किसी भी विशिष्ट स्टैक S और T के लिए अनुक्रम { <kbd>push</kbd>(S, x); <kbd>push</kbd>(T, y) } { <kbd>push</kbd>(T, y) के बराबर है; <kbd>push</kbd>(''S'', ''x'')}।
* किसी भी मान x, y और किसी भी विशिष्ट स्टैक S और T के लिए अनुक्रम { <kbd>push</kbd>(S, x); <kbd>push</kbd>(T, y) } { <kbd>push</kbd>(T, y) के बराबर है; <kbd>push</kbd>(''S'', ''x'')}।


अमूर्त स्टैक परिभाषा में सामान्यतः [[बूलियन मान]]-मूल्यवान फलन <kbd>खाली</kbd>(S) और एक <kbd>बनाना</kbd>() ऑपरेशन सम्मिलित होता है। जो स्टैक उदाप्रत्येकण वापस करता है। इसके समकक्ष स्वयंसिद्धों के साथ व्यवस्थित करता है।
अमूर्त स्टैक परिभाषा में सामान्यतः [[बूलियन मान]]-मूल्यवान फलन <kbd>खाली</kbd>(S) और एक <kbd>बनाना</kbd>() ऑपरेशन सम्मिलित होता है। जो स्टैक उदाहरण वापस करता है। इसके समकक्ष स्वयंसिद्धों के साथ व्यवस्थित करता है।
* <kbd>create</kbd>() ≠ S किसी भी पिछले स्टैक के लिए S (एक नया बनाया गया स्टैक पिछले सभी स्टैक से अलग है)।
* <kbd>create</kbd>() ≠ S किसी भी पिछले स्टैक के लिए S (एक नया बनाया गया स्टैक पिछले सभी स्टैक से अलग है)।
* <kbd>empty</kbd>(<kbd>create</kbd>() नया बनाया गया समूब खाली है।
* <kbd>empty</kbd>(<kbd>create</kbd>() नया बनाया गया समूब खाली है।
Line 80: Line 80:


====एकल-आवृत्ति शैली ====
====एकल-आवृत्ति शैली ====
कभी-कभी एडीटी को परिभाषित किया जाता है। जैसे कि एल्गोरिथम के निष्पादन के समय इसका केवल एक उदाप्रत्येकण उपस्थित था और सभी ऑपरेशन उस उदाप्रत्येकण पर संचालित किए गए थे। जो स्पष्ट रूप से नोट नहीं किया गया है। उदाप्रत्येकण के लिए उपरोक्त अमूर्त स्टैक को ऑपरेशन <kbd>push</kbd>(x) और <kbd>pop</kbd>() के साथ परिभाषित किया जा सकता था। जो केवल उपस्थिता स्टैक पर काम करता है। इस शैली में एडीटी परिभाषाओं को सरलता से एडीटी के कई सह-अस्तित्व वाले उदाप्रत्येकणों को स्वीकार करने के लिए पुनः लिखा जा सकता है। एक स्पष्ट उदाप्रत्येकण पैरामीटर (जैसे पिछले उदाप्रत्येकण में S) को प्रत्येक ऑपरेशन में जोड़ा जाता है। जो अंतर्निहित उदाप्रत्येकण का उपयोग करता है या संशोधित करता है।
कभी-कभी एडीटी को परिभाषित किया जाता है। जैसे कि एल्गोरिथम के निष्पादन के समय इसका केवल एक उदाहरण उपस्थित था और सभी ऑपरेशन उस उदाहरण पर संचालित किए गए थे। जो स्पष्ट रूप से नोट नहीं किया गया है। उदाहरण के लिए उपरोक्त अमूर्त स्टैक को ऑपरेशन <kbd>push</kbd>(x) और <kbd>pop</kbd>() के साथ परिभाषित किया जा सकता था। जो केवल उपस्थिता स्टैक पर काम करता है। इस शैली में एडीटी परिभाषाओं को सरलता से एडीटी के कई सह-अस्तित्व वाले उदाहरणों को स्वीकार करने के लिए पुनः लिखा जा सकता है। एक स्पष्ट उदाहरण पैरामीटर (जैसे पिछले उदाहरण में S) को प्रत्येक ऑपरेशन में जोड़ा जाता है। जो अंतर्निहित उदाहरण का उपयोग करता है या संशोधित करता है।


दूसरी ओर कुछ एडीटी को कई उदाप्रत्येकण ग्रहण किए बिना अमूर्त्थक रूप से परिभाषित नहीं किया जा सकता है। यह वह स्थिति है, जब एकल ऑपरेशन एडीटी के पैरामीटर के रूप में दो अलग-अलग उदाप्रत्येकण लेता है। उदाप्रत्येकण के लिए <kbd>तुलना</kbd> (S, T) ऑपरेशन के साथ अमूर्त स्टैक की परिभाषा को बढ़ाने पर विचार करें जो यह जाँचता है कि स्टैक S और T में समान क्रम में समान आइटम हैं या नहीं।
दूसरी ओर कुछ एडीटी को कई उदाहरण ग्रहण किए बिना अमूर्त्थक रूप से परिभाषित नहीं किया जा सकता है। यह वह स्थिति है, जब एकल ऑपरेशन एडीटी के पैरामीटर के रूप में दो अलग-अलग उदाहरण लेता है। उदाहरण के लिए <kbd>तुलना</kbd> (S, T) ऑपरेशन के साथ अमूर्त स्टैक की परिभाषा को बढ़ाने पर विचार करें जो यह जाँचता है कि स्टैक S और T में समान क्रम में समान आइटम हैं या नहीं।


=== कार्यात्मक-शैली परिभाषा ===
=== कार्यात्मक-शैली परिभाषा ===
Line 90: Line 90:


==== उदाहरण: अमूर्त समूह (कार्यात्मक) ====
==== उदाहरण: अमूर्त समूह (कार्यात्मक) ====
उदाप्रत्येकण के लिए अमूर्त समूह की एक पूर्ण कार्यात्मक-शैली परिभाषा तीन परिचालनों का उपयोग कर सकती है:
उदाहरण के लिए अमूर्त समूह की एक पूर्ण कार्यात्मक-शैली परिभाषा तीन परिचालनों का उपयोग कर सकती है:
* <kbd>push</kbd>: एक स्टैक स्थिति और मान लेता है। एक स्टैक स्थिति लौटाता है।
* <kbd>push</kbd>: एक स्टैक स्थिति और मान लेता है। एक स्टैक स्थिति लौटाता है।
* <kbd>top</kbd>: एक समूह स्थिति लेता है, एक मान देता है।
* <kbd>top</kbd>: एक समूह स्थिति लेता है, एक मान देता है।
Line 103: Line 103:
ध्यान दें कि ये सिद्धांत <kbd>top</kbd>(s) या <kbd>pop</kbd>(s) के प्रभाव को परिभाषित नहीं करते हैं। जब तक कि s <kbd>push उपस्थित न हो</kbd द्वारा लौटाई गई स्टैक स्थिति नहीं है >। चूँकि <kbd>push</kbd> स्टैक को गैर-खाली छोड़ देता है। वे दो ऑपरेशन अपरिभाषित हैं। जब s = Λ। दूसरी ओर स्वयंसिद्ध (और साइड इफेक्ट की कमी) का अर्थ है कि <kbd>push</kbd>(s, x) = <kbd>push</kbd>(t, y) यदि और केवल यदि x = y और s = t।
ध्यान दें कि ये सिद्धांत <kbd>top</kbd>(s) या <kbd>pop</kbd>(s) के प्रभाव को परिभाषित नहीं करते हैं। जब तक कि s <kbd>push उपस्थित न हो</kbd द्वारा लौटाई गई स्टैक स्थिति नहीं है >। चूँकि <kbd>push</kbd> स्टैक को गैर-खाली छोड़ देता है। वे दो ऑपरेशन अपरिभाषित हैं। जब s = Λ। दूसरी ओर स्वयंसिद्ध (और साइड इफेक्ट की कमी) का अर्थ है कि <kbd>push</kbd>(s, x) = <kbd>push</kbd>(t, y) यदि और केवल यदि x = y और s = t।


जैसा कि गणित की कुछ अन्य शाखाओं में होता है। यह मान लेना भी प्रथागत है कि स्टैक अवस्थाएँ केवल वे हैं, जिनका अस्तित्व स्वयंसिद्धों से सीमित संख्या में चरणों में सिद्ध किया जा सकता है। उपरोक्त अमूर्त स्टैक उदाप्रत्येकण में इस नियम का अर्थ है कि प्रत्येक स्टैक मूल्यों का एक परिमित अनुक्रम है। जो <kbd>pop</kbd>s की सीमित संख्या के बाद खाली स्टैक (Λ) बन जाता है। स्वयं में ऊपर दिए गए स्वयंसिद्ध अनंत स्टैक के अस्तित्व को प्रत्येक बार नहीं करते हैं (जो सदैव के लिए pop पेड हो सकते हैं, प्रत्येक बार एक अलग स्थिति उत्पन्न करते हैं) या गोलाकार समूह (जो एक परिमित संख्या के बाद उसी स्थिति में वापस आ जाते हैं) विशेष रूप से वे ऐसी स्थिति को उत्पन्न नहीं करते हैं। जैसे <kbd>pop</kbd>(s) = s या <kbd>push</kbd>(s, x) = s । चूंकि दिए गए कार्यों के साथ ऐसे समूह स्थिति प्राप्त नहीं किए जा सकते हैं। इसलिए उन्हें अस्तित्व में नहीं माना जाता है।
जैसा कि गणित की कुछ अन्य शाखाओं में होता है। यह मान लेना भी प्रथागत है कि स्टैक अवस्थाएँ केवल वे हैं, जिनका अस्तित्व स्वयंसिद्धों से सीमित संख्या में चरणों में सिद्ध किया जा सकता है। उपरोक्त अमूर्त स्टैक उदाहरण में इस नियम का अर्थ है कि प्रत्येक स्टैक मूल्यों का एक परिमित अनुक्रम है। जो <kbd>pop</kbd>s की सीमित संख्या के बाद खाली स्टैक (Λ) बन जाता है। स्वयं में ऊपर दिए गए स्वयंसिद्ध अनंत स्टैक के अस्तित्व को प्रत्येक बार नहीं करते हैं (जो सदैव के लिए pop पेड हो सकते हैं, प्रत्येक बार एक अलग स्थिति उत्पन्न करते हैं) या गोलाकार समूह (जो एक परिमित संख्या के बाद उसी स्थिति में वापस आ जाते हैं) विशेष रूप से वे ऐसी स्थिति को उत्पन्न नहीं करते हैं। जैसे <kbd>pop</kbd>(s) = s या <kbd>push</kbd>(s, x) = s । चूंकि दिए गए कार्यों के साथ ऐसे समूह स्थिति प्राप्त नहीं किए जा सकते हैं। इसलिए उन्हें अस्तित्व में नहीं माना जाता है।


=== जटिलता सम्मिलित करना है या नहीं ===
=== जटिलता सम्मिलित करना है या नहीं ===
Line 126: Line 126:
कुछ ऑपरेशन जो प्रायः एडीटीs (संभवतः अन्य नामों के अनुअमूर्त) के लिए निर्दिष्ट होते हैं
कुछ ऑपरेशन जो प्रायः एडीटीs (संभवतः अन्य नामों के अनुअमूर्त) के लिए निर्दिष्ट होते हैं
* <kbd>compare</kbd>(''s'', ''t''), जो परीक्षण करता है कि क्या दो दृष्टान्तों की अवस्थाएँ किसी अर्थ में समान हैं।
* <kbd>compare</kbd>(''s'', ''t''), जो परीक्षण करता है कि क्या दो दृष्टान्तों की अवस्थाएँ किसी अर्थ में समान हैं।
* <kbd>hash</kbd>(''s''), जो उदाप्रत्येकण की स्थिति से कुछ मानक [[हैश फंकशन]] की गणना करता है;
* <kbd>hash</kbd>(''s''), जो उदाहरण की स्थिति से कुछ मानक [[हैश फंकशन]] की गणना करता है;
* <kbd>print</kbd>(''s'')या show(s), जो उदाप्रत्येकण की स्थिति का मानव-पठनीय प्रतिनिधित्व उत्पन्न करता है।
* <kbd>print</kbd>(''s'')या show(s), जो उदाहरण की स्थिति का मानव-पठनीय प्रतिनिधित्व उत्पन्न करता है।


अनिवार्य-शैली एडीटी परिभाषाओं में प्रायः यह भी पाया जाता है।
अनिवार्य-शैली एडीटी परिभाषाओं में प्रायः यह भी पाया जाता है।
* <kbd>create</kbd>(), जो एडीटी का एक नया उदाप्रत्येकण देता है।
* <kbd>create</kbd>(), जो एडीटी का एक नया उदाहरण देता है।
* <kbd>initializes</kbd>(s), जो आगे के संचालन के लिए एक नया बनाया गया उदाप्रत्येकण तैयार करता है या इसे कुछ प्रारंभिक अवस्था में समुच्चय करता है।
* <kbd>initializes</kbd>(s), जो आगे के संचालन के लिए एक नया बनाया गया उदाहरण तैयार करता है या इसे कुछ प्रारंभिक अवस्था में समुच्चय करता है।
* copy(s, t), जो उदाप्रत्येकण s को t के समतुल्य स्थिति में रखती है।
* copy(s, t), जो उदाहरण s को t के समतुल्य स्थिति में रखती है।
* clone(t), जो s ← <kbd>create</kbd>(), <kbd>copy</kbd>(s, t) करता है और s लौटाता है।
* clone(t), जो s ← <kbd>create</kbd>(), <kbd>copy</kbd>(s, t) करता है और s लौटाता है।
* free(s) या destroy(s), जो s द्वारा उपयोग की गई मेमोरी और अन्य संसाधनों को पुनः प्राप्त करता है।
* free(s) या destroy(s), जो s द्वारा उपयोग की गई मेमोरी और अन्य संसाधनों को पुनः प्राप्त करता है।
Line 138: Line 138:
<kbd>मुफ्त</kbd> ऑपरेशन सामान्य रूप से प्रासंगिक या अमूर्त्थक नहीं है क्योंकि एडीटी सैद्धांतिक संस्थाएं हैं। जो मेमोरी का उपयोग नहीं करती हैं। चूंकि यह आवश्यक हो सकता है। जब किसी को एडीटी का उपयोग करने वाले एल्गोरिथम द्वारा उपयोग किए गए संग्रहण का विश्लेषण करने की आवश्यकता हो। उस स्थिति में किसी को अतिरिक्त सिद्धांतों की आवश्यकता होती है। जो निर्दिष्ट करती है कि प्रत्येक एडीटी इंस्टेंस अपने स्थिति के कार्य के रूप में कितनी मेमोरी का उपयोग करता है और इसमें से कितना <kbd>मुफ्त</kbd> द्वारा पूल में वापस किया जाता है।
<kbd>मुफ्त</kbd> ऑपरेशन सामान्य रूप से प्रासंगिक या अमूर्त्थक नहीं है क्योंकि एडीटी सैद्धांतिक संस्थाएं हैं। जो मेमोरी का उपयोग नहीं करती हैं। चूंकि यह आवश्यक हो सकता है। जब किसी को एडीटी का उपयोग करने वाले एल्गोरिथम द्वारा उपयोग किए गए संग्रहण का विश्लेषण करने की आवश्यकता हो। उस स्थिति में किसी को अतिरिक्त सिद्धांतों की आवश्यकता होती है। जो निर्दिष्ट करती है कि प्रत्येक एडीटी इंस्टेंस अपने स्थिति के कार्य के रूप में कितनी मेमोरी का उपयोग करता है और इसमें से कितना <kbd>मुफ्त</kbd> द्वारा पूल में वापस किया जाता है।


== उदाप्रत्येकण ==
== उदाहरण ==
कुछ सामान्य एडीटी, जो विभिन्न प्रकार के अनुप्रयोगों में उपयोगी सिद्ध हुए हैं, हैं
कुछ सामान्य एडीटी, जो विभिन्न प्रकार के अनुप्रयोगों में उपयोगी सिद्ध हुए हैं, हैं
{{div col|colwidth=20em}}
{{div col|colwidth=20em}}
Line 157: Line 157:
* [[डबल-एंडेड प्राथमिकता पंक्ति]]
* [[डबल-एंडेड प्राथमिकता पंक्ति]]
{{div col end}}
{{div col end}}
इन एडीटी में से प्रत्येक को कई तरीकों और रूपों में परिभाषित किया जा सकता है, जरूरी नहीं कि समकक्ष उदाप्रत्येकण के लिए अमूर्त स्टैक में <kbd>गिनती</kbd> ऑपरेशन हो सकता है या नहीं भी हो सकता है। जो बताता है कि कितने आइटम push किए गए हैं और अभी तक pop नहीं हुए हैं। यह विकल्प न केवल इसके ग्राहकों के लिए बल्कि कार्यान्वयन के लिए भी एक अंतर बनाता है।
इन एडीटी में से प्रत्येक को कई तरीकों और रूपों में परिभाषित किया जा सकता है, जरूरी नहीं कि समकक्ष उदाहरण के लिए अमूर्त स्टैक में <kbd>गिनती</kbd> ऑपरेशन हो सकता है या नहीं भी हो सकता है। जो बताता है कि कितने आइटम push किए गए हैं और अभी तक pop नहीं हुए हैं। यह विकल्प न केवल इसके ग्राहकों के लिए बल्कि कार्यान्वयन के लिए भी एक अंतर बनाता है।


; अमूर्त चित्रमय डेटा प्रकार
; अमूर्त चित्रमय डेटा प्रकार
Line 164: Line 164:
== कार्यान्वयन ==
== कार्यान्वयन ==
{{further|अपारदर्शी डेटा प्रकार}}
{{further|अपारदर्शी डेटा प्रकार}}
एडीटी को संचालित करने का अर्थ है प्रत्येक अमूर्त ऑपरेशन के लिए एक [[सबरूटीन]] प्रदान करना। एडीटी उदाप्रत्येकणों को कुछ ठोस डेटा संरचना द्वारा दर्शाया जाता है। जो एडीटी के विनिर्देशों के अनुअमूर्त उन प्रक्रियाओं द्वारा हेरफेर किया जाता है।
एडीटी को संचालित करने का अर्थ है प्रत्येक अमूर्त ऑपरेशन के लिए एक [[सबरूटीन]] प्रदान करना। एडीटी उदाहरणों को कुछ ठोस डेटा संरचना द्वारा दर्शाया जाता है। जो एडीटी के विनिर्देशों के अनुअमूर्त उन प्रक्रियाओं द्वारा हेरफेर किया जाता है।


सामान्यतः कई अलग-अलग ठोस डेटा संरचनाओं का उपयोग करके एक ही एडीटी को संचालित करने के कई प्रकार हैं। इस प्रकार उदाप्रत्येकण के लिए अमूर्त समूह को एक लिंक्ड सूची या एक ऐरे डेटा संरचना द्वारा कार्यान्वित किया जा सकता है।
सामान्यतः कई अलग-अलग ठोस डेटा संरचनाओं का उपयोग करके एक ही एडीटी को संचालित करने के कई प्रकार हैं। इस प्रकार उदाहरण के लिए अमूर्त समूह को एक लिंक्ड सूची या एक ऐरे डेटा संरचना द्वारा कार्यान्वित किया जा सकता है।


ग्राहकों को कार्यान्वयन पर निर्भर रहने से रोकने के लिए एडीटी को प्रायः एक या अधिक [[मॉड्यूल (प्रोग्रामिंग)]] में एक अपारदर्शी डेटा प्रकार के रूप में पैक किया जाता है। जिसके इंटरफ़ेस में केवल संचालन के हस्ताक्षर (संख्या और प्रकार के पैरामीटर और परिणाम) होते हैं। मॉड्यूल के कार्यान्वयन अर्थात् प्रक्रियाओं के निकाय और उपयोग की जाने वाली ठोस डेटा संरचना को तब मॉड्यूल के अधिकांश ग्राहकों से छिपाया जा सकता है। इससे ग्राहकों को प्रभावित किए बिना कार्यान्वयन को बदलना संभव हो जाता है। यदि कार्यान्वयन उजागर होता है। तो इसे एक पारदर्शी डेटा प्रकार के रूप में जाना जाता है।
ग्राहकों को कार्यान्वयन पर निर्भर रहने से रोकने के लिए एडीटी को प्रायः एक या अधिक [[मॉड्यूल (प्रोग्रामिंग)]] में एक अपारदर्शी डेटा प्रकार के रूप में पैक किया जाता है। जिसके इंटरफ़ेस में केवल संचालन के हस्ताक्षर (संख्या और प्रकार के पैरामीटर और परिणाम) होते हैं। मॉड्यूल के कार्यान्वयन अर्थात् प्रक्रियाओं के निकाय और उपयोग की जाने वाली ठोस डेटा संरचना को तब मॉड्यूल के अधिकांश ग्राहकों से छिपाया जा सकता है। इससे ग्राहकों को प्रभावित किए बिना कार्यान्वयन को बदलना संभव हो जाता है। यदि कार्यान्वयन उजागर होता है। तो इसे एक पारदर्शी डेटा प्रकार के रूप में जाना जाता है।


एडीटी संचालित करते समय प्रत्येक उदाप्रत्येकण (अनिवार्य-शैली परिभाषाओं में) या प्रत्येक राज्य (कार्यात्मक-शैली परिभाषाओं में) सामान्यतः किसी प्रकार के [[हैंडल (कंप्यूटिंग)]] द्वारा दर्शाया जाता है।<ref>{{cite book | author=Robert Sedgewick | title=Algorithms in C | publisher=Addison/Wesley | year=1998 | isbn=978-0-201-31452-6 | url-access=registration | url=https://archive.org/details/algorithmsinc00sedg }}, definition 4.4.</ref> आधुनिक वस्तु-उन्मुख भाषाएँ जैसे [[C++|सी++]] और जावा प्रोग्रामिंग भाषा अमूर्त डेटा प्रकारों के एक रूप का समर्थन करती हैं। जब एक वर्ग का उपयोग एक प्रकार के रूप में किया जाता है। तो यह एक अमूर्त प्रकार होता है, जो एक छिपे हुए प्रतिनिधित्व को संदर्भित करता है। इस मॉडल में एडीटी को सामान्यतः एक वर्ग (कंप्यूटर विज्ञान) के रूप में संचालित किया जाता है और एडीटी का प्रत्येक उदाप्रत्येकण सामान्यतः उस वर्ग का एक ऑब्जेक्ट (कंप्यूटर विज्ञान) होता है। मॉड्यूल का इंटरफ़ेस सामान्यतः निर्माणकर्ताओं को सामान्य प्रक्रियाओं के रूप में घोषित करता है और अधिकांश अन्य एडीटी संचालन उस वर्ग के तरीके (कंप्यूटर प्रोग्रामिंग) के रूप में होते हैं। चूंकि ऐसा दृष्टिकोण एडीटी में पाए जाने वाले कई प्रतिनिधित्वात्मक वेरिएंट को सरलता से एनकैप्सुलेट नहीं करता है। यह वस्तु-उन्मुख कार्यक्रमों की व्यापकता को भी कम कर सकता है। एक शुद्ध वस्तु-उन्मुख कार्यक्रम में जो इंटरफेस को प्रकार के रूप में उपयोग करता है, प्रकार व्यवहार को संदर्भित करता है, परन्तु प्रतिनिधित्व नहीं करता है।
एडीटी संचालित करते समय प्रत्येक उदाहरण (अनिवार्य-शैली परिभाषाओं में) या प्रत्येक राज्य (कार्यात्मक-शैली परिभाषाओं में) सामान्यतः किसी प्रकार के [[हैंडल (कंप्यूटिंग)]] द्वारा दर्शाया जाता है।<ref>{{cite book | author=Robert Sedgewick | title=Algorithms in C | publisher=Addison/Wesley | year=1998 | isbn=978-0-201-31452-6 | url-access=registration | url=https://archive.org/details/algorithmsinc00sedg }}, definition 4.4.</ref> आधुनिक वस्तु-उन्मुख भाषाएँ जैसे [[C++|सी++]] और जावा प्रोग्रामिंग भाषा अमूर्त डेटा प्रकारों के एक रूप का समर्थन करती हैं। जब एक वर्ग का उपयोग एक प्रकार के रूप में किया जाता है। तो यह एक अमूर्त प्रकार होता है, जो एक छिपे हुए प्रतिनिधित्व को संदर्भित करता है। इस मॉडल में एडीटी को सामान्यतः एक वर्ग (कंप्यूटर विज्ञान) के रूप में संचालित किया जाता है और एडीटी का प्रत्येक उदाहरण सामान्यतः उस वर्ग का एक ऑब्जेक्ट (कंप्यूटर विज्ञान) होता है। मॉड्यूल का इंटरफ़ेस सामान्यतः निर्माणकर्ताओं को सामान्य प्रक्रियाओं के रूप में घोषित करता है और अधिकांश अन्य एडीटी संचालन उस वर्ग के तरीके (कंप्यूटर प्रोग्रामिंग) के रूप में होते हैं। चूंकि ऐसा दृष्टिकोण एडीटी में पाए जाने वाले कई प्रतिनिधित्वात्मक वेरिएंट को सरलता से एनकैप्सुलेट नहीं करता है। यह वस्तु-उन्मुख कार्यक्रमों की व्यापकता को भी कम कर सकता है। एक शुद्ध वस्तु-उन्मुख कार्यक्रम में जो इंटरफेस को प्रकार के रूप में उपयोग करता है, प्रकार व्यवहार को संदर्भित करता है, परन्तु प्रतिनिधित्व नहीं करता है।


उदाप्रत्येकण: अमूर्त समूह का कार्यान्वयन एक उदाप्रत्येकण के रूप में यहाँ सी (प्रोग्रामिंग लैंग्वेज) में उपरोक्त अमूर्त स्टैक का कार्यान्वयन है।
उदाहरण: अमूर्त समूह का कार्यान्वयन एक उदाहरण के रूप में यहाँ सी (प्रोग्रामिंग लैंग्वेज) में उपरोक्त अमूर्त स्टैक का कार्यान्वयन है।


==== इम्पीरेटिव-स्टाइल इंटरफ़ेस ====
==== इम्पीरेटिव-स्टाइल इंटरफ़ेस ====
एक अनिवार्य-शैली इंटरफ़ेस हो सकता है:
अनिवार्य-शैली इंटरफ़ेस हो सकता है:


typedef struct stack_Rep stack_Rep;     // type: stack instance representation (opaque record)
<syntaxhighlight lang="cpp">
typedef struct stack_Rep stack_Rep;       // type: stack instance representation (opaque record)
typedef stack_Rep* stack_T;              // type: handle to a stack instance (opaque pointer)
typedef void* stack_Item;                // type: value stored in stack instance (arbitrary address)


typedef stack_Rep* stack_T;             // type: handle to a stack instance (opaque pointer)
stack_T stack_create(void);               // creates a new empty stack instance
void stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack
stack_Item stack_pop(stack_T s);          // removes the top item from the stack and returns it
bool stack_empty(stack_T s);              // checks whether stack is empty
</syntaxhighlight>


typedef void* stack_Item;                // type: value stored in stack instance (arbitrary address)
इस इंटरफ़ेस का उपयोग निम्नलिखित तरीके से किया जा सकता है:
<syntaxhighlight lang="cpp">
#include <stack.h>          // includes the stack interface


stack_T stack_create(void);             // creates a new empty stack instance
stack_T s = stack_create(); // creates a new empty stack instance
int x = 17;
stack_push(s, &x);          // adds the address of x at the top of the stack
void* y = stack_pop(s);    // removes the address of x from the stack and returns it
if (stack_empty(s)) { }    // does something if stack is empty
</syntaxhighlight>
 
इस इंटरफ़ेस को कई प्रकार से संचालित किया जा सकता है। कार्यान्वयन मनमाने ढंग से अक्षम हो सकता है क्योंकि उपरोक्त एडीटी की औपचारिक परिभाषा निर्दिष्ट नहीं करती है कि समूह कितनी स्थान का उपयोग कर सकता है, न ही प्रत्येक ऑपरेशन में कितना समय लगना चाहिए। यह यह भी निर्दिष्ट नहीं करता है कि कॉल x ← <kbd>pop</kbd>(s) के बाद स्टैक स्थिति उपस्थित रहती है या नहीं।
 
व्यवहार में औपचारिक परिभाषा में यह निर्दिष्ट होना चाहिए कि स्थान धकेले गए आइटमों की संख्या के समानुपाती है और अभी तक pop नहीं हुआ है और ऊपर दिए गए प्रत्येक ऑपरेशन को उस संख्या से स्वतंत्र रूप से निरंतर समय में पूरा करना चाहिए। इन अतिरिक्त विशिष्टताओं का अनुपालन करने के लिए कार्यान्वयन दो पूर्णांकों (एक आइटम संख्या और सरणी आकार) के साथ एक लिंक की गई सूची या अमूर्तणी (गतिशील आकार बदलने के साथ) का उपयोग कर सकता है।


void stack_push(stack_T s, stack_Item x);  // adds an item at the top of the stack


stack_Item stack_pop(stack_T s);        // removes the top item from the stack and returns it


bool stack_empty(stack_T s);            // checks whether stack is empty


इस इंटरफ़ेस का उपयोग निम्नलिखित तरीके से किया जा सकता है:


<nowiki>#</nowiki>include <stack.h>              // includes the stack interface


stack_T s = stack_create();        // creates a new empty stack instance


int x = 17;
stack_push(s, &x);      // adds the address of x at the top of the stack


void* y = stack_pop(s);          // removes the address of x from the stack and returns it


if (stack_empty(s)) { }            // does something if stack is empty


इस इंटरफ़ेस को कई प्रकार से संचालित किया जा सकता है। कार्यान्वयन मनमाने ढंग से अक्षम हो सकता है क्योंकि उपरोक्त एडीटी की औपचारिक परिभाषा निर्दिष्ट नहीं करती है कि समूह कितनी स्थान का उपयोग कर सकता है, न ही प्रत्येक ऑपरेशन में कितना समय लगना चाहिए। यह यह भी निर्दिष्ट नहीं करता है कि कॉल x ← <kbd>pop</kbd>(s) के बाद स्टैक स्थिति उपस्थित रहती है या नहीं।


व्यवहार में औपचारिक परिभाषा में यह निर्दिष्ट होना चाहिए कि स्थान धकेले गए आइटमों की संख्या के समानुपाती है और अभी तक pop नहीं हुआ है और ऊपर दिए गए प्रत्येक ऑपरेशन को उस संख्या से स्वतंत्र रूप से निरंतर समय में पूरा करना चाहिए। इन अतिरिक्त विशिष्टताओं का अनुपालन करने के लिए कार्यान्वयन दो पूर्णांकों (एक आइटम संख्या और सरणी आकार) के साथ एक लिंक की गई सूची या अमूर्तणी (गतिशील आकार बदलने के साथ) का उपयोग कर सकता है।


==== कार्यात्मक-शैली इंटरफ़ेस ====
==== कार्यात्मक-शैली इंटरफ़ेस ====
कार्यात्मक प्रोग्रामिंग भाषाओं के लिए कार्यात्मक-शैली एडीटी परिभाषाएं अधिक उपयुक्त हैं और इसके विपरीत। चूंकि सी जैसी अनिवार्य भाषा में भी कोई कार्यात्मक-शैली इंटरफ़ेस प्रदान कर सकता है। उदाप्रत्येकण के लिए:
कार्यात्मक प्रोग्रामिंग भाषाओं के लिए कार्यात्मक-शैली एडीटी परिभाषाएं अधिक उपयुक्त हैं और इसके विपरीत। चूंकि सी जैसी अनिवार्य भाषा में भी कोई कार्यात्मक-शैली इंटरफ़ेस प्रदान कर सकता है। उदाहरण के लिए:


=== एडीटी पुस्तकालय ===
=== एडीटी पुस्तकालय ===
Line 215: Line 221:


=== अंतर्निहित अमूर्त डेटा प्रकार ===
=== अंतर्निहित अमूर्त डेटा प्रकार ===
कुछ प्रोग्रामिंग भाषाओं के विनिर्देश जानबूझकर कुछ अंतर्निहित डेटा प्रकारों के प्रतिनिधित्व के बारे में अस्पष्ट हैं। केवल उन कार्यों को परिभाषित करते हैं, जो उन पर किए जा सकते हैं। इसलिए उन प्रकारों को अंतर्निर्मित एडीटी के रूप में देखा जा सकता है। उदाप्रत्येकण कई स्क्रिप्टिंग भाषाओं में अमूर्तणियाँ हैं। जैसे कि ऑक, [[लुआ (प्रोग्रामिंग भाषा)]] और [[पर्ल]], जिसे अमूर्त सूची के कार्यान्वयन के रूप में माना जा सकता है।
कुछ प्रोग्रामिंग भाषाओं के विनिर्देश जानबूझकर कुछ अंतर्निहित डेटा प्रकारों के प्रतिनिधित्व के बारे में अस्पष्ट हैं। केवल उन कार्यों को परिभाषित करते हैं, जो उन पर किए जा सकते हैं। इसलिए उन प्रकारों को अंतर्निर्मित एडीटी के रूप में देखा जा सकता है। उदाहरण कई स्क्रिप्टिंग भाषाओं में अमूर्तणियाँ हैं। जैसे कि ऑक, [[लुआ (प्रोग्रामिंग भाषा)]] और [[पर्ल]], जिसे अमूर्त सूची के कार्यान्वयन के रूप में माना जा सकता है।


== यह भी देखें ==
== यह भी देखें ==
Line 236: Line 242:


==संदर्भ==
==संदर्भ==
{{more footnotes|date=April 2022}}
{{refbegin}}
{{refbegin}}
* {{Cite conference
* {{Cite conference
Line 262: Line 267:
*{{Commonscatinline|Abstract data types}}
*{{Commonscatinline|Abstract data types}}
*[https://xlinux.nist.gov/dads/HTML/abstractDataType.html Abstract data type] in [[NIST]] Dictionary of Algorithms and Data Structures
*[https://xlinux.nist.gov/dads/HTML/abstractDataType.html Abstract data type] in [[NIST]] Dictionary of Algorithms and Data Structures
{{Data structures}}
{{Data types}}
{{Authority control}}
{{Authority control}}


{{DEFAULTSORT:Abstract Data Type}}[[Category: सार डेटा प्रकार | सार डेटा प्रकार ]] [[Category: डेटा के प्रकार]] [[Category: प्रकार सिद्धांत]]
{{DEFAULTSORT:Abstract Data Type}}
 
 


[[Category: Machine Translated Page]]
[[Category:Collapse templates|Abstract Data Type]]
[[Category:Created On 17/02/2023]]
[[Category:Commons category link is locally defined|Abstract Data Type]]
[[Category:Created On 17/02/2023|Abstract Data Type]]
[[Category:Lua-based templates|Abstract Data Type]]
[[Category:Machine Translated Page|Abstract Data Type]]
[[Category:Multi-column templates|Abstract Data Type]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists|Abstract Data Type]]
[[Category:Pages using div col with small parameter|Abstract Data Type]]
[[Category:Pages with script errors|Abstract Data Type]]
[[Category:Short description with empty Wikidata description|Abstract Data Type]]
[[Category:Sidebars with styles needing conversion|Abstract Data Type]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready|Abstract Data Type]]
[[Category:Templates that add a tracking category|Abstract Data Type]]
[[Category:Templates that generate short descriptions|Abstract Data Type]]
[[Category:Templates using TemplateData|Abstract Data Type]]
[[Category:Templates using under-protected Lua modules|Abstract Data Type]]
[[Category:Wikipedia fully protected templates|Div col]]
[[Category:डेटा के प्रकार|Abstract Data Type]]
[[Category:प्रकार सिद्धांत|Abstract Data Type]]
[[Category:सार डेटा प्रकार| सार डेटा प्रकार ]]

Latest revision as of 16:20, 11 March 2023

कंप्यूटर विज्ञान में अमूर्त डेटा प्रकार (एडीटी) डेटा प्रकारों के लिए एक गणितीय मॉडल है। अमूर्त डेटा प्रकार को उसके व्यवहार (सिमेंटिक्स (कंप्यूटर विज्ञान)) द्वारा परिभाषित किया जाता है। डेटा के उपयोगकर्ता (कंप्यूटिंग) के दृष्टिकोण से विशेष रूप से संभावित मूल्यों के संदर्भ में इस प्रकार के डेटा पर संभावित संचालन और इन परिचालनों का व्यवहार गणितीय मॉडल डेटा संरचनाओं के विपरीत है। जो डेटा के ठोस प्रतिनिधित्व हैं और एक कार्यान्वयनकर्ता के दृष्टिकोण हैं, परन्तु उपयोगकर्ता नहीं है।

औपचारिक रूप से एडीटी को वस्तुओं के एक वर्ग के रूप में परिभाषित किया जा सकता है। जिसका तार्कपूर्ण व्यवहार मूल्यों के एक समुच्चय और संचालन के समुच्चय द्वारा परिभाषित किया गया है।[1] यह गणित में बीजगणितीय संरचना के अनुरूप है। व्यवहार से क्या अभिप्राय लेखक द्वारा भिन्न होता है। व्यवहार दो मुख्य प्रकार के औपचारिक विनिर्देशों के साथ स्वयंसिद्ध (बीजगणितीय) विनिर्देश और अमूर्त मॉडल होता है।[2] ये क्रमशः अमूर्त मशीन के स्वयंसिद्ध शब्दार्थ और परिचालन शब्दार्थ के अनुरूप हैं। कुछ लेखकों में समय (कंप्यूटिंग संचालन के लिए) और स्थान (मूल्यों का प्रतिनिधित्व करने के लिए) दोनों के संदर्भ में कम्प्यूटेशनल जटिलता सिद्धांत (क्रय मूल्य) भी सम्मिलित है। व्यवहार में कई सामान्य डेटा प्रकार एडीटीएस नहीं हैं क्योंकि अमूर्तता सही नहीं है और उपयोगकर्ताओं को अंकगणितीय अतिप्रवाह जैसे विषयों के बारे में पता होना चाहिए। जो प्रतिनिधित्व के कारण होते हैं। उदाहरण के लिए पूर्णांकों को प्रायः निश्चित-चौड़ाई मान (32-बिट या 64-बिट बाइनरी संख्या) के रूप में संग्रहीत किया जाता है और इस प्रकार अधिकतम मान पार होने पर पूर्णांक अतिप्रवाह का अनुभव होता है।

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


अमूर्त डेटा प्रकार

उदाहरण के लिए पूर्णांक एक एडीटी होते हैं। जिन्हें मान ..., -2, -1, 0, 1, 2, ... के रूप में परिभाषित किया जाता है और जोड़, घटाव, गुणा और भाग की संक्रियाओं के साथ-साथ से अधिक के रूप में परिभाषित किया जाता है। जो परिचित गणित के अनुअमूर्त व्यवहार करते हैं। पूर्णांक विभाजन की देखभाल के साथ, कम, आदि स्वतंत्र रूप से कंप्यूटर द्वारा पूर्णांकों का प्रतिनिधित्व कैसे किया जाता है। [lower-alpha 1] स्पष्ट रूप से व्यवहार में विभिन्न स्वयंसिद्धों (संबद्धता और जोड़ की क्रमविनिमेयता आदि) का पालन करना और संचालन पर पूर्व नियम (शून्य से विभाजित नहीं किया जा सकता) सम्मिलित है। सामान्यतः पूर्णांकों को डेटा संरचना में बाइनरी संख्या के रूप प्रायः दो के पूरक के रूप में दर्शाया जाता है। किन्तु बाइनरी-कोडित दशमलव या एक के पूरक में हो सकता है। किन्तु अधिकांश उद्देश्यों के लिए उपयोगकर्ता प्रतिनिधित्व के ठोस विकल्प के अतिरिक्त अमूर्तता के साथ काम कर सकता है और केवल डेटा का उपयोग कर सकते हैं। जैसे कि प्रकार वास्तव में अमूर्त थे।

एडीटी में न केवल संचालन होते हैं। बल्कि मूल्यों का डोमेन भी होता है और परिभाषित संचालन पर बाधाएं होती हैं। इंटरफ़ेस सामान्यतः केवल संचालन को संदर्भित करता है और संचालन पर कुछ बाधाएं जैसे कि पूर्व-नियम और पश्च-नियम। किन्तु संचालन के बीच संबंध जैसी अन्य बाधाओं के लिए नहीं हैं।

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

एल्गोरिदम के एल्गोरिदम का विश्लेषण करते समय यह भी निर्दिष्ट किया जा सकता है कि सभी ऑपरेशन एक ही समय लेते हैं। तथापि कितने डेटा आइटम समूह में धकेल दिए गए हों और यह कि स्टैक प्रत्येक तत्व के लिए भंडारण की निरंतर मात्रा का उपयोग करता है। चूंकि समय सीमा को सदैव एडीटी की परिभाषा का भाग नहीं माना जाता है।

परिचय

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

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


अमूर्त डेटा प्रकार परिभाषित करना

अमूर्त डेटा प्रकार को डेटा ऑब्जेक्ट्स के गणितीय मॉडल के रूप में परिभाषित किया जाता है। जो डेटा प्रकार के साथ-साथ इन ऑब्जेक्ट्स पर काम करने वाले कार्यों को भी बनाता है। उन्हें परिभाषित करने के लिए कोई मानक सम्मेलन नहीं हैं। अनिवार्य (या परिचालन) और कार्यात्मक (या स्वयंसिद्ध) परिभाषा शैलियों के बीच व्यापक विभाजन तैयार किया जा सकता है।

आदेशात्मक-शैली परिभाषा

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

अमूर्त चर

एडीटी की अनिवार्य-शैली की परिभाषाएं प्रायः अमूर्त चर की अवधारणा पर निर्भर करती हैं। जिसे सबसे सरल गैर-तुच्छ एडीटी माना जा सकता है। एक अमूर्त चर V एक परिवर्तनशील इकाई है। जो दो संक्रियाओं को स्वीकार करता है:

  • store(V, x) जहाँ x अनिर्दिष्ट प्रकृति का मान है;
  • fetch(V), जो एक मान देता है,

उस जानकारी के साथ

  • fetch(V) सदैव उसी वेरिएबल V पर नवीनतम store(V, x) ऑपरेशन में उपयोग किए गए मान x को वापस करता है।

भंडारण से पहले लाने की अनुमति नहीं दी जा सकती है। एक निश्चित परिणाम के लिए परिभाषित किया गया है या (कम वांछनीय रूप से) व्यवहार को अनिर्दिष्ट छोड़ दें।

कई प्रोग्रामिंग भाषाओं की प्रकार ऑपरेशन store(V, x) को प्रायः V ← x (या कुछ समान अंकन) लिखा जाता है और fetch(V) निहित होता है। जब कोई चर V का उपयोग उस संदर्भ में किया जाता है। जहाँ मान की आवश्यकता होती है। इस प्रकार उदाहरण के लिए V ← V + 1 को सामान्यतः store(V,fetch(V) + 1) के लिए शॉर्टहैंड समझा जाता है।

इस परिभाषा में यह स्पष्ट रूप से माना जाता है कि नाम सदैव अलग होते हैं: एक चर U में मान संग्रहीत करने से एक अलग चर V की स्थिति पर कोई प्रभाव नहीं पड़ता है। इस धारणा को स्पष्ट करने के लिए कोई बाधा जोड़ सकता है। जो

  • यदि U और V भिन्न चर हैं। तो अनुक्रम {store(U, x); store(V, y) } { store(V, y) स्टोर(यू, एक्स)} के बराबर है।

सामान्यतः एडीटी परिभाषाएँ प्रायः मानती हैं कि कोई भी ऑपरेशन, जो एक एडीटी उदाहरण की स्थिति को बदलता है, उसी एडीटी के किसी अन्य उदाहरण की स्थिति पर कोई प्रभाव नहीं पड़ता है। जब तक कि एडीटी स्वयंसिद्ध कुछ उदाहरणों को कनेक्टेड के रूप में परिभाषित नहीं करता है (अलियासिंग (कंप्यूटिंग) देखें)। विशिष्ट उपाय सबसे सामान्य ऐसे कनेक्शनों में सम्मिलित हैं:

  • अलियासिंग, जिसमें दो या दो से अधिक नाम एक ही डेटा ऑब्जेक्ट को स्पष्ट रूप से संदर्भित करते हैं।
  • रचना, जिसमें एडीटी को (समान या अन्य) एडीटी के उदाहरण सम्मिलित करने के लिए परिभाषित किया गया है।
  • संदर्भ, जिसमें एडीटी को (समान या अन्य) एडीटी के उदाहरण के संदर्भ में परिभाषित किया गया है।

उदाहरण के लिए अमूर्त रिकॉर्ड (कंप्यूटर विज्ञान) को सम्मिलित करने के लिए अमूर्त चर की परिभाषा का विस्तार करते समय रिकॉर्ड चर आर के क्षेत्र एफ पर संचालन, स्पष्ट रूप से एफ को सम्मिलित करता है। जो आर से अलग है। किन्तु इसका एक भाग भी है।

एडीटी की परिभाषा अपने उदाहरणों के लिए संग्रहीत मूल्य (एस) को एक विशिष्ट समुच्चय एक्स के सदस्यों तक सीमित कर सकती है। जिसे उन चरों की श्रेणी कहा जाता है। उदाहरण के लिए एक समूह या पंक्ति जैसे समुच्चय के लिए एडीटी पंक्ति में सभी वस्तुओं को पूर्णांक होने के लिए बाध्य कर सकता है या कम से कम सभी एक ही प्रकार के हो सकते हैं। (देखें एकरूपता_और_विषमता_(आँकड़े))। प्रोग्रामिंग भाषाओं की प्रकार ऐसे प्रतिबंध एल्गोरिदम के विवरण और विश्लेषण को सरल बना सकते हैं और इसकी पठनीयता में सुधार कर सकते हैं।

ध्यान दें कि यह परिभाषा fetch(V) के मूल्यांकन के परिणाम के बारे में कुछ भी नहीं बताती है। जब V प्रारंभिक नहीं है अर्थात V पर कोई store ऑपरेशन करने से पहले An एल्गोरिथम, जो ऐसा करता है, उसे अमान्य माना जा सकता है या तो (ए) क्योंकि एडीटी इस प्रकार के ऑपरेशन को प्रतिबंधित करता है या (बी) केवल इसलिए कि इसका प्रभाव एडीटी द्वारा परिभाषित नहीं किया गया है। चूंकि कुछ महत्वपूर्ण एल्गोरिदम हैं। जिनकी दक्षता दृढ़ता से इस धारणा पर निर्भर करती है कि ऐसा fetch नियमानुअमूर्त है और वेरिएबल की सीमा में कुछ अनावश्यक मान देता है।

उदाहरण निर्माण

कुछ एल्गोरिदम को कुछ एडीटी (जैसे नए चर, या नए समूह) के नए उदाहरण बनाने की आवश्यकता होती है। इस प्रकार के एल्गोरिदम का वर्णन करने के लिए सामान्यतः एडीटी परिभाषा में create() ऑपरेशन सम्मिलित होता है। जो एडीटी का सामान्यतः स्वयंसिद्धों के बराबर उदाहरण देता है।

  • create() का परिणाम एल्गोरिथम द्वारा पहले से उपयोग किए जा रहे किसी भी उदाहरण से अलग है।

अन्य उदाहरणों के साथ आंशिक अलियासिंग को भी बाप्रत्येक करने के लिए इस स्वयंसिद्ध को शक्तिशाली किया जा सकता है। व्यावहारिक उपयोग के लिए, जैसे स्वयंसिद्ध अभी भी create() के कार्यान्वयन की अनुमति दे सकता है, जो पहले से बनाए गए उदाहरण को प्राप्त करने के लिए प्रोग्राम के लिए दुर्गम हो गया है। चूंकि परिभाषित करना कि ऐसा उदाहरण भी समान है। विशेष रूप से अमूर्त में (चूंकि स्मृति का एक पुन: उपयोग किया गया। ब्लॉक भी कुछ इंद्रियों में केवल एक ही वस्तु है।

उदाहरण: अमूर्त समूह (अनिवार्य)

एक अन्य उदाहरण के रूप में अमूर्त स्टैक की अनिवार्य-शैली की परिभाषा निर्दिष्ट कर सकती है कि स्टैक S की स्थिति को केवल संचालन द्वारा संशोधित किया जा सकता है।

  • push(S, x), जहाँ x अनिर्दिष्ट प्रकृति का कुछ मान है।
  • pop(S), जो परिणाम के रूप में मूल्य देता है।

उस जानकारी के साथ

  • किसी भी मान x और किसी अमूर्त चर V के लिए संचालन का क्रम {push(S, x); V ← pop(S) }, V ← x के बराबर है।

चूँकि असाइनमेंट V ← x, परिभाषा के अनुअमूर्त S की स्थिति को नहीं बदल सकता है। इस स्थिति का तात्पर्य है कि V ← pop(S) S को उस स्थिति में पुनर्स्थापित करता है। जो push(S, x)। इस स्थिति से अमूर्त चर के गुणों से यह इस प्रकार है। उदाहरण के लिए अनुक्रम

{ push(S, x); push(S, y); U ← pop(S); push(S, z); V ← pop(S); W ← pop(S) }

जहां x, y, और z कोई मान हैं, और U, V, W जोड़ीदार विशिष्ट चर हैं, के समतुल्य है

{ U ← y; V ← z; W ← x }

यहाँ यह स्पष्ट रूप से माना जाता है कि स्टैक इंस्टेंस पर संचालन अन्य स्टैक सहित किसी अन्य एडीटी इंस्टेंस की स्थिति को संशोधित नहीं करता है। वह है,

  • किसी भी मान x, y और किसी भी विशिष्ट स्टैक S और T के लिए अनुक्रम { push(S, x); push(T, y) } { push(T, y) के बराबर है; push(S, x)}।

अमूर्त स्टैक परिभाषा में सामान्यतः बूलियन मान-मूल्यवान फलन खाली(S) और एक बनाना() ऑपरेशन सम्मिलित होता है। जो स्टैक उदाहरण वापस करता है। इसके समकक्ष स्वयंसिद्धों के साथ व्यवस्थित करता है।

  • create() ≠ S किसी भी पिछले स्टैक के लिए S (एक नया बनाया गया स्टैक पिछले सभी स्टैक से अलग है)।
  • empty(create() नया बनाया गया समूब खाली है।
  • not empty(push(S, x) किसी चीज़ को समूब में धकेलने से वह गैर-रिक्त हो जाती है।

एकल-आवृत्ति शैली

कभी-कभी एडीटी को परिभाषित किया जाता है। जैसे कि एल्गोरिथम के निष्पादन के समय इसका केवल एक उदाहरण उपस्थित था और सभी ऑपरेशन उस उदाहरण पर संचालित किए गए थे। जो स्पष्ट रूप से नोट नहीं किया गया है। उदाहरण के लिए उपरोक्त अमूर्त स्टैक को ऑपरेशन push(x) और pop() के साथ परिभाषित किया जा सकता था। जो केवल उपस्थिता स्टैक पर काम करता है। इस शैली में एडीटी परिभाषाओं को सरलता से एडीटी के कई सह-अस्तित्व वाले उदाहरणों को स्वीकार करने के लिए पुनः लिखा जा सकता है। एक स्पष्ट उदाहरण पैरामीटर (जैसे पिछले उदाहरण में S) को प्रत्येक ऑपरेशन में जोड़ा जाता है। जो अंतर्निहित उदाहरण का उपयोग करता है या संशोधित करता है।

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

कार्यात्मक-शैली परिभाषा

एडीटी को परिभाषित करने का एक और उपाय कार्यात्मक प्रोग्रामिंग की भावना के पास संरचना के प्रत्येक राज्य को अलग इकाई के रूप में माना जाता है। इस दृष्टि से एडीटी को संशोधित करने वाले किसी भी ऑपरेशन को एक फलन (गणित) के रूप में तैयार किया जाता है। जो पुरानी स्थिति को तर्क के रूप में लेता है और परिणाम के भाग के रूप में नया स्थिति देता है। अनिवार्य संचालन के विपरीत इन कार्यों का कोई दुष्प्रभाव (कंप्यूटर विज्ञान) नहीं है। इसलिए जिस क्रम में उनका मूल्यांकन किया जाता है। वह अमूर्तहीन है और समान तर्कों (समान इनपुट राज्यों सहित) पर संचालित समान ऑपरेशन सदैव समान परिणाम (और आउटपुट स्थिति) वापस करेगा।

कार्यात्मक दृश्य में विशेष रूप से अनिवार्य चर के शब्दार्थ के साथ अमूर्त चर को परिभाषित करने का कोई उपाय (या आवश्यकता) नहीं है। (अर्थात, fetch और store संचालन के साथ) मानों को वेरिएबल्स में संग्रहीत करने के अतिरिक्त उन्हें फलन के तर्क के रूप में पास किया जाता है।

उदाहरण: अमूर्त समूह (कार्यात्मक)

उदाहरण के लिए अमूर्त समूह की एक पूर्ण कार्यात्मक-शैली परिभाषा तीन परिचालनों का उपयोग कर सकती है:

  • push: एक स्टैक स्थिति और मान लेता है। एक स्टैक स्थिति लौटाता है।
  • top: एक समूह स्थिति लेता है, एक मान देता है।
  • pop: स्टैक स्थिति लेता है, स्टैक स्थिति लौटाता है।

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

create() के अतिरिक्त अमूर्त स्टैक की कार्यात्मक-शैली परिभाषा विशेष स्टैक स्थिति के अस्तित्व को मान सकती है। खाली स्टैक, जिसे Λ या () जैसे विशेष प्रतीक द्वारा निर्दिष्ट किया जाता है या bottom() ऑपरेशन परिभाषित करें। जो कोई तर्क नहीं लेता है और इस विशेष स्टैक स्थिति को लौटाता है। ध्यान दें कि स्वयंसिद्धों का अर्थ है।

  • push(Λ, x) ≠ Λ.

स्टैक की कार्यात्मक-शैली की परिभाषा में किसी को खाली विधेय की आवश्यकता नहीं होती है। इसके अतिरिक्त कोई यह परीक्षण कर सकता है कि स्टैक खाली है या नहीं। यह परीक्षण करके कि क्या यह Λ के बराबर है।

ध्यान दें कि ये सिद्धांत top(s) या pop(s) के प्रभाव को परिभाषित नहीं करते हैं। जब तक कि s push उपस्थित न हो। चूँकि push स्टैक को गैर-खाली छोड़ देता है। वे दो ऑपरेशन अपरिभाषित हैं। जब s = Λ। दूसरी ओर स्वयंसिद्ध (और साइड इफेक्ट की कमी) का अर्थ है कि push(s, x) = push(t, y) यदि और केवल यदि x = y और s = t।

जैसा कि गणित की कुछ अन्य शाखाओं में होता है। यह मान लेना भी प्रथागत है कि स्टैक अवस्थाएँ केवल वे हैं, जिनका अस्तित्व स्वयंसिद्धों से सीमित संख्या में चरणों में सिद्ध किया जा सकता है। उपरोक्त अमूर्त स्टैक उदाहरण में इस नियम का अर्थ है कि प्रत्येक स्टैक मूल्यों का एक परिमित अनुक्रम है। जो pops की सीमित संख्या के बाद खाली स्टैक (Λ) बन जाता है। स्वयं में ऊपर दिए गए स्वयंसिद्ध अनंत स्टैक के अस्तित्व को प्रत्येक बार नहीं करते हैं (जो सदैव के लिए pop पेड हो सकते हैं, प्रत्येक बार एक अलग स्थिति उत्पन्न करते हैं) या गोलाकार समूह (जो एक परिमित संख्या के बाद उसी स्थिति में वापस आ जाते हैं) विशेष रूप से वे ऐसी स्थिति को उत्पन्न नहीं करते हैं। जैसे pop(s) = s या push(s, x) = s । चूंकि दिए गए कार्यों के साथ ऐसे समूह स्थिति प्राप्त नहीं किए जा सकते हैं। इसलिए उन्हें अस्तित्व में नहीं माना जाता है।

जटिलता सम्मिलित करना है या नहीं

स्वयंसिद्धों के संदर्भ में व्यवहार के अतिरिक्त एडीटी ऑपरेशन की परिभाषा में उनके एल्गोरिदम का विश्लेषण भी सम्मिलित करना संभव है। सी++ मानक टेम्पलेट लाइब्रेरी के प्रारूपर अलेक्जेंडर स्टेपानोव ने तर्क देते हुए एसटीएल विनिर्देशन में जटिलता की गारंटी सम्मिलित की:

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

— अलेक्जेंडर स्टेपानोव[5]


अमूर्त डेटा टाइपिंग के लाभ

एनकैप्सुलेशन

अमूर्तता (कंप्यूटर विज्ञान) प्रतिज्ञा प्रदान करता है कि एडीटी के किसी भी कार्यान्वयन में कुछ गुण और क्षमताएं हैं। एडीटी ऑब्जेक्ट का उपयोग करने के लिए यह जानना आवश्यक है। यह प्रोग्रामिंग भाषा में डेटा प्रकार के साथ परिधीय और गैर परिधीय डेटा प्रकार प्रयोग करने के लिए तैयार है।

परिवर्तन का स्थानीयकरण

एडीटी ऑब्जेक्ट का उपयोग करने वाले कोड को एडीटी के कार्यान्वयन को बदलने पर संपादित करने की आवश्यकता नहीं होगी। चूंकि कार्यान्वयन में कोई भी परिवर्तन अभी भी इंटरफ़ेस का अनुपालन करना चाहिए और चूंकि एडीटी ऑब्जेक्ट का उपयोग करने वाला कोड केवल इंटरफ़ेस में निर्दिष्ट गुणों और क्षमताओं को संदर्भित कर सकता है। कोड में किसी भी बदलाव की आवश्यकता के बिना कार्यान्वयन में परिवर्तन किए जा सकते हैं। जहां एडीटी का उपयोग किया जाता है। .

लचीलापन

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

विशिष्ट संचालन

कुछ ऑपरेशन जो प्रायः एडीटीs (संभवतः अन्य नामों के अनुअमूर्त) के लिए निर्दिष्ट होते हैं

  • compare(s, t), जो परीक्षण करता है कि क्या दो दृष्टान्तों की अवस्थाएँ किसी अर्थ में समान हैं।
  • hash(s), जो उदाहरण की स्थिति से कुछ मानक हैश फंकशन की गणना करता है;
  • print(s)या show(s), जो उदाहरण की स्थिति का मानव-पठनीय प्रतिनिधित्व उत्पन्न करता है।

अनिवार्य-शैली एडीटी परिभाषाओं में प्रायः यह भी पाया जाता है।

  • create(), जो एडीटी का एक नया उदाहरण देता है।
  • initializes(s), जो आगे के संचालन के लिए एक नया बनाया गया उदाहरण तैयार करता है या इसे कुछ प्रारंभिक अवस्था में समुच्चय करता है।
  • copy(s, t), जो उदाहरण s को t के समतुल्य स्थिति में रखती है।
  • clone(t), जो s ← create(), copy(s, t) करता है और s लौटाता है।
  • free(s) या destroy(s), जो s द्वारा उपयोग की गई मेमोरी और अन्य संसाधनों को पुनः प्राप्त करता है।

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

उदाहरण

कुछ सामान्य एडीटी, जो विभिन्न प्रकार के अनुप्रयोगों में उपयोगी सिद्ध हुए हैं, हैं

इन एडीटी में से प्रत्येक को कई तरीकों और रूपों में परिभाषित किया जा सकता है, जरूरी नहीं कि समकक्ष उदाहरण के लिए अमूर्त स्टैक में गिनती ऑपरेशन हो सकता है या नहीं भी हो सकता है। जो बताता है कि कितने आइटम push किए गए हैं और अभी तक pop नहीं हुए हैं। यह विकल्प न केवल इसके ग्राहकों के लिए बल्कि कार्यान्वयन के लिए भी एक अंतर बनाता है।

अमूर्त चित्रमय डेटा प्रकार

1979 में कंप्यूटर ग्राफिक्स के लिए एडीटी का विस्तार प्रस्तावित किया गया था।[6] एक अमूर्त चित्रमय डेटा प्रकार (एजीडीटी) इसे नादिया मैग्नेनेट थल्मन और डेनियल थाल्मन द्वारा प्रस्तुत किया गया था। एजीडीटी एक संरचित प्रकार से ग्राफिकल ऑब्जेक्ट्स बनाने की सुविधा के साथ एडीटी के लाभ प्रदान करते हैं।

कार्यान्वयन

Further information: अपारदर्शी डेटा प्रकार

एडीटी को संचालित करने का अर्थ है प्रत्येक अमूर्त ऑपरेशन के लिए एक सबरूटीन प्रदान करना। एडीटी उदाहरणों को कुछ ठोस डेटा संरचना द्वारा दर्शाया जाता है। जो एडीटी के विनिर्देशों के अनुअमूर्त उन प्रक्रियाओं द्वारा हेरफेर किया जाता है।

सामान्यतः कई अलग-अलग ठोस डेटा संरचनाओं का उपयोग करके एक ही एडीटी को संचालित करने के कई प्रकार हैं। इस प्रकार उदाहरण के लिए अमूर्त समूह को एक लिंक्ड सूची या एक ऐरे डेटा संरचना द्वारा कार्यान्वित किया जा सकता है।

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

एडीटी संचालित करते समय प्रत्येक उदाहरण (अनिवार्य-शैली परिभाषाओं में) या प्रत्येक राज्य (कार्यात्मक-शैली परिभाषाओं में) सामान्यतः किसी प्रकार के हैंडल (कंप्यूटिंग) द्वारा दर्शाया जाता है।[7] आधुनिक वस्तु-उन्मुख भाषाएँ जैसे सी++ और जावा प्रोग्रामिंग भाषा अमूर्त डेटा प्रकारों के एक रूप का समर्थन करती हैं। जब एक वर्ग का उपयोग एक प्रकार के रूप में किया जाता है। तो यह एक अमूर्त प्रकार होता है, जो एक छिपे हुए प्रतिनिधित्व को संदर्भित करता है। इस मॉडल में एडीटी को सामान्यतः एक वर्ग (कंप्यूटर विज्ञान) के रूप में संचालित किया जाता है और एडीटी का प्रत्येक उदाहरण सामान्यतः उस वर्ग का एक ऑब्जेक्ट (कंप्यूटर विज्ञान) होता है। मॉड्यूल का इंटरफ़ेस सामान्यतः निर्माणकर्ताओं को सामान्य प्रक्रियाओं के रूप में घोषित करता है और अधिकांश अन्य एडीटी संचालन उस वर्ग के तरीके (कंप्यूटर प्रोग्रामिंग) के रूप में होते हैं। चूंकि ऐसा दृष्टिकोण एडीटी में पाए जाने वाले कई प्रतिनिधित्वात्मक वेरिएंट को सरलता से एनकैप्सुलेट नहीं करता है। यह वस्तु-उन्मुख कार्यक्रमों की व्यापकता को भी कम कर सकता है। एक शुद्ध वस्तु-उन्मुख कार्यक्रम में जो इंटरफेस को प्रकार के रूप में उपयोग करता है, प्रकार व्यवहार को संदर्भित करता है, परन्तु प्रतिनिधित्व नहीं करता है।

उदाहरण: अमूर्त समूह का कार्यान्वयन एक उदाहरण के रूप में यहाँ सी (प्रोग्रामिंग लैंग्वेज) में उपरोक्त अमूर्त स्टैक का कार्यान्वयन है।

इम्पीरेटिव-स्टाइल इंटरफ़ेस

अनिवार्य-शैली इंटरफ़ेस हो सकता है: 

typedef struct stack_Rep stack_Rep;       // type: stack instance representation (opaque record)
typedef stack_Rep* stack_T;               // type: handle to a stack instance (opaque pointer)
typedef void* stack_Item;                 // type: value stored in stack instance (arbitrary address)

stack_T stack_create(void);               // creates a new empty stack instance
void stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack
stack_Item stack_pop(stack_T s);          // removes the top item from the stack and returns it
bool stack_empty(stack_T s);              // checks whether stack is empty

इस इंटरफ़ेस का उपयोग निम्नलिखित तरीके से किया जा सकता है: 

#include <stack.h>          // includes the stack interface

stack_T s = stack_create(); // creates a new empty stack instance
int x = 17;
stack_push(s, &x);          // adds the address of x at the top of the stack
void* y = stack_pop(s);     // removes the address of x from the stack and returns it
if (stack_empty(s)) { }     // does something if stack is empty

इस इंटरफ़ेस को कई प्रकार से संचालित किया जा सकता है। कार्यान्वयन मनमाने ढंग से अक्षम हो सकता है क्योंकि उपरोक्त एडीटी की औपचारिक परिभाषा निर्दिष्ट नहीं करती है कि समूह कितनी स्थान का उपयोग कर सकता है, न ही प्रत्येक ऑपरेशन में कितना समय लगना चाहिए। यह यह भी निर्दिष्ट नहीं करता है कि कॉल x ← pop(s) के बाद स्टैक स्थिति उपस्थित रहती है या नहीं।

व्यवहार में औपचारिक परिभाषा में यह निर्दिष्ट होना चाहिए कि स्थान धकेले गए आइटमों की संख्या के समानुपाती है और अभी तक pop नहीं हुआ है और ऊपर दिए गए प्रत्येक ऑपरेशन को उस संख्या से स्वतंत्र रूप से निरंतर समय में पूरा करना चाहिए। इन अतिरिक्त विशिष्टताओं का अनुपालन करने के लिए कार्यान्वयन दो पूर्णांकों (एक आइटम संख्या और सरणी आकार) के साथ एक लिंक की गई सूची या अमूर्तणी (गतिशील आकार बदलने के साथ) का उपयोग कर सकता है।







कार्यात्मक-शैली इंटरफ़ेस

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

एडीटी पुस्तकालय

कई आधुनिक प्रोग्रामिंग भाषाएं जैसे कि सी ++ और जावा, मानक पुस्तकालयों के साथ आती हैं। जो कई सामान्य एडीटी को संचालित करती हैं। जैसे ऊपर सूचीबद्ध हैं।

अंतर्निहित अमूर्त डेटा प्रकार

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

यह भी देखें

टिप्पणियाँ

  1. ↑ Compare to the characterization of integers in abstract algebra.


उद्धरण

  1. ↑ Dale & Walker 1996, p. 3.
  2. ↑ Dale & Walker 1996, p. 4.
  3. ↑ Liskov & Zilles 1974.
  4. ↑ Rudolf Lidl (2004). Abstract Algebra. Springer. ISBN 978-81-8128-149-4., Chapter 7, section 40.
  5. ↑ Stevens, Al (March 1995). "Al Stevens Interviews Alex Stepanov". Dr. Dobb's Journal. Retrieved 31 January 2015.
  6. ↑ D. Thalmann, N. Magnenat Thalmann (1979). Design and Implementation of Abstract Graphical Data Types. IEEE. doi:10.1109/CMPSAC.1979.762551., Proc. 3rd International Computer Software and Applications Conference (COMPSAC'79), IEEE, Chicago, USA, pp.519-524
  7. ↑ Robert Sedgewick (1998). Algorithms in C. Addison/Wesley. ISBN 978-0-201-31452-6., definition 4.4.


संदर्भ


अग्रिम पठन


बाप्रत्येकी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=अमूर्त_डेटा_प्रकार&oldid=105343’