מאגר טיפים להוראת עיצוב תכנה

תור דו-שלבי

פתרון שאלה 14 מבחינת בגרות תשנ"ו

יפית כהן, עירוני ג' בית חינוך, ירושלים

 

את התור הדו-שלבי  כדאי לממש כך שיהיה לנו קל לפתור את כל השאלה בקלות.

זאת אומרת שיש לקרוא את כל השאלה עד הסוף ורק אז להחליט איך לייצג את טיפוס הנתונים כך שיהיה לנו קל לענות על הסעיפים הנוספים.

אם נבחר ליצג את התור הדו-שלבי בצורה הכי פשוטה כך:

Type

Two-level-Queue=record

                                       Q1,Q2 : Queue-type;

End;             

הייצוג אומנם פשוט אך מה קורה עם הממוש?

הפעולה השלישית שהתבקשנו לממש ספור-איברים-בתור-דו-שלבי היא פעולה מסובכת למימוש עבור ייצוג מסוג תור. מכיון שאנו נצטרך תור עזר, אין לנו ברירה אלא להוציא מהתור המקורי את כל האיברים שבו כדי למנות אותם, אח"כ להחזירם לתור המקורי בלי לפגוע בסדר. מימוש כזה הוא ארוך ומיגע.

לכן  יהיה עדיף לנו לממש אולי כך, ע"י שתי רשימות:

Type

Two-level-Queue=record

                                       Q1,Q2 : list-type;

End;             

 

במימוש כזה לא היה לנו צורך להוציא את כל האיברים מהתור כדי למנות אותם אלא פשוט לעבור על כל האברים מהעוגן ועד סוף הרשימה.

והמימוש יראה כך: (נשתמש בפונקצית עזר num_element המונה את מספר האיברים שיש ברשימה.)

 

Functin TLQ_num_element (T :Two_Level_Queue; y:integer):integer;

Begin

         If y=1 then TLQ_num_element:=num_element(T.Q1)

         Else TLQ_num_element:= num_element(T.Q2);

END;

 

function num_element (L:list_type):integer;

var

         p:pos_type;        

         mone:integer;

begin

         mone:=0;

         p:=list_anchor(L);

         p:=list_next(L,p);

         while p<> list_end(L) do

         begin

               mone:=mone+1;                            

               p:=list_next(L,p);

         end;

         num_elementL:=mone;

end;

מה קורה למי שלא יודע למנות את מספר האיברים ברשימה?

צריך לחשוב על פיתרון כזה שיאפשר לו בשליפת נתון לאחזר את מספר האיברים לכל תור, כך:

Type

         Two-level-Queue=record

                                       Q1,Q2 : Queue-type;

                           Num1, num2 : integer; { { משתנים שיכילו את מספר האיברים בתורבהתאמה

End;

 

 נציג את כל הפתרון:

implementation

 

procedure TLQ_init(var T: Two_Level_Queue);

begin

         Queue_init(T.Q1);

         Queue_init(T.Q2);

         T.Num1:=0;

         T.Num2:=0;

End;

 

Procedure TLQ_delete (var T: Two_Level_Queue; var X:Queue_info_type);

Begin

      If not(Queue_is_empty(T.Q1) then

      begin

               Queue_delete(T.Q1,X);

               T.num1:=T.num1 - 1;

      end

      else begin

       Queue_delete(T.Q2,X);

       T.num2:=T.num2 - 1;

end;

End;

 

Functin TLQ_num_element(T :Two_Level_Queue; y:integer):integer;

Begin

         If y=1 then TLQ_num_element:=T.num1

         Else TLQ_num_element:= T.num2;   

END;

 

לאתר עיצוב תכנה

למאגר טיפים בעיצוב תכנה

חזרה