نوع البيانات المجردة

انطلاقًا من مبادئ البرمجة الوظيفية ، تُعتبر كل حالة من حالات بنية البيانات المجردة كيانًا أو قيمة مستقلة. في هذا السياق، تُنمذج كل عملية كدالة رياضية دون أي آثار جانبية . تُنمذج العمليات التي تُعدّل بنية البيانات المجردة كدوال تأخذ الحالة القديمة كمعامل وتُعيد الحالة الجديدة كجزء من النتيجة. لا يُهم ترتيب تقييم العمليات، فالعملية نفسها المطبقة على نفس المعاملات (بما في ذلك حالات الإدخال نفسها) ستُعيد دائمًا نفس النتائج (وحالات الإخراج). تُحدد القيود كمسلمات أو قوانين جبرية يجب أن تُحققها العمليات.

انطلاقًا من مبدأ البرمجة الإجرائية ، يُنظر إلى بنية البيانات المجردة على أنها كيان قابل للتغيير ، أي أنها تخضع لمفهوم الزمن، وقد تكون في حالات مختلفة في أوقات مختلفة. تُغير العمليات حالة بنية البيانات المجردة بمرور الوقت؛ لذا، يُعد ترتيب تنفيذ العمليات مهمًا، وقد يكون للعملية نفسها على الكيانات نفسها تأثيرات مختلفة إذا نُفذت في أوقات مختلفة. يُشابه هذا تعليمات الحاسوب أو أوامر وإجراءات لغة البرمجة الإجرائية. ولتأكيد هذا، يُقال عادةً إن العمليات تُنفذ أو تُطبق ، بدلًا من تقييمها ، على غرار أسلوب البرمجة الإجرائية المُستخدم غالبًا عند وصف الخوارزميات المجردة. وعادةً ما تُحدد القيود كتابيًا.

غالباً ما تقتصر عروض أنظمة البيانات الآلية (ADTs) على العمليات الرئيسية فقط. أما العروض الأكثر شمولاً فتتضمن عادةً عمليات إضافية على أنظمة البيانات الآلية، مثل:

• create()، مما ينتج عنه نسخة جديدة من نوع البيانات المجردة (ADT)؛
• compare(s, t)، الذي يختبر ما إذا كانت حالات مثيلين متكافئة بمعنى ما؛
• hash(s)، والتي تحسب دالة تجزئة قياسية من حالة المثيل؛
• print(s)أو show(s)، الذي ينتج تمثيلاً قابلاً للقراءة البشرية لحالة المثال.

هذه الأسماء توضيحية وقد تختلف بين المؤلفين. في تعريفات أنواع البيانات المجردة ذات النمط الإجرائي، نجد غالبًا أيضًا ما يلي:

• initialize(s)، الذي يهيئ نسخة تم إنشاؤها حديثًا sلمزيد من العمليات، أو يعيد ضبطها إلى "حالة أولية" ما؛
• copy(s)، مما يضع المثال sفي حالة مكافئة لحالة t؛
• clone(t)، الذي يقوم بـ s← create()، copy(s, t)، ويعيد s؛
• free(s)أو destroy(s)، الذي يستعيد الذاكرة والموارد الأخرى المستخدمة بواسطة s.

لا تُعدّ هذه freeالعملية عادةً ذات صلة أو معنى، لأنّ أنواع البيانات المجردة (ADTs) كيانات نظرية لا "تستخدم الذاكرة". مع ذلك، قد يكون من الضروري استخدامها عند الحاجة إلى تحليل مساحة التخزين التي تستخدمها خوارزمية تستخدم نوع البيانات المجردة. في هذه الحالة، يلزم وجود بديهيات إضافية تُحدّد مقدار الذاكرة التي يستخدمها كل مثيل من أنواع البيانات المجردة، كدالة لحالته، ومقدار الذاكرة التي يُعيدها إلى مجمع الذاكرة free.

غالبًا ما يُقيّد تعريف نوع البيانات المجردة (ADT) القيم المخزنة لمثيلاته، بحيث تقتصر على عناصر مجموعة محددة X تُسمى نطاق تلك المتغيرات. على سبيل المثال، قد يُقيّد متغير مجرد لتخزين الأعداد الصحيحة فقط. وكما هو الحال في لغات البرمجة، قد تُسهّل هذه القيود وصف الخوارزميات وتحليلها ، وتُحسّن من سهولة قراءتها.

