Posts Tagged Doubly Linked List

12- الخوارزميات وبنى المعطيات – المكدس Algorithms and Data Structure – Stack

facebook-groupالسلام عليكم ورحمة الله وبركاته

Algorithms and Data Structure – Stack
الخوارزميات وبنى المعطيات – المكدس

السلام عليكم ورحمة الله وبركاته

سنتحدث في هذه الحلقة عن احد بنى المعطيات المهمة جدا, الا وهي المكدس Stack

المكدس Stack: هو نمط معطيات مجردabstract data type  (ADT) ، شائع الاستخدام في معظم لغات البرمجة. يدعى المكدس لانه عبارة عن مجموعة من العناصر التي تتكدس فوق بعضها البعض، على سبيل المثال – مجموعة أوراق أو كومة من لوحات مكدسة فوق بعضها البعض ، إلخ.

stack_example

في اي مثال حقيقي للمكدس stack نلاحظ ان العمليات متاحة من نهاية واحدة فقط. على سبيل المثال ، يمكننا وضع أو إزالة بطاقة أو لوحة من الطرف العلوي من المكدس فقط. وبالمثل ، يتيح مفهوم المكدس البرمجي Stack ADT امكانية تنفيذ جميع العمليات من جهة واحدة فقط.  اي انه لا يمكننا الوصول إلا إلى العنصر العلوي للمكدسstack .

هذه الميزة تجعله المكدس من انماط بنية المعطيات التي تدعى باسم LIFO وهي اختصار للعبارة

Last-In-First-Out

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

في مصطلحات المكدس ، تدعى عملية الإدراج عملية PUSH وتسمى عملية الإزالة عملية POP.

 

تمثيل المكدس Stack Representation

الشكل ادناه عبارة عن تمثيل لمكدس stack  مع العمليات المتاحة عليه
stack_representation.jpg

يمكن تنفيذ مكدس بواسطة احد بنى المعطيات التالية Array و Structure و Pointer و Linked List.

كما انه يمكن ان يكون حجم المكدس ثابتًا أو متغيرا بشكل ديناميكي

ضمن هذه الدرس, سنقوم بتمثيل وتنفيذ المكدس باستخدام المصفوفات ، مما يجعله مكدس بحجم ثابت.

 

العمليات الاساسية Basic Operations

قد تتضمن العمليات التي يتم اجرائها على المكدس تهئيته قبل استخدامه.

ولكن بشكل عام – اذا تجاوزنا هذه التفاصيل – فإن هنالك عمليتين اساسيتين في المكدس

push () – دفع (تخزين) عنصر في المكدس.

pop () – إزالة (الوصول إلى) عنصر من المكدس.

لكي يتم استخدام المكدس بكفائه ، نحتاج إلى التحقق من حالة المكدس أيضًا. لنفس الغرض ، يتم إضافة الاجرائيات والوظائف التالية إلى المكدس  –

peek () – الحصول على عنصر البيانات العلوي من المكدس ، دون إزالته من المكدس.

isFull () – تحقق مما إذا كان المكدس ممتلئأ.

isEmpty () – تحقق من أن المكدس فارغ.

في كل الاحوال, يتم الاحتفاظ بمؤشر يشير الى اخر عنصر تمت اضافته الى المكدس.
أولا يجب أن نتعلم بعض إجراءات المهمة لوظائف المكدس –

Peek()

خوارزمية هذه الوظيفة كالتالي:

peek.JPG

مثال على تنفيذ هذا التابع – الوظيفة – بلغة C

peek-ex

IsFull()

خوارزمية هذه الوظيفة كالتالي:

isfull.JPG

مثال على تنفيذ هذا التابع – الوظيفة – بلغة C

isfull-ex

isEmpty()

خوارزمية هذه الوظيفة كالتالي:

isempty

مثال على تنفيذ هذا التابع – الوظيفة – بلغة C

isempty-ex.JPG

عملية الاضافة Push Operation

تعرف عملية اضافة عنصر بيانات جديد الى المكدس بعمليةPush . تتضمن الخطوات التالية:
الخطوة 1 – التحقق فيما اذا كان المكدس ممتلئ.

الخطوة 2 – إذا كان المكدس ممتلئ ، ينتج عنها خطأ والخروج.

الخطوة 3 – إذا لم يكن المكدس ممتلئ ، قم بزيادة العداد ليؤشر الى المساحة الفارغة التالية.

الخطوة 4 – إضافة عنصر بيانات إلى مؤشر المكدس –  يؤشر الى اعلى المكدس

الخطوة 5 – إرجاع حالة النجاح.

 

خوارزمية عملية الاضافة Algorithm for PUSH operation

فيما يلي مثال على خوارزمية الاضافة

push algorithm.JPG

مثال على تنفيذ هذه العملية بلغة C

push algorithm-ex.JPG

عملية اخراج عنصر من المكدس POP Operation

تعرف عملية الوصول الى العنصر الاخير في المكدس, وازالته من المكدس  باسم عملية Pop

عند تنفيذ وبرمجة هذه العملية باستخدام بنى المعطيات array – مصفوفة – لا تتم إزالة عنصر البيانات فعليًا ، بدلاً من ذلك يتم تقليل عداد المؤشر ليؤشر الى موضع أدنى في المكدس حيث القيمة التالية. ولكن عند  تنفيذ هذه العملية في بنية معطيات مثل القائمة المتصلة Linked List , عندها يقوم التابع  pop () بالفعل بإزالة عنصر البيانات وإلغاء تخصيص مساحة الذاكرة.

قد تتضمن عملية Pop الخطوات التالية –

الخطوة 1 – التحقق من أن المكدس فارغ.

الخطوة 2 – إذا كان المكدس فارغ ، ينتج عنها خطأ وتنتهي.

الخطوة 3 – إذا لم يكن المكدس فارغ، يتم الوصول إلى عنصر البيانات الذي يشير إليه مؤشر المكدس

الخطوة 4 – تقلل عداد مؤشر المكدس بمقدار 1 ليؤشر الى القيمة التالية.

الخطوة 5 – إرجاع حالة النجاح.

خوارزمية عملية pop

خوارزمية هذه الوظيفة كالتالي:

pop algorithm.JPG

مثال على تنفيذ هذا التابع – الوظيفة – بلغة C

pop algorithm-ex.JPG

نتابع ان شاء الله حديثا في الحلقة القادمة عن بنى المعطيات الرتل queue

والى ذلك الحين استودعكم الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

 

الترجمة المصطلح
بنى المعطيات, او هياكل المعطيات Data Structure
الخوارزميات Algorithm
قائمة متصلة Linked list
عملية Operation
عقدة Node
رابط Link
زمن التنفيذ Running time/execution time
البحث عن المعطيات Data search
سرعة المعالجة Processor speed
الطلبات المتعددة Multiple Request
التعقيد الزمني Time complexity
التعقيد المكاني Space complexity
التحليل المقار Asymptotic Analysis
أفضل حالة Best case
الحالة الوسيطية Average case
اسوء حالة Worst case

 

References
https://www.tutorialspoint.com/data_structures_algorithms/

 

 

 

Advertisements

, , , , , , , , , , , , , , , ,

أضف تعليق

11- الخوارزميات وبنى المعطيات – القائمة المتصلة الدائرية Algorithms and Data Structure – Circular Linked List

facebook-groupالسلام عليكم ورحمة الله وبركاته

Algorithms and Data Structure – Circular Linked List
الخوارزميات وبنى المعطيات –  القائمة المتصلة الدائرية

القائمة المرتبطة دائريا circular linked list: عبارة عن نسخة معدلة من القائمة المتصلة linked list بحيث يشير الأول الى العنصر الاخير, وكذلك يشير العنصر الاخير الى العنصر الاول.

