מיון בחירה ברשימה מקושרת (חד כיוונית) -

[Second Edition]

הי,

אני מנסה לממש מיון בחירה ברשימה מקושרת , חד-כיוונית .

אני מסתבך עם המצביעים ..

ניסיתי לחפש בגוגל מימוש , אבל משום מה אין ..

טיפים ? עצות ? קישור ?

תודה !

- - - תגובה אוחדה: - - -

נ.ב-

מדובר ברשימה מקושרת של Integrs .

[שכיר חרב]

אתה יכול להשתמש בפונ' ההסרה/הוספה שאני מניח שכבר מימשת.

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

(אפשר לממש את ההסרה ב-O(1). כמובן שגם את ההוספה.)

[Second Edition]

נראה לי שהצלחתי , אולי נשארו מעט שינויים ..

השתמשתי בשמונה מצביעים :

per

curr

beforelargest

largest

this._head

temp

first

ועוד אחד ..

[Second Edition]

הנה מה שרשמתי ..

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

אם יש למישהו רעיון יותר אלגנטי ..

[LEFT]public class IntList
{
private IntNode _head;

public IntList ()
{
_head=null;
}

public IntList (IntNode node)
{
_head = node;
}


public IntList selectionSort ()
{
IntNode curr , per , blargest , largest , bfirst , first , temp ;
blargest=null;
bfirst=null;

largest=this._head;
first = largest ;
per = first ;
curr = this._head.getNext();

boolean flag = true ;


while (first.getNext() != null)
{
boolean foundlarger = false;

while (curr != null)
{
if(curr.getValue() > largest.getValue())
{
foundlarger=true;
blargest = per;
largest = curr;
}
per=curr;
curr=curr.getNext();
}//Inner while.


if(foundlarger == true)
{
temp = largest.getNext();
largest.setNext(first);
blargest.setNext(temp);

if(flag == true)
{
flag=false;
this._head = largest;
bfirst=this._head;
}
else
{
bfirst.setNext(largest);
bfirst=bfirst.getNext();
}
}



per=first;
curr=first.getNext();
largest=first;
first=first.getNext();
}//While loop

return this;


}//End of selectionSort.


[/LEFT]

- - - תגובה אוחדה: - - -

עבר להפתעתי הרבה קומפיילר ..

[Gil28]

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

[Second Edition]

אני עובר על חלק מהמבחנים הישנים ..

כך שלפתרון השאלה הספציפית , לא נראה לי , שאפשר להשתמש במה שאתה מתכוון אליו ..

אבל להרחבת אופקים , לאיזה פונקציה אתה מתכוון ?

[Gil28]

תכתוב פונקציה getMin שמקבלת מצביע לראש הרשימה המקושרת ומחזירה מצביע לאיבר המינימלי.