נושא: מבנה נתונים-רשימה מקושרת חלקית מעגלית

נשלח בתאריך: 04 April 2007 בשעה 19:13 | IP רשוּם

בס"ד

שלום!

אשמח אם תוכלו לעזור לי בשאלה הבאה-

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

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

ואיך מוצאים את מספר איבריה בסיבוכיות זמן O)n(?...

שאלה נוספת-

למדנו על מבנה הskiplist הו במבנה נתונים והן במונחה עצמים(ושמנו לב שיש הבדלים בינהם בצורת המימוש).רציתי לשאול על כמה מושגים-מה זה "ערכי דמה אינסוף בskiplist"? ומה זה "skiplist דטרמיניסטי"?

תודה רבה!

נשלח בתאריך: 06 April 2007 בשעה 12:49 | IP רשוּם

בס"ד

אם נרוץ עם 2 פויינטרים- אחד ישמור לי את תחילת המעגל והשני ירוץ- עד שיגיע לסוף ויחזור לתחילת המעגל.הבעיה היא שאני לא יודעת מתי מבחינתו הוא יחליט שהוא פותח מעגל. ז"א- הוא יכול להחליט שהאיבר במקום השלישי הוא תחילת המעגל ואז בסוף הרשימה המקושרת הוא יחזור לשם.באותה מידה הוא יכול להחליט שזה האיבר הרביעי וכך הלאה...

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

תודה על עזרתך!!

נשלח בתאריך: 06 April 2007 בשעה 16:01 | IP רשוּם

בס"ד

אני חושבת שאני יכולה להניח שיש לי מעגל בטוח. לכן השאלה של

while p1!=NULL היא לא רלוונטית עבורי- כי הוא צריך לחזור לקודקוד מסויים ןלא לNULL.

אז יוצא שאני צריכה בעצם לזכור כל קודקוד שביקרתי בו ולשאול אם P1 שאיתו אני רצה מצביע על אחד הקודקודים שעברתי בהם....

נשמע לי מסובך מדי...בטח פספסתי איזושהי נקודה...

אשמח לשמוע פתרון!

תודה!שבת שלום! 

נשלח בתאריך: 06 April 2007 בשעה 17:43 | IP רשוּם

בס"ד

אם אני מניחה שהרשימה שלי היא כולה מעגלית(ז"א מתחילה מהאיבר בראשון ) ולא חלקית, אז אני אאתחל את p__head-שישמור את האיבר הראשון במעגל.

אני יצור עוד פויינטר-p שכל עוד p לא מצביע על p_head הוא ירוץ. וככה בסופו של דבר אני אעצר כשאגיע לתחילת(שהוא גם סוף) המעגל.

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

מה קורה אם הוא לא מתחיל באיבר הראשון, ואני לא יודעת באיזה איבר הוא מתחיל ואין לי גם את המ"ס האיברים  של הרשימה המקושרת ע"מ להצביע על נקודת סיום?...

לי נגמרו הרעיונות......

נשלח בתאריך: 07 April 2007 בשעה 20:21 | IP רשוּם

בס"ד

שבוע טוב!
כן, המטרה היא לבדוק האם הרשימה היא חלקית מעגלית או לא.

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

בחלקית מעגלית האיבר שחוזר אחורה ע"מ לסגור מעגל מצביע על איבר שכבר ביקרתי בו.אבל איך אני אמורה לזכור את זה?

נשלח בתאריך: 08 April 2007 בשעה 14:30 | IP רשוּם

בס"ד

נכון!באמת לא שמתי לב לזה....מצאתי את הדרך!תודה!

נשלח בתאריך: 10 April 2007 בשעה 01:03 | IP רשוּם

שלום אסתי

מה התשובה?

איך את בודקת אם היא חלקית מעגלעת ב O)N(?

נשלח בתאריך: 10 April 2007 בשעה 10:13 | IP רשוּם

חבל שאין קורס שמלמדים בו איך לחשוב באופן עצמאי.

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

נשלח בתאריך: 11 April 2007 בשעה 09:53 | IP רשוּם

כי לא הצלחתי למצוא תשובה

ואני צריך להגיש תרגעל מחר

ומצטער שאני לא טוב בחידות

אני לא מבין איך ניתן לרוץ עם 2 פוינטרים כשאחד מתקדם מהר יותר ולמצוא אם היא חלקית מgגלית במעבר של O)N(

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

נשלח בתאריך: 11 April 2007 בשעה 11:31 | IP רשוּם

ובכל זאת אני אשמח להכוונה

אני לא מבין כפי שכתבתי איך לעשות את זה כיון שאני לא יודע איפה מתחיל המעגל בתוך הרשימה ולכן זה יכול לרוץ המון פעמים עד שזה ימצא שיש מעגל וזה בטח לא O)N(

אין לי מושג איך בודקים אם זה מעגלי ואת הגודל של הרשימה

נשלח בתאריך: 11 April 2007 בשעה 12:06 | IP רשוּם

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

תחשוב רגע - האם אתה באמת צריך לדעת איפה מתחיל המעגל בשביל לגלות שיש מעגל ?

אם אתה רץ עם 2 פויינטרים - כאשר אחד מתקדם בכל איטרציה 2 איברים והשני איבר אחד - האם הם ייפגשו איפשהו למעט בנקודת ההתחלה ?

נשלח בתאריך: 11 April 2007 בשעה 12:32 | IP רשוּם

את זה הבנתי לבד

אבל האם זה כבר לא יוצא יותר מO)N(?

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

נשלח בתאריך: 11 April 2007 בשעה 12:50 | IP רשוּם

זה לא יוצא יותר מ-O של n.

בוא נראה מה המקרה הגרוע:

המקרה הגרוע עבור רשימה בת n איברים הוא שכאשר הפויינטר ה"איטי" נכנס למעגל, הפויינטר ה"מהיר" מצביע על איבר אחד אחריו, כלומר הם לא ייפגשו עד שהפויינטר המהיר ישלים מעגל + מה שהפויינטר האיטי הספיק להתקדם - חצי מעגל, כלומר סה"כ מעגל וחצי.

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

אזי מס' הפעולות הכולל הוא 5*n עבור מס' האיברים שמחוץ למעגל, ו-5*1.5*n עבור מס' האיברים שבתוך המעגל. סה"כ:

לגבי מציאת נק' ההתחלה - נראה לי שחייבים סיבוכיות מקום נוספת כלשהי - מעבר ל-O של 1. שינוי מימוש הרשימה, שימוש ב-HASH TABLE עם הפויינטרים כמפתחות וכו'.

נשלח בתאריך: 11 April 2007 בשעה 13:09 | IP רשוּם

smile86 כתב: למה אני מרגישה בזומבט?...

מה זה זומבט ?

נשלח בתאריך: 11 April 2007 בשעה 13:17 | IP רשוּם

צחי@ כתב: smile86 כתב: למה אני מרגישה בזומבט?... מה זה זומבט ?

והמבין יבין...

צחי-תודה על העזרה.

נשלח בתאריך: 11 April 2007 בשעה 14:07 | IP רשוּם

smile86 כתב: צחי@ כתב: smile86 כתב: למה אני מרגישה בזומבט?... מה זה זומבט ? והמבין יבין... צחי-תודה על העזרה.

אז עכשיו אני יוצא בתור הזה שלא מבין ...

נשלח בתאריך: 16 December 2009 בשעה 13:42 | IP רשוּם

מדוייק, פשוט ונכון

קייטרינג