לוגו אתר Fresh          
 
 
  אפשרות תפריט  ראשי         אפשרות תפריט  מבזקים     אפשרות תפריט  צור קשר     חץ שמאלה ‎print ‎"Hello World!"; if‎ ‎not rules.‎know ‎then rules.‎read(); חץ ימינה  

לך אחורה   לובי הפורומים > מחשבים > תכנות ובניית אתרים
שמור לעצמך קישור לדף זה באתרי שמירת קישורים חברתיים
תגובה
 
כלי אשכול חפש באשכול זה



  #1  
ישן 04-07-2015, 19:19
צלמית המשתמש של Musicman0
  משתמש זכר Musicman0 Musicman0 אינו מחובר  
 
חבר מתאריך: 25.12.05
הודעות: 4,999
מיזוג שתי רשימות מקושרות ב-C

היי
אני צריך לממש פונקציה שממזגת בין שתי רשימות מקושרות דו-כיווניות.
הפונקציה מקבלת שני מצביעים כל אחד לתחילת הרשימה.
המיזוג נעשה באמצעות שילוב אברי הרשימה השניה בראשונה בסדר הפוך
כאשר האיבר הראשון ברשימה החדשה יהיה האיבר הראשון מהרשימה הראשונה, האבר השני
יהיה האיבר האחרון מהרשימה השניה וכך הלאה
לדוגמה
בהנתן רשימה ראשונה
קוד:
5 --> 0 --> 3 --> 6

רשימה שניה:
קוד:
17--> 21--> -->81-->11


הפונקציה תחזיר את ראש הרשימה, שתראה ככה:
קוד:
5-->11-->0-->81-->3-->21-->6-->17



מה שעשיתי בפונקציה הוא כזה:
עבור הרשימה השנייה רציתי מצביע שיצביע לי על סוף הרשימה, כדי שאוכל לרוץ מהסוף.
לכן בלולאה רצתי כל עוד temp->next != NULL
וכעת יש לי את זנב הרשימה
ואז עשיתי לולאה עבור המיזוג

