מערכים

מקום 14C

• לקולנוע יש 300 מקומות. מערכת ההזמנות שלו אינה מכילה 300 משתנים הנקראים Seat1A, Seat1B, Seat1C. יש לה מערך אחד, וכרטיס הכניסה שלך הוא כתובת לתוכו: שורה 14, מקום C.
• שם אחד, מאות ערכים, כל אחד נמצא על ידי מספר. הוספת שורה ואין צורך לשנות את הקוד; לולאת על המספרים ונבדקו כל המקומות.
• כמעט כל אלגוריתם במבחן Paper 2 עובר על מערך: מחפש בו, מסכם אותו, מיישר אותו או מוצא את הערך הגדול ביותר.
• שיעור זה הוא המילון, ההצהרות וארבעת האלגוריתמים שהבוחן דורש בפסאודוקוד ובמילים.

המילון

• מערך הוא מבנה נתונים המכיל מספר קבוע של אלמנטים מאותו סוג נתונים תחת זיהוי אחד, כאשר כל אלמנט נגיש באמצעות אינדקס.
• הגבול התחתון והגבול העליון הם האינדקס הראשון והאחרון החלים. מספר האלמנטים שווה לגבול העליון פחות הגבול התחתון פלוס 1.
• המימד הוא מספר האינדקסים הנדרשים לאלמנט: אחד לרשימה, שניים לטבלה.
• בThisArray[n] ← 42 למערך יש מימד אחד, האינדקס הוא המשתנה INTEGER n, והאלמנט באינדקס זה מקבל את 42.

זיהוי אחד, אינדקס לכל אלמנט, גבולים בשני הקצוות

דוגמה פתורה: הצהרת מערך הנדרש ממשימה

עיבוד מערך 1-ממדי

DECLARE Names : ARRAY[1:5] OF STRING
Names[3] ← "Cara"

FOR i ← 1 TO 5
    OUTPUT Names[i]
NEXT i

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

מערכים 2-ממדיים

DECLARE Grid : ARRAY[1:3, 1:4] OF INTEGER
Grid[2, 3] ← 99      // row 2, column 3

• האינדקס הראשון הוא השורה, השני הוא העמודה. לולאות מוטבעות מבקרות בכל תא: הלולאה החיצונה בשורות, הפנימית בעמודות.
• השתמש ב1-D לסדרה יחידה וב2-D כאשר הנתונים ישנם שני מימדים טבעיים, כמו רשת מושבים או טבלת ציונים לפי תלמיד ונושא.

Grid[row, column], תמיד בסדר זה

דוגמה מפורטת: חיפוש ליניארי שיכול להציג "לא נמצא"

FoundAt ← -1
FOR i ← 1 TO n
    IF A[i] = Target THEN
        FoundAt ← i
    ENDIF
NEXT i
IF FoundAt = -1 THEN
    OUTPUT "Not found"
ELSE
    OUTPUT "Found at ", FoundAt
ENDIF

הערך הגדול ביותר, ואين הוא

Largest ← A[1]
Position ← 1
FOR i ← 2 TO n
    IF A[i] > Largest THEN
        Largest ← A[i]
        Position ← i
    ENDIF
NEXT i
OUTPUT Largest, " at ", Position

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

בועות (Bubble sort)

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

REPEAT
    Swapped ← FALSE
    FOR Index ← 1 TO Limit - 1
        IF Data[Index] > Data[Index + 1] THEN
            Temp ← Data[Index]
            Data[Index] ← Data[Index + 1]
            Data[Index + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT Index
    Limit ← Limit - 1
UNTIL Swapped = FALSE

כל מעבר מוביל את הערך הגדול הנותר לקצה

דוגמה מפורטת: איפה נמצאים סימני הבועות

דוגמה מפורטת: הסרה והכנסה

סימונים נופלים מהיד

הבנתך מושלמת