सार डेटा प्रकार

Not to be confused with Algebraic data type.

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

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

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

सार डेटा प्रकार

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

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

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

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

परिचय

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

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

एक सार डेटा प्रकार परिभाषित करना

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

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

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

सार चर

एडीटी की अनिवार्य-शैली की परिभाषाएं अक्सर अमूर्त चर की अवधारणा पर निर्भर करती हैं, जिसे सबसे सरल गैर-तुच्छ एडीटी माना जा सकता है। एक अमूर्त चर 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) के बराबर है; स्टोर(यू, एक्स)}।

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

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

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

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

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

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

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

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

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

उदाहरण: सार ढेर (अनिवार्य)

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

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

उस विवशता के साथ

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

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

{ पुश(S, x); पुश(एस, वाई); यू ← पॉप(एस); पुश(S, z); वी ← पॉप(एस); डब्ल्यू ← पॉप(एस)}

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

{ यू ← वाई; वी ← जेड; डब्ल्यू ← एक्स}

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

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

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

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

एक उदाहरण शैली

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

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

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

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

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

उदाहरण: सार ढेर (कार्यात्मक)

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

• push: एक स्टैक स्थिति और मनमाना मान लेता है, एक स्टैक स्थिति लौटाता है;
• शीर्ष: एक ढेर स्थिति लेता है, एक मान देता है;
• पॉप: स्टैक स्थिति लेता है, स्टैक स्थिति लौटाता है।

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

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

• पुश(Λ, x) ≠ Λ.

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

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

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

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

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

The reason for introducing the notion of abstract data types was to allow interchangeable software modules. You cannot have interchangeable modules unless these modules share similar complexity behavior. If I replace one module with another module with the same functional behavior but with different complexity tradeoffs, the user of this code will be unpleasantly surprised. I could tell him anything I like about data abstraction, and he still would not want to use the code. Complexity assertions have to be part of the interface.

— Alexander Stepanov

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

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

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

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

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

लचीलापन

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

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

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

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

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

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

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

उदाहरण

कुछ सामान्य ADT, जो विभिन्न प्रकार के अनुप्रयोगों में उपयोगी साबित हुए हैं, हैं

• संग्रह (सार डेटा प्रकार)
• कंटेनर (सार डेटा प्रकार)
• सूची (सार डेटा प्रकार)
• स्ट्रिंग (कंप्यूटर विज्ञान)
• सेट (सार डेटा प्रकार)
• मल्टीसेट
• सहयोगी सरणी
• मल्टीमैप
• ग्राफ (सार डेटा प्रकार)
• ट्री (डेटा संरचना)
• ढेर (सार डेटा प्रकार)
• कतार (सार डेटा प्रकार)
• प्राथमिकता कतार
• डबल-एंडेड कतार
• डबल-एंडेड प्राथमिकता कतार

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

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

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

कार्यान्वयन

Further information: Opaque data type

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

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

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

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

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

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

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

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) के बाद स्टैक स्थिति मौजूद रहती है या नहीं।

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

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

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

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

stack_T stack_empty(void);                   // returns the empty stack state
stack_T stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack state and returns the resulting stack state
stack_T stack_pop(stack_T s);                // removes the top item from the stack state and returns the resulting stack state
stack_Item stack_top(stack_T s);             // returns the top item of the stack state

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

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

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

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

यह भी देखें

• संकल्पना (जेनेरिक प्रोग्रामिंग)
• औपचारिक तरीके
• कार्यात्मक विनिर्देश
• सामान्यीकृत बीजगणितीय डेटा प्रकार
• प्रारंभिक बीजगणित
• लिस्कोव प्रतिस्थापन सिद्धांत
• सिद्धांत टाइप करें
• दीवारें और दर्पण

संदर्भ

• Liskov, Barbara; Zilles, Stephen (1974). "Programming with abstract data types". Proceedings of the ACM SIGPLAN Symposium on Very High Level Languages. SIGPLAN Notices. Vol. 9. pp. 50–59. CiteSeerX 10.1.1.136.3043. doi:10.1145/800233.807045.
• Dale, Nell; Walker, Henry M. (1996). Abstract Data Types: Specifications, Implementations, and Applications. Jones & Bartlett Learning. ISBN 978-0-66940000-7.

अग्रिम पठन

• Mitchell, John C.; Plotkin, Gordon (July 1988). "Abstract Types Have Existential Type" (PDF). ACM Transactions on Programming Languages and Systems. 10 (3): 470–502. doi:10.1145/44501.45065. S2CID 1222153. Archived (PDF) from the original on 2022-10-09.

बाहरी संबंध

• Media related to Abstract data types at Wikimedia Commons
• Abstract data type in NIST Dictionary of Algorithms and Data Structures