بنية بيانات

تركيب البيانات - طريقة لتنظيم البيانات في ذاكرة الحاسوب للوصول اليها واستخدامها بكفاءة

في هندسة البرمجيات، فإن بنية البيانات هي طريقة خاصة لتخزين وتنظيم البيانات في الحاسوب بحيث يمكن استخدامها بكفاءة.[1][2]

شجرة ثنائية، إحدى أمثلة هياكل البيانات
هيكل بيانات يعرف باسم hash table.

تناسب أنواع مختلفة من هياكل البيانات أنواع مختلفة من التطبيقات، وبعضها مخصص بدرجة عالية لبعض المهام المحددة. على سبيل المثال، الأشجار(trees) بشكل خاص مناسبة تماما لتنفيذ قواعد البيانات، في حين تنفيذ المترجم عادة ما يستخدم جداول الهاش للبحث عن المعرفات.

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

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

استخدامعدل

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

تتناسب أنواع مختلفة من هياكل البيانات مع أنواع مختلفة من التطبيقات، وبعضها شديد التخصص لمهام محددة. على سبيل المثال، عادةً ما تستخدم قواعد البيانات العلائقية فهارس B-tree لاسترداد البيانات، بينما تستخدم تطبيقات المجمّع عادةً جداول التجزئة للبحث عن المعرّفات.

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

التنفيذعدل

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

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

أمثلةعدل

هناك أنواع عديدة من هياكل البيانات، مبنية بشكل عام على أنواع بينات أولية أبسط:

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

بالإضافة إلى ذلك، تعد الرسوم البيانية والأشجار الثنائية هياكل بيانات أخرى شائعة الاستخدام.

دعم اللغةعدل

تفتقر معظم لغات التجميع وبعض اللغات منخفضة المستوى، مثل BCPL (Basic Combined Programming Language)، إلى الدعم المدمج لهياكل البيانات. من ناحية أخرى، فإن العديد من لغات البرمجة عالية المستوى وبعض لغات التجميع عالية المستوى، مثل MASM، لها بناء جملة خاص أو دعم آخر مدمج لهياكل بيانات معينة، مثل السجلات والمصفوفات. على سبيل المثال، تدعم لغات C (سليل مباشر لـ BCPL) وباسكال البنيات والسجلات، على التوالي، بالإضافة إلى المتجهات (المصفوفات أحادية البعد) والمصفوفات متعددة الأبعاد.

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

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

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

مبادئ أساسيةعدل

ان هياكل البيانات تستند عموما على قدرة الكمبيوتر على جلب وتخزين البيانات في أي مكان في الذاكرة، وتحدد بواسطة عنوان - سلسلة بت من المكن هي نفسها تخزين في الذاكرة وتعالج بواسطة البرنامج. وهكذا فإن السجل ومصفوفة هياكل البيانات تقوم على حساب عناوين البيانات بواسطة العمليات الحسابية، في حين تستند هياكل البيانات المرتبطة على عناوين تخزين عناصر البيانات داخل الهيكل نفسه. العديد من هياكل البيانات تستخدم كلا المبدئين جنبا إلى جنب، وفي بعض الأحيان تجمع بطرق غير تافهة (كما في ربط اكس اور (XOR linking)).

انظر أيضًاعدل

المراجععدل

  1. ^ Paul E. Black (ed.), entry for data structure in قاموس الخوارزميات وهياكل البيانات  [لغات أخرى]. U.S. National Institute of Standards and Technology. 15 December 2004. Online version Accessed 2009-05-21. نسخة محفوظة 23 سبتمبر 2010 على موقع واي باك مشين.
  2. ^ Entry data structure in the موسوعة بريتانيكا (2009) Online entry accessed on 2009-05-21. نسخة محفوظة 02 مايو 2015 على موقع واي باك مشين.