بنية البيانات

في علم الحاسوب ، تُعرَّف بنية البيانات بأنها طريقة لتنظيم البيانات وتخزينها ، وتُختار عادةً لضمان الوصول الفعال إليها. ^{[ 1 ] [ 2 ] [ 3 ]} وبشكل أدق، تُعرَّف بنية البيانات بأنها التنفيذ المادي لنوع البيانات ، بما في ذلك مواصفات تنظيم البيانات وتنسيق تخزينها، بالإضافة إلى الدوال أو العمليات اللازمة للتعامل مع هذه البيانات. وترتبط بنى البيانات ارتباطًا وثيقًا بأنواع البيانات المجردة (ADTs). ^{[ 4 ]} تصف بنية البيانات تمثيل البيانات في الذاكرة وكيفية تنفيذ العمليات، بينما يصف نوع البيانات المجرد الشكل المنطقي أو البنية الجبرية لنوع البيانات - أي العمليات المسموح بها والنتائج التي تُنتجها - دون وصف كيفية تنفيذ هذه العمليات. ^{[ 4 ]} ولا يستخدم بعض المؤلفين مصطلح "نوع البيانات المجرد"، بل يشيرون ببساطة إلى الشكلين المنطقي والمادي لبنية البيانات. ^{[ 5 ]}

تُعدّ هياكل البيانات الفعّالة ضرورية لإدارة مجموعات البيانات الضخمة، وهي أساسية لتصميم الخوارزميات. تستخدم قواعد البيانات العلائقية عادةً فهرس شجرة B لاسترجاع البيانات، ^{[ 6 ]} بينما تستخدم تطبيقات المترجمات عادةً جداول التجزئة للبحث عن المعرّفات . ^{[ 7 ]} وتعتمد أنظمة الملفات ومحركات البحث بشكل كبير على هياكل البيانات المتخصصة. ^{[ 8 ] [ 9 ]} وقد ذكر روب بايك أن اختيار هيكل البيانات غالبًا ما يكون له تأثير أكبر على الكفاءة من اختيار الخوارزمية، لأن الخوارزمية غالبًا ما تكون بديهية. ^{[ 10 ]} تُستخدم هياكل البيانات لتنظيم البيانات في كل من الذاكرة الرئيسية ( RAM ) والتخزين الثانوي (مثل الأقراص). ^{[ 11 ]}

يتضمن تنفيذ بنية بيانات كتابة مجموعة من الإجراءات الفرعية - مثل الإضافة والحذف والتنقل والبحث - التي تُنشئ وتُعالج نسخًا من تلك البنية. يمكن تنفيذ هياكل البيانات باستخدام مجموعة متنوعة من لغات البرمجة والتقنيات. تتوافق بنية البيانات مباشرةً مع تنفيذ ملموس واحد، على عكس نوع البيانات المجرد (ADT) الذي يصف السلوك والعمليات بشكل مستقل عن أي تنفيذ محدد. قد توجد هياكل بيانات ملموسة متعددة لنفس نوع البيانات المجرد، على سبيل المثال، قائمة مرتبطة أو مصفوفة قابلة لتغيير الحجم لنوع بيانات القائمة المجرد. ^{[ 12 ]} ولذلك، ترتبط كفاءة بنية البيانات ارتباطًا وثيقًا بتنفيذها الملموس، ويجب تقييمها من خلال معايير الأداء والمحاكاة النظرية. ^{[ 13 ]}

تعتمد هياكل البيانات عمومًا على قدرة الحاسوب على تخزين البيانات والوصول إليها عبر عناوين الذاكرة (كما هو محدد بواسطة مؤشر - سلسلة بتات - أو بشكل أكثر تجريدًا عبر المراجع ) التي يمكن تخزينها في الذاكرة ومعالجتها بواسطة البرنامج. على سبيل المثال، تخزن المصفوفات والسجلات العناصر في مواقع ذاكرة متجاورة، مما يتطلب تخطيطًا ثابتًا ولكنه يسمح بالوصول السريع المفهرس عن طريق حساب العنوان من خلال العمليات الحسابية . في المقابل، تخزن هياكل البيانات المرتبطة (مثل القوائم المرتبطة والأشجار) عناوين العناصر ذات الصلة داخل بنيتها، مما يتيح استخدامًا مرنًا للذاكرة وتغييرًا ديناميكيًا في حجمها. تأتي هذه الطرق المختلفة لهيكلة البيانات بمقايضات مختلفة وتناسب مهامًا مختلفة. على سبيل المثال، يسهل تخصيص الذاكرة المتجاورة في المصفوفات عمليات الوصول والتعديل السريعة، مما يؤدي إلى أداء مُحسَّن في سيناريوهات معالجة البيانات المتسلسلة. ^{[ 14 ]}

