מבנים

[pitbol3]

מבנים

אהלן,

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

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

הראשון בגודל N+1 ולבצע העתקה בעזרת לולאה.


האם ישנה דרך נוחה/נורמאלית יותר?

תודה

 

[BravoMan]

השאלה היא מה זה לשיטתך "מערך דינמי"?

כלומר, כיצד בדיוק הוא ממומש במקרה שלך.

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

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

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

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

 

[pitbol3]

אממ

לא הבנתי דבר אחד...
אם אני מקצה מערך דינאמי על מער דינאמי שכבר קיים(פשוט משנה את אורכו) הוא יאבד את המידע שיש ברשותו, הלא כך?
כלומר נניח a הוא מערך דינאמי בעל N איברים מסוג struct student.

אם אשלח את הכתובת של a לפונקציה ואת הגודל המבוקש N+1, ואבצע:

a=(struct student *) malloc(sizeof(struct student) * (n+1)) qq


אז a איבד את כל התאים שהיו לו, או שאני טועה?

אם לא, איך לדעתך, ללא רשימה משורשרת, אפשר לעשות את זה ביעילות?

תודה

 

[BravoMan]

לא בדיוק:

בהנחה ש-a הוא פרמטר לפונקציה מסוג *struct student הרי שבשורה הזו שמרת מצביע לזיכרון חדש שהוקצע במקום, שלא זמין מחוץ לפונקציה, כלומר ברגע שהפונקציה תסתיים, לא תהיה לך גישה לזיכרון החדש שהקצת.

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

למצב זה קוראים "זליגת זיכרון".

 

[pitbol3]

אני רוצה לסכם את זה

כתבתי בקטע המצורף פונקציה שמקבלת כתובת של מערך ואורכו. הפונקציה מגדילה את המערך ל N+1 (כאשר אורכו המקורי N). הפונקציה מחזירה את הכתובת של המערך החדש.

השאלה שלי היא כזאת, האם לא מספיק רק להקצות בפונקציה באמצעות malloc ל a מערך בגודל N+1 ואז להחזיר את a? האם יכולה להיות זליגת מידע באפשרות הזו? כי אם כן, הקוד שכתבתי

לא הכרחי...

תודה

 

[BravoMan]

יש לך הקצאה מיותרת, וגם זליגת זיכרון

פוטנציאלית!

ההקצאה המיותרת היא ההקצאה השנייה שאתה מבצע (ושומר ב-a).
כבר יש לך את כל המערך המוגדל ב-b, למה שלא תחזיר את b וזהו?

זליגת זיכרון:
בתוך הפונקציה אתה לא משחרר את המערך המקורי, האם אתה עושה זאת מחוץ לפונקציה?
כי אם לא, יש לך זליגה!

ושאלה אחרונה: האם המערך אמור להכיל את המבנים עצמם או רק מצביעים למבנה?

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

 

[pitbol3]

אמממ

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

הבעיה שלי יכולה להיות בקריאה לפונקציה? כי הרי אני רוצה לקבל את המערך החדש ואם אכתוב את הקריאה הבאה:

a=f(a,5 ) qq

אז יווצר מצב של זליגת זיכרון לא ככה?

 

[BravoMan]

בדיוק!

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

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

אני מכתוון למשהו כזה:

struct student* tmp;
tmp = f(a,5 );
if (tmp != NULL)
a = tmp;


זה כמובן בתנאי שיש free(a); z בתוך הפונקציה עצמה ואתה נפתר מההקצעה השנייה (שכאמור מיותרת לחלוטין).

 

[pitbol3]

אוקיי..ועכשיו ברשימה משורשרת

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

קצת הגדרות: b זה הכתובת שאני רוצה להוסיף לרשימה.

המטרה כאן זהה למקודם להוסיף איבר לרשימה ולקלוט אותו... בתחילת הקוד מוגדר איבר מסוג struct item.

תודה על העזרה!

 

[BravoMan]

רע מאוד!

אתה לא מקצה את האיבר החדש!
אתה רק יוצר משתנה מקומי שאמור להחזיק מצביע למבנה, אבל אתה לא מאתחל אותו.

אם תנסה להריץ את זה התוכנית תקרוס או תתנהג בצורה לא צפויה.

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

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

 

[pitbol3]

הבנתי את הטעות

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

 

[nocgod]

אני נהגתי להעביר

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

int enlarge(type** t, int size, int newSize)
{
type* tmp;
int i;

if (size > newSize)
{
return -1;
}
tmp = (type**) malloc (sizeof(type*) * newSize);
assert(t != null);
for (i = 0; i < size; i++)
{
tmp = t;
}

free(t); // it should be a dynamically allocated array otherwise there is no point in this function

for (int i = size; i < newSize; i++)
{
tmp = readNewData();
}

*t = tmp;
}

