ex3a.3 שרשרת חוליות

3a4.1 איחוד ממוין של רשימות מקושרות ללא כפילויות

link

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

דרישות:

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

הנחיות ליישום:

1. הגדירו מצביעים עבור כל אחת מהרשימות המקוריות (list1, list2) ועבור הרשימה החדשה שאתם בונים (resultHead, resultTail).
2. בצעו איטרציה על שתי הרשימות במקביל.
3. בכל שלב, השוו את הערכים של החוליות הנוכחיות משתי הרשימות:
4. אם אחד מהמצביעים הגיע לסוף הרשימה, הוסיפו את שאר האיברים מהרשימה השנייה (תוך כדי טיפול בכפילויות) לרשימה החדשה.
5. אם הערך בחוליה של list1 קטן מהערך בחוליה של list2, הוסיפו את הערך מ-list1 לרשימה החדשה (אם הוא לא כפילות של האיבר האחרון שנוסף) והתקדמו ב-list1.
6. אם הערך בחוליה של list2 קטן מהערך בחוליה של list1, הוסיפו את הערך מ-list2 לרשימה החדשה (אם הוא לא כפילות של האיבר האחרון שנוסף) והתקדמו ב-list2.
7. אם הערכים זהים, הוסיפו את הערך (רק פעם אחת) לרשימה החדשה (אם הוא לא כפילות של האיבר האחרון שנוסף) והתקדמו בשתי הרשימות.
8. זכרו לטפל במקרה שבו אחת הרשימות או שתיהן ריקות בהתחלה.

    public static Node<int> sortedUnionNew(Node<int> list1, Node<int> list2)
    {
        // Implement your solution here
        return null;
    }

3a4.2 איחוד ממוין של רשימות מקושרות עם חזרות

link

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

דרישות:

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

הנחיות למימוש:

1. צרו רשימה מקושרת חדשה ריקה שתשמש כרשימת הפלט.
2. השתמשו בשני מצביעים, אחד לכל רשימת קלט, כדי לעבור על הרשימות במקביל.
3. בכל שלב, השוו את האיברים הנוכחיים משתי הרשימות:
4. אם אחד מהאיברים קטן מהשני, הוסיפו אותו לרשימה החדשה והתקדמו במצביע של הרשימה ממנה נלקח האיבר.
5. אם האיברים שווים, הוסיפו את שניהם לרשימה החדשה (שמרו על הסדר) והתקדמו בשני המצביעים.
6. לאחר שאחת הרשימות מסתיימת, הוסיפו את כל האיברים הנותרים מהרשימה השנייה לרשימת הפלט.

שימו לב: יש לממש את הפעולה בתוך מחלקה סטטית בשם Solution.

public static Node<int> SortedUnionNewDuply(Node<int> list1, Node<int> list2)
{
    // Implement your solution here
    return null;
}

3a4.XX (כפילות עם SortedUnionNew 3a4.1) איחוד (union) רשימות ממויינות ללא כפילויות

למחוק את זה!

link

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

    public static Node<int> SortedUnionToList(Node<int> list1, Node<int> list2)
    {
        // Your implementation here
        return null; 
    }

3a4.4 הכנסת שלם לרשימה ממוינת

link

**רצוי לתת את השאלה גם בגרסה של הכנסת Node, ולקראת בגרות אפילו לדבר שם על Node with Comparator**

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

הנחיות:

1. שם הפעולה: insertIntoSortedList
2. חתימת הפעולה: הפעולה תקבל שני פרמטרים:
3. head: צומת ראשון של הרשימה המקושרת
4. number: המספר השלם שיש להכניס לרשימה.
5. ערך החזרה: הפעולה תחזיר את הצומת הראשון החדש של הרשימה המעודכנת
6. שמירה על מיון: ודאו שהרשימה נשארת ממוינת בסדר עולה לאחר הכנסת המספר.
7. מקרה קצה - הכנסה בראש הרשימה: טפלו במקרה שבו המספר החדש קטן מהאיבר הראשון ברשימה, ועליו להיות הצומת הראשון החדש.
8. מקרה קצה - רשימה ריקה: טפלו במקרה שבו הרשימה המקורית ריקה, והמספר החדש יהיה האיבר היחיד ברשימה.

    public static Node<int> insertIntoSortedList(Node<int> head, int number)
    {
        // Implement your solution here
        return null;
    }

