הקצאה דינמית ומערכים בשפת C

[א]

האם יש אפשרות לקלוט מספר לא ידוע של מספרים אל תוך מערך של INT, מבלי שהמשתמש מזין את כמות המספרים שייקלטו?

[שניצל]

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

[א]

תודה

למה אבל פי 2? לא עדיף להגדיל כל פעם באחד?

[שניצל]

כי זה לא יעיל.

realloc זו פעולה כבדה - היא מקצה מערך חדש, מעתיקה את כל התוכן מהמערך הישן לחדש, ומשחררת את הישן.

[א]

אז למה לא פי 10? (ובכך הקצאנו מלא זכרון שייתכן ויהיה מיותר)

אני פשוט לא מבין איפה עובר הגבול בין סביר למוגזם בקטע הזה.

[שניצל]

זה שרירותי, מותר פי כמה שאתה רוצה. העיקר שאתה כל פעם כופל באותו פקטור, ולא מוסיף.

[Zelig]

אם אתה כופל כל פעם ב-2, אז במקרה הכי גרוע אתה משתמש בפי 2 זכרון ממה שאתה באמת צריך, ועשית רק logN הקצאות (זה נכון עבור כל פקטור קבוע) שזה לא נורא.

אם אתה כופל ב-10 אז במקרה הכי גרוע אתה משתמש בפי 10 זכרון ממה שאתה באמת צריך.

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

[א]

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

[שניצל]

אי אפשר באמצעות gets או scanf (ובגלל זה הן פונקציות לא בטוחות לשימוש).

יש כמה פתרונות:

א. לקרוא תו אחר תו באמצעות getchar ולהכניס אותם למערך.

ב. להשתמש ב-fgets שעובדת כמו gets אבל מקבלת שלושה פרמטרים - מערך לקרוא לתוכו, מספר תווים מקסימלי לקריאה (פחות 1 עבור '0\'), וקובץ לקרוא ממנו (במקרה של קלט מהמשתמש הקובץ צריך להיות stdin).

אופציה א' נותנת לך מקסימום שליטה.

[Gil28]

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

[א]

תודה, כרגע אני בכלל בבעיה שלא קשורה להקצאה דינמית.

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

זה הקוד:

[Gil28]

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

[א]

זאת הייתה כוונתך?

[Gil28]

המונה מיותר אם אתה משתמש ב-i. התנאי counter<=1 לא ברור. למה דווקא 1? מה אתה מנסה לבדוק?

[א]

המערך הנוכחי בגודל 3, כלומר יש מקום ל-2 תווים + תו סוף מחרוזת. הבדיקה היא בשביל לוודא שאני מכניס רק לתא 0 ולתא 1.

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