يمكن لكلا النوعين: “القائمة المتصلة المفردة singly lined list والقائمة المتصلة مزدوجة الارتباط doubly linked list ان تكونا دائريتان بحسب الوصف السابق.

 

القائمة المتصلة  – الدائرية Singly linked list as circular

في القائمة المتصلة احادية الاتجاه, يجب ان يشير المؤشر التالي للعنصر الاخير next pointer of last item الى اول عنصر – عقدة ضمن القائمة.

singly_circular_linked_list.jpg

القائمة المزدوجة الارتباط الدائرية doubly linked list as circular

يجب ان يشير رابط التالي next link للعنصر الاخير الى العنصر الاول في القائمة, وان يشير رابط السابق prev link للعنصر الاول الى اخر عنصر ضمن القائمة.

doubly_circular_linked_list.jpg

وبذلك نحصل على قائمة متصلة دائرية يمكن التجوال فيها باتجاهين

من الاشكال السابقة, نلاحظ بأن هنالك عدة نقاط مهمة يجب التنويه اليها:

في كلا نوعي القوائم المتصلة – المفردة والمزدوجة: نجد بأن رابط التالي next  للعقدة الاخيرة في القائمة يشير الى العنصر الاول في القائمة.

اما في القائمة مزدوجة الارتباط فإن رابط السابق prev link للعنصر الاول يؤشر الى العنصر الاخير ضمن السلسلة

العمليات الاساسية

فيما يلي عدد من العمليات الاساسية المهمة المدعومة ضمن القوائم المتصلة الدائرية:

  • الاضافة insert : اضافة عنصر عند بداية القائمة.
  • الحذف delete: حذف عنصر من بداية القائمة list .
  • العرض display : عرض عناصر القائمة list .

عملية الاضافة insertion operation

الكود التالي يوضح عملية الاضافة الى بداية القائمة المتصلة الدائرية الاحادية

مثال

insert operation.JPG

عملية الحذف deletion operation

الكود التالي يمثل عملية حذف العنصر الاول من قائمة متصلة احادية الاتجاهsingle linked list

delete operation.JPG

عملية عرض القائمة display list operation

الكود التالي يمثل عملية عرض عناصر قائمة متصلة احادية الاتجاهsingle linked list

display op.JPG

وبهذا ننهي حديثنا عن القوائم المتصلة, لننتقل للحديث عن موضوع شيق الا وهو بنية المطيات المكدس Stack data structure

والى ذلك الحين استودعكم الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

 

الترجمة المصطلح
بنى المعطيات, او هياكل المعطيات Data Structure
الخوارزميات Algorithm
قائمة متصلة Linked list
عملية Operation
عقدة Node
رابط Link
زمن التنفيذ Running time/execution time
البحث عن المعطيات Data search
سرعة المعالجة Processor speed
الطلبات المتعددة Multiple Request
التعقيد الزمني Time complexity
التعقيد المكاني Space complexity
التحليل المقار Asymptotic Analysis
أفضل حالة Best case
الحالة الوسيطية Average case
اسوء حالة Worst case

 

References
https://www.tutorialspoint.com/data_structures_algorithms/

 

 

 

, , , , , , , , , , , , ,

أضف تعليق

10- الخوارزميات وبنى المعطيات – القائمة المتصلة مزدوجة الارتباط Algorithms and Data Structure – Linked List

facebook-groupالسلام عليكم ورحمة الله وبركاته

Algorithms and Data Structure – Doubly Linked List
الخوارزميات وبنى المعطيات –  القائمة المتصلة المزدوجة الارتباط

القائمة المتصلة المزدوجة الارتباط: عبارة عن نسخة معدلة من القائمة المزودجة, بحيث تمكن التجوال باتجاهين – للامام والخلف – بسهولة التجوال المتواجد ضمن القائمة المتصلة linked list .

