هياكل البيانات الأكثر شعبية

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

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


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


المصفوفات - المصفوفات
المصفوفة هي أبسط هيكل للبيانات وأكثرها استخدامًا. يتم اشتقاق تراكيب البيانات الأخرى ، مثل المداخن وقوائم الانتظار ، من المصفوفات.
هذه صورة لصفيف بسيط من الحجم 4 يحتوي على عناصر (1 و 2 و 3 و 4).

صورة

يتم تعيين قيمة رقمية موجبة لكل عنصر بيانات يسمى الفهرس ، والذي يتوافق مع موضع هذا العنصر في الصفيف. تحدد معظم اللغات فهرس البداية للمصفوفة على أنه 0.

فيما يلي نوعان من المصفوفات:
  • صفائف أحادية البعد (كما هو موضح أعلاه)
  • صفائف متعددة الأبعاد (صفائف داخل صفائف) صفائف متعددة الأبعاد


العمليات الأساسية على المصفوفات.
إدراج - إدراج
عنصر في فهرس محدد.
حذف (حذف) - إزالة عنصر في فهرس محدد.
الحجم - الحصول على العدد الإجمالي للعناصر في مصفوفة.

للدراسة الذاتية:
1 ابحث عن العنصر الثاني الأدنى للصفيف.
2. أول عدد صحيح غير متكرر في المصفوفة.
3. دمج صفيفين مفروزين.
4. إعادة ترتيب القيم الموجبة والسالبة في الصفيف.

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

من الأمثلة الحقيقية على المكدس مجموعة من الكتب مرتبة رأسياً. للحصول على كتاب في مكان ما في المنتصف ، تحتاج إلى حذف جميع الكتب الموضوعة فوقه. إليك كيفية عمل طريقة LIFO (Last In First Out) .
هذه صورة لمكدس يحتوي على ثلاثة عناصر بيانات (1 و 2 و 3) ، حيث يوجد 3 في الأعلى وسيتم حذفه أولاً:



العمليات الأساسية مع المداخن:
Push - إدراج عنصر فوق الآخرين.
سحب (Pop) - إرجاع العنصر العلوي بعد إزالته من المكدس.
فارغة؟ (IsEmpty) - إرجاع true (true) إذا كان المكدس فارغًا.
أعلى (أعلى) - إرجاع العنصر العلوي بدون الحذف من المكدس.

للدراسة المستقلة:
1. قم بتقييم تعبير postfix باستخدام المكدس.
2. فرز القيم على المكدس.
3. تحقق من الأقواس المتوازنة في التعبير.

قوائم الانتظار
مثل المكدس ، قائمة الانتظار هي بنية بيانات خطية أخرى يتم فيها تخزين العناصر بشكل تسلسلي. الفرق الوحيد المهم بين المكدس وقائمة الانتظار هو أنه بدلاً من استخدام طريقة LIFO ، تقوم قائمة الانتظار بتطبيق طريقةFIFO ، وهو اختصار لـ First in First Out .
مثال حقيقي على الخط: عدد من الأشخاص ينتظرون في مكتب التذاكر. إذا جاء شخص جديد ، ينضم إلى الخط من النهاية ، وليس من البداية - وسيكون الشخص الذي يقف في المقدمة هو أول من يحصل على تذكرة ، وبالتالي ، سيترك الخط.
فيما يلي صورة لقائمة انتظار تحتوي على أربعة عناصر بيانات (1 و 2 و 3 و 4) ، حيث تكون 1 في الأعلى وسيتم حذفها أولاً:



العمليات الأساسية في قائمة الانتظار:
Enqueue - إدراج عنصر في نهاية قائمة الانتظار.
Dequeue - لحذف عنصر من بداية قائمة الانتظار.
فارغة؟ (IsEmpty) - إرجاع true (true) إذا كانت قائمة الانتظار فارغة.
أعلى (أعلى) - إرجاع العنصر الأول في قائمة الانتظار.