זה נראה ככה:
קוד:
while (temp2->next != NULL){//find the tail of 2nd list temp2 = temp2->next; //tail = temp2; } tail = temp2; temp3 = head1; while (tail->prev != NULL && temp1->next != NULL){//merge two linkedlist temp3->next = tail; temp3 = temp3->next; tail = tail->prev; temp1 = temp1->next; temp3->next = temp1; temp3 = temp3->next; } return head1;



הבעיה היא שהרשימה הראשונה הולכת לאיבוד..
הרשימה שמתקבלת לי היא
קוד:
5-->11-->81-->21-->17

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


אפשר עזרה בבקשה?
תודה
_____________________________________
תמונה שהועלתה על ידי גולש באתר ולכן אין אנו יכולים לדעת מה היא מכילה

תמונה שהועלתה על ידי גולש באתר ולכן אין אנו יכולים לדעת מה היא מכילה

תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #4  
ישן 05-07-2015, 14:40
צלמית המשתמש של Benjamin Willard
  משתמש זכר Benjamin Willard Benjamin Willard אינו מחובר  
 
חבר מתאריך: 25.04.11
הודעות: 9,924
בתגובה להודעה מספר 1 שנכתבה על ידי Musicman0 שמתחילה ב "מיזוג שתי רשימות מקושרות ב-C"

1. נכתב בלי קומפיילר....

2. שים לב שזאת רקורסיה אמיתית, ולא רקורסיית זנב.

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

קוד PHP:
 List* Merge(List *first , List *second)
{
    
// Assuming second is pointing to the END of the second list

    
if(first ==second && first == NULL)
    {
        return 
NULL;
    }
    else if ( 
first == NULL)
    {
        return 
Reverse(second); 
    }
    else if (
second == NULL)
    {
        return 
first;
    }

    List *
merged Merge(first->nextsecond->prev);

    if(
merged != NULL)
    {
        
merged->prev second;
    }
    
second->next merged;

    
second->prev first;
    
first->next second;

    return 
first;

_____________________________________
תמונה שהועלתה על ידי גולש באתר ולכן אין אנו יכולים לדעת מה היא מכילה


נערך לאחרונה ע"י Benjamin Willard בתאריך 05-07-2015 בשעה 14:46.
תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #8  
ישן 07-07-2015, 12:29
צלמית המשתמש של Benjamin Willard
  משתמש זכר Benjamin Willard Benjamin Willard אינו מחובר  
 
חבר מתאריך: 25.04.11
הודעות: 9,924
בתגובה להודעה מספר 7 שנכתבה על ידי Musicman0 שמתחילה ב "וואו תודה רבה! אבל הבעיה..."

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

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

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

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

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

4. מבחינת סיבוכיות, זה בדיוק אותה סיבוכיות כמו הפתרון הרגיל, ואפשר בקלות להתגבר על העובדה שזה לא זנב (continuation) . אבל זה כן יעבור פעמיים (סוג של) על כל תא ברשימה....
_____________________________________
תמונה שהועלתה על ידי גולש באתר ולכן אין אנו יכולים לדעת מה היא מכילה

תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #10  
ישן 08-07-2015, 00:35
  The_Equivocator The_Equivocator אינו מחובר  
 
חבר מתאריך: 11.02.04
הודעות: 16,442
בתגובה להודעה מספר 9 שנכתבה על ידי Musicman0 שמתחילה ב "- מכיוון שהעתקתי את הפונקציה..."

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

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

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

נניח הסדרה שלנו זה 1:8:14:2:5:4 והK שלנו זה 16. במקרה זה התשובה היא כן כי למשל 8*2=16.

עכשיו בוא נחשוב על דרך לפתור שאלה זו.
נרוץ על כל איברי המערך, לכל איבר נפצל עץ, ענף אחד משמעותו שבחרו את האיבר הI במערך, וענף אחר עבור האפשרות שלא. (וכך נחסה את כל האפשרויות).
קוד:
boolean foo(int index, int value){ if (value == K) return true;// מצאנו פתרון נכון ונחזיר אמת if (index == N) return false;//עברנו על הכל ולא מצאנו פתרון.. נחזיר שקר! return foo(index+1,value)// הענף בעץ עבורו לא בחרנו את באיבר המערך || foo(index+1,value*ARR[index]); //הענף בעץ עבורו כן בחרנו לקחת את האיבר //ישנם בדיוק שני תרחשים עבור כל איבר במערך, או שמנסים אותו להיות חלק מהמכפלה שלנו, או שלא... ובכך חיסינו את כל האפשרויות }


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

נערך לאחרונה ע"י The_Equivocator בתאריך 08-07-2015 בשעה 00:38.
תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #19  
ישן 09-07-2015, 19:36
צלמית המשתמש של Musicman0
  משתמש זכר Musicman0 Musicman0 אינו מחובר  
 
חבר מתאריך: 25.12.05
הודעות: 4,999
בתגובה להודעה מספר 10 שנכתבה על ידי The_Equivocator שמתחילה ב "מה זה זנב ולא זנב, זה כרגע לא..."

אגב,
אם ברקורסיה עסקינן

יש אולי למישהו רעיון רקורסיבי לשאלה הבאה:

כתבו פונקציה רקורסיבית המקבלת מערך A של מספרי שלמים ואת אורכו (n).
הפונקציה מחזירה את מספר המופעים של האיבר המינימלי במערך.
על הפונקציה לבצע מעבר יחיד על המערך.
רמז: יש מקסימום n+1 קריאות לפונקציה

אשמח לרעיון כללי

את הקוד אני רוצה לנסות לכתוב לבד..

אותנו לימדו , בשביל למצוא פתרון רקורסיבי
"להאמין" שיש לי פתרון עבור בעיה בגודל n-1 ואז "להשלים" את הפתרון עבור n.
זה רק נשמע פשוט,אבל זה לא עוזר לי


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

תמונה שהועלתה על ידי גולש באתר ולכן אין אנו יכולים לדעת מה היא מכילה


נערך לאחרונה ע"י Musicman0 בתאריך 09-07-2015 בשעה 19:49.
תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #26  
ישן 12-07-2015, 17:41
צלמית המשתמש של קוביבי
  משתמש זכר קוביבי קוביבי אינו מחובר  
מנהל פורום מערכות הפעלה - הרובע המייקרוסופטי.
 
חבר מתאריך: 07.10.04
הודעות: 13,777
LinkedIn profile
בתגובה להודעה מספר 25 שנכתבה על ידי Musicman0 שמתחילה ב "לא הבנתי."

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

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

קוד:
int rec(arr[], arr_size) { return tail_rec(arr, arr[arr_size-1], arr_size-1, count); } int tail_rec(int[] arr, int min, int index, int count) { if (index < 0) retrun count; if (arr[index] == min) count++; if (arr[index] < min) { count = 1; min = arr[index]; } return (tail_rec(arr, min, index - 1, count)); }

הסבר זריז: rec הוא הפונקצייה לה קוראים
tail_rec (שם לא מתאים אבל העתקתי מיכם) הוא מה שסופר את מספר החזרות של המספר המינימלי.
אנחנו מתחילים מאינדקס size (סוף המערך) והולכים אחורה.
אם מצאנו מספר קטן יותר - נאפס את המונה,
אם מצאנו מספר זהה למינימום - נגדיל את המונה,
אם אנחנו לא באינדקס 0 (הגענו לתחילת המערך) - נחזיר את התשובה של מערך "קטן ב-1",
למה מרכאות? כי זה אינדקס, לא גודל, ולכן קשה לראות איך זה מסביר מה זה רקורסיה.

נכתב זריז, בלי בדיקה, יכול להיות שיש טיפה תיקונים שם, אבל זה הרעיון הכללי
_____________________________________
תמונה שהועלתה על ידי גולש באתר ולכן אין אנו יכולים לדעת מה היא מכילה

תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #27  
ישן 12-07-2015, 18:22
  The_Equivocator The_Equivocator אינו מחובר  
 
חבר מתאריך: 11.02.04
הודעות: 16,442
בתגובה להודעה מספר 26 שנכתבה על ידי קוביבי שמתחילה ב "הציעו לך פתרון שמבוסס על..."

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

*לא מכיר שום מוסד שמלמד C במבוא למדעי המחשב, זה תמיד CPP, ואם זה המקרה, אז כלל לא מדובר במשתנה גלובאלי!

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

3)בשביל מה שנית את המבנה שלי? ))), לא היה יותר קל להעביר את גודל המערך בתור פרמטר? ))))

