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

מערך
סיבוכיות מקום וזמן
	ממוצע במקרה הגרוע
זיכרון:	O(n) O(n)
חיפוש:	O(log n)\O(n)‎ O(log n)\O(n)‎
הכנסה:	O(1)\O(n)‎ O(1)\O(n)‎
הוצאה:	O(1)\O(n)‎ O(1)\O(n)‎

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

תכונות המערך

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

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

למערך שני חסרונות בולטים שקשורים למבנה הסטאטי שלו:

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

מימוש בתכנות

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

ישנן שתי שיטות מקובלות להגדרה של מיקומי האיברים במערך: מרחק מתחילת המערך, ומספור הערך במערך. בשיטה הראשונה, המיון מתבצע לפי המרחק של הערך מהערך הראשון במערך, כך שהערך הראשון במערך מקבל מיקום 0, הערך השני 1, והערך ה-$\ n$י - את המיקום ה$\ n-1$. בשיטה השנייה, מספור הערך במערך, המיון מתבצע לפי מספר הערך במערך, כך הערך הראשון יהיה במיקום 1, הערך השני במיקום 2, והערך ה$\ n$י - במיקום ה$\ n$.

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

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

דוגמה

נניח שרוצים לאחסן את הרשימה של המספרים הריבועיים {1,4,9} בזיכרון המחשב. יש להגדיר מערך שיכונה בשם כלשהו, למשל $\ square$, כמערך שיכול להכיל שלושה מספרים שלמים. ולהציב

$\ square[0]=1,square[1]=4,square[2]=9$.

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

דרך גישה מסורבלת יותר למערכים, שבאסמבלר היא היחידה האפשרית, היא באמצעות שימוש במצביעים לתאי זיכרון. אין הבדל של ממש בין השיטות: הביטוי $\ square[0]$ מתורגם בפועל לכתובת הזיכרון בה מאוחסן הנתון. עם זאת במטריצות שימוש כזה עשוי להיות יעיל משמעותית.

תכונות המערך בשפות תכנות

למערך ישנם כמה חסרונות שדורשות התייחסות בעבודה עם המבנה במהלך תכנות:

• אם מספר האיברים אשר יוכנסו למערך לא ידוע מראש, יכול להווצר מצב שמערך שהוגדר יהיה קטן מדי ותהיה דרישה להגדילו. פעילות כזאת תדרוש, לעיתים, העתקת כל הנתונים הקיימים למקום אחר שממנו אפשר להגדיל את הרצף בזיכרון, דבר שמכביד מבחינת ביצועי התוכנה. שפות תכנות מסוימות מאפשרות טיפוסים מובנים שמבצעים את ההגדלה הדינאמית (כמו למשל Visual Basic, הטיפוס הפרימטיבי list בPython, וכדומה), שפות אחרות דורשות מהמתכנת לבצע את הפעולה בפירוש, תוך הגדרה של גודל החדש.
• במקרים שבהם זקוקים למערך דליל (מערך בעל טווח ערכים גדול במיוחד, אף שרוב תאיו לא ינוצלו), אין זה מן הנמנע שבזיכרון הפנוי במחשב לא יימצא כלל מקום לרצף התאים שנתבקש, והקצאת המערך לא תתאפשר, וגם אם תתאפשר הקצאת המערך תגרום לבזבוז רב של זיכרון. למשל: אם משתמשים במערך כדי לייצג את כל תושבי מדינת ישראל, כך שהאינדקס של כל איבר במערך יהיה מספר תעודת הזהות של התושב, יהיה מספר עצום של תאים ($\ 10^{9}$) שרק חלק זעום מהם יהיה תפוס. לבעיות מטיפוס כזה מתאימים מבני נתונים אחרים, כדוגמת טבלת גיבוב או מטריצה דלילה.

מטריצות

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

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

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

שימושים עיקריים

ישנם שימושים רבים מאוד למבנה הנתונים הזה, ולהלן העיקריים שבהם:

• בעזרת מערכים ניתן לייצג מבני נתונים מורכבים יותר: ערימות, טבלאות גיבוב, תורים, מחסניות, רשימות, מחרוזת, עץ חיפוש (למשל B-Tree) ועוד.
• מערכים משמשים בהרבה מקרים בתור מונים באלגוריתמים שונים (למשל - מיון מנייה).
• מערכים משמשים בהרבה מקרים בתור אוסף של דגלים (בשפות תכנות מתייחסים לעיתים לשימוש כזה של מערך בשם bitmask, המערך הוא מערך ביטים בודדים וכל ביט יכול לקבל ערך $\ 1$ או $\ 0$).

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

קישורים חיצוניים

מדיה וקבצים בנושא מערך בוויקישיתוף