Data Structure using C++ PDF

‫هـيـاكـل الـبـيــانـات‬ ‫‪Data Structure using C++‬‬ ‫إعداد‬ ‫دكتور ‪ /‬كمال حفنى‬  ‫المقدمة‬ ‫عملية تمثيل البيانات في ذاكرة الحاسوب بصورة صحيحة تؤدي دورا مهما في‬ ‫رفع اداء البرامج ا...

‫هـيـاكـل الـبـيــانـات‬ ‫‪Data Structure using C++‬‬ ‫إعداد‬ ‫دكتور ‪ /‬كمال حفنى‬  ‫المقدمة‬ ‫عملية تمثيل البيانات في ذاكرة الحاسوب بصورة صحيحة تؤدي دورا مهما في‬ ‫رفع اداء البرامج المخصصة للتعامل مع البيانات‪.‬‬ ‫يمكن تمثيل البيانات في ذاكرة الحاسوب باستخدام هياكل بيانية مختلفة لكل منها‬ ‫مايميزه‪.‬ويعد اختيار الهيكل المناسب لتمثيل البيانات معتمدا بشكل اساسي علي‬ ‫المساحة التخزنية والسرعه في التعامل مع البيانات المخزونه داخل الهيكل‬ ‫لذلك يجب اختيار هيكل البيانات الذي يقلل من الهدر في ذاكرة الحاسوب وكتابة‬ ‫الخوارزميات التي توفر السرعة عند التعامل مع البينات المخزونة‬  ‫البيانات‪:‬‬ ‫عبارة عن مجموعة من الرموز او الحروف اواالرقام او الصور ليس لها معني محدد‬ ‫مثال علي البيانات ‪ :‬أسماء المستخدمين لتطبيق ما والبريد الخاص بهم وعناوينهم‬ ‫وأسماء األقسام والمنتجات وكل شيء في التطبيق‬ ‫المعلومات ‪:‬‬ ‫المعالجة الدقيقية للبيانات واخراجها علي شكل حقائق ذات معني‪.‬‬ ‫انواع البيانات األساسية ) ‪(int , float , char, double, void‬‬ ‫‪Integer‬‬ ‫وهو العدد الصحيح وهو عدد يمكن كتابته بدون كسور أو فواصل عشرية على سبيل‬ ‫المثال ( ‪) 3 ,2 ,1‬‬  ‫‪Float‬‬ ‫العدد الفاصل العائم هو العدد العشري الذي يحتوي على عالمة عشرية‬ ‫‪Character‬‬ ‫كل رقم وحرف وعالمة هم في النهاية ‪Character‬على سبيل المثال ‪A, B, C, 1,‬‬ ‫‪# ,@ ,- ,2, 3‬‬ ‫( فمثال في لغة ‪C ++‬تستخدم التعريفات) ‪:‬‬ ‫; ‪Int x‬‬ ‫; ‪Float y‬‬ ‫; ‪Char A‬‬ ‫‪Boolean‬‬ ‫في علوم الكمبيوتر ‪Boolean Data Types‬هي قيمة من قيمتين محتملين وفي‬ ‫الغالب يكونوا ‪True‬و ‪False‬‬  ‫تعريف هياكل البيانات) ‪(Data structures‬‬ ‫هى دراسة طرق جمع وتمثيل البيانات في ذاكرة الحاسوب عن طريق بناء‬ ‫هياكل بيانات تدعم نوع البيانات المراد تخزنها وهي هياكل تخصصية بتنظيم‬ ‫البيانات ومعالجتها واسترجاعها ‪.‬‬ ‫على الرغم من وجود العديد من أنواع الهياكل األساسية والمتقدمة‪ ،‬فقد صمم كل‬ ‫نوع لترتيب البيانات بطريقة تناسب غر ً‬ ‫ضا محددًا بحيث يمكن الوصول إلى‬ ‫هذه البيانات والعمل معها بطرق مناسبة وسهله‪،‬‬ ‫عند دراسة هياكل البيانات يجب االخذ بعاملين مهمين وهما المساحة التخزينية (‬ ‫) ‪space memory‬والسرعة او عامل الزمن )‪( time‬في التعامل مع البيانات‬  ‫انواع هياكل البيانات‬ ‫الفيزيائي )‪(Physical structure‬‬ ‫تقسم هياكل البيانات الى قسمين اساسيين وهما الهيكل‬ ‫يقصد بالهيكل الفيزيائي عملية تمثيل البيانات في ذاكرة‬ ‫والمنطقي )‪(Logical structure‬‬ ‫الحاسوب )‪(Memory‬اما الهيكل المنطقي فيمثل نظرة المبرمج لشكل البيانات المخزونة‬ ‫داخل الهيكل البياني‪.‬‬  ‫ويمكن تقسيم انواع هياكل البيانات علي حسب خصائصها الى هياكل‬ ‫البيانات الخطية وهياكل البيانات الغير خطية‬ ‫هياكل بيانات خطية ‪:Linear Data Structure‬‬ ‫تحتوي بنية البيانات الخطية على عناصر بيانات مرتبة بشكل تسلسلي‬ ‫مما يعني أنه إذا أردنا زيارة العنصر رقم ‪ ، 100‬فعليه المرور عبر‬ ‫العناصر الـ ‪ 99‬السابقة‬  ‫وتقسم هياكل البيانات الي هياكل البيانات الثابته وهياكل البيانات الديناميكية‪:‬‬ ‫هياكل البيانات الثابتة ‪:‬‬ ‫لها أحجام وهياكل ومواقع ذاكرة ثابتة في وقت الترجمة (‪.)compile time‬‬ ‫مثال ‪ :‬المصفوفات ‪.Array‬‬ ‫هياكل البيانات الديناميكية‪:‬‬ ‫لها أحجام وهياكل ومواقع ذاكرة و يمكن أن تتقلص أو تتوسع حسب االستخدام‬ ‫في وقت الترجمة (‪. )compile time‬‬ ‫مثال ‪ :‬القوائم ‪ Linked List‬والمكدس ‪ Stack‬والطوابير ‪.Queue‬‬  ‫هياكل البيانات الغير خطية ‪Non - Linear Data Structure‬‬ ‫ال تحتوي بنية البيانات غير الخطية على تسلسل محدد لالتصال بجميع عناصرها ويمكن أن‬ ‫يكون لكل عنصر مسارات متعددة لالتصال بالعناصر األخرى‬ ‫هياكل البيانات هذه ليست سهلة التنفيذ ولكنها أكثر كفاءة في استخدام ذاكرة الكمبيوتر‪.‬‬ ‫أمثلة على هياكل البيانات غير الخطية هي الشجرة ‪tree‬والرسوم البيانية ‪Graph‬‬ ‫تتناسب أنواع مختلفة من هياكل البيانات مع أنواع مختلفة من‬ ‫التطبيقات ‪ ،‬حيث أن هياكل البيانات هي طريقة متخصصة بحفظ البيانات‬ ‫وتنظيمها ومعالجاتها واستعادتها‬ ‫امثلة على انواع هياكل البيانات ‪:‬‬ ‫ ‪Array‬‬ ‫ ‪Linked List‬‬ ‫ ‪Stack‬‬ ‫ ‪Queue‬‬ ‫ ‪Tree‬‬ ‫ ‪Graph‬‬  ‫العمليات الرئيسية علي هياكل البيانات‬ ‫ البحث‪ :‬يمكننا البحث عن أي عنصر في بنية البيانات‪.‬‬ ‫ الفرز‪ :‬يمكننا فرز عناصر بنية البيانات إما بترتيب تصاعدي أو تنازلي‪.‬‬ ‫ اإلدراج‪ :‬نستطيع إدراج العنصر الجديد في بنية البيانات‪.‬‬ ‫ التحديث‪ :‬كما يمكننا تحديث العنصر‪ ،‬أي يمكننا استبدال العنصر بعنصر آخر‪.‬‬ ‫ الحذف‪ :‬يمكننا كذلك إجراء حذف للبيانات‪.‬‬  ‫تعريف الخوارزمية ‪:‬‬ ‫هي مجموعة من الخطوات المنطقية المتسلسلة التي يتم تطبيقها على‬ ‫مجموعة من البيانات المتاحة والتي تعرف بـ المدخالت ‪،Inputs -‬‬ ‫لتحصل منها على نتيجة (حل المشكلة) وهو ما يعرف بـ المخرجات –‬ ‫‪Output‬‬  ‫خصائص الخوارز ٌميات‬ ‫خطوات الخوارز ٌميه مرتبه‪.‬‬ ‫‪.1‬‬ ‫خطواتها منت ٌهيه ‪.‬‬ ‫‪.2‬‬ ‫سيطه‬ ‫خطوات الخوارز ٌميه تنفذ اعمال ب ٌ‬ ‫‪.3‬‬ ‫طريقة الحل ٌيجب ان تكون عامه‪.‬‬ ‫ٌ‬ ‫‪.4‬‬ ‫( ‪O )n‬درجة تعقيد الخوارز ٌمية ‪:‬‬ ‫عدد العمليات التي تنفذها للوصول الي الحل وليس الزمن الفعلي للتنفيذ طبقا للقواعد االتية‪:‬‬ ‫‪ -1‬العمليات االولية مثل الجمع والطرح والضرب والقسمة ‪.‬‬ ‫‪ -2‬جمل االختيار مثل ‪. if else‬‬ ‫‪ -3‬جمل االختيار التراجعية‪.‬‬ ‫‪ -4‬جمل التكرار مثل ‪. for‬‬ ‫‪ -5‬جمل التكرار المتداخلة ‪.‬‬ ‫‪ -6‬الجمل المتتابعة ‪.‬‬  ‫أهمية هياكل البيانات‬ ‫‪.1‬سرعة المعالجة للبيانات‬ ‫‪.2‬سهولة الوصول والبحث عن البيانات‬ ‫‪.3‬االستخدام الفعال للذاكرة‬ ‫‪.4‬الحصول على الترتيب المنهجي السليم للبيانات‬ ‫‪.5‬تسريع تنفيذ العمليات وتوفير الوقت والمساحة داخل ال ‪Memory‬‬ ‫‪.6‬إستهالك موارد أقل لتنفيذ العمليات التي تتم على البيانات (‪) Edit, Delete, Update‬‬ ‫‪.7‬يمكن دمجها كحزمة (‪ )package‬واحدة في مكتبة ويمكن استخدام هذه المكتبات في مواقف مختلفة‬ ‫ً‬ ‫حلوال متعددة لمشكلة معينة‬ ‫‪.8‬تتيح‬  ‫الباب الثاني‬ ‫العمليات علي المصفوفات والقوائم‬  ‫‪.1‬المصفوفات ‪Array‬‬ ‫هي مجموعة من العناصر الموجودة بجانب بعضها البعض من نفس النوع في مكان‬ ‫واحد ويمكن الوصول لكل عنصر من العناصر عن طريق ال ‪ Index‬الخاص به‬  ‫مثال‪ :‬مجموعة من األعداد الصحيحة بحجم ‪.10‬يمكن تصور تنظيم العناصر على النحو التالي‪:‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪2‬‬ ‫‪3‬‬ ‫‪4‬‬ ‫‪5‬‬ ‫‪6‬‬ ‫‪7‬‬ ‫‪8‬‬ ‫‪9‬‬ ‫‪25‬‬ ‫‪13‬‬ ‫‪0‬‬ ‫‪-16‬‬ ‫‪14‬‬ ‫‪38‬‬ ‫‪-65‬‬ ‫‪42‬‬ ‫‪97‬‬ ‫‪38‬‬ ‫يشار إلى المركز األول بالفهرس ‪.0‬في مثل هذه الحالة ‪ ،‬يمكن الوصول إلى القيمة ‪ 14‬باعتبارها [‪[4‬‬ ‫ويتم اإلعالن عن الصف فى لغة ‪ C ++‬بالصورة اآلتية‪:‬‬ ‫[طول الصف] < اسم الصف > < نوع بيانات الصف>‬ ‫مثال‪ int x; :‬فى هذا المثال تم اإلعالن عن صف طوله خمس عناصر من نوع رقم صحيح‬ ‫وله اسم ‪.x‬‬ ‫نالحظ تتابع األرقام ‪ 4 ,3 ,2 ,1 ,0‬هذه األرقام تسمى فهرس الصف وتستخدم هذا الفهرس مع‬ ‫اسم الصف فى التعامل مع عناصر الصف‪.‬‬  ‫كيفية تخزين الصف داخل ذاكرة الجهاز‬ ‫يتم تخزين الصف داخل ذاكرة الجهاز فى تتابع حقيقي حيث يتم حجز مساحة داخل‬ ‫الذاكرة تساوى حاصل ضرب طول الصف فى الوحدة التخزينية لنوع عناصر الصف‪.‬‬ ‫مثال‪:‬‬ ‫اذا أردنا حساب حجم الذاكرة المطلوب لتخزين هذا الصف‪:‬‬ ‫الحجم المطلوب = طول الصف × الوحدة التخزينية لنوع البيانات‬ ‫طول الصف = ‪ 5‬عناصر‬ ‫الوحدة التخزينية للنوع بايت ‪int = 4‬‬ ‫الحجم المطلوب = ‪20 = 4×5‬بايت‬  ‫تطبيق عملي ‪:‬‬ ‫طباعه عناصر صف‬ ‫> ‪#include x [ j ]; for( j = 9 ; j >= 0 ; j -- ) cout tar; //33 for(int i=0;i