بنية بيانات

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

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

استخدامها[عدل]

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

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

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

التنفيذ[عدل]

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

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

أمثلة[عدل]

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

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

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

دعم اللغة[عدل]

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

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

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

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

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

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

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

المراجع[عدل]

  1. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms, Third Edition (الطبعة 3rd). The MIT Press. ISBN 978-0262033848. الوسيط |CitationClass= تم تجاهله (مساعدة)
  2. ^ Black, Paul E. (15 December 2004). "data structure". In Pieterse, Vreda; Black, Paul E. (المحررون). Dictionary of Algorithms and Data Structures [online]. المعهد الوطني للمعايير والتقنية. اطلع عليه بتاريخ 06 نوفمبر 2018. الوسيط |CitationClass= تم تجاهله (مساعدة)
  3. ^ "Data structure". Encyclopaedia Britannica. 17 April 2017. مؤرشف من الأصل في 14 يوليو 2021. اطلع عليه بتاريخ 06 نوفمبر 2018. الوسيط |CitationClass= تم تجاهله (مساعدة)
  4. ^ Wegner, Peter; Reilly, Edwin D. (2003-08-29). Encyclopedia of Computer Science. Chichester, UK: John Wiley and Sons. صفحات 507–512. ISBN 978-0470864128. الوسيط |CitationClass= تم تجاهله (مساعدة)
  5. ^ "Abstract Data Types". Virginia Tech - CS3 Data Structures & Algorithms. مؤرشف من الأصل في 20 مارس 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)
  6. ^ Gavin Powell (2006). "Chapter 8: Building Fast-Performing Database Models". Beginning Database Design. Wrox Publishing. ISBN 978-0-7645-7490-0. الوسيط |CitationClass= تم تجاهله (مساعدة)
  7. ^ "1.5 Applications of a Hash Table". University of Regina - CS210 Lab: Hash Table. مؤرشف من الأصل في 27 أبريل 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)
  8. ^ "When data is too big to fit into the main memory". homes.sice.indiana.edu. مؤرشف من الأصل في 27 أبريل 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)