فيما يلي قائمة بالمصطلحات المهمة فيما يتعلق بالقائمة المتصلة المزدوجة الارتباط Doubly Linked List:

  • الرابط Link: يمكن لكل رابط – من روابط القائمة المتصلة – ان يخزن المعطيات, وتدعى هذه المعطيات باسم العنصر element.
  • التالي Next: يحوي كل رابط Link ضمن القائمة المتصلة على رابط للعنصر التالي مباشرة, ويدعى هذا الرابط باسم التالي Next.
  • التالي Prev: يحوي كل رابط Link ضمن القائمة المتصلة على رابط للعنصر السابق مباشرة, ويدعى هذا الرابط باسم التالي Prev.

 

تمثيل القائمة المتصلة المزدوجة الارتباط doubly linked list representation

doubly_linked_list

فيما يلي بعض النقاط الهامة التي يجدر الانتباه اليها في القائمة المتصلة المزدوجة الارتباطdoubly linked list :

  • تحوي على رابط يدعلى الرابط الاول first link, وعلى رابط يدعى الرابط الاخير last link.
  • كل رابط Link يحوي على حقل معطيات – او عدة حقول – وعلى حقلين خاصين بالروابط links يدعيان التالي next والسابق Prev.
  • يحوي العنصر الاخير على رابط next يشير الى القيمة Null معلنا بذلك نهاية القائمة.

العمليات الأساسية:

فيما يلي قائمة بالعمليات الاساسية المدعومة ضمن القائمة المتصلة:

  • الاضافة insertion : اضافة عنصر الى بداية القائمة المتصلة
  • الحذف deletion: حذف عنصر من بداية القائمة المتصلة
  • الاضافة للاخير insert last: اضافة عنصر الى اخر القائمة المتصلة
  • حذف العنصر الاخير delete last: حذف عنصر من نهاية السلسلة.
  • الاضافة بعد عنصر insert after: اضافة عنصر بعد عنصر محدد من القائمة>
  • الحذف delete : حذف عنصر من القائمة باستخدام مفتاح محددkey .
  • العرض قدما Display forward: عرض كامل السلسلة من البداية للنهاية
  • العرض بشكل تراجعي display backward: عرض كامل محتويات السلسلة بشكل تراجعي من النهاية للبداية.

 

عملية الاضافة Insertion Operation

الكود التالي يبين عملية اضافة عنصر الى بداية القائمة المتصلة المزدوجة الارتباط doubly linked list

مثال:

insert begining 1.JPG

عملية الحذف Deletion Operation

الكود التالي يمثل عملية الحذف لعنصر من بداية القائمة المتصلة المزدوجة الارتباط

مثال:

delete example.JPG

الاضافة الى نهاية السلسلة Insertion at the End of an doubly linked list

الكود ادناه يمثل عملية اضافة عنصر الى نهاية قائمة متصلة مزدوجة.

insert at the end of the list.JPG

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

كتمرين, بامانكم كتابة خوارزمية تنفيذ بقية العمليات على هذا النوع من القوائم

نلتقي في الدرس القادم للحديث عن القوائم المتصلة الدائرية

circular linked list

والى ذلك الحين استودعكم الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

 

الترجمة المصطلح
بنى المعطيات, او هياكل المعطيات Data Structure
الخوارزميات Algorithm
قائمة متصلة Linked list
عملية Operation
عقدة Node
رابط Link
زمن التنفيذ Running time/execution time
البحث عن المعطيات Data search
سرعة المعالجة Processor speed
الطلبات المتعددة Multiple Request
التعقيد الزمني Time complexity
التعقيد المكاني Space complexity
التحليل المقار Asymptotic Analysis
أفضل حالة Best case
الحالة الوسيطية Average case
اسوء حالة Worst case

 

References
https://www.tutorialspoint.com/data_structures_algorithms/index.htm

 

 

 

, , , , , , , , , , , , ,

أضف تعليق