للدراسة المستقلة:
1. تنفيذ المكدس باستخدام قائمة الانتظار.
2. عناصر k الأولى العكسية لقائمة الانتظار.
3. توليد أرقام ثنائية من 1 إلى n باستخدام قائمة الانتظار.

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

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

تستخدم القوائم المرتبطة لتنفيذ أنظمة الملفات وجداول التجزئة وقوائم المجاورة.

فيما يلي تمثيل مرئي للبنية الداخلية لقائمة مرتبطة:



فيما يلي أنواع القوائم المرتبطة:
  • قائمة ارتباط واحد (أحادي الاتجاه)
  • قائمة مرتبطة مزدوجة (ثنائية الاتجاه)


عمليات
الإدراج الأساسية في قائمة مرتبطة InsertAtEnd - إدراج عنصر في نهاية قائمة مرتبطة.
InsertB Start (InsertAtHead) - لإدراج عنصر في بداية القائمة المرتبطة.
حذف - يزيل هذا العنصر من القائمة المرتبطة.
DeleteBeginning (DeleteAtHead) - حذف العنصر الأول من القائمة المرتبطة.
بحث - لإرجاع العنصر الموجود من القائمة المرتبطة.
فارغة؟ (IsEmpty) - إرجاع صواب (صواب) إذا كانت القائمة المرتبطة فارغة.

للدراسة المستقلة:
1. اقلب القائمة المرتبطة (عكس ، عكس ، عرض للخلف).
2. تحديد حلقة في قائمة مرتبطة.
3. إعادة العقدة Nth من النهاية في القائمة المرتبطة.
4. إزالة التكرارات من القائمة المرتبطة.

الرسوم
البيانية الرسوم البيانية هي مجموعة من العقد المتصلة ببعضها البعض في شكل شبكة. تسمى العقد أيضًا القمم. يُدعى الزوج (س ، ص) بالحافة ، مما يشير إلى أن الرأس x متصل مع الرأس y. يمكن أن تحتوي الحافة على الوزن / التكلفة ، مما يوضح مقدار التكلفة اللازمة للانتقال من أعلى x إلى y.



أنواع الرسوم البيانية:
  • رسم بياني غير موجه
  • مخطط موجه


في لغات البرمجة ، يتم تمثيل الرسوم البيانية في شكلين:


فيما يلي مثال لقائمة المجاورة المتجاورة (رسم بياني غير موجه).



أمثلة معروفة لتحريك الخوارزميات على طول الرسوم البيانية:


للدراسة المستقلة:
1. تنفيذ البحث الأول والعمق.
2. تحقق مما إذا كان الرسم البياني عبارة عن شجرة أم لا.
3. عد عدد الحواف في الرسم البياني.
4. البحث عن أقصر مسار بين القمم.

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

تستخدم الأشجار على نطاق واسع في الذكاء الاصطناعي والخوارزميات المعقدة لتوفير آلية تخزين فعالة لخوارزميات حل المشكلات.

فيما يلي صورة لشجرة بسيطة والمصطلحات الأساسية المستخدمة في بنية بيانات الشجرة:



هناك أنواع من الأشجار:

  • N-
  • (Balanced Tree)
  • (Binary Tree)
  • (Binary Search Tree)
  • AVL
  • - (Red Black Tree)
  • 2–3


مما ورد أعلاه ، تعد الشجرة الثنائية وشجرة البحث الثنائية الشجرة الأكثر استخدامًا.

للدراسة المستقلة:
1. أوجد ارتفاع الشجرة الثنائية.
2. أوجد القيمة القصوى kth في شجرة البحث الثنائية.
3. ابحث عن العقد على مسافة "k" من الجذر.
4. ابحث عن أسلاف العقدة المعطاة في الشجرة الثنائية.

أمثلة عملية:

1. Facebook: كل مستخدم هو رأس ، وشخصان صديقان عندما تكون هناك حافة بين ذروتين. كما يتم احتساب التوصيات للأصدقاء على أساس نظرية الرسم البياني.