נערך לאחרונה ע"י The_Equivocator בתאריך 12-07-2015 בשעה 18:28.
תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #28  
ישן 14-07-2015, 16:16
צלמית המשתמש של קוביבי
  משתמש זכר קוביבי קוביבי אינו מחובר  
מנהל פורום מערכות הפעלה - הרובע המייקרוסופטי.
 
חבר מתאריך: 07.10.04
הודעות: 13,777
LinkedIn profile
בתגובה להודעה מספר 27 שנכתבה על ידי The_Equivocator שמתחילה ב "1)אפשר להימנע בשימוש במשתנים..."

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

2. לא אמרתי שזה לא רקורסיית זנב, הבאתיא ת הקוד כדי להסביר לו על השאלה שלו וזהו, לא לשנות את הפתרון שלך שהיה נכון ועבד (מעבר ל return שדילגת עליו, אבל זה לא קריטי)

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

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

תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
תגובה

כלי אשכול חפש באשכול זה
חפש באשכול זה:

חיפוש מתקדם
מצבי תצוגה דרג אשכול זה
דרג אשכול זה:

מזער את תיבת המידע אפשרויות משלוח הודעות
אתה לא יכול לפתוח אשכולות חדשים
אתה לא יכול להגיב לאשכולות
אתה לא יכול לצרף קבצים
אתה לא יכול לערוך את ההודעות שלך

קוד vB פעיל
קוד [IMG] פעיל
קוד HTML כבוי
מעבר לפורום



כל הזמנים המוצגים בדף זה הם לפי איזור זמן GMT +3. השעה כעת היא 14:37

הדף נוצר ב 0.30 שניות עם 10 שאילתות

הפורום מבוסס על vBulletin, גירסא 3.0.6
כל הזכויות לתוכנת הפורומים שמורות © 2019 - 2000 לחברת Jelsoft Enterprises.
כל הזכויות שמורות ל Fresh.co.il ©

צור קשר | תקנון האתר