CS2_test.pdf

‫علوم حاسب‪-12-‬تكنولوجي‬ ‫الفصل األول ‪ -‬هياكل البيانات المتقدمة‬ ‫الدرس الثاني ‪ -‬القائمة المرتبطة ‪Linked List‬‬...

‫علوم حاسب‪-12-‬تكنولوجي‬ ‫الفصل األول ‪ -‬هياكل البيانات المتقدمة‬ ‫الدرس الثاني ‪ -‬القائمة المرتبطة ‪Linked List‬‬ ‫هياكل البيانات الثابتة والديناميكية‬ ‫هياكل البيانات هي طريقة لتخزين وتنظيم البيانات بكفاءة‪.‬‬ ‫‪ -‬ثابتة ‪.Static‬‬ ‫‪ -‬ديناميكية (متغيرة) ‪.Dynamic‬‬ ‫هياكل البيانات الثابتة ‪:‬‬ ‫ذات حجم ثابت‪ ،‬فيتم تخصيص مواقع متجاورة في الذاكرة لعناصرها ( المصفوفات )‪.‬‬ ‫ ‬ ‫هياكل البيانات الديناميكية (المتغرية) ‪:‬‬ ‫ً‬ ‫يتغير حجمها أثناء تنفيذ البرنامج اعتمادا علي العمليات التي يتم إجراؤها‪ ،‬وتصمم لتوفير المرونة في تغيير‬ ‫ ‬ ‫حجم هياكل البيانات وقت التشغيل (القائمة المرتبطة)‬ ‫ ‬ ‫سؤال ‪ :‬قارن بين هياكل البيانات الثابتة وهياكل البيانات الديناميكية ؟‬ ‫هياكل البيانات الثابتة وهياكل البيانات الديناميكية‬ ‫الديناميكية‬ ‫الثابتة‬ ‫وجه املقارنة‬ ‫ال نامج‬ ‫يتغ أثناء تنفيذ ب‬ ‫يمكن أن ي‬ ‫ثابت‬ ‫حجم الذاكرة‬ ‫مواقع عشوائية‬ ‫مواقع متجاورة‬ ‫طريقة التخزين‬ ‫أبطأ‬ ‫أرسع‬ ‫رسعة الوصول يإيل البيانات‬ ‫تخصيص الذاكرة‬ ‫‪ ‬تنتمي القائمة المرتبطة لهياكل البيانات الديناميكية ‪ ،‬ولهذا السبب نحتاج إلي استخدام مؤشرات أخرى خاصة للعقد‬ ‫‪ -‬ثابتة ‪:‬‬ ‫تحتــاج إلــي مجموعــة متجــاورة مــن مواقــع‬ ‫الذاكــرة (المصفوفــات)‬ ‫‪ -‬ديناميكية ‪:‬‬ ‫ال تحتــاج إلــي مواقــع ذاكــرة متجــاورة ‪،‬‬ ‫فيمكنهــا التوســع بصــورة ديناميكيــة (القوائــم‬ ‫المرتبطــة)‬ ‫‪17‬‬ ‫‪55437757‬‬ ‫مصطفى بكري‬ ‫بايثونيستا الثانوية العامة‬ ‫علوم حاسب‪-12-‬تكنولوجي‬ ‫الفصل األول ‪ -‬هياكل البيانات المتقدمة‬ ‫القائمة المرتبطة ‪Linked List‬‬ ‫ً‬ ‫هــي أحــد أكثــر هيــاكل البيانــات الخطيــة شــيوعا فــي عالــم البرمجــة ‪ ،‬تشــبه سلســلة مــن العقــد المتتاليــة ‪ ،‬وكل عقــدة تحــوي علــي‬ ‫حقليــن ‪ :‬حقــل البيانــات وحقــل يحــوي عنــوان العقــدة التاليــة وتســتثني العقــدة األخيــرة التــي ال يحمــل حقــل العنــوان فيهــا أي‬ ‫ً‬ ‫بيانــات‪.‬احــد مزاياهــا فــي زيــادة او نقــص حجمهــا تلقائيــا بإضافــة او حــذف عقــدة‪.‬‬ ‫العقدة ‪Node‬‬ ‫تتكون كل عقدة من قسمين ‪:‬‬ ‫‪ -‬البيانات‪.‬‬ ‫‪ -‬مؤرش يشري إيل عنوان العقد التالية‪.‬‬ ‫‪ 1-‬ليس للعقد في القائمة أي أسماء فقط العنوان (موقع الذاكرة) الذي يتم تخزينه للوصول إلي أي عقدة‪.‬‬ ‫‪ 2-‬الوصول في القائمة المرتبطة وصول تسلسلي إي أن للوصول الى عقده يجب المرور بجميع العقد التي تسبقها‪.‬‬ ‫‪18‬‬ ‫‪55437757‬‬ ‫مصطفى بكري‬ ‫بايثونيستا الثانوية العامة‬ ‫علوم حاسب‪-12-‬تكنولوجي‬ ‫الفصل األول ‪ -‬هياكل البيانات المتقدمة‬ ‫قارن بين القائمة (المصفوفة) والقائمة المرتبطة ؟‬ ‫هياكل البيانات الثابتة وهياكل البيانات الديناميكية‬ ‫القائمة املرتبطة‬ ‫القائمة‬ ‫وجه املقارنة‬ ‫ف‬ ‫ف‬ ‫غ متجاورة‬ ‫تخزن ي مواقع ي‬ ‫تخزن ي مواقع مجاورة‬ ‫تخزين البيانات‬ ‫التعامل مع عنارصها من خالل‬ ‫التسلسيل‬ ‫ي‬ ‫التعامل مع عنارصها بالرقم‬ ‫المؤ ‬‫ش‬ ‫‪xednI‬‬ ‫الهيكل‬ ‫تخزن العنارص كعقد فيها البيانات‬ ‫ش‬ ‫يتم تخزين كل عنرص بعد اآلخر‬ ‫(مؤ )‬ ‫التايل‬ ‫ي‬ ‫العنرص‬ ‫وعنوان‬ ‫ف‬ ‫ش‬ ‫ف‬ ‫والمؤ ات ي الذاكرة‬ ‫تخزين البيانات‬ ‫تخزين البيانات فقط ي الذاكرة‬ ‫استخدام الذاكرة‬ ‫ئ‬ ‫تسلسيل‬ ‫ي‬ ‫عشوا ‬ ‫ي‬ ‫الوصول يإيل البيانات‬ ‫أبطأ‬ ‫أرسع‬ ‫رسعة الوصول‬ ‫أرسع‬ ‫أبطأ‬ ‫رسعة اإلضافة واإلزالة‬ ‫سؤال ‪ :‬كيف يمكن الوصول لبيانات العقدة الثالثة في قائمة ؟‬ ‫إذا أردنا الوصول إلي العقدة الثالثة من القائمة لمعالجة بياناتها ‪ ،‬يجب أن نبدأ من العقدة األولي في القائمة ‪ ،‬ثم من‬ ‫العقدة األولي للثانية ومن الثانية للوصول إلي الثالثة‪.‬‬ ‫‪ -‬يتم تخزين عنوان العقدة األولي في متغير خاص (مستقل) نسميه الرأس ‪.Head‬‬ ‫‪ -‬يشير مؤشر العقدة األخيرة من القائمة إلي قيمة خالية ‪ Null‬ونمثلها بالرمز ‪.‬‬ ‫‪ -‬عندما تكون القائمة فارغة‪ ،‬يشير مؤشر الرأس إلي قيمة خالية ‪.Null‬‬ ‫سؤال ‪ :‬ماذا تعني ‪ Null‬؟‬ ‫سؤال ‪ :‬متي يشير مؤشر الرأس الى قيمة ‪ Null‬؟‬ ‫‪19‬‬ ‫‪55437757‬‬ ‫مصطفى بكري‬ ‫بايثونيستا الثانوية العامة‬ ‫علوم حاسب‪-12-‬تكنولوجي‬ ‫الفصل األول ‪ -‬هياكل البيانات المتقدمة‬ ‫القائمة المرتبطة في ‪Python‬‬ ‫ال يوجد نوع مخصص للقوائم المرتبطة بلغة البرمجة ‪ ، Python‬لذلك علينا استخدام مكتبات ‪ Python‬إضافية توفر‬ ‫ً‬ ‫تمثيال لهذا النوع من البيانات‪.‬يتم استخدام الفئات كقالب إلنشاء الكائنات‪.‬‬ ‫الفئة ‪class‬‬ ‫هي بنية يحددها المستخدم وتحتفظ بمجموعتها الخاصة من البيانات مثل‪ :‬الخصائص والوظائف‪.‬‬ ‫العقدة تكون مقسمة الى ‪ 3‬أجزاء وهي كالتالي ‪:‬‬ ‫‪1-‬عنوان العقدة ويشير الى مكان العقدة في الذاكرة‬ ‫‪2-‬البيانات التي تحملها العقدة‬ ‫‪3-‬عنوان العقدة التالية‬ ‫انظر الى الرسم التالي ثم جاوب على األسئلة التالية ‪:‬‬ ‫‪ -‬ما هو عنوان اخر عقدة ؟‬ ‫‪ -‬ما هو عنوان ثاني عقدة ؟‬ ‫‪ -‬ما هي البيانات الموجودة في العقدة األولى ؟‬ ‫‪ -‬ما معنى العالمة ( ) في اخر عقدة‬ ‫‪ -‬ما هي العقدة التي تلي العقدة التي تحمل عنوان ‪30‬‬ ‫‪20‬‬ ‫‪55437757‬‬ ‫مصطفى بكري‬ ‫بايثونيستا الثانوية العامة‬ ‫علوم حاسب‪-12-‬تكنولوجي‬ ‫الفصل األول ‪ -‬هياكل البيانات المتقدمة‬ ‫ال يوجــد متغيــر مدمــج فــي ‪ Python‬لتمثيــل القوائــم المرتبطــة (‪ )Linked Lists‬كمــا هــو الحــال مــع القوائــم العاديــة‪.‬‬ ‫ولكــن يمكننــا إنشــاء قائمــة مرتبطــة عــن طريــق تعريــف فئتيــن (‪ :)Classes‬واحــدة لتمثيــل العقــدة (‪ )Node‬واألخــرى‬ ‫لتمثيــل القائمــة المرتبطــة نفســها‪.‬‬ ‫إليك كيفية إنشاء قائمة مرتبطة بسيطة في ‪ Python‬الكود البرمجي مصحوب بشرح للكود ‪.‬‬ ‫المثال التالي لعمل قائمة مرتبطة أليام األسبوع من االثنين الى األربعاء ‪:‬‬ ‫تعريف فئة العقدة (‪)Node Class‬‬ ‫هي فئة تمثل كل عقدة في القائمة المرتبطة‪.‬‬ ‫ تحتوي العقدة على بيانات (‪ )data‬ومرجع او عنوان إلى العقدة التالية (‪.)next‬‬ ‫ يتم تعيين (‪ )data‬و (‪ )next‬افتراضيا الى ‪.None‬‬ ‫تعريف فئة القائمة المرتبطة (‪)LinkedList Class‬‬ ‫هي فئة تمثل القائمة المرتبطة ‪.LinkedList‬‬ ‫ تحتوي على رأس القائمة (‪ )head‬الذي يشير إلي العقدة األولى في القائمة‪.‬‬ ‫ً‬ ‫ يتم تعيين (‪ )head‬افتراضيا الى ‪.None‬مما يعني أن القائمة تبدأ افتراضيا‪.‬‬ ‫الربنامج الرئييس‬ ‫ يتم إنشاء كائن ‪ ،LinkedList‬مما يعني أن القائمة المرتبطة تبدأ فارغة ‪.None‬‬ ‫ يتم إنشاء العقدة األولى التي تحتوي على "‪ "Monday‬وتعيينها كرأس القائمة‪.‬‬ ‫ يتم إنشاء العقدة الثانية التي تحتوي على "‪ "Tuesday‬وربطها بالعقدة األولى‪.‬‬ ‫ يتم إنشاء العقدة الثالثة التي تحتوي على "‪ "Wednesday‬وربطها بالعقدة الثانية‪.‬‬ ‫‪21‬‬ ‫‪55437757‬‬ ‫مصطفى بكري‬ ‫بايثونيستا الثانوية العامة‬ ‫علوم حاسب‪-12-‬تكنولوجي‬ ‫الفصل األول ‪ -‬هياكل البيانات المتقدمة‬ ‫طباعة محتويات القائمة المرتبطة‬ ‫ يبدأ الطباعة من رأس القائمة (‪.)head‬‬ ‫ يتم تكرار الطباعة حتى الوصول إلى نهاية القائمة عندما يكون ‪ node‬هو ‪None‬‬ ‫ يتم طباعة البيانات (‪ )data‬لكل عقدة‪ ،‬ثم االنتقال إلى العقدة التالية (‪.)next‬‬ ‫إضافة العقدة إيل قائمة مرتبطة ‪:‬‬ ‫‪ -‬مؤشر أول عقدة يشير إلي عنوان العقد الجديدة‪.‬‬ ‫‪ -‬يجب أن يشير مؤشر العقدة الجديدة (الثانية) إلي عنوان العقد الثالثة‪.‬‬ ‫‪ -‬بهذه الطريقة ال نضطر إلي إزاحة العناصر في حال إضافة عنصر جديد‪.‬‬ ‫علل ‪ :‬عملية الضافة في القوائم المرتبطة أسرع من القوائم المتسلسلة ؟‬ ‫ألنها تقتصر على تغيير قيم العناوين في العقد فقط‪.‬‬ ‫حذف العقدة من القائمة المرتبطة‬ ‫يتوجب علينا تغيير مؤشر العقدة السابقة لها لتشير إلي العقدة التالية للعقدة المحذوفة هي (بيانات عديمة الفائدة)‬ ‫‪22‬‬ ‫‪55437757‬‬ ‫مصطفى بكري‬ ‫بايثونيستا الثانوية العامة‬ ‫علوم حاسب‪-12-‬تكنولوجي‬ ‫الفصل األول ‪ -‬هياكل البيانات المتقدمة‬ ‫تطبيقات القوائم المرتبطة في علم الحاسوب‬ ‫‪ -‬تخصيص الذاكرة الديناميكية من خالل نظام التشغيل‪.‬‬ ‫‪ -‬أداء العمليات الحسابية الخاصة باألعداد الصحيحة الطويلة‪.‬‬ ‫‪ -‬االحتفاظ بجميع التطبيقات التي تعمل علي جهاز الحاسوب في قائمة مرتبطة‪.‬‬ ‫‪ -‬عرض الصور بشكل متتالي ببرنامج عارض الصور (‪.)image viewer‬‬ ‫‪ -‬الحركة بين الصفحة السابقة والتالية في متصفح الويب‪.‬‬ ‫ً‬ ‫‪ -‬ربط ملفات الصوت السابقة والتالية معا في مشغل الصوتيات‪.‬‬ ‫هياكل البيانات الثابتة وهياكل البيانات الديناميكية‬ ‫الديناميكية‬ ‫الثابتة‬ ‫ال نامج‬ ‫يتغ أثناء تنفيذ ب‬ ‫يمكن أن ي‬ ‫ثابت‬ ‫حجم الذاكرة‬ ‫مواقع عشوائية‬ ‫مواقع متجاورة‬ ‫طريقة التخزين‬ ‫أبطأ‬ ‫أرسع‬ ‫رسعة الوصول يإيل البيانات‬ ‫‪23‬‬ ‫‪55437757‬‬ ‫مصطفى بكري‬ ‫بايثونيستا الثانوية العامة‬ ‫علوم حاسب‪-12-‬تكنولوجي‬ ‫الفصل األول ‪ -‬هياكل البيانات المتقدمة‬ ‫الدرس الثالث ‪ -‬هياكل بيانات األشجار‬ ‫هياكل البيانات غري الخطية‬ ‫تمتاز بإمكانية ربط عناصرها بأكثر من عنصر آخر في نفس الوقت‪.‬‬ ‫سؤال ‪ :‬ما هي األمثلة على البيانات غير الخطية ؟‬ ‫األمثلة علي البيانات غير الخطية ‪ :‬األشجار (‪ )Trees‬والمخططات (‪.)Graphs‬‬ ‫الفروقات بين هياكل البيانات الخطية وغير الخطية‬ ‫غير الخطية‬ ‫الخطية‬ ‫يتم ترتيب عناصر البيانات بشكل خطي حيث يتم إحلاق كل عنصر يتم ترتيب عناصر البيانات بشكل غري خطي حبيث ميكن ربط عنصر‬ ‫بأكثر من عنصر‪.‬‬ ‫بعنصر سابق وعنصر تالي‪.‬‬ ‫توجد مستويات متعددة لتمثيل البيانات‬ ‫يوجد مستوي واحد لتمثيل البيانات‬ ‫يكون التنفيذ أكثر تعقيداً‬ ‫يتم التنفيذ بشكل أسهل‬ ‫‪24‬‬ ‫‪55437757‬‬ ‫مصطفى بكري‬ ‫بايثونيستا الثانوية العامة‬ ‫علوم حاسب‪-12-‬تكنولوجي‬ ‫الفصل األول ‪ -‬هياكل البيانات المتقدمة‬ ‫األشجار‬ ‫هي هياكل بيانات غير خطية ‪ ،‬وتتكون من مجموعة من العقد ترتب بشكل هرمي ويمكن لكل عقدة أن ترتبط بعقدة أو أكثر‪.‬‬ ‫سؤال ‪ :‬فيما تستخدم هيالك البيانات األشجار ؟‬ ‫تستخدم في العديد من مجاالت علوم الحاسوب مثل أنظمة التشغيل والرسومات وأنظمة قواعد البيانات واأللعاب والذكاء‬ ‫االصطناعي وشبكات الحاسوب‪.‬‬ ‫المصطلحات المستخدمة في هيكل بيانات الشجرة‬ ‫‪ -‬الجذر (‪ : )Root‬هي العقدة األولي وليس لها أب (‪ )Parent‬وتكون في المستوي األول من الشجرة‪.‬‬ ‫‪ -‬االبن (‪ : )Child‬هي العقدة المتصلة مباشرة بعقدة في مستوي أعلي‪.‬‬ ‫‪ -‬األب (‪ : )Parent‬هي العقدة التي لديها ابن واحد أو أكثر في مستوي أدنى‪.‬‬ ‫‪ -‬الورقة (‪ : )Leaf‬هي العقدة التي ال تحتوي علي أي عقد فرعية (ابن)‪.‬‬ ‫‪ -‬األشقاء (‪ : )Siblings‬هي جميع العقد التابعة لنفس العقد األصلية (األب)‪.‬‬ ‫‪ -‬األطراف (‪ : )Edges‬هي الروابط التي تربط بين عقد الشجرة‪.‬‬ ‫‪ -‬الشجرة الفرعية (‪ : )Sub-Tree‬هي األشجار الصغيرة التي يمكن العثور عليها داخل الشجرة الكبيرة‪.‬‬ ‫‪25‬‬ ‫‪55437757‬‬ ‫مصطفى بكري‬ ‫بايثونيستا الثانوية العامة‬ ‫علوم حاسب‪-12-‬تكنولوجي‬ ‫الفصل األول ‪ -‬هياكل البيانات المتقدمة‬ ‫رسم توضيحي للمصطلحات المستخدمة في هيكل بيانات الشجرة‬ ‫سؤال ‪ :‬قم برسم الشجرة التالية ‪:‬‬ ‫ الجذر (‪ :)Root‬العقدة العليا في الشجرة (مدير المشروع)‪.‬‬ ‫ األب (‪ :)Parent‬عقدة لها أبناء (مدير المشروع‪ ،‬مدير التطوير)‪.‬‬ ‫ األبناء (‪ :)Children‬العقد التي تتفرع من عقدة معينة (مدير التطوير‪ ،‬مدير التصميم‪ ،‬مدير‬ ‫االختبار هم أبناء مدير المشروع)‪.‬‬ ‫ العقد (‪ :)Nodes‬جميع العناصر في الشجرة (مدير المشروع‪ ،‬مدير التطوير‪ ،‬مدير التصميم‪ ،‬مدير‬ ‫االختبار‪ ،‬مطور‪ ،1‬مطور‪ ،2‬مطور‪ ،3‬مصمم‪ ،1‬مختبر‪ ،1‬مختبر‪ ،2‬متدرب)‪.‬‬ ‫ األطراف (‪ :)Leaves‬عقدة ليس لها أبناء (مطور‪ ،2‬مطور‪ ،3‬مصمم‪ ،1‬مختبر‪ ،1‬مختبر‪ ،2‬متدرب)‪.‬‬ ‫‪26‬‬ ‫‪55437757‬‬ ‫مصطفى بكري‬ ‫بايثونيستا الثانوية العامة‬ ‫علوم حاسب‪-12-‬تكنولوجي‬ ‫الفصل األول ‪ -‬هياكل البيانات المتقدمة‬ ‫مزيات هيكل بيانات الشجرة‬ ‫‪ -‬تستخدم لتمثيل التسلسل الهرمي‪.‬‬ ‫ً‬ ‫‪ -‬تتسم بالمرونة ‪ ،‬فمن السهل جدا إضافة أو إزالة عنصر‪.‬‬ ‫‪ -‬تتسم بسهول البحث عن عنصر داخل الشجرة‪.‬‬ ‫‪ -‬تبين العالقات الهياكل بين البيانات‪.‬‬ ‫هيكل بيانات الشجر في ‪Python‬‬ ‫ً‬ ‫ال تقدم لغة برمجة ‪ Python‬نوع بيانات محدد مسبقا لهيكل بيانات الشجرة ‪ ،‬ولكن يمكن إنشاؤه باستخدام القوائم‬ ‫(‪ )Lists‬والقواميس (‪.)Dictionaries‬‬ ‫‪27‬‬ ‫‪55437757‬‬ ‫مصطفى بكري‬ ‫بايثونيستا الثانوية العامة‬ ‫علوم حاسب‪-12-‬تكنولوجي‬ ‫الفصل األول ‪ -‬هياكل البيانات المتقدمة‬ ‫مثال ‪ :2‬باستخدام لغة الـ ‪ Python‬قوم بإنشاء شجرة عائلة بسيطة تتكون من جد وأب له ابن ‪ 1‬وابن ‪2‬‬ ‫وعم له ابن واحد ‪ ،‬ثم قم بطباعة الشجرة بشكل هرمي ‪ ،‬أرسم الشجرة وبين الجذر والعقد‪.‬‬ ‫في المثال السابق غير ما يلزم لطباعة الشجرة بشكل هرمي مع طباعة عدد العقد التي تنتمي لكل أب‬ ‫في األباء‬ ‫مثال ‪ : 3‬باستخدام لغة الـ ‪ Python‬قوم بإنشاء شجرة تنظيمية لفريق برمجي يتكون من مدير مشروع‬ ‫يترأس مدير للتطوير ومدير للتصميم بينما مدير التطوير يترأس مطور ‪ 1‬ومطور ‪ 2‬واخيرا مدير التصميم‬ ‫يترأس مصمم واحد فقط ‪ ،‬ثم قم بطباعة الشجرة بشكل هرمي ‪ ،‬أرسم الشجرة وبين الجذر والعقد‪.‬‬ ‫مثال ‪ :4‬باستخدام لغة الـ ‪ Python‬قوم بإنشاء شجرة قرارات مبسطة لنظام اختياري الجذر هو ‪:‬‬ ‫«السؤال‪ ،»1‬األجوبة تفرع إلى «الجواب‪ 1-‬نعم» أو «السؤال‪.»2‬‬ ‫«السؤال‪ »2‬يتفرع إلى «الجواب‪ 2-‬نعم» أو «الجواب‪ 2-‬ال»‪.‬‬ ‫ثم قم بطباعة الشجرة بشكل هرمي ‪ ،‬أرسم الشجرة وبين الجذر والعقد‪.‬‬ ‫‪28‬‬ ‫‪55437757‬‬ ‫مصطفى بكري‬ ‫بايثونيستا الثانوية العامة‬ ‫علوم حاسب‪-12-‬تكنولوجي‬ ‫الفصل األول ‪ -‬هياكل البيانات المتقدمة‬ ‫الشجرة الثنائية ‪Binary Tree‬‬ ‫هي حالة خاصة من هياكل بيانات األشجار ‪ ،‬وتتميز بوجود «ابنين» ‪ ،‬يطلق عليهما االبن األيمن (‪ )Right Child‬واالبن‬ ‫األيسر (‪.)Left Child‬‬ ‫أنواع هيكل بيانات الشجرة الثنائية‬ ‫رسم اهليكل‬ ‫الوصف‬ ‫النوع‬ ‫الشجرة الثنائية الممتلئة‬ ‫يوجد لكل عقدة إما ‪ 0‬أو ‪ 2‬أبناء‬ ‫‪eerT yraniB lluF‬‬ ‫تمتئل جميع المستويات بالكامل‬ ‫ئ‬ ‫الشجرة الثنائية الكاملة‬ ‫األخ ما أمكن‬ ‫ي‬ ‫باستثناء المستوي‬ ‫‪eerT yraniB etelpmoC‬‬ ‫ذلك (تملء من اليسار قدر االمكان أوال)‬ ‫جميع العقد الداخلية لها ابنان وجميع‬ ‫الشجرة الثنائية التامة‬ ‫االوراق ف ي نفس المستوي‪.‬‬ ‫‪eerT yraniB tcefreP‬‬ ‫سؤال ‪ :‬حدد نوع الشجرة الثنائية ‪ Binary Tree‬في كل من الهياكل التالية‪:‬‬ ‫)‬ ‫(‬ ‫ ‬ ‫)‬ ‫ ‬ ‫(‬ ‫) ‬ ‫( ‬ ‫‪29‬‬ ‫‪55437757‬‬ ‫مصطفى بكري‬ ‫بايثونيستا الثانوية العامة‬ ‫علوم حاسب‪-12-‬تكنولوجي‬ ‫الفصل األول ‪ -‬هياكل البيانات المتقدمة‬ ‫أمثلة عيل تطبيقات هياكل بيانات األشجار‬ ‫‪ -‬تخزين البيانات الهرمية ‪ ،‬مثل هياكل المجلدات‪.‬‬ ‫‪ -‬تعريف البيانات في لغة ‪.HTML‬‬ ‫‪ -‬تنفيذ الفهرسة في قواعد البيانات‪.‬‬ ‫شجرة القرار ‪Decision Tree‬‬ ‫شــجرة الق ـرار (‪ )Decision Tree‬تتشــابه نوعــا مــا مــع المخطــط االنســيابي (‪ ، )Flow Chart‬مــع مالحظــة أن المخططــات‬ ‫االنســيابية تســمح بالتك ـرارات‪.‬‬ ‫يطلق مصطلح "تعلم شجرة القرار" (‪ )Decision Tree Learning‬علي تطبيق أشجار القرار في علم الذكاء االصطناعي‬ ‫وتعلــم اآللــة‪.‬حيــث تســمي العقــد النهائيــة بالورقــة أو بعقــدة القـرار وتحتــوي عــادة علــي الحلــول وترتبــط كل عقــدة ‪ -‬باســتثناء‬ ‫األوراق ‪ -‬بشــرط منطقي يتفرع منه احتماالت اإلجابة بنعم أو ال‪.‬‬ ‫‪30‬‬ ‫‪55437757‬‬ ‫مصطفى بكري‬ ‫بايثونيستا الثانوية العامة‬ ‫علوم حاسب‪-12-‬تكنولوجي‬ ‫الفصل األول ‪ -‬هياكل البيانات المتقدمة‬ ‫الدرس الرابع ‪ -‬هياكل بيانات المخططات‬ ‫المخطط ‪Graph‬‬ ‫هــو أحــد أنــواع هيــاكل البيانــات التــي تتكــون مــن مجموعــة مــن العقــد (أو النقــاط أو الــرؤوس) ‪ ،‬ومجموعــة مــن‬ ‫الخطــوط أو (األضــاع أو األط ـراف) ‪ ،‬والتــي تربــط جميــع العقــد أو بعضهــا‪.‬‬ ‫مالحظات هامة ‪:‬‬ ‫ً‬ ‫‪1.‬يعتبر المخطط أكثر هياكل البيانات استخداما‪.‬‬ ‫‪2.‬الشجرة يمكن أن تكون مخطط وال يمكن اعتبار المخطط شجرة‪.‬‬ ‫سؤال ‪ :‬قارن بين األشجار والمخططات ؟‬ ‫الفروقات بين األشجار والمخططات‬ ‫المخططات‬ ‫األشجار‬ ‫ترتابط يف شكل شبكة‬ ‫ترتابط يف شكل هرمي‬ ‫ال توجد عقدة فريدة أو جذر‬ ‫توجد يف األشجار عقدة فريدة تسمي اجلذر‬ ‫ال توجد عالقة أب وأبناء بني العقد‬ ‫ترتبط العقد بعالقة أب وأبناء (‪)dlihC - tneraP‬‬ ‫املخططات هي هياكل أكثر تعقيداً‬ ‫تعترب األشجار هياكل أكثر بساطة مقارنة باملخططات‬ ‫‪31‬‬ ‫‪55437757‬‬ ‫مصطفى بكري‬ ‫بايثونيستا الثانوية العامة‬ ‫علوم حاسب‪-12-‬تكنولوجي‬ ‫الفصل األول ‪ -‬هياكل البيانات المتقدمة‬ ‫أنواع المخططات‬ ‫المخطط الموجه ‪Directed Graph‬‬ ‫ترتبــط العقــد بأضــاع موجهــة باتجــاه واحــد فقــط ‪ ،‬نســتطيع االنتقــال مــن العقــدة ‪ A‬إلــي العقــدة ‪B‬‬ ‫ ‬ ‫والعكس غير صحيح‪ (.‬اإلنتقال في اتجاه واحد )‬ ‫المخطط غري الموجه ‪Undirected graphs‬‬ ‫ال يكون لالرتباطات أي اتجاه ‪ ،‬نستطيع االنتقال من العقدة ‪ A‬إلي العقدة ‪ B‬والعكس أيضا صحيح‪.‬‬ ‫ ‬ ‫المخططات في حياتنا اليومية ‪:‬‬ ‫شــبكة الويــب العالميــة ‪ ،‬تعتبــر بمثابــة مخطــط موجــه ‪ ،‬فالعقــد هــي صفحــات الويــب واألضــاع الموجهــة هــي االرتباطــات‬ ‫التشــعبية ‪.‬‬ ‫تنقيب هياكل الويب (‪: )Web Structure Mining‬‬ ‫هو عملية اكتشاف المعرفة المفيدة من هياكل شبكة الويب العالمية من خالل االرتباطات التشعبية‪.‬‬ ‫األهمية النسبية (‪ )Relative Importance‬لصفحة الويب ‪:‬‬ ‫العالقــة الموجــودة بيــن صفحــات الويــب المختلفــة ‪ ،‬ويمكــن حســابها مــن خــال تكويــن مخطــط لهيــاكل بيانــات‬ ‫االرتباطــات التشــعبية‬ ‫‪Facebook‬‬ ‫ً‬ ‫الفيســبوك مثــال آخــر علــي هيــاكل المخطــط الغيــر موجــه ‪ ،‬فعندمــا نضيــف صديقــا يتوجــب عليــه قبــول طلبــك ‪ ،‬كمــا أن خوارزميــة‬ ‫اقترح األصدقاء في فيسبوك تستخدم نظرية المخطط (‪.)Graph Theory‬‬ ‫خرائط ‪Google‬‬ ‫تســتخدم خرائــط ‪ Google‬وجميــع التطبيقــات المماثلــة األخــرى المخططــات غيــر الموجهــة إلظهــار أنظمــة النقــل وحســاب‬ ‫أقصــر مســار بيــن موقعيــن‪.‬‬ ‫المخططات في ‪Python‬‬ ‫ً‬ ‫ال يوجد نوع بيانات معرف مسبقا في الـ ‪ ،Python‬ويمكننا إنشاء المخططات بواسطة القوائم والقواميس مثل األشجار‪.‬‬ ‫‪32‬‬ ‫‪55437757‬‬ ‫مصطفى بكري‬ ‫بايثونيستا الثانوية العامة‬