אהלן,

אני צריך למיין doubly-linked list with iterator בצורה רקורסיבית בלי שימוש בספריות המובנות בשפה.

יש לי קוד עובד של מיון מערך ואני מנסה להמיר אותו לעבוד על הרשימה אבל אני לא מצליח.

 /**
 * This method sorts the array by using merge sort
 * @param a array to be sorted
 */
 public static void mergeSort(int[] a)
 {
   if (a.length <= 1) return;
   int[] first = new int[a.length / 2];
   int[] second = new int[a.length - first.length];
   System.arraycopy(a, 0, first, 0, first. length);
   System.arraycopy(a, first.length, second, 0, second.length);
   mergeSort(first);
   mergeSort(second);
   merge(a, first, second);
 }

 /**
 * Merges two sorted arrays into one array
 * @param a array to save the results in
 * @param first the first sorted array
 * @param second the second sorted array
 */
 private static void merge(int[] a, int[] first, int[] second)
 {
   int iFirst = 0;
   // Next element to consider in the first array
   int iSecond = 0;
   // Next element to consider in the second array
   int j = 0;
   // Next open position in a

   // As long as neither iFirst nor iSecond past the end, move
   // the smaller element into a
   while (iFirst < first. length && iSecond < second. length)
   {
    if (first[iFirst] < second[iSecond])
    {
      a[j] = first[iFirst];
      iFirst++;
    }
    else
    {
      a[j] = second[iSecond];
      iSecond++;
    }
    j++;
   }

   // Note that only one of the two calls to arraycopy below
   // copies entries

   // Copy any remaining entries of the first array
   System.arraycopy(first, iFirst, a, j, first.length - iFirst);

   // Copy any remaining entries of the second half
   System.arraycopy(second, iSecond, a, j, second.length - iSecond);
  }

לכל Node ברשימה יש שדה data וכמובן שני מצביעים.

אשמח לכל עזרה, בעיקר עם הmethod הראשון.

תודה

while (iFirst < first. length && iSecond < second. length)

{

if (first[iFirst] < second[iSecond])

{

a[j] = first[iFirst];

iFirst++;

}

else

{

a[j] = second[iSecond];

iSecond++;

}

j++;

}

לגבי הבלוק הנ"ל

בגלל המבנה של הרשימה המקושרת זה לא עובד

במקום תחליף בין כל שני פוינטרים שכנים.

יש לך 2 תאים שכנים

אקושילירבק עם העיברית הזו !!!!

[ק:מידע1:ה]-->[ק:מידע2:ה]

אם מידע1>מידע2 אתה צריך לבצע השמה ולקבל:

[ק:מידע2:ה]-->[ק:מיד1:ה]

כאשר ה. הוא פויינטר אל התא הבא

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