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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

[עריכה] דוגמה

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

.

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

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

[עריכה] תכונות המערך

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

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

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

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

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

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

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

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

[עריכה] מטריצות

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

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

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