תוֹכֶן

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

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

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

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

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

1. טבלת השוואה
2. הגדרה
3. הבדלים עיקריים
4. סיכום

טבלת השוואה

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

הגדרת מערך

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

הבה נתבונן בכמה מהמושגים שיש לזכור לגבי מערכים:

• ניתן לגשת לאלמנטים האישיים של מערך על ידי תיאור שם המערך, ואחריו אינדקס או תסריט (קביעת מיקום האלמנט במערך) בתוך הסוגריים המרובעים. לדוגמה, כדי לאחזר אלמנט חמישי במערך, עלינו לכתוב הצהרה א.
• בכל מקרה האלמנטים של המערך יאוחסנו במקום זיכרון רצוף.
• המרכיב הראשון במערך כולל אינדקס אפס. המשמעות היא שהאלמנט הראשון והאחרון יצוין כ- ו- בהתאמה.
• מספר האלמנטים הניתנים לאחסון במערך, כלומר גודל המערך או אורכו, ניתן על ידי המשוואה הבאה:
  (גבול עליון-גבול תחתון) + 1
  עבור המערך לעיל, זה יהיה (9-0) + 1 = 10. כאשר 0 הוא הגבול התחתון של המערך, ו- 9 הוא הגבול העליון של המערך.
• מערכים ניתנים לקריאה או כתיבה דרך הלולאה. אם אנו קוראים את המערך החד מימדי, הוא זקוק לולאה אחת לקריאה ואחרת לכתיבה (ing) של המערך, למשל:
  א. לקריאת מערך
  עבור (i = 0; i <= 9; i ++)
  {scanf ("% d", & a); }
  ב. לכתיבת מערך
  עבור (i = 0; i <= 9; i ++)
  {f ("% d", א); }
• במקרה של מערך דו-ממדי, הוא ידרוש שני לולאות ומערך n ממדי באופן דומה היה זקוק לולאות n.

הפעולות המתבצעות במערכים הן:

1. יצירת מערך
2. חוצה מערך
3. הכנסת אלמנטים חדשים
4. מחיקת האלמנטים הנדרשים.
5. שינוי של אלמנט.
6. מיזוג מערכים

דוגמא

התוכנית הבאה ממחישה את הקריאה והכתיבה של המערך.

# כלול
# כלול
ראשי בטל ()
{
int a, i;
f ("הזן את המערך");
עבור (i = 0; i <= 9; i ++)
{
scanf ("% d", ו- a);
}
f ("הזן את המערך");
עבור (i = 0; i <= 9; i ++)
{
f ("% d n", a);
}
גץ '();
}

הגדרת הרשימה המקושרת

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

INFO חלק המאחסן את המידע ואת POINTER שמצביע על האלמנט הבא. כידוע לשמירת כתובת, יש לנו מבני נתונים ייחודיים ב- C הנקראים מצביעים. מכאן שהשדה השני ברשימה חייב להיות סוג מצביע.

סוגי הרשימות המקושרות הן רשימה מקושרת יחידה, רשימה מקושרת כפליים, רשימה מקושרת מעגלית, רשימה כפולה מעגלית.

הפעולות שבוצעו ברשימה המקושרת הן:

1. יצירה
2. חוצה
3. הכנסה
4. מחיקה
5. מחפש
6. שרשור
7. תצוגה

דוגמא

הקטע הבא ממחיש יצירה של רשימה מקושרת:

צומת מבנה
{
int num;
עצור צומת * הבא;
}
התחל = NULL;
ליצור ריק ()
{
typedef struct צומת NODE;
NODE * p, * q;
בחירת char;
ראשון = NULL;
לעשות
{
p = (NODE *) malloc (sizeof (NODE));
f ("הזן את פריט הנתונים n");
scanf ("% d", & p -> num);
אם (p == NULL)
{
q = התחל;
בעוד (q -> הבא! = NULL)
{q = q -> הבא
}
p -> הבא = q -> הבא;
q -> = p;
}
אחר
{
p -> הבא = התחל;
התחל = p;
}
f ("האם ברצונך להמשיך (הקלד y או n)? n");
scanf ("% c", & בחירה);
}
בעוד ((בחירה == y) || (בחירה == Y));
}

1. מערך הוא שמבנה הנתונים מכיל אוסף של אלמנטים נתונים דומים ואילו הרשימה המקושרת נחשבת כמבנה נתונים שאינו פרימיטיבי מכיל אוסף של אלמנטים מקושרים לא מסודרים המכונים צמתים.
2. במערך האלמנטים שייכים לאינדקסים, כלומר אם ברצונך להיכנס לאלמנט הרביעי עליך לכתוב את שם המשתנה עם האינדקס או המיקום שלו בתוך סוגר הריבוע.
   ברשימה מקושרת, עלייך להתחיל מהראש ולעבוד דרכך עד שתגיע לרכיב הרביעי.
3. הגישה למערך אלמנטים מהירה בזמן שרשימה מקושרת אורכת זמן ליניארי כך שהיא מעט איטית יותר.
4. פעולות כמו החדרה ומחיקה במערכים צורכות זמן רב. מצד שני, ביצועי הפעולות הללו ברשימות מקושרות מהירות.
5. מערכים בגודל קבוע. לעומת זאת, רשימות מקושרות הן דינמיות וגמישות ויכולות להרחיב ולהתכווץ בגודלה.
6. במערך, זיכרון מוקצה בזמן קומפילציה ואילו ברשימה מקושרת הוא מוקצה במהלך ביצוע או בזמן ריצה.
7. המרכיבים נשמרים ברציפות במערכים ואילו הם מאוחסנים באופן אקראי ברשימות מקושרות.
8. דרישת הזיכרון פחות נובעת מהנתונים בפועל המאוחסנים בתוך האינדקס במערך. לעומת זאת, יש צורך בזיכרון רב יותר ברשימות המקושרות עקב אחסון של רכיבי הפניה הבאה והקודמת.
9. בנוסף השימוש בזיכרון אינו יעיל במערך. לעומת זאת, השימוש בזיכרון יעיל במערך.

סיכום

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