אלצ'קו
אחראי פורומים
ג2ר פ33תי
הצטרף / הצטרפה: 20 January 2006
משתמש: מנותק/ת
הודעות: 609
|
| נשלח בתאריך: 08 August 2006 בשעה 23:22 | | IP רשוּם
|
|
|
|
תתפלא, אבל כדי לממש רשימה מקושרת, אתה די צריך להקצות זיכרון בכל פעם שאתה מוסיף תא...
אתה אולי מתכוון לשאול איך עדיף לממש "מערך" שגדלו משתנה: כרשימה מקושרת, או כמערך-C-רגיל שעושים לו realloc כשצריך?
לפני שניגשים לתשובה, חשוב לציין נקודה אחרת: אם אתה יודע שגודל המידע שלך
לא יעבור גבול מסויים, אולי עדיף להקצות מראש את כל הגודל, ולא להסתבך
בהמון הקצאות דינמיות. (לדוגמה: מערך בגודל 10000 של אובייקטים בגודל 20
בייט ייקח רק 20K, וזו לא אמורה להיות בעיה בשום מחשב מודרני)
ובחזרה לשאלה: מערכי-C או רשימות מקושרות?
תלוי בהמון גורמים. נתחיל מזה שרשימות מקושרות עדיפות כשאתה מוסיף מידע
באמצע המערך ולא בקצוות שלו. אם אתה מוסיף מידע בקצוות, מערכים רגילים הם
די בסדר (בהנחה שאין מגבלות זיכרון לא-נעימות).
נקודה שניה שכדאי לשים לב אליה הוא שברשימות מקושרות אתה מקצה רק את
הזיכרון הנוסף שאתה צריך, בעוד שבראלוקציה של מערכים אתה חייב להקצות את
כל גודל המערך, להעתיק את כל המידע למערך החדש, ולשחרר את הישן (תאר לעצמך
ראלוקציה של 10MB ל-10.01MB)
מצד שני, עם מערכים יש לך גישה אקראית לכל אלמנט, בעוד שעם רשימה מקושרת אתה חייב "לזחול" על כל הרשימה עד שתגיע לאלמנט שאתה רוצה.
אפשר לבצע כל מיני מעקפים ושילובים של שתי האפשרויות. לדוגמה:
- אפשר ליצור מערך שיהווה אינדקס עבור רשימה המקושרת, ויאפשר גישה
אקראית לתוכה. מצד שני, כשרוצים לשנות את גודל האינדקס, חוזרים לבעיה
ההתחלתית.
- רשימה מקושרת של מערכי-C: אם נתון מערך בגודל A ואתה רוצה להוסיף x,
במקום לעשות ראלוקציה לגודל A+x, אתה יוצר מערך נוסף בגודל x ומקשר אותו
לסוף של המערך בגודל A.
תהיה לך פה גישה אקראית שקצת יותר איטית מגישה אקראית במערך רגיל, אבל
תחסוך את הראלוקציות, ולא תהיה חייב "לזחול" כמו ברשימה מקושרת.
בקיצור, אין תשובה חדה ויחידה, אלא יש מיליון פתרונות תלויי-מצב.
|
נושאים פעילים
רשימת משתמשים
חיפוש
עזרה
הרשמה
התחברות
UnderWarrior Forums : 
תיכנות
