هيكل البيانات

في علوم الكمبيوتر ، بنية البيانات هي تنسيق لتنظيم البيانات وتخزينها والذي يتم اختياره عادةً للوصول الفعال إلى البيانات. ^{[1] [2] [3]} وبشكل أكثر دقة، بنية البيانات هي مجموعة من قيم البيانات، والعلاقات بينها، والوظائف أو العمليات التي يمكن تطبيقها على البيانات، ^[4] أي أنها بنية جبرية حول البيانات .

تعمل هياكل البيانات كأساس لأنواع البيانات المجردة (ADT). تحدد أنواع البيانات المجردة الشكل المنطقي لنوع البيانات. تنفذ بنية البيانات الشكل المادي لنوع البيانات . ^[5]

تتناسب أنواع مختلفة من هياكل البيانات مع أنواع مختلفة من التطبيقات، وبعضها متخصص للغاية في مهام محددة. على سبيل المثال، تستخدم قواعد البيانات العلائقية عادةً فهرس شجرة B لاسترجاع البيانات، ^[6] بينما تستخدم تطبيقات المترجم عادةً جداول التجزئة للبحث عن المعرفات . ^[7]

توفر هياكل البيانات وسيلة لإدارة كميات كبيرة من البيانات بكفاءة لاستخدامات مثل قواعد البيانات الكبيرة وخدمات فهرسة الإنترنت. عادةً، تكون هياكل البيانات الفعّالة هي المفتاح لتصميم خوارزميات فعّالة . تؤكد بعض طرق التصميم الرسمية ولغات البرمجة على هياكل البيانات، بدلاً من الخوارزميات، كعامل تنظيمي رئيسي في تصميم البرامج. يمكن استخدام هياكل البيانات لتنظيم تخزين واسترجاع المعلومات المخزنة في كل من الذاكرة الرئيسية والذاكرة الثانوية . ^[8]

يمكن تنفيذ هياكل البيانات باستخدام مجموعة متنوعة من لغات البرمجة والتقنيات، لكنها جميعًا تشترك في الهدف المشترك المتمثل في تنظيم البيانات وتخزينها بكفاءة. ^[9] تعتمد هياكل البيانات بشكل عام على قدرة الكمبيوتر على جلب البيانات وتخزينها في أي مكان في ذاكرته، ويتم تحديد ذلك بواسطة مؤشر - سلسلة بتات تمثل عنوان ذاكرة ، يمكن تخزينها في الذاكرة ومعالجتها بواسطة البرنامج. وبالتالي، تعتمد هياكل بيانات المصفوفة والسجل على حساب عناوين عناصر البيانات باستخدام العمليات الحسابية ، بينما تعتمد هياكل البيانات المرتبطة على تخزين عناوين عناصر البيانات داخل الهيكل نفسه. هذا النهج في هيكلة البيانات له آثار عميقة على كفاءة وقابلية التوسع للخوارزميات. على سبيل المثال، يسهل تخصيص الذاكرة المتجاورة في المصفوفات عمليات الوصول السريع والتعديل، مما يؤدي إلى تحسين الأداء في سيناريوهات معالجة البيانات المتسلسلة. ^[10]

يتطلب تنفيذ بنية البيانات عادةً كتابة مجموعة من الإجراءات التي تنشئ وتتعامل مع مثيلات تلك البنية. لا يمكن تحليل كفاءة بنية البيانات بشكل منفصل عن تلك العمليات. تحفز هذه الملاحظة المفهوم النظري لنوع البيانات المجرد ، وهي بنية بيانات يتم تعريفها بشكل غير مباشر من خلال العمليات التي يمكن إجراؤها عليها، والخصائص الرياضية لتلك العمليات (بما في ذلك تكلفتها المكانية والزمنية). ^[11]

هناك أنواع عديدة من هياكل البيانات، والتي يتم بناؤها عمومًا على أنواع بيانات بدائية أبسط . ومن الأمثلة المعروفة: ^[12]

