מערך (מבנה נתונים)
במדעי המחשב, מערך (Array) הוא אחד ממבני הנתונים הפשוטים ביותר: מערך הוא אוסף פריטים שניתן לגשת אליהם בצורה ישירה באמצעות אינדקס. תכונות המערךבאופן עקרוני, מערך הוא בעצם מקרה ספציפי של מילון בו המפתחות הם מספרים טבעיים או תווים, וסיבוכיות גישה ישירה לכל נתון בודד באוסף לפי אינדקס היא קבועה (). ולכן הוא סוג של מבנה נתונים מופשט. עם זאת, מערכים הם טיפוס נתונים פרימיטיבי ברוב שפות התכנות (האימפרטיביות) ולכן כשמדברים על מערך מתכוונים לרוב למימוש נפוץ כלשהו שלו. תכונה נוספת של המבנה היא דרישות הזיכרון שלו – מבנה הנתונים דורש בדיוק את הזיכרון הנדרש עבור הנתונים עצמם, ובכך הוא החסכוני מבין כל מבני הנתונים. למערך שני חסרונות בולטים שקשורים למבנה הסטאטי שלו:
מימוש בתכנותבתכנות מערכים ממומשים בדרך כלל על ידי קטע רציף של זיכרון אשר מחולק בין כל הנתונים באוסף. למשתנה המסמל את הרצף זה יש שם יחיד, וכל אחד מהנתונים נקרא איבר של המערך. אל כל איבר באוסף מתייחסים באמצעות שם המערך ואינדקס של הערך (לרוב מספרו הסידורי של האיבר בתוך האוסף). ישנן שתי שיטות מקובלות להגדרה של מיקומי האיברים במערך: מרחק מתחילת המערך, ומספור הערך במערך. בשיטה הראשונה, המיון מתבצע לפי המרחק של הערך מהערך הראשון במערך, כך שהערך הראשון במערך מקבל מיקום 0, הערך השני – מיקום 1, והערך ה--י – את המיקום ה-. בשיטה השנייה, מספור הערך במערך, המיון מתבצע לפי מספר הערך במערך, כך הערך הראשון יהיה במיקום 1, הערך השני במיקום 2, והערך ה--י – במיקום ה-. השיטה הראשונה מייצגת באופן ברור יותר את המימוש של מערך כגוש זיכרון רצוף, ומהווה למעשה את הדרך בה המחשב מתייחס למערך. השיטה השנייה מייצגת באופן יותר ברור את מיקום הערכים כפי שמקובל בשפת אדם, ויותר פשוטה להבנה. בשפת Pascal ממומש מיון הערכים במערך בדרך השנייה (זאת אומרת, הערך הראשון במערך יקבל מען 1). בשפת C לעומת זאת משתמשים בשיטה הראשונה. דוגמהנניח שרוצים לאחסן את הרשימה של המספרים הריבועיים {1,4,9} בזיכרון המחשב. יש להגדיר מערך שיכונה בשם כלשהו, למשל square, כמערך שיכול להכיל שלושה מספרים שלמים. ולהציב: square[0]=1
square[1]=4
square[2]=9
כאן אנו מציגים דרך סטנדרטית לגישה למערכים: שם המערך נכתב ראשון, ואחריו, בסוגריים מרובעים, נכתב האינדקס של האיבר שאת ערכו אנו רוצים לשנות. נשים לב כי במקרה זה, לאיבר הראשון במערך יש את האינדקס 0. זוהי בחירה שרירותית – בשפות תכנות מסוימות (דוגמת C) זה כך, ובשפות אחרות זה אחרת. דרך גישה מסורבלת יותר למערכים, שבאסמבלר היא היחידה האפשרית, היא באמצעות שימוש במצביעים לתאי זיכרון. אין הבדל של ממש בין השיטות: הביטוי square[0] מתורגם בפועל לכתובת הזיכרון בה מאוחסן הנתון. עם זאת במטריצות שימוש כזה עשוי להיות יעיל משמעותית. תכונות המערך בשפות תכנותלמערך ישנם כמה חסרונות שדורשות התייחסות בעבודה עם המבנה במהלך תכנות:
מטריצותנוסף למערך הרגיל שמייצג למעשה וקטור, ניתן ליצור גם מערך דו־ממדי השקול למטריצה ואף מערך רב ממדי. הייצוג הפנימי המקובל למערך דו־ממדי הוא אחסון שורות המטריצה ברצף בזיכרון המחשב, שורה אחר שורה. כאשר מבקשים לפנות למידע תוך התבססות על שני הממדים של האיבר שאותו מבקשים, המערך הדו־ממדי מיוצג על ידי מערך חד־ממדי, שכל אחד מאבריו הוא מערך חד־ממדי בעצמו. למשל, אם שם המערך הדו הממדי הוא והמשתמש רוצה את האיבר בשורה השנייה ובעמודה החמישית, הוא יבקש את האיבר (דבר השקול לבקשת האיבר החמישי במערך ששמור במקום השני במערך החד־ממדי ). הסדר של המטריצה שונה משפת תכנות אחת לשנייה. לרוב הסידור הוא סידור לפי שורות: קודם התאים של השורה הראשונה ולאחר מכן התאים של השורה השנייה וכך הלאה. בחלק משפות התכנות כגון Fortran הסידור הוא לפי עמודות, כלומר קודם העמודה הראשונה, אחר השנייה וכך הלאה. באמצעות מערך רב ממדי ניתן לייצג טנזור כללי, בעל מספר ממדים כלשהו. שימושים עיקרייםישנם שימושים רבים מאוד למבנה הנתונים הזה, ולהלן העיקריים שבהם:
אלטרנטיבה מקובלת למערך במקרה של מספר נתונים משתנה היא רשימה מקושרת, המאופיינת בגמישות בהוספה ובמחיקה של איברים. קישורים חיצונייםביאורים
הערות שוליים
|