بنية البيانات المرتبطة

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

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

يمكن إجراء الربط بطريقتين - باستخدام التخصيص الديناميكي واستخدام ربط مؤشر المصفوفة.

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

القائمة المرتبطة هي مجموعة من الهياكل مرتبة ليس حسب موقعها المادي في الذاكرة ولكن حسب الروابط المنطقية المخزنة كجزء من البيانات في الهيكل نفسه. ليس من الضروري تخزينها في مواقع الذاكرة المجاورة. كل هيكل يحتوي على حقل بيانات وحقل عنوان. يحتوي حقل العنوان على عنوان خليفته .

يمكن أن تكون القائمة المرتبطة مفردة أو مزدوجة أو متعددة الارتباطات، ويمكن أن تكون خطية أو دائرية.

الخصائص الأساسية

• ترتبط الكائنات، المسماة بالعقد ، في تسلسل خطي.
• يتم الاحتفاظ دائمًا بالإشارة إلى العقدة الأولى في القائمة. وهذا ما يسمى "الرأس" أو "الواجهة". ^[3]

تحتوي القائمة المرتبطة التي تحتوي على ثلاث عقد على حقلين لكل منهما: قيمة عددية ورابط إلى العقدة التالية

هذا مثال لفئة العقدة المستخدمة لتخزين الأعداد الصحيحة في تنفيذ Java لقائمة مرتبطة:

public class IntNode { public int value ; public IntNode link ; public IntNode ( int v ) { value = v ; } }   
       
       
            

هذا مثال للهيكل المستخدم لتنفيذ القائمة المرتبطة في C:

بنية العقدة { int val ؛ بنية العقدة * التالية ؛ }; 

	 
	  

هذا مثال لاستخدام typedefs :

typedef struct node node ;   

بنية العقدة { int val ؛ العقدة * التالية ؛ }; 

	 
	 

ملاحظة: الهيكل مثل هذا الذي يحتوي على عضو يشير إلى نفس الهيكل يسمى هيكل مرجعي ذاتي.

هذا مثال على بنية فئة العقدة المستخدمة لتنفيذ القائمة المرتبطة في C++:

الفئة Node { int val ; Node * next ; }; 

	 
	 

شجرة البحث هي بنية بيانات شجرة يمكن تخزين قيم البيانات في عقدها من مجموعة مرتبة ، بحيث يتم زيارة العقد في عملية التنقل داخل الشجرة بترتيب تصاعدي للقيم المخزنة.

الخصائص الأساسية

• يتم تخزين الكائنات، والتي تسمى بالعقد، في مجموعة مرتبة.
• يوفر التنقل بالترتيب قراءة تصاعدية للبيانات الموجودة في الشجرة.

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

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

من ناحية أخرى، يتطلب الوصول إلى أي عقدة معينة في بنية بيانات مرتبطة اتباع سلسلة من المراجع المخزنة في كل عقدة. إذا كانت البنية تحتوي على n عقدة، وكل عقدة تحتوي على b روابط على الأكثر، فستكون هناك بعض العقد التي لا يمكن الوصول إليها في أقل من log _b n خطوة، مما يؤدي إلى إبطاء عملية الوصول إلى هذه العقد - وهذا يمثل أحيانًا تباطؤًا كبيرًا، خاصة في حالة الهياكل التي تحتوي على أعداد كبيرة من العقد. بالنسبة للعديد من الهياكل، قد تتطلب بعض العقد أسوأ حالة تصل إلى n −1 خطوة. على النقيض من ذلك، تسمح العديد من هياكل بيانات المصفوفة بالوصول إلى أي عنصر بعدد ثابت من العمليات، بغض النظر عن عدد الإدخالات.

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

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

في المصفوفات، يمكن الوصول إلى العنصر n على الفور، بينما في بنية البيانات المرتبطة يتعين علينا اتباع مؤشرات متعددة حتى يختلف وقت الوصول إلى العنصر وفقًا لمكان وجود العنصر في البنية.

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

• قائمة هياكل البيانات

Original text

Rate this translation

Your feedback will be used to help improve Google Translate