كلية دراسات الحاسوب والإحصاء
اهلا ومرحبا بك عزيزي الزائر في رحاب كلية دراسات الحاسوب والاحصاء
اذا كانت هذه زيارتك الاولى للمنتدى فتكرم بزيارة صفحة التعليمات او نتشرف بانضمامك
لنا كعضو مسجل في المنتدى


ملتقى طلاب كلية دراسات الحاسوب والاحصاء-جامعه كردفان
 
الرئيسيةبحـثالتسجيلدخول

شاطر | 
 

 ماهي المكدسات ..؟؟

استعرض الموضوع السابق استعرض الموضوع التالي اذهب الى الأسفل 
كاتب الموضوعرسالة
رافع حسين
المدير العام
المدير العام
avatar

عدد المساهمات : 208
النقاط : 2453
تاريخ التسجيل : 23/12/2011
العمر : 30
الموقع : الابيض -عروس الرمال-

مُساهمةموضوع: ماهي المكدسات ..؟؟   الخميس 19 أبريل 2012 - 16:25




[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذا الرابط]


ماهي المكدسات ..؟؟

هذا السؤال قد يراود الكثيرين منا .. ولم نعرف له اجابة قط... ولكن الان سوف نتعرف على المكدسات



المكدسات:


تعريفها: هي إحدى طرق تركيب البيانات التي تكون من نفس النوع.

مبدأ عملها: تتم عملية الإضافة والإزالة من طرف واحد .

من يدخل آخرا يخرج أولا LIFO.

طرق التعبير عن المكدسات

• يعبر عنها بمصفوفة أحادية .

• نحتاج إلى الإعلان عن متغير يعمل كمؤشر يشير إلى أخر عنصر موجود في المكدسة يسمى TOP ويمثل INDEX لها.

في البداية تكون قيمة TOP = -1


العمليات الممكنة عليها :

• عملية الإضافة PUSH

• عملية الحذف POP

• فحص هل المكدسة فارغة STACK EMPTY

• فحص هل المكدسة ممتلئة STACK FULL


الإضافة PUSH :

• عند القيام بعملية الإضافة لا بد من فحص المصفوفة هل هي ممتلئة أم لا .

• ملاحظة إذا كان عدد العناصر= N فإن موقع أخر عنصر= N-1

• لإضافة القيمة F :

IF TOP>=N-1 THEN

ممتلئة PRINT “OVERFLOW ”

ELSE

TOP=TOP+1

S(TOP)=F

END IF

الحذف pop :

• قبل الحذف لا بد فحص المصفوفة إذا ما كانت فارغة .

• يتم ذلك من خلال فحص قيمة TOP

IF TOP= -1 THEN

PRINT “EMPTY”

ELSE

F=S(TOP)



END IF


من أشهر التطبيقات على المكدسات :


• تستخدم لفحص التعابير الحسابية التي تحتوي على أقواس (مطابقة الأقواس).

• مثل (((5+2)*3)-1)

• المبدأ:

• قوس يسار :إضافة

• قوس يمين : إزالة

• تحليل النتيجة : 1- الانتهاء والمصفوفة (المكدسة )فارغة يكون التعبير صحيحا.

2-إذا تعرضنا لحالة إخراج pop وكانت المصفوفة فارغة

يكون عدد الأقواس اليمنى >من اليسرى.

3-الانتهاء والمصفوفة غير فارغة يكون عدد الأقواس اليسرى >من اليمنى.





الطوابير –الأرتالQUEUES

• التعريف: نوع من التراكيب لبيانات من نفس النوع.

• مبدأ العمل : تتم الإضافة من طرف (المؤخرة ) والحذف من الطرف الأخر .

من يدخل أولا يخرج أولا FIFO



العمليات على الطوابير


• الإضافة : تتم من المؤخرة

• الحذف تتم من المقدمة

• فحص الطابور :فارغ أم لا قبل الحذف

• فحص الطابور ممتلئ أم لا قبل الإضافة .


في البداية


• نجعل FRONT = 0

• REAR = -1


• يكون الطابور فارغا عندما FRONT > REAR

(عدد العناصر= صفر .)

• يكون الطابور ممتلئا عندما يكون عدد العناصر= سعته

• نحسب عدد العناصر كالتالي:

• N = REAR - FRONT +1

الإضافة


• قبل الإضافة لا بد من فحص إذا ما كان الطابور ممتلئا :

نجد عدد العناصر= N = REAR-FRONT+1

IF N= SIZE THEN

PRINT “FULL”

ELSE

REAR=REAR+1

Q(REAR)= F

END IF





الحذف من الطابور


• قبل الحذف نفحص هل هو فارغ أم لا وذلك عن طريق فحص عدد العناصر أو FRONT > REAR

• IF FRONT > REAR THEN

• PRINT “EMPTY”

• ELSE

• F=Q(FRONT)

• FRONT=FRONT+1

• END IF

قد نصل إلى حالة :

• مثلا نريد أن نضيف عنصرا إلى المصفوفة المجاورة.

• نفحص هل ممتلئة حسب عدد العناصر :الجواب لا !

• نزيد قيمة REAR=REAR+1

• نحصل على القيمة 5 للمتغير REAR

• عندما نقوم بإدخال القيمة للمتغير Q(REAR) أي Q(5)

• يظهر خطأ لأن موقع أخر عنصر هو Q(4) !

من هنا نتجت فكرة الطوابير الدائرية .



الطوابير الدائرية

• نحتاج إلى عداد C ليحسب عدد العناصر المدخلة إلى الطابور

• نصفر قيم المتغيرات FRONT =0 ,REAR=0 , C=0

• نستخدم العداد لفحص حالة الطابور ممتلئ أم لا .

عند الإضافة نستخدم الجملتين :

REAR = (REAR+1) MOD 5

C=C+1

عند الحذف نستخدم الجملتين :

FRONT= (FRONT+1) MOD 5

C=C-1

وذلك حتى تبقى قيم FRONT ,REAR محصورة بين (0 و4 )


ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ

الله اكبر

ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذا الرابط]
الرجوع الى أعلى الصفحة اذهب الى الأسفل
http://comsat.hooxs.com
 
ماهي المكدسات ..؟؟
استعرض الموضوع السابق استعرض الموضوع التالي الرجوع الى أعلى الصفحة 
صفحة 1 من اصل 1

صلاحيات هذا المنتدى:لاتستطيع الرد على المواضيع في هذا المنتدى
كلية دراسات الحاسوب والإحصاء :: القسم الاكاديمي :: كتب عن الحاسوب-
انتقل الى: