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

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

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

תוכן עניינים

1 תכונות המערך
2 מימוש בתכנות
3 דוגמה
4 תכונות המערך בשפות תכנות
5 מטריצות
6 שימושים עיקריים

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

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

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

הראשון שבהם הוא חוסר הגמישות שבו: קשה למחוק איברים ממערך תוך שמשאירים את האיברים הנותרים סמוכים זה לזה, שכן אם נמחוק את אחד האיברים נצטרך להעביר את כל האיברים שאחריו מקום אחד אחורה בזיכרון, פעולה שהיא בסיבוכיות $\ O(n)$ , כאשר $\ n$ הוא מספר התאים שיש להזיז.
כמו כן, אין זה פשוט להוסיף למערך איברים חדשים. ייתכן שתאי הזיכרון שאחרי המקום האחרון במערך כבר נתפסו למטרה אחרת, ולפיכך כדי להגדיל את המערך יש להעתיק את כולו מחדש לרצף תאים פנויים במספר הנדרש. אומנם, ניתן להראות שהעלות המשוערכת (amortized cost) של הוספת תאים חדשים בדרך חכמה (על פי רוב, הכפלת המערך פי שניים בכל פעם שנדרשים להגדיל אותו) לא תעלה על $\ 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, מחלקת הvector הסטנדרטית ב++C, וכדומה), שפות אחרות דורשות מהמתכנת לבצע את הפעולה בפירוש, תוך הגדרה של גודל החדש (כמו למשל פונקציית realloc בשפת C).
במקרים שבהם זקוקים למערך דליל (מערך בעל טווח ערכים גדול במיוחד, אף שרוב תאיו לא ינוצלו), אין זה מן הנמנע שבזיכרון הפנוי במחשב לא יימצא כלל מקום לרצף התאים שנתבקש, והקצאת המערך לא תתאפשר, וגם אם תתאפשר הקצאת המערך תגרום לבזבוז רב של זיכרון. למשל: אם משתמשים במערך כדי לייצג את כל תושבי מדינת ישראל, כך שהאינדקס של כל איבר במערך יהיה מספר תעודת הזהות של התושב, יהיה מספר עצום של תאים ( $\ 10^9$ ) שרק חלק זעום מהם יהיה תפוס. לבעיות מטיפוס כזה מתאימים מבני נתונים אחרים, כדוגמת טבלת גיבוב או מטריצה דלילה.

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

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

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

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

[עריכה] שימושים עיקריים

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

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