توجد أنواع عديدة من هياكل البيانات، والتي تُبنى عمومًا على أنواع بيانات أولية أبسط . ومن الأمثلة المعروفة: ^{[ 15 ]}

• المصفوفة عبارة عن مجموعة من العناصر مرتبة بترتيب محدد، وعادةً ما تكون جميعها من نفس النوع (بحسب لغة البرمجة، قد يُفرض على جميع العناصر أن تكون من نفس النوع، أو قد تكون من أي نوع تقريبًا). يتم الوصول إلى العناصر باستخدام فهرس عددي لتحديد العنصر المطلوب. عادةً ما تُخصص كلمات ذاكرة متجاورة لعناصر المصفوفات (لكن هذا ليس شرطًا دائمًا). قد تكون المصفوفات ثابتة الطول أو قابلة لتغيير الحجم.
• القائمة المتصلة (وتُسمى أيضًا القائمة فقط ) هي مجموعة خطية من عناصر البيانات من أي نوع، تُسمى عُقدًا، حيث تحتوي كل عقدة على قيمة خاصة بها، وتشير إلى العقدة التالية في القائمة المتصلة. الميزة الرئيسية للقائمة المتصلة على المصفوفة هي إمكانية إضافة القيم وإزالتها بكفاءة عالية دون الحاجة إلى إعادة ترتيب باقي عناصر القائمة. مع ذلك، فإن بعض العمليات الأخرى، مثل الوصول العشوائي إلى عنصر معين، تكون أبطأ في القوائم منها في المصفوفات.
• السجل (ويُسمى أيضًا صفًا أو بنية ) هو بنية بيانات مُجمّعة . السجل عبارة عن قيمة تحتوي على قيم أخرى، عادةً بعدد وتسلسل ثابتين، ويتم فهرستها عادةً بالأسماء. تُسمى عناصر السجلات عادةً بالحقول أو الأعضاء . في سياق البرمجة كائنية التوجه ، تُعرف السجلات باسم هياكل البيانات التقليدية لتمييزها عن الكائنات. ^{[ 16 ]}
• جداول التجزئة ، والمعروفة أيضًا باسم خرائط التجزئة، هي هياكل بيانات توفر استرجاعًا سريعًا للقيم بناءً على المفاتيح. تستخدم هذه الجداول دالة تجزئة لربط المفاتيح بالفهارس في مصفوفة، مما يسمح بالوصول في وقت ثابت في المتوسط. تُستخدم جداول التجزئة بشكل شائع في القواميس، وذاكرة التخزين المؤقت، وفهرسة قواعد البيانات. مع ذلك، قد تحدث تصادمات في التجزئة، مما قد يؤثر على أدائها. تُستخدم تقنيات مثل التسلسل والعنونة المفتوحة لمعالجة هذه التصادمات.
• الرسوم البيانية عبارة عن مجموعات من العقد المتصلة بالحواف، تمثل العلاقات بين الكيانات. يمكن استخدام الرسوم البيانية لنمذجة الشبكات الاجتماعية، وشبكات الحاسوب، وشبكات النقل، وغيرها. تتكون الرسوم البيانية من رؤوس (عقد) وحواف (روابط بين العقد). قد تكون الرسوم البيانية موجهة أو غير موجهة، وقد تحتوي على دورات أو لا تحتوي عليها. تشمل خوارزميات اجتياز الرسوم البيانية البحث بالعرض أولاً والبحث بالعمق أولاً.
• تُعدّ المكدسات والطوابير أنواع بيانات مجردة يمكن تمثيلها باستخدام المصفوفات أو القوائم المتصلة. للمكدس عمليتان أساسيتان: الدفع (إضافة عنصر إلى أعلى المكدس) والسحب (إزالة العنصر العلوي من المكدس)، وتتبعان مبدأ "آخر ما يدخل، أول ما يخرج" (LIFO). أما الطوابير، فلها عمليتان أساسيتان: الإضافة (إضافة عنصر إلى نهاية الطابور) والإزالة (إزالة عنصر من بداية الطابور)، وتتبعان مبدأ "أول ما يدخل، أول ما يخرج" (FIFO).
• تمثل الأشجار تنظيمًا هرميًا للعناصر. تتكون الشجرة من عقد متصلة بحواف، حيث تمثل إحدى العقد الجذر، بينما تشكل جميع العقد الأخرى أشجارًا فرعية. تُستخدم الأشجار على نطاق واسع في مختلف الخوارزميات وسيناريوهات تخزين البيانات. تُعد الأشجار الثنائية (وخاصة الأكوام )، وأشجار AVL ، وأشجار B من الأنواع الشائعة للأشجار. فهي تُمكّن من البحث والفرز والتمثيل الهرمي للبيانات بكفاءة وفعالية.
• شجرة التراي ، أو شجرة البادئات، هي نوع خاص من الأشجار يُستخدم لاسترجاع السلاسل النصية بكفاءة. في شجرة التراي، يُمثل كل عقد حرفًا من السلسلة النصية، وتمثل الحواف بين العقد الأحرف التي تربطها. يُعد هذا الهيكل مفيدًا بشكل خاص لمهام مثل الإكمال التلقائي، والتدقيق الإملائي، وإنشاء القواميس. تُتيح أشجار التراي إجراء عمليات بحث وعمليات سريعة بناءً على بادئات السلاسل النصية.

