DataStructure And Algo
1.0.0
هياكل البيانات هي وسيلة متخصصة لتنظيم وتخزين البيانات في أجهزة الكمبيوتر بطريقة يمكننا إجراء عمليات على البيانات المخزنة بشكل أكثر كفاءة. هياكل البيانات لها نطاق واسع ومتنوع من الاستخدام عبر مجالات علوم الكمبيوتر وهندسة البرمجيات. يتم استخدام هياكل البيانات في كل برنامج أو نظام برمجي تم تطويره تقريبًا. علاوة على ذلك ، تخضع هياكل البيانات تحت أساسيات علوم الكمبيوتر وهندسة البرمجيات. إنه موضوع رئيسي عندما يتعلق الأمر بأسئلة مقابلة هندسة البرمجيات. وبالتالي كمطورين ، يجب أن يكون لدينا معرفة جيدة حول هياكل البيانات.
المصفوفة هي بنية ذات حجم ثابت ، والتي يمكن أن تحتفظ بنوع البيانات نفسه. يمكن أن تكون مجموعة من الأعداد الصحيحة ، ومجموعة من أرقام النقطة العائمة ، أو مجموعة من الأوتار أو حتى مجموعة من المصفوفات (مثل المصفوفات ثنائية الأبعاد). يتم فهرسة المصفوفات ، مما يعني أن الوصول العشوائي ممكن.
لا يمكن إجراء إدخال عناصر على صفيف وحذف عناصر من صفيف على الفور حيث يتم تثبيت المصفوفات في الحجم. إذا كنت ترغب في إدراج عنصر إلى صفيف ، فسيتعين عليك أولاً إنشاء مجموعة جديدة ذات حجم متزايد (الحجم الحالي + 1) ، ونسخ العناصر الحالية وإضافة العنصر الجديد. وينطبق الشيء نفسه على الحذف مع مجموعة جديدة من الحجم المنخفض.
القائمة المرتبطة هي هيكل متسلسل يتكون من سلسلة من العناصر بالترتيب الخطي المرتبط ببعضها البعض. وبالتالي ، يجب عليك الوصول إلى البيانات بشكل متتابع ، ولا يمكن الوصول إلى عشوائي. توفر القوائم المرتبطة تمثيلًا بسيطًا ومرنًا للمجموعات الديناميكية.
المكدس هو Lifo (Last in First Out - يمكن الوصول إلى العنصر الذي تم وضعه أخيرًا في البداية) والذي يمكن العثور عليه عادة في العديد من لغات البرمجة. تم تسمية هذا الهيكل على أنه "مكدس" لأنه يشبه كومة العالم الحقيقي-كومة من اللوحات.
تستخدم لتقييم التعبير (على سبيل المثال: خوارزمية الساحة التحول لتحليل وتقييم التعبيرات الرياضية). تستخدم لتنفيذ مكالمات الوظائف في برمجة العودية.
قائمة الانتظار عبارة عن هيكل FIFO (الأول في البداية - يمكن الوصول إلى العنصر الذي تم وضعه في البداية في البداية) والذي يمكن العثور عليه عادة في العديد من لغات البرمجة. تم تسمية هذا الهيكل على أنه "قائمة انتظار" لأنه يشبه قائمة انتظار في العالم الحقيقي-الأشخاص الذين ينتظرون في قائمة انتظار.
تستخدم لإدارة المواضيع في multithreading. تستخدم لتنفيذ أنظمة قائمة الانتظار (على سبيل المثال: قوائم قوائم الأولوية).
جدول التجزئة هو بنية بيانات تخزن القيم التي لها مفاتيح مرتبطة بكل منها. علاوة على ذلك ، فإنه يدعم البحث بكفاءة إذا كنا نعرف المفتاح المرتبط بالقيمة. وبالتالي فهو فعال للغاية في إدخال والبحث ، بغض النظر عن حجم البيانات.
يستخدم العنوان المباشر رسم الخرائط الفردية بين القيم والمفاتيح عند التخزين في الجدول. ومع ذلك ، هناك مشكلة في هذا النهج عندما يكون هناك عدد كبير من أزواج القيمة الرئيسية. سيكون الجدول ضخمًا مع العديد من السجلات وقد يكون غير عملي أو حتى من المستحيل تخزينه ، نظرًا للذاكرة المتاحة على جهاز كمبيوتر نموذجي. لتجنب هذه المشكلة ، نستخدم جداول التجزئة .
يتم استخدام وظيفة خاصة تسمى وظيفة التجزئة (H) للتغلب على المشكلة المذكورة أعلاه في العنوان المباشر. في الوصول المباشر ، يتم تخزين قيمة مع المفتاح K في الفتحة K. باستخدام وظيفة التجزئة ، نقوم بحساب فهرس الجدول (الفتحة) التي تذهب إليها كل قيمة. تسمى القيمة المحسوبة باستخدام وظيفة التجزئة لمفتاح معين قيمة التجزئة التي تشير إلى فهرس الجدول الذي يتم تعيين القيمة إليه.
الشجرة هي بنية هرمية حيث يتم تنظيم البيانات بشكل هرمي وترتبط معًا. يختلف هذا الهيكل عن قائمة مرتبطة ، بينما ، في قائمة مرتبطة ، يتم ربط العناصر بترتيب خطي. تم تطوير أنواع مختلفة من الأشجار على مدار العقود الماضية ، من أجل تناسب تطبيقات معينة وتلبية قيود معينة. بعض الأمثلة هي شجرة البحث الثنائية وشجرة B و Treap و Red Black Tree و Tream Tree و AVL Tree و N-ary.
شجرة البحث الثنائية (BST) ، كما يوحي الاسم ، هي شجرة ثنائية حيث يتم تنظيم البيانات في بنية هرمية. بنية البيانات هذه تخزن القيم بترتيب فرز. تشتمل كل عقدة في شجرة بحث ثنائية على السمات التالية.
تُظهر شجرة البحث الثنائية خاصية فريدة تميزها عن الأشجار الأخرى. تُعرف هذه الخاصية باسم خاصية ** Binary-Search-Tree **.
كومة هي حالة خاصة لشجرة ثنائية حيث تتم مقارنة العقد الأم مع أطفالها بقيمهم ويتم ترتيبها وفقًا لذلك.
يمكن أن تكون أكوام من نوعين.
يتكون الرسم البياني من مجموعة محدودة من الرؤوس أو العقد ومجموعة من الحواف التي تربط هذه القمم.
ترتيب الرسم البياني هو عدد القمم في الرسم البياني. حجم الرسم البياني هو عدد الحواف في الرسم البياني.
يقال إن العقدتين متاخمين إذا تم توصيلهما ببعضهما البعض بنفس الحافة.
يقال إن الرسم البياني G عبارة عن رسم بياني موجه إذا كان لكل حوافه اتجاه يشير إلى ما هو قمة البدء وما هو قمة النهاية . نقول أن (u ، v) هو حادث من أو يترك Vertex u ويحدث أو يدخل في Vertex v. الحلقات الذاتية: حواف من قمة الرأس إلى نفسها.
يقال إن الرسم البياني G عبارة عن رسم بياني غير موجه إذا لم يكن لكل حوافها اتجاه. يمكن أن يذهب في كلا الاتجاهين بين الرأسين.
إذا لم يتم توصيل قمة الرأس بأي عقدة أخرى في الرسم البياني ، يقال إنه معزول .
Trie هو بنية بيانات استرجاع المعلومات التي تشبه الأشجار التي تخزن العقد رسائل الأبجدية. يُعرف أيضًا باسم شجرة رقمية أو شجرة أو شجرة بادئة Radix.
تري هي بنية بيانات استرجاع المعلومات الفعالة. باستخدام Trie ، يمكن إحضار تعقيدات البحث إلى الحد الأمثل (طول المفتاح). إذا قمنا بتخزين المفاتيح في شجرة البحث الثنائية ، فستحتاج BST متوازنة جيدًا إلى وقت يتناسب مع M * log n ، حيث يكون M أقصى طول للسلسلة و N هو عدد المفاتيح في الشجرة. باستخدام Trie ، يمكننا البحث في وقت O (M) .
1. TRIE القياسي : إنها شجرة مرتبة مثل بنية البيانات.
2. تري المضغوط : يتم استخدامه لتحقيق تحسين المساحة. تري المضغوط هو نسخة متقدمة من TRIE القياسية.
3. لاحقة تري : لاحقة تري هي نسخة متقدمة من تري المضغوط.
مع Trie ، يمكننا إدراج والعثور على سلاسل في وقت O (ل) حيث تمثل L طول كلمة واحدة. من الواضح أن هذا أسرع من BST. هذا أيضًا أسرع من التجزئة بسبب الطرق التي يتم تنفيذه. لا نحتاج إلى حساب أي وظيفة تجزئة. ميزة أخرى من Trie هي أنه يمكننا بسهولة طباعة جميع الكلمات بالترتيب الأبجدي الذي لا يمكن بسهولة مع التجزئة.
البرمجة الديناميكية هي تقنية تحطم المشكلات إلى مشكلات فرعية ، وتوفر نتيجة لأغراض مستقبلية حتى لا نحتاج إلى حساب النتيجة مرة أخرى. يتم تحسين المشكلات الفرعية لتحسين الحل الكلي باسم خاصية البنية التحتية الأمثل. الاستخدام الرئيسي للبرمجة الديناميكية هو حل مشاكل التحسين. هنا ، تعني مشاكل التحسين أنه عندما نحاول معرفة الحد الأدنى أو الحد الأقصى لحل المشكلة. يضمن البرمجة الديناميكية العثور على الحل الأمثل للمشكلة في حالة وجود الحل.
خوارزمية تعقيد الوقت O (1) تبحث عن عنصر معين في صفيف ، مثل هذا على سبيل المثال: Print (My_array [97]) بغض النظر عن حجم الصفيف ، يمكن البحث عن عنصر مباشرة ، فهو يتطلب عملية واحدة فقط. (هذه ليست حقًا خوارزمية بالمناسبة ، ولكنها يمكن أن تساعدنا على فهم كيفية عمل تعقيد الوقت.)
س (ن) إيجاد أدنى قيمة. يجب أن تقوم الخوارزمية بالعمليات في صفيف مع قيم n للعثور على أدنى قيمة ، لأن الخوارزمية يجب أن تقارن كل قيمة مرة واحدة.
O (n 2) فرز الفقاعة ، فرز الاختيار وفرز الإدراج هي خوارزميات مع هذا الوقت التعقيد. يتم شرح سبب تعقيدات الوقت الخاصة بهم على صفحات هذه الخوارزميات.
مجموعات البيانات الكبيرة تبطئ هذه الخوارزميات بشكل كبير. مع زيادة في N من 100 إلى 200 قيمة ، يمكن أن يزداد عدد العمليات بمقدار 30000!
o (n log n) خوارزمية Quicksort أسرع في المتوسط من خوارزميات الفرز الثلاثة المذكورة أعلاه ، مع أن O (n log n) هي المتوسط وليس أسوأ وقت. أسوأ وقت لـ QuickSort هو أيضًا O (n 2) ، ولكن هذا هو متوسط الوقت الذي يجعل Quicksort ممتعًا للغاية. سوف نتعرف على Quicksort لاحقًا.
المرجع مأخوذ من هذا الرابط - Sourav Saini؟