في أسلوب التشغيل، غالبًا ما يكون من غير الواضح كيفية التعامل مع حالات متعددة، وما إذا كان تعديل حالة واحدة قد يؤثر على الحالات الأخرى. يُعرّف أسلوب شائع لأنواع البيانات المجردة (ADTs) العمليات كما لو كانت حالة واحدة فقط موجودة أثناء تنفيذ الخوارزمية، وتُطبّق جميع العمليات على تلك الحالة. على سبيل المثال، قد تحتوي مكدسة على العمليتين push( x ) و pop()، اللتين تعملان على المكدسة الوحيدة الموجودة. يمكن إعادة كتابة تعريفات أنواع البيانات المجردة بهذا الأسلوب بسهولة للسماح بوجود حالات متعددة متزامنة من نوع البيانات المجردة، وذلك بإضافة مُعامل حالة صريح (مثل S في مثال المكدسة أدناه) إلى كل عملية تستخدم أو تُعدّل الحالة الضمنية. لا يمكن تعريف بعض أنواع البيانات المجردة تعريفًا ذا معنى دون السماح بوجود حالات متعددة، على سبيل المثال عندما تأخذ عملية واحدة حالتين مختلفتين من نوع البيانات المجردة كمعاملات، مثل unionعملية على مجموعات أو compareعملية على قوائم.

يُدمج أسلوب تعدد الحالات أحيانًا مع مبدأ التداخل ، أي أن نتيجة الدالة create() تختلف عن أي حالة يستخدمها الخوارزمية بالفعل. قد تُعيد تطبيقات أنواع البيانات المجردة استخدام الذاكرة وتسمح لتطبيقات الدالة create() بإنتاج حالة مُنشأة مسبقًا؛ ومع ذلك، فإن تحديد ما إذا كانت هذه الحالة "مُعاد استخدامها" يُعد أمرًا صعبًا في شكلية أنواع البيانات المجردة.

بشكلٍ أعم، يمكن تعزيز هذه البديهية لاستبعاد التداخل الجزئي مع حالات أخرى، بحيث يُفترض أن أنواع البيانات المجردة المركبة (مثل الأشجار أو السجلات) وأنواع البيانات المجردة المرجعية (مثل المؤشرات) منفصلة تمامًا. على سبيل المثال، عند توسيع تعريف متغير مجرد ليشمل السجلات المجردة ، فإن العمليات على الحقل F لمتغير سجل R تتضمن بوضوح F ، وهو حقل منفصل عن R ولكنه جزء منه . تنص بديهية التداخل الجزئي على أن تغيير حقل في متغير سجل واحد لا يؤثر على أي سجلات أخرى.

يُدرج بعض المؤلفين أيضًا التعقيد الحسابي ("التكلفة") لكل عملية، سواءً من حيث الوقت (لعمليات الحساب) أو المساحة (لتمثيل القيم)، للمساعدة في تحليل الخوارزميات . على سبيل المثال، يمكن تحديد أن كل عملية تستغرق نفس الوقت وأن كل قيمة تشغل نفس المساحة بغض النظر عن حالة نوع البيانات المجرد (ADT)، أو أن هناك "حجمًا" لنوع البيانات المجرد وأن العمليات خطية أو تربيعية، وما إلى ذلك، بالنسبة لحجم نوع البيانات المجرد. وقد أدرج ألكسندر ستيبانوف ، مصمم مكتبة القوالب القياسية للغة C++ ، ضمانات التعقيد في مواصفات STL، مُبررًا ذلك بما يلي:

كان الهدف من إدخال مفهوم أنواع البيانات المجردة هو السماح بتبادل وحدات البرمجيات. لا يمكن أن تكون الوحدات قابلة للتبادل إلا إذا كانت تتشارك سلوكًا مشابهًا من حيث التعقيد. إذا استبدلتُ وحدةً بأخرى لها نفس السلوك الوظيفي ولكن بمفاضلات مختلفة في التعقيد، فسيتفاجأ مستخدم هذا الكود سلبًا. حتى لو شرحتُ له أي شيء عن تجريد البيانات، فلن يرغب في استخدام الكود. يجب أن تكون تأكيدات التعقيد جزءًا من واجهة المستخدم.

ويخالف مؤلفون آخرون هذا الرأي، بحجة أن نوع البيانات المجردة للمكدس هو نفسه سواء تم تنفيذه باستخدام قائمة مرتبطة أو مصفوفة، على الرغم من اختلاف تكاليف التشغيل، وأن مواصفات نوع البيانات المجردة يجب أن تكون مستقلة عن التنفيذ.

يمكن اعتبار المتغير المجرد أبسط أنواع البيانات المجردة غير التافهة، وله دلالات المتغير الإجرائي. وهو يقبل عمليتين، fetchو store. غالبًا ما تُكتب التعريفات الإجرائية بدلالة المتغيرات المجردة. في الدلالات البديهية، يكون${\displaystyle V}$أن يكون نوع المتغير المجرد و${\displaystyle X}$يكون نوع محتوياته fetchدالة${\displaystyle V\to X}$وهي storeدالة من النوع${\displaystyle V\times X\to V}$الشرط الرئيسي هو أن fetchتُعيد الدالة دائمًا القيمة x المستخدمة في آخر storeعملية على نفس المتغير V ، أي fetch(store(V,x)) = xx = 0. قد نشترط أيضًا أن storeتُستبدل القيمة بالكامل store(store(V,x1),x2) = store(V,x2).

