מערך (מבנה נתונים)

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

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

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

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

בשפות נמוכות כמו אסמבלר משתמשים במצביעים (כתובות זיכרון) כדי לגשת לאיברים. בפועל הביטוי square[0] מתורגם לכתובת של התא בזיכרון.

נניח מערך בשם square שמכיל שלושה מספרים שלמים. אפשר לשים בו:
square[0] = 1
square[1] = 4
square[2] = 9
כאן האינדקס 0 מצביע על הפריט הראשון. בחלק מהשפות האינדקס הזה יכול להיות 1.

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

אפשר גם ליצור מערכים דו־ממדיים (מטריצות) או רב־ממדיים. ייצוג נפוץ למערך דו־ממדי הוא לאחסן שורה אחר שורה ברצף בזיכרון. גישה לאיבר במטריצה יכולה להיראות כך: A[2][5], כלומר האיבר בשורה השנייה ובעמודה החמישית. בחלק מהשפות, כמו Fortran, הסידור בזיכרון נעשה לפי עמודות.

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

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

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

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

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

נניח מערך בשם square עם שלושה מספרים:
square[0] = 1
square[1] = 4
square[2] = 9
כאן 0 הוא האינדקס של הפריט הראשון. בשפות אחרות האינדקס יכול להתחיל ב־1.

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

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