5. מערכים חד-ממדיים

5.1 מהו מערך?

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

הסבר כתוב אודות: מהו מערך

5.2 דוגמות ראשונות לשימוש במערך

תרגול עצמי בסיסי בנושא מערך חד-ממדי

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

5.3 מציאת האיבר המרבי במערך, ובאילו תאים במערך הוא מופיע

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

5.3.1 מציאת האיבר המרבי במערך, ובאילו תאים במערך הוא מופיע - שיטה א'

הסבר כתוב אודות מציאת האיבר המרבי במערך, ובאילו תאים במערך הוא מופיע - שיטה א'

5.3.2 מציאת האיבר המרבי במערך, ובאילו תאים הוא מופיע - שיטה ב'

הסבר כתוב אודות מציאת האיבר המרבי במערך, ובאילו תאים הוא מופיע - שיטה ב'

5.3.4 עיון חוזר בפקודת ההגדלה העצמית (++)

5.4 חיפוש במערך

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

לצורך המשך דיוננו נניח כי בתכנית הוגדר המשתנה:

; int stud_list[LIST_SIZE]

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

5.4.1 חיפוש סדרתי במערך לא ממוין

הסבר כתוב אודות חיפוש סדרתי במערך לא ממוין

5.4.2 חיפוש בינארי במערך ממוין

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

הסבר כתוב אודות חיפוש בינארי במערך ממוין

תרגול עצמי בסיסי בנושא חיפוש בינארי

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

5.5 מיון בועות (Bubble Sort)

בסעיף הקודם ראינו כיצד נחפש במערך ממוין. בסעיף הנוכחי אציג אלגוריתם למיון המערך הקרוי: מיון בועות. אעיר שמיון בועות הוא, יחסית, אלגוריתם לא יעיל למין מערך, אך בכך נוכל להכיר רק עת נלמד בשלב מאוחר הרבה יותר בקורס מיונים יעלים יותר (כגון מיון מהיר).

הסבר כתוב אודות מיון בועות

5.6 מציאת מספרים ראשוניים בשיטת הכברה

הסבר כתוב אודות שיטת הכברה

תרגול עצמי בסיסי בעקבות שיטת הכברה

כתבו תכנית המגדירה מערך בולאני של עשרים תאים, ומאתחלת את תאיו לערך false.

עתה התכנית קוראת מספרים שלמים עד קבלת הערך 999.

כל פעם שהתכנית קוראת ערך בתחום 0 עד 19 היא מסמנת בתא שזה מספרו במערך שמספר זה נקרא.

אחרי סיום שלב הקלט (אחרי שהתכנית קוראת את 999) היא בודקת מה הייתה סדרת המספרים הרציפים x, x+1, x+2, ..., x+k-1, x+k הארוכה ביותר שהיא קראה, ומציגה את המספר הראשון בסדרה, ואת אורכה.

לדוגמה: אם הקלט היה (משמאל לימין) 999, 18, 7, 4 , 8, 100, 16, 6, 3-, 3879, 17, 5 אזי סדרת המספרים הרציפים הארוכה ביותר שהוזנה היא: 8, 7, 6, 5, 4 כלומר סדרה שמתחילה במספר 4 ואורכה הוא 5, ולכן זה יהיה הפלט: 5 4.

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

5.7 תרגילים

כאמור, כדאי מאוד, מאוד לפתור בצורה מושלמת, באמצעות תכנית כתובה כהלכה מהחל ועד כלה, לכל הפחות שלושה תרגילים