2. خرائط Google: تمثل المواقع المختلفة القمم والطرق ممثلة بالحواف ، وتستخدم نظرية الرسم البياني للعثور على أقصر مسار بين القمتين.

3. شبكات النقل: فيها القمم هي تقاطعات الطرق والأضلاع - وهي أجزاء الطريق بين تقاطعاتها.

4. تمثيل الهياكل الجزيئية حيث تكون القمم جزيئات والحواف هي الروابط بين الجزيئات.

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

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

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

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

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

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

لC # عشاق، مثلي، وصلة مع أمثلة C # رمز الرسوم البيانية هو هنا. للمكتبة الأكثر تقدما مع تنفيذ الرسوم البيانية في C ++ هنا . لمحبي AI و Skynet ، ستومب هنا .

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

فيما يلي توضيح لكيفية تخزين الكلمات الثلاث "أعلى" و "هكذا" و "الخاصة بهم" في الأولوية:



يتم تخزين الكلمات من الأعلى إلى الأسفل ، حيث تشير العقد الخضراء "p" و "s" و "r" إلى نهاية "top" و " وبالتالي "و" هم "، على التوالي.

للدراسة المستقلة:
1. احسب إجمالي عدد الكلمات في الأولوية.
2. طباعة جميع الكلمات المخزنة في الأولوية.
3. فرز عناصر المصفوفة باستخدام الأولوية.
4. توليد الكلمات من القاموس باستخدام قوائم الانتظار.
5. إنشاء قاموس T9.

أمثلة عملية للاستخدام:
1. الاختيار من القاموس أو إكماله عند كتابة كلمة.
2. البحث في جهات الاتصال في الهاتف أو قاموس الهاتف.

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

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

يتم تطبيق جداول التجزئة عادةً باستخدام المصفوفات.

يعتمد أداء تجزئة بنية البيانات على هذه العوامل الثلاثة:
  • دالة تجزئة
  • تجزئة حجم الجدول
  • طريقة معالجة التصادم


فيما يلي توضيح لكيفية عرض التجزئة في صفيف. يتم حساب فهرس هذا الصفيف باستخدام دالة التجزئة.



للدراسة المستقلة:
1. ابحث عن أزواج متماثلة في المصفوفة.
2. اتبع مسار السفر الكامل.
3. اكتشف ما إذا كان الصفيف مجموعة فرعية من صفيف آخر.
4. تحقق مما إذا كانت الصفيفات مفككة.

يوجد أدناه نموذج رمز استخدام جدول التجزئة في .Net

static void Main(string[] args)
        {
            Hashtable ht = new Hashtable
            {
                { "001", "Zara Ali" },
                { "002", "Abida Rehman" },
                { "003", "Joe Holzner" },
                { "004", "Mausam Benazir Nur" },
                { "005", "M. Amlan" },
                { "006", "M. Arif" },
                { "007", "Ritesh Saikia" }
            };

            if (ht.ContainsValue("Nuha Ali"))
            {
                Console.WriteLine("    !");
            }
            else
            {
                ht.Add("008", "Nuha Ali");
            }

            //   .
            ICollection key = ht.Keys;

            foreach (string k in key)
            {
                Console.WriteLine(k + ": " + ht[k]);
            }
            Console.ReadKey();
        }


أمثلة عملية:

1. لعبة "الحياة". في ذلك ، التجزئة هي مجموعة من الإحداثيات لكل خلية حية.

2. يمكن لإصدار بدائي من محرك بحث Google تعيين جميع الكلمات الموجودة في مجموعة من عناوين URL التي تظهر فيها. في هذه الحالة ، يتم استخدام جداول التجزئة مرتين: المرة الأولى لتعيين الكلمات إلى مجموعات عناوين URL ، وفي المرة الثانية ، لحفظ كل مجموعة من عناوين URL.

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

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

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

All Articles