دليل دراسي · نحو 12 دقيقة قراءة

هياكل البيانات

طريقة تخزين البيانات تحدد ما هو سريع وما هو بطيء. اختر مهمة يومية لترى أي بنية سيختارها المبرمج.

مكدسكل تعديل يُدفع إلى الأعلى؛ والتراجع يسحب الأحدث أولًا. آخر الداخلين أول الخارجين.

ما بنية البيانات، باختصار

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

لخّص نيكلاوس فيرث أهميتها في عنوان كتابه عام 1976: Algorithms + Data Structures = Programs.

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

العناصر نفسها تدخل، وعنصر مختلف يخرج

أضف عناصر إلى الاثنين، ثم احذف واحدًا. المكدس يعيد الأحدث (آخر الداخلين أول الخارجين)؛ والطابور يعيد الأقدم (أول الداخلين أول الخارجين).

المكدس · LIFOدفع / سحب
ABCالقمة · التالي خروجًا
سجل التراجع، وزر الرجوع في المتصفح، ومكدس الاستدعاءات الذي يتتبع أي دالة استدعت أيها.
الطابور · FIFOإدخال / إخراج
خروج ←
Aالتالي خروجًاBC
← دخول
المحذوف حتى الآن
المكدس:-الطابور:-
مهام الطباعة، والرسائل التي تنتظر خادمًا، والبحث بالعرض أولًا في مخطط.
جداول التجزئة

اقفز مباشرة إلى الدرج الصحيح

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

N(78) + o(111) + a(97) = 286 → 286 mod 8 = الخانة 6
خانة 0
Ana
خانة 1
خانة 2
خانة 3
خانة 4
خانة 5
Ben
خانة 6
Noa
خانة 7
لا تصادمات بعد. واصل إضافة الأسماء: مع 8 خانات فقط، سيتشارك اثنان خانة قريبًا.
الأشجار

اليسار أصغر، واليمين أكبر

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

503070204060801025354555657590
مسار البحث
1. 45 < 50 ← اذهب يسارًا2. 45 > 30 ← اذهب يمينًا3. 45 > 40 ← اذهب يمينًا4. 45 = 45 ✓ وُجد
4خطوات في الشجرة
7خطوات في القائمة (بالترتيب)
المفاضلات

ورقة المراجعة

سريعمقبولبطيء
البنيةالوصول بالموضعالبحثالإدراجالحذف
مصفوفة
O(1)O(n)O(n)O(n)
قائمة مترابطة
O(n)O(n)O(1)O(1)
مكدس
n/aO(n)O(1) للقمة فقطO(1) للقمة فقط
طابور
n/aO(n)O(1) للقمة فقطO(1) للقمة فقط
جدول تجزئة
n/aO(1)O(1)O(1)
شجرة بحث متوازنة
O(log n)O(log n)O(log n)O(log n)
كومة
n/aO(n)O(log n)O(log n)
حالات نموذجية أو متوسطة. قد تتدهور جداول التجزئة إلى O(n) مع تصادمات كثيرة؛ ويفترض صف الشجرة أنها تبقى متوازنة. «الإدراج» في مصفوفة يعني في المنتصف؛ والإضافة في النهاية عادةً O(1).

محطات بارزة

1945البرامج المخزّنة.وضع تصميم فون نيومان البيانات والتعليمات في الذاكرة نفسها، فجعل البنى ممكنة.
1953التجزئة.وصف هانز بيتر لون في IBM التجزئة للبحث السريع.
1955القوائم المترابطة.استخدمها نيويل وشو وسايمون في Logic Theorist، أحد أوائل برامج الذكاء الاصطناعي.
1962الأشجار المتوازنة.اخترع أديلسون-فيلسكي ولانديس شجرة AVL التي تعيد توازنها لتبقى سريعة.
1964الكومة.قدّم ج. و. ج. ويليامز الكومة الثنائية، مع الترتيب بالكومة.

تابع

Algorithms + Data Structures = ProgramsNiklaus Wirth · 1976
Introduction to AlgorithmsCormen, Leiserson, Rivest & Stein · 1990
Grokking AlgorithmsAditya Bhargava · 2016

بيانات منظمة، عقل منظم. اختبر استدلالك.

يغطي اختبار الذكاء الكامل لدينا الاستدلال المنطقي والعددي واللفظي والمكاني: 60 سؤالًا، نحو 30 دقيقة.

خذ اختبار الذكاء الكامل