في دلالات العمليات، يُمثل fetch( V ) إجراءً يُعيد القيمة الحالية في الموقع V ، بينما يُمثل store( V , x ) إجراءً من voidنوع إرجاع يُخزن القيمة x في الموقع V. وتُوصَف القيود بشكل غير رسمي بأن عمليات القراءة تتوافق مع عمليات الكتابة. وكما هو الحال في العديد من لغات البرمجة، غالبًا ما تُكتب العملية 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 ); store( U , x ) }.

لا يُشير هذا التعريف إلى نتيجة تقييم fetch( V ) عندما تكون V غير مُهيأة ، أي قبل إجراء أي storeعملية عليها . يمكن منع جلب البيانات قبل تخزينها، أو تحديد نتيجة معينة لها، أو تركها غير مُحددة. توجد بعض الخوارزميات التي تعتمد كفاءتها على افتراض أن هذا الإجراء fetchقانوني، وتُعيد قيمة عشوائية ضمن نطاق المتغير.

المكدس المجرد هو بنية بيانات تُدخل فيها البيانات أولاً، وتُعرَّف عمومًا بثلاث عمليات رئيسية: pushإدخال عنصر بيانات إلى المكدس، popوإزالة عنصر بيانات منه، peekوالوصول topإلى عنصر بيانات في أعلى المكدس دون إزالته. يتضمن تعريف المكدس المجرد الكامل أيضًا دالة منطقيةempty ( S ) وعملية create() تُعيد نسخة أولية من المكدس.

في علم الدلالة البديهية، السماح${\displaystyle S}$أن يكون نوع حالات المكدس و${\displaystyle X}$قد تكون أنواع القيم الموجودة في المكدس هي${\displaystyle push:S\to X\to S}$،${\displaystyle pop:S\to (S,X)}$،${\displaystyle top:S\to X}$،${\displaystyle create:S}$، و${\displaystyle empty:S\to \mathbb {B} }$في الدلالات البديهية، يُعد إنشاء المكدس الأولي عملية "بسيطة"، ويعيد دائمًا نفس الحالة المميزة. لذلك، غالبًا ما يُشار إليه برمز خاص مثل Λ أو "()". emptyويمكن كتابة مُسند العملية ببساطة على النحو التالي:${\displaystyle s=\Lambda }$أو${\displaystyle s\neq \Lambda }$.

تكون القيود كما يلي pop(push(S,v))=(S,v): top(push(S,v))=v[ ^{9 ]} ( ) = T (المكدس المُنشأ حديثًا فارغ)، ⁽ ( S , x ) ) = F (إضافة عنصر إلى المكدس تجعله غير فارغ). لا تُحدد هذه البديهيات تأثير ( s ) أو ( s )، إلا إذا كانت s حالة مكدس مُعادة من دالة . بما أن ( s) تجعل المكدس غير فارغ، يُمكن تعريف هاتين العمليتين على أنهما غير صالحتين عندما s = Λ. من هذه البديهيات (وعدم وجود آثار جانبية)، يُمكن استنتاج أن (Λ, x ) ≠ Λ. أيضًا، ( s , x ) = ( t , y ) إذا وفقط إذا كان x = y و s = t .emptycreateemptypushtoppoppushpushpushpushpush

كما هو الحال في بعض فروع الرياضيات الأخرى، من المعتاد افتراض أن حالات المكدس هي فقط تلك التي يمكن إثبات وجودها من البديهيات في عدد محدود من الخطوات. في هذه الحالة، يعني ذلك أن كل مكدس هو سلسلة منتهية من القيم، تصبح مكدسًا فارغًا (Λ) بعد عدد محدود من popالخطوات. لا تستبعد البديهيات المذكورة أعلاه، في حد ذاتها، وجود مكدسات لانهائية (يمكن popتكرارها إلى ما لا نهاية، وفي كل مرة تُنتج حالة مختلفة) أو مكدسات دائرية (تعود إلى الحالة نفسها بعد عدد محدود من popالخطوات). على وجه الخصوص، لا تستبعد هذه البديهيات الحالات s التي يكون فيها pop( s ) = s أو push( s , x ) = s لبعض قيم x . ومع ذلك، بما أنه لا يمكن الحصول على مثل هذه الحالات من حالة المكدس الأولية بالعمليات المعطاة، يُفترض أنها "غير موجودة".

في التعريف العملي للمكدس المجرد، لا تُرجع الدالة push( S , 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 ) }.

