שתי שאלות בC

[ofir_yair]

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

void insert (stack s, Object *obj) {

if (obj==NULL) return;

if (top(s)!=*obj){

push(s, *obj);

}

obj=obj->next;

insert(s,obj);

}

switching to english:

assumptions:

stack is the data type you want to insert objects to, obj is a pointer to an object you want to insert.

your list is a linked list, where the last object points to a NULL value.

your list is already sorted in the right way.

top returns NUll when the stack is empty.

the stack is initialized as an empty stack

[orninyo]

במידה ואני לא משתמש בפונקצית מיון ואני שולח רשימה ממויינת מראש,

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

לדוגמא במקום להעתיק 90 80 30 1 היא תעתיק 1 30 80 90

Stack fromListToStack(const List L,Stack S)
{
	Position P=L;
	P=Advance(P);
	if (P)
	{
	 if (Top(S)!=Retreive(P))
	    Push(Retreive(P), S);
	 return fromListToStack(P,S);
	}
	else	
	return S;
}

[one123]

אז הנה פתרון אלגנטי וחמוד.

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

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

וכמובן - החזק מונה לוודא שאתה מסיים

[orninyo]

כבר חשבתי על זה אבל זה בלתי אפשרי בגלל האילוץ שאסור להשתמש בלולאות

אם אתה עדיין חושב שזה אפשרי אשמח אם תשתף אותי ברעיון יותר בפירוט

[ofir_yair]

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

[orninyo]

אהבתי את הרעיון, זה מה שעשיתי:

הבעיה שזה נכנס לי ללופ אינסופי ועף, בגלל שהP הפך להיות בעל איבר אחד (האיבר האחרון)

List SetP(const List L)
{
	Position P=L;
	if(!IsLast(P,P))
	{
		P=Advance(P);
		return SetP(P);
	}
	else
		return P;
}
Stack fromListToStack(const List L,Stack S)
{
	Position P=L;
	if(IsEmpty1(S))
		P=SetP(P);
	if (!First(P))
	{
	 if (Top(S)!=Retreive(P))
	    Push(Retreive(P), S);
	 P=FindPrevious(Retreive(P),P);
	 return fromListToStack(P,S);
	}
	else	
	return S;
}

[ofir_yair]

קודם כל מצטער על התגובה המאוחרת, הייתי קצת עסוק היום...

לגבי הקוד, יש כמה דברים שתיאלץ לפרט עליהם קצת יותר כדי שאוכל לעזור. למשל באיזה מקרה First(P) אמור לקבל NULL, כי אם אני משער נכון, FindPrevious מחזירה NULL כאשר אין איבר לפני הנוכחי, ואז בעצם אתה קורא לפונקציה First עם מצביע NULL.

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

הפונקציות:

First

FindPrevious

Top

Retreive

[Ghosthunter]

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

[orninyo]

unsigned -עוד לא למדתי מבני נתונים.

אופיר, הפונקציות שביקשת מצורפות:

   Position FindPrevious(ElementType X, List L)
   { 
    Position P;
    P=L;
     while (P->Next != NULL && P->Next->Element != X)
         P=P->Next;
      return P;
    } 

Position First(List L)
{
	return L->Next;
}

ElementType Retreive(Position P)
{
	return P->Element;
}

ElementType Top(Stack S)
 {
   if (!IsEmpty1( S )) return S->Next->Element;
   perror("Empty stack"); 
   return 0; /* return value used to avoid warning */ 
  }

[Ghosthunter]

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

[orninyo]

כן כבר עשיתי זאת והבנתי מה הבעיה, אבל אני לא יודע איך לפתור אותה

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

אני לא ידוע איך לעשות אותה כך שהיא תעשה את מה שהיא אמורה לעשות בלי לשנות את הרשימה..

[Ghosthunter]

תלך מהסוף להתחלה לא ע"י הפונקציות של הרשימה, אלא ע"י הרקורסיה עצמה.

[orninyo]

ניסיתי

Stack fromListToStack(const List L,Stack S)
{
	Position P=L;
	if(IsEmpty1(S)&&!IsLast(P,L))
	{
		P=Advance(P);
		return fromListToStack(P,S);
	}
	if (!First(P))
	{
	 if (Top(S)!=Retreive(P))
	   Push(Retreive(P), S);
	 P=FindPrevious(Retreive(P),P);
	 return fromListToStack(P,S);
	}
	else	
	return S;
}

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

היא מחזירה p->next עד שהוא לא Null

[Ghosthunter]

שים לב שהפונקציות האלה מחזירות אותו דבר -

!IsLast(P,L)

!First(P)

אתה אף פעם לא תגיע לIF השני.

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

[orninyo]

זה מודול מוכן שאסור לי לשנות, גם לי זה היה משונה .

גם כל המודולים של רשימות מקושרות שמצאתי בגוגל ממומשים אותו דבר [br]פורסם בתאריך: 26.09.2007 בשעה 20:58:30

---

בכל אופן הדד ליין שלי זה עד היום ב00:00

אז אני אגיש את זה ככה

תודה לכולם על העזרה