• المصفوفة عبارة عن عدد من العناصر بترتيب معين، وعادة ما تكون جميعها من نفس النوع (اعتمادًا على اللغة، قد يتم إجبار جميع العناصر الفردية على أن تكون من نفس النوع، أو قد تكون من أي نوع تقريبًا). يتم الوصول إلى العناصر باستخدام فهرس عدد صحيح لتحديد العنصر المطلوب. تخصص التطبيقات النموذجية كلمات ذاكرة متجاورة لعناصر المصفوفات (ولكن هذا ليس ضروريًا دائمًا). قد تكون المصفوفات ذات طول ثابت أو قابلة للتغيير في الحجم.
• القائمة المرتبطة (وتسمى أيضًا القائمة فقط ) عبارة عن مجموعة خطية من عناصر البيانات من أي نوع، تسمى العقد، حيث تحتوي كل عقدة على قيمة خاصة بها، وتشير إلى العقدة التالية في القائمة المرتبطة. الميزة الأساسية للقائمة المرتبطة على المصفوفة هي أنه يمكن دائمًا إدراج القيم وإزالتها بكفاءة دون نقل بقية القائمة. ومع ذلك، فإن بعض العمليات الأخرى، مثل الوصول العشوائي إلى عنصر معين، تكون أبطأ على القوائم منها على المصفوفات.
• السجل (يُسمى أيضًا tuple أو struct ) هو بنية بيانات مجمعة . السجل هو قيمة تحتوي على قيم أخرى، عادةً في عدد ثابت وتسلسل وعادةً ما يتم فهرستها بالأسماء. تُسمى عناصر السجلات عادةً حقولًا أو أعضاء . في سياق البرمجة الموجهة للكائنات ، تُعرف السجلات باسم هياكل البيانات القديمة البسيطة لتمييزها عن الكائنات. ^[13]
• جداول التجزئة ، والمعروفة أيضًا باسم خرائط التجزئة، هي هياكل بيانات توفر استرجاعًا سريعًا للقيم استنادًا إلى المفاتيح. وهي تستخدم دالة تجزئة لربط المفاتيح بالفهرس في مصفوفة، مما يسمح بالوصول في وقت ثابت في الحالة المتوسطة. تُستخدم جداول التجزئة عادةً في القواميس وذاكرات التخزين المؤقت وفهرسة قواعد البيانات. ومع ذلك، يمكن أن تحدث تصادمات التجزئة، مما قد يؤثر على أدائها. يتم استخدام تقنيات مثل التسلسل والتوجيه المفتوح للتعامل مع التصادمات.
• الرسوم البيانية عبارة عن مجموعات من العقد المتصلة بواسطة حواف، تمثل العلاقات بين الكيانات. يمكن استخدام الرسوم البيانية لنمذجة الشبكات الاجتماعية وشبكات الكمبيوتر وشبكات النقل، من بين أشياء أخرى. تتكون من رؤوس (عقد) وحواف (اتصالات بين العقد). يمكن أن تكون الرسوم البيانية موجهة أو غير موجهة، ويمكن أن يكون لها دورات أو غير دورية. تتضمن خوارزميات عبور الرسم البياني البحث أولاً بالعرض والبحث أولاً بالعمق.
• تعتبر المكدسات والطوابير أنواع بيانات مجردة يمكن تنفيذها باستخدام المصفوفات أو القوائم المرتبطة. تحتوي المكدس على عمليتين أساسيتين: push (إضافة عنصر إلى أعلى المكدس) وpop (إزالة العنصر الأعلى من المكدس)، والتي تتبع مبدأ Last In, First Out (LIFO). تحتوي الطوابير على عمليتين رئيسيتين: enqueue (إضافة عنصر إلى الجزء الخلفي من قائمة الانتظار) وdequeue (إزالة عنصر من مقدمة قائمة الانتظار) والتي تتبع مبدأ First In, First Out (FIFO).
• تمثل الأشجار تنظيمًا هرميًا للعناصر. تتكون الشجرة من عقد متصلة بحواف، حيث تكون إحدى العقد هي الجذر وجميع العقد الأخرى تشكل أشجارًا فرعية. تُستخدم الأشجار على نطاق واسع في العديد من الخوارزميات وسيناريوهات تخزين البيانات. الأشجار الثنائية (خاصة الكومة )، وأشجار AVL ، وأشجار B هي بعض الأنواع الشائعة من الأشجار. إنها تمكن من البحث والفرز والتمثيل الهرمي للبيانات بكفاءة وفعالية.

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

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

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

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

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

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

• هياكل البيانات المفتوحة بقلم بات مورين
• GH Gonnet و R. Baeza-Yates ، Handbook of Algorithms and Data Structures - in Pascal and C ، الطبعة الثانية، Addison-Wesley، 1991، ISBN 0-201-41607-7 
• إليس هورويتز وسارتاج ساهني، أساسيات هياكل البيانات في باسكال ، مطبعة علوم الكمبيوتر ، 1984، ISBN 0-914894-94-3 

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