שים לב שאפשר לקצר את כל התהליך הזה עם realloc אבל כדאי להזהר...

 

[pitbol3]

אממ

לדעתי יש בעיה קטנה בשורה הזאת:
tmp = (type**) malloc (sizeof(type*) * newSize);

tmp הוא מסוג type * , משום מה בקאסטינג המרת אותו ל type**...

תוכל להרחיב למה השתמשת במצביע למצביע כאן? תודה

 

[BravoMan]

נכון, וזה לא המקום היחיד שיש קצת בלבול עם

כוכביות בקוד.

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

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

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

זה מפנה את הערך המוחזר מהפונקציה לאינדיקציה על שגיאות.

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

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

 

[nocgod]

כמובן שטעיתי...כמו שאמרתי לא הרצתי את זה

cast צריך להיות כמובן עם * אחת ולא ** כמובן.
למה השתמשתי במצביע למצביע? כי נניח שאני שומר את המצביע למערך שלי באיזהו משתנה
type * dynArr

כאשר אני שולח לפונקציה את המצביע אני שולח לו רק את כתובת תחילת המערך.
void func(type* arrPtr)

זאת אומרת שאם במהלך הפונקציה אני צריך לשנות את הכתובת של המערך ואני אבצע שינוי במשתנה הפורמלי arrPtr השינוי הזה ימות יחד עם הפונקציה כשהיא תגמר ושום שינוי לא ישמר במצביע המקורי dynArr כי שלחתי לו את הערך שdynArr מחזיר ולא את המשתנה dynArr עצמו כדי לשנות את התוכן שלו.
מאחר ואנחנו כותבים בC ואין פה ייחוסים (references) אנחנו נצטרך לעשות קומבינה ולשלוח את המקום בזיכרון של המצביע dynArr לפונקציה func שלנו ככה שאם במהלך ריצת func אני אצטרך להחליף את המערך אליו מצביע dynArr למערך אחר (מסיבה זו או אחרת) אני אוכל לשנות את התוכן של dynArr עצמו ולא המשתנה הפורמלי ששומר את ערך המצביע למערך. (משתנה פורמלי הוא משתנה של הפונקציה אשר מת ביציאה מהscope של הפונקציה)

קצת עשיתי משמש בהסבר אבל מקווה שהבנת

 

[pitbol3]

שאלה נוספת

השאלה היא בהתמודדות עם תלמידים שנרשמים לקורסים. אנו שומרים רשימות של סטודנטים ורשימות של
קורסים, כאשר כל סטודנט יודע לאיזה קורסים הוא רשום וכן כל קורס "יודע" איזה סטודנטים רשומים אליו . המבנים של student ו- course מוגדרים בקובץ המצורף...

נתונה פנוקציה:
ZZ slist* add_student(slist *students, char *name, int id);

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


יש לי 2 שאלות:
א. נניח ואני מגדיר משתנה נוסף slist*a , ואני רוצה להכניס את ת.ז ואת השם במבנה הראשון, האם הפקודות הבאות הן הנכונות?(מבחינת סינטקס):
a->info->id=id
strcpy(a->info->name,name) qq

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

 

[BravoMan]

תשובות:

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

כשאתה רושם:

slist* a;

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

כנ"ל לגבי האיבר name: הוא רק מצביע למערך תווים, אבל אתה עדיין חייב להקצות את המערך הזה בעצמך.

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

יש מקומות מוגבלים בהם מקובלים שמות בעלי אות אחת כגון במונה של לולאות (i, j וכו') או במקום שלאות יש באמת משמעות, כמו קואורדינטות x, y. (זה לרוב יהיה בתוך מבנה).

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

המבנים במקרה שלך לא מכילים ממש אחד את השני, אלא רק מחזיקים במצביע למבנה הנוסף.
למעשה, הכינויים slist ו-clist (שאני מניח הם קיצורים של student_list ו-course_list) לא לגמרי מדויקים, כי המבנים אינם מייצגים את הרשימה כולה אלא רק צומת אחד ברשימה, ואולי מתאים יותר לכנות אותם node.

 

[pitbol3]

אמ

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

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


תודה!

 

[BravoMan]

אתה טועה בעניין א'

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

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

לגבי ב: לא הבנתי מה לא הצלחת לאתחל. אם תפרט, אשמח לעזור...

 

[pitbol3]

אז ככה

בקריאה שניה אתה צודק- צריך לקלוט את NAME כל פעם מחדש(שמות שונים של סטודנטים).

מה רע בקוד הזה למשל?(פרט לכך שחסר MAIN וכדומה).