3a4.111 חיתוך (intersect) רשימות מקושרות ניטרול כפילויות. מעבר יחיד

כנראה קשוח

link

תיאור המשימה

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

דרישות:

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

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

   public static Node SortedListsIntersection(Node list1, Node list2) { // Implement your solution here return null; }

3a4.5 מיון הכנסה לשרשרת חדשה

link

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

הנחיות למימוש

1. הגדרת המחלקה Solution: צרו מחלקה סטטית בשם Solution שתכיל את הפעולות הנדרשות.
2. מבנה הנתונים Unit4.Node: התרגיל מתבסס על מבנה הנתונים Unit4.Node המייצג צומת ברשימה מקושרת. לכל צומת יש שדה Value (מספר שלם) ושדה Next (מצביע לצומת הבא).
3. פעולת עזר InsertSorted:
4. כתבו פעולה סטטית פרטית בשם InsertSorted בתוך המחלקה Solution.
5. הפעולה תקבל שני פרמטרים: head (ראש רשימה מקושרת ממויינת) ו-newNode (צומת חדש שיש להכניס לרשימה).
6. תפקיד הפעולה הוא להכניס את newNode למקומו הנכון ברשימה הממויינת head, כך שהרשימה תישאר ממויינת.
7. הפעולה תחזיר את ראש הרשימה הממויינת החדשה.
9. פעולה ראשית insertionSort:
10. כתבו פעולה סטטית ציבורית בשם insertionSort בתוך המחלקה Solution.
11. הפעולה תקבל פרמטר אחד: head (ראש רשימה מקושרת לא ממויינת).
12. תפקיד הפעולה הוא למיין את הרשימה הנתונה באמצעות אלגוריתם מיון הכנסה, תוך שימוש בפעולת העזר InsertSorted.
13. הפעולה תחזיר את ראש הרשימה הממויינת החדשה.

דרישות נוספות

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

    private static Node<int> InsertSorted(Node<int> head, Node<int> newNode)
    {
        // Implement InsertSorted logic here
        return null; // Placeholder
    }

    public static Node<int> insertionSort(Node<int> head)
    {
        // Implement insertionSort logic here
        return null; // Placeholder
    }

3a4.111 מיון הכנסה (in-place) לשרשרת

link

במשימה זו, עליכם לממש את אלגוריתם מיון ההכנסה (Insertion Sort) עבור רשימה מקושרת. המיון צריך להתבצע ‘במקום’ (in-place), כלומר, עליכם לשנות את הקישורים בין החוליות הקיימות ברשימה מבלי ליצור חוליות חדשות.

הפעולה אותה תצטרכו לממש היא:

1. public static void InsertionSortInPlace(Node

תיאור המשימה:

קלט: הפעולה תקבל כפרמטר head המייצג את ראש הרשימה המקושרת שיש למיין.

פלט: הפעולה תחזיר את ראש הרשימה הממויינת

אלגוריתם מיון הכנסה:

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

``

דגשים חשובים:

1. מיון ‘במקום’ (In-Place): אסור ליצור חוליות Node חדשות. יש לשנות רק את הקישורים (השדות Next) של החוליות הקיימות.
2. טיפול במקרה של רשימה ריקה או חוליה בודדת: הפעולה צריכה לעבוד נכון גם עבור רשימות אלו.
3. עדכון ראש הרשימה: אם חוליה מוכנסת בתחילת הרשימה, יש לעדכן את הפרמטר head

    public static Node<int> InsertionSortInPlace(Node<int> head)
    {
        // Implement the insertionSortInPlace method here
        return null;
    }