تفتقر معظم لغات التجميع وبعض اللغات منخفضة المستوى ، مثل لغة البرمجة الأساسية المدمجة ( BCPL )، إلى دعم مدمج لهياكل البيانات. في المقابل، تتمتع العديد من لغات البرمجة عالية المستوى وبعض لغات التجميع عالية المستوى، مثل MASM ، ببنية خاصة أو دعم مدمج لهياكل بيانات معينة، مثل السجلات والمصفوفات. على سبيل المثال، تدعم لغتا C (المشتقة مباشرة من BCPL) وباسكال الهياكل والسجلات على التوالي، بالإضافة إلى المتجهات ( المصفوفات أحادية البعد ) والمصفوفات متعددة الأبعاد. ^{[ 17 ] [ 18 ]}

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

تدعم اللغات الحديثة عمومًا البرمجة المعيارية ، أي الفصل بين واجهة وحدة المكتبة وتنفيذها. وتوفر بعضها أنواع بيانات مبهمة تسمح للمستخدمين بإخفاء تفاصيل التنفيذ. وتستخدم لغات البرمجة كائنية التوجه ، مثل C++ و Java و Smalltalk ، عادةً الفئات لهذا الغرض.

تتمتع العديد من هياكل البيانات المعروفة بإصدارات متزامنة تسمح لعدة خيوط حسابية بالوصول إلى نسخة واحدة محددة من هيكل البيانات في وقت واحد. ^{[ 19 ]}

• بيتر براس، هياكل البيانات المتقدمة ، مطبعة جامعة كامبريدج ، 2008، رقم ISBN 978-0521880374
• دونالد كنوث ، فن برمجة الحاسوب ، المجلد 1. أديسون-ويسلي ، الطبعة الثالثة، 1997، رقم ISBN 978-0201896831
• دينش ميهتا وسارتاج ساهني ، دليل هياكل البيانات وتطبيقاتها ، تشابمان آند هول / سي آر سي برس ، 2004، رقم ISBN 1584884355
• نيكلاوس ويرث ، الخوارزميات وهياكل البيانات ، برنتيس هول ، 1985، رقم ISBN 978-0130220059

• هياكل البيانات المفتوحة بقلم بات مورين
• جي إتش جونيت و آر. بايزا-ياتس ، دليل الخوارزميات وهياكل البيانات - بلغة باسكال وسي ، الطبعة الثانية، أديسون-ويسلي، 1991، رقم ISBN 0-201-41607-7
• إليس هورويتز وسارتاج ساهني، أساسيات هياكل البيانات في لغة باسكال ، دار نشر علوم الحاسوب ، 1984، رقم ISBN 0-914894-94-3

• أوصاف من قاموس الخوارزميات وهياكل البيانات
• دورة هياكل البيانات
• دراسة هياكل البيانات من منظور .NET
• شافر، سي. هياكل البيانات وتحليل الخوارزميات