ومن الأمثلة الأكثر تعقيدًا تسلسل Boom الهرمي لأنواع البيانات المجردة: الشجرة الثنائية، والقائمة، والحقيبة، والمجموعة. [ 10 ] يمكن تعريف جميع أنواع ^{البيانات هذه بثلاث} عمليات: null ، التي تُنشئ حاوية فارغة؛ وsingle ، التي تُنشئ حاوية من عنصر واحد؛ و append ، التي تجمع حاويتين من النوع نفسه. ويمكن بعد ذلك تحديد المواصفات الكاملة لأنواع البيانات الأربعة بإضافة القواعد التالية تباعًا على هذه العمليات:

يمثل الصفر الحياد الأيسر والأيمن للشجرة	append(null,A) = A, append(A,null) = A.
تُضاف القوائم التي تُلحق البيانات التي تكون ترابطية	append(append(A,B),C) = append(A,append(B,C)).
تُضفي الحقائب سهولة التنقل	append(B,A) = append(A,B).
وأخيرًا، المجموعات أيضًا متطابقة	append(A,A) = A.

يمكن تحديد الوصول إلى البيانات عن طريق مطابقة الأنماط عبر العمليات الثلاث، على سبيل المثال دالة عضوية لهذه الحاويات بواسطة:

member(X,single(Y)) = eq(X,Y)

member(X,null) = false

member(X,append(A,B)) = or(member(X,A), member(X,B))

يجب توخي الحذر لضمان ثبات الدالة وفقًا للقواعد ذات الصلة بنوع البيانات. ضمن كل فئة من فئات التكافؤ التي تنطوي عليها المجموعة الفرعية المختارة من المعادلات، يجب أن تعطي الدالة النتيجة نفسها لجميع عناصرها.

بعض أنواع البيانات المجردة الشائعة، والتي أثبتت فائدتها في مجموعة كبيرة ومتنوعة من التطبيقات، هي

يمكن تعريف كل نوع من أنواع البيانات المجردة هذه بطرق وصيغ متعددة، وليست بالضرورة متكافئة. على سبيل المثال، قد يحتوي مكدس مجرد على countعملية تُحدد عدد العناصر التي تم إضافتها ولم يتم إزالتها بعد، أو قد لا يحتوي عليها. هذا الاختيار يُحدث فرقًا ليس فقط بالنسبة للمستخدمين، بل أيضًا بالنسبة للتنفيذ.

نوع بيانات رسومي مجرد

في عام 1979، تم اقتراح امتداد لأنواع البيانات المجردة (ADT) في مجال رسومات الحاسوب، وهو نوع بيانات رسومي مجرد (AGDT). ^{[ 11 ]} وقد قدمه كل من نادية ماغنانات تالمان ودانيال تالمان . توفر أنواع البيانات الرسومية المجردة مزايا أنواع البيانات المجردة مع إمكانية إنشاء كائنات رسومية بطريقة منظمة.

كمثال على ذلك، إليك تطبيق للمكدس المجرد أعلاه بلغة البرمجة C.

// النوع: تمثيل مثيل المكدس (سجل مبهم) typedef struct { // التنفيذ هنا } Stack ;// النوع: قيمة مخزنة في مثيل مكدس (عنوان عشوائي) typedef void * Item ;// ينشئ نسخة جديدة فارغة من المكدس Stack * stack_create ( void );// يضيف عنصرًا في أعلى المكدس void stack_push ( Stack * s , Item x );// يزيل العنصر العلوي من المكدس ويعيده Item stack_pop ( Stack * s );// يتحقق مما إذا كانت المكدسة فارغة bool stack_is_empty ( Stack * s );

#include <stack.h>int main () { Stack * s = stack_create (); // إنشاء نسخة جديدة فارغة من المكدس int x = 17 ;// يضيف عنوان x في أعلى المكدس stack_push ( s , & x ); // يزيل عنوان x من المكدس ويعيده Item y = stack_pop ( s );if ( stack_is_empty ( s )) { // يقوم بشيء ما إذا كانت المكدسة فارغة printf ( "المكدسة فارغة!" ); } }

// النوع: تمثيل مثيل المكدس (سجل مبهم) typedef struct { // التنفيذ هنا } Stack ;// النوع: قيمة مخزنة في مثيل مكدس (عنوان عشوائي) typedef void * Item ;// تُعيد حالة المكدس الفارغ Stack * stack_is_empty ( void );// يضيف عنصرًا في أعلى حالة المكدس ويعيد حالة المكدس الناتجة Stack * stack_push ( Stack * s , Item x );// يزيل العنصر العلوي من حالة المكدس ويعيد حالة المكدس الناتجة Stack * stack_pop ( Stack * s );// تُعيد العنصر العلوي من حالة المكدس Item stack_top ( Stack * s );