שתי שאלות בC

[orninyo]

איך אפשר לעשות שהפונקציה הזאת לא תשנה את L שבמיין?

Stack fromListToStack(const List L,Stack S)
{
	Position P=L,Head;
	Position TmpCell=L;
	ElementType i;
	bool flag;
	P=Advance(P);
	while(P)
	{
		Push(Retreive(P),S);
		i=(Retreive(P));
		Delete(Retreive(P),P);
		while(P)
		{
			flag=false;
			if(Retreive(P)==i)
			{
				Delete(Retreive(P),P);
				P=Advance(P);
				Head=Header(P);
				flag=true;
			}
			if(!flag)
				P=Advance(P);
		}
		P=Head;
	}
	return S;
}

איך אפשר למיין סטאק עם הפונקציות האלו?:

 #ifndef _Stack_h
 #define _Stack_h
 struct Node;
 typedef int ElementType ;
 typedef struct Node *PtrToNode;
 typedef PtrToNode Stack;
 int IsEmpty1(Stack S);
 Stack CreateStack(void);
 void DisposeStack(Stack S);
 void MakeEmpty1(Stack S);
 void Push(ElementType X, Stack S);
 ElementType Top(Stack S);
 void Pop(Stack S);
 #endif 

[שניצל]

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

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

[orninyo]

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

[k-o-b-y]

אתה חייב לבצע את המעבר מרשימה למחסנית ואת המיון בשני שלבים נפרדים?

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

[orninyo]

לא אני לא חייב

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

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

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

[SweeT_EviL]

תמיד אתה יכול להקל על עצמך ולהשתמש במערך עזר

[one123]

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

הרעיון פשוט: בשלב n : האיבר ה n - מקסימלי יהיה במחסנית המקורית במקום ה n מלמטה

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

בשלב ה n נעשה אותו הדבר רק שנעצור לאחר m-n צעדים (כי כבר מיינו n אלמנטים).

[k-o-b-y]

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

[orninyo]

אז זהו שלא הזכרתי שאסור לי להשתמש במחסניות ומערכי עזר.

קובי: שאני מוציא את האיברים מהמחסנית איפה אני שומר אותם בשביל להחזיר אותם אחרי זה?

ואיך יש לי גישה לאיברים שאחרי הTop ? הרי איך לי פונקציות advance או find

יש לכם אולי רעיון איך לבצע את ההכנסה (עם האילוץ שאסור להכניס אותו מספר פעמיים) בלי המחיקות המתבצעות על הרשימה?

כי אני צריך שבסוף הפעולה הרשימה תשאר כמו בהתחלה

[k-o-b-y]

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

[orninyo]

לא, גם אסור רשימות עזר

בלי קשר איך הייתה לי גישה לאיברים שאחרי הTop? במקרה שלא מוציאים את הTop

[k-o-b-y]

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

מהן הפעולות (פונקציות) שקיימות עבור רשימה אצלך?

[ofir_yair]

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

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

[SweeT_EviL]

אתה יכול לשנות את הרשימה הנתונה? או שצריך לשמור עליה?

[orninyo]

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

evil- אני לא יכול לשנות את הרשימה וזה הבעיה שלי עכשיו

קובי - אלה הפונקציות:

לרשימה : advance first isempty islast find delete previus insert header retrieve

למחסנית: push pop top isempty

וכמובן הפונקציות שיוצרות את הכותרים שלהם והפונקציות שמוחקות אותם.

עכשיו הבעיה שהפונקציה שעשיתי fromlisttostack לא טובה כי

1. היא משנה את הרשימה , ואני צריך שהרשימה תשאר כמו שהיא

2. היא מכניסה את האיברים בסדר ההפוך למה שאני צריך

ובלי קשר זה נראה לי ממוש מסורבל, למישהו יש אלגוריתם יותר חכם לעשות זאת?

אני צריך שהפונקציה תעתיק את האיברים מהרשימה למחסנית עם אילוץ לא להעתיק את אותו איבר פעמיים

והיא צריכה להיות רקורסיבית לחלוטין ללא לולאות.

אפשר לעשות פונקציות עזר. (שגם הן ללא לולאות)